五天自学完 王道考研-操作系统 第二章 进程同步、进程互斥、实现、信号量、管程、死锁

本文主要是介绍五天自学完 王道考研-操作系统 第二章 进程同步、进程互斥、实现、信号量、管程、死锁,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第二章 进程同步、进程互斥、实现、信号量、管程、死锁

  • 一、进程同步
    • 进程具有异步性的特征。
    • 同步亦称直接制约关系。
  • 二、进程互斥
    • 互斥亦称间接制约关系。
    • 为了实现对临界资源的互斥访问,同时保证系统整体性能,需要遵循以下原则:
      • 1.空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区;
      • 2.忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待;
      • 3.有限等待。对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿)
      • 4.让权等待。当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。
  • 三、进程互斥的软件实现方式
    • 1.单标志法
      • 该算法可以实现“同一时刻最多只允许一个进程访问临界区”。
      • 主要问题:违背“空闲让进”原则。
    • 2.双标志先检查法
      • 主要问题:违反“忙则等待”原则。
    • 3.双标志后检查法
      • 解决了“忙则等待”的问题
      • 主要问题:违背了“空闲让进”和“有限等待”原则
    • 4.Peterson算法
      • Peterson算法用软件方法解决了进程互斥问题,遵循了空闲让进、忙则等待、有限等待三个原则
      • 但是依然未遵循让权等待的原则。
  • 三、进程互斥的硬件实现方式
    • 1.中断屏蔽方法
    • 2.TestAndSet指令(TS指令)、TestAndSetLock指令(TSL指令)
    • 3.Swap指令、Exchange指令(XCHG指令)
  • 五、信号量机制
    • 整型信号量
      • 用一个整数型的变量作为信号量,用来表示系统中某种资源的数量。
      • 存在的问题:不满足“让权等待”原则,会发生“忙等”
    • 记录型信号量
  • 六、信号量机制实现进程互斥、同步、前驱
    • 信号量机制实现进程互斥
    • 信号量机制实现进程同步
    • 信号量机制实现前驱关系
  • 七、管程:一种高级同步机制
    • 各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据
    • 每次仅允许一个进程在管程内执行某个内部过程
  • 八、死锁
    • 预防死锁
    • 避免死锁
    • 死锁的检测和解除
  • 这一篇里边接触了很多崭新的概念:进程互斥、信号量、PV操作、管程、死锁

一、进程同步

进程具有异步性的特征。

异步性是指,各并发执行的进程以各自独立的、不可预知的速度向前推进。

同步亦称直接制约关系。

它是指为完成某种任务而建立的两个或多个进程,这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。
进程间的直接制约关系就是源于它们之间的相互合作

二、进程互斥

互斥亦称间接制约关系。

进程之间没有关系,只是要访问同一个资源。
在这里插入图片描述
在这里插入图片描述

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

1.空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区;

2.忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待;

3.有限等待。对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿)

4.让权等待。当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。

三、进程互斥的软件实现方式

1.单标志法

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

该算法可以实现“同一时刻最多只允许一个进程访问临界区”。

主要问题:违背“空闲让进”原则。

2.双标志先检查法

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

主要问题:违反“忙则等待”原则。

3.双标志后检查法

算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”,但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到先“上锁”后“检查”的方法,来避免上述问题。

解决了“忙则等待”的问题

主要问题:违背了“空闲让进”和“有限等待”原则

会因各进程都长期无法访问临界资源而产生“饥饿”现象。

4.Peterson算法

Peterson算法用软件方法解决了进程互斥问题,遵循了空闲让进、忙则等待、有限等待三个原则

但是依然未遵循让权等待的原则。

在这里插入图片描述

三、进程互斥的硬件实现方式

1.中断屏蔽方法

利用“开/关中断指令”实现(与原语的实现思想相同,即在某进程开始访问临界区到结束访问为止都不允许被中断,也就不能发生进程切换,因此也不可能发生两个同时访问临界区的情况)
关中断后即不允许当前进程被中断,也必然不会发生进程切换,直到当前进程访问完临界区,再执行开中断指令,才有可能有别的进程上处理机并访问临界区。

关中断;
临界区;
开中断;

优点:简单、高效
缺点:不适用于多处理机;只适用于操作系统内核进程,不适用于用户进程(因为开/关中断指令只能运行在内核态,这组指令如果能让用户随意使用会很危险)

2.TestAndSet指令(TS指令)、TestAndSetLock指令(TSL指令)

TSL指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。
在这里插入图片描述

