礦大《操作系統(tǒng)》考前知識點(diǎn)整理

1、第一章 操作系統(tǒng)概述識記： 1. OS有哪3種觀點(diǎn)（目標(biāo)？）和OS的定義:操作系統(tǒng)是一組計(jì)算機(jī)程序的集合1) 控制和管理計(jì)算機(jī)的硬件和軟件資源，2) 合理地組織計(jì)算機(jī)的工作流程，使之可以得到更加合理的共享及保護(hù)，以及盡量好的性能。3) 向應(yīng)用程序和用戶提供方便、快捷、友好的使用接口。2. OS有哪3種基本類型及其目標(biāo):1) 批處理操作系統(tǒng)：提高系統(tǒng)資源利用率和作業(yè)吞吐率2) 分時(shí)操作系統(tǒng)：滿足用戶交互的及時(shí)響應(yīng)3) 實(shí)時(shí)操作系統(tǒng)：提高系統(tǒng)的及時(shí)性和可靠性（？）3. OS有哪4個(gè)特征: 并發(fā)性、共享性、虛擬性、異步性（隨機(jī)性）4. OS有哪5大功能：（6？）進(jìn)程管理、存儲管理、文件管理和設(shè)備管理

2、是操作系統(tǒng)的基本功能，網(wǎng)絡(luò)通信與服務(wù)、安全與保護(hù)是現(xiàn)在主流操作系統(tǒng)的衍生功能。第二章 進(jìn)程管理識記：1. 進(jìn)程的定義： 可并發(fā)執(zhí)行的程序在某個(gè)數(shù)據(jù)集合上的一次執(zhí)行過程,是操作系統(tǒng)資源分配、保護(hù)和調(diào)度的一個(gè)基本單位進(jìn)程的基本狀態(tài)： 就緒狀態(tài)，運(yùn)行狀態(tài)，阻塞狀態(tài)（等待狀態(tài)）進(jìn)程的組成： 進(jìn)程控制塊（PCB）+程序塊+數(shù)據(jù)塊+堆棧進(jìn)程控制塊的組織方式： 線性方式（有？）鏈接方式：單向，或雙向索引方式：對具有相同狀態(tài)的進(jìn)程，分別設(shè)置各自的PCB索引表，表明PCB在PCB表中的地址2. 原語的定義: 由若干條指令所組成，用來實(shí)現(xiàn)某個(gè)特定功能，在執(zhí)行過程中不可被中斷的程序段3. 進(jìn)程互斥的定義: 若干進(jìn)程

3、因相互爭奪獨(dú)占型資源而產(chǎn)生的競爭制約關(guān)系（若干個(gè)進(jìn)程要訪問同一共享資源時(shí)，任何時(shí)刻最多允許一個(gè)進(jìn)程訪問，其他進(jìn)程必須等待，直到占有資源的進(jìn)程釋放該資源）4. 臨界資源和臨界區(qū)的定義；臨界資源：某段時(shí)間內(nèi)只能允許一個(gè)進(jìn)程使用的共享資源臨界區(qū)：訪問臨界資源的代碼段5. 進(jìn)程同步的定義： 為完成共同任務(wù)的并發(fā)進(jìn)程基于某個(gè)條件來協(xié)調(diào)其運(yùn)行進(jìn)度、執(zhí)行次序而等待、傳遞信號或消息而產(chǎn)生的協(xié)作制約關(guān)系理解：1. 進(jìn)程同步機(jī)制； 鎖、信號量、管程、消息傳遞2. 進(jìn)程互斥與進(jìn)程同步的異同點(diǎn)；（？）異：進(jìn)程同步是為完成共同任務(wù)的并發(fā)進(jìn)程基于某個(gè)條件來協(xié)調(diào)其運(yùn)行進(jìn)度、執(zhí)行次序而等待、傳遞信號或消息而產(chǎn)生的協(xié)作制約關(guān)系

4、，而進(jìn)程互斥是若干進(jìn)程因相互爭奪獨(dú)占型資源而產(chǎn)生的競爭制約關(guān)系。同：互斥是一種特殊的同步關(guān)系以一定次序協(xié)調(diào)地使用共享資源3. 調(diào)用信號量S的P(S)操作與V(S)操作及其處理的物理意義。（P39）P(s)：將信號量s的值減1，若結(jié)果小于0，則調(diào)用P(s)的進(jìn)程被阻塞，并進(jìn)入信號量s的阻塞隊(duì)列中;若結(jié)果大于等于0，則調(diào)用P(s)的進(jìn)程繼續(xù)運(yùn)行物理意義：P(s)操作表示進(jìn)程申請一個(gè)資源，求而不得則阻塞進(jìn)程void P(semaphore &s) s.value-; if(s.value<0) block(s.list); /阻塞本進(jìn)程并進(jìn)入S信號量隊(duì)列V(s)：將信號量s的值加1，若

