操作系統(tǒng)習(xí)題分析課件

《操作系統(tǒng)》習(xí)題分析《操作系統(tǒng)》習(xí)題分析1總問題概念要清楚、定義要準確敘述要清楚、具體解題過程要詳細有關(guān)PV操作的題必須編寫程序，給出算法總問題概念要清楚、定義要準確2第1章補充作業(yè)1、設(shè)在內(nèi)存中有三道程序A、B和C，并按A、B、C的優(yōu)先次序運行，其內(nèi)部計算和I/O操作的時間如圖1所示。若處理機調(diào)度程序每次進行程序狀態(tài)轉(zhuǎn)換的時間為2ms，請畫出多道程序系統(tǒng)中在處理機調(diào)度程序管理下各程序狀態(tài)轉(zhuǎn)換的時間關(guān)系圖，并計算出完成這三道程序共花多少時間？比單道運行節(jié)省了多少時間？圖1各程序內(nèi)部計算和I/O操作的時間

第1章補充作業(yè)1、設(shè)在內(nèi)存中有三道程序A、B和C，并按A、3圖2各程序執(zhí)行與狀態(tài)轉(zhuǎn)換的時間關(guān)系圖解：多道程序系統(tǒng)中，在處理機調(diào)度程序管理下各程序狀態(tài)轉(zhuǎn)換的時間關(guān)系圖如圖2所示。單道系統(tǒng)中，三道程序共運行的時間為：T=60+2+30+2+40+2+50+2+20+2+50+2+70+2+50+2+40+2+30+2+20+2=482多道運行比單道運行節(jié)省時間為：482－306=176圖2各程序執(zhí)行與狀態(tài)轉(zhuǎn)換的時間關(guān)系圖解：多4第3章進程管理教材p832、6、7、8、9、10、11、13、14、15第3章進程管理教材p835第3章進程管理1.設(shè)有三個并發(fā)進程R、M、P，它們共享一個緩沖區(qū)。R負責(zé)從輸入設(shè)備讀信息，每讀一個記錄后，就把它存放在緩沖區(qū)中；M在緩沖區(qū)中加工讀入的記錄；P把加工后的記錄打印輸出。讀入的記錄經(jīng)加工輸出后，緩沖區(qū)又可存放下一個記錄。試寫出它們能正確執(zhí)行的程序。緩沖區(qū)輸入進程R打印進程P處理進程M第3章進程管理1.設(shè)有三個并發(fā)進程R、M、P，它們共63.6進程同步緩沖區(qū)計算進程PC打印進程PP計算進程PC

：反復(fù)地把每次計算結(jié)果放入緩沖區(qū)Buf中打印進程PP

：將計算進程每次放入緩沖區(qū)Buf中的數(shù)據(jù)取出，通過打印機打印輸出緩沖區(qū)Buf

：一次只可放一個數(shù)據(jù)例，共享一個緩沖區(qū)的合作進程3.6進程同步緩沖區(qū)計算進程PC打印進程PP計算進程PC7BeginSc,Sp:semaphore;Sp=0;/*信號量Sp，表示緩沖區(qū)Buf

是否存放計算結(jié)果*/Sc=1;/*信號量Sc，表示緩沖區(qū)Buf是否為空*/CobeginPc:While(計算未結(jié)束);/*計算進程*/{計算；P(Sc);/*緩沖區(qū)是否為空？若非空，則等待*/Buf←計算結(jié)果；V(Sp);}Pp:While(打印未完成);/*打印進程*/{P(Sp);/*緩沖區(qū)是否為數(shù)據(jù)？若無，則等待*/從緩沖區(qū)Buf取數(shù)據(jù)；V(Sc);打印數(shù)據(jù)；}CoendEndBegin8分析緩沖區(qū)是臨界資源，必須互斥訪問信號量empty：表示緩沖區(qū)是否為空，初值為1信號量Sr：進程R是否已輸入信息，初值Sr=0信號量Sm：進程M是否已加工信息，初值Sm=0分析緩沖區(qū)是臨界資源，必須互斥訪問9beginempty,Sr,Sm,Sp:semaphoreempty:=1;Sr:=0;Sm:=0;CobeginPr:Repeat從輸入設(shè)備讀一個記錄；P(empty);將記錄存入緩沖區(qū)；V(Sr);UntilfalsePm:RepeatP(Sr);在緩沖區(qū)中加工記錄；V(Sm);Untilfalsebeginempty,Sr,Sm,Sp:sem10