若刚开始lock是 false,则TSL返回的old值为 false,while循环条件不满足,直接跳过循环,进入临界区。若刚开始lock是 true,则执行TLS后old返回的值为true,while循环条件满足,会一直循环,直到当前访问临界区的进程在退出区进行“解锁”。
相比软件实现方法,TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点:实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境
缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。

3.Swap指令、Exchange指令(XCHG指令)

逻辑上来看Swap和TSL并无太大区别,都是先记录下此时临界区是否已经被上锁(记录在old变量上),再将上锁标记lock设置为true,最后检查old,如果old为 false则说明之前没有别的进程对临界区上锁,则可跳出循环,进入临界区。
优点:实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境
缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用cPU并循环执行TSL指令,从而导致“忙等”。
在这里插入图片描述

五、信号量机制

复习回顾+思考:之前学习的这些进程互斥的解决方案分别存在哪些问题?
进程互斥的四种软件实现方式(单标志法、双标志先检查、双标志后检查、Peterson算法)进程互斥的三种硬件实现方式(中断屏蔽方法、TS/TSL指令、Swap/XCHG指令)
1.在双标志先检查法中,进入区的“检查”、“上锁”操作无法一气呵成,从而导致了两个进程有可能同时进入临界区的问题;
2.所有的解决方案都无法实现“让权等待”
1965年,荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制
在这里插入图片描述

整型信号量

在这里插入图片描述

用一个整数型的变量作为信号量,用来表示系统中某种资源的数量。

与普通整数变量的区别:对信号量的操作只有三种,即初始化、P操作、v操作
“检查”和“上锁”一气呵成,避免了并发、异步导致的问题

存在的问题:不满足“让权等待”原则,会发生“忙等”

记录型信号量

整型信号量的缺陷是存在“忙等”问题,因此人们又提出了“记录型信号量”,即用记录型数据结构表示的信号量。
在这里插入图片描述
在这里插入图片描述

六、信号量机制实现进程互斥、同步、前驱

信号量机制实现进程互斥

注意:对不同的临界资源需要设置不同的互斥信号量。
P、V操作要成对出现。
在这里插入图片描述

信号量机制实现进程同步

在这里插入图片描述

信号量机制实现前驱关系

在这里插入图片描述
在这里插入图片描述

信号量机制存在的问题:编写程序困难、易出错

七、管程:一种高级同步机制

各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据

每次仅允许一个进程在管程内执行某个内部过程

水水水水水

八、死锁

在这里插入图片描述

预防死锁

在这里插入图片描述

避免死锁

在这里插入图片描述

死锁的检测和解除

在这里插入图片描述
————————————————————————————————————————————————————————————

这一篇里边接触了很多崭新的概念:进程互斥、信号量、PV操作、管程、死锁

多进程并发执行,各自以不可预知的速度向前推进,即具有异步性,但因为在某些情况下,我们需要它们有序执行,有了先后顺序,即进程间有了直接制约关系。这种直接制约关系就是进程同步

前面已经知道,系统中的某些资源,一个时间段内只允许一个进程访问,即互斥地进行访问,这些资源称为临界资源。
需要访问同一个临界资源的进程中,除一个正在访问的进程,其他进程都要等待,这种间接制约关系就是进程互斥

对临界资源的互斥访问,在逻辑上分为四个部分:进入区、临界区、退出区、剩余区

公共厕所是个很经典的临界资源:
进入区:判断是否有人,无人就进入并上锁
临界区:使用临界资源
退出区:解锁并离开
剩余区:做其他处理,如洗手
注意:进入区和退出区负责实现互斥的代码段

为了实现对临界资源的互斥访问,同时保证系统整体性能,需要遵循以下原则:
1.空闲让进。厕所没人,只要来人就让他进
2.忙则等待。厕所有人,谁来都得让他等
3.有限等待。不能让等的人拉裤子吧,所以要想办法保证在有限时间内能让他们上到厕所
4.让权等待。当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。

进程互斥的软件实现方式:
1.单标志法:先随便指定第一个人,只有等第一个人用完,他再指定下一个人,然后这个人使用完再指定下下个人。。。
所以如果某个人现在不想使用,他后面的所有人都要一直等待
违背了空闲让进原则。

2.双标志先检查法:有一个上厕所意愿表,某人想上厕所的时候,先看看表上有人正在上没,没有的话就写上自己的名字,然后上厕所
可惜这个表是网上签字的(进程异步,互相独立,不知道对方的行为),所以会有两个人“同时”想上厕所,它们“同时”看表上没人,“同时”签字,“同时”上厕所。。。
(这个同时是几乎同时,由进程切换带来的后果)
违反“忙则等待”原则。