5、結(jié)果不大于0，則調(diào)用V(s)的進(jìn)程從該信號量阻塞隊(duì)列中釋放，喚醒一個(gè)處于等待狀態(tài)的進(jìn)程，將其轉(zhuǎn)換為就緒狀態(tài)，調(diào)用V(s)的進(jìn)程繼續(xù)運(yùn)行; 若結(jié)果大于0，則調(diào)用V(s)的進(jìn)程繼續(xù)運(yùn)行。物理意義：V(s)操作表示釋放一個(gè)資源，若此時(shí)還有進(jìn)程在等待獲取該資源，則被喚醒void V(semaphore &s) s.value+; if(s.value<=0) wakeup(s.list); /喚醒s信號量隊(duì)列中的一個(gè)進(jìn)程入就緒隊(duì)列簡單應(yīng)用：利用信號量解前趨圖問題。（？） 利用信號量描述程序和語句之間的前驅(qū)關(guān)系如果進(jìn)程p1中有語句 s1， p2中有語句 s2，為實(shí)現(xiàn)s1執(zhí)行后再執(zhí)行s2，只

6、需讓p1,p2進(jìn)程共享一個(gè)公共信號量S,且init(S)=0例題：在公共汽車上，司機(jī)和售票員的工作流程如下圖所示。為保證乘客的安全，司機(jī)和售票員應(yīng)協(xié)調(diào)工作：停車后才能開門，關(guān)車門后才能行車。用PV操作來實(shí)現(xiàn)他們之間的協(xié)調(diào)分析:司機(jī)啟動車輛的動作必須于售票員關(guān)車門的動作取得同步，售票員開車門的動作也必須與司機(jī)停車取得同步綜合應(yīng)用： .1. 能寫和理解計(jì)算、打印問題程序，生產(chǎn)者/消費(fèi)者問題程序；（P43）（生產(chǎn)者進(jìn)程可以是計(jì)算、發(fā)送進(jìn)程，消費(fèi)者進(jìn)程可以是打印、接受進(jìn)程）計(jì)算、打印問題程序 設(shè)信號量bufempty=1 (表示緩沖區(qū)數(shù)) buffull=0（表示運(yùn)算結(jié)果數(shù)）process C() p

7、rocess P() while(true) while(true) P(bufempty); P(buffull); 計(jì)算； 取出buf中的數(shù)據(jù) buf ß 計(jì)算結(jié)果 置空標(biāo)記，打印 V( buffull); V(bufempty); 生產(chǎn)者/消費(fèi)者問題：m個(gè)生產(chǎn)者和n個(gè)消費(fèi)者共享k件產(chǎn)品緩沖區(qū)，只要緩沖區(qū)未滿，生產(chǎn)者就可送入緩沖區(qū)；只要緩沖區(qū)不空，消費(fèi)者就可從緩沖區(qū)取走并消耗產(chǎn)品解：互斥信號量mutex: 限制生產(chǎn)者和消費(fèi)者互斥地對緩沖區(qū)進(jìn)行存取，初值為1同步信號量empty:保證生產(chǎn)者不向已滿地緩沖區(qū)中放入產(chǎn)品，初值為k同步信號量full：保證消費(fèi)者有產(chǎn)品消費(fèi)，初值為0in和o

8、ut：放入緩沖區(qū)指針和取出緩沖區(qū)指針item Bk; /緩沖區(qū)，長度ksemaphore empty=k; /可用的空緩沖區(qū)數(shù)semaphore full0; /緩沖區(qū)內(nèi)可用的產(chǎn)品數(shù)semaphore mutex1; /互斥信號量int in=0; /緩沖區(qū)放入位置int out=0; /緩沖區(qū)取出位置cobeginprocess producer_i() process consumer_j() while(true) while(true) produce(); /生產(chǎn)一個(gè)產(chǎn)品 P(full);P(empty); /申請空緩沖區(qū) P(mutex);P(mutex); /申請互斥使用緩沖區(qū)

