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

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

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

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

：一次只可放一個(gè)數(shù)據(jù)例，共享一個(gè)緩沖區(qū)的合作進(jìn)程Begin

Sc,Sp:semaphore;Sp=0;/*信號(hào)量Sp，表示緩沖區(qū)Buf

是否存放計(jì)算結(jié)果*/Sc=1;/*信號(hào)量Sc，表示緩沖區(qū)Buf

是否為空*/CobeginPc:While(計(jì)算未結(jié)束);/*計(jì)算進(jìn)程*/{計(jì)算；

P(Sc);/*緩沖區(qū)是否為空？若非空，則等待*/

Buf←計(jì)算結(jié)果；

V(Sp);}Pp:While(打印未完成);/*打印進(jìn)程*/{P(Sp);/*緩沖區(qū)是否為數(shù)據(jù)？若無，則等待*/

從緩沖區(qū)Buf取數(shù)據(jù)；

V(Sc);打印數(shù)據(jù)；

}

CoendEnd分析緩沖區(qū)是臨界資源，必須互斥訪問信號(hào)量empty：表示緩沖區(qū)是否為空，初值為1信號(hào)量Sr：進(jìn)程R是否已輸入信息，初值Sr=0信號(hào)量Sm：進(jìn)程M是否已加工信息，初值Sm=0beginempty,Sr,Sm,Sp:semaphoreempty:=1;Sr:=0;Sm:=0;

CobeginPr:Repeat

從輸入設(shè)備讀一個(gè)記錄；

P(empty);

將記錄存入緩沖區(qū)；

V(Sr);UntilfalsePm:Repeat

P(Sr);

在緩沖區(qū)中加工記錄；

V(Sm);Untilfalse

Pp:Repeat

P(Sm);

從緩沖區(qū)取出一個(gè)記錄；

V(empty);

打印記錄；

Untilfalse

Coendend第3章進(jìn)程管理2.有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上進(jìn)行登記。該表為每一座位列出一個(gè)表目，包括座號(hào)、姓名。讀者離開時(shí)撤消登記信息。閱覽室有100個(gè)座位，試問：（1）為描述讀者的動(dòng)作，應(yīng)編寫幾個(gè)程序，應(yīng)該設(shè)置幾個(gè)進(jìn)程？進(jìn)程和程序之間的對(duì)應(yīng)關(guān)系如何？（2）試用P、V操作描述這些進(jìn)程間的同步算法。分析讀者動(dòng)作：登記、讀書、撤消座位總數(shù)：100登記/撤消都需要在登記表修改信息，一次只能有一個(gè)讀者對(duì)登記表進(jìn)行訪問登記表是臨界資源，必須互斥訪問一個(gè)讀者一個(gè)進(jìn)程信號(hào)量的設(shè)置

S：用于讀者互斥訪問（登記/撤消）登記表，初值為1

Sn：表示空座位數(shù)，初值為100每個(gè)座位設(shè)一個(gè)狀態(tài)位：滿/空（類似信箱通訊）程序beginS,Sn:Semaphore;S:=1;Sn:=100;

