最全計(jì)算機(jī)操作系統(tǒng)期末復(fù)習(xí)課件

計(jì)算機(jī)操作系統(tǒng)復(fù)習(xí)

2022年11月25日1計(jì)算機(jī)操作系統(tǒng)復(fù)習(xí)

2022年11月22日1標(biāo)題添加點(diǎn)擊此處輸入相關(guān)文本內(nèi)容點(diǎn)擊此處輸入相關(guān)文本內(nèi)容前言點(diǎn)擊此處輸入相關(guān)文本內(nèi)容標(biāo)題添加點(diǎn)擊此處輸入相關(guān)文本內(nèi)容2標(biāo)題添加點(diǎn)擊此處輸入相點(diǎn)擊此處輸入前言點(diǎn)擊此處輸入標(biāo)題添加點(diǎn)課程主要內(nèi)容教材內(nèi)容操作系統(tǒng)引論（第1章）進(jìn)程管理（第2章）處理機(jī)調(diào)度與死鎖（第3章）存儲(chǔ)管理（第4章）設(shè)備管理（第5章）文件管理（第6章）UNIX系統(tǒng)內(nèi)核結(jié)構(gòu)(第10章）3課程主要內(nèi)容教材內(nèi)容3計(jì)算題類型總結(jié)利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步處理機(jī)調(diào)度算法（周轉(zhuǎn)時(shí)間）銀行家算法分區(qū)存儲(chǔ)管理算法邏輯地址物理地址變換請(qǐng)求分頁(yè)中的頁(yè)面置換算法磁盤訪問時(shí)間磁盤調(diào)度算法（平均移道數(shù)）混合索引分配文件控制塊和索引結(jié)點(diǎn)位示圖4計(jì)算題類型總結(jié)利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步4第一章操作系統(tǒng)引論

5第一章操作系統(tǒng)引論

51.3操作系統(tǒng)的基本特征并發(fā)性(Concurrence)共享性(Sharing)虛擬性(Virtual)異步性(Asynchronism)基本特征:最重要特性，其它三種特性以此為前提。61.3操作系統(tǒng)的基本特征并發(fā)性(Concurrence)操作系統(tǒng)的形成單道批處理系統(tǒng)多道批處理系統(tǒng)操作系統(tǒng)的形成在多道程序系統(tǒng)中增設(shè)一組軟件以有效加以解決，同時(shí)增設(shè)方便用戶使用計(jì)算機(jī)的軟件，這樣便形成了操作系統(tǒng)。操作系統(tǒng)：是一組控制和管理計(jì)算機(jī)硬件和軟件資源，合理地對(duì)各類作業(yè)進(jìn)行調(diào)度，以及方便用戶使用的程序集合。7操作系統(tǒng)的形成單道批處理系統(tǒng)操作系統(tǒng)：是一組控制和管理計(jì)算機(jī)操作系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)傳統(tǒng)的操作系統(tǒng)結(jié)構(gòu)無(wú)結(jié)構(gòu)操作系統(tǒng)模塊化OS結(jié)構(gòu)分層式OS結(jié)構(gòu)現(xiàn)代操作系統(tǒng)結(jié)構(gòu)微內(nèi)核的OS結(jié)構(gòu)：將客戶/服務(wù)器技術(shù)、面向?qū)ο蠹夹g(shù)用于OS中所形成的OS結(jié)構(gòu)。8操作系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)傳統(tǒng)的操作系統(tǒng)結(jié)構(gòu)8第二章進(jìn)程管理

9第二章進(jìn)程管理

92、進(jìn)程process的基本特征

（1）結(jié)構(gòu)特征從結(jié)構(gòu)上看，每個(gè)進(jìn)程（進(jìn)程實(shí)體）都是由程序段、數(shù)據(jù)段及進(jìn)程控制塊（PCB）組成。

（2）動(dòng)態(tài)性

進(jìn)程的實(shí)質(zhì)是程序在處理機(jī)上的一次執(zhí)行過程，因此是動(dòng)態(tài)性的。所以動(dòng)態(tài)性是進(jìn)程的最基本的特征。同時(shí)動(dòng)態(tài)性還表現(xiàn)在進(jìn)程則是有生命期的，它因創(chuàng)建而產(chǎn)生，因調(diào)度而執(zhí)行，因得不到資源而暫停，因撤消而消亡。進(jìn)程的定義、特征102、進(jìn)程process的基本特征進(jìn)程的定義、特征10

進(jìn)程在運(yùn)行期間并非固定處于某個(gè)狀態(tài)，而是不斷從一個(gè)狀態(tài)轉(zhuǎn)換到另一個(gè)狀態(tài)。二、進(jìn)程狀態(tài)2、進(jìn)程狀態(tài)轉(zhuǎn)換11進(jìn)程在運(yùn)行期間并非固定處于某個(gè)狀態(tài)，而是不斷從一個(gè)狀態(tài)轉(zhuǎn)換具有掛起狀態(tài)的進(jìn)程狀態(tài)活動(dòng)就緒執(zhí)行掛起調(diào)度時(shí)間片完活動(dòng)阻塞事件發(fā)生等待事件靜止就緒靜止阻塞激活掛起事件發(fā)生激活掛起12具有掛起狀態(tài)的進(jìn)程狀態(tài)活動(dòng)就緒執(zhí)行掛起調(diào)度時(shí)間片完活動(dòng)阻塞事線程的基本概念進(jìn)程是資源分配的單位，而線程是處理機(jī)調(diào)度的單位。一個(gè)進(jìn)程可以創(chuàng)建一個(gè)或多個(gè)線程。多個(gè)線程會(huì)爭(zhēng)奪CPU，在不同的狀態(tài)之間進(jìn)行轉(zhuǎn)換。線程也是一個(gè)動(dòng)態(tài)的概念，也有一個(gè)從創(chuàng)建到消亡的生命過程，具多種狀態(tài)。同一進(jìn)程中的所有線程都具有相同的地址空間（進(jìn)程的地址空間）。13線程的基本概念進(jìn)程是資源分配的單位，而線程是處理機(jī)調(diào)度的單位線程的實(shí)現(xiàn)方式

線程的實(shí)現(xiàn)方式內(nèi)核支持線程的實(shí)現(xiàn)直接利用系統(tǒng)調(diào)用進(jìn)行線程控制。用戶級(jí)線程的實(shí)現(xiàn)不能直接利用系統(tǒng)調(diào)用。為了取得內(nèi)核的服務(wù)（獲得系統(tǒng)資源），需要借助中間系統(tǒng)（運(yùn)行時(shí)系統(tǒng)、輕型進(jìn)程）。14線程的實(shí)現(xiàn)方式線程的實(shí)現(xiàn)方式14同步機(jī)制應(yīng)遵循的規(guī)則空閑讓進(jìn):當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。忙則等待:當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表明臨界資源正在被訪問，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問。有限等待:對(duì)要求訪問臨界資源的進(jìn)程，應(yīng)保證在有限時(shí)間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入死等狀態(tài)。讓權(quán)等待:當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入忙等。15同步機(jī)制應(yīng)遵循的規(guī)則空閑讓進(jìn):當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，表明臨界信號(hào)量機(jī)制信號(hào)量機(jī)制信號(hào)量用于表示資源數(shù)目或請(qǐng)求使用某一資源的進(jìn)程個(gè)數(shù)的整型量。整型信號(hào)量記錄型信號(hào)量信號(hào)量集（AND信號(hào)量集、一般信號(hào)量集）16信號(hào)量機(jī)制信號(hào)量機(jī)制16利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步例：進(jìn)程A與進(jìn)程B共享同一文件file，設(shè)此文件要求互斥使用，則可將file作為臨界資源，有關(guān)file的使用程序段分別為臨界區(qū)CSA和CSB。

semaphoremutex=1;PA:{ L1：P(mutex); CSA;

V(mutex);

remainderofprocessA; GOTOL1;}PB:{ L2:P(mutex); CSB;

V(mutex); remainderofprocessB;GOTOL2;}

17利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步例：進(jìn)程A與進(jìn)程B共享同一文件fileS1S3S2S4S5S6S7S8例：利用信號(hào)量來(lái)描述前趨圖關(guān)系利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步18S1S3S2S4S5S6S7S8例：利用信號(hào)量來(lái)描述前趨圖關(guān)

具有8個(gè)結(jié)點(diǎn)的前趨圖。圖中的前趨圖中共有10條有向邊，可設(shè)10個(gè)信號(hào)量，初值均為0；有8個(gè)結(jié)點(diǎn)，可設(shè)計(jì)成8個(gè)并發(fā)進(jìn)程，具體描述如下：S1S3S2S4S5S6S7S8agefbcdhij利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步19具有8個(gè)結(jié)點(diǎn)的前趨圖。圖中的前趨圖中共有10條有向邊Structsmaphorea,b,c,d,e,f,g,h,i,j=0,0,0,0,0,0,0,0,0,0cobegin{S1;V(a);V(b);V(c);}{P(a);S2;V(d);}{P(b);S3;V(e);V(f);}{P(c);S4;V(g);}{P(d);P(e);S5;V(h);}{P(f);P(g);S6;V(i)}{P(h);P(i);S7;V(j);}{P(j);S8;}coendS1S3S2S4S5S6S7S8agefbcdhij利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步20Structsmaphorea,b,c,d,e,f,g,2.4經(jīng)典進(jìn)程的同步問題

