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

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

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

1.3操作系統(tǒng)的基本特征并發(fā)性

(Concurrence)共享性

(Sharing)虛擬性

(Virtual)異步性

(Asynchronism)基本特征:最重要特性，其它三種特性以此為前提。操作系統(tǒng)的形成單道批處理系統(tǒng)多道批處理系統(tǒng)操作系統(tǒng)的形成在多道程序系統(tǒng)中增設(shè)一組軟件以有效加以解決，同時增設(shè)方便用戶使用計算機(jī)的軟件，這樣便形成了操作系統(tǒng)。操作系統(tǒng)：是一組控制和管理計算機(jī)硬件和軟件資源，合理地對各類作業(yè)進(jìn)行調(diào)度，以及方便用戶使用的程序集合。操作系統(tǒng)的結(jié)構(gòu)設(shè)計傳統(tǒng)的操作系統(tǒng)結(jié)構(gòu)無結(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)。第二章進(jìn)程管理

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

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

（2）動態(tài)性

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

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

線程的實現(xiàn)方式內(nèi)核支持線程的實現(xiàn)直接利用系統(tǒng)調(diào)用進(jìn)行線程控制。用戶級線程的實現(xiàn)不能直接利用系統(tǒng)調(diào)用。為了取得內(nèi)核的服務(wù)（獲得系統(tǒng)資源），需要借助中間系統(tǒng)（運行時系統(tǒng)、輕型進(jìn)程）。同步機(jī)制應(yīng)遵循的規(guī)則空閑讓進(jìn):當(dāng)無進(jìn)程處于臨界區(qū)時，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。忙則等待:當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時，表明臨界資源正在被訪問，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對臨界資源的互斥訪問。有限等待:對要求訪問臨界資源的進(jìn)程，應(yīng)保證在有限時間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入死等狀態(tài)。讓權(quán)等待:當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入忙等。信號量機(jī)制信號量機(jī)制信號量用于表示資源數(shù)目或請求使用某一資源的進(jìn)程個數(shù)的整型量。整型信號量記錄型信號量信號量集（AND信號量集、一般信號量集）利用信號量實現(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;}

S1S3S2S4S5S6S7S8例：利用信號量來描述前趨圖關(guān)系利用信號量實現(xiàn)進(jìn)程同步

具有8個結(jié)點的前趨圖。圖中的前趨圖中共有10條有向邊，可設(shè)10個信號量，初值均為0；有8個結(jié)點，可設(shè)計成8個并發(fā)進(jìn)程，具體描述如下：S1S3S2S4S5S6S7S8agefbcdhij利用信號量實現(xiàn)進(jìn)程同步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利用信號量實現(xiàn)進(jìn)程同步2.4經(jīng)典進(jìn)程的同步問題

在多道程序環(huán)境下，進(jìn)程同步問題十分重要，出現(xiàn)一系列經(jīng)典的進(jìn)程同步問題，其中有代表性有：生產(chǎn)者—消費者問題哲學(xué)家進(jìn)餐問題讀者—寫者問題其他同步問題“哲學(xué)家進(jìn)餐”問題問題描述：有五個哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。他們共用一張圓桌，分別坐在五張椅子上。在圓桌上有五個碗和五支筷子，平時一個哲學(xué)家進(jìn)行思考，饑餓時便試圖取用其左、右最靠近他的筷子，只有在他拿到兩支筷子時才能進(jìn)餐。進(jìn)餐畢，放下筷子又繼續(xù)思考。解決死鎖問題的例子哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法一：至多只允許四位哲學(xué)家同時去拿左筷子，最終能保證至少有一位哲學(xué)家能進(jìn)餐，并在用完后釋放兩只筷子供他人使用。方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起時才允許進(jìn)餐。方法三：規(guī)定奇數(shù)號哲學(xué)家先拿左筷子再拿右筷子，而偶數(shù)號哲學(xué)家相反。哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法一：至多只允許四位哲學(xué)家同時去拿左筷子，最終能保證至少有一位哲學(xué)家能進(jìn)餐，并在用完后釋放兩只筷子供他人使用。設(shè)置一個初值為4的信號量r，只允許4

