一同步與互斥問題分析題意，確定同步、互斥或同步與互斥問題。設(shè)信號量，給出信號量表示的含義（公用，私用）和初始值。描述算法，注意死鎖問題。一同步與互斥問題分析題意，確定同步、互斥或同步與互斥問題。1把一個長度為n的有界緩沖區(qū)(n＞0)與一群生產(chǎn)者進(jìn)程P1，P2，…，Pm和一群消費者進(jìn)程C1，C2，…，Ck聯(lián)系起來3.6.4生產(chǎn)者—消費者問題

把一個長度為n的有界緩沖區(qū)(n＞0)與一群生產(chǎn)者進(jìn)程P1，P2設(shè)生產(chǎn)者進(jìn)程和消費者進(jìn)程是互相等效的，其中，各生產(chǎn)者進(jìn)程使用的過程deposit(data)和各消費者使用的過程remove(data)可描述如下：1.首先生產(chǎn)者—消費者問題是一個同步問題。即生產(chǎn)者和消費者之間滿足如下條件：1)消費者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是滿的2)生產(chǎn)者想發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是空的2.由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費者進(jìn)程之間必須互斥執(zhí)行。3.6.4生產(chǎn)者—消費者問題

設(shè)生產(chǎn)者進(jìn)程和消費者進(jìn)程是互相等效的，其中，各生產(chǎn)者進(jìn)程使用3★公用信號量mutex，保證生產(chǎn)者進(jìn)程和消費者進(jìn)程之間的互斥，表示可用有界緩沖區(qū)的個數(shù)，初值為1；★信號量avail為生產(chǎn)者進(jìn)程的私用信號量，表示有界緩沖區(qū)中的空單元個數(shù)，初值為n；

★信號量full為消費者進(jìn)程的私用信號量，表示有界緩沖區(qū)中非空單元個數(shù)，初值為0。從而有：3.6.4生產(chǎn)者—消費者問題

★公用信號量mutex，保證生產(chǎn)者進(jìn)程和消費者進(jìn)程之間的互斥4deposit(data)：begin

P(avail)

P(mutex)送數(shù)據(jù)入緩沖區(qū)某單元

V(full)

V(mutex)Endremove(data)：begin

P(full)

P(mutex)取緩沖區(qū)中某單元數(shù)據(jù)

V(avail)

V(mutex)end3.6.4生產(chǎn)者—消費者問題

deposit(data)：remove(data)：3.5哲學(xué)家就餐問題有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子每個哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉為了吃通心粉，每個哲學(xué)家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子哲學(xué)家就餐問題有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉6設(shè)fork[5]為5個信號量，初值為均1,fork[i]表示i號筷子被拿（i=0，1，2，3，4）Philosopheri：while(1){

思考；P(fork[i]);P(fork[(i+1)%5])；進(jìn)食；V(fork[i]);V(fork[(i+1)%5])；}解設(shè)fork[5]為5個信號量，初值為均1,fork[i]7以上解法會出現(xiàn)死鎖，為防止死鎖發(fā)生可采取的措施：最多允許4個哲學(xué)家同時坐在桌子周圍僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才允許他拿筷子給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之。