在多道程序環(huán)境下，進(jìn)程同步問題十分重要，出現(xiàn)一系列經(jīng)典的進(jìn)程同步問題，其中有代表性有：生產(chǎn)者—消費(fèi)者問題哲學(xué)家進(jìn)餐問題讀者—寫者問題其他同步問題212.4經(jīng)典進(jìn)程的同步問題在多道程序“哲學(xué)家進(jìn)餐”問題問題描述：有五個(gè)哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。他們共用一張圓桌，分別坐在五張椅子上。在圓桌上有五個(gè)碗和五支筷子，平時(shí)一個(gè)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取用其左、右最靠近他的筷子，只有在他拿到兩支筷子時(shí)才能進(jìn)餐。進(jìn)餐畢，放下筷子又繼續(xù)思考。解決死鎖問題的例子22“哲學(xué)家進(jìn)餐”問題問題描述：解決死鎖問題的例子22哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法一：至多只允許四位哲學(xué)家同時(shí)去拿左筷子，最終能保證至少有一位哲學(xué)家能進(jìn)餐，并在用完后釋放兩只筷子供他人使用。方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起時(shí)才允許進(jìn)餐。方法三：規(guī)定奇數(shù)號(hào)哲學(xué)家先拿左筷子再拿右筷子，而偶數(shù)號(hào)哲學(xué)家相反。23哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法一：至多只允許四位哲學(xué)家同時(shí)去拿哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法一：至多只允許四位哲學(xué)家同時(shí)去拿左筷子，最終能保證至少有一位哲學(xué)家能進(jìn)餐，并在用完后釋放兩只筷子供他人使用。設(shè)置一個(gè)初值為4的信號(hào)量r，只允許4個(gè)哲學(xué)家同時(shí)去拿左筷子，這樣就能保證至少有一個(gè)哲學(xué)家可以就餐，不會(huì)出現(xiàn)餓死和死鎖的現(xiàn)象。原理：至多只允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐，以保證至少有一個(gè)哲學(xué)家能夠進(jìn)餐，最終總會(huì)釋放出他所使用過的兩支筷子，從而可使更多的哲學(xué)家進(jìn)餐。24哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法一：至多只允許四位哲學(xué)家同時(shí)去拿哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstick[5]={1，1，1，1，1};semaphorer=4;voidphilosopher(inti){while(true){think();wait(r);//請(qǐng)求進(jìn)餐wait(chopstick[i]);//請(qǐng)求左手邊的筷子wait(chopstick[(i+1)mod5]);//請(qǐng)求右手邊的筷子eat();signal(chopstick[(i+1)mod5]);//釋放右手邊的筷子signal(chopstick[i]);//釋放左手邊的筷子signal(r);//釋放信號(hào)量rthink();}}25哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstic哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起時(shí)才允許進(jìn)餐。解法1：利用AND型信號(hào)量機(jī)制實(shí)現(xiàn)。原理：多個(gè)臨界資源，要么全部分配，要么一個(gè)都不分配，因此不會(huì)出現(xiàn)死鎖的情形。26哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();Swait(chopstick[i];chopstick[(i+1)mod5]);eat();Ssignal(chopstick[(i+1)mod5];chopstick[i]);think();}}27哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstic哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起時(shí)才允許進(jìn)餐。解法2：利用信號(hào)量的保護(hù)機(jī)制實(shí)現(xiàn)。原理：通過互斥信號(hào)量mutex對(duì)eat()之前取左側(cè)和右側(cè)筷子的操作進(jìn)行保護(hù)，可以防止死鎖的出現(xiàn)。28哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphoremutex=1;semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();wait(mutex);wait(chopstick[i]);wait(chopstick[(i+1)mod5]);signal(mutex);eat();signal(chopstick[(i+1)mod5]);signal(chopstick[i]);think();

}}29哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphoremutex=哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法三：規(guī)定奇數(shù)號(hào)哲學(xué)家先拿左筷子再拿右筷子，而偶數(shù)號(hào)哲學(xué)家相反。原理：按照下圖，將是2,3號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子，4,5號(hào)哲學(xué)家競(jìng)爭(zhēng)5號(hào)筷子。1號(hào)哲學(xué)家不需要競(jìng)爭(zhēng)。最后總會(huì)有一個(gè)哲學(xué)家能獲得兩支筷子而進(jìn)餐。先申請(qǐng)的哲學(xué)家會(huì)較先可以吃飯并釋放筷子，因此不會(huì)出現(xiàn)餓死的哲學(xué)家。122133445530哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法三：規(guī)定奇數(shù)號(hào)哲學(xué)家先拿左筷子再哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){if(imod2==0)//偶數(shù)哲學(xué)家，先右后左。{wait(chopstick[(i+1)mod5]);wait(chopstick[i]);eat();signal(chopstick[i]);signal(chopstick[(i+1)mod5]);}Else//奇數(shù)哲學(xué)家，先左后右。{wait(chopstick[i]);wait(chopstick[(i+1)mod5]);eat();signal(chopstick[(i+1)mod5]);signal(chopstick[i]);}}}31哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstic第三章處理機(jī)調(diào)度與死鎖

32第三章處理機(jī)調(diào)度與死鎖

32提交作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)狀態(tài)轉(zhuǎn)換圖后備退出完成一、調(diào)度的層次就緒阻塞就緒阻塞運(yùn)行交換調(diào)度進(jìn)程調(diào)度（線程調(diào)度）33提交作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)狀態(tài)轉(zhuǎn)換圖后備退出完成一、調(diào)度的層次FCFS例題例：下面三個(gè)作業(yè)幾乎同時(shí)到達(dá)系統(tǒng)并立即進(jìn)行FCFS調(diào)度：作業(yè)名所需CPU時(shí)間作業(yè)128作業(yè)210作業(yè)31假設(shè)提交順序?yàn)?、2、3，則平均作業(yè)周轉(zhuǎn)時(shí)間T=若提交順序改為作業(yè)2、1、3，則T=若提交順序改為作業(yè)3、2、1，則T=由此可以看出，F(xiàn)CFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)提交的順序有關(guān)。(28+38+39)/3=35(10+38+39)/3=29(1+11+39)/3=1734FCFS例題例：下面三個(gè)作業(yè)幾乎同時(shí)到達(dá)系統(tǒng)并立即進(jìn)行FCF進(jìn)程調(diào)度算法先來(lái)先服務(wù)FCFS例1：進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間A01B1100C

2

1D3

10035進(jìn)程調(diào)度算法先來(lái)先服務(wù)FCFS35周轉(zhuǎn)時(shí)間服務(wù)時(shí)間完成時(shí)間-到達(dá)時(shí)間開始時(shí)間+服務(wù)時(shí)間上一個(gè)進(jìn)程的完成時(shí)間1 101 1001101 102100100102 2021991.9936周轉(zhuǎn)時(shí)間服務(wù)時(shí)間完成時(shí)間-到達(dá)時(shí)間開始時(shí)間+服務(wù)時(shí)間上一個(gè)進(jìn)執(zhí)行順序：SJF/SPF（非搶占式）A033103ABCDE24686452B3971.1791131.51115112.751520142.8ECD7.61.84周轉(zhuǎn)時(shí)間＝結(jié)束時(shí)間-到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間＝周轉(zhuǎn)/服務(wù)37執(zhí)行順序：SJF/SPF（非搶占式）A033103ABCDE基本思想：多級(jí)反饋隊(duì)列調(diào)度算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)調(diào)度算法的綜合和發(fā)展，通過動(dòng)態(tài)調(diào)整進(jìn)程優(yōu)先級(jí)和時(shí)間片大小，不必事先估計(jì)進(jìn)程的執(zhí)行時(shí)間。多級(jí)反饋隊(duì)列可兼顧多方面的系統(tǒng)目標(biāo)，是目前公認(rèn)的一種較好的進(jìn)程調(diào)度算法。FCFS+優(yōu)先級(jí)+RR+搶占七、多級(jí)反饋隊(duì)列調(diào)度算法38基本思想：七、多級(jí)反饋隊(duì)列調(diào)度算法38七、多級(jí)反饋隊(duì)列調(diào)度算法---實(shí)現(xiàn)思想（1）設(shè)置多個(gè)就緒隊(duì)列，并為每個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。隊(duì)列1的優(yōu)先級(jí)最高，其余隊(duì)列逐個(gè)降低。（2）每個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，進(jìn)程所在隊(duì)列的優(yōu)先級(jí)越高，其相應(yīng)的時(shí)間片就越短。（3）當(dāng)一個(gè)新進(jìn)程進(jìn)入系統(tǒng)時(shí)，首先將它放入隊(duì)列1的末尾，按FCFS等待調(diào)度。如能完成，便可準(zhǔn)備撤離系統(tǒng)，反之由調(diào)度程序?qū)⑵滢D(zhuǎn)入隊(duì)列2的末尾，按FCFS再次等待調(diào)度，如此下去，最后進(jìn)入隊(duì)列n按RR算法調(diào)度執(zhí)行。（4）僅當(dāng)隊(duì)列1為空時(shí)，才調(diào)度隊(duì)列2中的進(jìn)程運(yùn)行。若一個(gè)隊(duì)列中的進(jìn)程正執(zhí)行，此時(shí)有新進(jìn)程進(jìn)入優(yōu)先級(jí)較高的隊(duì)列中，則新進(jìn)程將搶占運(yùn)行，原進(jìn)程轉(zhuǎn)移至本隊(duì)列隊(duì)尾。39七、多級(jí)反饋隊(duì)列調(diào)度算法---實(shí)現(xiàn)思想（1）設(shè)置多個(gè)就緒隊(duì)列二、產(chǎn)生死鎖的原因競(jìng)爭(zhēng)資源進(jìn)程間推進(jìn)順序非法三、產(chǎn)生死鎖的必要條件

