操作系統(tǒng)總復習

1、從不同角度理解作業(yè)（了解作業(yè)概念） 從用戶角度看，在一次應用業(yè)務處理過程中，從輸入開始到輸出結(jié)束，用戶要求計算機所做的有關(guān)該次業(yè)務處理的全部工作稱為一個作業(yè)（P21）。 從系統(tǒng)角度看，作業(yè)由程序、數(shù)據(jù)和作業(yè)說明書組成，系統(tǒng)通過作業(yè)說明書控制文件形式的數(shù)據(jù)和程序，操作或執(zhí)行它們。1第2章 操作系統(tǒng)用戶界面作業(yè)的輸入輸出方式 聯(lián)機輸入輸出方式 脫機輸入輸出方式 直接耦合方式 SPOOLING系統(tǒng) 網(wǎng)絡(luò)聯(lián)機方式2SPOOLING系統(tǒng) SPOOLING（Simultaneous Peripheral Operation On-Line,外圍設(shè)備同時聯(lián)機操作）系統(tǒng)將外圍設(shè)備利用通道或DMA器件和主機與外

2、存相連。 可以在不使用低檔計算機的情況下，實現(xiàn)多用戶聯(lián)機操作。其中輸入井和輸出井起到緩沖的作用。 作業(yè)的輸入輸出過程由主機中的操作系統(tǒng)控制。 輸入輸入/ /輸出輸出程序程序讀讀過過程程寫寫過過程程P233SPOOLING系統(tǒng)圖示 通 道 通 道輸入裝置輸入裝置輸出裝置輸出裝置外 存輸入井輸出井通 道主機系統(tǒng)作業(yè)結(jié)果輸入管理模塊輸出管理模塊4SPOOLING工作原理 作業(yè)執(zhí)行前用慢速設(shè)備將作業(yè)預先輸入到后援存儲器（如磁盤、磁鼓，稱為輸入井）中，稱為預輸入 作業(yè)運行后，使用數(shù)據(jù)時，從輸入井中取出 作業(yè)執(zhí)行不必直接啟動外設(shè)輸出數(shù)據(jù)，只需將這些數(shù)據(jù)寫入輸出井中 作業(yè)全部運行完畢，再由外設(shè)輸出全部數(shù)據(jù)和

3、信息，稱為緩輸出 使外設(shè)在CPU直接控制下，與CPU并行工作（稱為假脫機）52.3命令控制界面（重點） 命令控制界面 命令接口：是系統(tǒng)為用戶提供的各種命令接口界面，用戶利用這些操作命令來組織和控制作業(yè)的執(zhí)行或管理計算機系統(tǒng)。 另一個接口是系統(tǒng)調(diào)用，編程人員使用系統(tǒng)調(diào)用來請求操作系統(tǒng)提供服務6命令控制界面分類 使用操作命令進行作業(yè)控制的方式有兩種： 聯(lián)機控制方式 脫機控制方式7聯(lián)機命令控制界面組成聯(lián)機命令控制界面包含： 一組聯(lián)機命令 終端處理程序 命令解釋程序 命令處理程序記住作用終端處理程序主要功能：1）接收字符并傳送給用戶程序2）暫存字符3）回送顯示4）屏幕編輯5）特殊字符處理命令解釋程序主

4、要功能： 1）產(chǎn)生提示符 2）讀入用戶命令 3）識別并分析命令 4）給出命令處理程序入口地址 5）將控制權(quán)交命令處理程序 6）顯示結(jié)果或出錯信息10返回返回命令控制界面脫機命令控制界面聯(lián)機命令控制界面一組聯(lián)機命令終端處理程序命令解釋程序命令處理程序112.5系統(tǒng)調(diào)用 系統(tǒng)調(diào)用是操作系統(tǒng)提供給編程人員的唯一接口。 含義：完成特定功能的系統(tǒng)子程序12計算機操作系統(tǒng)教程管理科學與工程學院管理科學與工程學院 矯健矯健3.1 進程的概念 程序順序執(zhí)行的特點 順序性:指令一條接著一條執(zhí)行，不被打斷。 封閉性:程序執(zhí)行的最終結(jié)果完全由初始條件（比如一個數(shù)據(jù)集合）決定，不受其他外界因素影響。 可再現(xiàn)性:任何時

5、候運行可以得到完全相同的結(jié)果，即執(zhí)行結(jié)果與執(zhí)行速度無關(guān)。 15程序并發(fā)執(zhí)行的特征 間斷性：并發(fā)程序之間的制約關(guān)系導致并發(fā)程序“執(zhí)行暫停執(zhí)行再執(zhí)行”這種間斷性的活動規(guī)律 失去封閉性：資源狀態(tài)由多個程序改變，程序執(zhí)行結(jié)果受外界環(huán)境影響 不可再現(xiàn)性：不同時間運行程序可導致不同的運行結(jié)果。受程序執(zhí)行速度制約。16進程的定義 進程是指一個具有獨立功能的程序的一次執(zhí)行活動(過程)； 17程序和進程的區(qū)別 程序 進程 183.2 進程的狀態(tài)進程控制塊（PCB）包含了有關(guān)進程的描述信息、控制信息以及資源信息，是進程動態(tài)特征的集中反映。系統(tǒng)根據(jù)PCB感知進程的存在。進程的狀態(tài)進程在生命周期內(nèi)有三種基本狀態(tài): 執(zhí)

6、行狀態(tài)(Running) 進程占有CPU，并在CPU上運行 就緒狀態(tài)(Ready) 一個進程已經(jīng)具備運行條件，但由于無CPU暫時不能運行的狀態(tài)（當調(diào)度給其CPU時，立即可以運行） 等待/阻塞狀態(tài)(Blocked) 指進程因等待某種事件的發(fā)生而暫時不能運行的狀態(tài)（即使CPU空閑，該進程也不可運行）20進程狀態(tài)的轉(zhuǎn)換就緒就緒執(zhí)行執(zhí)行等待等待完成完成提交進入提交進入資源不足資源不足等待某事件等待某事件得到資源得到資源某事件發(fā)生某事件發(fā)生時間片到時間片到調(diào)度選調(diào)度選中進入中進入213.3 進程的描述進程控制塊PCB PCB（Process Control Block）是一個專門的數(shù)據(jù)結(jié)構(gòu)，用它來記錄進

