操作系统理论第二章（进程的描述与控制）—第四节（进程同步（上））

本文主要是介绍操作系统理论第二章（进程的描述与控制）—第四节（进程同步（上）），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

写在前面：

本系列笔记主要以《计算机操作系统（汤小丹…）》为参考，大部分内容出于此书，笔者的工作主要是挑其重点展示，另外配合下方视频链接的教程展开思路，在笔记中一些比较难懂的地方加以自己的一点点理解（重点基本都会有标注，没有任何标注的难懂文字应该是笔者因为强迫症而加进来的，可选择性地忽略）。
视频链接：操作系统（汤小丹等第四版）_哔哩哔哩_bilibili

一、进程同步的基本概念

1、进程同步机制的任务

进程同步机制的主要任务是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。

2、两种形式的制约关系

（1）间接相互制约关系：

多个程序在并发执行时，由于共享系统资源，致使在这些并发执行的程序之间形成相互制约的关系。

对于像打印机、磁带机这样的临界资源，必须保证多个进程对之只能互斥地访问，由此，在这些进程间形成了源于对该类资源共享的所谓间接相互制约关系。为了保证这些进程能有序地运行，对于系统中的这类资源，必须由系统实施统一分配，即用户在要使用之前，应先提出申请，而不允许用户进程直接使用。

（2）直接相互制约关系：

某些应用程序为了完成某任务而建立了两个或多个进程，这些进程将为完成同一项任务而相互合作，进程间的直接制约关系就是源于它们之间的相互合作。

例如，有两个相互合作的进程——输入进程A和计算进程B，它们之间共享一个缓冲区，进程A通过缓冲向进程B提供数据，进程B从缓冲中取出数据，并对数据进行处理，但如果该缓冲为空，计算进程因不能获得所需数据而被阻塞，一旦进程A把数据输入缓冲区后便将进程B唤醒，反之，当缓冲区已满时，进程A因不能再向缓冲区投放数据而被阻塞，当进程B将缓冲区数据取走后便可唤醒A。

3、关于临界资源的“生产者-消费者”问题

（1）把一段时间内只允许一个进程访问的资源称为临界资源或独占资源。

（2）“生产者-消费者”的问题描述：

①有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。

②为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将其所生产的产品放入一个缓冲区中，消费者进程可从一个缓冲区中取走产品去消费。

③尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，既不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

（3）解决“生产者-消费者”问题的程序：

①利用一个数组buffer来表示上述的具有n个缓冲区的缓冲池，每投入（或取出）一个产品时，缓冲池buffer中暂存产品（或已取走产品的空闲单元）的数组单元指针in（或out）加1。由于这里由buffer组成的缓冲池是被组织成循环缓冲的，故应把输入指针in（或输出指针out）加1，表示成in=(in+1)%n（或out=(out+1)% n）。当(in+1)%n=out时表示缓冲池满，而in=out则表示缓冲池空。

②引入一个整型变量counter，其初始值为0，每当生产者进程向缓冲池中投放（或取走）一个产品后，使counter加1（或减1）。需要注意的是，变量counter应该作为两个进程的临界资源，也就是令生产者进程和消费者进程互斥地访问变量counter。

③在生产者进程中使用一个局部变量nextp暂时存放每次刚刚生产出来的产品，在消费者进程中使用一个局部变量nextc存放每次要消费的产品。

4、临界区

（1）每个进程中访问临界资源的那段代码称为临界区。

（2）访问临界区的程序设计：

①每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问，如果此刻临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。因此，必须在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区。

②在临界区后面要加上一段称为退出区的代码，用于将临界区正被访问的标志恢复为未被访问的标志。

③进程中除上述进入区、临界区及退出区之外的其它部分的代码都称为剩余区。

5、同步机制应遵循的规则

（1）空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。

（2）忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。

（3）有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。

（4）让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

二、进程互斥的实现方法

1、软件同步机制

（1）单标志法：

①算法思想：进程在访问完临界区后会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限只能被另一个进程赋予。

②算法流程：在进入区只做“检查”（检查资源是否正在被访问），不“上锁”；在退出区把临界区的使用权限转交给另一个进程。

③主要问题：违背“空闲让进”原则，原因在于需要允许一个进程进入临界区，但是如果这个进程“不愿意”进入临界区，临界资源就会一直空闲。

（2）双标志先检查法：

