Synchronization Primitives

这里介绍的所有技术都是解决 进程同步（process synchronization） 问题的基本功能块。例如，给定在同一台机器上彼此独立运行的程序，如何实现确保同时允许哪些操作组合和不允许哪些操作组合。

在现实世界问题的其他示例中，我们正在需要可以实现以下功能的技术:

进程的互斥: 一部分代码不能同时由两个进程执行。
进程会合: 在其他进程完成其操作之前，一个进程不得执行一项操作 (例如生成摘要)。
共享读者/单一写者的资源锁定方法: 许多进程可能同时读取一个表，但是一次只能写入一个表，且写操作同时应该阻止读者访问该表，直到表返回到一致状态为止。

注意: 良好的同步实现不仅应保证 正确，而且还应保证 公平 (所有进程都有平等的机会获得访问权限) 和 非饥饿 (任何等待进程最终都将拥有资源)。

信号量 Semaphores

信号量是确保两个或多个过程之间互斥的最古老和最广泛使用的方法之一。信号量是 (通常) 初始化为1的特殊整数变量，只能通过一对函数进行更改。这些函数中的每一个，在历史上被称为 “p” 和 “v” (来自荷兰语单词 “proceren”尝试和 “verhogene”增量) 都必须是原子操作。每个信号量都有一个关联的队列，用于记录那些等待它保护资源的进程。

函数 “p”，也称为 wait() (或 test())，使信号量的值递减，如果信号量为负，将进程放在等待队列中，直到信号量被持有它的进程释放。

函数 “v”，也称为 signal() (或 release())，增加信号量，如果仍然为负，则指示调度程序唤醒队列中的下一个等待过程。

请注意，一般的信号量可以做的不仅仅是保证相互排斥。例如，可以通过使用一个信号量计数 “有多少消息可用” 和另一个计数 “有多少空闲槽可用” 来实现某些FIFO队列 (单个读取器和单个写入器)

 Message queue[N];
 Semaphore slots=new Semaphore(N);
 Semaphore messages=new Semaphore(0);
 int last_read=0, last_written=0;
 
 Message get() {
   Message m;
   messages.wait();
   m=queue[last_read]; last_read=(last_read+1)%N;
   slots.signal();
   return m;
 }
 
 void put(Message m) {
   slots.wait();
   queue[last_written]=m; last_written=(last_written+1)%N;
   messages.signal();
 }

互斥 Mutexes

对此的一种变体，称为 “二进制信号量”，使用布尔值而不是整数。在这种情况下，“p” 测试信号量的值，如果为true，则将其设置为false，如果为false，则等待。二进制 “v” 函数检查等待队列，如果它为空，则将信号量设置为true; 否则，它指示调度程序唤醒下一个排队的进程。

无论哪种形式，重要的是，一旦进程使用完它保护的资源，就释放信号量，否则资源可能无法访问。

请注意，虽然 “信号量” 是全球唯一的语义项，但仅说 “互斥体” 是一个模糊的名称，不同系统的设计人员倾向于拥有 “各自的互斥体”所指内容，具体比如像是自旋锁，或者二进制信号量，或者一般说信号量...

自旋锁 Spinlocks

自旋锁同样是要处理互斥问题，但是如果资源繁忙，则自旋锁无需依赖额外的调度程序基础结构来使进程休眠。相反，spinlock将持续检查该值，直到它发生变化，并且通常依赖于CPU上的一些原子指令 test_and_set 来执行其任务 (请参阅英特尔手册，以了解如何使用 xchg 模拟 test_and_set 虚拟操作码)。

虽然使用不当的自旋锁将导致单cpu系统的严重性能下降，但明智地在多cpu上使用可能会获得更高的吞吐量。

如果你使用的是GCC，它提供了一组原子内置程序，可用于实现自旋锁。以下示例使用了 “full barrier”（译者注：这里指的是一种编译选项，具体请搜索 full memory barrier 完全内存屏障），因此可以用作多处理器代码的一种简单锁。 __ sync_bool_compare_and_swap 是一个原子指令，它简单地检查给定指针后面的值是否等于第二个参数，如果是，就用第三个参数替换它并返回true-否则它什么都不做，返回false,这样以下代码中我们的锁就不断处于自旋中:

typedef volatile int mutex_t;

void acquire_mutex(mutex_t* mutex)
{
	while(!__sync_bool_compare_and_swap(mutex, 0, 1))
	{
		asm("pause");
	}
}

void release_mutex(mutex_t* mutex)
{
	*mutex = 0;
}

* IA-32程序员注意事项 *: 如果你考虑使用spinlocks，请注意，随着spinloop完成，P4/Xeon cpu将错误地检测到可能的内存顺序违规，从而导致巨大的额外性能损失。将暂停指令放入自旋锁中，以避免这种不良行为。有关更多信息，请参阅英特尔手册。

另见

论坛主题

外部链接

Spinlocks and Read-Write locks - 展示某些类型的自旋锁和读写锁的基本代码