《操作系統(tǒng)概念》第六版作業(yè)解答2解讀

Chapter7進程同步進程的同步隱含了系統(tǒng)中并發(fā)進程之間存在的兩種相互制約關系：競爭（互斥）與協(xié)作（同步）互斥：兩個并行的進程A、B，如果當A進行某個操作時，B不能做這一操作，進程間的這種限制條件稱為進程互斥，這是引起資源不可共享的原因。同步：我們把進程間的這種必須互相合作的協(xié)同工作關系，稱為進程同步。進程之間的互斥是由于共享系統(tǒng)資源而引起的一種間接制約關系進程之間的同步是并發(fā)進程由于要協(xié)作完成同一個任務而引起的一種直接制約關系如果無進程在使用共享資源時，可允許任何一個進程去使用共享資源（即使某個進程剛用過也允許再次使用），這是通過進程互斥的方式來管理共享資源如果某個進程通過共享資源得到指定消息時，在指定消息未到達之前，即使無進程在共享資源仍不允許該進程去使用共享資源，這是通過采用進程同步的方式來管理共享資源。有些問題是互斥問題，有些是同步問題，有些是互斥同步混合問題實現(xiàn)臨界區(qū)互斥的基本方法臨界資源：一些被共享的資源，具有一次僅允許一個進程使用的特點臨界區(qū)：并發(fā)進程訪問臨界資源的那段必須互斥執(zhí)行的程序實現(xiàn)臨界區(qū)互斥一個遵循的準則有空讓進，臨界區(qū)空閑時，允許一個進程進入執(zhí)行無空等待，有進程在臨界區(qū)執(zhí)行時，要進入的進程必須等待讓權等待，有進程在臨界區(qū)執(zhí)行時，要求進入的進程必須立即釋放CPU而等待有限等待，不應該使進入臨界區(qū)的進程無限期地等待在臨界區(qū)之外實現(xiàn)方法：軟件方法、硬件方法臨界區(qū)問題的解決方案-滿足三個基本條件MutualExclusion(互斥條件)：IfprocessPiisexecutinginitsCS,thennootherprocessescanbeexecutingintheirCSsProgress(進入條件)：IfnoprocessisexecutinginitsCSandsomeprocesseswishtoentertheirCSs,thenonlythoseprocessesthatarenotexecutingintheirRSscanparticipateinthedecisiononwhichwillenteritsCSnext,andthisselectioncannotbepostponedindefinitely.BoundedWaiting(有限等待的條件)：Thereexistsabound,orlimit,onthenumberoftimesthatotherprocessesareallowedtoentertheirCSaafteraprocesshasmadearequesttoenteritsCSandbeforethatrequestisgranted.信號量信號量表示資源的物理實體typedef

struct{

intvalue;//系統(tǒng)初始化時根據代表資源類可用的數(shù)量給其賦值

structprocess*L;//等待使用該資源的進程列表

}semaphore信號量的操作：P（wait）、V（signal）P相當于申請資源V相當于釋放資源操作系統(tǒng)利用信號量的狀態(tài)對進程和資源進行管理，根據用途不同，可以把信號量分為公用信號量和私有信號量公用信號量，用于解決進程之間互斥進入臨界區(qū)私有信號量，用于解決異步環(huán)境下進程之間的同步，利用信號量解決臨界區(qū)互斥，設置一個公用信號量Mutext，初始值為1，任何要使用臨界區(qū)資源的進程：調用P(Mutext)，使用臨界區(qū)，調用V(Mutex)利用信號量和PV操作實現(xiàn)進程同步，對所有協(xié)作關系的并發(fā)進程，他們在使用共享資源時必須互通消息，僅當進程收到指定的消息后才能使用共享資源，否則需等待，直到指定的消息到達。經典同步問題生產者-消費者同步，生產者將生產的產品放入緩存區(qū)，消費者從緩存區(qū)取用產品，所以他們要互通消息，生產者放之前要測試緩存區(qū)是不是滿，消費者在從緩存區(qū)取之前要測試是不是為空。互斥，任何時候只有一個生產者或者消費者可以訪問緩存區(qū)讀者-寫者讀寫互斥訪問寫寫互斥訪問允許多個讀者同時讀，多個讀者共享讀者計數(shù)器變量，互斥操作哲學家就餐讀者-寫者（寫者優(yōu)先）int