CobeginprocessReaderi(i=1,2,……,n）

begin

P(Sn);P(S);

選擇標(biāo)志為空的座位X；登記；置座位X的標(biāo)志為滿；

V(S);

讀書；

P(S)

在登記表中查找座位X；撤消登記信息；

置座位X的標(biāo)志為空；

V(Sn)V(S)end

Coend討論并分析上述程序：采用指針形式（類似生產(chǎn)者-消費(fèi)者問題）給每個(gè)座位設(shè)置一個(gè)信號(hào)量（類似哲學(xué)家就餐問題）第3章補(bǔ)充題3.桌上有一只盤子，每次只能放入一個(gè)水果。爸爸專向盤中放蘋果，媽媽專向盤中放桔子，一個(gè)女兒專等吃盤中的蘋果，一個(gè)兒子專等吃盤中的桔子。試用P、V操作寫出他們能同步的程序。分析：信號(hào)量S：表示盤子是否為空，初值為1信號(hào)量So：表示盤中是否有桔子，初值為0信號(hào)量Sa：表示盤子是否有蘋果，初值為0程序beginS,Sa,So:semaphoreS=1;Sa=0;So=0;

Cobeginfather:RepeatP(S);

將蘋果放入盤中；

V(Sa);Untilfalsemother:RepeatP(S);

將桔子放入盤中；

V(So);Untilfalse

daughter:RepeatP(Sa);

從盤中取出蘋果；

V(S);

吃蘋果；

Untilfalseson:RepeatP(So);

從盤中取出桔子；

V(S);

吃桔子；

Untilfalse

Coendend第3章補(bǔ)充題4、某大學(xué)軍訓(xùn)正在進(jìn)行實(shí)彈練習(xí)?，F(xiàn)有一保管員負(fù)責(zé)管理槍支彈藥，有A、B兩組學(xué)生，A組學(xué)生每人都有一支槍，B組學(xué)生每人都備有足夠的子彈，任一學(xué)生只要有槍和子彈就可以進(jìn)行實(shí)彈練習(xí)。在打靶場(chǎng)有一個(gè)可以放一只槍或一發(fā)子彈的盒子，當(dāng)盒中無物品時(shí)，保管員就可以任意放一支槍或一發(fā)子彈供學(xué)生取用。當(dāng)盒中有學(xué)生所需材料時(shí)，每次允許一個(gè)學(xué)生從中取出自己所需的材料，材料取走后，保管員再放一件材料。（1）試說明A、B兩組學(xué)生、保管員之間的相互制約關(guān)系。（2）應(yīng)設(shè)置哪些信號(hào)量，它們的初值是什么？（3）試用P、V寫出他們并發(fā)執(zhí)行的程序（類C或類PASCAL語言）。解答解：（1）這是一個(gè)生產(chǎn)者-消費(fèi)者問題。

A、B兩組學(xué)生是消費(fèi)者，保管員是生產(chǎn)者，盒子是緩沖區(qū)，是一個(gè)臨界資源。它們之間的相互制約關(guān)系是：保管員與學(xué)生之間不僅要同步，而且保管員與A、B兩組學(xué)生之間、以及A、B兩組學(xué)生之間還要互斥。（2）設(shè)置3個(gè)信號(hào)量如下：公用信號(hào)量S：初值為1，表示盒子是否為空；私用信號(hào)量Sgun：表示盒子中是否有一支槍，初值為0；私用信號(hào)量Sbullet：表示盒子中是否有一發(fā)子彈，初值為0程序如下：BeginS,Sgun,Sbullet:semaphoreS=1;/*表示盒子是否為空，初值為1*/

Sgun=0;/*表示盒子中是否有一支槍，初值為0*/

Sbullet=0;/*表示盒子中是否有一發(fā)子彈，初值為0*/

CobeginKeeper：

RepeatP(S);

將一支槍或一發(fā)子彈放入盒子中；

If放入的是一支槍

Then

V(Sgun)Else

V(Sbullet)

fiUntilfalse

StudentAi(i=1,2,…)Repeat

P(Sbullet);

從盒子中取出子彈；

V(S);

打靶；

UntilfalseStudentBj(j=1,2,…)Repeat

P(Sgun);

從盒子中取出槍；

V(S);

打靶；

Untilfalse

Coendend5、假定系統(tǒng)中有五個(gè)進(jìn)程{P0，P1，P2，P3，P4}和三種類型的資源{A，B，C}，每種資源的數(shù)量分別為10，5，7，在T時(shí)刻的資源分配情況如表所示。

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

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

0生產(chǎn)者—消費(fèi)者進(jìn)程描述生產(chǎn)者進(jìn)程生產(chǎn)一種產(chǎn)品P(avail)P(mutex)產(chǎn)品送入緩沖區(qū)V(full)V(mutex)消費(fèi)者進(jìn)程P(full)P(mutex)從緩沖區(qū)取一產(chǎn)品V(avail)V(mutex)消耗該產(chǎn)品生產(chǎn)者指針P

消費(fèi)者指針R

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

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

I12J…中間狀態(tài)RP…n什么情況下，出現(xiàn)阻塞？經(jīng)典生產(chǎn)者—消費(fèi)者問題設(shè)置信號(hào)量公用信號(hào)量S：初值為1，表示沒有進(jìn)程進(jìn)入臨界區(qū)，用于實(shí)現(xiàn)進(jìn)程互斥私用信號(hào)量S0：表示產(chǎn)品數(shù)目，初值為0私用信號(hào)量Sn：表示可用緩沖區(qū)數(shù)，初值為n生產(chǎn)者—消費(fèi)者進(jìn)程描述生產(chǎn)者進(jìn)程生產(chǎn)一種產(chǎn)品P(Sn)P(S)產(chǎn)品送入緩沖區(qū)V(S0)V(S)消費(fèi)者進(jìn)程P(S0)P(S)從緩沖區(qū)取一產(chǎn)品V(Sn)V(S)消耗該產(chǎn)品BeginB: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:produceaproduct

P(Sn);P(S);B[P]:=product;P:=(P+1)modn;V(S0);V(S);

gotoL1endProcessconsumerj(j=1,2,…,k)BeginL2:P(S0);P(S);takeaproductfromB[R];R:=(R+1)modn;

V(Sn);V(S);consumegotoL2end

CoendendP833.10解：設(shè)互斥信號(hào)量mutex[n]為緩沖區(qū)的公用信號(hào)量，初始值為1。設(shè)信號(hào)量S1為生產(chǎn)者進(jìn)程信號(hào)量，初始值為m。設(shè)信號(hào)量S2為消費(fèi)者信號(hào)量，初始值為0。各生產(chǎn)者進(jìn)程使用的過程Deposit(data)如下：Deposit(data) Begin P(S1)

選擇第n個(gè)空緩沖區(qū)

P(mutex[n])

送數(shù)據(jù)入第n個(gè)緩沖區(qū)

V(S2)

V(mutex[n])End各消費(fèi)者進(jìn)程使用的過程Remove(data)如下：Remove(data) Begin P(S2)

選擇一個(gè)已有數(shù)據(jù)的緩沖區(qū)k

P(mutex[k])

取出緩沖區(qū)k中的數(shù)據(jù)

V(S1)

V(mutex[k]) EndP833.11P61例P61例，設(shè)進(jìn)程PA和PB通過緩沖區(qū)隊(duì)列傳遞數(shù)據(jù)(如圖3.14)。PA為發(fā)送進(jìn)程，PB為接收進(jìn)程。PA發(fā)送數(shù)據(jù)時(shí)調(diào)用發(fā)送過程deposit(data)，PB接收數(shù)據(jù)時(shí)調(diào)用過程remove(data)。且數(shù)據(jù)的發(fā)送和接收過程滿足如下條件：在PA至少送一塊數(shù)據(jù)入一個(gè)緩沖區(qū)之前，PB不可能從緩沖區(qū)中取出數(shù)據(jù)（假定數(shù)據(jù)塊長等于緩沖區(qū)長度）PA往緩沖隊(duì)列發(fā)送數(shù)據(jù)時(shí)，至少有一個(gè)緩沖區(qū)是空的由PA發(fā)送的數(shù)據(jù)塊在緩沖隊(duì)列中按先進(jìn)先出(FIFO)方式排列描述發(fā)送進(jìn)程deposit(data)和接收進(jìn)程remove(data)圖3.14緩沖區(qū)隊(duì)列P833.11解：由題可知，進(jìn)程PA調(diào)用發(fā)送過程deposit(data)和進(jìn)程PB調(diào)用過程remove(data)必須同步執(zhí)行，因此，設(shè)：Bufempty為進(jìn)程PA的私用信號(hào)量，初值Bufempty=nBuffull為進(jìn)程PB的私用信號(hào)量，初值Buffull=0

則，過程deposit(data)和remove(data)描述如下：P833.11設(shè)：有兩個(gè)緩沖區(qū)隊(duì)列i=1、2，每個(gè)緩沖區(qū)隊(duì)列有n個(gè)緩沖區(qū)。

buf[i](k)表示第i個(gè)緩沖隊(duì)列的第k個(gè)緩沖區(qū)bufempty[0]，buffull[1]為PA的私有信號(hào)量buffull[0]，buffempty[1]是PB的私有信號(hào)量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ù)；發(fā)送過程send(i,m)begin

