操作系統(tǒng)習(xí)題分析.ppt

操作系統(tǒng)習(xí)題分析,總問(wèn)題,概念要清楚、定義要準(zhǔn)確 敘述要清楚、具體 解題過(guò)程要詳細(xì) 有關(guān)PV操作的題必須編寫(xiě)程序，給出算法,第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)畫(huà)出多道程序系統(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í)間為：482306=176,第3章 進(jìn)程管理,教材 p83 2、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è)記錄。試寫(xiě)出它們能正確執(zhí)行的程序。,緩沖區(qū),輸入進(jìn)程R,打印進(jìn)程P,處理進(jìn)程M,3.6 進(jìn)程同步,計(jì)算進(jìn)程PC ：反復(fù)地把每次計(jì)算結(jié)果放入緩沖區(qū)Buf中 打印進(jìn)程PP ：將計(jì)算進(jìn)程每次放入緩沖區(qū)Buf中的數(shù)據(jù)取出，通過(guò)打印機(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 是否為空*/ Cobegin Pc: While (計(jì)算未結(jié)束); /*計(jì)算進(jìn)程*/ 計(jì)算； P(Sc); /*緩沖區(qū)是否為空？若非空，則等待*/ Buf計(jì)算結(jié)果； V(Sp); Pp: While (打印未完成); /*打印進(jìn)程*/ P(Sp); /*緩沖區(qū)是否為數(shù)據(jù)？若無(wú)，則等待*/ 從緩沖區(qū)Buf取數(shù)據(jù)； V(Sc); 打印數(shù)據(jù)； Coend End,分析,緩沖區(qū)是臨界資源，必須互斥訪問(wèn) 信號(hào)量empty：表示緩沖區(qū)是否為空，初值為1 信號(hào)量Sr：進(jìn)程R是否已輸入信息，初值Sr=0 信號(hào)量Sm：進(jìn)程M是否已加工信息，初值Sm=0,begin empty, Sr, Sm, Sp : semaphore empty:=1; Sr:=0; Sm:=0 ; Cobegin Pr: Repeat 從輸入設(shè)備讀一個(gè)記錄； P(empty); 將記錄存入緩沖區(qū)； V(Sr); Until false Pm: Repeat P(Sr); 在緩沖區(qū)中加工記錄； V(Sm); Until false,Pp: Repeat P(Sm); 從緩沖區(qū)取出一個(gè)記錄； V(empty); 打印記錄； Until false Coend end,第3章 進(jìn)程管理,2.有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上進(jìn)行登記。該表為每一座位列出一個(gè)表目，包括座號(hào)、姓名。讀者離開(kāi)時(shí)撤消登記信息。閱覽室有100個(gè)座位，試問(wèn)： （1）為描述讀者的動(dòng)作，應(yīng)編寫(xiě)幾個(gè)程序，應(yīng)該設(shè)置幾個(gè)進(jìn)程？進(jìn)程和程序之間的對(duì)應(yīng)關(guān)系如何？ （2）試用P、V操作描述這些進(jìn)程間的同步算法。,分析,讀者動(dòng)作：登記、讀書(shū)、撤消 座位總數(shù)：100 登記/撤消都需要在登記表修改信息，一次只能有一個(gè)讀者對(duì)登記表進(jìn)行訪問(wèn) 登記表是臨界資源，必須互斥訪問(wèn) 一個(gè)讀者一個(gè)進(jìn)程 信號(hào)量的設(shè)置 S：用于讀者互斥訪問(wèn)（登記/撤消）登記表，初值為1 Sn：表示空座位數(shù)，初值為100 每個(gè)座位設(shè)一個(gè)狀態(tài)位：滿(mǎn)/空（類(lèi)似信箱通訊）,程 序,begin S, Sn : Semaphore; S:=1 ; Sn:=100; Cobegin process Reader i (i=1, 2, , n ） begin P(Sn); P(S) ; 選擇標(biāo)志為空的座位X； 登記； 置座位X的標(biāo)志為滿(mǎn)； V(S);,讀書(shū)； P(S) 在登記表中查找座位X； 撤消登記信息； 置座位X的標(biāo)志為空； V(Sn) V(S) end Coend 討論并分析上述程序： 采用指針形式（類(lèi)似生產(chǎn)者-消費(fèi)者問(wèn)題） 給每個(gè)座位設(shè)置一個(gè)信號(hào)量（類(lèi)似哲學(xué)家就餐問(wèn)題）,第3章 補(bǔ)充題,3. 桌上有一只盤(pán)子，每次只能放入一個(gè)水果。爸爸專(zhuān)向盤(pán)中放蘋(píng)果，媽媽專(zhuān)向盤(pán)中放桔子，一個(gè)女兒專(zhuān)等吃盤(pán)中的蘋(píng)果，一個(gè)兒子專(zhuān)等吃盤(pán)中的桔子。試用P、V操作寫(xiě)出他們能同步的程序。 分析： 信號(hào)量S：表示盤(pán)子是否為空，初值為1 信號(hào)量So：表示盤(pán)中是否有桔子，初值為0 信號(hào)量Sa：表示盤(pán)子是否有蘋(píng)果，初值為0,程序,begin S, Sa, So : semaphore S=1; Sa=0; So=0; Cobegin father: Repeat P(S); 將蘋(píng)果放入盤(pán)中； V(Sa); Until false mother: Repeat P(S); 將桔子放入盤(pán)中； V(So); Until false,daughter: Repeat P(Sa); 從盤(pán)中取出蘋(píng)果； V(S); 吃蘋(píng)果； Until false son: Repeat P(So); 從盤(pán)中取出桔子； V(S); 吃桔子； Until false Coend end,第3章 補(bǔ)充題,4、某大學(xué)軍訓(xùn)正在進(jìn)行實(shí)彈練習(xí)。現(xiàn)有一保管員負(fù)責(zé)管理槍支彈藥，有A、B兩組學(xué)生，A組學(xué)生每人都有一支槍?zhuān)珺組學(xué)生每人都備有足夠的子彈，任一學(xué)生只要有槍和子彈就可以進(jìn)行實(shí)彈練習(xí)。在打靶場(chǎng)有一個(gè)可以放一只槍或一發(fā)子彈的盒子，當(dāng)盒中無(wú)物品時(shí)，保管員就可以任意放一支槍或一發(fā)子彈供學(xué)生取用。當(dāng)盒中有學(xué)生所需材料時(shí)，每次允許一個(gè)學(xué)生從中取出自己所需的材料，材料取走后，保管員再放一件材料。 （1）試說(shuō)明A、B兩組學(xué)生、保管員之間的相互制約關(guān)系。 （2）應(yīng)設(shè)置哪些信號(hào)量，它們的初值是什么？ （3）試用P、V寫(xiě)出他們并發(fā)執(zhí)行的程序（類(lèi)C或類(lèi)PASCAL語(yǔ)言）。,解答,解： （1）這是一個(gè)生產(chǎn)者-消費(fèi)者問(wèn)題。 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：表示盒子中是否有一支槍?zhuān)踔禐?； 私用信號(hào)量Sbullet：表示盒子中是否有一發(fā)子彈，初值為0,程序如下：,Begin S, Sgun, Sbullet : semaphore S=1; /*表示盒子是否為空，初值為1*/ Sgun=0; /*表示盒子中是否有一支槍?zhuān)踔禐?*/ Sbullet=0; /*表示盒子中是否有一發(fā)子彈，初值為0*/ Cobegin Keeper： Repeat P(S); 將一支槍或一發(fā)子彈放入盒子中； If 放入的是一支槍 Then V(Sgun) Else V(Sbullet) fi Until false,Student Ai (i=1,2,) Repeat P(Sbullet); 從盒子中取出子彈； V(S); 打靶； Until false Student Bj (j=1,2,) Repeat P(Sgun); 從盒子中取出槍?zhuān)?V(S); 打靶； Until false Coend end,5、假定系統(tǒng)中有五個(gè)進(jìn)程P0，P1，P2，P3，P4和三種類(lèi)型的資源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)能否將資源分配給它？為什么？,第3章 補(bǔ)充題,解： （1）進(jìn)程的最大資源需求數(shù)減去當(dāng)前進(jìn)程已分配到的資源數(shù)就是進(jìn)程仍需要的資源數(shù)。此時(shí)各進(jìn)程的仍需資源數(shù)向量為,已知：系統(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。具體如下：,（2）如果進(jìn)程P4此時(shí)提出資源申請(qǐng)（3，3，1），系統(tǒng)滿(mǎn)足進(jìn)程P4的請(qǐng)求，則系統(tǒng)的可用資源數(shù)變?yōu)椋?，0，1）。而此時(shí)各進(jìn)程的仍需資源數(shù)向量為：,這時(shí)系統(tǒng)的可用資源數(shù)（0，0，1）不能滿(mǎn)足任何一個(gè)進(jìn)程，系統(tǒng)處于不安全狀態(tài)。 因此，系統(tǒng)不能將資源分配給進(jìn)程P4。,P83 3.10,P62 經(jīng)典生產(chǎn)者-消費(fèi)者問(wèn)題,經(jīng)典生產(chǎn)者消費(fèi)者問(wèn)題,設(shè)生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程是互相等效的，其中，各生產(chǎn)者進(jìn)程使用過(guò)程deposit(data)，各消費(fèi)者使用的過(guò)程remove(data) 生產(chǎn)者-消費(fèi)者問(wèn)題是一個(gè)同步問(wèn)題 消費(fèi)者想接收數(shù)據(jù)時(shí)，緩沖區(qū)中至少有一個(gè)單元是滿(mǎn)的 生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，緩沖區(qū)中至少有一個(gè)單元是空的 生產(chǎn)者-消費(fèi)者問(wèn)題是一個(gè)互斥問(wèn)題 緩沖區(qū)是臨界資源,經(jīng)典生產(chǎn)者消費(fèi)者問(wèn)題,設(shè)置信號(hào)量 公用信號(hào)量mutex：保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥；初值為1，表示沒(méi)有進(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,為什么要互斥訪問(wèn)緩沖區(qū)？,什么情況下，出現(xiàn)阻塞？,經(jīng)典生產(chǎn)者消費(fèi)者問(wèn)題,設(shè)置信號(hào)量 公用信號(hào)量S：初值為1，表示沒(méi)有進(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)品,Begin B:array0n-1 of integer; P, R: integer; S, Sn, S0: semaphore; P:=R:=0; S:=1; Sn:=n; S0 :=0; Cobegin Process Produce i (i=1, 2, ,m) Begin L1: produce a product P(Sn); P(S); BP:=product; P:=(P+1) mod n; V(S0); V(S);,go to L1 end Process consumer j (j=1, 2, ,k) Begin L2: P(S0); P(S); take a product from BR; R:=(R+1) mod n; V(Sn); V(S); consume go to L2 end Coend end,P83 3.10,解：設(shè)互斥信號(hào)量mutexn為緩沖區(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)程使用的過(guò)程Deposit(data)如下： Deposit(data) Begin P(S1) 選擇第n個(gè)空緩沖區(qū) P(mutexn) 送數(shù)據(jù)入第n個(gè)緩沖區(qū) V(S2) V(mutexn) End,各消費(fèi)者進(jìn)程使用的過(guò)程Remove(data)如下： Remove(data) Begin P(S2) 選擇一個(gè)已有數(shù)據(jù)的緩沖區(qū)k P(mutexk) 取出緩沖區(qū)k中的數(shù)據(jù) V(S1) V(mutexk) End,P83 3.11,P61 例,P61 例，設(shè)進(jìn)程PA和PB通過(guò)緩沖區(qū)隊(duì)列傳遞數(shù)據(jù)(如圖3.14)。 PA為發(fā)送進(jìn)程， PB為接收進(jìn)程。 PA發(fā)送數(shù)據(jù)時(shí)調(diào)用發(fā)送過(guò)程deposit(data)， PB接收數(shù)據(jù)時(shí)調(diào)用過(guò)程remove(data)。且數(shù)據(jù)的發(fā)送和接收過(guò)程滿(mǎn)足如下條件： 在PA至少送一塊數(shù)據(jù)入一個(gè)緩沖區(qū)之前， PB不可能從緩沖區(qū)中取出數(shù)據(jù)（假定數(shù)據(jù)塊長(zhǎng)等于緩沖區(qū)長(zhǎng)度） 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ì)列,P83 3.11,解：由題可知，進(jìn)程PA調(diào)用發(fā)送過(guò)程deposit(data)和進(jìn)程 PB調(diào)用過(guò)程remove(data)必須同步執(zhí)行，因此， 設(shè)： Bufempty為進(jìn)程PA的私用信號(hào)量，初值Bufempty=n Buffull為進(jìn)程PB的私用信號(hào)量，初值Buffull=0 則，過(guò)程deposit(data)和remove(data)描述如下：,P83 3.11,設(shè)：有兩個(gè)緩沖區(qū)隊(duì)列i=1、2，每個(gè)緩沖區(qū)隊(duì)列有n個(gè)緩沖區(qū)。 bufi(k) 表示第i個(gè)緩沖隊(duì)列的第k個(gè)緩沖區(qū) bufempty0，buffull1為PA的私有信號(hào)量 buffull0，buffempty1是PB的私有信號(hào)量 bufempty0=bufempty1=n buffull0=buffull1=0 PA調(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ā)送過(guò)程 send(i,m) begin P(bufemptyi) FIFO方式選擇一個(gè)空緩沖區(qū)k bufi(k)=m bufi(k)置滿(mǎn)標(biāo)記 V(buffulli) End,接收過(guò)程 Receive(i,m) begin P(buffulli) FIFO方式選擇一個(gè)滿(mǎn)緩沖區(qū)k m=bufi(k) bufi(k)置空標(biāo)記 V(bufemptyi) end,P84 3.13（參考p72 例2）,#include Main() int i,r,P1,P2,fd3; char buf50,s50; pipe(fd); while(P1=fork()=-1); if(P1=0) lockf(fd1,1,0); sprintf(buf,”child process P1 is sending messages!n”); printf(“child process P1!n”); write(fd1,buf,50); sleep(5); lockf(fd1,0,0); exit(0); ,Else while(P2=fork()=-1); if(P2=0) lockf(fd1,1,0); sprintf(buf,”child process P2 is sending messages!n”); printf(“child process P2!n”); write(fd1,buf,50); sleep(5); lockf(fd1,0,0); exit(0); ,Else while(P3=fork()=-1); if(P3=0) lockf(fd1,1,0); sprintf(buf,”child process P3 is sending messages!n”); printf(“child process P3!n”); write(fd1,buf,50); sleep(5); lockf(fd1,0,0); exit(0); ,Wait(0); If(r=read(fd0,s,50)=-1) Printf(“cant read pipen”); Else printf(“%sn”,s); Wait(0); If(r=read(fd0,s,50)=-1) Printf(“cant read pipen”); Else printf(“%sn”,s); Wait(0); If(r=read(fd0,s,50)=-1) Printf(“cant read pipen”); Else printf(“%sn”,s); Exit(0); ,3.14 哲學(xué)家就餐問(wèn)題(習(xí)題p15),有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤(pán)通心粉，每人面前有一只空盤(pán)子，每?jī)扇酥g放一只筷子 每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉 為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子,Repeat 思考； 取forki ;/*取左邊筷子*/ 取fork(i+1) mod 5；/*取右邊筷子*/ 進(jìn)食； 放forki;/*放左邊筷子*/ 放fork(i+1) mod 5；/*放右邊筷子*/ Until false;,方法：為每根筷子單獨(dú)設(shè)置一個(gè)信號(hào)量，取筷子執(zhí)行P操作，放筷子執(zhí)行V操作 Var chopstick: array04 of semaphore; For i=0 to 4 chopsticki=1 Next i Pi: Repeat think; P(chopsticki); P(chopsticki+1 mod 5); eat; V(chopsticki); V(chopsticki+1 mod 5); Until false;,存在問(wèn)題,上述方法簡(jiǎn)單，并能保證任何時(shí)候均不存在兩個(gè)相鄰的哲學(xué)家同時(shí)在吃飯。 但由于進(jìn)程的并發(fā)執(zhí)行與CPU的調(diào)度問(wèn)題，可能使得每個(gè)哲學(xué)家都只能拿到了自己左邊的筷子，那么這一組進(jìn)程就會(huì)發(fā)生死鎖現(xiàn)象。,為防止死鎖發(fā)生可采取的措施： 最多允許4個(gè)哲學(xué)家同時(shí)坐在桌子周?chē)?僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子（） 給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之 為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進(jìn)食，并且一次拿到兩只筷子，否則不拿,state:array04 of (思考，饑餓，進(jìn)食）； ph: array04 of semaphore; mutex:semaphore; i:04;,Procedure test(i:=04); begin if (state i = 饑餓) And (state(i-1)mod5進(jìn)食) And (state(i+1)mod5進(jìn)食) then state i =進(jìn)食 V(ph i ) fi end,Procedure philosopher(i: 04) Begin Repeat 思考； statei :=饑餓； P(mutex); test(i); V(mutex); P(ph i ); 拿左筷子； 拿右筷子； 進(jìn)食； 放左筷子； 放右筷子；,P(mutex) state i :=思考； test(i-1mod5); tset(i+1mod5); V(mutex); until fales End state I =思考 ph I =0 mutex=1,第4章 處理機(jī)調(diào)度,P108 習(xí)題2、4、5、6,第4章 處理機(jī)調(diào)度,4.6 假設(shè)有4道作業(yè)，它們的提交時(shí)刻和執(zhí)行時(shí)間由下表給出：,計(jì)算在單道程序環(huán)境下，采用先來(lái)先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時(shí)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，并指出它們的調(diào)度順序。,1.先來(lái)先服務(wù)(FCFS)調(diào)度算法,將用戶(hù)作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排隊(duì)，按照先來(lái)先服務(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í)間很長(zhǎng)的作業(yè)或進(jìn)程之后到達(dá)，則它們將等待很長(zhǎng)的時(shí)間,采用先來(lái)先服務(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,先來(lái)先服務(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)度方式 問(wèn)題： SJF需要事先知道或至少需要估計(jì)每個(gè)作業(yè)所需的處理機(jī)時(shí)間 只要不斷的有短作業(yè)進(jìn)入系統(tǒng)，就有可能使長(zhǎng)作業(yè)長(zhǎng)期得不到運(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è)優(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è)優(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è)面走向?yàn)橐韵滦蛄校?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ì)算程序訪問(wèn)過(guò)程中所發(fā)生的缺頁(yè)次數(shù)和缺頁(yè)率。,FIFO算法的缺頁(yè)中斷次數(shù)F=11，缺頁(yè)率f=11/20=55%,LRU算法的缺頁(yè)中斷次數(shù)F=10，缺頁(yè)率f=10/20=50%,理想置換算法的缺頁(yè)中斷次數(shù)F=9 缺頁(yè)率f=9/20=45%,補(bǔ)充題,2、某系統(tǒng)采用請(qǐng)求分頁(yè)存儲(chǔ)管理，頁(yè)長(zhǎng)為2 KB（即2048B），某作業(yè)的頁(yè)表如下所示。請(qǐng)簡(jiǎn)述執(zhí)行指令 60 LOAD A, 5168 的地址變換過(guò)程。,解：執(zhí)行指令60 LOAD A,5168的地址變換過(guò)程為： （1）取指令：首先根據(jù)該指令的邏輯地址60，得到相應(yīng)的邏輯頁(yè)式地址為（0，60），然后查頁(yè)表得到其物理塊為3，計(jì)算出物理地址為： 32048+606204 所以，從6204單元中取出指令執(zhí)行。 （2）取數(shù)據(jù)：首先根據(jù)數(shù)據(jù)的邏輯地址5168，得到相應(yīng)的邏輯頁(yè)式地址為（2，1072），然后查頁(yè)表得到其物理塊為8，計(jì)算出物理地址為： 82048+107217456 所以，從174