0
0

【操作系统】第10话 · 进程同步与进程互斥是亲戚嘛？

🌕写在前面

​

​​​​​​​本专栏的名字为【闪耀计划】，目的是通过百天刷题计划，通过题目和知识点串联的方式，完成对计算机操作系统的复习和巩固；同时还配有专门的笔记总结和文档教程哦！想要搞定，搞透计算机操作系统的同学，本专栏将会通过模块化的分类，刷够1000道题，为大家提供点对点的考点相关知识轰炸！值得注意的是，本专栏将会通过教程+课后习题的方式来进行巩固教学，课后习题的题量也是算入总题数的哦！

🎉订阅本专栏，将为你带来最一手的备战秘籍！🎉

🍊博客主页：kikoking的江湖背景🍊

​​

🌟🌟往期回顾🌟🌟

【操作系统】第七话 · 处理机调度本章内容从整体角度对处理机调度的三种层次进行对应的分析和讲解，同时介绍了一些调度的评价标准，这类问题可能会考计算题哦！https://kikoking.blog.csdn.net/article/details/125341048【操作系统】第六话·线程是进程的(宝ᴗ宝)嘛？从今天开始，我们将要开启一个新的系列【闪耀计划】，没错！这是今年上半年的一整个系列计划！本专题目的是通过百天刷题计划，通过题目和知识点串联的方式，完成对计算机操作系统的复习和巩固；同时还配有专门的笔记总结和文档教程哦！想要搞定，搞透计算机操作系统的同学，本专栏将会通过模块化的分类，刷够1000道题，为大家提供点对点的考点相关知识轰炸！值得注意的是，本专栏将会通过教程+课后习题的方式来进行巩固教学，课后习题的题量也是算入总题数的哦！https://kikoking.blog.csdn.net/article/details/123444446

​

🍺知识点12：进程同步

🍯12.1 同步与互斥的概念

🥝1.什么是进程同步？

在多道程序环境下，进程是并发执行的，具有异步性，不同进程间存在不同的制约关系。进程同步就是为了协调进程间的相互制约关系，解决进程的异步问题。

我们可以通过一个简单的例子来说明，例如我们计算5\times 2+1​，这时系统就会产生2个进程，一个是加法进程，一个是乘法进程。我们作为人类，当然明白“先乘除、后加减”的原则，但是计算机并不知道，它的操作行为具有异步性，如果不设定一定的机制进行限制，它可能会进行“先加减、后乘除”的错误解法。进程同步就是这里所设定的机制。

🥝2.什么是进程互斥？

进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源后，另一个进程才能去访问临界资源。

临界资源：我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源；还有一些变量、数据也可被若干进程共享，也属于临界资源。

Q1：访问临界资源的过程有哪些？

A1：在每个进程中，访问临界资源的那段代码称为临界区，通常我们将临界资源的访问过程分为4个部分：

do {
    entry section;     //进入区：负责检查可否进入临界区；若可进入，应设置正在访问临界区标志（上锁），防止其他进程同时进入临界区
    critical section;  //临界区：访问临界资源的那段代码
    exit section;      //退出区：负责将正在访问临界区的标志解除（解锁）
    remainder section; //剩余区：其他代码
}while(true)

值得注意的是，上述4区中，进入区和退出区是负责实现进程互斥的代码段，负责处理各个进程的互斥关系，后续我们的代码题基本上都是围绕这两区进行的哦！

🥝3.同步和互斥的关系

​

关于这二者的区别，我们通过两个例子可以更好地进行解释说明：

同步（合作制约）：例如有两个进程A、B，其中进程B只有获得进程A的数据才能运行，即A、B之间存在合作关系。在这种情况下，一旦进程A将数据送入缓冲区，进程B就会被唤醒；反之，当缓冲区满时，进程A被阻塞，只有当进程B取走缓冲区数据时，才唤醒进程A。

互斥（被动制约）：例如只有一台打印机，此时有两个进程A、B都需要使用打印机。若此时系统先将打印机分配给进程A，那么进程B必须堵塞，被动等待；只有当进程A将打印机释放后，系统便将进程B唤醒，将其由阻塞态变为就绪态。

特别值得注意的是，为了禁止两个互斥的进程同时进入临界区，同步机制应当遵循以下原则：

  1. 空闲让进：临界区空闲时，允许一个请求进入临界区的进程立即进入。
  2. 忙则等待：当有进程进入临界区时，其他试图进入临界区的进程必须等待。
  3. 有限等待：对请求访问的进程，应当保证在有限时间内进入临界区。
  4. 让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

kiko：关于实现临界区的互斥主要有软件层面和硬件层面两类方法，接下来我们首先来学习软件层面的方法。

🍯12.2 临界区互斥的软件实现方法

软件层面的算法总思路是在进入区设置一些标志，以此来标明是否有进程在临界区中，若已有进程在临界区，通过while循环检查进行等待，进程离开临界区后在退出区修改标志。

🥝1. 单标志法

