进程同步

协作进程是可以在系统内执行的其他进程相互影响的进程。互相协作的进程可以直接共享逻辑地址空间（即代码和数据），或者只通过文件或消息来共享数据。前者可通过轻量级进程或线程来实现。共享数据的并发访问可能会产生数据的不一致。本部分讨论各种机制，以用于确保共享同一逻辑地址空间的协作进程有序地执行，从而能维护数据的一致性。

多个线程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关，称为竞争条件（race condition）。为了避免竞争条件，需要确保一段时间内只有一个进程能操作变量counter。为了实现这种保证，要求进行一定形式的进程同步。

这种情况经常出现在操作系统中，因为系统的不同部分操作资源。显然，需要这些变化不会互相影响。

临界区问题

假设某个系统有n个进程。每个进程有一个代码段称为临界区（critical section）,在该区中进程可能改变共同变量、更新一个表、写一个文件等。这种系统的重要特征是当一个进程进入临界区，没有其他进程可被允许在临界区内执行，即没有两个进程可同时在临界区内执行。临界区问题（critical-section proble）是设计一个以便进程协作的协议。每个进程必须请求允许进入其临界区。实现这一请求的代码段称为进入区（entry section）,临界区之后可能有退出区(exit section),其他代码为剩余去（remainder section）。

临界区问题的解答必须满足如下三项要求：
互斥(mutual exclusion):如果进程P在其临界区内执行，那么其他进程都不能在其临界区内执行。

前进（progress）: 如果没有进程在其临界区内执行且有进程需要进入临界区，那么只有那些不再剩余区内执行的进程可参加选择，以确定谁能下一个进入临界区，且这种选择不能无限推迟。

有限等待（bounded waiting）:从一个进程做出进入临界区的请求，直到该请求允许为止，其他进程允许进入其临界区的次数有上限。

假定每个进程的执行速度不为0。然而，不能对n个进程的相对速度（relative speed）做任何假设。

一个操作系统，在某个时刻，可同时存有多个处于内核模式的活动进程。因此，实现操作系统的代码（内核代码（kernel code））会出现竞争条件。例如，以系统内维护打开文件的内核数据结构链表为例。当新打开或关闭一个文件时，这个链表需要更新（向链表增加一个文件或删除一个文件）。如果两个进程同时打开文件，那么这两个独立的更新擦欧总可能会产生竞争条件。其他会导致竞争条件的内核数据结构包括维护内存分配，维护进程列表及处理中断处理程序的数据结构。内核开发人员有必要确保其操作系统不会产生竞争条件。

有两种方法用于处于操作系统内的临界问题：抢占内核（preemptive kernel）与非抢占内核（nonpreemptive kernel）。抢占内核允许处于内核模式的进程被抢占，非抢占内核不允许处于内核模式的进程被抢占。处于内核模式运行的进程会一直运行，直到它退出内核模式、阻塞或自动退出CPU的控制。显然，非抢占内核的内核数据结构根本上不会导致竞争条件，因为摸个时刻只有一个进程处于内核模式。然而，对于抢占内核，就不能这样简单说了，这抢占内核需要认真设计以确保其数据结构不会导致竞争条件。对于SMP体系结构，抢占内核更难设计，因为两个处于内核模式的进程可同时运行在不同的处理器上。

Peterson算法

Peterson算法适用于两个进程在临界区与剩余区间交替执行。两个进程为P0,P1。为了方便，当使用Pi时，用pj来表示另一个进程即j=1-i。

Peterson算法需要在两个进程之间共享两个数据项：

int turn;

boolean flag[2];

变量turn表示哪个进程可以进入其临界区。即如果trun==I,那么进程pi允许在其临界区内执行。数组flag表示哪个进程想要进入其临界区。例如，如果flag[i]为true，即进程pi想要进入其临界区。

硬件同步

上述描述了基于软件的临界区问题的结构。一般来说，可以说任何临界区问题都需要一个简单工具---锁。通过要求临界区用锁来防护，就可以避免竞争条件，即一个进程在进入临界区用锁来防护，就可以避免竞争条件，即一个进程在进入临界区之前必须得到锁，而在其退出临界区时释放锁。

