操作系統(tǒng)總復(fù)習(xí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、人在等待423.6 進(jìn)程同步進(jìn)程間的直接制約關(guān)系 由于共享某一公有資源而引起進(jìn)程間接制約關(guān)系 由于共享對方進(jìn)程私有資源而引起進(jìn)程直接制約關(guān)系并發(fā)進(jìn)程的各自執(zhí)行結(jié)果互為互為對方的執(zhí)行條件限制各進(jìn)程的執(zhí)行速度44進(jìn)程同步 進(jìn)程同步指一組在異步環(huán)境下的并發(fā)進(jìn)程，因存在直接制約關(guān)系而相互發(fā)送信息以使各進(jìn)程按一定次序執(zhí)行的過程。 簡言之，進(jìn)程同步指多個相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)。45發(fā)送消息機(jī)制實(shí)例 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私有信號量信號量可分為兩種: 公用信號量(互斥信號量)和私有信號量(同步信號量)只與制約進(jìn)程及被制約進(jìn)程有關(guān)如私有信號量Bufempty只與計算進(jìn)程和打印進(jìn)程有關(guān)，與其他無關(guān)與整組并發(fā)進(jìn)程有關(guān)如一組進(jìn)程PAPB都與公有信號 sem有關(guān)，根據(jù) sem值進(jìn)入相應(yīng)臨界區(qū)管理相應(yīng)臨界區(qū)的公有資源，代表可用資源

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

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

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

20、允許另一進(jìn)程去揀； 試寫出兩個并發(fā)進(jìn)程能正確執(zhí)行的程序。試寫出兩個并發(fā)進(jìn)程能正確執(zhí)行的程序。當(dāng)一進(jìn)程揀了一子時，必須讓另一進(jìn)程去揀。當(dāng)一進(jìn)程揀了一子時，必須讓另一進(jìn)程去揀。P2:揀黑子揀黑子 Begin Repeat P(mutex); 揀黑子揀黑子; V(mutex) Until false EndP1:揀白子揀白子 Begin Repeat P(mutex); 揀白子揀白子; V(mutex) Until false End設(shè)互斥信息量設(shè)互斥信息量mutex表示兩進(jìn)程互斥揀子，表示兩進(jìn)程互斥揀子，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)者-消費(fèi)者問題生產(chǎn)者生產(chǎn)者消費(fèi)者消費(fèi)者釋放某釋放某類資源類資源的進(jìn)程的進(jìn)程使用某使用某類資源類資源的進(jìn)程的進(jìn)程長度為長度為 n的緩沖區(qū)的緩沖區(qū)兩個同步信號量一個互斥信號量51同步P在互斥P之前，V無所謂P、V操作討論1) 信號量的物理含義: (S為信號量) S0表示有S個資源可用 S=0表示無資源可用 S0則| S |表示

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

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

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

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

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

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