7、程的外部特征，描述進程的運動變化過程。進程控制塊（PCB）包含了有關(guān)進程的描述信息、控制信息以及資源信息，是進程動態(tài)特征的集中反映。系統(tǒng)利用PCB來控制和管理進程PCB是系統(tǒng)感知進程存在的唯一標志PCB與進程一一對應PCB的全部或部分駐留內(nèi)存23PCB包含的信息 描述信息描述信息：進程名或進程標識符、用戶名或用戶識別：進程名或進程標識符、用戶名或用戶識別號、家族關(guān)系等。號、家族關(guān)系等。 控制信息控制信息：進程當前的狀態(tài)（就緒、執(zhí)行、等待）、：進程當前的狀態(tài)（就緒、執(zhí)行、等待）、進程的優(yōu)先級（與進程類別、占有和使用資源有關(guān)）、進程的優(yōu)先級（與進程類別、占有和使用資源有關(guān)）、程序的開始地址、各種計

8、時信息、通信信息等程序的開始地址、各種計時信息、通信信息等 資源管理信息資源管理信息：占用內(nèi)存的位置和大小、占用系統(tǒng)的：占用內(nèi)存的位置和大小、占用系統(tǒng)的外設(shè)情況等。外設(shè)情況等。 CPUCPU現(xiàn)場保護結(jié)構(gòu)現(xiàn)場保護結(jié)構(gòu)：任何一個進程在其生存期內(nèi)通常：任何一個進程在其生存期內(nèi)通常是是“走走停停走走停?！钡?，所以在一個的，所以在一個PCB中設(shè)有專門的中設(shè)有專門的CPU現(xiàn)場保護結(jié)構(gòu)，用于進程被中斷后再繼續(xù)執(zhí)行現(xiàn)場保護結(jié)構(gòu)，用于進程被中斷后再繼續(xù)執(zhí)行 243.4 進程控制進程控制 進程控制就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進程和完成進程之間各狀態(tài)的轉(zhuǎn)換。 目的：多進程并發(fā)執(zhí)行和協(xié)調(diào)、實現(xiàn)資源

9、共享。 進程控制一般由操作系統(tǒng)內(nèi)核來實現(xiàn)。26原語 原語是指在系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段。即原語是由若干條指令所構(gòu)成的，用于完成一定功能的一個過程。 原語與一般過程的區(qū)別在于: 它們是“原子操作”即一個操作中的所有動作，要么全做，要么全不做。換言之，原子操作是一個不可分割的操作。27進程控制原語 創(chuàng)建原語 撤消原語 阻塞原語 喚醒原語28進程創(chuàng)建過程系統(tǒng)調(diào)用創(chuàng)建原語創(chuàng)建進程: P46 申請空白PCB并獲得該PCB的內(nèi)部標識; 初始化PCB; 初始化標識符信息 初始化處理機狀態(tài)如PC指向程序入口地址 初始化處理機控制信息如將進程狀態(tài)置為就緒 將新進程插入就緒隊列29撤消原語流程查進程

10、鏈表或進程家族查進程鏈表或進程家族釋放該進程所占資源釋放該進程所占資源釋放該釋放該PCB本身結(jié)構(gòu)本身結(jié)構(gòu)有此有此PCB?該該PCB有子進程有子進程?出錯處理出錯處理返回有有有有無無無無30進程的阻塞與喚醒 進程的阻塞是由于進程期待某事件發(fā)生而產(chǎn)生的，阻塞后進程進入等待隊列。 P47 進程的喚醒是由于等待事件發(fā)生，所有等待該事件的進程都將被喚醒且進入就緒隊列。P47就緒就緒執(zhí)行執(zhí)行等待等待完成完成 創(chuàng)建創(chuàng)建資源不足資源不足等待某事件等待某事件得到資源得到資源某事件發(fā)生某事件發(fā)生時間片到時間片到調(diào)度選調(diào)度選中進入中進入阻塞喚醒31阻塞/喚醒原語流程保存當前進程保存當前進程CPU現(xiàn)場現(xiàn)場被阻塞進程進

11、等待隊列被阻塞進程進等待隊列轉(zhuǎn)進程調(diào)度轉(zhuǎn)進程調(diào)度入口置該進程狀態(tài)為等待置該進程狀態(tài)為等待從等待隊列中摘下被喚醒進程從等待隊列中摘下被喚醒進程將被喚醒進程送就緒隊列將被喚醒進程送就緒隊列轉(zhuǎn)進程調(diào)度或返回轉(zhuǎn)進程調(diào)度或返回入口將被喚醒進程置就緒將被喚醒進程置就緒阻塞原語流程阻塞原語流程喚醒原語流程喚醒原語流程323.5 進程互斥進程間的關(guān)系多道環(huán)境下進程間關(guān)系有: 資源共享關(guān)系（間接關(guān)系） 如共享CPU，I/O設(shè)備等。 相互合作關(guān)系（直接關(guān)系） 如相互傳送數(shù)據(jù)，輸入/計算/打印進程34臨界區(qū)(critical region) 臨界區(qū)指不允許多個并發(fā)進程交叉執(zhí)行的一段程序?；蛘哒f,臨界區(qū)是訪問公用數(shù)據(jù)

12、的那段程序。GetspaceRelease().PAPB堆棧S臨界區(qū)臨界臨界資源資源35間接制約 間接制約是由于同時使用公有資源而引起的進程之間的相互制約關(guān)系。資源對進程的制約,導致對并發(fā)進程執(zhí)行速度的間接制約如，共享一個內(nèi)存單元，使并發(fā)進程之間出現(xiàn)臨界區(qū)。主要體現(xiàn)在進程互斥直接制約是由于并發(fā)進程互相共享對方的私有資源所引起的制約關(guān)系進程同步36什么是互斥 互斥是一種管理公有資源的方法，其目的在于制約各并發(fā)進程以保證執(zhí)行結(jié)果的封閉性。互斥就是指多個共享公有資源的進程不能同時進入臨界區(qū)。（概念）一組并發(fā)進程互斥執(zhí)行時應遵守一定準則。要求37互斥的實現(xiàn) 互斥的加鎖實現(xiàn) 用P,V原語實現(xiàn)進程互斥38