互斥條件（mutualexclusion）請(qǐng)求和保持條件（hold-while-applying）不剝奪條件（nonpreemption）環(huán)路等待條件（circularwait）40二、產(chǎn)生死鎖的原因競(jìng)爭(zhēng)資源三、產(chǎn)生死鎖的必要條件四、處理死鎖的基本方法目前處理死鎖的基本方法有：預(yù)防死鎖：通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，來(lái)防止死鎖的發(fā)生。避免死鎖：在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。檢測(cè)死鎖：允許系統(tǒng)在運(yùn)行過程中發(fā)生死鎖，但可設(shè)置檢測(cè)機(jī)構(gòu)及時(shí)檢測(cè)死鎖的發(fā)生，并采取適當(dāng)措施加以清除。解除死鎖：當(dāng)檢測(cè)出死鎖后，便采取適當(dāng)措施將進(jìn)程從死鎖狀態(tài)中解脫出來(lái)。銀行家算法41四、處理死鎖的基本方法目前處理死鎖的基本方法有：銀行家算法4銀行家算法假定系統(tǒng)中有5個(gè)進(jìn)程P0到P4，3類資源及數(shù)量分別為A(10個(gè)），B（5個(gè)），C（7個(gè)），T0時(shí)刻的資源分配情況如下

表1T0時(shí)刻的資源分配表42銀行家算法假定系統(tǒng)中有5個(gè)進(jìn)程P0到P4，3類資源及數(shù)量分（1）T0時(shí)刻的安全性利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析:T0時(shí)刻存在著一個(gè)安全序列{P1,P3,P4,P2,P0}，故系統(tǒng)是安全的。表2T0時(shí)刻的安全性檢查表532true332532743true743745true745104710471057truetrue332ABCAvailable43（1）T0時(shí)刻的安全性T0時(shí)刻存在著一個(gè)安全序列{P1,P(2)

P1請(qǐng)求資源Request1(1,0,2)

P1發(fā)出請(qǐng)求向量Request1(1,0,2)，已知Need1(1,2,2)，Available(3,3,2)，系統(tǒng)按銀行家算法進(jìn)行檢查:1)Request1(1,0,2)≤Need1(1,2,2)2)Request1(1,0,2)≤Available(3,3,2)3)系統(tǒng)試為P1分配資源，并修改相應(yīng)的向量Available、Need、Allocation44(2)P1請(qǐng)求資源Request1(1,0,2)P1P1請(qǐng)求資源Request1(1,0,2)時(shí)的資源分配表(302)(020)(230)45P1請(qǐng)求資源Request1(1,0,2)時(shí)的資源分配表(3由安全性檢查分析得知：此時(shí)刻存在著一個(gè)安全序列{P1,P3,P4,P2,P0}，故系統(tǒng)是安全的，可以立即將P1所申請(qǐng)的資源分配給它。4)利用安全性算法檢查資源分配后此時(shí)系統(tǒng)是否安全P1請(qǐng)求資源Request1(1,0,2)時(shí)的安全性檢查表230532true532743true743745true7451047true10471057true46由安全性檢查分析得知：此時(shí)刻存在著一個(gè)安全序列{P1（3）P4請(qǐng)求資源Request4(3,3,0)

P4發(fā)出請(qǐng)求向量Request4(3,3,0)，系統(tǒng)按銀行家算法進(jìn)行檢查:1)Request4(3,3,0)≤Need4(4,3,1)2)Request4(3,3,0)>Available(2,3,0)，表示資源不夠，則讓P4等待47（3）P4請(qǐng)求資源Request4(3,3,0)P4發(fā)出(4)P0請(qǐng)求資源Request0(0,2,0)

P0發(fā)出請(qǐng)求向量Request0(0,2,0)，系統(tǒng)按銀行家算法進(jìn)行檢查:1)Request0(0,2,0)≤Need0(7,4,3)2)Request0(0,2,0)≤Available(2,3,0)3)系統(tǒng)試為P0分配資源，并修改相應(yīng)的向量。48(4)P0請(qǐng)求資源Request0(0,2,0)P0發(fā)表5P0請(qǐng)求資源Request0(0,2,0)時(shí)的資源分配表[210][030][723]

4)進(jìn)行安全性檢查資源分配后此時(shí)系統(tǒng)是否安全，因Avaliable(2,1,0)已不能滿足任何進(jìn)程需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。49表5P0請(qǐng)求資源Request0(0,2,0)時(shí)的資源分第四章存儲(chǔ)管理

50第四章存儲(chǔ)管理

504.2連續(xù)分配存儲(chǔ)管理方式連續(xù)分配方式（分區(qū)技術(shù)）：指為一個(gè)用戶程序分配一片連續(xù)的內(nèi)存空間。

單一連續(xù)分區(qū)分配（靜態(tài)分區(qū)技術(shù)）：僅用于單用戶單任務(wù)系統(tǒng)固定分區(qū)分配（靜態(tài)分區(qū)技術(shù)）：可用于多道系統(tǒng)可變分區(qū)分配（動(dòng)態(tài)分區(qū)技術(shù)）可重定位可變分區(qū)分配（動(dòng)態(tài)分區(qū)技術(shù)）：引入了動(dòng)態(tài)重定位和內(nèi)存緊湊技術(shù)伙伴系統(tǒng)（動(dòng)態(tài)分區(qū)技術(shù)）靜態(tài)分區(qū)：作業(yè)裝入時(shí)一次完成，分區(qū)大小及邊界在運(yùn)行時(shí)不能改變。動(dòng)態(tài)分區(qū)：根據(jù)作業(yè)大小動(dòng)態(tài)地建立分區(qū)，分區(qū)的大小、數(shù)目可變。514.2連續(xù)分配存儲(chǔ)管理方式連續(xù)分配方式（分區(qū)技術(shù)）：指為2、分區(qū)分配算法為了將一個(gè)作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法從空閑分區(qū)表（鏈）中選出一個(gè)滿足作業(yè)需求的分區(qū)分配給作業(yè)。目前常用分配算法有：首次適應(yīng)算法（First-Fit）循環(huán)首次適應(yīng)算法（Next-Fit）最佳適應(yīng)算法（Best-Fit）最壞適應(yīng)算法（Worst-Fit）按地址遞增的次序排列。按容量大小遞增的次序排列。按容量大小遞減的次序排列。522、分區(qū)分配算法為了將一個(gè)作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法4.3基本分頁(yè)存儲(chǔ)管理方式基本分頁(yè)存儲(chǔ)管理方式在分頁(yè)存儲(chǔ)管理方式中，如果不具備頁(yè)面對(duì)換功能，不支持虛擬存儲(chǔ)器功能，這種存儲(chǔ)管理方式稱為純分頁(yè)或基本分頁(yè)存儲(chǔ)管理方式。在調(diào)度作業(yè)運(yùn)行時(shí)，必須將它的所有頁(yè)面一次調(diào)入內(nèi)存，但邏輯上連續(xù)的各個(gè)頁(yè)所對(duì)應(yīng)的內(nèi)存塊可以不連續(xù)。特殊的固定分區(qū)+離散分配534.3基本分頁(yè)存儲(chǔ)管理方式基本分頁(yè)存儲(chǔ)管理方式53三、地址結(jié)構(gòu)邏輯地址：例：地址長(zhǎng)為32位，其中0-11位為頁(yè)內(nèi)地址，即每頁(yè)的大小為212=4KB；12-31位為頁(yè)號(hào)，地址空間最多允許有220=1M頁(yè)。物理地址：例：地址長(zhǎng)為22位，其中0-11位為塊內(nèi)地址，即每塊的大小為212=4KB，與頁(yè)相等；12-21位為塊號(hào)，內(nèi)存地址空間最多允許有210=1K塊。