個哲學(xué)家同時去拿左筷子，這樣就能保證至少有一個哲學(xué)家可以就餐，不會出現(xiàn)餓死和死鎖的現(xiàn)象。原理：至多只允許四個哲學(xué)家同時進(jìn)餐，以保證至少有一個哲學(xué)家能夠進(jìn)餐，最終總會釋放出他所使用過的兩支筷子，從而可使更多的哲學(xué)家進(jìn)餐。哲學(xué)家進(jìn)餐問題的改進(jìn)解法semaphorechopstick[5]={1，1，1，1，1};semaphorer=4;voidphilosopher(inti){while(true){think();wait(r);//請求進(jìn)餐

wait(chopstick[i]);//請求左手邊的筷子

wait(chopstick[(i+1)mod5]);//請求右手邊的筷子

eat();signal(chopstick[(i+1)mod5]);//釋放右手邊的筷子

signal(chopstick[i]);//釋放左手邊的筷子

signal(r);//釋放信號量rthink();}}哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起時才允許進(jìn)餐。解法1：利用AND型信號量機(jī)制實現(xiàn)。原理：多個臨界資源，要么全部分配，要么一個都不分配，因此不會出現(xiàn)死鎖的情形。哲學(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();}}哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法二：僅當(dāng)哲學(xué)家的左右手筷子都拿起時才允許進(jìn)餐。解法2：利用信號量的保護(hù)機(jī)制實現(xiàn)。原理：通過互斥信號量mutex對eat()之前取左側(cè)和右側(cè)筷子的操作進(jìn)行保護(hù)，可以防止死鎖的出現(xiàn)。哲學(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();

}}哲學(xué)家進(jìn)餐問題的改進(jìn)解法方法三：規(guī)定奇數(shù)號哲學(xué)家先拿左筷子再拿右筷子，而偶數(shù)號哲學(xué)家相反。原理：按照下圖，將是2,3號哲學(xué)家競爭3號筷子，4,5號哲學(xué)家競爭5號筷子。1號哲學(xué)家不需要競爭。最后總會有一個哲學(xué)家能獲得兩支筷子而進(jìn)餐。先申請的哲學(xué)家會較先可以吃飯并釋放筷子，因此不會出現(xiàn)餓死的哲學(xué)家。1221334455哲學(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]);}}}第三章處理機(jī)調(diào)度與死鎖

提交作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)狀態(tài)轉(zhuǎn)換圖后備退出完成一、調(diào)度的層次就緒阻塞就緒阻塞運行交換調(diào)度進(jìn)程調(diào)度（線程調(diào)度）FCFS例題例：下面三個作業(yè)幾乎同時到達(dá)系統(tǒng)并立即進(jìn)行FCFS調(diào)度：作業(yè)名所需CPU時間作業(yè)128

作業(yè)210

作業(yè)31假設(shè)提交順序為1、2、3，則平均作業(yè)周轉(zhuǎn)時間T=若提交順序改為作業(yè)2、1、3，則T=若提交順序改為作業(yè)3、2、1，則T=由此可以看出，F(xiàn)CFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時間與作業(yè)提交的順序有關(guān)。(28+38+39)/3=35(10+38+39)/3=29(1+11+39)/3=17進(jìn)程調(diào)度算法先來先服務(wù)FCFS

例1：進(jìn)程名到達(dá)時間服務(wù)時間A01B1100C

2

1D3

100進(jìn)程名到達(dá)時間服務(wù)時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A01B1100C21D3100周轉(zhuǎn)時間服務(wù)時間完成時間-到達(dá)時間開始時間+服務(wù)時間上一個進(jìn)程的完成時間01111 101 1001101 102100100102 2021991.99作業(yè)到達(dá)時間Tin服務(wù)時間Tr開始時間Ts結(jié)束時間Tc周轉(zhuǎn)時間T帶權(quán)周轉(zhuǎn)時間W平均時間

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

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

MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431表1T0時刻的資源分配表WorkABCNeedABCAllocationABCWork+AllocationABCFinishP0743010falseP1122200falseP2600302falseP3011211falseP4431002false（1）T0時刻的安全性利用安全性算法對T0時刻的資源分配情況進(jìn)行分析:T0時刻存在著一個安全序列{P1,P3,P4,P2,P0}，故系統(tǒng)是安全的。表2T0時刻的安全性檢查表532true332532743true743745true745104710471057truetrue332ABCAvailable(2)

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

P1發(fā)出請求向量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、AllocationMaxAllocationNeedAvailableABCABCABCABCP0753010743332