13、信號量(semaphore) 信號量是資源的管理者 信號量：通常是一個整數(shù)(可以用 sem表示)，用來管理相應臨界區(qū)中的臨界資源。 當sem0時表示現(xiàn)有空閑資源的數(shù)量； 當sem=0時表示資源全部被占用； 當sem=0,則進程繼續(xù)執(zhí)行3、若sem0,則進程繼續(xù)執(zhí)行3、若sem=0,則從等待隊列 中喚醒一進程 40用P、V原語實現(xiàn)進程互斥 有兩并發(fā)進程PA和 PB共享某一臨界資源，用 P、V原語實現(xiàn)兩進程的互斥操作。 設(shè)互斥信號量為sem,其初值為1。S表示臨界區(qū)。其描述如下： PA: P(sem) V(sem) PB: P(sem) V(sem) 當sem=1時表示可用資源數(shù)為1，無進程進入臨

14、界區(qū);當sem=0時表示已有一進程進入臨界區(qū);另一進程申請時將等待當sem=-1時表示一進程已進入臨界區(qū)，另一進程等待。41進程互斥實現(xiàn)實例 有100個同學共享1本教材，試用P、V原語描述這100個同學互斥使用這本教材的過程設(shè)信號量為sem,其初值為1表示有1個共享資源(書) 互斥使用：1、每個同學都可使用教材2、某個同學不使用時不阻 止其他同學使用3、有多個同學需要教材時 只允許一個同學使用同學i取教材用進程Pi表示其中，i=1,2,100Pi : begin P(sem) /申請使用 使用教材 V(sem) /用完放回 endSem=1 0 -(100-1)1本書被使用1本書被使用還有99

15、人在等待423.6 進程同步進程間的直接制約關(guān)系 由于共享某一公有資源而引起進程間接制約關(guān)系 由于共享對方進程私有資源而引起進程直接制約關(guān)系并發(fā)進程的各自執(zhí)行結(jié)果互為互為對方的執(zhí)行條件限制各進程的執(zhí)行速度44進程同步 進程同步指一組在異步環(huán)境下的并發(fā)進程，因存在直接制約關(guān)系而相互發(fā)送信息以使各進程按一定次序執(zhí)行的過程。 簡言之，進程同步指多個相關(guān)進程在執(zhí)行次序上的協(xié)調(diào)。45發(fā)送消息機制實例 Pp (打印) B: wait(buffull) 打印Buf中的數(shù)據(jù) 清除Buf中的數(shù)據(jù) buffull false signal(bufempty) goto B設(shè)消息名設(shè)消息名bufempty表示表示B

16、uf空，且初始化空，且初始化bufempty=true 消息名消息名buffull表示表示Buf滿滿, 且初始化且初始化buffull=flase Pc (計算) A: wait(bufempty) 計算 Buf計算結(jié)果 bufemptyfalse signal(buffull) goto A46私有信號量信號量可分為兩種: 公用信號量(互斥信號量)和私有信號量(同步信號量)只與制約進程及被制約進程有關(guān)如私有信號量Bufempty只與計算進程和打印進程有關(guān)，與其他無關(guān)與整組并發(fā)進程有關(guān)如一組進程PAPB都與公有信號 sem有關(guān)，根據(jù) sem值進入相應臨界區(qū)管理相應臨界區(qū)的公有資源，代表可用資源

17、實體資源實體如信號量初值為1表示并發(fā)進程可用資源數(shù)為1指各進程間發(fā)送的消息消息,一個進程進程Pi的私有信號量的私有信號量是從制約進程發(fā)送來的進程Pi的執(zhí)行條件所需要的消息消息如計算進程的私有信號量Bufempty是從打印進程發(fā)來的計算進程執(zhí)行所需要的消息：緩沖區(qū)為空47用P、V原語實現(xiàn)進程同步實現(xiàn)進程同步的三個步驟: 1、為各并發(fā)進程設(shè)置私有信號量 2、為私有信號量賦初值 3、利用P、V原語和私用信號量規(guī)定各進程的執(zhí)行次序PAPBBuf 1Buf 2Buf iBuf n條件: 1、當緩沖區(qū)為空時， PB不能從中取數(shù)據(jù) 2、當PA送數(shù)據(jù)到緩沖區(qū)時，至少有一個為空 3、緩沖區(qū)中數(shù)據(jù)按FIFO排列例

18、如: 兩進程PA和PB通過緩沖隊列傳遞數(shù)據(jù) P57 PA發(fā)送進程，用過程deposit(data)表示 PB接收進程，用過程remove(data)表示PA:Bufempty PB:Buffulln048用P、V原語實現(xiàn)實例Pb: remove (data) begin local x P (buffull) 按FIFO選擇一個滿Buf(x) data Buf(x) Buf(x)置空標記置空標記 V(bufempty) end設(shè)進程設(shè)進程Pa的私有信號量的私有信號量bufempty，且初始化，且初始化bufempty=n 進程進程Pb的私有信號量的私有信號量buffull, 且初始化且初始化b

19、uffull=0Pa: deposit (data) begin local x P(bufempty) 按FIFO選擇一個空Buf(x) Buf(x)data Buf(x)置滿標記置滿標記 V(buffull) end49 在一個盒子里，混裝數(shù)量相等的圍棋白子和在一個盒子里，混裝數(shù)量相等的圍棋白子和黑子?，F(xiàn)在要用自動分揀系統(tǒng)把白子和黑子分黑子。現(xiàn)在要用自動分揀系統(tǒng)把白子和黑子分開。設(shè)系統(tǒng)有兩個進程開。設(shè)系統(tǒng)有兩個進程P1和和P2，其中，其中P1揀白子、揀白子、P2揀黑子。規(guī)定每個進程每次只揀一子。當一揀黑子。規(guī)定每個進程每次只揀一子。當一進程正在揀子時，不允許另一進程去揀；進程正在揀子時，不

20、允許另一進程去揀； 試寫出兩個并發(fā)進程能正確執(zhí)行的程序。試寫出兩個并發(fā)進程能正確執(zhí)行的程序。當一進程揀了一子時，必須讓另一進程去揀。當一進程揀了一子時，必須讓另一進程去揀。P2:揀黑子揀黑子 Begin Repeat P(mutex); 揀黑子揀黑子; V(mutex) Until false EndP1:揀白子揀白子 Begin Repeat P(mutex); 揀白子揀白子; V(mutex) Until false End設(shè)互斥信息量設(shè)互斥信息量mutex表示兩進程互斥揀子，表示兩進程互斥揀子，mutex=1 設(shè)信號量設(shè)信號量S1表示是否揀白子，表示是否揀白子，S1=1 信號量信號量S2