3112110頁(yè)號(hào)p位移量w2112110塊號(hào)b塊內(nèi)位移d54三、地址結(jié)構(gòu)邏輯地址：31

給定一個(gè)邏輯地址空間中的地址為A，頁(yè)面的大小為L(zhǎng)，則頁(yè)號(hào)P和頁(yè)內(nèi)地址d可按下式求得：

其中，INT是整除函數(shù)，mod是取余函數(shù)。例如，系統(tǒng)的頁(yè)面大小為1KB，設(shè)A=2170B，則由上式可以求得P=2，d=122。

已知邏輯地址求頁(yè)號(hào)和頁(yè)內(nèi)地址頁(yè)從0開始編號(hào)三、地址結(jié)構(gòu)55給定一個(gè)邏輯地址空間中的地址為A，頁(yè)面的大小為L(zhǎng)，則頁(yè)號(hào)三、地址結(jié)構(gòu)例題例：設(shè)有一頁(yè)式存儲(chǔ)管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁(yè)，每頁(yè)2048B，內(nèi)存總共有8個(gè)存儲(chǔ)塊，試問邏輯地址至少應(yīng)為多少位？?jī)?nèi)存空間有多大？解：（1）頁(yè)式存儲(chǔ)管理系統(tǒng)的邏輯地址為：其中頁(yè)內(nèi)地址表每頁(yè)的大小即2048B=2*1024B=211B，所以頁(yè)內(nèi)地址為11位；頁(yè)號(hào)表最多允許的頁(yè)數(shù)即16頁(yè)=24頁(yè)，所以頁(yè)號(hào)為4位。故邏輯地址至少應(yīng)為15位。（2）物理地址為：其中塊內(nèi)地址表每塊的大小與頁(yè)大小相等，所以塊內(nèi)地址也為11位；其中塊號(hào)表內(nèi)存空間最多允許的塊數(shù)即8塊=23塊，所以塊號(hào)為3位。故內(nèi)存空間至少應(yīng)為14位，即214=16KB。56三、地址結(jié)構(gòu)例題例：設(shè)有一頁(yè)式存儲(chǔ)管理系統(tǒng)，向用戶提供的邏輯四、地址變換例題例1：若在一分頁(yè)存儲(chǔ)管理系統(tǒng)中，某作業(yè)的頁(yè)表如下表所示，已知頁(yè)面大小為1024B，試將十進(jìn)制邏輯地址1011，2148，5012轉(zhuǎn)化為相應(yīng)的物理地址。57四、地址變換例題例1：若在一分頁(yè)存儲(chǔ)管理系統(tǒng)中，某作業(yè)的頁(yè)表四、地址變換例題解：設(shè)頁(yè)號(hào)為P，頁(yè)內(nèi)位移為W，邏輯地址為A，內(nèi)存地址為M，頁(yè)面大小為L(zhǎng)，則P=int(A/L)W=AmodL對(duì)于邏輯地址1011P=int(1011/1024)=0W=1011mod1024=1011A=1011=(0,1011)查頁(yè)表第0頁(yè)在第2塊，所以物理地址為M=1024*2+1011=3059。58四、地址變換例題解：設(shè)頁(yè)號(hào)為P，頁(yè)內(nèi)位移為W，邏輯地址為A，四、地址變換例題對(duì)于邏輯地址為2148P=int(2148/1024)=2W=2148mod1024=100A=2148=(2,100)查頁(yè)表第2頁(yè)在第1塊，所以物理地址為M=1024*1+100=1124。對(duì)于邏輯地址5012P=int(5012/1024)=4W=5012mod1024=916因頁(yè)號(hào)超過頁(yè)表長(zhǎng)度，該邏輯地址非法。59四、地址變換例題對(duì)于邏輯地址為214859有效訪問內(nèi)存的時(shí)間

T=PTLB*（TTLB+TM）+（1-PTLB

）*（TTLB+2TM

）其中,PTLB為快表的命中率,TTLB為快表的訪問時(shí)間,TM為內(nèi)存的訪問時(shí)間具有快表的地址變換機(jī)構(gòu)938220頁(yè)表長(zhǎng)度頁(yè)表始址45224528823120+<頁(yè)表寄存器邏輯地址物理地址越界中斷頁(yè)合法頁(yè)表快表TTLB：訪問快表但沒有命中2TM：分別訪問頁(yè)表和數(shù)據(jù)60有效訪問內(nèi)存的時(shí)間具有快表的地址變換機(jī)構(gòu)938220頁(yè)表長(zhǎng)度例：

有一頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中。（1）如果對(duì)主存的一次存取需要100ns，試問實(shí)現(xiàn)一次頁(yè)面訪問的存取時(shí)間是多少？（2）如果系統(tǒng)加有快表，對(duì)快表的一次存取需要20ns,若平均命中率為85%，試問此時(shí)的存取時(shí)間為多少？解：（1）頁(yè)表放主存中，則實(shí)現(xiàn)一次頁(yè)面訪問需2次訪問主存，一次是訪問頁(yè)表，確定所存取頁(yè)面的物理塊，從而得到其物理地址，一次根據(jù)物理地址存取頁(yè)面數(shù)據(jù)。所以實(shí)現(xiàn)一次頁(yè)面訪問的存取時(shí)間為：100ns*2=200ns（2）系統(tǒng)有快表，則實(shí)現(xiàn)一次頁(yè)面訪問的存取時(shí)間為：

0.85*(20ns+100ns)+(1-0.85)*(20ns+2*100ns)=135ns

有效內(nèi)存訪問時(shí)間例題61例：有一頁(yè)式系統(tǒng)，其頁(yè)表存放在主存中。有效內(nèi)存訪問時(shí)間例題在為作業(yè)分配內(nèi)存時(shí)以段為單位，分配一段連續(xù)的物理地址空間；段間不必連續(xù)。作業(yè)的邏輯地址空間是二維的，其邏輯地址由段號(hào)和段內(nèi)地址組成。地址映射需要CPU的硬件支持（地址變換機(jī)構(gòu)）注：內(nèi)存分配分頁(yè)管理中，邏輯地址是線性地址（一維）。分段管理中，段號(hào)S和段內(nèi)位移d不能形成一個(gè)線性地址，因?yàn)樗鼘?shí)際上是代表著段長(zhǎng)和段內(nèi)位移兩個(gè)變量。由于這兩個(gè)變量沒有特定的限制范圍而無(wú)法用一個(gè)變量來(lái)替代，因此分段管理的邏輯地址是二維地址。62在為作業(yè)分配內(nèi)存時(shí)以段為單位，分配一段連續(xù)的物理地址空間；段例1、在一個(gè)段式存儲(chǔ)管理系統(tǒng)中，其段表為：段號(hào)內(nèi)存起始地址段長(zhǎng)02105001235020210090313505904193895試求右表中邏輯地址對(duì)應(yīng)的物理地址是什么？解：邏輯地址為：邏輯地址對(duì)應(yīng)的物理地址為：210+430=640。邏輯地址因?yàn)槎蝺?nèi)地址120>段長(zhǎng)90，所以該段為非法段。分段地址變換例題63例1、在一個(gè)段式存儲(chǔ)管理系統(tǒng)中，其段表為：分段地址變換例題6分頁(yè)和分段的主要區(qū)別二者優(yōu)點(diǎn)的結(jié)合----段頁(yè)式存儲(chǔ)管理64分頁(yè)和分段的主要區(qū)別二者優(yōu)點(diǎn)的結(jié)合----段頁(yè)式存儲(chǔ)管理64存儲(chǔ)管理策略分類存儲(chǔ)管理：實(shí)存管理分區(qū)（Partitioning）（連續(xù)分配方式）（包括固定分區(qū)、可變分區(qū)和伙伴系統(tǒng)）分頁(yè)（Paging）分段（Segmentation）段頁(yè)式（Segmentationwithpaging）虛存管理請(qǐng)求分頁(yè)（Demandpaging）--主流技術(shù)請(qǐng)求分段（Demandsegmentation）請(qǐng)求段頁(yè)式（DemandSWP）離散分配65存儲(chǔ)管理策略分類存儲(chǔ)管理：離散分配65虛擬存儲(chǔ)器的概念虛擬存儲(chǔ)技術(shù)的種類請(qǐng)求分頁(yè)請(qǐng)求分段請(qǐng)求段頁(yè)式速度和容量虛擬存儲(chǔ)量的擴(kuò)大是以犧牲CPU工作時(shí)間以及內(nèi)外存交換時(shí)間為代價(jià)。虛擬存儲(chǔ)器的容量取決于主存與輔存的容量，最大容量是由計(jì)算機(jī)的地址結(jié)構(gòu)決定。虛擬存儲(chǔ)器的邏輯地址空間理論上不受物理存儲(chǔ)器的限制。如32位機(jī)器，虛擬存儲(chǔ)器的最大容量就是4G，再大CPU無(wú)法直接訪問。66虛擬存儲(chǔ)器的概念虛擬存儲(chǔ)技術(shù)的種類66二、虛擬存儲(chǔ)器的實(shí)現(xiàn)方法1、分頁(yè)請(qǐng)求系統(tǒng)在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)器系統(tǒng)。它允許只裝入若干頁(yè)的用戶程序和數(shù)據(jù)，便可啟動(dòng)運(yùn)行，以后在硬件支持下通過調(diào)頁(yè)功能和置換頁(yè)功能，陸續(xù)將要運(yùn)行的頁(yè)面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)面換到外存上，置換時(shí)以頁(yè)面為單位。系統(tǒng)須設(shè)置相應(yīng)的硬件支持和軟件：（1）硬件支持：請(qǐng)求分頁(yè)的頁(yè)表機(jī)制、缺頁(yè)中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)。（2）軟件：請(qǐng)求調(diào)頁(yè)功能和頁(yè)置換功能的軟件。67二、虛擬存儲(chǔ)器的實(shí)現(xiàn)方法1、分頁(yè)請(qǐng)求系統(tǒng)674.7請(qǐng)求分頁(yè)中的頁(yè)面置換算法常用的頁(yè)面置換算法：最佳置換算法OPT：選擇永遠(yuǎn)不再需要的頁(yè)面或最長(zhǎng)時(shí)間以后才需要訪問的頁(yè)面予以淘汰。先進(jìn)先出置換算法FIFO：選擇先進(jìn)入內(nèi)存的頁(yè)面予以淘汰。最近最久未使用置換算法LRU：選擇最近一段時(shí)間最長(zhǎng)時(shí)間沒有被訪問過的頁(yè)面予以淘汰。684.7請(qǐng)求分頁(yè)中的頁(yè)面置換算法常用的頁(yè)面置換算法：最佳置換算法(Optimal,OPT)例