P1322200122P2902302600P3222211011P4433002431P1請求資源Request1(1,0,2)時的資源分配表(302)(020)(230)WorkABCNeedABCAllocationABCWork+AllocationABCFinishP1020302falseP3011211falseP4431002falseP2600302falseP0743010false由安全性檢查分析得知：此時刻存在著一個安全序列{P1,P3,P4,P2,P0}，故系統(tǒng)是安全的，可以立即將P1所申請的資源分配給它。4)利用安全性算法檢查資源分配后此時系統(tǒng)是否安全P1請求資源Request1(1,0,2)時的安全性檢查表230532true532743true743745true7451047true10471057true（3）P4請求資源Request4(3,3,0)

P4發(fā)出請求向量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等待(4)P0請求資源Request0(0,2,0)

P0發(fā)出請求向量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)的向量。MaxAllocationNeedAvailableABCABCABCABCP0753010743332(230)P1322200122(302)(020)P2902302600P3222211011P4433002431表5P0請求資源Request0(0,2,0)時的資源分配表[210][030][723]

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

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

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

3112110頁號p位移量w2112110塊號b塊內(nèi)位移d

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

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

已知邏輯地址求頁號和頁內(nèi)地址頁從0開始編號三、地址結(jié)構(gòu)三、地址結(jié)構(gòu)例題例：設(shè)有一頁式存儲管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁，每頁2048B，內(nèi)存總共有8個存儲塊，試問邏輯地址至少應(yīng)為多少位？內(nèi)存空間有多大？解：（1）頁式存儲管理系統(tǒng)的邏輯地址為：其中頁內(nèi)地址表每頁的大小即2048B=2*1024B=211B，所以頁內(nèi)地址為11位；頁號表最多允許的頁數(shù)即16頁=24頁，所以頁號為4位。故邏輯地址至少應(yīng)為15位。（2）物理地址為：其中塊內(nèi)地址表每塊的大小與頁大小相等，所以塊內(nèi)地址也為11位；其中塊號表內(nèi)存空間最多允許的塊數(shù)即8塊=23塊，所以塊號為3位。故內(nèi)存空間至少應(yīng)為14位，即214=16KB。頁號p位移量w塊號b塊內(nèi)偏移d四、地址變換例題例1：若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如下表所示，已知頁面大小為1024B，試將十進(jìn)制邏輯地址1011，2148，5012轉(zhuǎn)化為相應(yīng)的物理地址。頁號塊號02132136四、地址變換例題解：設(shè)頁號為P，頁內(nèi)位移為W，邏輯地址為A，內(nèi)存地址為M，頁面大小為L，則

P=int(A/L)W=AmodL頁號塊號02132136對于邏輯地址1011P=int(1011/1024)=0W=1011mod1024=1011A=1011=(0,1011)查頁表第0頁在第2塊，所以物理地址為M=1024*2+1011=3059。四、地址變換例題對于邏輯地址為2148P=int(2148/1024)=2W=2148mod1024=100A=2148=(2,100)查頁表第2頁在第1塊，所以物理地址為M=1024*1+100=1124。對于邏輯地址5012P=int(5012/1024)=4W=5012mod1024=916因頁號超過頁表長度，該邏輯地址非法。頁號塊號02132136有效訪問內(nèi)存的時間

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

）*（TTLB+2TM

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

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

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

有效內(nèi)存訪問時間例題在為作業(yè)分配內(nèi)存時以段為單位，分配一段連續(xù)的物理地址空間；段間不必連續(xù)。作業(yè)的邏輯地址空間是二維的，其邏輯地址由段號和段內(nèi)地址組成。地址映射需要CPU的硬件支持（地址變換機(jī)構(gòu)）注：內(nèi)存分配分頁管理中，邏輯地址是線性地址（一維）。分段管理中，段號S和段內(nèi)位移d不能形成一個線性地址，因為它實際上是代表著段長和段內(nèi)位移兩個變量。由于這兩個變量沒有特定的限制范圍而無法用一個變量來替代，因此分段管理的邏輯地址是二維地址。例1、在一個段式存儲管理系統(tǒng)中，其段表為：段號內(nèi)存起始地址段長

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

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

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