readcount=0,writecount=0;//讀者、寫者計數(shù)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);

讀數(shù)據…//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上排隊

寫數(shù)據…//CS

wait(wmutex);

writecount--;

if(writecount==0)signal(rw);//都寫完通知讀進程

signal(wmutex);}While(1)讀者-寫者（兩者公平）int

readcount=0;//讀者計數(shù)semaphorermutex=1;//讀者互斥訪問readcountsemaphorerwmutex=1;//讀者、寫者互斥訪問文件semaphorerw=1;//讀者與寫者競爭訪問文件//讀者do{

wait(rw);//讀進程與寫進程在rw上競爭

wait(rmutex);

readcount++;

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

signal(rmutex);

signal(rw);讀數(shù)據…//CS

wait(rmutex);

readcount--;

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

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

wait(rw);//讀者寫者競爭

wait(rwmutex);

寫數(shù)據…//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.互斥：只能有一個在臨界區(qū)

Pi在臨界區(qū)，Pj想進，看flag某進程進入臨界區(qū)之前，Pi、Pj都置flag為true，看turn，只有進了的進程退出臨界區(qū)以后另一個才能進進度： 當前沒有進程在臨界區(qū)，只有一個進程試圖進，看flag

兩個都試圖進，看turn，進了進程在有限時間內復位flag有限等待：

Pi被拒絕進入臨界區(qū)，Pj已在臨界區(qū)或者獲準進入，當Pj退出臨界區(qū)，置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.理發(fā)師和顧客同步，理發(fā)師必須由顧客喚醒，理發(fā)師給一個顧客理發(fā)完，要讓理發(fā)完的顧客退出，讓等待顧客進入，顧客互斥的占用n個位置//共享變量semaphoreScuthair,Snumchair;//Scuthair制約理發(fā)師,Snumchair制約顧客Scuthair=0;Snumchair=0;barber: do{

wait(Scuthair);//檢查是否有顧客，無就睡眠

給某個顧客理發(fā)

signal(Snumchair);//讓理發(fā)完的顧客退出，讓等待的一個顧客進入 }while(1);Customeri:

wait(Snumchair);//申請占用椅子

signal(Scuthair);//給理發(fā)師發(fā)一個信號

坐在椅子上等著理發(fā)//共享變量semaphoreScuthair,Mutexchair;//Scuthair給理發(fā)師,Mutexchair制約顧客對椅子的互斥占領intnumber=0;//顧客的共享變量，記錄已經有的顧客數(shù)Scuthair=0;Mutexchair=1;Customeri:

wait(Mutexchair);//申請對共享變量number的操作（申請占用椅子）

if(number==n-1){signal(Mutexchair);exit;}number=number+1;

signal(Scuthair);//給理發(fā)師發(fā)一個信號

signal(Mutexchair);

等待理發(fā)…理發(fā)完畢…

wait(Mutexchair);//申請對共享變量number的操作number=number-1;

signal(Mutexchair);

離開理發(fā)店barber: do{

wait(Scuthair);//檢查是否有顧客，無，就睡眠

給某個顧客理發(fā) }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和主存不可搶占資源：當資源從占用進程剝奪走時，可能引起進程計算失敗，打印機、繪圖儀、通常，死鎖涉及的是不可搶占資源死鎖：一組進程是死鎖的，該組中的每一個進程正在等待這組中其他進程占有的資源時可能引起的一種錯誤現(xiàn)象。死鎖產生的原因根本原因，系統(tǒng)資源不足進程推進順序不當死鎖產生的必要條件互斥，占有和等待，不可剝奪，循環(huán)等待死鎖處理策略忽略不計預防，設法破壞四個必要條件避免為進程分配資源時，每當完成分配后，立即檢查系統(tǒng)是否處于安全狀態(tài)，若是，分配成功，否則，分配作廢，讓其阻塞等待資源分配圖算法、銀行家算法需要進程對資源需求的先驗知識設法找到一種安全的進程執(zhí)行序列檢測與恢復采用資源動態(tài)分配算法，當進程請求分配資源時，只要系統(tǒng)有可用資源就滿足，系統(tǒng)定期啟動死鎖檢測算法，檢查是否有環(huán)（進程等待圖）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