现代计算机系统提供了特殊硬件以允许能原子地（不可中断地）检查和修改字的内容或交换两个字的内容（作为不可中断的指令）。

指令TestAndSet()

指令Swap()

这些算法解决了互斥，但是没有解决有限等待要求。下面，介绍一种使用指令TestAndSet的算法，该算法满足所有临界区问题的三个要求。共用数据结构如下：

这些数据结构初始化为false。为了证明满足互斥要求，注意，只有waiting[i]==false或key==false时，进程pi才进入临界区。只有当TestAndSet执行时，key的值才变成false。执行TestAndSet的第一个进程会发现key==false;所有其他进程必须等待。只有其他进程离开其临界区时，变量waiting[i]的值才能变成false;每次只有一个waiting[i]被设置为false，以满足要求。

为了证明满足有限等待，当一个进程退出其临界区时，它会循环地扫描数组waiting[i](i+1,i+2,i+3,…..,n-1,0,……,i-1)，并根据这一顺序二指派第一个等待进程（waiting[j]==true）作为下一个进入临界区的进程。因此，任何等待进入临界区的进程只需要等待n-1次。

信号量

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

wait定义可表示为：

signal定义可表示为：

在wait和signal操作中，对信号量整型值的修改必须不可分地执行，即当一个进程修改信号量时，不能有其他进程同时修改同一信号量的值。另外，对于wait(S),对S的整型值的测试(S<=0)和对其可能的修改（S--）,也必须不被中断地执行。

用法

通常操作系统区分计数信号量与二进制信号量。计数信号量的值域不受限制，而二进制信号量的值只能为0或1。有的系统，将二进制信号量称为互斥锁，因为它们可以提供互斥。

实现

这里定义的信号量的主要缺点是都要求忙等待（busy waiting）。当一个进程位于其临界区内时，任何其他试图进入其临界区的进程都必须在其进入代码中连续地循环。这种连续的循环在实际多道程序系统中显然是个问题，因为这里只有一个处理器为多个进程所共享。忙等待浪费了CPU时钟，这本来可以有效地为其他进程所使用。这种类型的信号量也称为自旋锁（spinlock）,这是因为进程在等待锁时还在运行（自旋锁有其优点，进程在等待锁时不进行上下文切换，而上下文切换可能需要花费相当长的时间。因此，如果锁的占用时间短，那么自旋锁就有用了；自旋锁常用于多处理器系统中，这样一个线程在一个处理器自旋时，另一个贤臣个可在另一处理器上在其临界区内执行。）

为了克服忙等，可以修改信号量操作wait和signal的定义。当一个进程执行wait操作时，发现信号量值不为正，则它必须等待。然而，该进程不是忙等待而是阻塞自己。阻塞操作将一个进程放入到与信号量相关的等待队列中，并将该进程的状态切换成等待状态。接着，控制转到CPU调度程序，以选择另一个进程来执行。

一个被阻塞在等待信号量S上的进程，可以在其他进程执行signal()操作之后被重新执行。该进程的重新执行时通过wakeup（）操作来进行的。该操作将进程的等待状态切换到就绪状态。接着，该进程被放入到就绪队列中（根据CPU调度算法的不同，CPU有可能会也可能不会从正在运行的进程切换到刚刚就绪的进程）。

信号量的定义如下：

每个信号量都有一个整型值和一个进程链表。当一个进程必须等待信号量时，就加入到进程链表上。操作signal会从等待进程链表中取一个进程以唤醒

信号量操作wait现在可按如下来定义：

信号量操作signal现在可按如下来定义：

操作block()挂起调用它的进程。操作wakeup重新启动阻塞进程p的执行。这两个操作都是由操作系统作为基本系统调用来提供的。

等待进程的链表可以用进程控制块PCB中的一个链接域来加以轻松实现。每个信号量包括一个整型值和一个PCB链表的指针。向链表中增加和删除一个进程以确保有限等待的一种方法可以使用FIFO队列。

信号量的关键之处是它们原子地执行。必须确保没有两个进程能同时对同一信号量值执行操作wait和signal。这属于临界区问题，可通过两种方法来操作。在单处理器环境下，可以在执行wait和signal操作时简单的禁止中断。在多处理器环境下，必须禁止每个处理器的中断。

