查看“Synchronization Primitives”的源代码

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

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

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


== 信号量 Semaphores==

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

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

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

请注意，一般的信号量可以做的不仅仅是保证相互排斥。 例如，可以通过使用一个信号量计数 “有多少消息可用” 和另一个计数 “有多少空闲槽可用” 来实现某些FIFO队列 (单个读取器和单个写入器)
<source lang="c">
 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();
 }
</source>

== 互斥 Mutexes ==

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

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

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

== 自旋锁 Spinlocks ==

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

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

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

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

== 另见 ==
=== 论坛主题 ===
*[[Topic:9440|Userland only Semaphores]]
*[[Topic:10363|Spinlocks that disable interrupts]]
*[[Topic:9699|SMP compatibility]]
*[[Topic:14261|Mutex Implementation]]
*[[Topic:11903|Mutexs, Spinlocks and all that jazz]]
*[[Topic:7500|Spinlocks & Semaphores]]

=== 外部链接 ===
*[http://locklessinc.com/articles/locks/ Spinlocks and Read-Write locks] - 展示某些类型的自旋锁和读写锁的基本代码

[[Category:IPC]]
[[Category:Synchronization]]