同步与互斥

进程同步与进程互斥

进程同步

首先我们在前面已经知道进程具有异步性的特点，异步性是指各进程并发地以各自独立的，不可预知的速度向前推进。而在某些需求上，仅仅实现异步性是不可以的。例如：进程通信中的管道通信，读进程和写进程是并发执行的，由于并发性必然导致异步性，因此“写数据”和“读数据”两个操作虽然根据并发和异步的特点会在一个时间间隔内交叉运行，但是归根结底，“读数据”时必须在“写数据”后面的，所以这里仅仅有异步性是不能满足这个需求的实现的，因为并发异步执行的先后顺序是不确定的。

所以这里我们引入了“进程同步”的概念，它是指为了完成某个任务（如上面的管道通信）而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而产生的限制关系。进程间的直接限制关系主要就是来源于他们之间的相互合作。

进程互斥

进程的“并发”需要“共享”的支持（前面讲过并发和共享相互存在，是操作系统进程的两大基础特性）。那么各个并发执行的进程不可避免的需要共享一些资源（比如内存，又比如打印机、摄像头等I/O设备），所以这里根据同一时间段内能否允许多个进程同时使用这个共享资源将共享细分为两类。

同时共享方式

即系统中的某些共享资源，允许一个时间段内由多个进程“同时”对其进行访问。

互斥共享方式

即系统中的某些共享资源，虽然可以提供给多个进程使用，但是一个时间段内只允许一个进程访问该资源。

我们把一个时间段内只允许一个进程使用的资源称为临界资源（前面也讲过访问临界资源的代码段称为临界区）。许多物理设备（比如摄像头，打印机）都属于临界资源，此外还有许多变量，数据，内存缓冲区等都属于临界资源。对临界资源的访问，必须互斥的进行。互斥，亦称为间接制约关系。

进程互斥是指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源以后，另一个进程才能去访问临界资源。所以互斥共享实际上就要求进程互斥关系。

对临界资源的互斥访问，可以在逻辑上分为如下四个部分：

临界区是进程访问临界资源的代码段，进入区和退出区是负责实现互斥的代码段（后面所讲的互斥锁PV操作代码段就是这两个区内完成），临界区也称为“临界段”。

思考：如果一个进程暂时不能进入临界区，那么该进程一直占用着处理机吗？该进程要是一直进不去临界区怎么办？

为了实现对临界资源的互斥访问，同时还要保证系统的整体性能，需要遵循以下原则：

空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
忙则等待：当已有进程进入临界区，其他试图进入临界区的进程必须等待。
有限等待：对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饿死）。
让权等待：当进程不能进入临界区，应立即释放处理机，防止进程忙等待。

思考：有限等待和让权等待不矛盾吗？

可能你会认为一方面保证进程会在优先时间内等待到进入临界区，一方面又说当不能进入临界区就释放处理机，那进程到底等不等？实际上有限等待的意思是保证进程在一段时间后必定会被操作系统提示可以进入临界区，而让权等待的意思是该进程在等待时就不要在这用cpu了，先阻塞或者挂起等待，在有限等待以后在唤醒该进程上cpu然后范文临界资源，所以不矛盾。

总结

进程互斥的软件实现方式

很明显进程互斥有研究的内容，毕竟具体怎样实现互斥的方法有多种，我们一一了解。

思考：进程互斥需要解决的根本问题？

首先我们先思考一个问题，现在有两个进程A和B并发地运行，如下图：

那么当A上处理机运行使用打印机时，我们知道根据调度算法，一般一个进程会在执行一个时间片（一般现在的操作系统都是MFQSA调度）后，可能并没有执行完，但是也需要下cpu让另一个进程开始执行，此时进程B上cpu后也开始运行使用打印机，这样结果就是A,B的内容混在了一起（这也解释了前面介绍系统调用必要性的例子中打印内容会混合在一起的原因），那么该怎样才能解决这个问题呢？

单标志法

算法思想：两个进程（注意只适用于两个对象的情况）在访问临界区后会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限只能被另一个进程赋予）。代码如下：

首先我们定义一个全局变量turn=0,turn表示当前允许进入临界区的进程号，因为就两个进程，所以0表示允许进程0访问临界资源，1表示允许进程1访问临界资源。

1	`int turn = 0;`

然后进程0的代码如下，这里我们要自己完善进入区和退出区，因为两个进程要互斥访问，所以1能否进入临界区取决于进程0有没有访问完，所以进程0访问完只需通知一下进程1现在可以进入即可，相对应的就是在退出区让turn=1，这样就可以允许进程1在进程0访问完以后进入临界区了。