21、表示是否揀黑子，表示是否揀黑子，S2=0P2:揀黑子揀黑子 Begin Repeat P(S2) 揀黑子揀黑子; V(S1) Until false EndP1:揀白子揀白子 Begin Repeat P(S1) 揀白子揀白子; V(S2) Until false End生產(chǎn)者-消費者問題生產(chǎn)者生產(chǎn)者消費者消費者釋放某釋放某類資源類資源的進程的進程使用某使用某類資源類資源的進程的進程長度為長度為 n的緩沖區(qū)的緩沖區(qū)兩個同步信號量一個互斥信號量51同步P在互斥P之前，V無所謂P、V操作討論1) 信號量的物理含義: (S為信號量) S0表示有S個資源可用 S=0表示無資源可用 S0則| S |表示

22、S等待隊列中的進程個數(shù) P(S):表示申請一個資源; V(S)表示釋放一個資源。信號量的初值應該大于等于0 2) P.V操作必須成對出現(xiàn) (S1為同步,S2為互斥)當為互斥操作時，它們同處于同一進程當為同步操作時，則不在同一進程中出現(xiàn)如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關(guān)重要, 應同步P操作在互斥P操作之前 但兩個V操作順序無關(guān)緊要52進程同步與互斥的關(guān)系 兩者都反映了在異步環(huán)境下并發(fā)進程間的相互制約關(guān)系。 可歸于同步范疇，但互斥是同步問題的一個特例，互斥解決臨界區(qū)的使用，同步是并發(fā)進程在一些關(guān)鍵點上需互相等待互發(fā)消息。533.7 進程通信進程通信的方式 在單機系統(tǒng)中，

23、進程通信的主要方式有: 主從式通信方式 會話式通信方式 消息或郵箱機制 共享存儲區(qū)方式（兩個進程共享存儲區(qū)的值，不發(fā)生數(shù)據(jù)傳遞，與前三個不同）55進程通信的實例管道 以UNIX系統(tǒng)的管道通信為例 管道是指能連接一個寫進程和一個讀進程的，并允許它們以生產(chǎn)者-消費者方式進行通信的一個共享文件。 由寫進程從管道的入端將數(shù)據(jù)寫入，而讀進程則從管道的出端讀出數(shù)據(jù)。pipe寫進程讀進程入端入端出端出端56 3.8 死鎖問題什么是死鎖 死鎖指各并發(fā)進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。P1S1S2S3P2P3進程間通信時的死鎖情況58產(chǎn)生死鎖的原因 原因:系統(tǒng)資源總數(shù)

24、小于所有進程對資源的需求總數(shù)。 進程間彼此互相等待對方所擁用的資源，且這些并發(fā)進程在得到對方的資源之后不會釋放，從而造成資源相互占用和循環(huán)等待。59產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件1、互斥條件: 進程獨占使用資源，在使用資源方面具有排他性，即在一段時間內(nèi)某資源僅為一進程所占用。2、不剝奪條件: 進程已獲得的資源在未使用完之前，不能被強行剝奪，只能用完后自已釋放。3、部分分配(請求/保持條件):當進程因請求新資源而阻塞時，對已獲得的資源保持不放。4、環(huán)路等待條件:存在一種進程循環(huán)鏈，鏈中每一個進程已獲得的資源同時被下一個進程所請求。 60死鎖的排除方法q 死鎖預防q 死鎖避免q 死鎖的檢測和

25、恢復61死鎖避免方法使用向量矩陣描述各進程的資源請求和獲得系統(tǒng)空閑資源的狀況。W(nm矩陣): Pi請求Rj的數(shù)目A(nm矩陣): Pi被分配Rj的數(shù)目B(nm矩陣): Pi釋放Rj的數(shù)目F:空閑資源數(shù)目并發(fā)進程 P1,P2,Pn (n=1)共享資源 R1,R2,Rm (m=1)每一資源Ri有固定的單元數(shù)目Ci 其中 1=i=n (資源數(shù)=進程數(shù)) 系統(tǒng)安全的條件(對任一進程) 1、第一步的請求資源=空閑數(shù) 2、其它步的請求資源將P1所申請的資源分配給它753.9 線程的概念什么是線程線程:有時稱輕權(quán)進程進程中的一個運行實體資源的擁有者但與資源分配無關(guān)，可共享進程資源線程與進程共享同一地址空間

26、77計算機操作系統(tǒng)教程管理科學與工程學院 矯健78主要內(nèi)容 在大型通用系統(tǒng)中，可能有數(shù)百個批處理作業(yè)存放在磁盤的作業(yè)隊列中，有數(shù)百個終端同主機相聯(lián)接。因此如何從這些作業(yè)中挑選作業(yè)進入主存運行、如何在作業(yè)或進程間分配處理機等，無疑是操作系統(tǒng)的資源管理功能中的一個重要問題。 本章主要討論處理機分配問題，或稱處理機調(diào)度。794.0 概述80不同系統(tǒng)要求的策略 分時系統(tǒng)分時系統(tǒng)各作業(yè)均等地獲得處理機各作業(yè)均等地獲得處理機使作業(yè)有較快響應時間使作業(yè)有較快響應時間資源利用率不高資源利用率不高 批處理系統(tǒng)批處理系統(tǒng)作業(yè)量均衡搭配作業(yè)量均衡搭配提高處理機利用率提高處理機利用率作業(yè)響應時間較長作業(yè)響應時間較長缺

27、陷：缺陷：目的：目的：組織：組織：操作系統(tǒng)要求不同其處理機管理的操作系統(tǒng)要求不同其處理機管理的策略策略不同。不同。814.1 分級調(diào)度82調(diào)度的層次調(diào)度的層次一般來說，處理機調(diào)度可以分成三級： 作業(yè)調(diào)度作業(yè)調(diào)度 交換調(diào)度交換調(diào)度 進程調(diào)度進程調(diào)度83作業(yè)調(diào)度 作業(yè)調(diào)度又稱為宏觀調(diào)度或高級調(diào)度。 主要任務是按一定原則對外存輸入井上的大量后備作業(yè)進行選擇，給選出的作業(yè)分配內(nèi)存、I/O設(shè)備等必要資源，并建立相應的進程，以使該作業(yè)的進程獲得競爭處理機的權(quán)利。在作業(yè)執(zhí)行完畢時，還負責回收系統(tǒng)資源。84具有掛起功能的進程狀態(tài)圖就緒執(zhí)行等待掛起等待掛起就緒wakeup (喚醒喚醒)事件發(fā)生掛起suspend