9、take() from Bout; append to Bin; /產(chǎn)品放入緩沖 out=(out+1)%k; in=(in+1)%k; /更新緩沖區(qū)指針 V(mutex); V(mutex); V(empty); V(full); consume(); coend 2. 能寫和理解哲學(xué)家問題的程序；（P46）有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌子中央有一盤通心面，每人面前有一只空盤子，每兩人之間放一個(gè)筷子。每個(gè)哲學(xué)家思考、饑餓，然后想吃通心面。為了吃面，每個(gè)哲學(xué)家必須獲得兩個(gè)筷子，規(guī)定每人只能直接從其左邊或右邊去取筷子解：筷子是共享資源，需要互斥訪問(信號量解決互斥問題)。 引入五個(gè)互斥信號量。給

10、所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之semaphore chopsticks 5;for (int i=0; i<5; i+) chopsticks i = 1;cobeginprocess philmac_i( ) /i=0,1,2,3,4 think( )； if(i%2 =0) P(chopsticks i)； P(chopsticks (i+1)%5 )； else P(chopsticks (i+l)% 5); P(chopsticks i); eat( )； V(chopsticks i)； V(chopsticks (i+ 1 % 5)；

11、coend3. 能寫和理解讀者/寫者問題的程序。(P45)有兩組并發(fā)進(jìn)程，讀進(jìn)程與寫進(jìn)程，共享一個(gè)文件，為防止出錯，要求： 1）允許多個(gè)讀進(jìn)程同時(shí)讀文件； 2）只允許一個(gè)寫進(jìn)程寫文件； 3）寫進(jìn)程在沒有寫完成之前不允許其他讀寫；4）寫之前應(yīng)該讓所有已經(jīng)在讀或?qū)懙倪M(jìn)程操作完成。 解：引入一個(gè)計(jì)數(shù)器和兩個(gè)信號量解決此問題：信號量： ws: 允許寫信號量，初值為1mutex: 互斥訪問rc計(jì)數(shù)器信號量，初值為1 計(jì)數(shù)量： readcount: 讀進(jìn)程計(jì)數(shù)器int readcount=0; /讀進(jìn)程計(jì)數(shù)器semaphore ws=1, mutex:=1;cobeginprocess reader_i(

12、 ) process writer_j( )P(mutex); P(ws); readcount +; 寫文件; if (readcount = 1) P(ws); V(ws); V(mutex); 讀文件； P(mutex); readcount -; if (readcount = 0) V(ws); V(mutex);coend處理器調(diào)度識記：1. 作業(yè)調(diào)度的定義； 按一定的算法對外存輸入井上的大量后備作業(yè)進(jìn)行選擇調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行（or：按照某種調(diào)度算法從后備作業(yè)隊(duì)列中選取作業(yè)，使其進(jìn)入內(nèi)存運(yùn)行）2. 進(jìn)程調(diào)度的定義；用

13、來決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作3. 中級調(diào)度的定義；為了提高內(nèi)存的利用率和系統(tǒng)吞吐量，根據(jù)存儲資源量和進(jìn)程的當(dāng)前狀態(tài)來決定輔存和主存中進(jìn)程的對換4. 進(jìn)程調(diào)度的兩種方式； 非搶占方式，搶占方式5. 作業(yè)平均周轉(zhuǎn)時(shí)間的公式T； T = (Ti) / n6. 作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間的公式W； W = (Wi) / n綜合應(yīng)用： 作業(yè)采用先來先服務(wù)、短作業(yè)優(yōu)先、優(yōu)先級高優(yōu)先的調(diào)度算法時(shí)計(jì)算一批作業(yè)的T和W。（P55）(一) 先來先服務(wù)算法（FCFS）n 【例】系統(tǒng)中現(xiàn)有5個(gè)作業(yè)A、B、C、D、E同時(shí)提交（到達(dá)順序也為ABCDE），其預(yù)計(jì)運(yùn)行時(shí)間分