P0：

//如果此时是对方进入回合即turn值为1则一直执行空语句等待
while(turn!=0){};    ----1//进入区
critical section； ----2//临界区
turn =1;   ----3//退出区
remainder section    ----4//剩余区

相对应的P1访问完临界区后也要告诉P0现在可以访问临界区了，所以turn=0;

P1:

//如果此时是对方进入回合即turn值为0则一直执行空语句等待
while(turn!=1){};    ----5//进入区
critical section； ----6//临界区
turn =0;   ----7//退出区
remainder section    ----8//剩余区

这样turn的初始值为0，所以一开始只允许进程0进入临界区，若P1先上的cpu执行到了访问临界区代码，则会一直卡在代码段5，即进入区禁止进入，此时就一直到P1的时间片用完，调度切换到P0上处理机运行，代码1就不会卡在P0，所以P0可以正常访问临界区，此时如果在P0还在访问临界区阶段时间片到了，此时turn还没有更新到1，所以即使切换到P1此时P1还是在等待，直至P0访问完临界资源并更新了turn值以后P1才能进入临界区。

因此，这种算法可以在软件层次上实现“同一时刻最多只允许一个进程访问临界区”。但是貌似有一些小问题，比如只能按照P0->P1->P0->P1…这样的顺序轮流访问，这种必须“轮流访问”的问题是，如果此时允许进入临界区的进程是P0，而P0一直不访问临界区或者根本就不想访问临界区，那么此时虽然临界区是空闲的，但是也不允许P1访问，因此单标志法违背了“空闲让进”原则。并且这种方法对于多个进程的情况会比较复杂。

注意：上方代码的while后面带分号什么意思？

一定要仔细观察代码，发现是对于P0，当turn!=0时在一直循环while的空语句表示等待，所以P0也可以写成：

while(turn!=0);    ----1//进入区
critical section； ----2//临界区
turn =1;   ----3//退出区
remainder section    ----4//剩余区

这个;很致命，一定要透彻理解第一行whlie语句的意义，他是判断是否需要等待，所以这里的判断条件为turn!=0则表示此时如果不是0的回合，那么0代码就一直在while后面的{};语句中执行空语句等待，这里因为{}里面是空语句所以可以省略大括号，P1同上原因。后面也都是这样表示。

双标志先检查法

算法思想：设置一个布尔型数组flag[],数组中各个元素用来标记各进程想进入临界区的意愿，比如"flag[0]=true"表示0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身的对应标志位flag[i]设置为true，之后开始访问临界区。

我们这里还是以进程P0和进程P1为例。首先初始化flag为两位，且一开始都默认为不想访问临界资源。

1	`bool flag[2]={false,false};`

然后P0和P1每次访问前都先检查对方是否进入临界区，如果对方不想（即flag=false)那么就将自身的标志位设置为true,这样在自己访问临界资源期间，对方是不能进入的，当访问结束后再将自身的标志位设置为false。

P0：

//如果此时对方想进入即布尔值为true则一直执行空语句等待
while(flag[1]); ----1  // 进入区
flag[0]=true; ----2//将自身标志位更新为true 进入区
critical section ---3//访问临界资源  临界区
flag[0]=false  ----4//访问完毕，将自身标志位在更新为false 退出区
remainder section //剩余区

P1:

//如果此时对方想进入即布尔值为true则一直执行空语句等待
while(flag[0]);  ----5 //进入区
flag[1]=true; ----6//将自身标志位更新为true 进入区
critical section ---7//访问临界资源  临界区
flag[1]=false  ----8//访问完毕，将自身标志位在更新为false 退出区
remainder section //剩余区

这个看似完美，实际上比上一个单标志法还不靠谱，他存在一个重大的bug，就是如果按照1->5->2->6->3->7的顺序执行，即假设现在flag数组所有位置都为false,即此时临界资源空闲，然后P0执行完允许进入后进入区判断以后突然时间片用完了，那么此时P0该下cpu了并且PCB记录此时状态是被允许进入空闲资源的，然后此时调度切换到P1执行了进入区代码，此时他发现P0的标志位仍然是false呢，所以他也进入，但是就那么巧，此时P1也用完时间片了下cpu前PCB记录此时被允许进入临界资源的状态，然后又切回了P0开始执行临界区，结果此时又用完时间片了此时P0还在临界资源，里面的P0临街资源还没被释放，P1又进来了，此时也可以对临界资源进行读写，完蛋，打印的内容又混在了一起。所以此时违背了“忙则等待”的原则。