分析以上解法會出現(xiàn)死鎖，為防止死鎖發(fā)生可采取的措施：分析8設(shè)fork[5]為5個信號量,初值為均1，fork[i]表示i號筷子被拿設(shè)信號量S，初值為4S用于封鎖第5個哲學(xué)家無死鎖哲學(xué)家就餐問題解1Philosopheri：while(1){

思考；P(S) P(fork[i]);P(fork[(i+1)%5])；進(jìn)食； V(fork[i]);V(fork[(i+1)%5])；V(S)}設(shè)fork[5]為5個信號量,初值為均1，for9設(shè)fork[5]為5個信號量，初值為均1，fork[i]表示i號筷子被拿無死鎖哲學(xué)家就餐問題解2Philosopheri：Beginifimod2==0then{

思考； P(fork[i]);P(fork[i+1]mod5)；進(jìn)食； V(fork[i]);V(fork[i+1mod5])；}else{

思考； P(fork[i+1mod5]);P(fork[i])；進(jìn)食； V(fork[i+1mod5]);V(fork[i])；}設(shè)fork[5]為5個信號量，初值為均1，fork[i]10二作業(yè)調(diào)度畫表格計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間給出作業(yè)（進(jìn)程）調(diào)度序列計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間二作業(yè)調(diào)度畫表格計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間114.4調(diào)度算法思想：按作業(yè)和就緒進(jìn)程來到的次序進(jìn)行調(diào)度。這種算法優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)，而不管它要求運行時間的長短。優(yōu)點：算法簡單，公平，容易實現(xiàn)缺點：對于短作業(yè)或短進(jìn)程，等待時間長★作業(yè)調(diào)度算法—FCFS（Firstcomefirstserve）4.4調(diào)度算法思想：按作業(yè)和就緒進(jìn)程來到的次序進(jìn)行調(diào)度。這124.4調(diào)度算法★作業(yè)調(diào)度算法—FCFS下面是4個作業(yè)在系統(tǒng)中從提交、運行的信息。作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18228.50.5390.149.50.2平均周轉(zhuǎn)時間：T=1.725平均帶權(quán)周轉(zhuǎn)時間W=6.87581010.510.61010.510.610.8221.61.314166.54.4調(diào)度算法★作業(yè)調(diào)度算法—FCFS下面是4個作業(yè)在系統(tǒng)134.4調(diào)度算法思想：比較作業(yè)緩沖區(qū)中的作業(yè)預(yù)計的運行時間，選擇預(yù)計時間最短的作業(yè)進(jìn)入運行狀態(tài)。優(yōu)點：算法簡單，可得到最大系統(tǒng)吞吐率，效率高。缺點：主要問題是對長作業(yè)不利，如果系統(tǒng)不斷地接收短作業(yè)，就會使長作業(yè)長時間等待?！锒套鳂I(yè)優(yōu)先算法—SJF（shortestjobfirst）4.4調(diào)度算法思想：比較作業(yè)緩沖區(qū)中的作業(yè)預(yù)計的運行時間，144.4調(diào)度算法★短作業(yè)優(yōu)先算法—SJF作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18228.50.5390.149.50.2平均周轉(zhuǎn)時間：T=1.55平均帶權(quán)周轉(zhuǎn)時間W=5.15810.31010.11010.810.110.322.31.10.814.61144.4調(diào)度算法★短作業(yè)優(yōu)先算法—SJF提交運行時間開始完成154.4調(diào)度算法響應(yīng)比=響應(yīng)時間/預(yù)計執(zhí)行時間響應(yīng)時間=等待時間+預(yù)計執(zhí)行時間所以響應(yīng)比為：1+作業(yè)等待時間/預(yù)計執(zhí)行時間思想：當(dāng)需要從就緒隊列中選擇進(jìn)程投入運行時，先計算每個進(jìn)程的響應(yīng)比，選擇響應(yīng)比最高的進(jìn)程運行優(yōu)點：短作業(yè)響應(yīng)比高，執(zhí)行時間短；長作業(yè)響應(yīng)比隨著等待時間增加而提高，不會過長等待。既照顧了短作業(yè)、也考慮到了長作業(yè)。缺點：每次調(diào)度前計算響應(yīng)比增加了系統(tǒng)開銷?！镒罡唔憫?yīng)比優(yōu)先—HRN（highestresponse-rationext）4.4調(diào)度算法響應(yīng)比=響應(yīng)時間/預(yù)計執(zhí)行時間★最高響應(yīng)比優(yōu)164.4調(diào)度算法作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18228.50.5390.149.50.20平均周轉(zhuǎn)時間：T=1.625W=5.675★最高響應(yīng)比優(yōu)先—HRN810.11010.61010.610.110.822.11.11.314.2116.54.4調(diào)度算法提交運行時間開始完成周轉(zhuǎn)帶權(quán)周轉(zhuǎn)時間182217三地址映射根據(jù)公式計算邏輯地址的頁號和頁內(nèi)地址p=int[A/L]d=[A]modL根據(jù)頁表查找頁面號。頁面號乘以頁長，加上位移量（d）計算邏輯地址多次計算直到找到數(shù)據(jù)、指令為止。三地址映射根據(jù)公式計算邏輯地址的頁號和頁內(nèi)地址18★邏輯空間上的地址為：頁號+頁內(nèi)地址，頁內(nèi)的地址空間是連續(xù)的，頁之間不必連續(xù)。199100頁號p頁內(nèi)地址d★如果給定的邏輯地址是A，頁面大小是L，則頁號p和頁內(nèi)地址d可以按以下公式求得：p=int[A/L]d=[A]modL例：邏輯地址100頁面大小1k