14、別10、1、2、1、5個(gè)時(shí)間單位，如表所示，計(jì)算FCFS調(diào)度下作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間 解：設(shè)作業(yè)到達(dá)時(shí)刻為0，根據(jù)定義計(jì)算，系統(tǒng)運(yùn)行情況 n 【例】在單道環(huán)境下，某批處理系統(tǒng)有四道作業(yè)，已知它們的進(jìn)入系統(tǒng)的時(shí)刻、估計(jì)運(yùn)算時(shí)間如下： 用FCFS 算法計(jì)算作業(yè)的運(yùn)行情況、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間解: 1) 調(diào)度次序：1 2 3 4 2) 完成時(shí)間圖: 3) T=2+2+1.6+1.3)÷41.725(h) W=(2/2+2/0.5+1.6/0.1+1.3/0.2)÷46.875(h)(二) 短作業(yè)優(yōu)先算法（SJF）n 【例】設(shè)有5道作業(yè)解：根據(jù)SJF原則，調(diào)

15、度次序?yàn)椋?P1-P2-P5-P4-P3 T=(0.3+0.6+0.4+0.8+1.3)÷50.68(h) W=(0.3/0.3+0.6/0.5+0.4/0.2+0.8/0.3+1.3/0.4)÷5 2.024(h)(三) 優(yōu)先級高優(yōu)先算法（HPF）n 【例】系統(tǒng)的進(jìn)程調(diào)度采用搶占式優(yōu)先權(quán)調(diào)度算法，優(yōu)先數(shù)越小優(yōu)先級越高，其參數(shù)如表所示，求平均周轉(zhuǎn)時(shí)間和平均等待時(shí)間 解：作業(yè)進(jìn)程綜合調(diào)度示例： 平均周轉(zhuǎn)時(shí)間T =（15+8+12+4）/ 4 = 9.75 平均等待時(shí)間Tw =（8+4+11+0）/ 4 = 5.75死鎖理解：1. 死鎖檢測；（P66）對資源的分配不加任何限制，

16、也不采取死鎖避免措施，但系統(tǒng)定時(shí)地運(yùn)行一個(gè)“死鎖檢測”程序，判斷系統(tǒng)內(nèi)是否已出現(xiàn)死鎖，如果檢測到系統(tǒng)已發(fā)生了死鎖，再采取措施解除它。 關(guān)鍵難點(diǎn):確定何時(shí)運(yùn)行死鎖檢測算法2. 死鎖解除；（P66） 重啟、撤銷、剝奪、回滾3. 死鎖預(yù)防；（P62）主要方法：（都會造成系統(tǒng)資源利用率和吞吐率降低）（1）破壞互斥條件：使資源可同時(shí)訪問而不是互斥使用，受資源本身特性限制，可行性較差（2）破壞占有并請求(等待): 靜態(tài)分配（進(jìn)程必須獲得所需要的所有資源才能運(yùn)行），嚴(yán)重降低資源利用效率（3）允許剝奪：剝奪式調(diào)度算法，只適用于CPU和內(nèi)存（4）阻止環(huán)路等待：層次分配策略，低效，限制新設(shè)備類型的增加，使執(zhí)行速度

17、變慢，并可能在無必要的情況下拒絕資源訪問4. 死鎖避免。 （P63） 常見的方法：銀行家算法不是通過對進(jìn)程隨意強(qiáng)加一些規(guī)則，而是通過對每一次資源申請進(jìn)行認(rèn)真的分析來判斷它是否能夠完全的分配，在確定不會發(fā)生死鎖的情況下，才把資源真正分配給進(jìn)程，從而避免死鎖的發(fā)生綜合應(yīng)用：銀行家算法的具體應(yīng)用。（必考） （P63-65） 多種資源的銀行家算法的具體過程：n 【例】設(shè)有五個(gè)進(jìn)程P0, P1, P2, P3, P4，三類資源A, B, C，各擁有資源數(shù)10，5，7，（1）在T0時(shí)刻系統(tǒng)的資源分配情況如下： 當(dāng)前狀態(tài)為： Available=3, 3, 2 則目前系統(tǒng)處于安全狀態(tài)，因?yàn)榇嬖诎踩蛄校篜1

18、, P3, P0, P2, P4，滿足安全性條件（2）假定進(jìn)程P1又要申請1個(gè)A類資源和2個(gè)C類資源，判斷此申請能否獲得批準(zhǔn)？ 首先檢查Request的有效性：Request1(1, 0, 2)<=S1(1, 2, 2)， Request1(1, 0, 2)<=Avaliable(3, 3, 2) 嘗試分配后的狀態(tài)是: Available=(2, 3, 0) Resource = (10, 5, 7) 仍存在一個(gè)執(zhí)行序列P1，P3，P4，P0，P2，滿足安全性條件，因此方案可行（3）如果進(jìn)程P4再發(fā)出資源請求：Request4(3, 3, 0)能否分配？ 系統(tǒng)剩余資源向量Avail