28、時間片完時間片完被調(diào)度被調(diào)度schoduler解掛active掛起suspend解掛active掛起suspend等待事件等待事件sleep事件發(fā)生wakeup (喚醒)圖：具有掛起功能的進圖：具有掛起功能的進程 狀 態(tài) 變 化程 狀 態(tài) 變 化85進程調(diào)度 進程調(diào)度又稱低級調(diào)度。 主要任務是按某種策略和方法選取一個處于就緒狀態(tài)的進程占用處理機。在確定了占用處理機的進程之后，系統(tǒng)需要進行上下文切換。86處理機調(diào)度示意圖執(zhí)行就緒等待掛起就緒掛起等待后備完成執(zhí)行內(nèi)存時間片到I/O請求I/O完成進程調(diào)度交換調(diào)度外存作業(yè)調(diào)度掛起掛起激活激活線程調(diào)度作業(yè)調(diào)度874.2 作業(yè)調(diào)度88作業(yè)調(diào)度的執(zhí)行階段 作

29、業(yè)調(diào)度完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)的轉(zhuǎn)變，以及從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。完成提交后備執(zhí)行作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度89作業(yè)調(diào)度的性能衡量 衡量一個作業(yè)調(diào)度算法是否滿足系統(tǒng)設(shè)計要求？批處理系統(tǒng)批處理系統(tǒng)分時分時/實時系統(tǒng)實時系統(tǒng)作業(yè)的平均周轉(zhuǎn)時間作業(yè)的平均周轉(zhuǎn)時間 平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間作業(yè)的平均周轉(zhuǎn)時間作業(yè)的平均周轉(zhuǎn)時間 平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間作業(yè)的響應時間作業(yè)的響應時間90作業(yè)的周轉(zhuǎn)時間周轉(zhuǎn)時間:作業(yè)提交作業(yè)完成之間的時間 調(diào)度算法應盡量使周轉(zhuǎn)時間縮短提交作業(yè)作業(yè)完成周轉(zhuǎn)時間周轉(zhuǎn)時間 Ti完成時間 Tci提交時間 Tsi等待時間 Twi執(zhí)行時間 Tri91周轉(zhuǎn)時間

30、計算周轉(zhuǎn)時間周轉(zhuǎn)時間：Ti = Tci Tsi Ti = Twi + Tri平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間:反映作業(yè)在系統(tǒng)中停留時間帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間: 反映作業(yè)在系統(tǒng)中停留時間與其執(zhí)行時間的關(guān)系平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間:設(shè)設(shè): : n 作業(yè)流中的作業(yè)數(shù)作業(yè)流中的作業(yè)數(shù) Ti 第第i i個作業(yè)周轉(zhuǎn)時間個作業(yè)周轉(zhuǎn)時間 Tsi 作業(yè)作業(yè)i i提交時間提交時間 Tci 作業(yè)作業(yè)i i完成時間完成時間 Twi 作業(yè)作業(yè)i i從后備從后備執(zhí)行執(zhí)行 的等待時間的等待時間 Tri 作業(yè)作業(yè)i i的執(zhí)行的執(zhí)行時間時間Wi 越小等待時間越少效率越高924.3 進程調(diào)度93什么是進程調(diào)度q進程調(diào)度任務：按

31、一定的策略，動態(tài)地把處理機分配給處于就緒隊列中的某一個進程，以使之執(zhí)行。負責進程調(diào)度功能的內(nèi)核程序稱為進程調(diào)度程序。94進程調(diào)度過程1、記錄系統(tǒng)中所有進程的執(zhí)行情況 通過PCB和PCB表的動態(tài)隊列，記錄系統(tǒng)中所有進程的執(zhí)行情況及狀態(tài)特征。2、選擇占有處理機的進程 按一定的策略選擇一個處于就緒狀態(tài)的進程，使其獲得處理機執(zhí)行。3、進行上下文切換 一個進程的執(zhí)行是在進程上下文中進行的。當處理機交給另一個進程時，系統(tǒng)要做進程上下文切換，以使另一個進程得以執(zhí)行。954.4 調(diào)度算法96常用調(diào)度算法（基本思想） 先來先服務(FCFS)調(diào)度算法 輪轉(zhuǎn)法(round robin) 多級反饋輪轉(zhuǎn)法 優(yōu)先級法 最

32、短作業(yè)優(yōu)先法(SJF) 最高響應比優(yōu)先法(HRN)作業(yè)作業(yè)/進程調(diào)度進程調(diào)度作業(yè)作業(yè)/進程調(diào)度進程調(diào)度進程調(diào)度進程調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度97先來先服務先來先服務(FCFS)調(diào)度算法調(diào)度算法 先來先服務算法是最簡單的調(diào)度方法?；驹瓌t是按照作業(yè)到達系統(tǒng)或進程進入就緒隊列的先后次序來選擇。FCFS 策略是屬于不可搶占策略。C B A CPU MEM 進程/作業(yè)98FCFS舉例作業(yè)提交時間運行時間開始時間完成時間 ts tR tB tC12348.008.509.009.502.000.500.100.208.0010.0010.5011.0010.0010.5011.0011.20作業(yè)調(diào)度順序為先后

33、到來的順序1,2,3,499FCFS調(diào)度算法特點調(diào)度算法特點 直觀上看，比較公平，先來的先被服務 對短作業(yè)/短進程不利(若在長作業(yè)/長進程之后到達，等待時間長) 一般情況下不單獨使用，常與其他算法配合使用。return100輪轉(zhuǎn)法輪轉(zhuǎn)法(RR) 基本思路：讓每個進程在就緒隊列中的等待時間與享受服務時間成比例，通過時間片輪轉(zhuǎn)實現(xiàn)。其步驟為： 1、將所有就緒進程按FCFS原則排成一個隊列，每次調(diào)度時把CPU分配給隊首進程并令其執(zhí)行一個時間片； 2、當時間片用完時，調(diào)度程序停止該進程的執(zhí)行并將它送入就緒隊列的末尾，等待下次執(zhí)行； 3、把處理機分配給就緒隊列中新的隊首進程，同時讓它執(zhí)行一個時間片,循環(huán)

