操作系统——同步

笔记内容及图片整理自XJTUSE “操作系统” 课程ppt，仅供学习交流使用，谢谢。

背景

解决有界缓冲区问题的共享内存方法在并发变量上存在竞争条件，即多个并发进程访问和操作同一个共享数据，从而其执行结果与特定访问次序有关。这种对共享数据的并发访问可能导致数据的不一致性，因此需要同步机制保证并发进程的正确执行顺序。

进程间的制约关系包括间接制约和直接制约。

间接制约——进程的互斥：对于需要互斥使用的资源，各进程竞争部分或全部共享资源

直接制约——进程的同步：处于等待状态的进程等待来自其他进程信息以进入就绪状态

临界区问题

每个进程都有一段称为临界区的代码，进程执行临界区以访问临界资源。临界区问题是设计一个便于协作进程的协议，使得每个进程必须请求许可以进入临界区。实现此请求的代码区段是进入区，临界区之后是退出区，其余临界区代码是剩余区。

临界区问题需要满足以下三个要求：

1）互斥——若一个进程在其临界区内执行，那么其他进程不能在各自的临界区内执行

2）有空让进——若没有进程在临界区内执行，而有其他进程需要进入临界区，那么便不能无限延长下一个要进入临界区进程的等待时间

3）有限等待——从一个进程提出进入临界区请求到该请求被允许的时间内，其他进程允许进入临界区的次数存在上限

处理操作系统的临界区问题有以下两种常用方法：

抢占式内核：允许处于内核模式的进程被抢占

非抢占式内核：不允许处于内核模式的进程被抢占，它会一直运行直到退出内核模式、阻塞或自愿放弃CPU控制

Peterson解决方案

算法1

设立一个进程Pi、Pj公用的整型变量turn，它是描述允许进入临界区的进程标识，如果turn==i，那么进程Pi允许在其临界区执行，下图是Pi的结构。

算法1的核心代码实现：

算法1的缺点是它强制各进程轮流进入临界区而没有考虑实际需要，容易造成资源利用的不充分；且在进程1退出临界区后，进程2使用临界区前，进程1无法再次使用临界区。

算法2

算法1只记住了哪个进程能进入临界区，并没有保存进程的状态，因此引入算法2。

设立一个初值为FALSE的标志数组 flag[] 以描述进程是否准备进入临界区，先申请后检查，这可以防止两个进程同时进入临界区，保证了互斥。

算法2的核心代码实现：

算法2的优点是进程可连续使用，不用交替进入临界区；缺点是在某个时刻进程1、进程2可能都无法进入临界区。这是因为Pi、Pj在切换自己flag之后和检查对方flag之前有一段时间，若两个进程都切换flag则检查都无法通过。

算法3（Peterson解决方案）

设立turn=j以描述可进入的进程。在算法2的基础上增加进入区先修改后检查，检查并发修改先后的规则：

1）空闲则入——检查对方flag，如果不在临界区则自己进入

2）先到先入，后到等待——检查flag在临界区则再检查turn，保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入。

Peterson解决方案的核心代码实现：

Peterson解决方案提供解决临界区问题的一个很好的算法，并能说明满足互斥、进步、有限等待等要求的软件设计的复杂性。

硬件同步

基于软件的解决方案并不保证在现代计算机架构上正确运行，这对硬件同步提出了要求。

对于单处理器环境，只要在修改共享变量时禁止中断便能解决临界区问题；对于多处理器环境，由于消息要传递到所有处理器，中断禁止非常耗时，大幅降低系统效率，因而许多现代系统提供能够原子地执行作为不可中断指令的特殊硬件指令。通过指令test and set，compare and swap可以抽象特殊硬件指令的主要概念。

test and set指令

test and set线程

compare and swap指令

compare and swap线程

硬件同步方法的优缺点

优点

1）适用于任意数量的进程

2）操作简单，易于验证正确性

3）只需为每个临界区设立一个布尔变量就能支持进程内存在多个临界区

缺点

1）等待耗费CPU时间，不能实现让权等待

2）从等待进程中随机选择一个进入临界区，导致有的进程可能遭遇饥饿，一直选不上

互斥锁