3.双标志后检查法:还是有一个上厕所意愿表,但是不是先看有人上没再签字,而是先把自己的名字写上,再看有没有人上
这样两个人都先写名字后,检查发现有人上,这俩都上不了。。。
解决了“忙则等待”的问题,违背了“空闲让进”和“有限等待”原则

4.Peterson算法:谁先让谁先上
在 双标志后检查法 的基础上,两人发现对方想上的时候,
其中一个立马说,:“你先上吧”,
对方也谦让,说,:“你先上吧”,
“行,我先上”,
于是两个人都能上厕所了。
但是在这种软件实现方式下,等待的那个人是在“忙等”
违背了“让权等待”原则。

进程互斥的硬件实现方式:

1.中断屏蔽方法
关中断后即不允许当前进程被中断,也必然不会发生进程切换,直到当前进程访问完临界区,再执行开中断指令,才有可能有别的进程上处理机并访问临界区。
优点:简单、高效
缺点:不适用于多处理机;只适用于操作系统内核进程,不适用于用户进程(因为开/关中断指令只能运行在内核态,这组指令如果能让用户随意使用会很危险)

2.TestAndSet指令(TS指令)、TestAndSetLock指令(TSL指令)
TSL指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。
这个和平常上厕所一模一样,你要上厕所就会来到厕所门口,如果没人你就上,如果有人,你就站在门口等,他上完了你就上。
不管你这里面上还是在门口等,都是为了不让后面的人比你先上,所以相当于“上锁”
厕所没人,你上厕所并“上锁”
厕所有人,你在外面等并“上锁”

相比软件实现方法,TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点:实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境
缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。

3.Swap指令、Exchange指令(XCHG指令)
逻辑上来看Swap和TSL并无太大区别
在这里插入图片描述

信号量机制
信号量S是一个整数,表示系统中某种资源的数量
S大于等于零是代表可供并发进程使用的资源实体数,当S小于零时则表示正在等待使用临界区的进程数。
Dijkstra同时提出了对信号量操作的PV原语:
P原语 - wait(S):
V原语 - signal(S):

P原语操作的动作是:
(1)S减1;
(2)若S减1后仍大于或等于零,则进程继续执行;
(3)若S减1后小于零,则该进程被阻塞后进入与该信号相对应的队列中,然后转进程调度。
V原语操作的动作是:
(1)S加1;
(2)若相加结果大于零,则进程继续执行;
(3)若相加结果小于或等于零,则从该信号的等待队列中唤醒一等待进程,然后再返回原进程继续执行或转进程调度。
PV操作对于每一个进程来说,都只能进行一次,而且必须成对使用。
在PV原语执行期间不允许有中断的发生。

整型信号量:用一个整数型的变量作为信号量,用来表示系统中某种资源的数量。
与普通整数变量的区别:对信号量的操作只有三种,即初始化、P操作、v操作
“检查”和“上锁”一气呵成,避免了并发、异步导致的问题
存在的问题:不满足“让权等待”原则,会发生“忙等”

记录型信号量:
整型信号量的缺陷是存在“忙等”问题,因此人们又提出了“记录型信号量”,即用记录型数据结构表示的信号量。
在这里插入图片描述

通过这个等待队列,通过自我阻塞block原语,可以把等待的进程都挂在等待队列上,实现让权等待

信号量机制实现进程互斥

进程互斥是同一时间段,只能有一个进程访问临界资源
设置互斥信号量,mutex=1——有一个资源
P(mutex)——使用资源
临界区
V(mutex)——补充资源
这样在P操作后,mutex=0,其他进程就无法访问,只有在V操作之后,其他进程才可访问

信号量机制实现进程同步

进程同步是进程间有先后关系,即A操作发生后,才能发生B操作
设置同步信号量,S=0——没有资源

P(S)——使用资源,因为最开始没有资源,所以一直在等待,只有补充了资源后,才能B操作
B操作

A操作
V(S)——补充资源,只有在A操作之后,才补充了资源

信号量机制实现前驱关系

就是多对 进程同步 问题

管程:一种高级同步机制

管程到底是个什么东西,我还不是很清楚
和类(C++ 类 & 对象)差不多,大概就是下面这个东西,学过c++的同学可以看一下我写的对不对,我c++学的不太好

class monitor		//类
{
private:	//私有成员condition full,empty;int count=0;
public: 	//公用方法void insert(Item item){...}Item remove(){...}
}int main()
{monitor ProducerConsumer;	//实例化对象ProducerConsumer.inster(item);	//使用点运算符可以访问类对象的公共成员。item = ProducerConsumer.remove();//调用类的方法
}