5.4.1頁式管理的基本原理★邏輯空間上的地址為：頁號+頁內(nèi)地址，頁內(nèi)的地址空間是連續(xù)的195.4.2靜態(tài)頁面管理★地址變換：根據(jù)邏輯空間的頁號，查找頁表對應(yīng)項找到對應(yīng)的物理頁面號，頁面號乘以頁長，加上位移量（頁內(nèi)地址）就是物理地址。每個作業(yè)的邏輯地址是連續(xù)的，重定位到內(nèi)存空間后就不一定連續(xù)了。變換過程全部由硬件地址變換機(jī)構(gòu)自動完成。

5.4.2靜態(tài)頁面管理★地址變換：205.4.2靜態(tài)頁面管理★地址變換：

請求表中讀出MOVr1，[2500]虛地址為100

8*1024+452=86445.4.2靜態(tài)頁面管理★地址變換：請求表中讀出MOVr121四頁面置換根據(jù)引用頁面序列畫出頁面置換圖給出被置換頁面序列，調(diào)入內(nèi)存頁面序列計算缺頁次數(shù)，缺頁率，命中率四頁面置換根據(jù)引用頁面序列畫出頁面置換圖225.4.4請求頁式管理的置換算法★先進(jìn)先出算法(FIFO-FirstInputFirstOutput）,先進(jìn)入內(nèi)存的頁面先淘汰。優(yōu)點：實現(xiàn)簡單。缺點：常用的頁會被淘汰。缺頁率15/20=75%5.4.4請求頁式管理的置換算法★先進(jìn)先出算法(FIFO-23123412512345111444555555222111113333332222244123412512345111111555544222222111153333332222444444333Belady現(xiàn)象：分配給一個進(jìn)程的頁面增加，反而出現(xiàn)缺頁增加的現(xiàn)象5.4.4請求頁式管理的置換算法缺頁率為9/12=75%缺頁率=10/12=83.3%原因是沒有考慮頁的執(zhí)行順序

123412512345111444555555222111245.4.4請求頁式管理的置換算法★最優(yōu)淘汰算法（OPT-Optimalreplacementalgorithm）：是理想算法。系統(tǒng)預(yù)測作業(yè)將要訪問的頁面。淘汰預(yù)測不被訪問或長時間后才被訪問中的頁面。缺頁率9/20=45%幾乎無法實現(xiàn)!5.4.4請求頁式管理的置換算法★最優(yōu)淘汰算法（OPT-O255.4.4請求頁式管理的置換算法★最近最久未使用頁面淘汰法（LRU-LeastRecentlyUsed）：淘汰最近一段時間最久沒訪問的頁面。

缺點：每頁設(shè)訪問記錄，每次更新，系統(tǒng)開銷大。缺頁率12/20=60%5.4.4請求頁式管理的置換算法★最近最久未使用頁面淘汰法26五死鎖避免先驗證系統(tǒng)初始狀態(tài)的安全性，找出安全序列。根據(jù)申請資源情況，結(jié)合剩余資源檢查申請合理性。驗證分配后系統(tǒng)安全性，給出安全序列，否則不能分配資源給相應(yīng)進(jìn)程。五死鎖避免先驗證系統(tǒng)初始狀態(tài)的安全性，找出安全序列。27銀行家算法實例假定系統(tǒng)有四個進(jìn)程P1,P2,P3,P4,三種類型的資源R1,R2,R3,數(shù)量分別為9，3，6，在T0時刻的資源分配情況如下： ProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false1/1/2 P26/1/35/1/11/0/2falseP33/1/42/1/11/0/3falseP44/2/20/0/24/2/0false銀行家算法實例假定系統(tǒng)有四個進(jìn)程P1,P2,P3,P4,三種28驗證T0時刻的安全性分析：

1.四進(jìn)程執(zhí)行狀態(tài)都是未完成，F(xiàn)inish=false2.找Pi，其需要的資源need<=有效資源work3.當(dāng)前的work={1/1/2}，needP1P2P3P4{(2/2/2),(1/0/2),(1/0/3),(4/2/0)}4.找到P2滿足條件，如果讓P2運行結(jié)束，驗證T0時刻的安全性分析：29驗證T0時刻的安全性存在運行序列：P2,P1,P3,P4ProcessWorkneedallocationWork-newFinishP21/1/21/0/25/1/1falseP12/2/21/0/0falseP31/0/32/1/1falseP44/2/00/0/2false0/1/00/0/06/1/3true6/2/36/2/34/0/10/0/03/2/27/2/37/2/36/2/00/0/0truetruetrue0/0/03/1/49/3/49/3/45/1/44/2/29/3/6驗證T0時刻的安全性存在運行序列：P2,P1,P3,P4Pr30P2請求資源{1，0，1}現(xiàn)在P2請求資源{1/0/1}，按照銀行家算法檢查：Request2{1/0/1}<=Need2{1/0/2}Request2{1/0/1}<=Available2{1/1/2}假定可以分配，修改Available,Allocation,Need

ProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false0/1/1

P26/1/36/1/20/0/1falseP33/1/42/1/11/0/3falseP44/2/20/0/24/2/0false進(jìn)行安全性檢查P2請求資源{1，0，1}現(xiàn)在P2請求資源{1/0/1}，按31驗證P2分配資源后的安全性存在運行序列：P2,P1,P3,P4ProcessWorkneedallocationWork-newFinishP20/1/10/0/16/1/2falseP12/2/21/0/0falseP31/0/32/1/1falseP44/2/00/0/2false0/1/00/0/06/1/3true6/2/36/2/34/0/10/0/03/2/27/2/37/2/36/2/00/0/0truetruetrue0/0/03/1/49/3/49/3/45/1/44/2/29/3/6驗證P2分配資源后的安全性存在運行序列：P2,P1,P3,P32P1請求資源{1/0/1}，按照銀行家算法檢查：Request1{1/0/1}<=Need1{2/2/2}Request1{1/0/1}>Available1{0/1/1}條件不滿足，不能分配，讓P1等待。P1請求資源{1，0，1}P1請求資源{1/0/1}，按照銀行家算法檢查：P1請求資源33P3請求資源{0，0，1}現(xiàn)在P3請求資源{0/0/1}，按照銀行家算法檢查：Request3{0/0/1}<=Need3{1/0/3}Request3{0/0/1}<=Available3{0/1/1}假定可以分配，修改Available,Allocation,NeedProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false0/1/0P26/1/36/1/20/0/1falseP33/1/42/1/21/0/2falseP44/2/20/0/24/2/0false進(jìn)行安全性檢查P3請求資源{0，0，1}現(xiàn)在P3請求資源{0/0/1}，按34P3分配資源后的安全性分析：四進(jìn)程執(zhí)行狀態(tài)都是未完成，F(xiàn)inish=false找Pi，其需要的資源need<=當(dāng)前的work={0/1/0}進(jìn)程的needP1P2P3P4{(2/2/2),0/0/1),(1/0/2),(4/2/0)}找不到滿足條件的Pi,因此資源P3不能分配本次資源，回退。ProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false0/1/1

P26/1/36/1/20/0/1falseP33/1/42/1/11/0/3falseP44/2/20/0/24/2/0falseP3分配資源后的安全性分析：四進(jìn)程執(zhí)行狀態(tài)都是未完成，F(xiàn)in35P2請求資源{1，0，1}現(xiàn)在P2請求資源{1/0/1}，按照銀行家算法檢查：Request2{1/0/1}<=Need2{1/0/2}Request2{1/0/1}<=Available2{1/1/2}假定可以分配，修改Available,Allocation,Need

ProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false0/1/1

P26/1/36/1/20/0/1falseP33/1/42/1/11/0/3falseP44/2/20/0/24/2/0falseP2請求資源{1，0，1}現(xiàn)在P2請求資源{1/0/1}，按36一同步與互斥問題分析題意，確定同步、互斥或同步與互斥問題。設(shè)信號量，給出信號量表示的含義（公用，私用）和初始值。描述算法，注意死鎖問題。一同步與互斥問題分析題意，確定同步、互斥或同步與互斥問題。37把一個長度為n的有界緩沖區(qū)(n＞0)與一群生產(chǎn)者進(jìn)程P1，P2，…，Pm和一群消費者進(jìn)程C1，C2，…，Ck聯(lián)系起來3.6.4生產(chǎn)者—消費者問題

把一個長度為n的有界緩沖區(qū)(n＞0)與一群生產(chǎn)者進(jìn)程P1，P38設(shè)生產(chǎn)者進(jìn)程和消費者進(jìn)程是互相等效的，其中，各生產(chǎn)者進(jìn)程使用的過程deposit(data)和各消費者使用的過程remove(data)可描述如下：1.首先生產(chǎn)者—消費者問題是一個同步問題。即生產(chǎn)者和消費者之間滿足如下條件：1)消費者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是滿的2)生產(chǎn)者想發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是空的2.由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費者進(jìn)程之間必須互斥執(zhí)行。3.6.4生產(chǎn)者—消費者問題