互斥锁是解决临界区问题的软件工具，它能保护临界区从而防止竞争条件。一个进程在进入临界区时应通过acquire（）获取锁，它在退出临界区时应通过release（）释放锁。

每个互斥锁有个布尔变量available，其值表示锁是否可用。若锁可用，则调用acquire（）成功且锁不再可用。当一个进程请求获取不可用的锁时，进程阻塞直至锁被释放。

acquire and release定义和实现

信号量

信号量的使用与实现

互斥算法是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题，操作系统可从进程管理者的角度来处理互斥问题，而信号量就是操作系统提供的管理公有资源的有效手段。信号量代表可用资源实体的数量，与其相关的用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。

一个信号量S是个整型变量，初始化指定一个非负整数值，表示空闲资源总数，除了初始化外只能通过两个标准原子操作：wait（）【P】和signal（）【V】来访问。P、V操作中信号量整数值的修改应不可分割地执行，即当一个进程修改一个信号量的值时没有其他进程能同时修改同一个信号量的值。在信号量经典定义下，信号量S的值不可能为负。

S≥0——可供并发进程使用的资源数

S<0——其绝对值就是正在等待进入临界区的进程数

P原语操作功能流程图如下：

V原语操作功能流程图如下：

信号量描述前趋关系

并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成，则为每个前趋关系设置一个同步信号量S12，令其初值为0，可通过信号量实现前驱关系。

某程序执行如下操作，试画出程序的前驱图，并用P、V操作描述前驱关系。

{

// exp

计算，生成数据S1；

由数据S1，计算生成数据S2、S3；

由数据S2，计算生成数据S4、S5；

由数据S3 、S4、S5，计算生成数据S6；

}

先定义信号量a, b, c, d, e, f, g ,令其初值均为0，并绘制前驱图：

再用P、V操作描述前驱关系：

死锁与饥饿

饥饿：进程无限等待信号量，可能永远无法从它等待的信号量队列中移去。若对与信号量有关的链表按照LIFO顺序增加和删除进程，则容易发生饥饿。

死锁：两个及以上进程无限等待一个事件发生，而该事件正是由这些等待进程之一产生的。

假设一个拥有进程P0、P1的系统，S、Q是两个初值为1的共享信号量，下图将发生死锁：

P0执行P（S）；

P1执行P（Q ）；

P0执行P（Q）但需等待P1执行V（Q）释放Q；

然而P1需等待P0执行V（S）释放S后才能执行V（Q）；

由于V（S）、V（Q）均不能执行，系统发生了死锁。

信号量集

信号量集用于同时需要多个资源时的信号量操作，比如AND型信号量集。AND型信号量集用于同时需要多个资源且每个资源占用一个时的信号量操作。

一段处理代码需要同时获取两个及以上临界资源，这会导致死锁，各进程分别获得部分临界资源，然后等待其余的临界资源，互不相让。因此信号量集的基本思想是对于一个原语中的同时需要多个临界资源的一段代码，要么将全部临界资源分配给它，要么一个都不予分配。这称为同步等待，此时各个信号量的次序虽然会影响进程归入哪个阻塞队列，但是由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。

信号量机制的缺点

1）同步操作分散——信号量机制中同步操作分散在各个进程中，使用不当可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）

2）易读性差——要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或并发程序

3）不利于修改和维护——各模块独立性差，任一组变量或代码的修改都可能影响全局

4）正确性难以保证——操作系统或并发程序通常很大，难以保证这样一个复杂的系统没有逻辑错误

经典同步问题

哲学家就餐问题

问题描述：5个哲学家围绕一张圆桌而坐，桌子上放着5根筷子，每两个哲学家间放一根；哲学家的动作包括思考和进餐，进餐时需同时拿起他左边和右边的两根筷子，思考时则同时将两根筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子。

哲学家i就餐的代码实现：

当5个哲学家同时拿起同一个方向的筷子，系统可能出现死锁。解决方法如下：

1）最多允许四个哲学家同时就坐

2）哲学家需要同时拿起两根筷子

3）通过非对称解决

有界缓冲问题

问题描述：若干进程通过有限的共享缓冲区交换数据。"生产者"进程不断写入，而"消费者"进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。

"满"数目（full）初值为0，"空"数目（empty）初值为N。实际上，full + empty == N。

Mutex是用于访问缓冲区时的互斥，初值为1。

