操作系統(tǒng) 第二章作業(yè)本(含答案).doc

第二章作業(yè)第一次作業(yè)：1. 進(jìn)程有哪三種基本狀態(tài)？進(jìn)程在三種基本狀態(tài)之間轉(zhuǎn)換的典型原因是什么？ 答： 三種基本狀態(tài)：就緒狀態(tài)、執(zhí)行狀態(tài)、阻塞狀態(tài)。 （1）就緒狀態(tài)執(zhí)行狀態(tài)：進(jìn)程分配到CPU資源（進(jìn)程調(diào)度）；（2）執(zhí)行狀態(tài)就緒狀態(tài)：時(shí)間片用完（3）執(zhí)行狀態(tài)阻塞狀態(tài)：I/O請(qǐng)求（4）阻塞狀態(tài)就緒狀態(tài)：I/O完成2. 在Linux系統(tǒng)中運(yùn)行下面程序，最多可產(chǎn)生多少個(gè)進(jìn)程？畫(huà)出進(jìn)程家族樹(shù)。main() fork(); fork(); fork();答：最多可以產(chǎn)生7個(gè)進(jìn)程。其家族樹(shù)為： 3. 試從動(dòng)態(tài)性、并發(fā)性和獨(dú)立性上比較進(jìn)程和程序。答：1) 動(dòng)態(tài)性是進(jìn)程最基本的特性，可表現(xiàn)為由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，因得不到資源而暫停執(zhí)行，以及由撤銷(xiāo)而消亡，因而進(jìn)程由一定的生命期；而程序只是一組有序指令的集合，并存放于某種介質(zhì)上，其本身并不具有運(yùn)動(dòng)的含義，因而是靜態(tài)的；2) 并發(fā)性是進(jìn)程的重要特征，同時(shí)也是OS的重要特征。引入進(jìn)程的目的正是為了使其程序能和其它建立了進(jìn)程的程序并發(fā)執(zhí)行，而程序本身（沒(méi)有建立PCB）是不能并發(fā)執(zhí)行的；3) 獨(dú)立性是指進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立接受調(diào)度的基本單位。凡未建立PCB的程序，都不能作為一個(gè)獨(dú)立的單位來(lái)運(yùn)行。4. 分析下列代碼的功能：答：sleep_on實(shí)現(xiàn)進(jìn)程的睡眠過(guò)程；wake_up實(shí)現(xiàn)進(jìn)程的喚醒過(guò)程。第二次作業(yè)：1. 同步機(jī)制應(yīng)該遵循哪些基本準(zhǔn)則？你認(rèn)為整型信號(hào)量機(jī)制遵循了同步機(jī)制的哪些基本準(zhǔn)則？ 答：同步機(jī)制應(yīng)遵循四個(gè)基本準(zhǔn)則：a.空閑讓進(jìn)：當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。b.忙則等待：當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，其它試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問(wèn)。c.有限等待：對(duì)要求訪問(wèn)臨界資源的進(jìn)程，應(yīng)保證在有限時(shí)間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入“死等”狀態(tài)。d.讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”狀態(tài)。整型信號(hào)量機(jī)制使進(jìn)程處于“忙等”狀態(tài)，并未遵循“讓權(quán)等待”的準(zhǔn)則；而記錄型信號(hào)量機(jī)制則完全遵循了同步機(jī)構(gòu)的四條準(zhǔn)則。 2. 使用信號(hào)量實(shí)現(xiàn)下面的前趨圖。答：Var a,b,c,d,e,f,g,h:semaphore:=0,0,0,0,0,0,0,0; begin parbegin begin S1;signal(a);signal(b);end; begin wait(a);s2; signal(c); signal(d); end; begin wait(b);s3; signal(e); end; begin wait(c);s4; signal(f); end; begin wait(d);s5; signal(g); end;begin wait(e);s6; signal(h); end; begin wait(f);wait(g);wait(h);s6; end; parend end3. 我們?yōu)槟撑R界資源設(shè)置一把鎖W，當(dāng)W=1時(shí)表示關(guān)鎖；當(dāng)W=0時(shí)表示鎖已打開(kāi)，試寫(xiě)出開(kāi)鎖和關(guān)鎖原語(yǔ)，并利用它們?nèi)?shí)現(xiàn)互斥。答：整型信號(hào)量：lock(W): while W=1 do no-opW:=1;unlock(W): W:=0;記錄型信號(hào)量：lock(W): W:=W+1;if(W1) then block(W, L)unlock(W): W:=W-1;if(W0) then wakeup(W, L)例子：Var W:semaphore:=0；beginrepeatlock(W);critical sectionunlock(W);remainder sectionuntil false;end4. 桌子上有一個(gè)空盤(pán)子，允許存放一只水果，爸爸可以向盤(pán)中放蘋(píng)果，媽媽向盤(pán)子中放橘子，女兒專門(mén)吃盤(pán)子中的蘋(píng)果，兒子專門(mén)吃盤(pán)子中的橘子。規(guī)定當(dāng)盤(pán)子空的時(shí)候一次只能放一只水果，請(qǐng)用信號(hào)量實(shí)現(xiàn)他們之間的同步與互斥關(guān)系。答：S, S1, S2 :semaphore=1,0,0;Process Father:Begin:L1: P(S); Put Apple; V(S1)；End；Process Mother:Begin:L2: P(S); Put Orange; V(S2)；End；Process Son:Begin:L3: P(S2); Get Orange; V(S)；End；Process Daughter:Begin:L4: P(S1); Get Apple; V(S)；End；5. 用信號(hào)量解決“獨(dú)木橋”問(wèn)題：同一個(gè)方向行人可連續(xù)過(guò)橋，當(dāng)某一方向有人過(guò)橋時(shí)，另一個(gè)方向的行人必須等待；當(dāng)某一方向無(wú)人過(guò)橋時(shí)，另外方向的行人可以過(guò)橋。（1）本問(wèn)題中有哪些同步或互斥關(guān)系？（2）給出兩個(gè)方向任一行人通過(guò)該獨(dú)木橋的同步算法。答：將獨(dú)木橋的兩個(gè)方向分別標(biāo)記為A和B；并用整形變量countA和countB分別表示A、B方向上已在獨(dú)木橋上的行人數(shù)，初值為0；再設(shè)置三個(gè)初值都1的互斥信號(hào)量：SA用來(lái)實(shí)現(xiàn)對(duì)countA的互斥訪問(wèn)，SB用來(lái)實(shí)現(xiàn)對(duì)countB的互斥訪問(wèn)，mutex用來(lái)實(shí)現(xiàn)兩個(gè)方向的行人對(duì)獨(dú)木橋的互斥使用。則具體描述如下：VarSA,SB,mutex:semaphore:=1,1,1;CountA,countB:integer:=0,0:beginparbeginprocessA:beginwait(SA);if(countA=0)thenwait(mutex);countA:=countA+1;signal(SA);過(guò)獨(dú)木橋；wait(SA);countA:=countA-1;if(countA=0)thensignal(mutex);signa(SA);endprocessB:beginwait(SB);if(countB=0)thenwait(mutex);countB:=countB+1;signal(SB);過(guò)獨(dú)木橋；wait(SB);countB:=countB-1;if(countB=0)thensignal(mutex);signa(SB);endparendend6. （選做）設(shè)有兩個(gè)生產(chǎn)者進(jìn)程A、B和一個(gè)銷(xiāo)售者進(jìn)程C，他們共享一個(gè)無(wú)限大的倉(cāng)庫(kù)，生產(chǎn)者每次循環(huán)生產(chǎn)一個(gè)產(chǎn)品，然后入庫(kù)供銷(xiāo)售者銷(xiāo)售；銷(xiāo)售者每次循環(huán)從倉(cāng)庫(kù)中取出一個(gè)產(chǎn)品銷(xiāo)售。如果不允許同時(shí)入庫(kù)，也不允