28、時間片完時間片完被調(diào)度被調(diào)度schoduler解掛active掛起suspend解掛active掛起suspend等待事件等待事件sleep事件發(fā)生wakeup (喚醒)圖：具有掛起功能的進(jìn)圖：具有掛起功能的進(jìn)程 狀 態(tài) 變 化程 狀 態(tài) 變 化85進(jìn)程調(diào)度 進(jìn)程調(diào)度又稱低級調(diào)度。 主要任務(wù)是按某種策略和方法選取一個處于就緒狀態(tài)的進(jìn)程占用處理機(jī)。在確定了占用處理機(jī)的進(jìn)程之后，系統(tǒng)需要進(jìn)行上下文切換。86處理機(jī)調(diào)度示意圖執(zhí)行就緒等待掛起就緒掛起等待后備完成執(zhí)行內(nèi)存時間片到I/O請求I/O完成進(jìn)程調(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)分時分時/實(shí)時系統(tǒng)實(shí)時系統(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īng)時間作業(yè)的響應(yīng)時間90作業(yè)的周轉(zhuǎn)時間周轉(zhuǎn)時間:作業(yè)提交作業(yè)完成之間的時間 調(diào)度算法應(yīng)盡量使周轉(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 進(jìn)程調(diào)度93什么是進(jìn)程調(diào)度q進(jìn)程調(diào)度任務(wù)：按

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

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

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

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

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

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

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

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

39、閑區(qū)插入可用表/自由鏈時，該區(qū)與上下相鄰區(qū)的關(guān)系可能有四種情況： 如圖 P110 應(yīng)將上述四種情況下的空閑區(qū)進(jìn)行拼接。148分區(qū)管理的評價 優(yōu)點(diǎn)： 實(shí)現(xiàn)多作業(yè)和進(jìn)程對內(nèi)存的共享 硬件支持少，管理簡單 缺點(diǎn)： 內(nèi)存利用率不高,存在碎片 難以實(shí)現(xiàn)各分區(qū)間的信息共享 作業(yè)和進(jìn)程受分區(qū)大小限制且不可實(shí)現(xiàn)虛存1495.4 頁式管理150頁式管理 內(nèi)存劃分成不同的頁面，地址空間劃分為不同的頁，內(nèi)存分配以頁為單位來進(jìn)行。151頁式管理基本原理 各進(jìn)程的地址空間劃為成若干個長度相等的頁；每個頁長一般為1K-4K。 內(nèi)存空間也按頁的大小劃分為片或頁面； 內(nèi)存分配以頁為單位，作業(yè)/進(jìn)程的各頁在內(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)，如果當(dāng)時頁面數(shù)不足，則該作業(yè)必須等待，系統(tǒng)再調(diào)度另外的作業(yè)。153地址變換 地址變換是由頁號和頁內(nèi)地址構(gòu)成的邏輯地址變換到內(nèi)存物理地址的過程。 地址變換過程： 1、請求表 控制寄存器； (也稱頁表寄存器，頁表始址+頁表長度) 2、由控制寄存器的頁表始址找到頁表所在位置； 3、從頁表中取出相應(yīng)的頁面號； 4、將頁面號 頁內(nèi)地址=物

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

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

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

44、率：缺頁率：9/12=75163最近最久未使用頁面置換算法 最近最久未使用頁面置換算法(LRU )的基本思想：當(dāng)需要淘汰某一頁時，選擇離當(dāng)前時間的一段時間內(nèi)沒有使用過的頁先淘汰。 該方法不易實(shí)現(xiàn)，通常使用近似的LRU 算法。164LRU實(shí)例 設(shè)進(jìn)程P可分為5頁，訪問順序?yàn)?1,2,3,4,1,2,5,1,2,3,4,5,當(dāng)進(jìn)程P分得3個頁面時，執(zhí)行過程中內(nèi)存變化如下：123412512345111444555333222111111443332222225缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺缺頁次數(shù)：缺頁次數(shù)：10 缺頁率：缺頁率：10/12=83.3165LRU實(shí)例續(xù)若進(jìn)程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抖動問題 如果置換算法選擇不當(dāng)，有可能產(chǎn)生剛被調(diào)出內(nèi)存的頁又要馬上被調(diào)回內(nèi)存，調(diào)回內(nèi)存不久又要馬上被調(diào)出內(nèi)存，如此反復(fù)的局面。如果頁面調(diào)度過

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

48、立、撤銷、讀寫、修改和復(fù)制文件，還負(fù)責(zé)完成對文件的按名存取和進(jìn)行存取控制P1861758.2 文件的邏輯結(jié)構(gòu) 與存取方法176記錄式文件的結(jié)構(gòu) 文件由一系列的記錄組成 (P188) 常見邏輯結(jié)構(gòu) 連續(xù)結(jié)構(gòu)： 記錄按生成順序連續(xù)排列。 有利于記錄的追加和修改，但不利于查找 。P188 多重結(jié)構(gòu)：組成以記錄為元素的隊(duì)列，每個隊(duì)列的隊(duì)首為“鍵”，分別對應(yīng)一個記錄鏈。通常查找記錄是按“鍵”查找：這樣便于查找。P189 轉(zhuǎn)置結(jié)構(gòu)：每個鍵下包含所有相關(guān)記錄的的指針，可以進(jì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)。 文件以塊為單位進(jìn)行信息的存儲、傳輸和分配。 文件的存儲設(shè)備被劃分成若干大小相等的物理塊，它是與內(nèi)存一次交換數(shù)據(jù)的大小。與此相對應(yīng)，將文件信息也劃分成相同大小的邏輯塊。所有塊統(tǒng)一編號。 一個文件至少占用一個物理塊，可以占用多個物理塊。 179常見物理結(jié)構(gòu) 連續(xù)文件: 一個邏輯文件的信息依次存于外存的若干連續(xù)的物理塊中。P192 串聯(lián)文件：用非連續(xù)的物理塊存放文件信息，其中每個物理塊設(shè)有一個指針，指向其后續(xù)連接的另一個物理塊。P192-193 索引文件: 系統(tǒng)為每個文件建立一張索引表

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

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

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

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