假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，進(jìn)程運(yùn)行時(shí)的頁(yè)面走向?yàn)?,2,3,4,1,2,5,1,2,3,4,5，開始時(shí)3個(gè)物理塊均為空，計(jì)算采用最佳置換頁(yè)面淘汰算法時(shí)的缺頁(yè)率？注：實(shí)際上這種算法無(wú)法實(shí)現(xiàn)，因?yàn)轫?yè)面訪問的未來(lái)順序很難精確預(yù)測(cè)，但可用該算法評(píng)價(jià)其它算法的優(yōu)劣。1缺缺缺缺缺缺缺12312121212121212333444442555555(7/12)最佳置換算法：選擇永遠(yuǎn)不再需要的頁(yè)面或最長(zhǎng)時(shí)間以后才需要訪問的頁(yè)面予以淘汰。69最佳置換算法(Optimal,OPT)例假定系統(tǒng)為某進(jìn)程分先進(jìn)先出置換算法(FIFO)例題1、假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，進(jìn)程運(yùn)行時(shí)的頁(yè)面走向?yàn)?,2,3,4,1,2,5,1,2,3,4,5，開始時(shí)3個(gè)物理塊均為空，計(jì)算采用先進(jìn)先出頁(yè)面淘汰算法時(shí)的缺頁(yè)率？(9/12)70先進(jìn)先出置換算法(FIFO)例題1、假定系統(tǒng)為某進(jìn)程分配了3最近最久未使用算法LRU例最近最久未使用算法（LRU,LeastRecentlyUsed）例：假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，進(jìn)程運(yùn)行時(shí)的頁(yè)面走向?yàn)?,2,3,4,1,2,5,1,2,3,4,5，開始時(shí)3個(gè)物理塊均為空，計(jì)算采用最近最久未使用頁(yè)面淘汰算法時(shí)的缺頁(yè)率？(10/12)最近最久未使用置換算法：選擇最近一段時(shí)間最長(zhǎng)時(shí)間沒有被訪問過的頁(yè)面予以淘汰。71最近最久未使用算法LRU例最近最久未使用算法（LRU,Le第五章設(shè)備管理

72第五章設(shè)備管理

725.5.4.SPOOLing技術(shù)SPOOLing（SimultaneousPeripheralOperationsOn-Line，外部設(shè)備聯(lián)機(jī)并行操作），也稱假脫機(jī)技術(shù)。SPOOLing是指在多道程序的環(huán)境下，利用多道程序中的一道或兩道程序來(lái)模擬外圍控制機(jī)，從而在聯(lián)機(jī)的條件下實(shí)現(xiàn)脫機(jī)I/O的功能。735.5.4.SPOOLing技術(shù)SPOOLing（Sim5.5.4.SPOOLing技術(shù)設(shè)計(jì)思想：可以用常駐內(nèi)存的進(jìn)程去模擬一臺(tái)外圍機(jī)，從而用一臺(tái)主機(jī)就可完成脫機(jī)技術(shù)中需用三臺(tái)計(jì)算機(jī)完成的工作。功能:

把獨(dú)占設(shè)備改造為邏輯共享設(shè)備。把一臺(tái)物理I/O設(shè)備虛擬為多臺(tái)邏輯I/O設(shè)備。組成：專門負(fù)責(zé)I/O的常駐內(nèi)存的進(jìn)程；輸入井、輸出井；輸入緩沖區(qū)、輸出緩沖區(qū)。745.5.4.SPOOLing技術(shù)設(shè)計(jì)思想：可以用常駐內(nèi)存1、磁盤性能磁盤性能簡(jiǎn)述數(shù)據(jù)的組織磁盤結(jié)構(gòu)：磁道、柱面、扇區(qū)磁盤物理塊的地址：磁頭號(hào)、柱面號(hào)、扇區(qū)號(hào)存儲(chǔ)容量＝磁頭（盤面）數(shù)×磁道（柱面）數(shù)×每道扇區(qū)數(shù)×每扇區(qū)字節(jié)數(shù)假定一塊硬盤磁頭數(shù)為4，柱面數(shù)為2048，每個(gè)磁道有扇區(qū)2048，每個(gè)扇區(qū)記錄1KB（字節(jié)），該硬盤儲(chǔ)存容量為：4×2048×2048×1024/1024/1024/1024=16G4×2048×2048×1024/1000/1000/1000=17.2G（廠家）751、磁盤性能磁盤性能簡(jiǎn)述751、磁盤性能訪問時(shí)間尋道時(shí)間Ts：將磁頭從當(dāng)前位置移到指定磁道所經(jīng)歷的時(shí)間Ts=m×n+s。s為啟動(dòng)磁臂的時(shí)間，n為移動(dòng)的磁道數(shù)，m為常數(shù)。旋轉(zhuǎn)延遲時(shí)間Tr：指定扇區(qū)移動(dòng)到磁頭下面所經(jīng)歷的時(shí)間。設(shè)每秒r轉(zhuǎn)，則Tr＝1/2r（均值）傳輸時(shí)間Tt：將扇區(qū)上的數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時(shí)間Tt＝b/rN。其中b：讀寫字節(jié)數(shù)，N：每道上的字節(jié)數(shù)?？刂破鲿r(shí)間Tc訪問時(shí)間Ta：Ta=m×n+s+1/2r+b/rN+Tc761、磁盤性能訪問時(shí)間761、磁盤性能例：假設(shè)磁盤空閑（沒有排隊(duì)延遲）。平均尋道時(shí)間是9ms，傳輸速度是4MB/s，轉(zhuǎn)速是7200rpm，控制器的開銷是1ms。問讀或?qū)懸粋€(gè)512字節(jié)的扇區(qū)的平均時(shí)間是多少？解：訪問時(shí)間=尋道時(shí)間+旋轉(zhuǎn)延遲時(shí)間+傳輸時(shí)間+控制器時(shí)間訪問時(shí)間=9ms+0.5/7200(rpm)+0.5(k)/4(MB/s)+1ms=9ms+0.5/7200/60/1000+0.5/(4×1024/1000)+1ms≈9+4.2+0.122+1=14.322ms1秒等于1000毫秒771、磁盤性能例：假設(shè)磁盤空閑（沒有排隊(duì)延遲）。平均尋道時(shí)間磁盤調(diào)度算法磁盤調(diào)度算法早期的磁盤調(diào)度算法先來(lái)先服務(wù)FCFS最短尋道時(shí)間優(yōu)先SSTF掃描算法掃描(SCAN)/電梯(LOOK)算法循環(huán)掃描(CSCAN)算法本教材不區(qū)分SCAN算法和LOOK算法，我們做題時(shí)都按LOOK算法解決（不掃描到頭?。?8磁盤調(diào)度算法磁盤調(diào)度算法78FCFS先來(lái)先服務(wù)按進(jìn)程請(qǐng)求訪問磁盤的先后次序進(jìn)行調(diào)度磁頭臂來(lái)回反復(fù)移動(dòng)，增長(zhǎng)了等待時(shí)間，對(duì)機(jī)械結(jié)構(gòu)不利79FCFS先來(lái)先服務(wù)按進(jìn)程請(qǐng)求訪問磁盤的先后次序進(jìn)行調(diào)度磁最短尋道時(shí)間優(yōu)先（SSTF）選擇從當(dāng)前磁頭位置所需尋道時(shí)間最短的請(qǐng)求。可能使一些申請(qǐng)者在較長(zhǎng)時(shí)間內(nèi)得不得服務(wù)的機(jī)會(huì)80最短尋道時(shí)間優(yōu)先（SSTF）選擇從當(dāng)前磁頭位置所需尋道時(shí)間最假定磁頭向磁道號(hào)增加的方向移動(dòng)。Scan/Look算法81假定磁頭向磁道號(hào)增加的方向移動(dòng)。Scan/Look算法81第六章文件管理

