Synchronization Primitives - 版本历史

2022年2月5日 (六) 14:27 Zhang3

2022-02-05T14:27:00Z

←上一版本		2022年2月5日 (六) 14:27的版本
第1行：		第1行：
	这里介绍的所有技术都是解决 ''~~进程同步~~'' ~~问题的基本构建块。例如，给定在同一台机器上彼此独立运行的程序，如何实现一些特性确保允许哪些操作组合和不允许哪些操作组合。~~		这里介绍的所有技术都是解决 ''进程同步（process synchronization）'' 问题的基本功能块。例如，给定在同一台机器上彼此独立运行的程序，如何实现确保同时允许哪些操作组合和不允许哪些操作组合。

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

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


	== 信号量 ==		== 信号量 Semaphores==

	信号量是确保两个或多个过程之间 [[Mutual Exclusion\|互斥]] 的最古老和最广泛使用的方法之一。信号量是 (通常) 初始化为1的特殊整数变量，只能通过一对函数进行更改。这些函数中的每一个，在历史上被称为 “p” 和 “v” (来自荷兰语单词 “proceren”尝试和 “verhogene”增量) 都必须是 [[Atomic operation\|原子操作]]。每个信号量都有一个关联的队列，用于记录那些等待它保护资源的进程。		信号量是确保两个或多个过程之间 [[Mutual Exclusion\|互斥]] 的最古老和最广泛使用的方法之一。信号量是 (通常) 初始化为1的特殊整数变量，只能通过一对函数进行更改。这些函数中的每一个，在历史上被称为 “p” 和 “v” (来自荷兰语单词 “proceren”尝试和 “verhogene”增量) 都必须是 [[Atomic operation\|原子操作]]。每个信号量都有一个关联的队列，用于记录那些等待它保护资源的进程。
第49行：		第49行：
	== 自旋锁 Spinlocks ==		== 自旋锁 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> 虚拟操作码)。		[[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上使用可能会获得更高的吞吐量。		虽然使用不当的自旋锁将导致单cpu系统的严重性能下降，但明智地在多cpu上使用可能会获得更高的吞吐量。

	~~如果你使用的是GCC，则它提供了一组~~ [https://gcc.gnu.org/onlinedocs/gcc-8.3.0/gcc/_005f_005fsync-Builtins.html 原子内置程序]，可用于实现自旋锁。 ~~以下示例确保了~~ “full ~~barrier”，因此可以用作多处理器代码的简单锁。~~ ''__ sync_bool_compare_and_swap ''是一个原子指令，它简单地检查给定指针后面的值是否等于第二个参数，如果是，就用第三个参数替换它并返回true-否则它什么都不做，返回false,这样以下代码中我们的锁就不断处于自旋中:		如果你使用的是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">		<source lang="c">
	typedef volatile int mutex_t;		typedef volatile int mutex_t;
第71行：		第71行：
	</source>		</source>

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

	== 另见 ==		== 另见 ==

Zhang3：创建页面，内容为“这里介绍的所有技术都是解决 ''进程同步'' 问题的基本构建块。例如，给定在同一台机器上彼此独立运行的程序，如何实现一些特性确保允许哪些操作组合和不允许哪些操作组合。在现实世界问题的其他示例中，我们正在寻找可以授予以下功能的技术: * 进程的互斥: 一部分代码不能同时由两个进程执行。 * 会合: 在其他进程完成其操作之前，一个进…”

2022-02-05T14:15:08Z

创建页面，内容为“这里介绍的所有技术都是解决 ''进程同步'' 问题的基本构建块。例如，给定在同一台机器上彼此独立运行的程序，如何实现一些特性确保允许哪些操作组合和不允许哪些操作组合。在现实世界问题的其他示例中，我们正在寻找可以授予以下功能的技术: * 进程的互斥: 一部分代码不能同时由两个进程执行。 * 会合: 在其他进程完成其操作之前，一个进…”

新页面

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

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

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

== 信号量 ==

信号量是确保两个或多个过程之间 [[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”，因此可以用作多处理器代码的简单锁。 ''__ 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]]