思考：能不能优化一下代码避免这种bug?

可以，我们仔细观察，发现出现这种问题主要是因为进入区的“检查”和“上锁”两个操作不是一气呵成的所以会有可能在“检查完”和“上锁前”出现进程切换。所以我们可以更改一下操作顺序，管那么干嘛，先上上锁不让别人进来然后再检查，即更改成如下

双标志后检查法

首先初始化肯定是不变的

1	`bool flag[2]={false,false};`

但是此时是先上锁在检查

P0：

flag[0]=true; ----1//先上锁 进入区
//如果此时对方想进入即布尔值为true则一直执行空语句等待
while(flag[1]); ----2 // 进入区
critical section; ----3//临界区
flag[0]=fasle; ----4//访问完后解锁 退出区
remainder section;

P1:

flag[1]=true; ----5//先上锁 进入区
//如果此时对方想进入即布尔值为true则一直执行空语句等待
while(flag[0]);----6//进入区
critical section; ----7//临界区
flag[1]=fasle; ----8//访问完后解锁 退出区
remainder section;

好像更改完确实不会在发生“忙则不等待”的问题了，但是此时貌似又出问题了，按照1->5->2->6的顺序即进程0想访问临界资源然后上锁了但是在检查前时间片用完了，切换到进程1他也先上锁然后发现0貌似已经上锁了所以就一直停在了代码6直至时间片用完，此时又切换回了进程0，由于进程1并没有检查完发现不能进以后解锁的操作，所以此时进程0也会发现进程1貌似也已经上锁了，所以进程0也一直卡在检查区代码2最终时间片用完，就这样即使空闲资源空闲，但是双方都发现对方上锁了就都一直不进入（其实就是产生了对方正在访问的误会），产生了饥饿现象。所以双标志后检查法不能应用。

思考：难道不能进一步优化双标志位法避免bug?

你可能会想到之所以双方都不进入是因为在检查到对方上锁后自己不能进入后没有解锁的操作，所以可能认为在2和6下方各加上一个若发现对方在就自己解锁的操作。但是你会发现无论这个功能根本实现不了，无论这个解锁操作放在哪里都不太合适仍然会触发更多的bug，所以就不要在尝试优化双标志法了，直接放弃思考一个更好的方法。

Peterson算法

算法思想：结合双标志法和单标志法的思想特点，如果双方都想争着进入临界区，那么就尝试互相退让，作一个有礼貌的进程。

其实实现也很简单就是有添加一个新的参量turn表示优先让哪个进程进入临界区，这样就实现了进程之间的谦让，代码如下：

还是先初始化

1 2	`bool flag[2]={false,false};//初始化时默认此时双方都不想访问临界资源 turn=0;//初始化时默认进程1谦让进程0`

P0:

flag[0]=true; ----1//表达自己想进去的意愿上锁 进入区
turn=1; -----2//优先让1进程进，即自己谦让有礼貌 进入区
//如果此时1也想进入即对方上锁了且自己谦让，那么就循环空语句等待
while(flag[1]&&turn==1);----3 //进入区
critical section; ----4//临界区
flag[0]=false; ----5//访问完了，解锁 退出区
remainder section; //剩余区

P1：

flag[1]=true; ----6//表达自己想进去的意愿上锁 进入区
turn=0; -----7//优先让0进程进，即自己谦让有礼貌 进入区
//如果此时0也想进入即对方上锁了且自己谦让，那么就循环空语句等待
while(flag[0]&&turn==0);----3 //进入区
critical section; ----4//临界区
flag[1]=false; ----5//访问完了，解锁 退出区
remainder section; //剩余区

此时进程们都很有礼貌了，每次自己想进去时都会谦让，这是我们在走一次1->2->3->6->7->8我们会发现确实做到了“忙则等待”和“空闲让进”并且没有在出现重大致命bug了，但是此种方法也不是太好，首先turn值限制了当涉及到多各进程之间时也很复杂，turn就会变得不那么简单，其次他和前面两种方法一样也没有做到“让权等待”即等待是下处理机，而是一直在循环执行while的空语句所以一直在占用cpu，所以peterson算法虽然比前面的方法好但是也不够好。

总结

进程互斥的硬件实现方法

中断屏蔽方法

利用“开/关中断指令”实现（和原语的实现思想相同，即在某个进程开始访问临界区到结束访问临界区为止都不允许中断，也就不会发生进程切换了因为时钟管理也只是在时间片结束后向cpu发送中断信号但是cpu可以忽视即决定权在cpu手中，这样也就不可能发生两个同时访问临界区的情况了）

