本文共 10120 字，大约阅读时间需要 33 分钟。
进程同步机制
进程的同步机制包含软件同步机制、硬件同步机制、信号量机制等，也就是这些机制，可以保证程序并发执行时的可再现性，在介绍之前，我们先来看下几个概念：
一、进程同步的几个重要概念
进程同步机制的主要任务，是对多个相关的进程在执行次序上进行协调，使并发执行的诸多进程之间能够按照一定的规则共享系统资源，并能很好的相互合作，从而使程序之间的执行具有可再现性。
-
1. 进程间的两种制约关系：
- 间接相互制约（互斥）：因为进程在并发执行的时候共享临界资源而形成的相互制约的关系，需要对临界资源互斥地访问；
- 直接制约关系（同步）：多个进程之间为完成同一任务而相互合作而形成的制约关系。
-
2. 临界资源：
指同一时刻只允许一个进程可以该问的资源称之为临界资源，诸进程之间采取互斥方式，实现对临界资源的共享。 -
3. 临界区
进程中访问临界资源的那段代码。 每个进程在进入临界区之前，应先对欲访问的临界资源的“大门”状态进行检测，如果“大门”敞开，进程便可进入临界区，并将临界区的“大门”关上；否则就表示有进程在临界区内，当前进程无法进入临界区。 -
4. 指令
指令就是机器语言的一个语句，它是一组有意义的二进制代码，因为是机器语言的一条指令，所以指令就可以等价于是原子性的，只有在执行完一条指令后才会去响应中断。 -
5. 原语
由若干条指令组成的，用户完成一定功能的一个过程。原语操作的一个特点就是“原子操作”， 因此原语在执行的过程中不允许被中断。原子操作在系统态下执行，常驻内存。 -
同步机制应遵循的规则
- 1. 空闲让进：当临界区的“大门”敞开时，应当允许一个请求的进入临界区的进程立即进入临界区。
- 2. 忙则等待：当临界区的“大门”关闭时，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
- 3. 有限等待：对要求进入临界区的进程，应保证有限的时间能进入自已的临界区，以免陷入“死等” 状态。
- 4. 让权等待：当进程不能进入自已的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。
忙等 和 死等 都是没能进入临界区，它们的区别如下：
- 死等： 对行死等的进程来说，这个进程可能是处于阻塞状态，等着别的进程将其唤醒（signal 原语），但是如果唤醒原语一直无法执行，对于阻塞的进程来说，就是一直处于死等的状态，是无法获得处理机的。
- 忙等：忙等状态比较容易理解，处于忙等状态的进程是一直占有处理机去不断的判断临界区是否可以进入，在此期间，进程一直在运行，这就是忙等状态。有一点需要注意的是，忙等是非常可怕的，因为处于忙等的进程会一直霸占处理机的，相当于陷入死循环了。 忙等的状态在单CPU 系统中是无法被打破的，只能系统重启解决。
不管是“忙等”还是“死等”，都是对OS 有害的，都应该努力避免。
二、软件同步机制
其实说到使用软件来实现同步机制，大家想到最多的应该就是 Java 多线程，Java 通过锁，synchronized，信号量等机制实现了线程的同步，但是线程间是共享父进程中的所有资源的。
但是当线程之间，如果需要共享系统资源时，进程之间很难直接通过软件来进行交流，对系统资源的互斥共享就很麻烦，需要借助硬件资源来完成同步，需要在内存中单独使用一块区域来保存进程是否在临界区内的标志。2.1 双标志位法
先来看一段代码：
// inside1, inside2, 是进程p1 和 p2 在内存中保存的标志，表示进程是否在临界区inside1 = false;inside2 = false;// 进程p1process p1begin while(inside2); // 循环测试，当 inside2=false 时往下走 inside1 := true; 临界区 inside1 := false;end;// 进程p1process p2begin while(inside1); // 循环测试，当 inside1=false 时往下走 inside2 := true; 临界区 inside2 := false;end;
代码逻辑很清晰，就是进程p1 或 p2 想进入临界区之前，先去判断对方是否在临界区内，如果在的话，就一直循环等待，束则就进入临界区，然后挂锁。
第一眼看起来没啥问题，但是如果进程在执行期间，比如p1 中的while 判断完比后，进入，在inside1 = true 之前发生了中断，p1 进入了临界区，但锁没来得及挂上；因此如果此时 进程p2 运行时，也可以进入临界区，这种情况下两个进程同时进入了临界区，进程的执行就会出现错误。虽然前面的是小概率事件，但也是可能存在的。
针对这个问题，你可能会想，我在判断之前挂上锁呢，我们把代码的须序调整一下：
// inside1, inside2, 是进程p1 和 p2 在内存中保存的标志，表示进程是否在临界区inside1 = false;inside2 = false;// 进程p1process p1begin inside1 := true; while(inside2); // 循环测试，当 inside2=false 时往下走 临界区 inside1 := false;end;// 进程p1process p2begin inside2 := true; while(inside1); // 循环测试，当 inside1=false 时往下走 临界区 inside2 := false;end;
这样的话，进程 p1 和 p2 在并发执行的时候就没有问题了。
我们来看这样一种情况，p1 先执行，挂锁成功，假设在成功之后，p1 发生了中断，进程p2 开始执行，此时p2 同样也可以挂锁，但是在判断是否可以进入临界区时，无法成功，会一直循环中断判断，当p1 恢复再次执行时，尴尬的事情发生了，p1 也无法进入临界区了，因为 p2 同样把锁给锁上了。双标志位法先检查可能会让两个进程同时进入临界区，双标志位法后检查可能会让两个进程都无法进入临界区，形成死锁问题。
三、硬件同步机制
前面我们在软件同步机制里，都是在落锁和判断之间发生中断，乃至导致无法实现互斥进入临界区，
那么我们是不是可以在这个期间不允许发生中断呢？这就需要用到硬件了。
3.1 关中断
这个方法简单有效，进程在落锁和判断之间不是有可能发生中断么，那我们在测试之前关闭中断（OS 内核不响应中断信号），到测试并上锁后在打开中断。
这样可以保证两个操作之间的连续性，保证临界资源的互斥访问。3.2 测试并建立（Test-and-Set，TS）指令
我们使用关中断来解决落锁与判断之间不允许响应中断，但是我们如果把这两个执行变成一条指令呢？
这样是不是就可以保证中断不会在落锁和判断之间被响应？我们可以借助一条硬件指令 — “测试并建立” 指令TS（Test-and-Set）来实现临界资源的互斥访问。
TS 指令一般描述如下：
// TS 指令boolean TS(boolean * lock){ if(*lock == false){ *lock = true; return true; }else{ return false; }}boolean lock;lock = false; // 临界区可以进入// 进程 p1, p2, p3,..., pnprocess pi{ // ... while( !TS(&lock) ); //循环请求锁 临界区； lock = false; // 解锁，归还临界次源} 我们可以把TS 指令看成上面的TS 函数的执行过程，其执行过程是一可分割的，即是一条原语。
当 lock 值为 false 时，表示临界资源空闲，当lock 的值为true 时，表示该资源正在被使用。使用TS 指令管理临界区时，需要为每个临界资源设置一个布尔变量lock。 当有进程需要进入临界区时，需要先用TS 指令尝试临界区对应的那把锁。
如果返回true，临界区空闲，可以进入，并落锁 ，阻止别的进程再进入临界区； 如果返回fase，则必须要循环请求，直到TS 返回的值变为 true。3.3 对换指令
该指令也称为 swap 指令，用于交换两个字的内容，其处理过程描述如下：
void swap(boolean * a, boolean * b){ boolean tmp; tmp = *a; *a = * b; *b = tmp;}boolean lock;lock = false; // 临界区可以进入// 进程 p1, p2 ,p3 ,p4process pi{ do{ swap(&lock, & key); }while(key != false) // 循环请求锁}临界区lock = false; swap 指令 和 TS 指令 类似，也需要为每个临界资源设置一个布尔变量lock，不同的进程中使用一个局部变量key 字段去替换出lock中的值 ，通过key 的值就可以判断出临界资源是否空闲。
有一点需要注意的，因为原语是将多个指令合并成一个指令，在原语的执行过程中也是不响应中断的，使之成为原子操作，
这个期间，等于是屏蔽中断，也就等价于我们讲的第一种硬件方式----- 关中断， 因此原语操作的指令长序应该是短小精悍的，这样才能保证系统的效率。四、信号量机制
信号量机制是1965年迪杰斯特拉（Edsger Wybe Dijkstra）提出的一种卓有成效的进程同步工具。
信号量机制在长期的应用中得到了很大的发展，从整型信号量经记录型信号量，进而发展为“信号量集”机制，在目前来讲，信号量。需要着重说明的一点是：
信号量除了初始化外，仅能被通过两个标准的原子操作wait(S)和signal(S)来访问，这两个操作也被称为P、V操作，这几个操作都是原语操作。 4.1 整型信号量
整型信号量是最开始由迪杰斯特拉定义的，整型信号量也很简单，里面只有一个表示资源的数量的整形量，
一般使用S符号来表示，整型信号量下的wait和signal操作可描述如下：int S; // 整型信号量定义// P 操作wait(S){ while(S <= 0); S--;}//V 操作signal(S){ S++;} 因为wait和signal操作是原子的，因此他们在执行的过程中是不可被中断的。
也就是说当一个进程在修改某个信号量时，没有其他的进程可以同时对该信号量进行修改。需要注意的是，整型信号量的wait操作，只要是信号量S<=0，就会不断的测试，让进程处于一种“忙等”的状态，没有遵循让权等待的原则。
还有就是，把信号量的初值置为1，表示只允许一个进程访问临界资源，此时的信号量就可以转换为互斥信号量，用于完成进程的互斥（对所有的信号量机制都是一样）。
4.2 记录型信号量
为了解决整型信号量存在的忙等问题，应当采取让权等待原则。
但是又会出现一个新的问题，如果多个进程并发请求访问临界资源，除了第一个抢到了信号量外，其余的进程都应该释放处理机，但是这些等待的进程要如何保存呢？为此，除了wait操作需要遵循让权等待原则，还需在信号量中增加一个进程的链表指针list，用与链接上面描述的多个等待访问临界资源的进程。
也因为记录了等待的进程，这种信号量集之被称为记录型信号量。记录型信号量具体的描述以及对应的wait和signal操作如下所示：
//记录型信号量typedef struct{ int value; struct process_control_block * list;}semaphore;// P操作wait(semaphore *S){ S->value --; if(S->Value < 0){ block( S->list ); }]signal(semaphore *S){ S->value++; if(S->value <= 0){ wakeup(S->list); }} 在记录型型号量中，S->value的初值表示系统中某类资源的数目；对它每次wait操作，意味进程请求一个单位的该类资源，使得系统中可分配的该类资源数减少一个，因此描述为S->value–；
当S.value<0时，表示在执行此次分配之前，系统中的该类资源已经全部分配完了，因此该访问进程应调用block原语进行自我阻塞，放弃处理机并插入到等待进程的队列S->list中。我们再来分析下signal操作，首先释放一个单位资源（S->value++），然后判断是否有进程在等待申请信号量，如果有的话，就应该调用wakeup原语从等待队列（list所链接的进程队列）中唤醒一个进程。
通过上面的描述，我们来说一下在记录型型号量中，value值所代表的意义：
- value>0，此时表示系统中还剩余的该类资源的数量；
- value=0，此时恰好处于一个平衡状态，系统中的资源分配完了，同样也没有进程在等待资源，即list队列中是没有等待进程的；
- value<0，此时，value的绝对值表示有多少个进程在等待申请信号量，也即是list队列的长度。并且P、V操作必须成对的出现，有一个P操作就必定有一个与之配对的V操作（当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现）。
4.3 AND型信号量
AND信号量正如其名，其基本思想是：
将进程在整个运行过程中需要所有资源，一次性的全部分配给进程，待进程使用完后再一起释放。AND 信号量可以满足某些进程需要申请多个资源后才可以执行任务的场景，并且AND 信号量可以解决死锁问题，
比始哲学家进餐问题中，一次给哲学家分配左右两支筷子，那么就不会有哲学家会因为吃不到而饿死了。AND 信号量使用的还是记录型信号量的数据结构，下面是 Swait 操作和 Ssignal 操作：
//记录型信号量定义typedef struct{ int value; struct process_control_block * list;}semaphore;//P操作SWait(S1, S2, ..., Sn){ while(true){ if(S1 >= 1 && ... && Sn>=1){ for(i = 1; i 需要注意的就是，因为一次申请多个资源，所以在申请的过程中，如果因为哪一类资源不足而阻塞（请求N多个资源时第一个发现不满足的资源，即资源数<1），就要将进程插入到对应信号量的list中；
与之对应的唤醒操作也有所不同，不再是唤醒阻塞队列中的某一个进程，而是将等待队列中的所有进程全部移除，插入到就绪队列中，让这些进程再次执行一次资源请求操作（这里因为是一次请求多个资源，后面可能依旧有资源无法满足进程的需求）。4.4 信号量集
在前面讲的信号量机制中，wait、signal操作仅能对信号量施以加1或者减1操作，当一次需要N个单位的资源时，便要执行N次的wait(S)操作，这显然是低效的，并且会增大发生死锁的概率（需要执行N次，在这N次执行的过程中可能会发生中断，资源也可能会被别的进程抢占）。
此外，在某些情况下，为了确保系统的安全性，当所申请的资源数量低于某一个下限时，就不予分配（保证地主家里有余粮）。
为了满足上述的两个需求，信号量机制又升级了，在AND型信号量的基础上进行扩充，对进程所申请的所有资源，在一次P、V操作中完成申请或释放。并且进程对每类信号量的测试值也不在是1，而是该资源的分配下限ti，也就是要求Si≥ti，否则不予分配。因此这里就不在给出具体的Swait和Ssignal的代码了，而是给出函数声明：
Swait(S1, t1, d1, ... , Sn, tn, dn);Ssignal(S1, d1, ... , Sn, dn);
这里与记录性型号量稍有不同的地方就是判断每类资源是否满足需求时，
判断的条件由Si>=1变为Si>=ti，并且分配资源由Si–变为Si=Si-ti； 与之对应的Ssignal操作，不同的一点就是，一次可以归还多个资源，相对应的资源释放代码由Si++变为Si=Si+ti。需要注意的是，因为AND型信号量和信号量集一次申请进程执行所需的全部资源，这样的优点就是简单、易行且安全，但是缺点也很明显：
- 资源被严重浪费，严重的恶化了资源的利用率；
- 使进程经常会发生饥饿现象（因为个别资源被占用的概率很大，会导致进程因为申请不到所有资源迟迟得不到执行）。
五、管程机制
虽然信号量机制是一种既方便、又有效的进程同步机制，但是每个访问临界资源的进程都需要自备同步操作wait(S)和signal(S)操作，这就使大量的同步操作分散在各个进程中，不利于大家去集中的思考、抽象，使得程序设计的时候难度非常大，容易产生各种各样的程序设计错误。
在这样的情况下，便产生了一种新的进程同步工具----管程（Monitors）。值得一提的是，管程也是迪杰斯特拉提出的。
hansen对管程的定义如下：
一个管程定义了一个数据结构和能力为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。由上述的定义可知，管程有四部分组成：
- 管程的名称；
- 共享数据结构说明；
- 对数据结构进行操作的一组过程；
- 初始化语句。
下面我们来看下管程的语法描述：
//管程的描述Monitor monitor_name { //管程名 share variable declarations; //共享变量说明 cond cond_declarationas; //条件变量说明 public: //能被进程调用的过程 void P1(...){ //对数据结构操作过程 ... } void P2(...){ ... } ... void(...){ ... } ... { initilization code; //初始化代码 }} 通过上面的代码描述，你是不是觉得很熟悉！
实际上，管程中包含了面向对象的思想，它将共享资源、对共享资源的操作抽象成变量和方法，并与同步机制一同封装在一个对象内部，隐藏了实现细节。但是你所不知道的是，在管程出现的时候，还没有面向对象程序设计，是不是很意外。
封装于管程内部的数据结构仅能被管程内部的过程访问（类似于Java中的私有变量），如果想在管程外部访问管程内部的数据结构，就必须使用内部过程（管程内部的public修饰的方法，Java 类中的公共方法）。
所有的进程想要访问临界资源，都只能通过管程间接的访问，并且管程每次只允许一个进程进入管程，从而实现了进程互斥。
有一点需要说明的是，管程为了实现更加复杂的进程同步方式，增加了一个条件变量。
通常会根据进程被阻塞或者挂起的原因，设置不同的条件变量， 每个条件变量保存一个链表指针，用与链接所有因为该条件变量而阻塞或挂起的所有进程， 同时提供两个P、V操作也可以表示为x.wait和x.signal，这两个操作的含义如下：
- x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列中，并释放管程，直至x条件发生变化。
- x.signal：正在调用管程的进程因为x条件发生了变化（资源使用完，归还），则调用x.signal，重新启动一个因x条件而阻塞或挂起的进程，如果存在多个，则选择其中的一个，如果没有，继续执行原进程，不产生任何唤醒操作。
对于上面的操作，其实是有些问题的，我们设想一下，如果进程P1因x条件处于阻塞状态，那么当进程P2执行了x.signal操作唤醒P1后，进程P1和P2此时同时处于管程中了，这是不被允许的，那么如何确定哪个执行哪个等待？这个问题也很简单，可采用下面的两种方式之一进行处理：
- P2等待，直至P1离开管程或者等待另一个条件；
- P1等待，直至P2离开管程或者等待另一个条件。
采用哪种处理方式，也存在很多争论。Hoare采用了第一种处理方式，而Hansen采用了两者的折中，它规定管程中的所有过程执行的signal操作是过程体的最后一个操作，于是，进程P2执行完signal操作后立即退出管程，因此进程P1马上被恢复执行。
但是hansen的这种折中的办法，规定死了释放的时机，增加了程序设计的难度。因此现在的管程普遍采用Hoare的方式，也被称为霍尔管程。霍尔管程相比于管程、汉森管程，他的一个更大的优势是可以基于PV操作原语来实现，换一句话说就是，wait和signal可以是程序过程而不需要是原语实现（可以使用语言机制实现霍尔管程）。这个就很厉害了，霍尔管程可以基于操作系统的程序库或者是高级程序设计语言，在基础的P、V操作原语上实现wait和signal操作，而不用扩展操作系统的内核。
管程的示意图如下，从图中我们可以看到，每个条件变量都有一个对应的等待队列，除了等待调用管程的进程队列外，还有一个紧急队列（优先级高，由进程调用signal操作后插入），对于具体的操作，我们可以结合霍尔管程中条件变量中的wait、signal操作来讲。
下面是霍尔管程的条件变量上的wait操作和signal操作的描述：
//霍尔管程使用的信号量定义//semaphore为本文之前定义的记录型信号量typedef struct{ semaphore mutex; //用与管程调用的互斥信号量 semaphore next; //发出signal的进程挂起自己的信号量，信号量中记录着等待调用管程的进程 int next_count; //在next上等待的进程数}interf;//霍尔管程中的条件变量typedef struct{ semaphore x_sem; //与资源相关的信号量 int x_count; //在x_sem上等待的进程数}cond;//条件变量对应的wait操作wait(cond declar, interf IM){ declar->x_count++; //在条件变量declar上等待的进程数量加1 if(IM->next_count > 0){ //判断是否有进程在高优先级队列中 V(IM->next); //唤醒因调用signal操作的进程 } else { V(IM->mutex); //没有的话，唤醒一个等待进入管程的进程 } P(declar->x_sem); //释放资源后，立即把自己挂起 declar->xcount--; //恢复执行后，重新开始执行，退出管程，条件变量declar等待的进程数量减1}//条件变量对应的signal操作signal(cond declar, interf IM){ if(declar->x_count > 0){ //判断是否有等待条件变量的进程 IM->next_count++; //挂起自己后，因为调用signal挂起自己的进程数量加1 V(declar->x_sem); //唤醒一个等待条件变量的进程 P(IM->next); //释放资源后，立即把自己挂起,进入高优先级队列 IM->next_count--; //恢复执行后，等待调用的管程的进程数量减1 }} 我们看上面的代码，此时的wait操作和signal操作与P、V原语是有区别的，wait和signal是在P、V的基础上实现的。首先我们来看下wait操作，唤醒进程（高优先级队列或者是等待调用管程的队列）后，立即将自己挂起，并将自己插入到对应的条件变量的等待队列中（上图中左上方的队列），当被唤醒再次执行时，将对应的等待数量减1。我们在来看下signal操作，首先判断是否有等待条件变量的进程，如果没有的话，就可以什么都不用执行；如果有进程在条件变量的等待队列中，则从队列中唤醒一个，并挂起自己，插入到紧急队列中。
霍尔管程中的wait、signal操作比较抽象，可以结合图片查看，可以帮助理解。
学自《》
转载地址：https://ciellee.blog.csdn.net/article/details/107331288 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