算法思想：设置一个公共变量turn，用于标识被允许进入临界区的进程编号，即若turn=1，则允许进程p_{1}​进入临界区；若turn=0，则允许进程p_{0}​进入临界区。一个进程在访问完临界区后，会把临界区的权限转交给另一个进程，即每个进程进入临界区的权限由另一个进程赋予，这就实现了多个进程交替进入临界区。

//假设两个进程进行互斥访问

int turn = 0;     //turn表示当前进入临界区的进程号，初始化为0，表示先运行P0进程

P0进程:
while (turn != 0) //进入区：如果turn的值不为0，就一直进行while循环，执行空语句（相当于等待）
;
critical section; //临界区
turn = 1;         //退出区：将turn值赋值为另一个进程的进程号，此处将其赋值为1
remainder section;//剩余区

P1进程:
while (turn != 1) //进入区：如果turn的值不为1，就一直进行while循环，执行空语句（相当于等待）
;
critical section;
turn = 0;
remainder section;

算法优点：该算法可以保证每次只有一个进程进入临界区。

算法缺点：由于每个进程进入临界区的权限由另一个进程赋予，因此当一个进程不进入临界区时，也就不会进入退出区进而赋予下一个进程权限，这就导致了下一个进程将无法进入临界区。例如P0进程顺利进入临界区后并离开，在退出区时赋予进程P1权限，然而P1并不打算进入临界区，此时进程P1就不会运行退出区里turn=0；这条语句，turn=1将一直成立，P0就无法再次进入临界区。

🥝2. 双标志法（先检查）

算法思想：在每个进程访问临界资源前，先查看临界资源是否正被访问，若正被访问，则该进程需要等待；否则，该进程访问临界资源。因此我们设置一个数据 *flag[ i ] *来标识第i个进程是否进入了临界区，如果p_{i}​进程未进入临界区，则 flag[ i ] = FALSE；若p_{i}​进程进入临界区，则 flag[ i ] = TRUE。

//假设两个进程进行互斥访问

Pi进程:
while (flag[j]) ①  //进入区：如果flag[j]为真，即Pj进程进入临界区，就循环执行空语句（等待）
;
flag[i] = TRUE; ②  //进入区：当flag[j]为假，即Pj进程未进入临界区，将Pi进程标志置为TRUE
critical section; //临界区
flag[i] = FALSE;  //退出区：将进程i的flag设置为FALSE，表示Pi进程离开临界区
remainder section;//剩余区

Pj进程:
while (flag[i]) ③
;
flag[j] = TRUE; ④
critical section;
flag[j] = FALSE;
remainder section;

算法优点：各个进程可以不用交替进入，能连续使用。

算法缺点：Pi 和Pj 进程可能会同时进入临界区，违背了“忙则等待”的准则。这是因为while判断与flag赋值操作不能一气呵成的执行，即计算机可能会按照①——>③——>②——>④的顺序并发执行这两个进程，导致这两个进程都判断此时临界区空闲，都为它们自己的flag赋值。

🥝3. 双标志法（后检查）

算法思想：由于双标志法（前检查）中，检查与赋值操作无法一气呵成执行，因此会导致两个进程同时进入临界区。因此“后检查双标志法”将检查放到了赋值之后，先将自己的标志设置为TRUE，再检测对方的状态标志，若对方的标志为TRUE，则进程等待；否则进入临界区。

//假设两个进程进行互斥访问

Pi进程:
flag[i] = TRUE;   //进入区：为Pi进程的flag赋值为TRUE
while (flag[j])   //进入区：如果flag[j]为真，即如果Pj显示TRUE，就循环执行空语句（让Pj进程进临界区）
;
critical section; //临界区：若flag[j]为假，表明Pj进程未进入临界区，则跳出while循环，Pi进程进入临界区
flag[i] = FALSE;  //退出区：将Pi进程的flag置为假
remainder section;//剩余区

Pj进程:
flag[j] = TRUE; 
while (flag[i])   
;
critical section; 
flag[j] = FALSE;  
remainder section;

算法优点：避免了两个进程同时进入临界区的情况发生。

算法缺点：当两个进程几乎同时想进入临界区时，Pi 与 Pj 进程分别将自己的 flag 都设置为TRUE，此时它们同时检测对方状态都为TRUE，发现对方也要进入临界区，于是双方都谦让对方先进临界区，结果二者都进不了临界区，从而导致“饥饿”现象。

🥝4. Peterson算法

算法思想：Peterson算法对“后检查双标志法”又进行了改进，为了防止两个进程想同时进入临界区而无限等待，又另外设置了一个变量turn，用来表示优先让哪个进程进入临界区，比如 *turn=j *，表示优先 *Pj *进程进入临界区， *Pi *进程就需要等待。

Q1：为什么加了一个turn变量就能避免两个进程无限等待呢？

A1：之所以加一个turn变量就能改进是因为turn的值取决于最后执行的那一条语句，由于进程并发执行，Pi 和 Pj 可能同时都想访问临界区，但是这两个进程中的turn的赋值语句的执行具有先后顺序。若Pi 进程先执行turn=j，Pj 进程后执行turn=i，那么turn的最终值为i，这将决定 *Pi *进程先进入临界区，避免了二者无限等待的情况发生。

//假设两个进程进行互斥访问

