CPU Cache
  指令缓存 instruction cache
  数据缓存 data cache
    多级缓存 L1 L2 L3 L4
  旁路转换缓冲 TLB (translation lookside buffer, part of MMU)
缓存记录 cache entry
  缓存线 cache line : 固定大小,数据拷贝,内存地址(memory location, tag), 标志(flag, invalid bit, dirty bit)
  替换策略: 最近最少使用(LRU)
  写策略: 写通过(write-through), 回写(write-back), 缓存一致性协议, DMA, multi-core
  CPU 和 内存之前通过 Cache 架起桥梁,消除鸿沟(gap)
  CPU 在缓存未命中而访问内存并创建缓存线的等待状态称为闲置(Stall)
  为消除CPU的闲置(keep cpu busy),引入了乱序执行(out-of-order execution), 超线程(hyper-threading, HT)技术
缓存未命中 cache miss
  读 miss:取指令,取数据
  写 miss:队列 store buffer
内存管理单元 MMU
  虚拟内存 virtual memory
  virtual address To physical address
  TLB (translation lookside buffer)
  page table, segment table
  MESI: Modified, Exclusive, Shared, Invalid
    Read Response
    Invlaidate Acknowledge
    Read Invalidate
  CPU 闲置 Stall
    Memory Barriers
    Store Buffer
      Store Forwarding
    Invalidate Queue

硬件同步原语 Hardware synchronization primitives
  Compare and swap (CAS)
    atomic test-and-set operation / atomic read-modify-write sequence
    On Intel processors, compare-and-swap is implemented by the cmpxchg family of instructions.
    A CAS operation includes three operands -- a memory location (V),
      the expected old value (A), and a new value (B).
    CAS effectively says "I think location V should have the value A; if it does, put B in it,
      otherwise, don't change it but tell me what value is there now.

无锁编程 lockless programming
  原子操作 atomic operation
      _InterlockedIncrement on Win32
      _InterlockedCompareExchange on Win32
  Memory Ordering
    compiler reordering / processor reordering
    内存屏障/栏栅 memory fence/barrier

锁 lock
  自旋锁 spinlock

  lock overhead: the extra resources for using locks, like the memory space allocated for locks, the CPU time to initialize and destroy locks, and the time for acquiring or releasing locks. The more locks a program uses, the more overhead associated with the usage;
  lock contention: this occurs whenever one process or thread attempts to acquire a lock held by another process or thread. The more fine-grained the available locks, the less likely one process/thread will request a lock held by the other. (For example, locking a row rather than the entire table, or locking a cell rather than the entire row.);
  deadlock: the situation when each of at least two tasks is waiting for a lock that the other task holds. Unless something is done, the two tasks will wait forever.




睡眠 0 1 -1




Memory fences / Memory barrier

自旋锁 SpinLock
  忙等 busy waiting

事件 Event
  ManualResetEvent 惊群
信号量 Semaphore

互斥锁 Mutex
  递归锁 Recursion
  线程所有权 Thread Ownership

读写锁 ReadWritLock

混合锁 Hybrid Lock
  用户模式 + 内核模式

异步 IO

A thread waiting on a construct might block forever if the thread currently holding the construct
never releases it. If the construct is a user-mode construct, the thread is running on a CPU forever, and
we call this a livelock. If the construct is a kernel-mode construct, the thread is blocked forever, and we
call this a deadlock. Both of these are bad, but of the two, a deadlock is always preferable to a livelock,
because a livelock wastes both CPU time and memory (the thread’s stack, etc.), while a deadlock wastes
only memory.

Context SWitch

Kernel Mode / User Mode

Volatile / Memory fences

Volatile’s Read method performs an atomic read operation, and its Write method performs an
atomic write operation. That is, each method performs either an atomic read operation or an atomic
write operation. 


atomic read and write operation

Thread / logic CPU

Hyperthreaded CPU
  let only one thread run at a time

  executes a special CPU instructions; 
  A thread can force itself to pause, allowing a hyperthreaded CPU
    to switch to its other thread
Sleep(0) Sleep(-1) Sleep(1)

User-Mode Constructs

Kernel-Mode Constructs


  Single-instance Application

    Events are simply Boolean variables maintained by the kernel.
    true / false
    unblock / block
    AutoSet: unblock a thread then set event to false
    ManualSet: unblock all thread, set event to false yourself

    SpinWait based autoresetwaithandle:
      forces the calling thread to transition from managed code to the kernel and back—which is bad. But when there is contention, the losing thread is blocked by the kernel and is not spinning and wasting CPU cycles—which is good.
    Semaphores are simply Int32 variables maintained by the kernel. A thread waiting on a semaphore blocks when the semaphore is 0 and unblocks when the semaphore is greater than 0. When a thread waiting on a semaphore unblocks, the kernel automatically subtracts 1 from the semaphore’s count.
    A Mutex represents a mutual-exclusive lock. It works similar to an AutoResetEvent or a Semaphore with a count of 1 since all three constructs release only one waiting thread at a time.
    recursion count
    Usually a recursive lock is needed when a method takes a lock and then calls another method that also requires the lock

  Hybrid Constructs
    Spinning / Thread OwnerShip / Recursion

    Monitor / lock
      Sync block index
      public / private lock object
      Recusion / Thread Ownership / upgrade
      This construct blocks a thread until its internal counter reaches 0.

Instead, you should use the thread pool to rent threads for short periods of time. So, a thread
pool thread starts out spell checking, then it changes to grammar checking, and then it changes again
to perform work on behalf of a client request, and so on.

In addition, avoid using recursive locks (especially recursive reader-writer locks) because they hurt
performance. However, Monitor is recursive and its performance is very good.77 Also, avoid releasing
a lock in a finally block because entering and leaving exception-handling blocks incurs a
performance hit, and if an exception is thrown while mutating state, then the state is corrupted, and
other threads that manipulate it will experience unpredictable behavior and security bugs.

In the CLR, calling any lock method is a full memory fence, and any variable writes you have before the fence must complete before the fence and any variable reads after the fence must start after it.

Double-Check Locking

Condition Variable Pattern
  • https://www.ibm.com/developerworks/java/library/j-jtp11234/