死锁与饥饿

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

与死锁相关的另一个问题是无限期阻塞（indefinite blocking）或饥饿(starvation)，即进程在信号量内无限等待。

经典同步问题

生产者-消费者问题

读者-写者问题

一个数据库可能为多个并发进程所共享。其中，有的进程可能只需要都数据库，而其他进程可能要更新（即读和写）数据库。为了区分这两种类型的进程，将前者称为读者，而后者称为写者。显然，如果两个读者同时访问共享数据，那么不会产生什么不利的结果。然而，如果两个读者同时访问共享数据，那么不会产生什么不利的结果。如果既有读者也有写者同时访问共享对象，很可能混乱。

为了确保不会产生这样的困难，要求写者对共享数据库有排他的访问。这一同步问题称为读者-写者问题。最为简单的，通常称为第一读者-写者问题，要求没有读者需要保持等待除非已有一个写者已获得允许以使用共享数据库。换句话说，没有读者会因为有一个写者在等待而会等待其他读者的完成。

读者—写者问题及其解答可以进行推广，用来对那些系统提供读写锁。在获取读写锁时，需要指定锁的模式:读访问或写访问。当一个进程只希望读共享数据时，可申请读模式的读写锁；当一个进程希望修改数据时，则必须申请写模式的读写锁。多个进程可允许并发获取读模式的读写锁；而只有一个进程可为写操作而获取读写锁。

读写锁在以下情况下最为有用：

当可以区分哪些进程只需要读共享数据而哪些进程只需要写共享数据。

当读者进程数比写进程多时。

哲学家进餐问题

假设有5个哲学家，每位都有一把椅子。在桌子中央是一碗米饭，在桌子上放着5只筷子。一次只能拿起一只筷子，不能从其他哲学家手里拿走筷子。当有两只筷子的时候就可以吃了，吃完后放下两只筷子。

这样的解决方法可能导致死锁，可能的解决方法如下：

最多只允许4个哲学家同时坐在桌子上

只有两只筷子都可用时才允许一个哲学家拿起其它们。

管程

虽信号量提供了一种方便且有效的机制以处理进程同步，但是使用不正确仍然会导致一些时序错误，并且难以检测，因为这些错误只有在忒那个执行顺序的情况下才会出现，而这些顺序并不总是会出现。然而，即使采用了信号量，这样的时序错误还是会出现。回顾一下使用信号量解决临界区的问题。所有进程共享一个信号量变量mutex,其初始化为1。每个进程在进入临界区之前执行wait(mutex),之后执行signal(mutex)。如果这一顺序不被遵守，那么两个进程会同时出现在临界区内。为此提出了管程（monitor）类型。

使用

类型和抽象数据类型，封装了私有数据类型及操作数据的公有方法。管程类提供了一组由程序员定义的，在管程内互斥的操作。管程类型的表示包括一组变量的声明（这些变量的值定义了一个类型实例的状态）和对这些变量操作的子程序和函数的实现。一般语法如下：

管程结构确保一次只有一个进程能在管程内活动。然而，现在所定义的管程结构还未强大都能处理一些特殊同步方案的地步。为此，需要一些额外的同步机制。这些可由条件（condition）结构来提供。对条件变量仅有的操作是wait()和signal()操作。操作signal()重新启动一个悬挂的进程，如果没有进程悬挂，那么操作siganal()就没有作用。

Horare方法

霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理。

不要求signal操作是过程提的最后一个操作，且wait和signal操作可被设计成可以中断的过程。

Mutex

对每个管程，使用用于管理中过程互斥调用的信号量mutex(初值为1)。

进程调用管程中的任何过程时，应该执行P(mutex);进程退出管程时应执行V(mutex)开放管程，以便让其他调用者进入。

为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex),否则会妨碍其他进程进入管程，导致无法释放资源。

next和next-count(执行Signal操作时，唤醒和被唤醒者之间的关系)

对每个管程，引入信号量next(初始值为0)

凡发出signal操作的进程应该用P(next)挂起自己，直到被释放进程退出管程或产生其他等待条件。