82第六章文件管理

826.2文件邏輯結(jié)構(gòu)對(duì)任一文件存在著兩種形式的結(jié)構(gòu)：文件的邏輯結(jié)構(gòu)（文件組織）從用戶觀點(diǎn)出發(fā)，所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它獨(dú)立于物理特性。順序文件、索引文件、索引順序文件文件的物理結(jié)構(gòu)（文件的存儲(chǔ)結(jié)構(gòu)）從系統(tǒng)的觀點(diǎn)出發(fā)，是指文件在外存上的存儲(chǔ)組織形式，與存儲(chǔ)介質(zhì)的存儲(chǔ)性能有關(guān)。順序文件、鏈接文件、索引文件注：文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)都將影響文件的檢索速度。836.2文件邏輯結(jié)構(gòu)對(duì)任一文件存在著兩種形式的結(jié)構(gòu)：83多級(jí)索引分配如果每個(gè)盤塊的大小為1KB，每個(gè)盤塊號(hào)占4個(gè)字節(jié)，則在一個(gè)索引塊中可存放256個(gè)盤塊號(hào)。在兩級(jí)索引時(shí)，最多可存放的盤塊號(hào)總數(shù)N=256×256=64K個(gè)，即所允許的文件最大長(zhǎng)度為64MB。如果每個(gè)盤塊的大小為4KB，每個(gè)盤塊號(hào)占4個(gè)字節(jié)，單級(jí)索引時(shí)所允許的文件最大長(zhǎng)度為如果采用兩級(jí)級(jí)索引時(shí)最大文件長(zhǎng)度為1024×4KB=4MB1024×1024×4KB=4GB84多級(jí)索引分配如果每個(gè)盤塊的大小為1KB，每個(gè)盤塊號(hào)占4個(gè)字混合索引分配直接地址(多個(gè))一次間接地址二次間接地址混合索引分配：地址項(xiàng)既采用了直接地址，又采用了多級(jí)索引分配方式。索引結(jié)點(diǎn)（FCB主部）索引塊85混合索引分配直接地址(多個(gè))一次間接地址二次間接地址混合索引練習(xí)題例：存放在某個(gè)磁盤上的文件系統(tǒng)，采用混合索引分配方式，其FCB中共有13個(gè)地址項(xiàng)（索引項(xiàng)），第0-9個(gè)地址項(xiàng)為直接地址，第10個(gè)地址項(xiàng)為一次間接地址，第11個(gè)地址項(xiàng)為二次間接地址，第12個(gè)地址項(xiàng)為三次間接地址。如果每個(gè)盤塊的大小為512字節(jié)，盤塊號(hào)需要用3個(gè)字節(jié)來(lái)描述，而每個(gè)盤塊最多存放170個(gè)盤塊地址。問：（1）該文件系統(tǒng)允許文件的最大長(zhǎng)度是多少？（2）將文件的字節(jié)偏移量5000、15000、150000轉(zhuǎn)換為物理塊號(hào)和塊內(nèi)偏移量。（3）假設(shè)某個(gè)文件的FCB己在內(nèi)存，但其他信息均在外存，為了訪問該文件中某個(gè)位置的內(nèi)容，最少需要幾次訪問磁盤，最多需要幾次訪問磁盤？512/3≈17086練習(xí)題例：存放在某個(gè)磁盤上的文件系統(tǒng)，采用混合索引分配方式，練習(xí)題解：（1）該文件系統(tǒng)中一個(gè)文件的最大長(zhǎng)度可達(dá)：

10+170+170×170+170×170×170=4942080塊，共4942080×512字節(jié)=2471040KB

≈2.36GB或用如下解法：直接索引項(xiàng)可管理上限：10×0.5KB=5KB；一次間接索引項(xiàng)可管理上限：170×0.5KB=85KB；二次間接索引項(xiàng)可管理上限：170×170×0.5KB=14450KB；三次間接索引項(xiàng)可管理上限：170×170×170×0.5KB=2456500KB；可管理文件上限：5KB+85KB+14450KB+2456500KB。87練習(xí)題解：（1）該文件系統(tǒng)中一個(gè)文件的最大長(zhǎng)度可達(dá)：87練習(xí)題解：（2）

5000／512得到商為9，余數(shù)為392，即字節(jié)偏移量5000對(duì)應(yīng)的邏輯塊號(hào)為9，塊內(nèi)偏移量為392。由于9<10，故可直接從該文件的FCB的第9個(gè)地址項(xiàng)處得到物理盤塊號(hào)，塊內(nèi)偏移量為392。15000／512得到商為29，余數(shù)為152，即字節(jié)偏移量15000對(duì)應(yīng)的邏輯塊號(hào)為29，塊內(nèi)偏移量為152。由于10<29<10+170，而29-10=19，故可從FCB的第10個(gè)地址項(xiàng)，即一次間址項(xiàng)中得到一次間址塊的地址；并從一次間址塊的第19項(xiàng)（即該塊的第57~59這3個(gè)字節(jié)）中獲得對(duì)應(yīng)的物理盤塊號(hào)，塊內(nèi)偏移量為152。

盤塊號(hào)用3個(gè)字節(jié)描述88練習(xí)題解：（2）盤塊號(hào)用3個(gè)字節(jié)描述88練習(xí)題150000／512得到商為292，余數(shù)為496，即字節(jié)偏移量150000對(duì)應(yīng)的邏輯塊號(hào)為292，塊內(nèi)偏移量為496。由于10+170<292<10+170+170×170，而292-(10+170)=112，112／170得到商為0，余數(shù)為112，故可從FCB的第11個(gè)地址項(xiàng)，即二次間址項(xiàng)中得到二次間址塊的地址，并從二次間址塊的第0項(xiàng)中獲得一個(gè)一次間址塊的地址，再?gòu)倪@一次間址塊的第112項(xiàng)中獲得對(duì)應(yīng)的物理盤塊號(hào)，塊內(nèi)偏移量為496。89練習(xí)題150000／512得到商為292，余數(shù)為496，即字練習(xí)題

（3）假設(shè)某個(gè)文件的FCB己在內(nèi)存，但其他信息均在外存，為了訪問該文件中某個(gè)位置的內(nèi)容，最少需要幾次訪問磁盤，最多需要幾次訪問磁盤？解：由于文件的FCB己在內(nèi)存，為了訪問文件中某個(gè)位置的內(nèi)容，最少需要1次訪問磁盤（即可通過直接地址直接讀文件盤塊），最多需要4次訪問磁盤（第一次是讀三次間址塊，第二次是讀二次間址塊，第三次是讀一次間址塊，第四次是讀文件盤塊）。90練習(xí)題（3）假設(shè)某個(gè)文件的FCB己在內(nèi)存，但其他信息均在文件控制塊（FCB）文件目錄文件目錄是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識(shí)系統(tǒng)中的文件及其物理地址，將文件名映射到外存物理位置，供檢索時(shí)使用。目錄項(xiàng)構(gòu)成文件目錄的項(xiàng)目（目錄項(xiàng)就是FCB）文件目錄：文件控制塊的有序集合。目錄文件為了實(shí)現(xiàn)對(duì)文件目錄的管理，通常將文件目錄以文件的形式保存在外存，這個(gè)文件就叫目錄文件。文件目錄和目錄文件是同一事物的兩種稱謂。從用途角度來(lái)看稱其為文件目錄，從實(shí)現(xiàn)角度來(lái)看稱其為目錄文件。91文件控制塊（FCB）文件目錄文件目錄和目錄文件是同一事物的兩索引結(jié)點(diǎn)索引結(jié)點(diǎn)引入文件目錄通常是存放在磁盤上的，當(dāng)文件很多時(shí)，文件目錄可能要占用大量的盤塊。在查找目錄的過程中，先將存放目錄文件的第一個(gè)盤塊中的目錄調(diào)入內(nèi)存，然后把用戶所給定的文件名與目錄項(xiàng)中的文件名逐一比較。若未找到指定文件，便再將下一個(gè)盤塊中的目錄項(xiàng)調(diào)入內(nèi)存。設(shè)目錄文件所占用的盤塊數(shù)為N，按此方法查找，則查找一個(gè)目錄項(xiàng)平均需要調(diào)入盤塊(N+1)/2次。92索引結(jié)點(diǎn)索引結(jié)點(diǎn)引入92解：在引入索引節(jié)點(diǎn)前，256個(gè)目錄項(xiàng)的目錄總共需要占用256×64／512=32個(gè)盤塊。在目錄中檢索到一個(gè)文件平均啟動(dòng)磁盤次數(shù)為（1+32）／2=16.5。