P(bufempty[i]) FIFO方式選擇一個(gè)空緩沖區(qū)k

buf[i](k)=m

buf[i](k)置滿標(biāo)記

V(buffull[i])End接收過程Receive(i,m)begin

P(buffull[i]) FIFO方式選擇一個(gè)滿緩沖區(qū)k m=buf[i](k)

buf[i](k)置空標(biāo)記

V(bufempty[i])endP843.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); }

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{ 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); }

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); } }}3.14哲學(xué)家就餐問題(習(xí)題p15)

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

思考；取fork[i];/*取左邊筷子*/

取fork[(i+1)mod5]；/*取右邊筷子*/

進(jìn)食；

放fork[i];/*放左邊筷子*/

放fork[(i+1)mod5]；/*放右邊筷子*/Untilfalse;方法：為每根筷子單獨(dú)設(shè)置一個(gè)信號(hào)量，取筷子執(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í)候均不存在兩個(gè)相鄰的哲學(xué)家同時(shí)在吃飯。但由于進(jìn)程的并發(fā)執(zhí)行與CPU的調(diào)度問題，可能使得每個(gè)哲學(xué)家都只能拿到了自己左邊的筷子，那么這一組進(jìn)程就會(huì)發(fā)生死鎖現(xiàn)象。

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