进程在退出管程的过程前或产生其他等待条件，必须检查是否有别的进程在信号量next上等待，若有，则用V(next)唤醒它。next-count(初始值为0)，用来记录在next上等待的进程个数。

x-sem和x-count(执行wait操作时)(模拟条件变量)

引入信号量x-sem(初始值为0)，申请资源得不到满足时，执行P(x-sem)挂起。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器x-count(初始值为0)记录等待资源的进程数。

执行signa操作时，应让等待资源的诸进程中的某个进程逻辑恢复运行，而不让其他进程抢先进入管程，这可以用V(x-sem)来实现

数据结构

TYPE interf=RECORD

mutex:semaphore //进程调用管程过程前使用的互斥信号量

next:semaphore //发出signal的进程挂起自己的信号量

next_count:integer: //在next上等待的进程数

wait操作

procedure wait(var x_sem:semaphore,x_count:integer,IM:interf)

begin

x_count:=x_count+1;

if IM.next_count>0 then V(IM.next); //被Signal唤醒的进程，在执行中再次阻塞，阻塞前唤醒曾唤醒它的进程

else V(IM.nutex); //阻塞前开放管程

P(x_sem);

x_count:=x_count-1;

end;

signal操作

procedure signal(var x_sem:semaphore,x_count:integer,IM:interf);

begin

if x_count>0 then begin

IM.next_count:=IM.next_count+1;

V(x_sem); //唤醒一个资源等待者

P(IM.next); //执行唤醒的进程，自己阻塞

IM.next_count:=IM.next_count-1;

end;

管程的外部过程形式

任何一个调用管程过程的外部过程应组织成下列形式，确保互斥地进入管程

P(IM.mutex);

<过程体>

if IM.next_count>0 then V(IM.next);

else V(IM.mutex);

从管程中退出时，要检查next是否有等待者

哲学家问题

TYPE dining-philosophers=MONITOR

var state: array[0..4] of (thingk,hungry,eating);

s:array[0..4] of semaphore;

s-count:array[0..4] of integer;

define pickup,putdown;

use wait,signal;

procedure test(k:0..4);

begin

if state[(k-1) mod 5]<>eating and state[k]=hungry and state[(k+1) mod 5]<>eating then begin

state[k]:=eating;

signal(s[k],s-count[k],IM);

end;

procedure pickup(i:0..4);

begin

state[i]:=hungry;

test(i);

if state[i]<>eating then

wait(s[i],s-count[i],IM);

end;

procedure putdown(i:0..4);

begin

state[i]:=thinking;

test((i-1) mod5);

test((i+1) mod 5);

end;

begin

for i:=0 to 4 do state[i]:=thinking;

end;

cobegin

process philosopher-i

begin

……

P(IM.mutex);

call dining-philosopher.pickup(i);

if IM.next-count>0

then V(IM.next)

else

V(IM.mutex);

吃通心面；

P(IM.mutex);

call dining-philosopher.putdown(i);

if IM.next-count>0

then V(IM.next);

else

V(IM.mutex);

….

end;

coend;

Linux同步实例

Linux系统中提供两种实现线程同步的方法：信号量和互斥量

每种方法都有一组实现的函数库，以二进制信号量方法为例：

使用信号量实现线程同步

原子事务

临界区的互斥确保临界区原子地执行，即如果两个临界区并发执行，那么其结果相当于它们按某个次序顺序执行。但是在许多情况下希望确保临界区作为一个逻辑工作单元，要么完全执行，要么什么也不做。例如资金转账，为了保持数据一致性，要么同时借和贷，要么既不借也不贷。

系统模型

执行单个逻辑功能的一组指令或操作称为事务（transaction）。处理事务的主要问题是不管出现什么计算机系统的可能失败，都要保证事务的原子性

可以认为事务时访问且可能更新各种驻留在磁盘文件中的数据项的程序单元。从用户角度来看，事务只是一系列read操作和write操作，并以commit操作或abort操作终止。操作commit表示事务已成功执行；操作abort表示因各种逻辑错误，事务必须停止执行。已成功完成执行的终止事务称为提交（committed）;否则，称为撤销（aborted）。

