“Synchronization Primitives”的版本间差异

来自osdev
跳到导航 跳到搜索
(创建页面,内容为“这里介绍的所有技术都是解决 ''进程同步'' 问题的基本构建块。 例如,给定在同一台机器上彼此独立运行的程序,如何实现一些特性确保允许哪些操作组合和不允许哪些操作组合。 在现实世界问题的其他示例中,我们正在寻找可以授予以下功能的技术: * 进程的互斥: 一部分代码不能同时由两个进程执行。 * 会合: 在其他进程完成其操作之前,一个进…”)
 
 
第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 英特尔手册]。'''


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

2022年2月5日 (六) 14:27的最新版本

这里介绍的所有技术都是解决 进程同步(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将错误地检测到可能的内存顺序违规,从而导致巨大的额外性能损失。 将暂停指令放入自旋锁中,以避免这种不良行为。 有关更多信息,请参阅 英特尔手册

另见

论坛主题

外部链接