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

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

struct{

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

structprocess*L;//等待使用該資源的進(jìn)程列表

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

readcount=0,writecount=0;//讀者、寫者計(jì)數(shù)semaphorermutex=1,wmutex=1;//讀者、寫者分別互斥訪問readcount,writecountsemaphorerwmutex=1;//讀者、寫者互斥訪問文件semaphorer=1;//所有讀者排隊(duì)semaphorerw=1;//一個(gè)讀者與一個(gè)寫者競(jìng)爭(zhēng)訪問文件//讀者do{

wait(r);//其他讀進(jìn)程在r上排隊(duì)

wait(rw);//一個(gè)讀進(jìn)程與一個(gè)寫進(jìn)程在rw上競(jìng)爭(zhēng)

wait(rmutex);

readcount++;

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

signal(rmutex);

signal(rw);

signal(r);

讀數(shù)據(jù)…//CS

wait(rmutex);

readcount--;

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

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

wait(wmutex);

writecount++;

if(writecount==1)wait(rw);//一個(gè)寫進(jìn)程在rw競(jìng)爭(zhēng)

signal(wmutex);

wait(rwmutex);//其他寫進(jìn)程在rwmutex上排隊(duì)

寫數(shù)據(jù)…//CS

wait(wmutex);

writecount--;

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

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

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

wait(rw);//讀進(jìn)程與寫進(jìn)程在rw上競(jìng)爭(zhēng)

wait(rmutex);

readcount++;

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

signal(rmutex);

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

wait(rmutex);

readcount--;

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

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

wait(rw);//讀者寫者競(jìng)爭(zhēng)

wait(rwmutex);

寫數(shù)據(jù)…//CS

signal(wmutex);

signal(rw);}While(1)哲學(xué)家就餐共享變量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.互斥：只能有一個(gè)在臨界區(qū)

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

兩個(gè)都試圖進(jìn)，看turn，進(jìn)了進(jìn)程在有限時(shí)間內(nèi)復(fù)位flag有限等待：

Pi被拒絕進(jìn)入臨界區(qū)，Pj已在臨界區(qū)或者獲準(zhǔn)進(jìn)入，當(dāng)Pj退出臨界區(qū)，置turn為i，復(fù)位flag，Pi可以進(jìn)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ā)師給一個(gè)顧客理發(fā)完，要讓理發(fā)完的顧客退出，讓等待顧客進(jìn)入，顧客互斥的占用n個(gè)位置//共享變量semaphoreScuthair,Snumchair;//Scuthair制約理發(fā)師,Snumchair制約顧客Scuthair=0;Snumchair=0;barber: do{

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

給某個(gè)顧客理發(fā)

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

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

signal(Scuthair);//給理發(fā)師發(fā)一個(gè)信號(hào)

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

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

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

signal(Scuthair);//給理發(fā)師發(fā)一個(gè)信號(hào)

signal(Mutexchair);

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

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

signal(Mutexchair);

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

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

給某個(gè)顧客理發(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.原料供應(yīng)者和三個(gè)吸煙者之間需要同步//共享變量semaphoreSa,Ss;//分別控制供應(yīng)者和吸煙者Sa=1;

Ss=0;//供應(yīng)者wait(Sa);//桌面上沒有原料任意丟兩樣?xùn)|西到桌面signal(Ss);//通知吸煙者//吸煙者wait(Ss);//查看桌面原料，同時(shí)只能有一個(gè)吸煙者查看if(是我需要的兩種原料){取原料，卷煙，吸煙

signal(Sa);//通知供應(yīng)者可以放新的原料}else{

signal(Ss);//讓別的吸煙者查看}吸煙者另解-更細(xì)//共享變量semaphoreSa;//控制供應(yīng)者semaphoreS1,S2,S3;//控制三個(gè)吸煙者Sa=1;S1=S2=S3=0;//供應(yīng)者flagf1,f2,f3;//三個(gè)標(biāo)記，分別代表紙，煙草，火柴wait(Sa);//桌面上沒有原料任意丟兩樣?xùn)|西到桌面if(f2&&f3)//供煙草，火柴

signal(S1);//通知有紙的吸煙者elseif(f1&&f3)signal(S2);//通知有煙草的吸煙者elsesignal(S3);//通知有火柴的吸煙者//有紙的吸煙者wait(S1);//等待桌面上有需要的原料取煙草，火柴，卷煙，吸煙signal(Sa);//通知供應(yīng)者可以放新的原料//有煙草的吸煙者wait(S2);//等待桌面上有需要的原料取紙，火柴，卷煙，吸煙signal(Sa);//通知供應(yīng)者可以放新的原料//有火柴的吸煙者wait(S3);//等待桌面上有需要的原料取紙，煙草，卷煙，吸煙signal(Sa);//通知供應(yīng)者可以放新的原料Chapter8資源是有限的，對(duì)資源的需求可能是無限的當(dāng)占有了部分資源而渴求更多的資源的時(shí)候，可能會(huì)引起deadlock（死鎖）計(jì)算機(jī)資源具有兩類不同的性質(zhì)：可搶占和不可搶占可搶占資源：當(dāng)資源從占用進(jìn)程剝奪走時(shí)，對(duì)進(jìn)程不產(chǎn)生破壞性影響，CPU和主存不可搶占資源：當(dāng)資源從占用進(jìn)程剝奪走時(shí)，可能引起進(jìn)程計(jì)算失敗，打印機(jī)、繪圖儀、通常，死鎖涉及的是不可搶占資源死鎖：一組進(jìn)程是死鎖的，該組中的每一個(gè)進(jìn)程正在等待這組中其他進(jìn)程占有的資源時(shí)可能引起的一種錯(cuò)誤現(xiàn)象。死鎖產(chǎn)生的原因根本原因，系統(tǒng)資源不足進(jìn)程推進(jìn)順序不當(dāng)死鎖產(chǎn)生的必要條件互斥，占有和等待，不可剝奪，循環(huán)等待死鎖處理策略忽略不計(jì)預(yù)防，設(shè)法破壞四個(gè)必要條件避免為進(jìn)程分配資源時(shí)，每當(dāng)完成分配后，立即檢查系統(tǒng)是否處于安全狀態(tài)，若是，分配成功，否則，分配作廢，讓其阻塞等待資源分配圖算法、銀行家算法需要進(jìn)程對(duì)資源需求的先驗(yàn)知識(shí)設(shè)法找到一種安全的進(jìn)程執(zhí)行序列檢測(cè)與恢復(fù)采用資源動(dòng)態(tài)分配算法，當(dāng)進(jìn)程請(qǐng)求分配資源時(shí)，只要系統(tǒng)有可用資源就滿足，系統(tǒng)定期啟動(dòng)死鎖檢測(cè)算法，檢查是否有環(huán)（進(jì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