数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学硬件同步
在硬件同步中，我们探索了更多解决临界区问题的方案，这些方案使用了从基于硬件到基于软件的API等多种技术，这些API可供应用程序程序员使用。这些解决方案基于锁定的前提；但是，此类锁的设计可能非常复杂。
这些硬件特性可以简化任何编程任务并提高系统效率。在这里，我们介绍一些许多系统上都可用的简单硬件指令，并展示如何有效地使用它们来解决临界区问题。如果我们能够防止在修改共享变量时发生中断，则可以在单处理器环境中简单地解决临界区问题。通过这种方式，我们可以确保当前指令序列能够按顺序执行而不会被抢占。不会执行其他指令，因此不会对共享变量进行意外修改。非抢占式内核采用的就是这种方法。但不幸的是，这种解决方案在多处理器环境中并不那么可行。由于消息被传递到所有处理器，因此在多处理器上禁用中断可能非常耗时。
当此消息传递延迟进入每个临界区时，系统效率会降低。如果时钟由中断保持更新，则还会考虑对系统时钟的影响。因此，许多现代计算机系统都提供特殊的硬件指令，允许我们以原子方式测试和修改字的内容或交换两个字的内容——也就是说，作为一个不可中断的单元。我们可以使用这些特殊指令以相对简单的方式解决临界区问题。现在我们抽象出这些指令背后的主要概念。TestAndSet() 指令可以定义如下所示。
boolean test and set(boolean *target){
boolean rv = *target;
*target = true;
return rv;
}TestAndSet() 指令的定义。
其基本特征是此指令以原子方式执行。因此，如果同时执行两个 TestAndSet() 指令（每个指令在不同的 CPU 上），则它们将按某种任意顺序顺序执行。如果机器支持 TestAndSet() 指令，我们可以通过声明一个初始化为 false 的布尔变量 lock 来实现互斥。进程 P 的结构如下所示。
示例
do {
while (test and set(&lock)) ;
/* do nothing */
/* critical section */
lock = false;
/* remainder section */
}
while (true);使用 TestAndSet() 实现互斥。
与 TestAndSet() 指令相反，Swap() 指令操作于两个字的内容；它以原子方式执行。如果机器支持 Swap() 指令，则可以如下提供互斥。这里，声明一个全局布尔变量 lock 并将其初始化为 false。此外，每个进程都有一个局部布尔变量 key。进程 P 的结构如下图所示。
int compare_and_swap(int *val, int expected, int new val){
int temp = *val;
if (*val == expected)
*val = new val;
return temp;
}Compare and Swap() 指令的定义。
do{
while (compare_and_swap(&lock, 0, 1) != 0) ;
/* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}
while (true);使用 Compare and Swap() 指令实现互斥。
由于这些算法满足互斥要求，因此它们不满足有界等待要求。在下面的代码中，我们介绍了另一个使用 TestAndSet() 指令的算法，该算法满足所有临界区要求。
do{
waiting[i] = true;
key = true;
while (waiting[i] && key)
key = test and set(&lock);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = false;
else
waiting[j] = false;
/* remainder section */
}
while (true);使用 TestAndSet() 实现有界等待互斥。
相同的数据结构是 boolean waiting[n]; boolean lock; 这些数据结构初始化为 false。为了证明满足互斥要求，我们注意到进程 P; 只有当 waiting[i] == false 或 key == false 时才能进入其临界区。只有当执行 TestAndSet() 时，key 的值才能变为 false。第一个执行 TestAndSet() 的进程将发现 key == false；所有其他进程都必须等待。只有当另一个进程离开其临界区时，变量 waiting[i] 才能变为 false；只有一个 waiting[i] 设置为 false，从而保持互斥要求。
为了证明满足进展要求，我们注意到为互斥提出的论点也适用于此，因为进程退出临界区要么将 lock 设置为 false，要么将 waiting[j] 设置为 false。两者都允许等待进入其临界区的进程继续执行。为了证明满足有界等待要求，我们注意到，当一个进程离开其临界区时，它会以循环顺序 (i + 1, i + 2,..., n - 1, 0, ..., i - 1) 扫描数组 waiting。它将此顺序中第一个处于入口段 (waiting[j] == true) 的进程指定为下一个进入临界区的进程。
任何等待进入其临界区的进程都将在 n - 1 个轮次内这样做。不幸的是，对于硬件设计人员而言，在多处理器上实现原子 TestAndSet() 指令并非易事。
14K+ 次浏览