設(shè)生產(chǎn)者進(jìn)程和消費者進(jìn)程是互相等效的，其中，各生產(chǎn)者進(jìn)程使用39★公用信號量mutex，保證生產(chǎn)者進(jìn)程和消費者進(jìn)程之間的互斥，表示可用有界緩沖區(qū)的個數(shù)，初值為1；★信號量avail為生產(chǎn)者進(jìn)程的私用信號量，表示有界緩沖區(qū)中的空單元個數(shù)，初值為n；

★信號量full為消費者進(jìn)程的私用信號量，表示有界緩沖區(qū)中非空單元個數(shù)，初值為0。從而有：3.6.4生產(chǎn)者—消費者問題

★公用信號量mutex，保證生產(chǎn)者進(jìn)程和消費者進(jìn)程之間的互斥40deposit(data)：begin

P(avail)

P(mutex)送數(shù)據(jù)入緩沖區(qū)某單元

V(full)

V(mutex)Endremove(data)：begin

P(full)

P(mutex)取緩沖區(qū)中某單元數(shù)據(jù)

V(avail)

V(mutex)end3.6.4生產(chǎn)者—消費者問題

deposit(data)：remove(data)：3.41哲學(xué)家就餐問題有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子每個哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉為了吃通心粉，每個哲學(xué)家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子哲學(xué)家就餐問題有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉42設(shè)fork[5]為5個信號量，初值為均1,fork[i]表示i號筷子被拿（i=0，1，2，3，4）Philosopheri：while(1){

思考；P(fork[i]);P(fork[(i+1)%5])；進(jìn)食；V(fork[i]);V(fork[(i+1)%5])；}解設(shè)fork[5]為5個信號量，初值為均1,fork[i]43以上解法會出現(xiàn)死鎖，為防止死鎖發(fā)生可采取的措施：最多允許4個哲學(xué)家同時坐在桌子周圍僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才允許他拿筷子給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之。