在这里插入图片描述

感觉有好多都是操作系统特有的性质,因为它有这个性质,所以才能实现这样的功能
唉不懂不懂

死锁
各进程互相等待对方手里的资源,导致各进程都阻塞,无法向前推进。
死锁还挺好理解的,

死锁!=饥饿,但是死锁一定会导致饥饿(在死锁里的所有进程)
死锁进程至少有两个,且处于阻塞态
饥饿进程可能处于阻塞态或就绪态
死循环的进程可以是运行态

死锁产生的必要条件:我拿着一种宝贝不放,我还要别人的另一样宝贝,他不给,我就一直等
1.互斥条件:进程要抢夺临界资源,宝贝是唯一的
2.不剥夺条件:宝贝不能抢,只能自己主动放手
3.请求和保持条件:我拿着一种宝贝不放,我还要别人的另一样宝贝
4.循环等待条件:他不给,我就一直等

死锁的处理策略

预防死锁:通过破坏必要条件
1.破坏互斥条件:将临界资源改造为可共享使用的资源(如SPOOLing技术)
缺点:可行性不高,很多时候无法破坏互斥条件
在这里插入图片描述

2.破坏不剥夺条件:
方案一,申请的资源得不到满足时,立即释放拥有的所有资源
方案二,申请的资源被其他进程占用时,由操作系统协助剥夺(考虑优先级)
缺点:实现复杂;剥夺资源可能导致部分工作失效;反复申请和释放导致系统开销大;可能导致饥饿

3.破坏请求和保持条件:运行前分配好所有需要的资源,之后一直保持
缺点:资源利用率低;可能导致饥饿

4.破坏循环等待条件:给资源编号,必须按编号从小到大的顺序申请资源
缺点:不方便增加新设备;会导致资源浪费;用户编程麻烦

避免死锁:通过预先推算安全序列的方式,避免系统进入不安全状态
安全序列:如果系统按照这种序列分配资源,则每个进程都能顺利完成。
只要能找出一个安全序列,系统就是安全状态
反之为,不安全状态,就可能发生死锁

某一份资源,要分给几个进程,要保证 每次分完之后的资源 至少能满足某一进程(满足该进程之后,该进程就会释放资源)

银行家算法”的核心思想:在资源分配之前预先判断这次分配是否会导致系统进入不安全状态,以此决定是否答应资源分配请求。

死锁的检测和解除

在这里插入图片描述
资源分配图感觉只是某一时刻的资源分配:这个图里R1为P2提供了一个资源,但是P2又向R1申请了一个资源

可完全简化的:将既不阻塞又不是孤点的进程Pi的所有边去掉,直到不存在这样的进程。
若能消除所有边,此时一定没有发生死锁。
在这里插入图片描述
如果最终不能消除所有边,那么此时就是发生了死锁
最终还连着边的那些进程就是处于死锁状态的进程

在这里插入图片描述
死锁定理:如果某时刻系统的资源分配图是不可完全简化的,那么此时系统死锁。

解除死锁的主要方法有:
1.资源剥夺法。挂起(暂时放到外存上)某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2.撤销进程法(或称终止进程法)。强制撤销部分、甚至全部死锁进程,并剥夺这些进程的资源。这种方式的优点是实现简单,但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间,己经接近结束了,一旦被终止可谓功亏一篑,以后还得从头再来。
3.进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息,设置还原点。
在这里插入图片描述

这篇关于五天自学完 王道考研-操作系统 第二章 进程同步、进程互斥、实现、信号量、管程、死锁的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/849512

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注,收藏不迷路💖 Kubernetes的PodSecurityPolicy(PSP)是一个关键的安全特性,它在Pod创建之前实施安全策略,确保P

工厂ERP管理系统实现源码(JAVA)

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本,并实时掌握各环节的运营状况。 在采购管理方面,系统能够处理采购订单、供应商管理和采购入库等流程,确保采购过程的透明和高效。仓库管理方面,实现库存的精准管理,包括入库、出库、盘点等操作,确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

[Linux]:进程(下)

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯,先赞后看哦~🎈🎈 所属专栏:Linux学习 贝蒂的主页:Betty’s blog 1. 进程终止 1.1 进程退出的场景 进程退出只有以下三种情况: 代码运行完毕,结果正确。代码运行完毕,结果不正确。代码异常终止(进程崩溃)。 1.2 进程退出码 在编程中,我们通常认为main函数是代码的入口,但实际上它只是用户级