Synchronization Primitives

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

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

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

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

信号量

信号量是确保两个或多个过程之间 互斥 的最古老和最广泛使用的方法之一。 信号量是 (通常) 初始化为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”，因此可以用作多处理器代码的简单锁。 __ 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将错误地检测到可能的内存顺序违规，从而导致巨大的额外性能损失。 将暂停指令放入旋转锁中，以避免这种不良行为。 有关更多信息，请参阅 pentium4/manuals/index_new.htm 英特尔手册。

另见

论坛主题

• Userland only Semaphores
• Spinlocks that disable interrupts
• SMP compatibility
• Mutex Implementation
• Mutexs, Spinlocks and all that jazz
• Spinlocks & Semaphores

外部链接

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