《操作系统概念》第六版作业解答7-8章.ppt
《《操作系统概念》第六版作业解答7-8章.ppt》由会员分享,可在线阅读,更多相关《《操作系统概念》第六版作业解答7-8章.ppt(23页珍藏版)》请在装配图网上搜索。
Chapter7进程同步 进程的同步隐含了系统中并发进程之间存在的两种相互制约关系 竞争 互斥 与协作 同步 互斥 两个并行的进程A B 如果当A进行某个操作时 B不能做这一操作 进程间的这种限制条件称为进程互斥 这是引起资源不可共享的原因 同步 我们把进程间的这种必须互相合作的协同工作关系 称为进程同步 进程之间的互斥是由于共享系统资源而引起的一种间接制约关系进程之间的同步是并发进程由于要协作完成同一个任务而引起的一种直接制约关系如果无进程在使用共享资源时 可允许任何一个进程去使用共享资源 即使某个进程刚用过也允许再次使用 这是通过进程互斥的方式来管理共享资源如果某个进程通过共享资源得到指定消息时 在指定消息未到达之前 即使无进程在共享资源仍不允许该进程去使用共享资源 这是通过采用进程同步的方式来管理共享资源 有些问题是互斥问题 有些是同步问题 有些是互斥同步混合问题 实现临界区互斥的基本方法 临界资源 一些被共享的资源 具有一次仅允许一个进程使用的特点临界区 并发进程访问临界资源的那段必须互斥执行的程序实现临界区互斥一个遵循的准则有空让进 临界区空闲时 允许一个进程进入执行无空等待 有进程在临界区执行时 要进入的进程必须等待让权等待 有进程在临界区执行时 要求进入的进程必须立即释放CPU而等待有限等待 不应该使进入临界区的进程无限期地等待在临界区之外实现方法 软件方法 硬件方法 临界区问题的解决方案 满足三个基本条件 MutualExclusion 互斥条件 IfprocessPiisexecutinginitsCS thennootherprocessescanbeexecutingintheirCSsProgress 进入条件 IfnoprocessisexecutinginitsCSandsomeprocesseswishtoentertheirCSs thenonlythoseprocessesthatarenotexecutingintheirRSscanparticipateinthedecisiononwhichwillenteritsCSnext andthisselectioncannotbepostponedindefinitely BoundedWaiting 有限等待的条件 Thereexistsabound orlimit onthenumberoftimesthatotherprocessesareallowedtoentertheirCSaafteraprocesshasmadearequesttoenteritsCSandbeforethatrequestisgranted 信号量 信号量表示资源的物理实体typedefstruct intvalue 系统初始化时根据代表资源类可用的数量给其赋值structprocess L 等待使用该资源的进程列表 semaphore信号量的操作 P wait V signal P相当于申请资源V相当于释放资源操作系统利用信号量的状态对进程和资源进行管理 根据用途不同 可以把信号量分为公用信号量和私有信号量公用信号量 用于解决进程之间互斥进入临界区私有信号量 用于解决异步环境下进程之间的同步 利用信号量解决临界区互斥 设置一个公用信号量Mutext 初始值为1 任何要使用临界区资源的进程 调用P Mutext 使用临界区 调用V Mutex 利用信号量和PV操作实现进程同步 对所有协作关系的并发进程 他们在使用共享资源时必须互通消息 仅当进程收到指定的消息后才能使用共享资源 否则需等待 直到指定的消息到达 经典同步问题 生产者 消费者同步 生产者将生产的产品放入缓存区 消费者从缓存区取用产品 所以他们要互通消息 生产者放之前要测试缓存区是不是满 消费者在从缓存区取之前要测试是不是为空 互斥 任何时候只有一个生产者或者消费者可以访问缓存区读者 写者读写互斥访问写写互斥访问允许多个读者同时读 多个读者共享读者计数器变量 互斥操作哲学家就餐 读者 写者 写者优先 intreadcount 0 writecount 0 读者 写者计数semaphorermutex 1 wmutex 1 读者 写者分别互斥访问readcount writecountsemaphorerwmutex 1 读者 写者互斥访问文件semaphorer 1 所有读者排队semaphorerw 1 一个读者与一个写者竞争访问文件 读者do wait r 其他读进程在r上排队wait rw 一个读进程与一个写进程在rw上竞争wait rmutex readcount if readcount 1 wait rwmutex signal rmutex signal rw signal r 读数据 CSwait rmutex readcount if readcount 0 signal rwmutex signal rmutex while 1 写者Do wait wmutex writecount if writecount 1 wait rw 一个写进程在rw竞争signal wmutex wait rwmutex 其他写进程在rwmutex上排队写数据 CSwait wmutex writecount if writecount 0 signal rw 都写完通知读进程signal wmutex While 1 读者 写者 两者公平 intreadcount 0 读者计数semaphorermutex 1 读者互斥访问readcountsemaphorerwmutex 1 读者 写者互斥访问文件semaphorerw 1 读者与写者竞争访问文件 读者do wait rw 读进程与写进程在rw上竞争wait rmutex readcount if readcount 1 wait rwmutex signal rmutex signal rw 读数据 CSwait rmutex readcount if readcount 0 signal rwmutex signal rmutex while 1 写者Do wait rw 读者写者竞争wait rwmutex 写数据 CSsignal wmutex signal rw While 1 哲学家就餐 共享变量semaphorechopstick 5 mutex Initiallyallvaluesare1Philosopheri do wait mutex wait chopstick i wait chopstick i 1 5 signal mutex eat signal chopstick i signal chopstick i 1 5 think while 1 Chapter7 7 4Thefirstknowncorrectsoftwaresolutiontothecritical sectionproblemfortwothreadswasdevelopedbyDekker Thetwothreads T0andT1 sharethefollowingvariables Booleanflag 2 initiallyfalse intturn ThestructureofthreadTi i 0or1 withTj j 1or0 beingtheotherthread isshownas do flag i true while flag j if turn j flag i false while turn j flag i true criticalsectionturn j flag i false remaindersection while 1 Provethatthealgorithmsatisfiesallthreerequirementsforthecritical sectionproblem 互斥 只能有一个在临界区Pi在临界区 Pj想进 看flag某进程进入临界区之前 Pi Pj都置flag为true 看turn 只有进了的进程退出临界区以后另一个才能进进度 当前没有进程在临界区 只有一个进程试图进 看flag两个都试图进 看turn 进了进程在有限时间内复位flag有限等待 Pi被拒绝进入临界区 Pj已在临界区或者获准进入 当Pj退出临界区 置turn为i 复位flag Pi可以进 7 cont 7 5Thefirstknowncorrectsoftwaresolutiontothecritical sectionproblemfornprocesseswithalowerboundonwaitingofn 1turnswaspresentedbyEisenbergandMcGuire Theprocessessharethefollowingvariables enumpstatefidle wantin incsg pstateflag n intturn Alltheelementsofflagareinitiallyidle theinitialvalueofturnisimmaterial between0andn 1 ThestructureofprocessPiisshownas Provethatthealgorithmsatisfiesallthreerequirementsforthecritical sectionproblem 7 cont 7 7Showthat ifthewaitandsignaloperationsarenotexecutedatomically thenmutualexclusionmaybeviolated 7 cont 7 8TheSleeping BarberProblem Abarbershopconsistsofawaitingroomwithnchairsandthebarberroomcontainingthebarberchair Iftherearenocustomerstobeserved thebarbergoestosleep Ifacustomerentersthebarbershopandallchairsareoccupied thenthecustomerleavestheshop Ifthebarberisbusybutchairsareavailable thenthecustomersitsinoneofthefreechairs Ifthebarberisasleep thecustomerwakesupthebarber Writeaprogramtocoordinatethebarberandthecustomers 理发师和顾客同步 理发师必须由顾客唤醒 理发师给一个顾客理发完 要让理发完的顾客退出 让等待顾客进入 顾客互斥的占用n个位置 共享变量semaphoreScuthair Snumchair Scuthair制约理发师 Snumchair制约顾客Scuthair 0 Snumchair 0 barber do wait Scuthair 检查是否有顾客 无就睡眠给某个顾客理发signal Snumchair 让理发完的顾客退出 让等待的一个顾客进入 while 1 Customeri wait Snumchair 申请占用椅子signal Scuthair 给理发师发一个信号坐在椅子上等着理发 共享变量semaphoreScuthair Mutexchair Scuthair给理发师 Mutexchair制约顾客对椅子的互斥占领intnumber 0 顾客的共享变量 记录已经有的顾客数Scuthair 0 Mutexchair 1 Customeri wait Mutexchair 申请对共享变量number的操作 申请占用椅子 if number n 1 signal Mutexchair exit number number 1 signal Scuthair 给理发师发一个信号signal Mutexchair 等待理发 理发完毕 wait Mutexchair 申请对共享变量number的操作number number 1 signal Mutexchair 离开理发店barber do wait Scuthair 检查是否有顾客 无 就睡眠给某个顾客理发 while 1 7 cont 7 9TheCigarette SmokersProblem Considerasystemwiththreesmokerprocessesandoneagentprocess Eachsmokercontinuouslyrollsacigaretteandthensmokesit Buttorollandsmokeacigarette thesmokerneedsthreeingredients tobacco paper andmatches Oneofthesmokerprocesseshaspaper anotherhastobacco andthethirdhasmatches Theagenthasaninfinitesupplyofallthreematerials Theagentplacestwooftheingredientsonthetable Thesmokerwhohastheremainingingredientthenmakesandsmokesacigarette signalingtheagentoncompletion Theagentthenputsoutanothertwoofthethreeingredients andthecyclerepeats Writeaprogramtosynchronizetheagentandthesmokers 原料供应者和三个吸烟者之间需要同步 共享变量semaphoreSa Ss 分别控制供应者和吸烟者Sa 1 Ss 0 供应者wait Sa 桌面上没有原料任意丢两样东西到桌面signal Ss 通知吸烟者 吸烟者wait Ss 查看桌面原料 同时只能有一个吸烟者查看if 是我需要的两种原料 取原料 卷烟 吸烟signal Sa 通知供应者可以放新的原料 else signal Ss 让别的吸烟者查看 吸烟者另解 更细 共享变量semaphoreSa 控制供应者semaphoreS1 S2 S3 控制三个吸烟者Sa 1 S1 S2 S3 0 供应者flagf1 f2 f3 三个标记 分别代表纸 烟草 火柴wait Sa 桌面上没有原料任意丢两样东西到桌面if f2 通知有火柴的吸烟者 有纸的吸烟者wait S1 等待桌面上有需要的原料取烟草 火柴 卷烟 吸烟signal Sa 通知供应者可以放新的原料 有烟草的吸烟者wait S2 等待桌面上有需要的原料取纸 火柴 卷烟 吸烟signal Sa 通知供应者可以放新的原料 有火柴的吸烟者wait S3 等待桌面上有需要的原料取纸 烟草 卷烟 吸烟signal Sa 通知供应者可以放新的原料 Chapter8 资源是有限的 对资源的需求可能是无限的当占有了部分资源而渴求更多的资源的时候 可能会引起deadlock 死锁 计算机资源具有两类不同的性质 可抢占和不可抢占可抢占资源 当资源从占用进程剥夺走时 对进程不产生破坏性影响 CPU和主存不可抢占资源 当资源从占用进程剥夺走时 可能引起进程计算失败 打印机 绘图仪 通常 死锁涉及的是不可抢占资源死锁 一组进程是死锁的 该组中的每一个进程正在等待这组中其他进程占有的资源时可能引起的一种错误现象 死锁产生的原因根本原因 系统资源不足进程推进顺序不当死锁产生的必要条件互斥 占有和等待 不可剥夺 循环等待 死锁处理策略 忽略不计预防 设法破坏四个必要条件避免为进程分配资源时 每当完成分配后 立即检查系统是否处于安全状态 若是 分配成功 否则 分配作废 让其阻塞等待资源分配图算法 银行家算法需要进程对资源需求的先验知识设法找到一种安全的进程执行序列检测与恢复采用资源动态分配算法 当进程请求分配资源时 只要系统有可用资源就满足 系统定期启动死锁检测算法 检查是否有环 进程等待图 Chapter8 8 4ConsiderthetrafficdeadlockdepictedinfollowingFigure a Showthatthefournecessaryconditionsfordeadlockindeedholdinthisexample b Stateasimplerulethatwillavoiddeadlocksinthissystem 8 cont 8 6Inarealcomputersystem neithertheresourcesavailablenorthedemandsofprocessesforresourcesareconsistentoverlongperiods months Resourcesbreakorarereplaced newprocessescomeandgo newresourcesareboughtandaddedtothesystem Ifdeadlockiscontrolledbythebanker salgorithm whichofthefollowingchangescanbemadesafely withoutintroducingthepossibilityofdeadlock andunderwhatcircumstances a IncreaseAvailable newresourcesadded b DecreaseAvailable resourcepermanentlyremovedfromsystem c IncreaseMaxforoneprocess theprocessneedsmoreresourcesthanallowed itmaywantmore d DecreaseMaxforoneprocess theprocessdecidesitdoesnotneedthatmanyresources e Increasethenumberofprocessesf Decreasethenumberofprocesses 8 cont 8 9Considerasystemconsistingofmresourcesofthesametype beingsharedbynprocesses Resourcescanberequestedandreleasedbyprocessesonlyoneatatime Showthatthesystemisdeadlock freeifthefollowingtwoconditionshold a Themaximumneedofeachprocessisbetween1andmresourcesb Thesumofallmaximumneedsislessthanm n已知 资源m个 进程n个 资源的请求和释放一次一个Maxi 1 m Maxi m n因为Needi Allocationi Maxi所以 Needi Allocationi Maxi m n假设存在死锁 则所有资源分配完成即 Allocationi m由 Needi Allocationi m n得 Needi n 故有进程Pi所需资源为0由于Maxi 1 m 所以Pi已经分配至少一个资源 他执行完以后至少可以释放一个资源 由已知可知资源的请求一次只一个 所以不会存在死锁 8 cont 8 13Considerthefollowingsnapshotofasystem Answerthefollowingquestionsusingthebanker salgorithm a WhatisthecontentofthematrixNeed b Isthesysteminasafestate c IfarequestfromprocessP1arrivesfor 0 4 2 0 cantherequestbegrantedimmediately a Need Max Allocation00000750100200200642b 安全算法找安全序列c 先请求算法 再安全算法找安全序列 如果安全 请求可以响应- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统概念 操作系统 概念 第六 作业 解答
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文