34、下去直到隊列中無進程。時間片到C B A CPU 進程完成F 隊首隊尾A B C D 101時間片大小的確定 輪轉(zhuǎn)法中時間片的大小影響系統(tǒng)性能 若時間片過大每個進程在各時間片內(nèi)完成FCFS 若時間片適當進程均勻執(zhí)行 若時間片過小剝奪處理機次數(shù)增加 系統(tǒng)開銷增大 確定時間片的大小要考慮的主要因素： 系統(tǒng)對響應時間的要求 就緒隊列中進程的數(shù)目設(shè)響應時間為R, 時間片大小為q, 就緒隊列中最大進程數(shù)目為N則：R=Nq 當N一定時時間片大小正比于系統(tǒng)所要求的響應時間 當系統(tǒng)有較好的響應時間時間片大小反比于進程數(shù) 除此之外，確定時間片大小還要考慮進程的除此之外，確定時間片大小還要考慮進程的切換時間和切換

35、時間和CPUCPU的能力的能力( (運算速度運算速度) )。102多級反饋輪轉(zhuǎn)法 在輪轉(zhuǎn)法中，進入就緒隊列的進程有三種情況： 1、進程的時間片用完但進程未完成，再回到隊尾 2、因I/O請求等事件而阻塞,當解除后重新回到就緒 3、新創(chuàng)建進程進入就緒隊列 多級反饋輪轉(zhuǎn)法中將這些進程分類并賦于不同的優(yōu)先級和時間片,如：按進程類型(大計算/多I/O)分類 按進程阻塞原因(等待事件)103多級反饋輪轉(zhuǎn)算法1、設(shè)置多個就緒隊列并賦予不同的優(yōu)先權(quán)。第一個隊列優(yōu)先權(quán)最高，第二個次之，其余逐個降低。2、賦予各隊列不同的時間片，優(yōu)先權(quán)越高時間片越小。3、新進程進入內(nèi)存后將它放在第一隊列的末尾，按FCFS排隊，若在

36、時間片內(nèi)未完成則將該進程轉(zhuǎn)入第二隊列的末尾 當一個長作業(yè)降到第n隊列時，按時間片輪轉(zhuǎn)方式運行。4、僅當?shù)谝粋€隊列為空時，調(diào)度程序才調(diào)度第二隊列中的進程 若處理機正在第i隊列中為某進程服務時，又有較高優(yōu)先級的的新進程進入，則新進程搶占處理機，并將原進程放回第i隊列的末尾。104多級反饋輪轉(zhuǎn)法圖示就緒隊列就緒隊列1 1就緒隊列就緒隊列2 2就緒隊列就緒隊列3 3就緒隊列就緒隊列n n至CPU至CPU至CPU至CPUS1S2S3時間片S1S2高地址)，來了一個作業(yè)需分配19k內(nèi)存。指針10k60k90k20k41k41k10k90k20k142最先適應法評價優(yōu)點： 1、該方法傾向于優(yōu)先分配存儲空間中

37、低地址部分的空閑區(qū)，而高地址部分的大的空閑區(qū)劃分的機會較少，當大作業(yè)到來時比較容易得到滿足。 2、算法簡單，查找速度快。缺點： 1、在可用表/自由鏈的前端存在許多外零頭。 2、在可用表/自由鏈的尾端才可能有較大的空閑區(qū)，因此，將使找到合適空閑區(qū)的速度降低。143補充：下次適應法 下次適應法（ Next fit: NF ）又稱循環(huán)適應法。它實際上是首次適應算法的一種變形。 該方法要求存儲空間中的空閑區(qū)構(gòu)成一個循環(huán)鏈。 每次為作業(yè)/進程分配存儲空間時，總是從上次查找結(jié)束的地方開始，只要找到一個足夠大的空閑區(qū)，就將它劃分后分配出去。 修改可用表或自由鏈。 注：頭指針從低地址開始向高地址循環(huán)移動144

38、下次適應法示例起始指針10k60k90k20k來了一個作業(yè)需分配19k內(nèi)存，之后又有一個75k和30k的作業(yè)起始指針10k41k90k20k為第一個作業(yè)分配19k內(nèi)存，145下次適應法示例續(xù)起始指針10k41k15k20k為第二個作業(yè)分配75k內(nèi)存，起始指針10k11k15k20k為第三個作業(yè)分配30k內(nèi)存，146下次適應法評價 優(yōu)點： 存儲空間的利用率比較均衡，而不至于使小的空閑區(qū)集中于存儲器的一端。 缺點： 多次分配后可能沒有較大的空閑區(qū)，難以滿足大作業(yè)/進程。147動態(tài)分區(qū)的回收與拼接 用戶作業(yè)/進程執(zhí)行結(jié)束，存儲管理程序要收回已使用完畢的空閑區(qū)，并將其插入可用表/自由鏈。 將新釋放的空

39、閑區(qū)插入可用表/自由鏈時，該區(qū)與上下相鄰區(qū)的關(guān)系可能有四種情況： 如圖 P110 應將上述四種情況下的空閑區(qū)進行拼接。148分區(qū)管理的評價 優(yōu)點： 實現(xiàn)多作業(yè)和進程對內(nèi)存的共享 硬件支持少，管理簡單 缺點： 內(nèi)存利用率不高,存在碎片 難以實現(xiàn)各分區(qū)間的信息共享 作業(yè)和進程受分區(qū)大小限制且不可實現(xiàn)虛存1495.4 頁式管理150頁式管理 內(nèi)存劃分成不同的頁面，地址空間劃分為不同的頁，內(nèi)存分配以頁為單位來進行。151頁式管理基本原理 各進程的地址空間劃為成若干個長度相等的頁；每個頁長一般為1K-4K。 內(nèi)存空間也按頁的大小劃分為片或頁面； 內(nèi)存分配以頁為單位，作業(yè)/進程的各頁在內(nèi)存中可不連續(xù)；（頁

40、內(nèi)連續(xù)，頁間不連續(xù)） 頁式管理中作業(yè)地址空間中的邏輯地址格式為：頁號+頁內(nèi)地址 P115頁號頁內(nèi)地址地址空間中所含頁數(shù) 地址在頁內(nèi)偏移量091019頁長1K1024頁152靜態(tài)頁式管理 靜態(tài)頁式管理主要思想是： 在調(diào)度一個作業(yè)時，必須把它的所有頁一次裝入到主存的頁面內(nèi)，如果當時頁面數(shù)不足，則該作業(yè)必須等待，系統(tǒng)再調(diào)度另外的作業(yè)。153地址變換 地址變換是由頁號和頁內(nèi)地址構(gòu)成的邏輯地址變換到內(nèi)存物理地址的過程。 地址變換過程： 1、請求表 控制寄存器； (也稱頁表寄存器，頁表始址+頁表長度) 2、由控制寄存器的頁表始址找到頁表所在位置； 3、從頁表中取出相應的頁面號； 4、將頁面號 頁內(nèi)地址=物