由于被中止的事务可能已改变了它所访问的数据，这些数据的状态与事务的原子执行情况下是不一样的。被中止的事务必须对其所修改的数据不产生任何影响，以便确保原子特性。因此，被中止的事务所访问的数据状态必须恢复到事务刚刚开始执行之前，即这个事务已经回退（rolled back）。确保这一属性是系统的责任。

为了决定系统如何确保原子性，首先需要认识用于存储事务所访问的各种数据的设备的属性。不同类型的存储介质可以通过它们的相对速度，容量和容错能力来区分。

易失性存储：驻留在易失性存储上的信息通常在系统崩溃后不能保存。内存和高速缓存就是这样存储的例子。对易失性的访问非常快，这是由于内存访问本身的速度以及易失性存储内的任何数据项都可以直接访问。

非易失性存储：驻留在非易失性存储上的信息通常在系统崩溃后能保存。磁盘和磁带就是这种存储介质的例子。磁盘比内存更为可靠。

基于日志的恢复

确保原子性的一种方法是在稳定存储上记录有关事务对其访问的数据所做各种修改的描述信息。实现这种形式记录最为常用的方法是先记日志后操作。系统在稳定存储上维护一个被称为日志的数据结构。每个日志记录描述了一个事务写出的单个操作，并具有如下域：

事务名称：执行写操作事务的唯一名称。

数据项名称：所写数据项的唯一名称。

旧值：写操作前的数据项的值。

新值：写操作后的数据项的值。

其他特殊日志记录用于记录处理事务的重要事件，如事务开始和事务的提交或放弃。

在事务Ti开始执行之前，记录<Ti,starts>被写到记录。在执行时，每个Ti的写操作之前都要将适当新纪录先写到日志。当Ti提交时，记录<Ti commits>被写到日志中。

因为日志信息用于构造各种食物所访问数据项的状态，所以在将相应日志记录写出道稳定存储之前，不能允许真正地更新数据项。因此，要求在执行操作write(X)之前，对应于X的日志记录要先写到稳定存储上。

采用日志，系统可处理错误，以便不会再非易失性存储上造成数据损失。恢复算法采用两个步骤。

undo(Ti):事务Ti更新的所有数据的值恢复到原来值。

redo(Ti):事务Ti更新的所有数据的值设置成新值。

由Ti所更新的数据与原来值和新值的集合可以在日志中找到。

操作undo和redo必须幂等（即一个操作的多次执行与一次执行有同样结果），以确保正确的行为（无论恢复过程是否有错误发生）。

如果事务Ti夭折，那么可通过undo（Ti）以恢复所更新数据的状态。如果系统出现错误，那么可通过检测日志以确定哪些事务需要重做而哪些事务需要撤销。这种事务分类可按如下方式进行:

如果日志包括<Ti starts>记录但没有包括<Ti commits>记录，那么事务Ti需要撤销。

如果日志包括<Ti starts>和<Ti commits>记录，那么事务Ti需要重做。

检查点

当系统出现错误，必须参考日志以确定哪些事务需要重做而哪些事务需要撤销。从原理上来说，需要搜索整个日志以便做出这些决定。这种方法有两个主要缺点：

搜索进程费时。

绝大多数所根据的算法需要重做的事务（如日志记录所说的那样）已经更新了数据。虽然重做数据修改并没有什么损坏（因为幂等），但是它会导致恢复需要较长时间。

为了降低这些类型的额外开销，在此引入了检查点（checkpoint）的概念。在执行时，系统维护写前日志。另外，系统定期执行检查点并执行如下动作:

将当前驻留在易失性存储（通常是内存）上的所有日志记录输出到稳定存储上。
将当前驻留在易失性存储上的所有修改数据输出到稳定存储上。
在稳定存储上输出一个日志记录<checkpoint>。

日志记录的<checkpoint>的存在允许系统简化其恢复过程。

并发原子操作

因为每个事务是原子性的，所以事务的并发执行必须相当于这些事务按任意顺序串行执行。这一属性称为串行化（serializability）,可以简单地在临界区内执行每个事务，即所有这些事务共享一个信号量mutex,其初始值为1.当事务开始执行时，其第一动作是执行wait(mutex)。在事务提交或夭折后，它执行signal(mutex)。