每个进程中P操作的次序最为重要：先检查资源数目，再检查是否互斥，否则可能死锁。

有界缓冲的代码实现：

读者-写者问题

问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许存在一个，而“读者”则允许存在多个。读者-写者问题存在以下关系：“读－写”互斥、“写－写”互斥、"读－读"允许。

对于读者：

无读者、写者，新读者可以读；

有写者等，但有其它读者正在读，则新读者也可以读；

有写者写，新读者等待。

对于写者：

无读者、写者，新写者可以写；

有读者，新写者等待；

有其它写者，新写者等待。

既有读者又有写者时：写者先到，则后来读者不允许读，写者不允许写；读者先到，则后来读者可以读，写者不允许写。

信号量Wmutex表示"允许写"，初值为1；

公共变量Rcount表示“正在读”的进程数，初值为0；

信号量Rmutex表示对Rcount的互斥操作，初值为1。

读者-写者的代码实现：

读者

写者

整体

PV操作讨论

信号量的物理含义：

1）S>0表示有S个资源可用

2）S=0表示无资源可用

3）S<0则 | S | 表示S等待队列中的进程个数

信号量的初值需>=0

P(S)、V(S)的物理含义：

1）P(S)表示申请一个资源

2）V(S)表示释放一个资源

PV操作必须成对出现，有一个P操作就一定有一个V操作。对于互斥操作，它们处于同一进程；对于同步操作，它们不能在同一进程出现。对于前后相连的两个P操作，它们的顺序至关重要：同步P操作应该放在互斥P操作前，而两个V操作的顺序则无关紧要。

信号量解题的关键步骤：信号量设置->信号量赋初值（常用的互斥和同步信号量值的大小）->P、V操作安排位置（P、V操作要成对出现）

管程

尽管信号量机制是解决进程互斥、同步的有效工具，但前提是信号量设置、确定初值及相关进程中安排P-V操作的位置必须正确，否则同样会造成时间相关的错误，甚至会造成死锁；同时由于信号量的控制分布在整个程序中，其正确性分析也将变得困难。

管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块，它把所有进程对某一临界资源的使用进行集中控制，以提高可靠性。管程是管理进程间同步的机制，比信号量更易于控制，它保证进程互斥地访问共享变量，并易于阻塞和唤醒进程。

引入管程可以提高代码的可读性，便于修改和维护，易于保证正确性。管程采用集中式同步机制，常以函数库的形式实现，一个操作系统或并发程序由若干个这样的模块所构成，一个模块通常较短，模块之间关系清晰。

管程的主要特征

1）模块化——管程是一个基本程序单位，可以单独编译

2）抽象数据类型——管程是一种特殊数据类型，其中包含数据和对数据进行操作的代码

3）信息封装——管程是半透明的，管程中的函数实现了某些功能，而外部不可见实现这些功能的具体方法

实现管程的关键问题

1）互斥——并发进程需要互斥地进入管程

2）条件变量——管程引入了条件变量，不同的条件变量对应不同原因的进程等待队列

3）同步——管程中必须设置两个同步操作原语wait（P）和signal（V）

互斥

当进程需要访问管程中的临界资源的时候，可调用管程中的有关入口过程。但当多个进程需调用某一管程的同一个或不同的入口过程时，仅允许一个进程调用，其他调用者必须等待。由此引出入口等待队列，当一个进程试图进入一个已被占用的管程时，它应在管程的入口处等待，即入口等待队列，亦称作进程等待队列。

条件变量

管程机制中引起等待的原因很多，引入条件变量以区分它们，并在当进入管程的进程因资源被占用等原因不能运行时使其等待。每个条件变量表示一种等待原因，对应一个等待队列。

每个条件变量都需在管程说明，调用x.wait的线程将一直等待到另一个线程才调用x.signal。

同步

针对条件变量存在两个同步操作原语：

C.wait（c）——执行此操作的进程排入c队列尾部

C.signal（c）——若c队列为空则相当于空操作，原进程继续，否则唤醒首个等待进程

当进程通过管程请求访问共享数据而未能满足时，调用wait原语在有关的条件变量上等待，当另一进程访问完共享数据且释放后，调用signal原语唤醒相关条件变量的首个等待进程。