游戏直播网站怎么做的,重庆seo推广渠道,网站成立时间,公司做网站比较好的平台学习日期#xff1a;2024.7.8
内容摘要#xff1a;进程同步/互斥的概念和意义#xff0c;基于软/硬件的实现方法 进程同步与互斥的概念和意义
为什么要有进程同步机制#xff1f;
回顾#xff1a;在《进程管理》第一章中#xff0c;我们学习了进程具有异步性的特征2024.7.8
内容摘要进程同步/互斥的概念和意义基于软/硬件的实现方法 进程同步与互斥的概念和意义
为什么要有进程同步机制
回顾在《进程管理》第一章中我们学习了进程具有异步性的特征即各个并发执行的进程以各自独立、不可预知的速度向前推进。
但是有的情况下我们希望某几个特定的进程按一定的顺序执行。比如说在进程通信——管道通信的时候读进程和写进程是并发运行的但是我们当然是希望是写数据的进程先传输信息然后读数据的进程再接收。
所以为了解决进程的异步性和我们对进程有序执行的需求的矛盾操作系统需要提供进程同步机制。
什么是进程同步
同步又称直接制约关系它是指为了完成某种任务而建立的两个或多个进程因为需要在某些位置上协调他们的工作次序而产生的制约关系。进程间的同步就是源于它们之间的相互合作。
为什么要有进程互斥机制
进程的“并发”需要“共享”的支持各个并发执行的进程不可避免的需要共享一些系统资源比如说内存或打印机、摄像头这样的I/O设备而不是所有的系统资源都有足够的量或者能同时分配给多个进程共享的为了解决系统资源的有限性和多个进程对同一资源的需求的矛盾需要提供进程互斥机制。
我们把一个时间段内只允许一个进程使用的资源称为临界资源很多I/O设备打印机、摄像头都属于临界资源此外还有许多变量、数据、内存缓冲区等都属于临界资源对临界资源的访问必须互斥进行。
什么是进程互斥
互斥又称间接制约关系它是指当一个进程访问某个临界资源时其它想访问该临界资源的进程必须等待直到该进程的访问结束释放该资源以后另一个进程才能访问。
进程互斥的逻辑分区 临界区是进程中访问临界资源的代码段进入区和退出区是负责实现互斥的代码段
进程互斥的四大原则
为了实现对对临界资源的互斥访问同时保证系统整体性能需要满足
1.空闲让进。临界区空闲时允许一个请求进入临界区的进程立即进入。
2.忙则等待。当已有进程进入临界区时其它试图进入的进程必须等待。
3.有限等待。对请求访问的进程应保证其能在有限时间内进入临界区不会饥饿。
4.让权等待。当进程不能进入临界区时立即释放处理机避免进程占用处理机的同时等待忙等待。 进程互斥的软件实现方法
单标志法
算法思想两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程也就是说每个进程进入临界区的权限只能被另一个进程赋予。 如图turn的初始值为0即刚开始只允许0号进程进入临界区。
若P1先上则会一直卡在⑤直到P1的时间片用完切换回P0直到P0正常访问完临界资源退出时将turn改为1P1才能进入临界区。
两个进程互相“谦让”轮流使用临界资源。每次使用前先检查是否轮到自己使用如果没轮到就等待如果轮到就使用然后在使用完之后把使用权让出。
缺点进程必须轮流访问临界区但如果此时允许进入临界区的进程是P0P0却一直不访问临界区就会导致在临界区资源空闲的前提下P1一直不能访问临界区。这违背了“空闲让进”原则。
双标志先检查法
算法思想设置一个布尔型数组flag[],数组中的各个元素用来标记各个进程想进入临界区的意愿。比如flag[0]true表示0号进程现在想进入临界区每个进程在进入临界区之前先检查有没有别的进程想进入临界区如果没有则把自身对应的标志flag[i]设为true之后开始访问临界区。 好比两个人互斥的使用公共厕所这个确实不太能共享进去之前先看一下厕所是不是显示“有人”检查其它进程意愿如果没人就打开门进去挂上“有人”的牌子标记为本进程想进入临界区最后在上完厕所之后再把牌子取下来。访问完之后修改标记
缺点P0和P1在某些情况下可能同时访问临界区违背了“忙则等待”原则。
因为进入区的“检查”和“上锁”两个步骤不是一气呵成的。生活中我们可以看到旁边有人也想上厕所但是进程不行。进程在“检查”后看到门口没有牌子就打开了厕所门但此时是可能发生进程切换的若进程A检查完还没有挂上牌子时切换到了进程B进程B此时发现厕所门没有牌子就打开进去上厕所了但一段时间之后进程A又切换回来因为之前已经检查过了所以进程A不会看牌子会直接打开厕所门导致A和B同时使用一个厕所没能互斥。即上述代码顺序为①⑤②⑥...时会导致P0和P1同时访问临界区。
双标志后检查法
算法思想双标志先检查法的改版。前一个算法的问题是先“检查”后“标记”但是这两个操作无法一气呵成导致两个进程同时进入临界区的问题因此该方法是先“标记”后“检查”。 与上一方法对比来看就是交换了检查和标记的位置。
还是以上厕所来举例此方法就是在进入厕所前先不看有没有牌子只要自己想上就先挂一个“有人”的牌子然后再检查有没有别人的牌子如果没有就直接进去如果有就等待别人的牌子被取下。
缺点与前一个算法有类似的问题因为标记和检查的过程不连贯当上述代码顺序为①⑤②⑥...时会出现明明临界区空闲但P0和P1都无法访问临界区的情况违背了“空闲让进”和“有限等待”原则会导致进程饥饿。
进程A首先给厕所门挂上了牌子但是此时发生了进程切换换到进程B进程B也会直接挂上牌子然后又切换回了进程A此时进程A执行检查步骤发现门上有进程B的牌子会开始等待。当进程A的时间片用完后切到进程BB发现门上有进程A的牌子也不敢进去这样其实厕所里根本没人但是AB双方都误以为有人会无限的等待下去导致进程饥饿憋死了。
Peterson算法重难点
算法思想结合双标志法、单标志法的思想同时设置布尔数组flag[]和整型变量turn。如果双方都想进入临界区那么可以让进程互相谦让。 进程首先表达意愿然后把turn设为对方的编号表示谦让注意理解此处while判断的含义while通过的意思是被循环卡住了循环等待检查是否是对方想进且自己表达了最后一次的“谦让”
很绕我们结合例子来理解
进程P0首先声明自己想上厕所挂上牌子然后表示我愿意谦让给对方先上更新turn值然后判断是否厕所门上有对方的牌子且最后是自己表达了谦让如果都满足就等待对方结束否则开始上厕所。
谁在最后谦让了修改turn值了说“客气话”了谁就会失去行动的优先权。
P0说“你也想上厕所那你先请吧”但是P1说“不了不了还是你先。”然后P0就会去上厕所
因为P1已经说了你先请turn0P1就“不好意思”在P0谦让之前上厕所对P0也是同理。 当执行顺序为①⑥②⑦时首先进程P0挂上牌子切到P1挂上牌子然后P0谦让turn1切到P1谦让turn0。
此时若切回P0下一步是③则门上有P1的牌子但是turn0对于P0来说上一次谦让的不是自己上一步不是②所以P0不会等待直接开始使用。
若P1谦让后继续执行下一步是⑧则门上有P0的牌子且turn0对于P1来说上一次谦让的是自己⑦和⑧连续执行所以要等待直到切换回P0P0会直接开始使用。 当执行顺序为①⑥②时首先进程挂上P0牌子切到P1挂上牌子然后P0谦让turn1。 若下一步是⑦则同上若下一步是③此时门上有P1的牌子且turn1对于P0来说上一次谦让的是自己②和③连续执行所以要等待直到切换回P1P1会直接开始使用。
同理当执行顺序是①⑥⑦时和①⑥②没有区别只相当于对换了P0和P1进程而已。
至此我们已经列举了前两步是①⑥的所有情况都不会产生问题所以Peterson算法不会因为检查和标记的不连贯产生问题。
缺点Peterson算法用软件方法解决了进程互斥问题遵循了空闲让进、忙则等待、有限等待三个原则但是没有遵循让权等待的原则会发生“忙等”。进程缺乏临界资源却占用处理机等待
其相较于之前介绍的三种软件解决方案来说是最好的但是依然不够好。 进程互斥的硬件实现方法
前面介绍的方法中很多问题都是由于标记和检查的过程不连贯不能一气呵成导致的这让我们想到之前在《进程控制》章节中学习过的“原语”如果可以用某种方法一气呵成中间不发生进程切换不就解决问题了吗
中断屏蔽方法
利用“开/关中断指令实现”与原语的实现思想相同即在某进程开始访问临界区到结束为止都不允许被中断也就不能发生进程切换
优点简单高效。
缺点不适用于多处理机因为如果是多核处理机处理机A和处理机B上的进程可能同时访问同一个临界资源且都不能被中断。
而且开/关中断指令的权限非常高只适用于内核进程不适用于用户进程应用范围不够广泛。
TestAndSet指令
简称TS指令或TSL指令L代表LockTSL指令是用硬件实现的执行的过程不允许被中断只能一气呵成。
以下是C语言描述的逻辑演示 若刚开始lock是false未上锁则TestAndSet指令返回的old值为flasewhile循环条件不满足不会卡住会跳过循环进入临界区
若刚开始是true则TS指令返回的old值也是truewhile循环条件满足循环等待直到当前访问临界区的进程更新lock值“解锁”。
TS指令中每次都设成true是因为每次TS指令运行都是有程序想访问临界区要上锁。
实际上TS指令不是真的return一个值而是把这个值存到某个物理寄存器里面是用汇编语言执行的。
优点实现简单无需像软件实现方法那样严格检查逻辑漏洞且适用于多处理机环境。
缺点不满足“让权等待”原则暂时无法进入临界区的进程依然会占用CPU并且循环等待即“忙等”。
Swap指令
又称Exchange指令或者XCHG指令Exchange什么天才简称Swap指令是用硬件实现的执行的过程同样不允许被中断只能一气呵成。
逻辑描述如下 其实和TSL在逻辑上是相同的先给old赋值为true然后交换lock和old的值事实上就是给lock赋值true上锁然后判断old的值是不是true如果是说明之前就是上锁的则循环等待直到解锁如果不是则跳出循环开始运行。
优缺点同TS指令一样实现简单、适用于多处理机环境但不满足让权等待原则会导致忙等。
补充互斥锁
互斥锁是解决临界区的简单工具可以理解为一个布尔型的变量通常用硬件操作实现。
以上方法除中断屏蔽法都依赖于内部的一个while循环语句来实现互斥这是最简单的互斥锁这种需要连续循环忙等的锁叫自旋锁spin lock顾名思义就是在自己循环转圈其最大缺点就是忙等待。
使用这种方法进程在时间片用完后才会下处理机会违反“让权等待”原则但优点是等待期间不用切换进程上下文常用于多处理器系统一个核忙等另外的核正常工作并快速释放临界资源不必频繁切换进程。但不太适用于单处理机系统忙等的过程不可能解锁白白浪费时间和CPU资源。 内容总结自王道计算机考研《操作系统》 和 人民邮电出版社《操作系统导论》