19、able（2，3，0）小于該請求向量，故無法通過有效性檢查，P4進(jìn)程阻塞（4）進(jìn)程P0請求資源 Request0(0,2,0),能否滿足分配？ 雖可通過有效性檢查，但試分配后，系統(tǒng)的剩余資源不能滿足任何進(jìn)程的需求缺口，因而無法找到一個(gè)執(zhí)行序列，將導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，所以不能按P0的請求進(jìn)行資源分配第三章 存儲管理識記：1. 3級存儲器在容量、速度和價(jià)格方面的比較；2. 邏輯地址和物理地址的定義；邏輯地址: 目標(biāo)程序使用的地址物理地址: 程序在物理內(nèi)存中的實(shí)際存儲位置3. 地址重定位及靜態(tài)重定位和動態(tài)重定位； 地址重定位：把程序和數(shù)據(jù)的邏輯地址轉(zhuǎn)換為物理地址，使程序正確運(yùn)行的過程靜態(tài)重定位：

20、在用戶作業(yè)裝入內(nèi)存時(shí)由裝入程序(裝配程序)實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換，地址轉(zhuǎn)換在作業(yè)執(zhí)行前一次完成動態(tài)重定位：程序執(zhí)行過程中，CPU在訪問程序和數(shù)據(jù)之前才實(shí)現(xiàn)地址轉(zhuǎn)換4. 存儲管理的4大功能；1) 內(nèi)存的分配和回收：2) 提高內(nèi)存的利用率：3) 通過虛擬存儲技術(shù)“擴(kuò)充”內(nèi)存容量。4) 內(nèi)存信息保護(hù)5. 虛存的定義； 具有請求調(diào)入功能和置換功能，能夠從邏輯上對內(nèi)存空間進(jìn)行擴(kuò)展，允許用戶的邏輯地址空間大于物理內(nèi)存地址空間的存儲器系統(tǒng)6. 提取頁面的兩種策略；（P103） 請求頁調(diào)入、預(yù)先頁調(diào)入7. 頁式、段式虛存段表表目各個(gè)表項(xiàng)的作用；1) 頁式： (P99)u 狀態(tài)位： 用于標(biāo)志一頁是否已裝

21、入內(nèi)存u 外存地址：頁在外存中的地址u 修改位： 頁在內(nèi)存中是否被修改過的標(biāo)志，用來確定如果該頁被換出內(nèi)存時(shí)，是否需要再回寫入外存u 訪問字段：標(biāo)志頁在內(nèi)存時(shí)是否被訪問過, 用于進(jìn)行頁面置換時(shí)考慮是否將該頁換出內(nèi)存。如果該頁被訪問過，在進(jìn)行頁面置換時(shí)，系統(tǒng)會考慮該頁可能以后會被再次訪問而不將其換出2) 段式: (P109) （？）u 段號，段長u 主存始址（在內(nèi)存中的起始地址），輔存始址（在外存中的起始地址）u 特征位: 該段是否在內(nèi)存。0 (不在主存)；1(在主存)；u 存取權(quán)限: 00(可執(zhí)行)；01(可讀)；11(可寫)；u 擴(kuò)充位: 該段是否可擴(kuò)充。 0(固定長)；1(可擴(kuò)充)；u 標(biāo)

22、志位: 該段是否被修改過，是否移動。 00(未修改)；01(已修改)；11(不可移動)u 共享標(biāo)志：該段能否共享。8. 段頁式虛存管理的基本思想。1) 虛地址以程序的邏輯結(jié)構(gòu)劃分成段(段頁式存儲管理的段式特征)2) 實(shí)地址劃分成位置固定、大小相等的頁框(段頁式存儲管理的頁式特征)3) 將每一段的線性地址空間劃分成與頁框大小相等的頁面，于是形成了段頁式存儲管理的特征。4) 邏輯地址形式為：理解：1. 實(shí)現(xiàn)虛存的基本方法；請求分頁虛擬存儲管理、請求分段虛擬存儲管理、請求段頁虛擬存儲管理2. 分頁存儲管理的基本方法；（P87）頁式存儲管理采用了對進(jìn)程的邏輯地址空間分頁，對內(nèi)存的物理空間分塊，頁的大小