分析以上解法會出現(xiàn)死鎖，為防止死鎖發(fā)生可采取的措施：分析44設(shè)fork[5]為5個信號量,初值為均1，fork[i]表示i號筷子被拿設(shè)信號量S，初值為4S用于封鎖第5個哲學(xué)家無死鎖哲學(xué)家就餐問題解1Philosopheri：while(1){

思考；P(S) P(fork[i]);P(fork[(i+1)%5])；進(jìn)食； V(fork[i]);V(fork[(i+1)%5])；V(S)}設(shè)fork[5]為5個信號量,初值為均1，for45設(shè)fork[5]為5個信號量，初值為均1，fork[i]表示i號筷子被拿無死鎖哲學(xué)家就餐問題解2Philosopheri：Beginifimod2==0then{

思考； P(fork[i]);P(fork[i+1]mod5)；進(jìn)食； V(fork[i]);V(fork[i+1mod5])；}else{

思考； P(fork[i+1mod5]);P(fork[i])；進(jìn)食； V(fork[i+1mod5]);V(fork[i])；}設(shè)fork[5]為5個信號量，初值為均1，fork[i]46二作業(yè)調(diào)度畫表格計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間給出作業(yè)（進(jìn)程）調(diào)度序列計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間二作業(yè)調(diào)度畫表格計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間474.4調(diào)度算法思想：按作業(yè)和就緒進(jìn)程來到的次序進(jìn)行調(diào)度。這種算法優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)，而不管它要求運行時間的長短。優(yōu)點：算法簡單，公平，容易實現(xiàn)缺點：對于短作業(yè)或短進(jìn)程，等待時間長★作業(yè)調(diào)度算法—FCFS（Firstcomefirstserve）4.4調(diào)度算法思想：按作業(yè)和就緒進(jìn)程來到的次序進(jìn)行調(diào)度。這484.4調(diào)度算法★作業(yè)調(diào)度算法—FCFS下面是4個作業(yè)在系統(tǒng)中從提交、運行的信息。作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18228.50.5390.149.50.2平均周轉(zhuǎn)時間：T=1.725平均帶權(quán)周轉(zhuǎn)時間W=6.87581010.510.61010.510.610.8221.61.314166.54.4調(diào)度算法★作業(yè)調(diào)度算法—FCFS下面是4個作業(yè)在系統(tǒng)494.4調(diào)度算法思想：比較作業(yè)緩沖區(qū)中的作業(yè)預(yù)計的運行時間，選擇預(yù)計時間最短的作業(yè)進(jìn)入運行狀態(tài)。優(yōu)點：算法簡單，可得到最大系統(tǒng)吞吐率，效率高。缺點：主要問題是對長作業(yè)不利，如果系統(tǒng)不斷地接收短作業(yè)，就會使長作業(yè)長時間等待?！锒套鳂I(yè)優(yōu)先算法—SJF（shortestjobfirst）4.4調(diào)度算法思想：比較作業(yè)緩沖區(qū)中的作業(yè)預(yù)計的運行時間，504.4調(diào)度算法★短作業(yè)優(yōu)先算法—SJF作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18228.50.5390.149.50.2平均周轉(zhuǎn)時間：T=1.55平均帶權(quán)周轉(zhuǎn)時間W=5.15810.31010.11010.810.110.322.31.10.814.61144.4調(diào)度算法★短作業(yè)優(yōu)先算法—SJF提交運行時間開始完成514.4調(diào)度算法響應(yīng)比=響應(yīng)時間/預(yù)計執(zhí)行時間響應(yīng)時間=等待時間+預(yù)計執(zhí)行時間所以響應(yīng)比為：1+作業(yè)等待時間/預(yù)計執(zhí)行時間思想：當(dāng)需要從就緒隊列中選擇進(jìn)程投入運行時，先計算每個進(jìn)程的響應(yīng)比，選擇響應(yīng)比最高的進(jìn)程運行優(yōu)點：短作業(yè)響應(yīng)比高，執(zhí)行時間短；長作業(yè)響應(yīng)比隨著等待時間增加而提高，不會過長等待。既照顧了短作業(yè)、也考慮到了長作業(yè)。缺點：每次調(diào)度前計算響應(yīng)比增加了系統(tǒng)開銷?！镒罡唔憫?yīng)比優(yōu)先—HRN（highestresponse-rationext）4.4調(diào)度算法響應(yīng)比=響應(yīng)時間/預(yù)計執(zhí)行時間★最高響應(yīng)比優(yōu)524.4調(diào)度算法作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18228.50.5390.149.50.20平均周轉(zhuǎn)時間：T=1.625W=5.675★最高響應(yīng)比優(yōu)先—HRN810.11010.61010.610.110.822.11.11.314.2116.54.4調(diào)度算法提交運行時間開始完成周轉(zhuǎn)帶權(quán)周轉(zhuǎn)時間182253三地址映射根據(jù)公式計算邏輯地址的頁號和頁內(nèi)地址p=int[A/L]d=[A]modL根據(jù)頁表查找頁面號。頁面號乘以頁長，加上位移量（d）計算邏輯地址多次計算直到找到數(shù)據(jù)、指令為止。三地址映射根據(jù)公式計算邏輯地址的頁號和頁內(nèi)地址54★邏輯空間上的地址為：頁號+頁內(nèi)地址，頁內(nèi)的地址空間是連續(xù)的，頁之間不必連續(xù)。199100頁號p頁內(nèi)地址d★如果給定的邏輯地址是A，頁面大小是L，則頁號p和頁內(nèi)地址d可以按以下公式求得：p=int[A/L]d=[A]modL例：邏輯地址100頁面大小1k