Pp:RepeatP(Sm);從緩沖區(qū)取出一個記錄；V(empty);打印記錄；UntilfalseCoendendPp:Repeat11第3章進程管理2.有一閱覽室，讀者進入時必須先在一張登記表上進行登記。該表為每一座位列出一個表目，包括座號、姓名。讀者離開時撤消登記信息。閱覽室有100個座位，試問：（1）為描述讀者的動作，應(yīng)編寫幾個程序，應(yīng)該設(shè)置幾個進程？進程和程序之間的對應(yīng)關(guān)系如何？（2）試用P、V操作描述這些進程間的同步算法。第3章進程管理2.有一閱覽室，讀者進入時必須先在一張登記12分析讀者動作：登記、讀書、撤消座位總數(shù)：100登記/撤消都需要在登記表修改信息，一次只能有一個讀者對登記表進行訪問登記表是臨界資源，必須互斥訪問一個讀者一個進程信號量的設(shè)置

S：用于讀者互斥訪問（登記/撤消）登記表，初值為1Sn：表示空座位數(shù)，初值為100每個座位設(shè)一個狀態(tài)位：滿/空（類似信箱通訊）分析讀者動作：登記、讀書、撤消13程序beginS,Sn:Semaphore;S:=1;Sn:=100;CobeginprocessReaderi(i=1,2,……,n）beginP(Sn);P(S);選擇標志為空的座位X；登記；置座位X的標志為滿；V(S);程序beginS,Sn:Semaphore;14

讀書；P(S)在登記表中查找座位X；撤消登記信息；置座位X的標志為空；V(Sn)V(S)endCoend討論并分析上述程序：采用指針形式（類似生產(chǎn)者-消費者問題）給每個座位設(shè)置一個信號量（類似哲學(xué)家就餐問題）讀書；15第3章補充題3.桌上有一只盤子，每次只能放入一個水果。爸爸專向盤中放蘋果，媽媽專向盤中放桔子，一個女兒專等吃盤中的蘋果，一個兒子專等吃盤中的桔子。試用P、V操作寫出他們能同步的程序。分析：信號量S：表示盤子是否為空，初值為1信號量So：表示盤中是否有桔子，初值為0信號量Sa：表示盤子是否有蘋果，初值為0第3章補充題3.桌上有一只盤子，每次只能放入一個水果。16程序beginS,Sa,So:semaphoreS=1;Sa=0;So=0;Cobeginfather:RepeatP(S);將蘋果放入盤中；V(Sa);Untilfalsemother:RepeatP(S);將桔子放入盤中；V(So);Untilfalse程序begin17

daughter:RepeatP(Sa);從盤中取出蘋果；V(S);吃蘋果；Untilfalseson:RepeatP(So);從盤中取出桔子；V(S);吃桔子；UntilfalseCoendenddaughter:Repeat18第3章補充題4、某大學(xué)軍訓(xùn)正在進行實彈練習(xí)?，F(xiàn)有一保管員負責(zé)管理槍支彈藥，有A、B兩組學(xué)生，A組學(xué)生每人都有一支槍，B組學(xué)生每人都備有足夠的子彈，任一學(xué)生只要有槍和子彈就可以進行實彈練習(xí)。在打靶場有一個可以放一只槍或一發(fā)子彈的盒子，當(dāng)盒中無物品時，保管員就可以任意放一支槍或一發(fā)子彈供學(xué)生取用。當(dāng)盒中有學(xué)生所需材料時，每次允許一個學(xué)生從中取出自己所需的材料，材料取走后，保管員再放一件材料。（1）試說明A、B兩組學(xué)生、保管員之間的相互制約關(guān)系。（2）應(yīng)設(shè)置哪些信號量，它們的初值是什么？（3）試用P、V寫出他們并發(fā)執(zhí)行的程序（類C或類PASCAL語言）。第3章補充題4、某大學(xué)軍訓(xùn)正在進行實彈練習(xí)?，F(xiàn)有一保管員19解答解：（1）這是一個生產(chǎn)者-消費者問題。A、B兩組學(xué)生是消費者，保管員是生產(chǎn)者，盒子是緩沖區(qū)，是一個臨界資源。它們之間的相互制約關(guān)系是：保管員與學(xué)生之間不僅要同步，而且保管員與A、B兩組學(xué)生之間、以及A、B兩組學(xué)生之間還要互斥。（2）設(shè)置3個信號量如下：公用信號量S：初值為1，表示盒子是否為空；私用信號量Sgun：表示盒子中是否有一支槍，初值為0；私用信號量Sbullet：表示盒子中是否有一發(fā)子彈，初值為0解答解：20程序如下：BeginS,Sgun,Sbullet:semaphoreS=1;/*表示盒子是否為空，初值為1*/Sgun=0;/*表示盒子中是否有一支槍，初值為0*/Sbullet=0;/*表示盒子中是否有一發(fā)子彈，初值為0*/CobeginKeeper：RepeatP(S);將一支槍或一發(fā)子彈放入盒子中；If放入的是一支槍ThenV(Sgun)ElseV(Sbullet)fiUntilfalse程序如下：Begin21StudentAi(i=1,2,…)RepeatP(Sbullet);從盒子中取出子彈；V(S);打靶；UntilfalseStudentBj(j=1,2,…)RepeatP(Sgun);從盒子中取出槍；V(S);打靶；UntilfalseCoendendStudentAi(i=1,2,…)225、假定系統(tǒng)中有五個進程{P0，P1，P2，P3，P4}和三種類型的資源{A，B，C}，每種資源的數(shù)量分別為10，5，7，在T時刻的資源分配情況如表所示。

（1）T時刻系統(tǒng)是否為安全狀態(tài)，若是，請給出安全序列。

（2）如果進程P4此時提出資源申請（3，3，1），系統(tǒng)能否將資源分配給它？為什么？資源進程最大需求矩陣M分配矩陣RABCABCP0P1P2P3P4753322902222433010200302211002第3章補充題5、假定系統(tǒng)中有五個進程{P0，P1，P2，P3，P4}和三23解：（1）進程的最大資源需求數(shù)減去當(dāng)前進程已分配到的資源數(shù)就是進程仍需要的資源數(shù)。此時各進程的仍需資源數(shù)向量為進程仍需資源數(shù)QP0743P1122P2600P3011P4431解：進程仍需資源數(shù)QP07424已知：系統(tǒng)的可用資源向量為W=（10，5，7）已分配的資源向量為P=（7，2，5）則，系統(tǒng)的當(dāng)前剩余資源向量為S=（3，3，2）在T時刻系統(tǒng)存在如下進程執(zhí)行序列，可以使進程順利進行完畢，所以該狀態(tài)是安全的，安全序列為P1、P3、P0、P4、P2。具體如下：進程系統(tǒng)可用資源數(shù)SP1完成后：5，3，2P3完成后：7，4，3P0完成后：7，5，3P4完成后：7，5，5P2完成后：10，5，7已知：系統(tǒng)的可用資源向量為W=（10，5，7）進程系統(tǒng)可用25（2）如果進程P4此時提出資源申請（3，3，1），系統(tǒng)滿足進程P4的請求，則系統(tǒng)的可用資源數(shù)變?yōu)椋?，0，1）。而此時各進程的仍需資源數(shù)向量為：進程仍需資源數(shù)P0743P1122P2600P3011P4100這時系統(tǒng)的可用資源數(shù)（0，0，1）不能滿足任何一個進程，系統(tǒng)處于不安全狀態(tài)。因此，系統(tǒng)不能將資源分配給進程P4。（2）如果進程P4此時提出資源申請（3，3，1），系統(tǒng)滿足進26P833.10P62經(jīng)典生產(chǎn)者-消費者問題P833.10P62經(jīng)典生產(chǎn)者-消費者問題27經(jīng)典生產(chǎn)者—消費者問題設(shè)生產(chǎn)者進程和消費者進程是互相等效的，其中，各生產(chǎn)者進程使用過程deposit(data)，各消費者使用的過程remove(data)生產(chǎn)者-消費者問題是一個同步問題消費者想接收數(shù)據(jù)時，緩沖區(qū)中至少有一個單元是滿的生產(chǎn)者想發(fā)送數(shù)據(jù)時，緩沖區(qū)中至少有一個單元是空的生產(chǎn)者-消費者問題是一個互斥問題緩沖區(qū)是臨界資源經(jīng)典生產(chǎn)者—消費者問題設(shè)生產(chǎn)者進程和消費者進程是互相等效的，28經(jīng)典生產(chǎn)者—消費者問題設(shè)置信號量公用信號量mutex：保證生產(chǎn)者進程和消費者進程之間的互斥；初值為1，表示沒有進程進入臨界區(qū)私用信號量avail：生產(chǎn)者進程的私用信號量，表示可用緩沖區(qū)數(shù)，初值為n私用信號量full：消費者進程的私用信號量，表示產(chǎn)品數(shù)目，初值為0經(jīng)典生產(chǎn)者—消費者問題設(shè)置信號量29生產(chǎn)者—消費者進程描述生產(chǎn)者進程生產(chǎn)一種產(chǎn)品P(avail)P(mutex)產(chǎn)品送入緩沖區(qū)V(full)V(mutex)消費者進程P(full)P(mutex)從緩沖區(qū)取一產(chǎn)品V(avail)V(mutex)消耗該產(chǎn)品生產(chǎn)者—消費者進程描述生產(chǎn)者進程生產(chǎn)一種產(chǎn)品消費者進程P(f30操作系統(tǒng)習(xí)題分析課件31生產(chǎn)者指針P

消費者指針R

有界緩沖區(qū)初始狀態(tài)RP…

I12J……n為什么要互斥訪問緩沖區(qū)？…

I12J…中間狀態(tài)RP…n什么情況下，出現(xiàn)阻塞？生產(chǎn)者指針P消費者指針R有界緩沖區(qū)初始狀態(tài)32經(jīng)典生產(chǎn)者—消費者問題設(shè)置信號量公用信號量S：初值為1，表示沒有進程進入臨界區(qū)，用于實現(xiàn)進程互斥私用信號量S0：表示產(chǎn)品數(shù)目，初值為0私用信號量Sn：表示可用緩沖區(qū)數(shù)，初值為n經(jīng)典生產(chǎn)者—消費者問題設(shè)置信號量33生產(chǎn)者—消費者進程描述生產(chǎn)者進程生產(chǎn)一種產(chǎn)品P(Sn)P(S)產(chǎn)品送入緩沖區(qū)V(S0)V(S)消費者進程P(S0)P(S)從緩沖區(qū)取一產(chǎn)品V(Sn)V(S)消耗該產(chǎn)品生產(chǎn)者—消費者進程描述生產(chǎn)者進程生產(chǎn)一種產(chǎn)品消費者進程P(S34BeginB:array[0..n-1]ofinteger;P,R:integer;S,Sn,S0:semaphore;P:=R:=0;S:=1;Sn:=n;S0:=0;CobeginProcessProducei(i=1,2,…,m)BeginL1:produceaproductP(Sn);P(S);B[P]:=product;P:=(P+1)modn;V(S0);V(S);Begin35

gotoL1endProcessconsumerj(j=1,2,…,k)BeginL2:P(S0);P(S);takeaproductfromB[R];R:=(R+1)modn;V(Sn);V(S);consumegotoL2endCoendendgotoL136P833.10解：設(shè)互斥信號量mutex[n]為緩沖區(qū)的公用信號量，初始值為1。設(shè)信號量S1為生產(chǎn)者進程信號量，初始值為m。設(shè)信號量S2為消費者信號量，初始值為0。各生產(chǎn)者進程使用的過程Deposit(data)如下：Deposit(data) Begin P(S1) 選擇第n個空緩沖區(qū) P(mutex[n]) 送數(shù)據(jù)入第n個緩沖區(qū) V(S2)V(mutex[n])EndP833.10解：設(shè)互斥信號量mutex[n]為緩沖區(qū)的37各消費者進程使用的過程Remove(data)如下：Remove(data) Begin P(S2) 選擇一個已有數(shù)據(jù)的緩沖區(qū)kP(mutex[k]) 取出緩沖區(qū)k中的數(shù)據(jù) V(S1) V(mutex[k]) End各消費者進程使用的過程Remove(data)如下：38P833.11P61例P833.11P61例39P61例，設(shè)進程PA和PB通過緩沖區(qū)隊列傳遞數(shù)據(jù)(如圖3.14)。PA為發(fā)送進程，PB為接收進程。PA發(fā)送數(shù)據(jù)時調(diào)用發(fā)送過程deposit(data)，PB接收數(shù)據(jù)時調(diào)用過程remove(data)。且數(shù)據(jù)的發(fā)送和接收過程滿足如下條件：在PA至少送一塊數(shù)據(jù)入一個緩沖區(qū)之前，PB不可能從緩沖區(qū)中取出數(shù)據(jù)（假定數(shù)據(jù)塊長等于緩沖區(qū)長度）PA往緩沖隊列發(fā)送數(shù)據(jù)時，至少有一個緩沖區(qū)是空的由PA發(fā)送的數(shù)據(jù)塊在緩沖隊列中按先進先出(FIFO)方式排列描述發(fā)送進程deposit(data)和接收進程remove(data)圖3.14緩沖區(qū)隊列P833.11P61例，設(shè)進程PA和PB通過緩沖區(qū)隊列傳遞數(shù)據(jù)(如圖340解：由題可知，進程PA調(diào)用發(fā)送過程deposit(data)和進程PB調(diào)用過程remove(data)必須同步執(zhí)行，因此，設(shè)：Bufempty為進程PA的私用信號量，初值Bufempty=nBuffull為進程PB的私用信號量，初值Buffull=0則，過程deposit(data)和remove(data)描述如下：解：由題可知，進程PA調(diào)用發(fā)送過程deposit(data)41操作系統(tǒng)習(xí)題分析課件42操作系統(tǒng)習(xí)題分析課件43P833.11設(shè)：有兩個緩沖區(qū)隊列i=1、2，每個緩沖區(qū)隊列有n個緩沖區(qū)。buf[i](k)表示第i個緩沖隊列的第k個緩沖區(qū)bufempty[0]，buffull[1]為PA的私有信號量buffull[0]，buffempty[1]是PB的私有信號量bufempty[0]=bufempty[1]=nbuffull[0]=buffull[1]=0PA調(diào)用send(0,m)發(fā)送數(shù)據(jù)，receive(1,m)接收數(shù)據(jù)；PB調(diào)用send(1,m)發(fā)送數(shù)據(jù)，receive(0,m)接收數(shù)據(jù)；P833.11設(shè)：有兩個緩沖區(qū)隊列i=1、2，每個緩沖區(qū)44發(fā)送過程send(i,m)begin P(bufempty[i]) FIFO方式選擇一個空緩沖區(qū)k buf[i](k)=m buf[i](k)置滿標記 V(buffull[i])End發(fā)送過程45接收過程Receive(i,m)begin P(buffull[i]) FIFO方式選擇一個滿緩沖區(qū)k m=buf[i](k) buf[i](k)置空標記 V(bufempty[i])end接收過程46P843.13（參考p72例2）#include<stdio.h>Main(){ inti,r,P1,P2,fd[3]; charbuf[50],s[50]; pipe(fd); while((P1=fork())==-1); if(P1==0){ lockf(fd[1],1,0); sprintf(buf,”childprocessP1issendingmessages!\n”); printf(“childprocessP1!\n”); write(fd[1],buf,50); sleep(5); lockf(fd[1],0,0); exit(0); }P843.13（參考p72例2）#include<st47 Else{ while((P2=fork())==-1); if(P2==0){ lockf(fd[1],1,0); sprintf(buf,”childprocessP2issendingmessages!\n”); printf(“childprocessP2!\n”); write(fd[1],buf,50); sleep(5); lockf(fd[1],0,0); exit(0); } Else{48 Else{ while((P3=fork())==-1); if(P3==0){ lockf(fd[1],1,0); sprintf(buf,”childprocessP3issendingmessages!\n”); printf(“childprocessP3!\n”); write(fd[1],buf,50); sleep(5); lockf(fd[1],0,0); exit(0); } Else{49 Wait(0); If(r=read(fd[0],s,50)==-1) Printf(“can’treadpipe\n”); Elseprintf(“%s\n”,s); Wait(0); If(r=read(fd[0],s,50)==-1) Printf(“can’treadpipe\n”); Elseprintf(“%s\n”,s);Wait(0); If(r=read(fd[0],s,50)==-1) Printf(“can’treadpipe\n”); Elseprintf(“%s\n”,s); Exit(0); } }} Wait(0);503.14哲學(xué)家就餐問題(習(xí)題p15)

有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子每個哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉為了吃通心粉，每個哲學(xué)家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子3.14哲學(xué)家就餐問題(習(xí)題p15) 有五個哲學(xué)51Repeat

思考；取fork[i];/*取左邊筷子*/取fork[(i+1)mod5]；/*取右邊筷子*/進食；放fork[i];/*放左邊筷子*/放fork[(i+1)mod5]；/*放右邊筷子*/Untilfalse;Repeat52方法：為每根筷子單獨設(shè)置一個信號量，取筷子執(zhí)行P操作，放筷子執(zhí)行V操作Varchopstick:array[0..4]ofsemaphore;Fori=0to4chopstick[i]=1NextiPi:Repeatthink;P(chopstick[i]);P(chopstick[i+1mod5]);eat;V(chopstick[i]);V(chopstick[i+1mod5]);Untilfalse;方法：為每根筷子單獨設(shè)置一個信號量，取筷子執(zhí)行P操作，放筷子53存在問題上述方法簡單，并能保證任何時候均不存在兩個相鄰的哲學(xué)家同時在吃飯。但由于進程的并發(fā)執(zhí)行與CPU的調(diào)度問題，可能使得每個哲學(xué)家都只能拿到了自己左邊的筷子，那么這一組進程就會發(fā)生死鎖現(xiàn)象。存在問題上述方法簡單，并能保證任何時候均不存54

為防止死鎖發(fā)生可采取的措施：最多允許4個哲學(xué)家同時坐在桌子周圍僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才允許他拿筷子（）給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進食，并且一次拿到兩只筷子，否則不拿 為防止死鎖發(fā)生可采取的措施：55state:array[0..4]of(思考，饑餓，進食）；ph:array[0..4]ofsemaphore;mutex:semaphore;i:0..4;state:array[0..4]of56Proceduretest(i:=0…4);beginif(state[i]=饑餓)And(state[(i-1)mod5]<>進食)And(state[(i+1)mod5]<>進食)thenstate[i]=進食V(ph[i])fiendProceduretest(i:=0…4);57Procedurephilosopher(i:0～4)BeginRepeat

思考；state[i]:=饑餓；P(mutex);test(i);V(mutex);P(ph[i]);

拿左筷子；拿右筷子；進食；放左筷子；放右筷子；Procedurephilosopher(i:0～4)58P(mutex)state[i]:=思考；test([i-1]mod5);tset([i+1]mod5);V(mutex);untilfalesEndstate[I]=思考ph[I]=0mutex=1P(mutex)59第4章處理機調(diào)度P108習(xí)題2、4、5、6第4章處理機調(diào)度P108習(xí)題2、4、5、660第4章處理機調(diào)度4.6假設(shè)有4道作業(yè)，它們的提交時刻和執(zhí)行時間由下表給出：作業(yè)號提交時刻/小時執(zhí)行時間/小時110:002210:201310:400.5410:500.3計算在單道程序環(huán)境下，采用先來先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，并指出它們的調(diào)度順序。第4章處理機調(diào)度4.6假設(shè)有4道作業(yè)，它們的提交時刻611.先來先服務(wù)(FCFS)調(diào)度算法將用戶作業(yè)和就緒進程按提交順序或變?yōu)榫途w狀態(tài)的先后排隊，按照先來先服務(wù)的方式調(diào)度

對于作業(yè)調(diào)度，該算法就是從后備作業(yè)隊列中（按進入的時間順序排隊）選擇隊首一個或幾個作業(yè)，調(diào)入內(nèi)存，創(chuàng)建進程，放入就緒隊列對于進程調(diào)度，該算法就是從就緒隊列中選擇一個最先進入隊列的進程，將CPU分配于它表面上，F(xiàn)CFS算法是公平的。但對于執(zhí)行時間較短的作業(yè)或進程，當(dāng)它們處于某些執(zhí)行時間很長的作業(yè)或進程之后到達，則它們將等待很長的時間1.先來先服務(wù)(FCFS)調(diào)度算法將用戶作業(yè)和就緒進程按提交62

采用先來先服務(wù)調(diào)度算法時的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間如下表所示，計算可得：平均周轉(zhuǎn)時間為：T=157m=2.6167h平均帶權(quán)周轉(zhuǎn)時間為：W=4.8075它們的調(diào)度順序是：作業(yè)1→作業(yè)2→作業(yè)3→作業(yè)4作業(yè)號提交時間Tin執(zhí)行時間Tr開始時間TS結(jié)束時間Tc周轉(zhuǎn)時間T(m)帶權(quán)周轉(zhuǎn)時間W110:002(120)10:0012:00T1=120(2h)WA=1210:201(60)12:0013:00T2=160(2.67h)WB=2.67310:400.5(30)13:0013:30T3=170(2.83h)WC=5.67410:500.3(18)13:3013:48T4=178(2.97h)WD=9.89平均T=157m=2.6167hW=4.8075

先來先服務(wù)算法（FCFS）

采用先來先服務(wù)調(diào)度算法時的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時63最短作業(yè)優(yōu)先法(SJF)方法：選擇那些估計需要執(zhí)行時間最短的作業(yè)投入執(zhí)行優(yōu)點：系統(tǒng)在同一時間內(nèi)處理的作業(yè)個數(shù)最多，吞吐量大于其他調(diào)度方式問題：SJF需要事先知道或至少需要估計每個作業(yè)所需的處理機時間只要不斷的有短作業(yè)進入系統(tǒng)，就有可能使長作業(yè)長期得不到運行而“餓死”SJF偏向短作業(yè)，不利于分時系統(tǒng)（由于不可搶占性）最短作業(yè)優(yōu)先法(SJF)方法：選擇那些估計需要執(zhí)行時間最短的64

采用最短作業(yè)優(yōu)先法時的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間如下表所示（情況1：將作業(yè)收集成一批再處理），計算可得：平均周轉(zhuǎn)時間為：T=123m=2.05h平均帶權(quán)周轉(zhuǎn)時間為：W=1.8875它們的調(diào)度順序是：作業(yè)4→作業(yè)3→作業(yè)2→作業(yè)1作業(yè)號提交時間Tin執(zhí)行時間Tr開始時間TS結(jié)束時間Tc周轉(zhuǎn)時間T(m)帶權(quán)周轉(zhuǎn)時間W110:002(120)12:3814:38T1=278W1=2.3167210:201(60)11:3812:38T2=138W2=2.3310:400.5(30)11:0811:38T3=58W3=1.93410:500.3(18)10:5011:08T4=18W4=1平均T=123m=2.05hW=1.8875最短作業(yè)優(yōu)先法（SJF）

采用最短作業(yè)優(yōu)先法時的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間如65

采用最短作業(yè)優(yōu)先法時的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間如下表所示（情況2：有作業(yè)就執(zhí)行），計算可得：平均周轉(zhuǎn)時間為：T=123m=2.05h平均帶權(quán)周轉(zhuǎn)時間為：W=1.8875它們的調(diào)度順序是：作業(yè)1→作業(yè)4→作業(yè)3→作業(yè)2作業(yè)號提交時間Tin執(zhí)行時間Tr開始時間TS結(jié)束時間Tc周轉(zhuǎn)時間T(m)帶權(quán)周轉(zhuǎn)時間W110:002(120)10:0012:00T1=120(2h)W1=1210:201(60)12:4813:48T2=208(3.47h)W2=3.467310:400.5(30)12:1812:48T3=128(2.13h)W3=4.267410:500.3(18)12:0012:18T4=88(1.46h)W4=4.889平均T=136m=2.265hW=3.4057最短作業(yè)優(yōu)先法（SJF）

采用最短作業(yè)優(yōu)先法時的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間如66第5章存儲管理p144習(xí)題2、3、4、6、9、10、11、15、16、19第5章存儲管理p14467補充作業(yè)1、存儲管理系統(tǒng)中，假定某進程分得三個內(nèi)存塊，其頁面走向為以下序列：5、0、1、2、1、3、2、4、2、3、0、3、2、1、2、0、1、5、0、1試用先進先出（FIFO）、最近最久未使用（LRU）和理想置換算法分別計算程序訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率。補充作業(yè)1、存儲管理系統(tǒng)中，假定某進程分得三個內(nèi)存塊，其頁面68走向50121324230321201501頁150121324230321201501頁25012132423032120150頁3500213342203312015缺頁××××√×√×√√×√√×√×√×√√走向50121324230321201501頁150122334440021111500頁25011223334402222155頁3500112223340000211缺頁××××√×√×√√×√××√√√××√FIFO算法的缺頁中斷次數(shù)F=11，缺頁率f=11/20=55%

LRU算法的缺頁中斷次數(shù)F=10，缺頁率f=10/20=50%

走向50121324230321201501頁150121369走向50121324230321201501頁150122334440001111555頁25011223333330000111頁3500002222222222000缺頁√√√√√√√√√√√理想置換算法的缺頁中斷次數(shù)F=9缺頁率f=9/20=45%

走向50121324230321201501頁150122370補充題2、某系統(tǒng)采用請求分頁存儲管理，頁長為2KB（即2048B），某作業(yè)的頁表如下所示。請簡述執(zhí)行指令60LOADA,5168的地址變換過程。358補充題2、某系統(tǒng)采用請求分頁存儲管理，頁長為2KB（即2071解：執(zhí)行指令60LOADA,5168的地址變換過程為：（1）取指令：首先根據(jù)該指令的邏輯地址60，得到相應(yīng)的邏輯頁式地址為（0，60），然后查頁表得到其物理塊為3，計算出物理地址為：3×2048+60＝6204所以，從6204單元中取出指令執(zhí)行。（2）取數(shù)據(jù)：首先根據(jù)數(shù)據(jù)的邏輯地址5168，得到相應(yīng)的邏輯頁式地址為（2，1072），然后查頁表得到其物理塊為8，計算出物理地址為：8×2048+1072＝17456所以，從17456單元中取出數(shù)據(jù)，放入寄存器A中。具體來說，該指令的執(zhí)行過程是：首先從內(nèi)存的6204單元取指令，然后再從17456單元取數(shù)據(jù)，放入寄存器A中。解：執(zhí)行指令60LOADA