23、等于塊大小等基本思想，通過頁表和地址轉(zhuǎn)換機(jī)構(gòu)實(shí)現(xiàn)邏輯地址到物理地址的變換，能夠有效地利用內(nèi)存空間。3. 頁式虛存的頁表結(jié)構(gòu)；除了要完成從邏輯地址到物理地址的轉(zhuǎn)換外，還需要提供頁面置換的相關(guān)信息。因此，頁表中除了有頁號和物理塊號等信息外，還增加了頁的狀態(tài)位、外存地址、修改位、訪問字段等信息4. 段式虛存管理方法；把作業(yè)的所有分段的副本都存放在輔助存儲器中，當(dāng)作業(yè)被調(diào)度投入運(yùn)行時(shí)，首先把當(dāng)前需要的一段或幾段裝入主存，在執(zhí)行過程中訪問到不在主存的段時(shí)再把它們裝入。5. 動態(tài)地址轉(zhuǎn)換過程。（P78）（?）(地址轉(zhuǎn)換有靜態(tài)重定位和動態(tài)重定位兩種方式)程序執(zhí)行過程中，CPU在訪問程序和數(shù)據(jù)之前才實(shí)現(xiàn)地址轉(zhuǎn)

24、換，稱為動態(tài)重定位。動態(tài)重定位必須借助于硬件地址轉(zhuǎn)換機(jī)構(gòu)來實(shí)現(xiàn)，硬件系統(tǒng)中設(shè)置了一個(gè)定位寄存器，當(dāng)操作系統(tǒng)為某程序分配了一塊內(nèi)存區(qū)域后，裝入程序把程序裝入到所分配的區(qū)域中，然后把該內(nèi)存區(qū)域的起始地址置入定位寄存器中。在程序執(zhí)行過程中需要進(jìn)行地址轉(zhuǎn)換時(shí)，只需將邏輯地址與定位寄存器中的值相加就可得到物理地址。簡單應(yīng)用：頁式虛存的動態(tài)地址的轉(zhuǎn)換過程。（P101） (請求分頁虛擬存儲技術(shù)是在程序執(zhí)行過程中逐步將程序頁面調(diào)入內(nèi)存的，所以從邏輯地址到物理地址的轉(zhuǎn)換是在程序運(yùn)行過程中完成的，是動態(tài)重定位裝入)綜合應(yīng)用：采用不同的頁面置換算法FIFO、LRU，時(shí)鐘置換計(jì)算進(jìn)程執(zhí)行時(shí)的缺頁次數(shù)和缺頁率。（P10

25、5）(一) 先進(jìn)先出頁面置換算法（FIFO）:將所有頁面按進(jìn)入內(nèi)存的次序排成一個(gè)隊(duì)列，設(shè)置一個(gè)替換指針指向隊(duì)頭的一頁。當(dāng)需要進(jìn)行頁面淘汰時(shí)，替換指針指向的即當(dāng)前最先進(jìn)入內(nèi)存的頁面，該頁被淘汰，然后修改指針指向淘汰頁后一個(gè)頁面即可，調(diào)入的新的頁面排入隊(duì)尾n 【例】某進(jìn)程的頁面訪問序列為7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 1 7 0 1，操作系統(tǒng)分配了3個(gè)內(nèi)存物理塊缺頁次數(shù)：12 （最先進(jìn)入的3個(gè)頁面是正常調(diào)入，不是缺頁調(diào)入） 缺頁率：12/21(二) 最近最久未使用頁面置換算法（LRU）:隊(duì)列中存放當(dāng)前在主存中的頁號，每當(dāng)訪問一頁時(shí)就調(diào)整一次，使隊(duì)尾總指向最近訪問

26、的頁，隊(duì)頭就是最近最少用的頁，發(fā)生缺頁中斷時(shí)總淘汰隊(duì)頭所指示的頁；執(zhí)行一次頁面訪問后，需要從隊(duì)列中把該頁調(diào)整到隊(duì)尾淘汰可選頁面中離當(dāng)前頁面向前最遠(yuǎn)的一頁，表示最近最少使用n 【例】某進(jìn)程的頁面訪問序列為7 0 1 2 0 3 0 5 2 3 0 3 2 1 2 0 1 7 0 1，操作系統(tǒng)分配了3個(gè)內(nèi)存物理塊缺頁次數(shù)：9 缺頁率：12/21(三) 時(shí)鐘置換算法（Clock）:在上述加標(biāo)示位的FIFO隊(duì)列基礎(chǔ)上，為了避免頻繁的出隊(duì)入隊(duì)操作，將內(nèi)存中所有頁面組織成一個(gè)循環(huán)隊(duì)列，隊(duì)列指針指向可能要淘汰的頁面，初始值指向最先進(jìn)入內(nèi)存的頁面。§ 實(shí)現(xiàn)要點(diǎn)：每一頁增加了一個(gè)指示位(1)一個(gè)頁面首