5.4.1頁式管理的基本原理★邏輯空間上的地址為：頁號+頁內(nèi)地址，頁內(nèi)的地址空間是連續(xù)的555.4.2靜態(tài)頁面管理★地址變換：根據(jù)邏輯空間的頁號，查找頁表對應(yīng)項找到對應(yīng)的物理頁面號，頁面號乘以頁長，加上位移量（頁內(nèi)地址）就是物理地址。每個作業(yè)的邏輯地址是連續(xù)的，重定位到內(nèi)存空間后就不一定連續(xù)了。變換過程全部由硬件地址變換機(jī)構(gòu)自動完成。

5.4.2靜態(tài)頁面管理★地址變換：565.4.2靜態(tài)頁面管理★地址變換：

請求表中讀出MOVr1，[2500]虛地址為100

8*1024+452=86445.4.2靜態(tài)頁面管理★地址變換：請求表中讀出MOVr157四頁面置換根據(jù)引用頁面序列畫出頁面置換圖給出被置換頁面序列，調(diào)入內(nèi)存頁面序列計算缺頁次數(shù)，缺頁率，命中率四頁面置換根據(jù)引用頁面序列畫出頁面置換圖585.4.4請求頁式管理的置換算法★先進(jìn)先出算法(FIFO-FirstInputFirstOutput）,先進(jìn)入內(nèi)存的頁面先淘汰。優(yōu)點：實現(xiàn)簡單。缺點：常用的頁會被淘汰。缺頁率15/20=75%5.4.4請求頁式管理的置換算法★先進(jìn)先出算法(FIFO-59123412512345111444555555222111113333332222244123412512345111111555544222222111153333332222444444333Belady現(xiàn)象：分配給一個進(jìn)程的頁面增加，反而出現(xiàn)缺頁增加的現(xiàn)象5.4.4請求頁式管理的置換算法缺頁率為9/12=75%缺頁率=10/12=83.3%原因是沒有考慮頁的執(zhí)行順序

123412512345111444555555222111605.4.4請求頁式管理的置換算法★最優(yōu)淘汰算法（OPT-Optimalreplacementalgorithm）：是理想算法。系統(tǒng)預(yù)測作業(yè)將要訪問的頁面。淘汰預(yù)測不被訪問或長時間后才被訪問中的頁面。缺頁率9/20=45%幾乎無法實現(xiàn)!5.4.4請求頁式管理的置換算法★最優(yōu)淘汰算法（OPT-O615.4.4請求頁式管理的置換算法★最近最久未使用頁面淘汰法（LRU-LeastRecentlyUsed）：淘汰最近一段時間最久沒訪問的頁面。

缺點：每頁設(shè)訪問記錄，每次更新，系統(tǒng)開銷大。缺頁率12/20=60%5.4.4請求頁式管理的置換算法★最近最久未使用頁面淘汰法62五死鎖避免先驗證系統(tǒng)初始狀態(tài)的安全性，找出安全序列。根據(jù)申請資源情況，結(jié)合剩余資源檢查申請合理性。驗證分配后系統(tǒng)安全性，給出安全序列，否則不能分配資源給相應(yīng)進(jìn)程。五死鎖避免先驗證系統(tǒng)初始狀態(tài)的安全性，找出安全序列。63銀行家算法實例假定系統(tǒng)有四個進(jìn)程P1,P2,P3,P4,三種類型的資源R1,R2,R3,數(shù)量分別為9，3，6，在T0時刻的資源分配情況如下： ProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false1/1/2 P26/1/35/1/11/0/2falseP33/1/42/1/11/0/3falseP44/2/20/0/24/2/0false銀行家算法實例假定系統(tǒng)有四個進(jìn)程P1,P2,P3,P4,三種64驗證T0時刻的安全性分析：

1.四進(jìn)程執(zhí)行狀態(tài)都是未完成，F(xiàn)inish=false2.找Pi，其需要的資源need<=有效資源work3.當(dāng)前的work={1/1/2}，needP1P2P3P4{(2/2/2),(1/0/2),(1/0/3),(4/2/0)}4.找到P2滿足條件，如果讓P2運行結(jié)束，驗證T0時刻的安全性分析：65驗證T0時刻的安全性存在運行序列：P2,P1,P3,P4ProcessWorkneedallocationWork-newFinishP21/1/21/0/25/1/1falseP12/2/21/0/0falseP31/0/32/1/1falseP44/2/00/0/2false0/1/00/0/06/1/3true6/2/36/2/34/0/10/0/03/2/27/2/37/2/36/2/00/0/0truetruetrue0/0/03/1/49/3/49/3/45/1/44/2/29/3/6驗證T0時刻的安全性存在運行序列：P2,P1,P3,P4Pr66P2請求資源{1，0，1}現(xiàn)在P2請求資源{1/0/1}，按照銀行家算法檢查：Request2{1/0/1}<=Need2{1/0/2}Request2{1/0/1}<=Available2{1/1/2}假定可以分配，修改Available,Allocation,Need

ProcessMaxallocatedNeedFinishAvailableP13/2/21/0/02/2/2false0/1/1

P26/1/36/1/20/0/1falseP33/1/42/1/11/0/3falseP44/2/20/0/24/2/0false進(jìn)行安全性檢查P2請求資源{1，0，1}現(xiàn)在P2請求資源{1/0/1}，按67驗證P2分配資源后的