虽然这种方案确保了所有并发执行事务的原子性，但是其限制太严。在许多情况下，可以允许这些事务互相重叠，而又能保证其串行化。有多个不同并发控制算法可确保串行化。

串行化能力

考虑一个系统，其中有两个数据项A和B，它们被两个事务T0和T1读和写。假若这两个操作按先T0后T1的顺序以原子地执行，这个执行顺序称为一个调度。每个事务原子地执行的调度称为串行调度。每个串行调度由不同事务指令的序列组成，其中属于单个事务的指令在调度中一起出现。因此，对于n个事务的集合，共有n!个不同的有效的串行调度。每个串行调度都是正确的，因为它相当于各个参与事务按某一特定顺序原子地执行。

如果允许两个事务重叠执行，那么这样的调度就不再是串行的。非串行调度不一定意味着其执行结果是不正确的（即与串行调度不同）。为了说明这种情况，需要定义冲突操作（conflicting operation）。

如果调度S可以通过一系列非冲突操作的交换而转换成串行调度S',说调度S为冲突可穿行化（conflict serializable）的。

加锁协议

确保串行化能力的一种方法是为每个数据项关联一个锁，并要求每个事务遵循加锁协议（locking protocal）以控制锁的获取与释放。对数据项加锁有许多方式。这里，只讨论两种方式：

共享（shared）:如果事务Ti获得了数据项Q的共享模式锁（记为S）,那么Ti可读取这一项，但不能修改它。

排他（exclusive）:如果事务Ti获得了数据项Q的排他模式锁(记为X)，那么Ti可读和写Q。

要求每个事务根据其对数据项Q所要进行操作的类型，以便按适当模型来请求数据项Q的锁。

确保串行化能力的一种协议为两阶段加锁协议（two-phase locking protocol）。这个协议要求每个事务按两个阶段来发出加锁和放锁请求：

增长阶段：事务可获取锁，但不能释放锁。

收缩阶段：事务可释放锁，但不能获取新锁。

开始时，事务处于增长阶段。事务根据其需要获取锁。一旦事务释放，它就进入收缩阶段，而不再提出加锁请求。

基于时间戳的协议

对于以上描述的加锁协议，每对冲突事务的顺序是由在执行时它们所请求的第一次不兼容的锁所决定的。确定串行化顺序的另一个方法是事先在事务之前选择一个顺序。这样做的最为常用的方法是使用时间戳（timestamp）排序方案。

小结

对于共享数据的一组协议的顺序进程必须提供互斥。一种解决方法是确保在某个时候只能有一个进程或线程可使用代码多的临界区。在假定只有存储式连锁可用时，可有许多不同方法解决临界区问题。

这些用户级解决方案的主要缺点是它们都需要忙等。信号量可克服这个困难。信号量可用于解决各种同步问题，且可高校地加以实现（尤其是在硬件支持原子操作时）。

各种不同的同步问题（如有限缓存区问题、读者-写者问题和哲学家进餐问题）均很重要，这是因为这些问题时大量并发控制问题的例子。这些问题用于测试几乎新提出的同步方案。

操作系统必须提供机制以防止时序出错问题。人们提出了多个不同结构以处理这些问题。管程为共享抽象数据类型提供了同步机制。条件变量提供了一个方法，以供管程程序阻塞其执行直到被通知可继续为止。

事务是一个原子执行的程序单元，即要么与其相关的所有操作都执行完，要么什么操作都不做。为了确保原子性（即使在系统出错时），可使用写前日志。所有更新记录在日志上，而日志保存在稳定存储上。如果系统出现死机，日志信息可用于恢复更新数据项的状态，这由undo和redo操作实现。为了降低在系统出错发生时搜索日志的额外开销，可以使用检测点方案。

当多个事务重叠执行时，这样的执行可能不再与这些操作原子执行时的相同。为了确保正确执行，必须使用并发控制方案以保证串行化。有各种不同并发控制方案以确保串行化，或者延迟操作或撤销发布这个操作的事务。最为常用的方法为加锁协议和时间戳顺序协议。