Process Synchronization(进程同步)

2017-04-04

Background

对共享数据的并发请求会导致数据的不一致
维持数据的一致需要一个能确保共享同一逻辑地址的协作进程可以有序地执行

The Critical-Section Problem(临界区问题)

何为临界区

每个进程有一个代码段称为临界区，在该区中进程可能改变共同变量、更新一个表、写一个文件等。这种系统的重要特征是当一个进程进入临界区，没有其他进程可被允许在临界区内执行，即没有两个进程可同时在临界区内执行。

何为临界区问题

临界区问题是设计一个以便进程协作的协议。每个进程必须请求允许进入临界区，实现这一请求的代码段称为进入区(entry section)，临界区之后可有退出区(exit section)，其他代码为剩余区(remainder section)。

通用结构

如何解决临界区问题

强制实施互斥：在具有关于相同资源或共享对象的临界区的所有过程中，一次只允许一个进程进入临界区；
一个在非临界区的进程必须不干涉其他进程；
不允许一个需要访问临界区的进程被无限延迟；
没有进程在临界区时，任何需要进入临界区的进程必须能够立即进入
相关进程的速度和处理器数目没有任何要求和限制
一个进程阻留在临界区中的时间必须时有限的

有空让进；无空等待；择一而入；算法可行

Peterson‘s Solution

经典的基于软件的临界区问题的解答。
适用于两个进程在临界区与剩余区之间交替执行。
LOAD 和 STORE 指令是原子型(atomic)的指令，即该指令不能被中断，或者说指令要么完全执行，要么完全不执行。

1 2	int turn; boolean flag[2];

peterson

Peterson算法适用于两个进程在临界区与剩余区交替执行。

通过证明三个条件成立证明算法可行：

互斥成立
前进要求满足
有限等待要求满足

Synchronization Hardware(硬件同步)

Peterson算法是基于软件的临界区问题的解决，同样，也可以通过硬件来实现。

对于单处理器的环境，临界区问题可简单地解决：在修改共享变量时，禁止中断出现。这样，就能确保当前指令序列地执行不会被中断。由于其他指令不可能执行，所以共享变量也就不会被意外修改。

然而，在多处理器地环境下，这种方法因为效率地原因行不通，因此现代计算机系统提供了特殊硬件指令以允许能原子地(不可中断地)检查和修改字的内容或交换两个字的内容。可以使用这些特殊指令来相对简单地解决临界区问题。

指令TestAndSet()的特点是该指令能原子地执行。因此，如果两个指令TestAndSet()同时执行在不同的CPU上，那么它们会按照任意顺序来执行。这样可以实现互斥。

testandset

因为在while的判断语句中的TestAndSetLock(&lock)是原子型的指令因此其在执行时不会被中断，也就是在这个指令执行之后，能够获得期待获得的结果，而不会因为该指令在执行的过程中被中断而导致lock的值被改变，从而导致未知的结果

例如：有两个指令TestAndSet()同时执行在不同的CPU上时，那么它们会按照任意顺序来顺序执行。而不会将TestAndSet()指令拆分为更小的指令交替执行。

testandset_instruction

缺点

对不能进入临界区的进程，采用忙等待，浪费CPU时间。
将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。

Semaphores(信号量)

什么是信号量

信号量S是个整数变量，除了初始化外，它只能通过两个标准原子操作：wait()和signal()来访问。这些操作被称为P和V操作。

在wait()和signal()操作中，对信号量整型值的修改必须不可分地执行，即当一个进程修改信号量值时，不能有其他进程同时修改同一信号量的值。

为了克服忙等待，可以修改信号量wait()和signal()的定义。当一个进程执行wait()操作时，发现信号量不为正，则它必须等待。这里的等待是阻塞(block)自己。即将一个进程放入到与信号量相关的等待队列中，并将该进程的状态切换为等待状态。然后将控制转到CPU调度程序，以选择另一个进程来执行。(相对于忙等待，这种方法需要消耗部分时间在上下文切换)

一个被阻塞在等待信号量S上的进程，可以在其他进程执行了signal()操作之后被重新执行(通过wakeup()操作来实现)，该操作将进程从等待状态切换到就绪状态然后放入就绪队列。

typedef struct {
  int value;
  struct process *list;
}semaphore;

wait()操作的实现：

wait(semaphore *S) {
  S->value--;
  if (S->value < 0) {
    add this process to S->list;
    block();
  }
}

signal()操作的实现：

signal(semaphore *S) {
  S->value++;
  if (S->value <= 0) {
    remove a process P from S->list;
    wakeup(P);
  }
}

如果信号量的值为负，那么其绝对值就是等待该信号量的进程的个数。

信号量的关键之处是它们原子地执行。必须确保没有两个进程同时对同一信号量执行操作wait()和signal()。

上述地情况也属于临界区问题，wait和signal方法的原子实现，单处理器环境只需要通过在执行wait()和signal()操作时禁止中断来解决。但是在多处理器环境下，则必须提供其他加锁技术(如自旋锁)，以确保wait()和signal()可原子地执行。

必须承认对于这里的wait()和signal()操作的定义，并没有完全取消忙等待，而是取消了应用程序进入临界区的忙等。而且，将忙等限制在操作wait()和signal()的临界区内，这些区比较短。因此，临界区几乎不被占用，忙等很少发生，且所需时间很短。

Deadlock and Starvation(死锁和饥饿)

什么是死锁

具有等待队列的信号量的实现可能导致这样的情况：两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生。这里的事件是signal()操作的执行。当出现这样的状态，这些进程就称为死锁。

什么是饥饿

饥饿也叫做无限期阻塞(indefinite blocking)，即进程在信号量内无限期等待。如果对与信号量相关的链表按LIFO顺序来增加和移动进程，那么可能会发生无限期阻塞

Classic Problems of Synchronization

Bounded-Buffer Problem(有限缓冲问题)

三个信号量，分别初始化：full = 0, empty = n, mutex = 1

其中mutex的作用是记录访问这个仓库（缓冲区）的进程的数量。
Readers and Writers Problem(读者写者问题)

有两组并发进程：读者和写者，共享一个文件F，要求：

任意多个读者可以同时读取文件；

一次只有一个进程可以往文件中写；

写进程执行写操作前，禁止任何文件读取文件
读-读允许，读-写互斥，写-写互斥
如果读者到：
- 无读者、写者，新读者可以读
- 有写者等，但有其他读者正在读，则新读者也可以读
- 有写者写，新读者等
如果写者到：
- 无读者，新写者可以写
- 有读者，新写者等待
- 有其他写者，新写者等待
如果读者优先，可能导致写进程长时间等待，出现写进程被饿死；实际的系统是写者优先，即当有进程在读文件时，如果有新进程请求写，那么新的读进程被拒绝。

信号量mutex和wrt初始化为1；readcount初始化为0.信号量wrt供写者作为互斥信号量；信号量mutex用于确保在更新变量readcount时的互斥。变量readcount用来跟踪有多少进程正在读对象。
Dining-Philosophers Problem(哲学家吃饭问题)