①算法思想：设置一个布尔型数组flag[n]，数组中各个元素用来标记各进程进入临界区的意愿，比如“flag[0] = true”意味着0号进程现在想要进入临界区，接着每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有则把自身对应的标志flag[i]设为true（也就是“上锁”，代表临界区正被一个进程访问），然后开始访问临界区，访问结束后把自身对应的标志flag[i]设为false（也就是“解锁”，解锁后临界区允许其它进程访问）。

②算法流程：在进入区先“检查”后“上锁”，退出区“解锁”。

③主要问题：违背“忙则等待”原则，原因在于进入区的“检查”和“上锁”两个处理不是一气呵成的，“检查”后、“上锁”前这段时间可能会发生进程切换，一个进程来不及“上锁”，另一个进程的“检查”就会通过，导致两个进程同时进入临界区。

（3）双标志后检查法：

①算法思想：双标志先检查法的问题是“检查”和“上锁”两个操作不是一气呵成的，这将导致两个进程可能同时进入临界区，于是又将算法改为先“上锁”后“检查”。

②算法流程：在进入区先“上锁”后“检查”，退出区“解锁”。

③主要问题：违背“空闲让进”和“有限等待”原则，如果两个进程争着进入临界区，它们可能会在“检查”之前一起“上锁”，这样到“检查”这一步它们会都认为临界资源正被其它进程访问，而且二者互不谦让（都不主动“解锁”），那么它们都无法进入临界区。

（4）Peterson算法：

①算法思想：如果两个进程都争着进入临界区，那么可以让进程尝试“孔融让梨”，即主动让对方进入临界区。

②Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是未遵循让权等待原则。

2、硬件同步机制

（1）关中断：

在进入锁测试（将临界资源是否被访问的标志看作一个锁）之前关闭中断，直到完成锁测试并上锁之后才能打开中断，这样进程在临界区执行期间计算机系统不会响应中断，从而不会引发调度，也就不会发生进程或线程切换，由此保证了对锁的测试和关锁操作的连续性和完整性，有效地保证了互斥。

关中断的方法存在许多缺点：

①滥用关中断权力可能导致严重后果。

②关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力。

③关中断方法不适用于多CPU系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。

（2）利用Test-and-Set指令实现互斥：

①TS指令的一般性描述如下所示，这条指令可以看作为一个函数过程，其执行过程是不可分割的，即是一条原语。其中lock有两种状态，当*locK=FALSE时表示该资源空闲，当*lock=TRUE时表示该资源正在被使用。

boolean TS(boolean *lock)

{

        boolean old;

        old = *lock;

        *lock = TRUE;

        return old;

};

②用TS指令管理临界区时，为每个临界资源设置一个布尔变量lock，由于变量lock代表了该资源的状态，故可把它看成一把锁。

[1]lock初值为FALSE，表示该临界资源空闲。

[2]进程在进入临界区之前，首先用TS指令测试lock，如果其值为FALSE则表示没有进程在临界区内，可以进入，并将TRUE值赋予lock，这等效于关闭了临界资源，使任何进程都不能进入临界区，否则必须循环测试直到TS(s)为TRUE。

[3]利用TS指令实现互斥的循环进程结构可描述如下：

do

{

        …

        while TS(&lock); //没有任何操作的循环，等待锁开（检测到锁开后会上锁）

        critical section;

        lock = FALSE;    //解锁

        remainder section;

}while(TRUE);

③相比软件实现方法，TS指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作，实现简单，不用严格检查是否有逻辑漏洞，适用于多处理机环境。TS指令的缺点是不满足“让权等待”原则，原因是当临界资源忙碌时，其它访问进程必须不断地进行测试，将会处于一种“忙等”状态。

（3）利用Swap指令实现进程互斥：

①Swap指令称为对换指令，用于交换两个字的内容，其处理过程如下：

void swap(boolean *a, boolean *b)

{

        boolean temp;

        temp = *a;

        *a = *b;

        *b = temp;

};

②用对换指令可以简单有效地实现互斥，方法是为每个临界资源设置一个全局的布尔变量lock，其初值为false，接着在每个进程中再设置一个局部布尔变量key记录此时临界区是否被上锁。利用Swap指令实现进程互斥的循环进程可描述如下：

do

{

        key = TRUE;   //默认临界区未上锁

        do

        {

                swap(&lock, &key); //更新key值，即当前临界区的状态（检测到锁开后会上锁）

        }while(key != FALSE);   //等待锁开

        临界区操作

        lock = FALSE;    //解锁

        …

}while(TRUE);