《操作系统概念》第六版作业解答2解读

Chapter7进程同步进程的同步隐含了系统中并发进程之间存在的两种相互制约关系：竞争（互斥）与协作（同步）互斥：两个并行的进程A、B，如果当A进行某个操作时，B不能做这一操作，进程间的这种限制条件称为进程互斥，这是引起资源不可共享的原因。同步：我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。进程之间的互斥是由于共享系统资源而引起的一种间接制约关系进程之间的同步是并发进程由于要协作完成同一个任务而引起的一种直接制约关系如果无进程在使用共享资源时，可允许任何一个进程去使用共享资源（即使某个进程刚用过也允许再次使用），这是通过进程互斥的方式来管理共享资源如果某个进程通过共享资源得到指定消息时，在指定消息未到达之前，即使无进程在共享资源仍不允许该进程去使用共享资源，这是通过采用进程同步的方式来管理共享资源。有些问题是互斥问题，有些是同步问题，有些是互斥同步混合问题实现临界区互斥的基本方法临界资源：一些被共享的资源，具有一次仅允许一个进程使用的特点临界区：并发进程访问临界资源的那段必须互斥执行的程序实现临界区互斥一个遵循的准则有空让进，临界区空闲时，允许一个进程进入执行无空等待，有进程在临界区执行时，要进入的进程必须等待让权等待，有进程在临界区执行时，要求进入的进程必须立即释放CPU而等待有限等待，不应该使进入临界区的进程无限期地等待在临界区之外实现方法：软件方法、硬件方法临界区问题的解决方案-满足三个基本条件MutualExclusion(互斥条件)：IfprocessPiisexecutinginitsCS,thennootherprocessescanbeexecutingintheirCSsProgress(进入条件)：IfnoprocessisexecutinginitsCSandsomeprocesseswishtoentertheirCSs,thenonlythoseprocessesthatarenotexecutingintheirRSscanparticipateinthedecisiononwhichwillenteritsCSnext,andthisselectioncannotbepostponedindefinitely.BoundedWaiting(有限等待的条件)：Thereexistsabound,orlimit,onthenumberoftimesthatotherprocessesareallowedtoentertheirCSaafteraprocesshasmadearequesttoenteritsCSandbeforethatrequestisgranted.信号量信号量表示资源的物理实体typedef

struct{

intvalue;//系统初始化时根据代表资源类可用的数量给其赋值

structprocess*L;//等待使用该资源的进程列表

}semaphore信号量的操作：P（wait）、V（signal）P相当于申请资源V相当于释放资源操作系统利用信号量的状态对进程和资源进行管理，根据用途不同，可以把信号量分为公用信号量和私有信号量公用信号量，用于解决进程之间互斥进入临界区私有信号量，用于解决异步环境下进程之间的同步，利用信号量解决临界区互斥，设置一个公用信号量Mutext，初始值为1，任何要使用临界区资源的进程：调用P(Mutext)，使用临界区，调用V(Mutex)利用信号量和PV操作实现进程同步，对所有协作关系的并发进程，他们在使用共享资源时必须互通消息，仅当进程收到指定的消息后才能使用共享资源，否则需等待，直到指定的消息到达。经典同步问题生产者-消费者同步，生产者将生产的产品放入缓存区，消费者从缓存区取用产品，所以他们要互通消息，生产者放之前要测试缓存区是不是满，消费者在从缓存区取之前要测试是不是为空。互斥，任何时候只有一个生产者或者消费者可以访问缓存区读者-写者读写互斥访问写写互斥访问允许多个读者同时读，多个读者共享读者计数器变量，互斥操作哲学家就餐读者-写者（写者优先）int

readcount=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);

读数据…//CS

wait(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上排队

写数据…//CS

wait(wmutex);

writecount--;

if(writecount==0)signal(rw);//都写完通知读进程

signal(wmutex);}While(1)读者-写者（两者公平）int

readcount=0;//读者计数semaphorermutex=1;//读者互斥访问readcountsemaphorerwmutex=1;//读者、写者互斥访问文件semaphorerw=1;//读者与写者竞争访问文件//读者do{

wait(rw);//读进程与写进程在rw上竞争

wait(rmutex);

readcount++;

if(readcount==1)wait(rwmutex);

signal(rmutex);

signal(rw);读数据…//CS

wait(rmutex);

readcount--;

if(readcount==0)signal(rwmutex);

signal(rmutex);}while(1);//写者Do{

wait(rw);//读者写者竞争

wait(rwmutex);

写数据…//CS

signal(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);Chapter77.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:

enum

pstate

fidle,wantin,incsg;

pstate

flag[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&&f3)//供烟草，火柴

signal(S1);//通知有纸的吸烟者elseif(f1&&f3)signal(S2);//通知有烟草的吸烟者elsesignal(S3);//通知有火柴的吸烟者//有纸的吸烟者wait(S1);//等待桌面上有需要的原料取烟草，火柴，卷烟，吸烟signal(Sa);//通知供应者可以放新的原料//有烟草的吸烟者wait(S2);//等待桌面上有需要的原料取纸，火柴，卷烟，吸烟signal(Sa);//通知供应者可以放新的原料//有火柴的吸烟者wait(S3);//等待桌面上有需要的原料取纸，烟草，卷烟，吸烟signal(Sa);//通知供应者可以放新的原料Chapter8资源是有限的，对资源的需求可能是无限的当占有了部分资源而渴求更多的资源的时候，可能会引起deadlock（死锁）计算机资源具有两类不同的性质：可抢占和不可抢占可抢占资源：当资源从占用进程剥夺走时，对进程不产生破坏性影响，CPU和主存不可抢占资源：当资源从占用进程剥夺走时，可能引起进程计算失败，打印机、绘图仪、通常，死锁涉及的是不可抢占资源死锁：一组进程是死锁的，该组中的每一个进程正在等待这组中其他进程占有的资源时可能引起的一种错误现象。死锁产生的原因根本原因，系统资源不足进程推进顺序不当死锁产生的必要条件互斥，占有和等待，不可剥夺，循环等待死锁处理策略忽略不计预防，设法破坏四个必要条件避免为进程分配资源时，每当完成分配后，立即检查系统是否处于安全状态，若是，分配成功，否则，分配作废，让其阻塞等待资源分配图算法、银行家算法需要进程对资源需求的先验知识设法找到一种安全的进程执行序列检测与恢复采用资源动态分配算法，当进程请求分配资源时，只要系统有可用资源就满足，系统定期启动死锁检测算法，检查是否有环（进程等待图）Chapter88.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