41、理地址。頁表始址和頁表長度154地址變換圖示頁號頁內(nèi)地址邏輯地址邏輯地址大小頁表始址控制寄存器控制寄存器若頁號頁表大小則中斷+ 頁表頁表頁面號 存取控制頁面號 頁內(nèi)地址物理地址物理地址頁描述子頁描述子155地址變換計算法 對某特定機器，其地址結(jié)構(gòu)是一定的。 若給定一個地址空間中的邏輯地址為A，頁面大小為L，則頁號P和頁內(nèi)地址W 可按下式求得： P=INTA/L W=A Mod L 地址變換實例地址變換實例 P117-118156動態(tài)頁式管理 動態(tài)頁式管理主要思想：將作業(yè)或進程的指令或數(shù)據(jù)內(nèi)存運行，其余部分在適當時機陸續(xù)裝入內(nèi)存。157請求式分頁管理 請求分頁式管理目標：實現(xiàn)小內(nèi)存裝大作業(yè) 實現(xiàn)

42、方法：作業(yè)運行時，只將當前的一部分裝入內(nèi)存其余的放在輔存，一旦發(fā)現(xiàn)訪問的頁不在內(nèi)存中，則發(fā)生缺頁中斷，由OS將其從輔存調(diào)入內(nèi)存，如果內(nèi)存無空頁面，則選擇一個頁面淘汰。158置換算法 置換算法即按某種原則，選擇內(nèi)存中的某些頁淘汰并將其換出到外存。 常見的置換算法：v 隨機淘汰算法v 輪轉(zhuǎn)法v FIFO 置換算法v 最近最久未使用頁面置換算法 159隨機淘汰算法 隨機淘汰算法指隨機地選擇某個用戶的頁面并將其換出。 該方法簡單，但有時效率低下。160輪轉(zhuǎn)法 輪轉(zhuǎn)法指巡回換出內(nèi)存可用區(qū)中一個可以被換出的頁，而無論該頁是剛被換進或已換進內(nèi)存很長時間。 使用該方法的內(nèi)存利用率不高。161FIFO 置換算法

43、 FIFO 置換算法總是選擇在內(nèi)存駐留時間最長的一頁將其淘汰。 實現(xiàn)FIFO 算法需要把各個已分配頁按分配時間順序鏈接起來，組成FIFO 隊列并置一指針指向隊首頁面。 當按FIFO置換時，將隊列前頭的頁置換出，而把換入的頁鏈接在隊列尾。 FIFO算法的內(nèi)存利用率不高，且有時出現(xiàn)陷阱現(xiàn)象。P121 162FIFO實例 設(shè)進程P可分為5頁，訪問順序為:1,2,3,4,1,2,5,1,2,3,4,5,當進程P分得3個頁面時，執(zhí)行過程中內(nèi)存變化如下：123412512345111444555555222111113333332222244缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺頁次數(shù)：缺頁次數(shù)：9 缺頁

44、率：缺頁率：9/12=75163最近最久未使用頁面置換算法 最近最久未使用頁面置換算法(LRU )的基本思想：當需要淘汰某一頁時，選擇離當前時間的一段時間內(nèi)沒有使用過的頁先淘汰。 該方法不易實現(xiàn)，通常使用近似的LRU 算法。164LRU實例 設(shè)進程P可分為5頁，訪問順序為:1,2,3,4,1,2,5,1,2,3,4,5,當進程P分得3個頁面時，執(zhí)行過程中內(nèi)存變化如下：123412512345111444555333222111111443332222225缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺頁次數(shù)：缺頁次數(shù)：10 缺頁率：缺頁率：10/12=83.3165LRU實例續(xù)若進程P分得4個頁面

45、時，執(zhí)行過程中內(nèi)存變化如下：123412512345111111111115222222222223333555544444444333缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺頁次數(shù)：缺頁次數(shù)：8 缺頁率：缺頁率：8/12=66.71665.5 段式與段頁式管理167段式與段頁式管理 段式管理 段頁式管理 除了分區(qū)管理和頁式管理之外，還有除了分區(qū)管理和頁式管理之外，還有兩種存儲管理方式：兩種存儲管理方式：168段式管理的基本思想 用戶按功能劃分段169分段地址空間 一個段可定義為一組邏輯信息，如子程序、數(shù)組等，每個作業(yè)的地址空間是由一些分段構(gòu)成的，每段都有自已的名子，且都是一段連續(xù)的首地址為零的地址

46、空間。整個作業(yè)的地址空間是二維的。 段式虛地址結(jié)構(gòu)：段號段內(nèi)地址地址空間中允許的段數(shù)地址在段內(nèi)偏移量07 823若按以上地址結(jié)構(gòu)，該系統(tǒng)允許若按以上地址結(jié)構(gòu)，該系統(tǒng)允許一個作業(yè)有一個作業(yè)有256段，最大段長為段，最大段長為64K170分段與分頁的比較1、分頁的作業(yè)地址空間是單一的線性地址空間； 分段作業(yè)的地址空間是二維的(不同各段，段號，段內(nèi)位移)。2、 大小固定,是，分頁活 動用戶看不見； 大小不定，是(即一 組 有意義的信息)，分段是用戶可見的。171抖動問題 如果置換算法選擇不當，有可能產(chǎn)生剛被調(diào)出內(nèi)存的頁又要馬上被調(diào)回內(nèi)存，調(diào)回內(nèi)存不久又要馬上被調(diào)出內(nèi)存，如此反復的局面。如果頁面調(diào)度過