Pi进程:
flag[i] = TRUE;    //进入区：将Pi进程标志设置为TRUE（主动争取）
turn = j;          //进入区：将临界区的优先进入机会给Pj（主动谦让）
while (flag[j] && turn = j) //进入区：当Pj进程的进程标志为真且turn都为j时，循环执行空语句（等待）
;
critical section; //临界区
flag[i] = FALSE;  //退出区：将Pi进程的flag标志置FALSE
remainder section;

Pj进程:
flag[j] = TRUE;    
turn = i;         
while (flag[i] && turn = i)
;
critical section; //临界区
flag[j] = FALSE;  //退出区：
remainder section;

算法优点：避免了两个进程都想进入进程时而相互等待的情况发生。

算法缺点：未遵循让权等待的原则，因为在等待过程中，进程依然占用处理机，不断运行while循环的空语句，当然这个缺点在上述四种算法都有，但因为Peterson太优秀了，所以只能挑出这个毛病。

kiko：接下来我们开始介绍临界区互斥的硬件实现方法，通过硬件支持实现临界段的问题，这种方法称为“元方法”或“低级方法”。

🍯12.3 临界区互斥的硬件实现方法

🥝1. 中断屏蔽方法

方法原理：利用“开/关中断指令”实现，防止其他进程进入临界区进行访问。这类方法同“原语”的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，因为CPU只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完，从而保证进程互斥的正确实现。

···
关中断; //关中断后不允许当前进程被中断，也不然不会发生进程切换

临界区;

开中断; //直到当前进程访问完临界区，再执行开中断指令，才有可能让别的进程访问临界区
···

方法优点：简单、高效。

方法缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组特权指令如果给用户进程使用，则可能会使得一个进程关中断后不再开中断。）

🥝2. 硬件指令方法（TSL）

方法原理：该指令方法简称为TS指令或TSL指令，它是用硬件实现的，执行的过程不允许被中断，只能一气呵成。它的功能是读出指定标志后，把该标志置为真。使用该指令时，为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态：true表示正被占用（上锁），false表示未被占用（未上锁），初始值为false。

bool TestAndSet(bool* lock) {
    bool old;
    old = *lock;    //old用来存放lock原来的值
    *lock = true;   //无论之前是否已加锁，都将lock设置为true，为其上锁
    return old;     //返回lock原来的值
}

在进程访问临界资源前，系统利用TSL指令检查和修改标志lock，下面是使用TSL指令实现互斥的算法逻辑：

while (TestAndSet(&lock)) //进入区：当TSL返回的值为true时，说明临界区上锁，现有进程循环执行空语句（等待）
;
critical section; //临界区：只有当TSL返回false值时，即临界区未上锁，该进程才会进入临界区
lock = false; //退出区：对该资源进行解锁
remainder section;

Q1：这种方法是如何实现进程互斥的呢？

A1：按照上面的说法，可能会较难理解，因此我们这里通过两种情况的例子来进行分析：

  • lock的初始值为false时：这种情况下TSL返回的old值为false（表示资源未被占用），while 循环条件不满足，跳出循环，进入临界区。
  • lock的初始值为true时：TSL返回的old值为true（表示资源正被占用），while循环条件满足，将一直循环空语句，直到当前访问临界区的进程在退出区进行解锁。

方法优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞，适用于多处理机环境。

方法缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU循环执行TSL指令，从而导致“忙等”。

🥝3. Swap指令

方法原理：Swap指令是用硬件实现的，执行过程不允许被中断，只能一气呵成；它的功能是交换两个字（字节）的内容。

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

使用Swap指令实现进程互斥的算法逻辑如下：

bool old = true;
while (old == true)
    Swap(&lock, &old);
critical section;
lock = false;
remainder section;

对于上述算法，是如何实现进程互斥的呢？我们同样举两种情况的例子来分析一下：

  • lock的初始值为false时：首先将old值赋为true，从而进入while循环并执行Swap函数，这种情况下Swap会将lock的值与old值相交换，这时old会被赋值为false，lock会被赋值为true；然后进行下一轮循环，此时由于old值为false，因此跳出while循环，该进程进入临界区。
  • lock的初始值为true时：这时依然先为old赋值为true进入while循环，执行Swap函数，将old赋值为true，lock交换后也赋值为true；然后由于old值依然为true，因此继续进行循环，直到临界区的进程进入退出区将lock值修改为false才可跳出循环。

方法优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。

方法缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行Swap指令，从而导致“盲等”。

标签： 操作系统 进程同步 进程互斥
本文转载自: https://blog.csdn.net/qq_54151955/article/details/125829919
版权归原作者 kikokingzz 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【操作系统】第10话 · 进程同步与进程互斥是亲戚嘛？”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

Docker 中使用环境变量的安全实践

[Linux]——常见指令（中）

【IntelliJ IDEA】IntelliJ IDEA中文语言包不起作用

vscode gitlens收费破解

是时候用开源降低AI落地门槛了

毕设开源 深度学习手写数字识别系统(源码+论文)

毕业设计 大数据电商用户行为分析及可视化(源码+论文)

文章导航