1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

2.该文档所得收入(下载+内容+预览三)归上传者、原创者。

3.登录后可充值，立即自动返金币，充值渠道很便利

操作系统级别概念讲义-进程同步与互斥.doc

操作系统级别概念讲义进程同步与互斥第章进程同步与互斥并发concurrency是多道程序技术多处理技术分布式处理技术的基础也是OS设计的重点资源的共享和争用多个进程活动的同步分配给进程的处理器时间等并发的原理,控制对共享资源的访问不加控制地访问共享资源会出现问题要求控制对共享资源的访问进程间的制约关系进程的同步直接制约synchronism指系统中一些进程需要相互合作共同完成一项任务具体说一个进程运行到某一点时要求另一伙伴进程为它提供消息在未获得消息之前该进程处于等待状态获得消息后被唤醒进入就绪态进程的互斥间接制约mutualexclusion由于各进程要求共享资源而有些资源需要互斥使用因此各进程间竞争使用这些资源进程的这种关系为进程的互斥进程间的制约关系相关概念互斥指多个进程不能同时使用同一个资源死锁指多个进程互不相让都得不到足够的资源饥饿指一个进程一直得不到资源其他进程可能轮流占用资源临界资源系统中某些资源一次只允许一个进程使用称这样的资源为临界资源或互斥资源或共享变量临界区进程中访问临界资源的一段代码同步问题例子谁买面包甲查看冰箱面包没了去超市到达超市买好面包回家把面包放入冰箱乙查看冰箱面包没了去超市到达超市买好面包回家把面包放入冰箱噢TooMuch临界区问题,原语内核在执行某些基本操作时往往利用原语操作实现原语是一种广义指令相当于扩充了机器指令集原语是由若干条指令构成用于完成一定功能的一个过程原语是原子操作atomicoperation原子操作一个操作中的所有动作要么全做要么全不做原子操作是一个不可分割的操作临界区问题,互斥的要求使用临界区应遵循的准则有空让进当无进程在临界区时任何有权使用临界区的进程可进入无空等待不允许两个以上的进程同时进入临界区多中择一当没有进程在临界区而同时有多个进程要求进入临界区只能让其中之一进入临界区其他进程必须等待有限等待任何进入临界区的要求应在有限的时间内得到满足让权等待处于等待状态的进程应放弃占用CPU平等竞争任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定实现互斥的方法实现互斥的方法软件方法硬件方式利用专门机器指令com实现互斥的方法软件的方法自学特点无需硬件OS和程序设计语言的支持处理开销大容易出错学习的意义更好地理解并发处理的复杂性适用范围单处理器系统共享主存的多处理系统前提假设存储器级的访问是互斥的com软件的方法,Dekker算法Dijkstra报告了Dekker荷兰数学家设计的算法尝试单标志Dekker算法,尝试Dekker算法,尝试双标志先检查优点不用交替进入可连续使用缺点不能保证互斥Pi和Pj可能同时进入临界区在Pi和Pj都不在临界区时假设按下面序列执行时会同时进入PiPjPiPj即在检查对方flag之后和切换自己flag之前有一段时间结果都检查通过这里的问题出在检查和修改操作不能连续进行一个进程在临界区内失败另一进程永远被阻塞Dekker算法,尝试双标志后检查Dekker算法,尝试双标志后检查优点类似于算法与算法的区别在于先修改后检查可防止两个进程同时进入临界区实现互斥缺点Pi和Pj可能都进入不了临界区在Pi和Pj都不在临界区时假设按下面序列执行则都进不了临界区PiPjPiPj即在切换自己的flag之后和检查对方flag之前有一段时间结果都切换flag都检查不通过Dekker算法,尝试思路使每个进程更礼让一些每个进程设置自己的flag表明自己想进入自己的临界区但也准备重置flag以尊重另一个进程优点保证互斥缺点出现活锁一组进程都想进入它们的临界区但没有一个能成功进入不是死锁因为两个进程相对速度的任何改变都会打破这种情形可能成功进入也可能有使得任何进程都不能进入临界区的执行顺序一种正确的方案避免无原则的礼让规定在都想进入时的进入顺序comPeterson算法先修改后检查后修改者等待Flag表示每个进程关于互斥的位置turn解决同时进入时的冲突问题turnj描述可进入的进程同时修改标志时在进入区先修改后检查并检查并发修改的先后检查对方flag如果不在临界区则自己进入,,空闲则入否则再检查turn保存的是较晚的一次赋值则较晚的进程等待较早的进程进入,,先到先入后到等待com互斥的实现,硬件方法中断禁用关中断InterruptDisabling单处理器系统并发进程交替执行而不重叠一个进程一直运行直到调用了一个OS服务或被中断如果进程访问临界资源时执行临界区代码不被中断就可以利用它来保证互斥地访问途径使用关中断原语开中断原语中断禁用关中断过程关中断原语临界区开中断原语其余部分存在问题代价高限制了处理器交替执行各进程的能力不能用于多处理器结构关中断不能保证互斥com互斥的实现,硬件方法专门的机器指令设计一些机器指令用于保证两个动作的原子性如在一个指令周期中实现测试和修改TestandSetTS指令Swap指令专门的机器指令Test和Set指令TS指令TS指令定义逻辑BooleanTestandSetintiifiireturntrueelsereturnfalse专门的机器指令SwapSwap指令定义voidSwapintaintbinttempaabbtempcom专门的机器指令,评价优点适用于单处理器或共享主存的多处理器系统进程数目任意简单且易于证明可以使用多个变量支持多个临界区只需为每个临界区设立一个布尔变量缺点忙等待当一个进程正在等待进入一个临界区时继续消耗处理器时间可能饿死任意选择等待的进程有的可能一直选不上可能死锁高优先级进程等待处于阻塞状态的低优先级进程的资源如进程P执行TS或Swap指令并进入临界区然后P被阻塞并把CPU给具有更高优先级的P若P试图使用与P相同的资源由于互斥机制它被拒绝访问因此进入忙等待循环又因P优先级高于P所以P总得不到调度执行P也无法执行信号量信号量机制OS可从进程管理者的角度来处理互斥的问题信号量就是OS提供的管理公有资源的有效手段是解决并发进程问题的第一个重要进展Dijkstra信号量定义与声明信号量定义semaphore是一个数据结构定义如下structsemaphoreintegercountPointerPCBqueue信号量声明Semaphores信号量,信号量的物理意义信号量s的count值含义初始化指定一个非负整数值表示空闲资源总数又称为资源信号量若为非负值表示当前的空闲资源数scount可用的资源数若为负值其绝对值表示当前等待临界区的进程数scount为等待的进程数每个信号量s除一个整数值scount计数外还有一个进程等待队列squeue其中是阻塞在该信号量的各个进程的标识信号量,waitsignal原语的定义信号量,PV原语的定义信号量,对信号量操作的物理意义操作系统对信号量只能通过初始化和两个标准的原语来访问对信号量的操作只有三种原子操作初始化通常将信号量的值初始化为非负整数P操作wait操作使信号量的值减申请一个单位的资源scount如果使信号量的值变成负数则执行P操作的进程被阻塞当scount时资源已分配完毕进程自己阻塞在S的队列上让权等待V操作signal操作使信号量的值加释放一个单位资源scount如果信号量的值不是正数则使一个因执行v操作被阻塞的进程解除阻塞若scount则唤醒一个等待进程用信号量实现互斥在互斥问题中对信号量mutex必须设置一次初值初值必须为PV原语操作应该分别紧靠临界区的头部和尾部从而提高进程的并发度Mutex的取值为nPV操作必须成对出现而且它们同处于同一个进程中互斥例过河问题某条河上只有一个独木桥以便行人过河现在河的两边都有人要过桥若把过桥者看做一个进程规定每次只有一个人通过为了保证过桥安全请用PV操作分别实现正确的管理互斥例对共享变量的访问观察者和报告者是两个并发执行的进程观察者不断观察并对通过的卡车计数报告者定时地将观察者的计数随时打印请用PV原语进行正确描述SemaphoremutexCountProcessobserverBeginrepeat观察到一辆车PmutexcountcountVmutexUntilfalseEnd利用信号量实现进程同步例进程Pc和Pp合作完成计算和打印任务设信号量bufempty表示buf空bufemptybuffull表示buf满buffullPpBPbuffull取出buf中的数据置空标记打印VbufemptyGotoB经典同步问题生产者消费者问题读写者问题哲学家问题分析P操作的顺序很重要P操作的顺序不当会产生死锁例假定执行顺序如下生产者消费者问题的有限循环缓冲区例与进程的执行顺序有关的问题有个进程PAPB和PC合作解决文件打印问题PA将文件记录从磁盘读入主存的缓冲区每执行一次读一个记录PB将缓冲区的内容复制到缓冲区每执行一次复制一个记录PC将缓冲区的内容打印出来每执行一次打印一个记录缓冲区的大小等于一个记录大小要求请用PV操作来保证文件的正确打印设置个信号量emptyemptyfullfullempty及empty分别表示缓冲区及缓冲区是否为空初值为fullfull分别表示缓冲区及缓冲区是否有记录可供处理其初值为例题PAWhile从磁盘读一个记录Pempty将记录存入缓冲区VfullPBWhilePfull从缓冲区中取出记录vemptyPempty将记录存入缓冲区VfullPCWhilePfull从缓冲区取一个记录Vempty打印记录IntemptyemptyfullfullMainCobeginPAPBPCCoend例读写问题问题描述有一个许多进程共享的数据区有一些只读取这个数据区的进程reader和一些只往数据区中写数据的进程writer此外还必须满足下列条件任意多的读进程可以同时读这个数据区一次只有一个写进程可以往数据区写如果一个写进程正在往数据区中写禁止任何读进程读数据区要求读,写互斥写,写互斥读,读允许读写问题读进程具有优先权例哲学家进餐问题thediningphilosophersproblem问题描述由Dijkstra首先提出并解决个哲学家围绕一张圆桌而坐桌子上放着支筷子每两个哲学家之间放一支哲学家的动作包括思考和进餐进餐时需要同时拿起他左边和右边的两支筷子思考时则同时将两支筷子放回原处问题如何保证哲学家们的动作有序进行如不出现相邻者同时要求进餐不出现有人永远拿不到筷子哲学家的生活规律Repeat思考取forki取forkimod进食放forki放forkimodUntilfalse为防止死锁发生可采取的措施最多允许个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时才允许他拿筷子给所有哲学家编号奇数号的哲学家必须首先拿左边的筷子偶数号的哲学家则反之为了避免死锁把哲学家分为三种状态思考饥饿进食并且一次拿到两只筷子否则不拿ProgramdiningphilosophersSemaphoreforkSemaphoreroomintiVoidphilospherintiwhiletruethinkingProomPforkiPforkimodeatingVforkiVforkimodVroom作业用PV原语实现东西向单行道上车辆的正确行驶当有车自东向西方向或自西向东方向行驶另一方向上的车辆须等待同一方向上的车可以连续通过当某一方向上已经没有车辆在单行道上行驶时另一方向上的车辆即可以进入单行道请完善这个程序可参考读写者问题作业beginmutexwesteasteastwestsemaphoremutexwesteasteastwesteastcountwestcountintegereastcountwestcountCobegineastwestwesteastCoend作业Processeastwestbegineastcounteastcountifeastcountthen通过单行道eastcounteastcountifeastcountthenVeastwestEnd作业表示申请一个资源表示没有空闲资源调用进程进入等待队列squeue阻塞调用进程表示释放一个资源表示有进程处于阻塞状态从等待队列squeue中取出一个进程P进程P进入就绪队列structsemaphoreintegercountPointerPCBqueuevoidPsemaphoresscount申请一个资源Ifscount没有空闲资源Placethisprocessinsqueue进程进入等待队列squeueBlockthisprocess阻塞调用进程voidVsemaphoresscount表示释放一个资源Ifscount表示有进程处于阻塞状态removeaprocessfromsqueue从等待队列squeue中取出一个进程placethisprocessinreadylist该进程进入就绪队列用PV原语解决n个进程互斥共享一个临界资源的编程模型constintn进程数SemaphoremutexVoidProcessintiwhiletruePmutexVmutexvoidmainparbeginProcessProcessProcessn请仔细分析信号量的变化过程它是如何保证互斥的constintn进程数SemaphoremutexvoidProcessEWintiwhiletruePmutexwaitsVmutexsignalsvoidmainparbeginProcessEWProcessEWProcessEWnProcessWEProcessWEnparendProcessreporterBeginrepeatPmutexprintcountcountVmutexUntilfalseEnd缓冲区bufPcPp计算打印放入条件buf空取出结果条件buf非空PcAPbufempty计算buf计算结果VbuffullGotoA例司机P售票员PREPEATREPEAT启动关门正常运行售票到站停开门UNTILFALSEUNTILFALSE司机启动车辆的动作必须于售票员关车门的动作取得同步售票员开车门的动作也必须与司机停车取得同步设信号量S是否允许司机启动汽车初值为S是否允许售票员开门初值为DriverWhilePS启动汽车正常行车到站停车VSBusmanWhile关车门VS售票PS开车门上下乘客IntsIntsMainCobeginDriverBusmanCoend例生产者消费者问题theproducerconsumerproblem有一群生产者进程在生产消息并将消息提供给消费者进程去消费为使生产者进程和消费者进程能并发执行在它们之间设置了一个具有n个缓冲区的缓冲池生产者进程可将它所生产的消息放入一个缓冲区中消费者进程可从一个缓冲区中取得一个消息消费尽管所有的生产者进程和消费者进程都以异步方式运行但它们之间必须保持同步即不允许消费进程者到一个空缓冲区去取消息也不允许生产者进程向一个已装有消息且尚未被取走消息的缓冲区中投放消息任何时刻只能有一个进程可对共享缓冲区进行操作生产者消费者问题theproducerconsumerproblem共享缓冲区生产指针消费指针ProducerProducerProducerMConsumerConsumerConsumerN满空指针移动方向设信号量Full是满缓冲区数量初值为Empty是空缓冲区数量初值为NfullemptyNMutex用于访问缓冲区时的互斥初值是ProducerPemptyPmutex进入区oneunitbufferVmutexVfull退出区ConsumerPfullPmutex进入区oneunitbufferVmutexVempty退出区每个进程中各个P操作的次序是重要的先检查资源数目再检查是否互斥――否则可能死锁ConsumerProducerPemptyPmutexoneunitbufVmutexVfullPfullPmutex进入区oneunitbufVmutexVempty退出区分析当fullmutex时执行顺序ConsumerPmutexConsumerPfullC阻塞等待Producer发出的full信号ProducerPemptyProducerPmutexP阻塞等待Consumer发出的empty信号思考还有其他的执行序列可以产生死锁吗发生死锁消费者whiletruepfullPmutexGetproductfrombufferoutoutoutmodnVmutexVemptyconsumeitem生产者whiletrueproduceitemvPemptyPmutexSendproducttobufferinininmodNVmutexVfullNNinout使用方向供应方向缓冲区被看作一个循环缓冲区指针值必须表达为按缓冲区的大小取模emptynfull,mutex生产者消费者问题的有限循环缓冲区例图书馆问题图书馆有个座位有一张登记表要求阅读者进入时登记取得座位号出来时注销登记表同时只能由一个人使用用PV原语描述一个读者的使用过程ReaderintiEnter阅读OuterEndEnterBeginPSNPmutex登记VmutexEndOuterBeginPmutex注销VmutexVSNEnd信号量SN表示可用座位数初值为信号量mutex表示登记表是否正在使用初值为缓冲区缓冲区PA从磁盘读入PB复制PC打印Wsem用于互斥只要一个写进程正在访问共享数据区其他的写进程和读进程都不能访问它Readcount用于记录读进程的数目信号量X用于确保readcount被正确更新互斥并发的原理,,,示例共享变量的修改冲突例一飞机订票系统两个终端运行TT进程TTReadxReadxifxthenifxthenxxxxwritexwritex设x的当前值为若执行顺序为先T后T则结果x若执行顺序为TReadxTReadxTifxthenxxTifxthenxxTwritexTwritex则结果x分析产生错误的原因是不加控制地访问共享变量xCobegingetcopyputCoendgetcopyputfstg复制一个记录并发的原理,,,示例与进程的执行顺序有关的错误源记录目标记录cmpmcgpcgpg并发环境下进程间的制约关系上例的正确执行顺序司机P售票员PREPEATREPEAT启动关门正常运行售票到站停开门UNTILFALSEUNTILFALSE进程间的制约关系临界区问题进入区退出区临界区剩余区临界区criticalsection进程中访问临界资源的一段代码进入区entrysection在进入临界区之前检查可否进入临界区的一段代码如果可以进入临界区通常设置相应"正在访问临界区"标志退出区exitsection用于将"正在访问临界区"标志清除剩余区remaindersection代码中的其余部分有两个进程PiPj设立一个共享全局整型变量turn描述允许进入临界区的进程标识在进入区循环检查是否允许本进程进入turn为i时进程Pi可进入在退出区修改允许进入进程标识进程Pi退出时改turn为进程Pj的标识j优点保持了互斥的特性缺点严格轮流使用临界区限制推进速度由执行较慢的进程决定容易造成资源利用不充分在Pi出让临界区之后Pj使用临界区之前Pi不可能再次使用临界区如果一个进程失败了另一个进程将被永久阻塞忙等待busywaiting为了等待一事件的发生重复执行一段循环代码白白消耗CPU时间Dekker算法,尝试双标志先检查设立一个标志数组flag描述进程是否在临界区初值均为FALSE它是进程到达临界区的钥匙先检查后修改在进入区中检查另一个进程是否在临界区不在临界区时修改本进程在临界区的标志在退出区修改本进程在临界区的标志Dekker算法,尝试P将flag置为trueP将flag置为trueP检查flagP检查flagP将flag置为falseP将flag置为falseP将flag置为trueP将flag置为true此序列无限延伸任何一个进程都不能进入自己的临界区flagiTRUEturnjwhileflagjturnjcriticalsectionflagiFALSEremaindersectionDekker算法解决了互斥问题但比较复杂证明起来也比较困难Peterson提出一种简单的方案使用TestAndSet实现互斥constintnintboltvoidPintiWhiletrueWhileTestandSetbolt什么都不做临界区bolt剩余区voidmainboltParbeginpppn使用Swap指令实现互斥dokeywhilekeySwaplockkey临界区lock剩余区while