27、次裝入主存，其“引用位”置0 。(2)主存中的任何頁面被訪問時(shí), “引用位”置1。(3)淘汰頁面時(shí),從指針當(dāng)前指向的頁面開始掃描循環(huán)隊(duì)列，把遇到的“引用位”是1的頁面的“引用位”清0,跳過這個(gè)頁面; 把所遇到的”引用位”是0的頁面淘汰掉,指針推進(jìn)一步。(4)掃描循環(huán)隊(duì)列時(shí)，如果碰到的所有頁面的”引用位”為1，指針就會繞整個(gè)循環(huán)隊(duì)列一圈，把碰到的所有頁面的”引用位”清0;指針停在起始位置，并淘汰掉這一頁,然后，指針推進(jìn)一步?！耙梦弧焙汀靶薷奈弧苯M合，將置換和寫外存同時(shí)考慮，產(chǎn)生改進(jìn)的時(shí)鐘置換算法，共組合成四種情況：(1)最近沒有被引用,沒有被修改(r=0,m=0)(2)最近沒有被引用,但被修改

28、(r=0,m=1)(3)最近被引用,沒有被修改(r=1,m=0)(4)最近被引用過,也被修改過(r=1,m=1)§ 步1：把碰到的第一個(gè)r=0,m=0的頁面作為淘汰頁面。§ 步2：如果步1失敗，再次從原位置開始，查找r=0且m=1的頁面，把碰到的第一個(gè)這樣的頁面作為淘汰頁面，而在掃描過程中把指針?biāo)鶔哌^的頁面的”引用位”r置0。§ 步3：如果步2失敗，指針再次回到了起始位置，由于此時(shí)所有頁面的”引用位”r均己為0，再轉(zhuǎn)向步1操作，必要時(shí)再做步2操作，這次一定可以挑出一個(gè)可淘汰的頁面。n 【例】假設(shè)采用固定分配策略，進(jìn)程分得三個(gè)頁框,執(zhí)行中按下列次序引用5個(gè)獨(dú)立的頁面

29、: 2 3 2 1 5 2 4 5 3 2 5 2，分別用計(jì)算LRU、FIFO和CLOCK算法中缺頁中斷的次數(shù)。第四章 設(shè)備管理識記：1. 通道的分類；（1）字節(jié)多路通道（2）選擇通道（3）成組多路通道2. 虛擬設(shè)備的定義；為了將慢速的獨(dú)占設(shè)備改造成多個(gè)用戶可共享的設(shè)備，以提高設(shè)備的利用率、提高系統(tǒng)進(jìn)程并行的程度，可借助于假脫機(jī)技術(shù)（SPOOLing）進(jìn)行模擬。模擬獨(dú)占設(shè)備的那部分共享設(shè)備的空間稱為虛擬設(shè)備。3. 設(shè)備分配中所采用的4種表的作用1) 系統(tǒng)設(shè)備表SDT：記錄系統(tǒng)中所有設(shè)備資源的狀態(tài)2) 設(shè)備控制表DCT：記錄設(shè)備的特性、設(shè)備和I/O控制器的連接情況以及設(shè)備的分配和使用情況3) 控制器控制表COCT：反映I/O控制器的使用情況以及所連接的通道情況4) 通道控制表CHCT：與COCT類似理解：1. 設(shè)備管理的任務(wù)和功能；任務(wù)（目標(biāo)？）：（1）提高使用效率 （2）提供便捷的界面功能：（1）設(shè)備的分配與回收 （2）設(shè)備控制和中斷處理 （3）緩沖區(qū)管理 （4）實(shí)現(xiàn)虛擬設(shè)備2. 設(shè)備的4種I/O控制方式及其性能比較；主要差別在于中央處理器和外圍設(shè)備并行工作的方式不同，并行工作的程度不同。1) 查詢方式：對CPU造成極大