在引入索引節(jié)點(diǎn)后，每個(gè)目錄項(xiàng)中只需存放文件名和索引節(jié)點(diǎn)的編號(hào)，因此256個(gè)目錄項(xiàng)的目錄總共需要占用256×（8+2）／512=5個(gè)盤塊。因此，找到匹配的目錄項(xiàng)平均需要啟動(dòng)3次磁盤；而得到索引結(jié)點(diǎn)編號(hào)后還需啟動(dòng)磁盤將對(duì)應(yīng)文件的索引結(jié)點(diǎn)讀入內(nèi)存，故平均需要啟動(dòng)磁盤4次。文件控制塊和索引結(jié)點(diǎn)93解：在引入索引節(jié)點(diǎn)前，256個(gè)目錄項(xiàng)的目錄總共需要占用2566.5文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理可采用連續(xù)分配和離散分配方式。內(nèi)存分配基本不采用連續(xù)分配方式。外存管理中，小文件經(jīng)常采用連續(xù)分配方式，大文件采用離散分配方式。存儲(chǔ)空間的管理方法空閑表法和空閑鏈法位示圖法成組鏈接法文件存儲(chǔ)器空間布局946.5文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理可采用連續(xù)分配和6.5.2位示圖法位示圖（二維）利用二進(jìn)制的一位（bit）來(lái)表示磁盤中一個(gè)盤塊的使用情況。每個(gè)字節(jié)的每一位都對(duì)應(yīng)了一個(gè)物理塊的狀態(tài)。當(dāng)該位取1時(shí)，表示對(duì)應(yīng)的物理塊已分配；取0時(shí)表示該物理塊未分配?？臻e空間表現(xiàn)為位圖或位向量。特點(diǎn)：占空間少，可放入內(nèi)存，易于訪問。956.5.2位示圖法位示圖（二維）95位示圖法12345678910123456796位示圖法1234練習(xí)題1例1：設(shè)某系統(tǒng)的磁盤有500塊，塊號(hào)為：0，1，2，3，…，499。（1）若用位示圖法管理這500塊的盤空間，當(dāng)字長(zhǎng)為32位時(shí)，此位示圖占了幾個(gè)字？（2）第i字的第j位對(duì)應(yīng)的塊號(hào)是多少？（其中：i=0，1，2，…，j=0，1，2，3，…）解：（1）位示圖法就是在內(nèi)存用一些字建立一張位示圖，用其中的每一位表示一個(gè)盤塊的使用情況，通常用“1”表示占用，“0”表示空閑。因此，本問題中位示圖所占的字?jǐn)?shù)為：500／32=15.625≈16。（2）第i字的第j位對(duì)應(yīng)的塊號(hào)N=32*i+j。97練習(xí)題1例1：設(shè)某系統(tǒng)的磁盤有500塊，塊號(hào)為：0，1，2，提問與解答環(huán)節(jié)Questionsandanswers98提問與解答環(huán)節(jié)98添加標(biāo)題添加標(biāo)題添加標(biāo)題添加標(biāo)題此處結(jié)束語(yǔ)點(diǎn)擊此處添加段落文本.您的內(nèi)容打在這里，或通過復(fù)制您的文本后在此框中選擇粘貼并選擇只保留文字99添加標(biāo)題添加添加添加標(biāo)題此處結(jié)束語(yǔ)點(diǎn)擊此處添加段落文本.感謝聆聽Theusercandemonstrateonaprojectororcomputer,orprintthepresentationandmakeitintoafilm講師：XXXX日期：20XX.X月100感謝聆聽講師：XXXX日期：20XX.X月100計(jì)算機(jī)操作系統(tǒng)復(fù)習(xí)

2022年11月25日101計(jì)算機(jī)操作系統(tǒng)復(fù)習(xí)

2022年11月22日1標(biāo)題添加點(diǎn)擊此處輸入相關(guān)文本內(nèi)容點(diǎn)擊此處輸入相關(guān)文本內(nèi)容前言點(diǎn)擊此處輸入相關(guān)文本內(nèi)容標(biāo)題添加點(diǎn)擊此處輸入相關(guān)文本內(nèi)容102標(biāo)題添加點(diǎn)擊此處輸入相點(diǎn)擊此處輸入前言點(diǎn)擊此處輸入標(biāo)題添加點(diǎn)課程主要內(nèi)容教材內(nèi)容操作系統(tǒng)引論（第1章）進(jìn)程管理（第2章）處理機(jī)調(diào)度與死鎖（第3章）存儲(chǔ)管理（第4章）設(shè)備管理（第5章）文件管理（第6章）UNIX系統(tǒng)內(nèi)核結(jié)構(gòu)(第10章）103課程主要內(nèi)容教材內(nèi)容3計(jì)算題類型總結(jié)利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步處理機(jī)調(diào)度算法（周轉(zhuǎn)時(shí)間）銀行家算法分區(qū)存儲(chǔ)管理算法邏輯地址物理地址變換請(qǐng)求分頁(yè)中的頁(yè)面置換算法磁盤訪問時(shí)間磁盤調(diào)度算法（平均移道數(shù)）混合索引分配文件控制塊和索引結(jié)點(diǎn)位示圖104計(jì)算題類型總結(jié)利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步4第一章操作系統(tǒng)引論

105第一章操作系統(tǒng)引論

51.3操作系統(tǒng)的基本特征并發(fā)性(Concurrence)共享性(Sharing)虛擬性(Virtual)異步性(Asynchronism)基本特征:最重要特性，其它三種特性以此為前提。1061.3操作系統(tǒng)的基本特征并發(fā)性(Concurrence)操作系統(tǒng)的形成單道批處理系統(tǒng)多道批處理系統(tǒng)操作系統(tǒng)的形成在多道程序系統(tǒng)中增設(shè)一組軟件以有效加以解決，同時(shí)增設(shè)方便用戶使用計(jì)算機(jī)的軟件，這樣便形成了操作系統(tǒng)。操作系統(tǒng)：是一組控制和管理計(jì)算機(jī)硬件和軟件資源，合理地對(duì)各類作業(yè)進(jìn)行調(diào)度，以及方便用戶使用的程序集合。107操作系統(tǒng)的形成單道批處理系統(tǒng)操作系統(tǒng)：是一組控制和管理計(jì)算機(jī)操作系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)傳統(tǒng)的操作系統(tǒng)結(jié)構(gòu)無(wú)結(jié)構(gòu)操作系統(tǒng)模塊化OS結(jié)構(gòu)分層式OS結(jié)構(gòu)現(xiàn)代操作系統(tǒng)結(jié)構(gòu)微內(nèi)核的OS結(jié)構(gòu)：將客戶/服務(wù)器技術(shù)、面向?qū)ο蠹夹g(shù)用于OS中所形成的OS結(jié)構(gòu)。108操作系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)傳統(tǒng)的操作系統(tǒng)結(jié)構(gòu)8第二章進(jìn)程管理

109第二章進(jìn)程管理

92、進(jìn)程process的基本特征

（1）結(jié)構(gòu)特征從結(jié)構(gòu)上看，每個(gè)進(jìn)程（進(jìn)程實(shí)體）都是由程序段、數(shù)據(jù)段及進(jìn)程控制塊（PCB）組成。

（2）動(dòng)態(tài)性

進(jìn)程的實(shí)質(zhì)是程序在處理機(jī)上的一次執(zhí)行過程，因此是動(dòng)態(tài)性的。所以動(dòng)態(tài)性是進(jìn)程的最基本的特征。同時(shí)動(dòng)態(tài)性還表現(xiàn)在進(jìn)程則是有生命期的，它因創(chuàng)建而產(chǎn)生，因調(diào)度而執(zhí)行，因得不到資源而暫停，因撤消而消亡。進(jìn)程的定義、特征1102、進(jìn)程process的基本特征進(jìn)程的定義、特征10