47、于頻繁，將大大影響系統(tǒng)效率，此現(xiàn)象稱為抖動現(xiàn)象。應該避免。 任何程序在局部性放入時，都有一個臨界值要求。當內(nèi)存分配小于這個臨界值，內(nèi)、外存交換頻率急劇增加（產(chǎn)生抖動），而內(nèi)存分配大于這個臨界值時，再增加內(nèi)存分配也不能顯著減少交換次數(shù)。這個內(nèi)存要求的臨界值被稱為工作集。參見P132 解決方法是：擴大工作集(臨界值)或選擇其他調(diào)度算法。172計算機操作系統(tǒng)教程管理科學與工程學院管理科學與工程學院 矯健矯健1738.1 文件與文件系統(tǒng)174文件與文件系統(tǒng) 什么是文件 文件是數(shù)據(jù)(信息)的一種組織形式。一段程序或數(shù)據(jù)的集合 什么是文件系統(tǒng) 文件系統(tǒng)是指文件和對文件進行操縱和管理的軟件集合。負責為用戶建

48、立、撤銷、讀寫、修改和復制文件，還負責完成對文件的按名存取和進行存取控制P1861758.2 文件的邏輯結(jié)構(gòu) 與存取方法176記錄式文件的結(jié)構(gòu) 文件由一系列的記錄組成 (P188) 常見邏輯結(jié)構(gòu) 連續(xù)結(jié)構(gòu)： 記錄按生成順序連續(xù)排列。 有利于記錄的追加和修改，但不利于查找 。P188 多重結(jié)構(gòu)：組成以記錄為元素的隊列，每個隊列的隊首為“鍵”，分別對應一個記錄鏈。通常查找記錄是按“鍵”查找：這樣便于查找。P189 轉(zhuǎn)置結(jié)構(gòu)：每個鍵下包含所有相關(guān)記錄的的指針，可以進一步改善搜索性能。 P189 順序結(jié)構(gòu)：按某一鍵有序排列文件中的記錄。1778.3 文件的物理結(jié)構(gòu) 與存儲設(shè)備178文件的物理結(jié)構(gòu) 文件

49、的物理結(jié)構(gòu)又稱為文件的存儲結(jié)構(gòu)，是從系統(tǒng)的角度研究文件，指文件在外存上的存儲組織形式，這與存儲介質(zhì)的存儲性能有關(guān)。 文件以塊為單位進行信息的存儲、傳輸和分配。 文件的存儲設(shè)備被劃分成若干大小相等的物理塊，它是與內(nèi)存一次交換數(shù)據(jù)的大小。與此相對應，將文件信息也劃分成相同大小的邏輯塊。所有塊統(tǒng)一編號。 一個文件至少占用一個物理塊，可以占用多個物理塊。 179常見物理結(jié)構(gòu) 連續(xù)文件: 一個邏輯文件的信息依次存于外存的若干連續(xù)的物理塊中。P192 串聯(lián)文件：用非連續(xù)的物理塊存放文件信息，其中每個物理塊設(shè)有一個指針，指向其后續(xù)連接的另一個物理塊。P192-193 索引文件: 系統(tǒng)為每個文件建立一張索引表

50、，表目為文件信息所在邏輯塊號和與之對應的物理塊號，索引表的物理地址則由文件說明信息給出。P193 可擴展為多重索引文件 P194180文件存儲設(shè)備文件存儲設(shè)備主要有兩大類 順序存儲設(shè)備: 以磁帶為代表 直接存儲設(shè)備：以磁盤為代表P194-1951818.4 文件存儲空間管理182文件存儲空間 文件存儲空間管理是文件系統(tǒng)的重要任務之一。 文件存儲空間的管理實質(zhì)上是一個空閑塊的組織和管理問題，包括：空閑塊的組織、空閑塊的分配與空閑塊的回收等幾個問題。183空閑文件目錄 系統(tǒng)為存儲設(shè)備中的空閑塊單獨建立一個目錄，稱為空閑文件目錄，每個空閑區(qū)域?qū)募夸浀囊粋€表項。 空閑文件目錄結(jié)構(gòu)：序號序號第一個

51、空閑塊號第一個空閑塊號空閑塊數(shù)空閑塊數(shù)空閑塊號空閑塊號124(2,3,4,5)293(9,10,11)3153(15,16,17)4-184空閑文件目錄特點 這種方法僅當有少量的空閑區(qū)時才有較好的效果。如果存儲空間中有大量的小的空閑區(qū)，則其目錄變得很大，因而效率大為降低。 這種技術(shù)適用于連續(xù)文件結(jié)構(gòu)的存儲區(qū)的分配與回收。185空閑塊鏈 空閑塊鏈法是把文件存儲設(shè)備上的所有空閑塊鏈接在一起，當申請者需要空閑塊時，分配程序從鏈頭摘取所需空閑塊，然后調(diào)整鏈指針，反之，當回收空閑塊時，把釋放的空閑塊逐個插入鏈尾上。 空閑塊鏈的鏈接方法因系統(tǒng)而不同，常用鏈接方法如下：按空閑區(qū)大小順序鏈接；按釋放先后順序鏈

52、接；按成組鏈接。186成組鏈接法 成組鏈接法是UNIX系統(tǒng)中采用的一種文件存儲空間的分配方法。 成組鏈接法的主要思想： 將文件存儲器中所有空閑塊分組，每組為50個塊，并且組的劃分是從后往前順次進行。 每組的第一塊用來存放前一組中各塊的塊號和總塊數(shù)。其中，第一組的塊數(shù)為49，最后一組的塊數(shù)可能不足50塊，且該組的塊號和總塊數(shù)放在管理文件存儲設(shè)備用的文件資源表中。187空閑塊分配 系統(tǒng)初啟時把文件資源表復制到內(nèi)存，使空閑塊的分配與回收可在主存中進行； 資源表中登記空閑塊號的區(qū)域是一種棧結(jié)構(gòu)，其中棧頂指針Ptr 值記載的總塊數(shù)，其后Ptr值為棧中單元號； 分配時先執(zhí)行，取出棧頂中對應的項作為這次申請

53、得到的物理塊號； 當時，系統(tǒng)作特殊處理：把登記在此表目中的塊號相對應的物理塊讀進內(nèi)存中的文件資源表的空白棧區(qū)，即把下一組空閑塊的塊號及總數(shù)讀進該棧，繼續(xù)。 當則表示遇到卷尾標志，表示無空閑塊可分。188空閑塊分配示例4350498 文件資源表文件資源表Ptr0：1：42：48：49：50100995251504985015014910210110099515004994524514504494014994515010099 5251文件資源表文件資源表Ptr0：1：48：49：500499 452451文件資源表文件資源表Ptr0：1：48：49：189空閑塊回收 空閑塊回收就是把空閑塊插入空閑塊鏈中。 若要插