优点很明显，简单高效确实实现了进程互斥的所有原则，但是缺点是不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令都是特权指令，只能运行在内核态，这组指令如果用户可以随意使用会很危险，所以覆盖范围太小）

TestAndSet指令

简称TS指令，也有地方成为TestAndSetLock指令，或者TSL指令，TSL是用硬件实现的，执行的过程不允许被中断只能一气呵成（很像原语），这里我们用C语言描述一下逻辑（但是一定要注意是硬件实现的，不是软件实现）。

//布尔共享变量lock表示当前临界区是否被加锁
//true 表示已加锁，false 表示未加锁
bool TestAndSet(bool *lock){
    bool old;
    old=*lock;//old用来存放lock原来的值
    *lock=true;//无论之前是否已经加锁，现在都将lock设置为true;
    return old;
}

//以下是使用TSL指令实现互斥的算法逻辑
while(TestAndSet(&lock));//上锁并检查 进入区
critical section;//临界区
lock=false;//访问完解锁 退出区
remainder section;//剩余区代码

实际上TSL就是通过硬件手段强制检查和上锁必须一气呵成执行（主要是因为TSL指令必须一气呵成，而TSL就一次完成上锁和检查），此时如果刚开始lock是false,则TSL返回的old值不满足while循环条件，直接跳过等待循环，进入临界区，如果刚开始lock是true,则执行TSL后old返回的值为true，此时满足while循环条件，会一直循环等待，直至当前访问临界区的进程在退出区进行“解锁”后该进程再访问临界资源。相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式绑定为一气呵成的原子操作，但是注意他不是真的原语，只是具有原语的特性。

优点是实现简单就可以避免bug，这种无需软件实现方法那样严格检查是否会有逻辑漏洞，适用于多处理机环境，缺点是不满足“让权等待”，一旦无法进入临界区进程就会一直执行循环空语句占用cpu。

Swap指令

有的地方也叫作Exchange指令，或简称XCHG指令，Swap指令也是使用硬件实现的，执行的过程中不允许被打断，只能一气呵成，以下是用C语言描述的逻辑（但是一定要注意是硬件实现的，不是软件实现）。

//Swap指令的作用是交换两个变量的值
Swap(bool *a, bool *b){
    bool temp;
    temp=*a;
    *a=*b;
    *b=temp
}

//以下是用Swap指令实现进程互斥的算法逻辑
//lock 表示当前临界区是否被加锁
bool old=true;
while(old==true){
    Swap(&lock,&old);
}
critical section;
lock=false;
remainder section;

看着有点晕😫，正常。我们来屡一下思路，首先我们有一个地方需要注意，此时的while后面不再是空语句了，而是Swap语句，这也就说明加入while判断条件返回为true即old为true,那么就会一直执行Swap(&lock,&old)交换lock和old值然后在判断，所以知道这一点后我们先假设lock=true的情况，那么此时说明有其他进程正在访问临界资源呢，然后bool设置为true后满足while条件进入循环语句内此时lock和old都是true，所以交换后还会满足while判断条件，所以又交换因此当当前正在访问临界资源的进程没有访问完，lock和old就会一直为true，所以等待的进程就是一直在不断的swap，直到那个进程访问完将lock更改为false,此时在经过1~2次的swap就会出现lock=true(实际上lock的true是和old换来的）,old=false(实际上old的false是和lock换过来的)此时这个进程就不在等待了出循环开始访问临界资源。而当lock一开始为false即临界资源空闲的情况，那么进入while循环一次后就会出现lock=true(实际上lock的true是和old换来的）,old=false(实际上old的false是和lock换过来的)的情况所以此时该进程就不需要等待就可以进入了。所以这个指令实现的方法很神奇，他唯一可以进入临界资源的情况就是出现lock=true(实际上lock的true是和old换来的）,old=false(实际上old的false是和lock换过来的)，当没有出现这个情况时等待的进程也不是一直循环空语句，而是一直在swap(虽然此时lock和old都为true😂),即使初始时临界资源空闲也要执行一次swap，所以无论何种情况，swap至少执行一次。并且转来转去实际上Swap和TSL实现的逻辑思路一模一样。

优点也是实现简单就可以避免bug，这种无需软件实现方法那样严格检查是否会有逻辑漏洞，适用于多处理机环境，缺点是不满足“让权等待”，一旦无法进入临界区进程就会一直循环执行Swap语句占用cpu。