進(jìn)程在運(yùn)行期間并非固定處于某個(gè)狀態(tài)，而是不斷從一個(gè)狀態(tài)轉(zhuǎn)換到另一個(gè)狀態(tài)。二、進(jìn)程狀態(tài)2、進(jìn)程狀態(tài)轉(zhuǎn)換111進(jìn)程在運(yùn)行期間并非固定處于某個(gè)狀態(tài)，而是不斷從一個(gè)狀態(tài)轉(zhuǎn)換具有掛起狀態(tài)的進(jìn)程狀態(tài)活動(dòng)就緒執(zhí)行掛起調(diào)度時(shí)間片完活動(dòng)阻塞事件發(fā)生等待事件靜止就緒靜止阻塞激活掛起事件發(fā)生激活掛起112具有掛起狀態(tài)的進(jìn)程狀態(tài)活動(dòng)就緒執(zhí)行掛起調(diào)度時(shí)間片完活動(dòng)阻塞事線程的基本概念進(jìn)程是資源分配的單位，而線程是處理機(jī)調(diào)度的單位。一個(gè)進(jìn)程可以創(chuàng)建一個(gè)或多個(gè)線程。多個(gè)線程會(huì)爭(zhēng)奪CPU，在不同的狀態(tài)之間進(jìn)行轉(zhuǎn)換。線程也是一個(gè)動(dòng)態(tài)的概念，也有一個(gè)從創(chuàng)建到消亡的生命過程，具多種狀態(tài)。同一進(jìn)程中的所有線程都具有相同的地址空間（進(jìn)程的地址空間）。113線程的基本概念進(jìn)程是資源分配的單位，而線程是處理機(jī)調(diào)度的單位線程的實(shí)現(xiàn)方式

線程的實(shí)現(xiàn)方式內(nèi)核支持線程的實(shí)現(xiàn)直接利用系統(tǒng)調(diào)用進(jìn)行線程控制。用戶級(jí)線程的實(shí)現(xiàn)不能直接利用系統(tǒng)調(diào)用。為了取得內(nèi)核的服務(wù)（獲得系統(tǒng)資源），需要借助中間系統(tǒng)（運(yùn)行時(shí)系統(tǒng)、輕型進(jìn)程）。114線程的實(shí)現(xiàn)方式線程的實(shí)現(xiàn)方式14同步機(jī)制應(yīng)遵循的規(guī)則空閑讓進(jìn):當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。忙則等待:當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表明臨界資源正在被訪問，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問。有限等待:對(duì)要求訪問臨界資源的進(jìn)程，應(yīng)保證在有限時(shí)間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入死等狀態(tài)。讓權(quán)等待:當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入忙等。115同步機(jī)制應(yīng)遵循的規(guī)則空閑讓進(jìn):當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，表明臨界信號(hào)量機(jī)制信號(hào)量機(jī)制信號(hào)量用于表示資源數(shù)目或請(qǐng)求使用某一資源的進(jìn)程個(gè)數(shù)的整型量。整型信號(hào)量記錄型信號(hào)量信號(hào)量集（AND信號(hào)量集、一般信號(hào)量集）116信號(hào)量機(jī)制信號(hào)量機(jī)制16利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步例：進(jìn)程A與進(jìn)程B共享同一文件file，設(shè)此文件要求互斥使用，則可將file作為臨界資源，有關(guān)file的使用程序段分別為臨界區(qū)CSA和CSB。

semaphoremutex=1;PA:{ L1：P(mutex); CSA;

V(mutex);

remainderofprocessA; GOTOL1;}PB:{ L2:P(mutex); CSB;

V(mutex); remainderofprocessB;GOTOL2;}

117利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步例：進(jìn)程A與進(jìn)程B共享同一文件fileS1S3S2S4S5S6S7S8例：利用信號(hào)量來(lái)描述前趨圖關(guān)系利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步118S1S3S2S4S5S6S7S8例：利用信號(hào)量來(lái)描述前趨圖關(guān)

具有8個(gè)結(jié)點(diǎn)的前趨圖。圖中的前趨圖中共有10條有向邊，可設(shè)10個(gè)信號(hào)量，初值均為0；有8個(gè)結(jié)點(diǎn)，可設(shè)計(jì)成8個(gè)并發(fā)進(jìn)程，具體描述如下：S1S3S2S4S5S6S7S8agefbcdhij利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步119具有8個(gè)結(jié)點(diǎn)的前趨圖。圖中的前趨圖中共有10條有向邊Structsmaphorea,b,c,d,e,f,g,h,i,j=0,0,0,0,0,0,0,0,0,0cobegin{S1;V(a);V(b);V(c);}{P(a);S2;V(d);}{P(b);S3;V(e);V(f);}{P(c);S4;V(g);}{P(d);P(e);S5;V(h);}{P(f);P(g);S6;V(i)}{P(h);P(i);S7;V(j);}{P(j);S8;}coendS1S3S2S4S5S6S7S8agefbcdhij利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步120Structsmaphorea,b,c,d,e,f,g,2.4經(jīng)典進(jìn)程的同步問題

在多道程序環(huán)境下，進(jìn)程同步問題十分重要，出現(xiàn)一系列經(jīng)典的進(jìn)程同步問題，其中有代表性有：生產(chǎn)者—消費(fèi)者問題哲學(xué)家進(jìn)餐問題讀者—寫者問題其他同步問題1212.4經(jīng)典進(jìn)程的同步問題在多道程序“哲學(xué)家進(jìn)餐”問題問題描述：有五個(gè)哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。他們共用一張圓桌，分別坐在五張椅子上。在圓桌上有五個(gè)碗和五支筷子，平時(shí)一個(gè)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取用其左、右最靠近他的筷子，只有在他拿到兩支筷子時(shí)才能進(jìn)餐。進(jìn)餐畢，放下筷子又繼續(xù)思考。解決死鎖問題的例子122“哲學(xué)家進(jìn)餐”問題問題描述：解決死鎖問題的例子22哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法一：至多只允許四位哲學(xué)家同時(shí)去拿左筷子，最終能保證至少有一位哲學(xué)家能進(jìn)餐，并在用完后釋放兩只筷子供他人使用。方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起時(shí)才允許進(jìn)餐。方法三：規(guī)定奇數(shù)號(hào)哲學(xué)家先拿左筷子再拿右筷子，而偶數(shù)號(hào)哲學(xué)家相反。123哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法一：至多只允許四位哲學(xué)家同時(shí)去拿哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法一：至多只允許四位哲學(xué)家同時(shí)去拿左筷子，最終能保證至少有一位哲學(xué)家能進(jìn)餐，并在用完后釋放兩只筷子供他人使用。設(shè)置一個(gè)初值為4的信號(hào)量r，只允許4個(gè)哲學(xué)家同時(shí)去拿左筷子，這樣就能保證至少有一個(gè)哲學(xué)家可以就餐，不會(huì)出現(xiàn)餓死和死鎖的現(xiàn)象。原理：至多只允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐，以保證至少有一個(gè)哲學(xué)家能夠進(jìn)餐，最終總會(huì)釋放出他所使用過的兩支筷子，從而可使更多的哲學(xué)家進(jìn)餐。124哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法一：至多只允許四位哲學(xué)家同時(shí)去拿哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstick[5]={1，1，1，1，1};semaphorer=4;voidphilosopher(inti){while(true){think();wait(r);//請(qǐng)求進(jìn)餐wait(chopstick[i]);//請(qǐng)求左手邊的筷子wait(chopstick[(i+1)mod5]);//請(qǐng)求右手邊的筷子eat();signal(chopstick[(i+1)mod5]);//釋放右手邊的筷子signal(chopstick[i]);//釋放左手邊的筷子signal(r);//釋放信號(hào)量rthink();}}125哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstic哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起時(shí)才允許進(jìn)餐。解法1：利用AND型信號(hào)量機(jī)制實(shí)現(xiàn)。原理：多個(gè)臨界資源，要么全部分配，要么一個(gè)都不分配，因此不會(huì)出現(xiàn)死鎖的情形。126哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();Swait(chopstick[i];chopstick[(i+1)mod5]);eat();Ssignal(chopstick[(i+1)mod5];chopstick[i]);think();}}127哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstic哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起時(shí)才允許進(jìn)餐。解法2：利用信號(hào)量的保護(hù)機(jī)制實(shí)現(xiàn)。原理：通過互斥信號(hào)量mutex對(duì)eat()之前取左側(cè)和右側(cè)筷子的操作進(jìn)行保護(hù)，可以防止死鎖的出現(xiàn)。128哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphoremutex=1;semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();wait(mutex);wait(chopstick[i]);wait(chopstick[(i+1)mod5]);signal(mutex);eat();signal(chopstick[(i+1)mod5]);signal(chopstick[i]);think();

}}129哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphoremutex=哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法三：規(guī)定奇數(shù)號(hào)哲學(xué)家先拿左筷子再拿右筷子，而偶數(shù)號(hào)哲學(xué)家相反。原理：按照下圖，將是2,3號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子，4,5號(hào)哲學(xué)家競(jìng)爭(zhēng)5號(hào)筷子。1號(hào)哲學(xué)家不需要競(jìng)爭(zhēng)。最后總會(huì)有一個(gè)哲學(xué)家能獲得兩支筷子而進(jìn)餐。先申請(qǐng)的哲學(xué)家會(huì)較先可以吃飯并釋放筷子，因此不會(huì)出現(xiàn)餓死的哲學(xué)家。1221334455130哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法三：規(guī)定奇數(shù)號(hào)哲學(xué)家先拿左筷子再哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){if(imod2==0)//偶數(shù)哲學(xué)家，先右后左。{wait(chopstick[(i+1)mod5]);wait(chopstick[i]);eat();signal(chops