把獨占設(shè)備改造為邏輯共享設(shè)備。把一臺物理I/O設(shè)備虛擬為多臺邏輯I/O設(shè)備。組成：專門負(fù)責(zé)I/O的常駐內(nèi)存的進(jìn)程；輸入井、輸出井；輸入緩沖區(qū)、輸出緩沖區(qū)。1、磁盤性能磁盤性能簡述數(shù)據(jù)的組織磁盤結(jié)構(gòu)：磁道、柱面、扇區(qū)磁盤物理塊的地址：磁頭號、柱面號、扇區(qū)號存儲容量＝磁頭（盤面）數(shù)×磁道（柱面）數(shù)×每道扇區(qū)數(shù)×每扇區(qū)字節(jié)數(shù)假定一塊硬盤磁頭數(shù)為4，柱面數(shù)為2048，每個磁道有扇區(qū)2048，每個扇區(qū)記錄1KB（字節(jié)），該硬盤儲存容量為：4×2048×2048×1024/1024/1024/1024=16G4×2048×2048×1024/1000/1000/1000=17.2G（廠家）1、磁盤性能訪問時間尋道時間Ts：將磁頭從當(dāng)前位置移到指定磁道所經(jīng)歷的時間Ts=m×n+s。s為啟動磁臂的時間，n為移動的磁道數(shù)，m為常數(shù)。旋轉(zhuǎn)延遲時間Tr

：指定扇區(qū)移動到磁頭下面所經(jīng)歷的時間。設(shè)每秒r轉(zhuǎn)，則Tr＝1/2r（均值）傳輸時間Tt：將扇區(qū)上的數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時間Tt＝b/rN

。其中b：讀寫字節(jié)數(shù)，N：每道上的字節(jié)數(shù)?？刂破鲿r間Tc訪問時間Ta：Ta=m×n+s+1/2r+b/rN+Tc1、磁盤性能例：假設(shè)磁盤空閑（沒有排隊延遲）。平均尋道時間是9ms，傳輸速度是4MB/s，轉(zhuǎn)速是7200rpm，控制器的開銷是1ms。問讀或?qū)懸粋€512字節(jié)的扇區(qū)的平均時間是多少？解：訪問時間=尋道時間+旋轉(zhuǎn)延遲時間+傳輸時間+控制器時間訪問時間=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毫秒磁盤調(diào)度算法磁盤調(diào)度算法早期的磁盤調(diào)度算法先來先服務(wù)FCFS最短尋道時間優(yōu)先SSTF掃描算法掃描(SCAN)/電梯(LOOK)算法循環(huán)掃描(CSCAN)算法本教材不區(qū)分SCAN算法和LOOK算法，我們做題時都按LOOK算法解決（不掃描到頭?。〧CFS先來先服務(wù)按進(jìn)程請求訪問磁盤的先后次序進(jìn)行調(diào)度下磁道移道數(shù)98451838537146122

85141081241106559672總道數(shù)640平均80磁頭臂來回反復(fù)移動，增長了等待時間，對機(jī)械結(jié)構(gòu)不利最短尋道時間優(yōu)先（SSTF）選擇從當(dāng)前磁頭位置所需尋道時間最短的請求。下磁道移道數(shù)6512672373014

23988412224124218359總道數(shù)236平均29.5可能使一些申請者在較長時間內(nèi)得不得服務(wù)的機(jī)會假定磁頭向磁道號增加的方向移動。下磁道移道數(shù)65126729831122

24124218359371461423總道數(shù)299平均37.4Scan/Look算法第六章文件管理

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

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

=2471040KB

≈2.36GB或用如下解法：直接索引項可管理上限：10×0.5KB=5KB；一次間接索引項可管理上限：170×0.5KB=85KB；二次間接索引項可管理上限：170×170×0.5KB=14450KB；三次間接索引項可管理上限：170×170×170×0.5KB=2456500KB；可管理文件上限：5KB+85KB+14450KB+2456500KB。練習(xí)題解：（2）

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

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

（3）假設(shè)某個文件的FCB己在內(nèi)存，但其他信息均在外存，為了訪問該文件中某個位置的內(nèi)容，最少需要幾次訪問磁盤，最多需要幾次訪問磁盤？解：由于文件的FCB己在內(nèi)存，為了訪問文件中某個位置的內(nèi)容，最少需要1次訪問磁盤（即可通過直接地址直接讀文件盤塊），最多需要4次訪問磁盤（第一次是讀三次間址塊，第二次是讀二次間址塊，第三次是讀一次間址塊，第四次是讀文件盤塊）。文件控制塊（FCB）文件目錄文件目錄是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識系統(tǒng)中的文件及其物理地址，將文件名映射到外存物理位置，供檢索時使用。目錄項構(gòu)成文件目錄的項目（目錄項就是FCB）文件目錄：文件控制塊的有序集合。目錄文件為了實現(xiàn)對文件目錄的管理，通常將文件目錄以文件的形式保存在外存，這個文件就叫目錄文件。文件目錄和目錄文件是同一事物的兩種稱謂