V(ph[i])

fiendProcedurephilosopher(i:0～4)BeginRepeat

思考；

state[i]:=饑餓；

P(mutex);test(i);

V(mutex);P(ph[i]);

拿左筷子；拿右筷子；進(jìn)食；放左筷子；放右筷子；

P(mutex)state[i]:=思考；

test([i-1]mod5);tset([i+1]mod5);

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

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

采用先來先服務(wù)調(diào)度算法時(shí)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間如下表所示，計(jì)算可得：平均周轉(zhuǎn)時(shí)間為：T=157m=2.6167h平均帶權(quán)周轉(zhuǎn)時(shí)間為：W=4.8075它們的調(diào)度順序是：作業(yè)1→作業(yè)2→作業(yè)3→作業(yè)4作業(yè)號(hào)提交時(shí)間

Tin執(zhí)行時(shí)間Tr開始時(shí)間TS結(jié)束時(shí)間Tc周轉(zhuǎn)時(shí)間T(m)帶權(quán)周轉(zhuǎn)時(shí)間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）

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

采用最短作業(yè)優(yōu)先法時(shí)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間如下表所示（情況1：將作業(yè)收集成一批再處理），計(jì)算可得：平均周轉(zhuǎn)時(shí)間為：T=123m=2.05h平均帶權(quán)周轉(zhuǎn)時(shí)間為：W=1.8875它們的調(diào)度順序是：作業(yè)4→作業(yè)3→作業(yè)2→作業(yè)1作業(yè)號(hào)提交時(shí)間

Tin執(zhí)行時(shí)間Tr開始時(shí)間TS結(jié)束時(shí)間Tc周轉(zhuǎn)時(shí)間T(m)帶權(quán)周轉(zhuǎn)時(shí)間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)先法時(shí)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間如下表所示（情況2：有作業(yè)就執(zhí)行），計(jì)算可得：平均周轉(zhuǎn)時(shí)間為：T=123m=2.05h平均帶權(quán)周轉(zhuǎn)時(shí)間為：W=1.8875它們的調(diào)度順序是：作業(yè)1→作業(yè)4→作業(yè)3→作業(yè)2作業(yè)號(hào)提交時(shí)間

Tin執(zhí)行時(shí)間Tr開始時(shí)間TS結(jié)束時(shí)間Tc周轉(zhuǎn)時(shí)間T(m)帶權(quán)周轉(zhuǎn)時(shí)間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）

第5章存儲(chǔ)管理p144習(xí)題2、3、4、6、9、10、11、15、16、19補(bǔ)充作業(yè)1、存儲(chǔ)管理系統(tǒng)中，假定某進(jìn)程分得三個(gè)內(nèi)存塊，其頁面走向?yàn)橐韵滦蛄校?/p>

5、0、1、2、1、3、2、4、2、3、0、3、2、1、2、0、1、5、0、1

試用先進(jìn)先出（FIFO）、最近最久未使用（LRU）和理想置換算法分別計(jì)算程序訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率。走向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頁150122334440001111555頁25011223333330000111頁3500002222222222000缺頁√√√√√√√√√√√理想置換算法的缺頁中斷次數(shù)F=9

缺頁率f=9/20=45%

補(bǔ)充題2、某系統(tǒng)采用請(qǐng)求分頁存儲(chǔ)管理，頁長為2KB（即2048B），某作業(yè)的頁表如下所示。請(qǐng)簡述執(zhí)行指令60LOADA,5168的地址變換過程。358解：執(zhí)行指令60LOADA,5168的地址變換過程為：（1）取指令：首先根據(jù)該指令的邏輯地址60，得到相應(yīng)的邏輯頁式地址為（0，60），然后查頁表得到其物理塊為3，計(jì)算出物理地址為：

3×2048+60＝6204

所以，從6204單元中取出指令執(zhí)行。（2）取數(shù)據(jù)：首先根據(jù)數(shù)據(jù)的邏輯地址5168，得到相應(yīng)的邏輯頁式地址為（2，1072），然后查頁表得到其物理塊為8，計(jì)算出物理地址為：

8×2048+1072＝17456

所以，從17456單元中取出數(shù)據(jù)，放入寄存器A中。具體來說，該指令的執(zhí)行過程是：首先從內(nèi)存的6204