南陽理工學(xué)院操作系統(tǒng)復(fù)習(xí)重點

1、 復(fù)習(xí)重點第一章1. 什么是操作系統(tǒng)？操作系統(tǒng)（OS）是直接配置在計算機(jī)硬件上的最基本的系統(tǒng)軟件，負(fù)責(zé)管理計算機(jī)的軟硬件資源，實現(xiàn)對計算機(jī)資源的抽象，為用戶提供方便易用的借口。2. 操作系統(tǒng)的四個目標(biāo)：1）有效性（提高系統(tǒng)資源利用率，提高系統(tǒng)的吞吐量）2）方便些3）可擴(kuò)充性4）開放性3. 操作系統(tǒng)的三大作用：1）OS作為用戶與計算機(jī)硬件系統(tǒng)之間的借口2)OS作為計算機(jī)系統(tǒng)資源的管理者3）OS實現(xiàn)了對計算機(jī)資源的抽象4. 歷史上的三種基本類型的操作系統(tǒng)：多道批處理系統(tǒng)，分時系統(tǒng)，實時系統(tǒng)5. 實時系統(tǒng)，分時系統(tǒng)的比較：1)多路性2）獨立性3）及時性：實時信息處理系統(tǒng)對實時性的要求與分實行系統(tǒng)類似

2、，都是以人所能接受的等待時間來確定，而實時系統(tǒng)的及時性，是以控制對象所要求得的開始截止時間或完成截止時間來確定，一般為秒級到毫級，甚至有的要求低于100微妙。4）交互性：實時信息處理系統(tǒng)雖然也具有交互性，但這是人與系統(tǒng)的交互僅限于訪問系統(tǒng)中某些特定的專用服務(wù)程序。它不像時分系統(tǒng)那樣能像終端用戶提供數(shù)據(jù)處理和資源共享服務(wù)5）可靠性：分時系統(tǒng)雖然也要求系統(tǒng)可靠，但相比之下，實時系統(tǒng)則要求洗頭具有高度的可靠性，因為任何差錯都有可能到來巨大的經(jīng)濟(jì)損失，甚至是無法預(yù)料的災(zāi)難性后果，所以在實時系統(tǒng)中，往往都采取了多級容錯措施來保障系統(tǒng)的安全性及數(shù)據(jù)的安全性。6. 操作系統(tǒng)的四大基本特征：并發(fā)性，共享性，虛

3、擬性，異步性 其中并發(fā)和共享是最基本的特征，有事互為存在的條件，并發(fā)性是最重的特征7. 為什么要引入進(jìn)程？為了是程序能可靠的并發(fā)，于是把程序包裝成進(jìn)程，程序以進(jìn)程實體的方式駐留在內(nèi)存，輪流占用CPU執(zhí)行。8. 進(jìn)程的特征：1）結(jié)構(gòu)特征。程序段、相關(guān)數(shù)據(jù)段和進(jìn)程控制塊(Process Control Block, PCB)三部分構(gòu)成了進(jìn)程實體；2）動態(tài)性。進(jìn)程由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡，此即進(jìn)程的生命期；3）并發(fā)性。引入進(jìn)程的目的就是為了能夠并發(fā)執(zhí)行；4）獨立性。進(jìn)程實體是一個能獨立運(yùn)行、獨立分配資源和獨立接受調(diào)度的基本單位。5）異步性。進(jìn)程實體按照異步方式，各自獨立地以不可預(yù)知的

4、速度向前推進(jìn)。9. 進(jìn)程的三種基本狀態(tài)極其轉(zhuǎn)換關(guān)系：10.進(jìn)程控制塊（PCB）是進(jìn)程實體的一部分，是操作系統(tǒng)中最重要的記錄性數(shù)據(jù)結(jié)構(gòu)，記錄了操作系統(tǒng)所需的、用于描述進(jìn)程的當(dāng)前情況以及控制進(jìn)程運(yùn)行的所有信息。OS是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理11.進(jìn)程控制塊（PCB）是進(jìn)程存在的唯一標(biāo)志。為什么呢？當(dāng)系統(tǒng)創(chuàng)建一個新進(jìn)程時，就為它建立了一個PCB；進(jìn)程結(jié)束時又回收其PCB，進(jìn)程于是也隨之消亡。PCB經(jīng)常被系統(tǒng)訪問，尤其是被運(yùn)行頻率很高的進(jìn)程及分派程序訪問，故PCB應(yīng)常駐內(nèi)存。12.進(jìn)程并發(fā)執(zhí)行時的相互制約關(guān)系1）間接相互制約關(guān)系，源于互斥資源的共享2）直接相互制約關(guān)系，源于進(jìn)程間的合

5、作13.臨界資源和臨界區(qū)的概念：許多硬件資源如打印機(jī)，磁帶機(jī)等，都屬于臨界資源。對于臨界資源(Critical Resource)，無論是硬件臨界資源（打印機(jī)等），還是軟件臨界資源（例如前面討論生產(chǎn)者-消費(fèi)者問題的變量counter），多個進(jìn)程必須互斥地對它進(jìn)行訪問。人們把每個進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)(Critical Section)。14.同步機(jī)制四準(zhǔn)則：空閑讓進(jìn)，忙則等待，有限等待 避免“死等”，讓權(quán)等待 避免“忙等15.信號量機(jī)制：整型信號量：會出現(xiàn)“忙等”，未遵循讓權(quán)等待準(zhǔn)則。 wait(S): while S<=0 do no-op; S:=S-1; signa

6、l(S): S:=S+1; wait(S)和signal(S)均為原子操作(Atomic Operation)。很長時間以來，它們被 稱為P、V操作，P操作請求資源，V操作釋放資源，它們應(yīng)成對出現(xiàn)。 記錄型信號量：不存在“忙等”現(xiàn)象，遵循讓權(quán)等待準(zhǔn)則。 1）記錄型信號量是整型信號量的改進(jìn)。 2）S.value的初值表示系統(tǒng)中某類資源的數(shù)目，因而又稱為資源信號量。 若初值為1則稱之為互斥信號量。 3）wait操作意味著進(jìn)程請求一個單位的該類資源，signal操作意味著進(jìn)程釋放一個單位的該資源。 （大題） type semaphore=record value: integer; L: list

7、of process; End procedure wait(S) var S: semaphore; begin S.value:=S.value-1; if S.value0 then block(S.L); End procedure signal(S) var S: semaphore; begin S.value:=S.value+1; if S.value0 then wakeup(S.L); end信號量可用于實現(xiàn)進(jìn)程間互斥及同步16.用信號量解決生產(chǎn)者-消費(fèi)者問題：利用記錄型信號量解決生產(chǎn)者-消費(fèi)者問題var mutex, empty, full: semaphore:=1,

8、n, 0; buffer: array0,n-1 of item; in, out: integer:=0, 0;parbeginproducer: begin repeat produce an item nextp; wait(empty); wait(mutex); buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); signal(full); until false;endconsumer: begin repeat wait(full); wait(mutex); nextc:=buffer(out); out:=(out+1) m

9、od n; signal(mutex); signal(empty); consume the item in nextc; until false;endparendend17. 三種高級進(jìn)程通信工具：1)共享存儲器(Shared Memory)系統(tǒng)(基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式（低效）基于共享存儲區(qū)的通信方式（高級通信）)2)消息傳遞(Message Passing)系統(tǒng)(是應(yīng)用最為廣泛的一種進(jìn)程間的通信機(jī)制。在該機(jī)制中，進(jìn)程間的數(shù)據(jù)交換是以格式化的消息(message)為單位的。程序員直接利用操作系統(tǒng)提供的一組通信命令(原語)，不僅能實現(xiàn)大量數(shù)據(jù)的傳遞，而且還隱藏了通信的實現(xiàn)細(xì)節(jié)，使通信過

10、程對用戶是透明的，從而大大簡化了通信程序編寫的復(fù)雜性。消息傳遞機(jī)制還是微內(nèi)核操作系統(tǒng)、分布式系統(tǒng)、計算機(jī)網(wǎng)絡(luò)等的最主要的通信工具。以其實現(xiàn)方式的不同，可進(jìn)一步分成直接通信方式和間接通信方式兩種。)3)管道(Pipe)通信(UNIX操作系統(tǒng)首創(chuàng)了這種通信機(jī)制。管道通信以文件系統(tǒng)為基礎(chǔ)，所謂管道(pipe)，就是連接兩個進(jìn)程之間的一個打開的共享文件，它專門用于進(jìn)程之間的通信。發(fā)送進(jìn)程可以執(zhí)行write操作，以字符流的形式源源不斷地向管道（共享文件）的一端寫入數(shù)據(jù)流，而接收進(jìn)程可以執(zhí)行read操作，從管道的另一端按先進(jìn)先出的順序讀出數(shù)據(jù)。管道機(jī)制具有互斥、同步、確定對方是否存在三方面的協(xié)調(diào)能力。)1

11、8. 為什么要引入線程？是為了減少程序在并發(fā)執(zhí)行時所付出的時空開銷，是OS具有更好的得并發(fā)性。19. 從調(diào)度，并發(fā)性，擁有資源，系統(tǒng)開銷方面比較線程和進(jìn)程：1)調(diào)度：傳統(tǒng)操作系統(tǒng)中，進(jìn)程是擁有資源的基本單位，又是獨立調(diào)度、分派的基本單位；而在引入線程的操作系統(tǒng)中，線程是調(diào)度和分派的基本單位，而進(jìn)程是資源擁有的基本單位。2)并發(fā)性：不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且一個進(jìn)程中的多個線程之間亦可并發(fā)執(zhí)行。例如，文件服務(wù)進(jìn)程的多個服務(wù)線程。3)擁有資源：進(jìn)程是擁有資源的基本單位，線程不擁有系統(tǒng)資源(只有一點必不可少的資源)，一個進(jìn)程的代碼段、數(shù)據(jù)段、系統(tǒng)資源等，可供該進(jìn)程中的所有線程共享。4)系統(tǒng)開銷：

12、進(jìn)程的創(chuàng)建、撤銷、切換，操作系統(tǒng)所付出的開銷遠(yuǎn)高于對線程的類似操作的開銷。在一些操作系統(tǒng)中，線程的切換、同步和通信都20.高級調(diào)度：又稱作業(yè)調(diào)度或長程調(diào)度，其主要功能是根據(jù)某些算法，吧外存上處于后備隊列中的那些作業(yè)調(diào)入內(nèi)存。21.低度調(diào)度：又稱進(jìn)程調(diào)度，是從內(nèi)存的就緒隊列中選擇某個進(jìn)程使它優(yōu)先獲得CPU進(jìn)入執(zhí)行態(tài)。進(jìn)程調(diào)度有搶占方式和非搶占方式兩種方式。搶占方式主要基于優(yōu)先權(quán)原則，短進(jìn)程優(yōu)先原則，時間片原則22.比較先來先服務(wù)（FCFS）和短作業(yè)（進(jìn)程）（SJ（P）F）優(yōu)先兩種調(diào)度算法的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。（大題10分）優(yōu)點：短進(jìn)程優(yōu)先調(diào)度算法能有效地降低作業(yè)的平均等待時間，提高系

13、統(tǒng)吞吐量。缺點：1）對長作業(yè)不利，會導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度(Starvation)；2）完全未考慮作業(yè)的緊迫程度；3）作業(yè)(進(jìn)程)的長短是預(yù)估的，不一定準(zhǔn)確。公式：平均周轉(zhuǎn)時間：從每個進(jìn)程的完成時間減去到達(dá)時間，即為周轉(zhuǎn)時間 平均帶權(quán)周轉(zhuǎn)時間：每個進(jìn)程的周轉(zhuǎn)時間與其服務(wù)時間之比，即為帶權(quán)時間23. 產(chǎn)生死鎖的原因;1）競爭資源（當(dāng)系統(tǒng)中供多個進(jìn)程共享的資源如打印機(jī)，公用隊列，其數(shù)目不足以滿足進(jìn)程的需要時，會引起諸進(jìn)程對資源的競爭而產(chǎn)生死鎖） 2）進(jìn)程間推進(jìn)順序非法（進(jìn)程在運(yùn)行過程中，請求和釋放資源的順序不當(dāng)，也會同樣導(dǎo)致產(chǎn)生進(jìn)程死鎖）24. 產(chǎn)生死鎖的四大必要條件：1）互斥條件，2）請

14、求和保持條件，3）不剝奪條件，4）環(huán)路等待條件25. 處理死鎖的四種方法：1）預(yù)防死鎖，2）避免死鎖，3)檢測死鎖，4）解除死鎖（剝奪資源，撤銷進(jìn)程）26. 避免死鎖：系統(tǒng)的安全狀態(tài)與不安全狀態(tài) （安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序，即安全序列P1，P2， ，Pn，來為每個進(jìn)程Pi分配所需資源，直至滿足每個進(jìn)程對資源的最大需求，使每個進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后，便有可能進(jìn)而進(jìn)入死鎖狀態(tài)。避免死鎖的實質(zhì)在于：系統(tǒng)在進(jìn)行資源分配時，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)）假定系統(tǒng)中有三個進(jìn)程P1、P2、P3，共有12臺磁帶機(jī)。假設(shè)在T0

15、時刻，P1、P2、P3已分別獲得5臺、2臺、2臺磁帶機(jī)，尚有3臺空閑未分配，如左表所示。經(jīng)分析發(fā)現(xiàn)，存在一個安全序列P2，P1，P3，能使每個進(jìn)程最終都順利完成，所以說T0時刻系統(tǒng)處于安全狀態(tài)。假設(shè)T0時刻之后，P3又請求1臺磁帶機(jī)，系統(tǒng)（在T1時刻）滿足了它的請求，于是系統(tǒng)進(jìn)入了不安全狀態(tài)，如右表所示，此時再也無法找到一個安全序列。27. 銀行家算法：（大題）假定系統(tǒng)中有五個進(jìn)程P0、P1、P2、P3、P4和三類資源A、B、C，各類資源數(shù)量分別為10、5、7，在T0時刻資源分配情況如下：(1) 利用安全性算法分析可知，在T0時刻存在安全序列P1，P3，P4，P2，P0，故系統(tǒng)是安全的。28.

16、存儲器層次結(jié)構(gòu)：在存儲器層次結(jié)構(gòu)中，越往高層則存取存取速度越快，容量越小，例如一臺計算機(jī)的寄存器總?cè)萘孔疃嗖贿^幾KB，而內(nèi)存可以達(dá)到幾GB甚至更大。29. 動態(tài)分區(qū)分配：常用的數(shù)據(jù)結(jié)構(gòu)有兩種形式：1）空閑分區(qū)表，2）空閑分區(qū)連。 分區(qū)分配算法：1）首次適應(yīng)算法（first fit）從空閑鏈?zhǔn)祝ǖ椭罚╅_始順序查找，直到找到一個大小能滿足要求的空閑分區(qū)，從該分區(qū)割下一塊空間分配給請求者，余下的空間仍留在空閑鏈中。該算法可保留高址部分的大空閑區(qū)，但會導(dǎo)致低址部分不斷被劃分，低址會產(chǎn)生很多碎片，增加查找空閑分區(qū)的開銷，不利于大作業(yè)。2)循環(huán)首次適應(yīng)算法（next fit）是first fit的變形。不

17、再是從鏈?zhǔn)祝ǖ椭罚╅_始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找。優(yōu)點是使空閑分區(qū)分布得更均勻，減少查找開銷，缺點是會缺乏大的空閑分區(qū)。3)最佳適應(yīng)算法（best fit）每次分配內(nèi)存時，總是把能滿足需求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。缺點是會在存儲器中留下許多難以利用的小碎片4)最壞適應(yīng)算法（worst fit)與best fit相反，挑最大的空閑區(qū)分割給作業(yè)使用。優(yōu)點是產(chǎn)生碎片的幾率最小，缺點是會缺乏大的空閑分區(qū)。5)快速適應(yīng)算法（quick fit）30.分頁式存儲管理：若給定邏輯地址A，頁面大小為L，則：頁號P 頁面地址d31 12 11 031. 再由業(yè)

18、號，查頁表可得到塊號，而頁內(nèi)地址與塊內(nèi)地址相同，于是完成了邏輯地址到物理地址的轉(zhuǎn)換。32. 地址變換時什么情況下會產(chǎn)生越界中斷：如果頁號大于或等于頁表長度，則表示本次所訪問的地址已經(jīng)超越進(jìn)程的地址空間。于是，這一錯誤將被系統(tǒng)發(fā)現(xiàn)并產(chǎn)生一地址越界中斷。33. 分頁系統(tǒng)中，若沒有引入快表，則每存取一個數(shù)據(jù)要兩次訪問內(nèi)存。34. 分頁和分段的區(qū)別與聯(lián)系：它們都屬于離散分配方式。分頁是從系統(tǒng)的角度，為了徹底解決碎片問題，提高內(nèi)存利用率；而分段是為了方便用戶，便于信息的共享與保護(hù)等。分頁的邏輯地址是一維的，而分段的邏輯地址是二維的。頁面大小固定，而段的長度不固定。段表跟頁表相似，地址變換時都可能產(chǎn)生越界

19、中斷。分段系統(tǒng)中，若沒引入快表則每存取一個數(shù)據(jù)要兩次訪問內(nèi)存35. 段頁式存儲管理方式是分段和分頁的結(jié)合，段頁式系統(tǒng)中，若沒引入快表，則每存取一個數(shù)據(jù)要三次訪問內(nèi)存。36. 虛擬寄存器：是指具有(頁或段)請求調(diào)入功能和(頁或段)置換功能，能在物理上不增加內(nèi)存容量的前提下，從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。其邏輯容量最大可接近內(nèi)存容量和外存容量之和，運(yùn)行速度接近內(nèi)存，單位容量的成本卻接近外存。37. 虛擬寄存器的四大特征：）虛擬性：從邏輯上擴(kuò)充內(nèi)存容量，使用戶看到的內(nèi)存容量遠(yuǎn)大于實際容量。是虛擬存儲器所表現(xiàn)出來的最重要的特征。虛擬性是以多次性和對換性為基礎(chǔ)的。）多次性：一個作業(yè)被分成多

20、次調(diào)入內(nèi)存運(yùn)行。是虛擬存儲器最重要的特征。） 對換性：允許作業(yè)在運(yùn)行過程中將一些程序和數(shù)據(jù)甚至是進(jìn)程在內(nèi)存和外存之間換進(jìn)、換出。）離散性：多次性和對換性建立在離散性的基礎(chǔ)上。離散性是虛擬存儲器最本質(zhì)的特征。38. 請求分頁系統(tǒng)：增加了請求調(diào)頁與頁面置換功能。39. 什么情況下會產(chǎn)生缺頁中斷：在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存。40. 三種頁面置換算法（的三幅圖是重點）：1）最佳置換算法：往后看哪一個最晚被訪問是哪一個就被淘汰2） 置換算法：顧名思義就是哪一個先被訪問過就淘汰哪一個）LRU置換算法：叫做最近最久未使用置換方法，其顧名思義是

21、往前看哪一個最靠前被訪問就淘汰哪一個。41. I/O控制方式：1）程序I/O方式：早期的計算機(jī)系統(tǒng) 2）中斷驅(qū)動I/O控制方式：引入中斷機(jī)制的現(xiàn)代計算機(jī)系統(tǒng)，使用于字符設(shè)備 3）直接存儲訪問I/O控制方式：引入了控制器的現(xiàn)代計算機(jī)系統(tǒng)，適用于塊設(shè)備。）I/O通道控制方式：引入了I/O通道的現(xiàn)代大中型計算機(jī)系統(tǒng)，進(jìn)一步減少的干預(yù)。（此處可出選擇和簡答題）老師給出的例子“鍵盤設(shè)備的I/O控制方式是？”答：中斷驅(qū)動I/O控制方式“磁盤設(shè)備的I/O控制方式是？”答：I/O控制方式在早期的計算機(jī)系統(tǒng)中，采用程序I/O方式；系統(tǒng)中引入中斷機(jī)制后，I/O控制方式便發(fā)展為中斷驅(qū)動(Interrupt Driv

22、en)方式；隨著DMA控制器的出現(xiàn)，I/O控制方式發(fā)展為DMA方式，從以字節(jié)為單位擴(kuò)大到以數(shù)據(jù)塊為單位進(jìn)行傳輸，大大改善塊設(shè)備的I/O性能；I/O通道方式的引入，使對I/O操作的組織和數(shù)據(jù)的傳送都能獨立地進(jìn)行而無需CPU干預(yù)。42. 緩沖的三條原因或作用：1）緩和CPU與I/O設(shè)備間速度不匹配的矛盾；2）減少對CPU的中斷頻率，放寬對CPU中斷響應(yīng)時間的限制；3）提高CPU和I/O設(shè)備之間的并行性。43. 單緩沖區(qū)：操作系統(tǒng)將該緩沖區(qū)中的數(shù)據(jù)傳到用戶區(qū)的時間為M，I/O設(shè)備輸入數(shù)據(jù)(T)和CPU對數(shù)據(jù)處理(C)兩者是可以并行的，當(dāng)T>C時，系統(tǒng)對每一塊數(shù)據(jù)的處理時間為M+T，反之則為M+

23、C，故可把系統(tǒng)對每一塊數(shù)據(jù)的處理時間表示為Max(C，T)+M。44. 雙緩沖區(qū)：雙緩沖又稱為緩沖對換(Buffer Swapping)，可加快輸入輸出速度，提高設(shè)備利用率。雙緩沖時，系統(tǒng)處理一塊數(shù)據(jù)的時間可以粗略地認(rèn)為是Max(C，T)。如果C<T，可使塊設(shè)備連續(xù)輸入；如果C>T，則可使CPU不必等待設(shè)備輸入45. I/O軟件：I/O軟件的總體目標(biāo)是高效性和通用性46. I/O軟件的層次結(jié)構(gòu)：1）用戶層軟件(高層)：實現(xiàn)與用戶交互接口，用戶可直接調(diào)用在用戶層提供的，與I/O操作有關(guān)的庫函數(shù)，對設(shè)備進(jìn)行操作。2）設(shè)備獨立性軟件(中間層)：負(fù)責(zé)實現(xiàn)與設(shè)備驅(qū)動器的統(tǒng)一接口，設(shè)備命名，設(shè)

24、備的保護(hù)以及設(shè)備的分配與釋放等，同時為設(shè)備管理與數(shù)據(jù)傳送提供必要的存儲空間。3）設(shè)備驅(qū)動程序(低層)：與硬件直接相關(guān)，負(fù)責(zé)具體實現(xiàn)系統(tǒng)對設(shè)備發(fā)出的操作指令，驅(qū)動I/O設(shè)備工作的驅(qū)動程序。4）中斷處理程序(最低層)：用于保存被中斷進(jìn)程的CPU環(huán)境，轉(zhuǎn)入相應(yīng)的中斷處理程序進(jìn)行處理，處理完后再恢復(fù)被中斷進(jìn)程的現(xiàn)場后返回到被中斷進(jìn)程。此圖為重點圖之一在課本P179頁可出選擇或簡答題（同上所訴）47.設(shè)備分配：需要用到一下幾種數(shù)據(jù)結(jié)構(gòu);DCT(設(shè)備控制表)，COCT（控制器控制表），CHCT（通道控制表），SDT（系統(tǒng)設(shè)備表）48. SPOOLing技術(shù)：體現(xiàn)了操作系統(tǒng)的四大特征之一：虛擬性，第一章講過

25、脫機(jī)輸入、輸出技術(shù)，可緩和CPU高速性和I/O設(shè)備低速性的矛盾。在多道程序系統(tǒng)中，可用一個進(jìn)程SPi模擬脫機(jī)輸入的外圍機(jī)，把低速輸入設(shè)備上的數(shù)據(jù)傳送到高速磁盤上；用另一個進(jìn)程SPo模擬脫機(jī)輸出的外圍機(jī)，把數(shù)據(jù)從高速磁盤傳送到低速輸出設(shè)備上。這樣在CPU的直接控制下，模擬脫機(jī)輸入、輸出功能，使外圍操作與CPU對數(shù)據(jù)的處理同時進(jìn)行，這種聯(lián)機(jī)操作稱為SPOOLing(Simultaneous Peripheral Operations On-Line)，或稱為假脫機(jī)操作。48.SPOOLing系統(tǒng)的特點：1）提高了I/O的速度 2）將獨占設(shè)備改為共享設(shè)備 3）實現(xiàn)了虛擬設(shè)備的功能49.尋道時間（T）

26、：其占據(jù)了磁盤訪問時間的大頭，且可用磁盤調(diào)度算法進(jìn)行優(yōu)化。 改時間是啟動磁臂的時間S與磁頭移動n條磁道所花費(fèi)的時間之和，即 T=m x n + s 其中m是一常數(shù)50.磁盤調(diào)度算法：1）先來先服務(wù)（FCFS）算法：平均尋道長度最大，故僅適用于請求磁盤I /O的進(jìn)程數(shù)目較少的場合。根據(jù)進(jìn)程請求訪問磁盤的先后次序進(jìn)行調(diào)度。缺點是平均尋道距離大，平均尋道時間長。2）最短尋道時間優(yōu)先算法（SSTF）：存在starvation（饑餓）現(xiàn)象，優(yōu)先選擇要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近的進(jìn)程，以使每次尋道時間最短，但SSTF算法不能保證平均尋道時間最短，并且可能導(dǎo)致進(jìn)程饑餓(starvation)現(xiàn)

27、象。3）掃描（SCAN）算法又稱電梯調(diào)度算法：該算法不僅考慮欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮磁頭當(dāng)前的移動方向。其磁頭移動規(guī)律頗似電梯的運(yùn)行，又稱電梯調(diào)度算法。既有較好的尋道性能，又避免饑餓現(xiàn)象。4）循環(huán)掃描（CSCAN）：CSCAN是SCAN變種，規(guī)定磁頭只能單向移動(例如自里向外)，移動到最外磁道訪問后立即移動到最里的欲訪問磁道，亦即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán)。相比SCAN可降低進(jìn)程的最大等待時間(由2T降到TSmax)。5）算法和算法：SSTF、SCAN、CSCAN都可能會出現(xiàn)磁臂粘著(arm stickiness)現(xiàn)象，即有一個或幾個進(jìn)程對某一磁道訪問頻率很高，磁臂停

28、留在該磁道不動，從而壟斷了整個磁盤設(shè)備，在高密度磁盤上容易出現(xiàn)此情況。N步SCAN算法是將磁盤請求隊列分成若干個長度為N的子隊列，磁盤調(diào)度將按FCFS算法依次處理這些子隊列，而每處理一個隊列時又是按SCAN算法?？杀苊庹持F(xiàn)象。當(dāng)N取值很大時，NStepSCAN接近SCAN；當(dāng)N=1時， NStepSCAN退化為FCFS。FSCAN實質(zhì)上是對NStepSCAN的簡化，只將磁盤請求隊列分成兩個子隊列。一個是由當(dāng)前所有請求磁盤I/O的進(jìn)程形成的隊列，另一個是掃描期間新出現(xiàn)的所有請求磁盤I/O的進(jìn)程形成的等待隊列。先來先服務(wù)（FCFS）算法最短尋道時間優(yōu)先算法（SSTF）掃描（SCAN）算法又稱電梯

29、調(diào)度算法循環(huán)掃描（CSCAN） 第六章 文件管理（p-208）（重點）文件的邏輯結(jié)構(gòu)：是從用戶觀點出發(fā)所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，獨立于文件的物理特性，又稱為文件組織(File Organization)。（重點）文件的物理結(jié)構(gòu)：又稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存儲組織形式，不僅與存儲介質(zhì)性能有關(guān)，而且與所采用的外存分配方式有關(guān)。無論是文件的邏輯結(jié)構(gòu)，還是其物理結(jié)構(gòu)，都會影響到文件的檢索速度。文件邏輯結(jié)構(gòu)的類型有結(jié)構(gòu)文件。根據(jù)每個記錄的長度，可分為定長記錄、變長記錄兩類；根據(jù)各記錄的組織形式，可分為順序文件、索引文件、索引順序文件三種。無結(jié)構(gòu)文件，即流式文

30、件文件的邏輯結(jié)構(gòu)：順序文件:文件是記錄的集合，文件中的記錄可以是任意順序的，可歸納為串結(jié)構(gòu)和順序結(jié)構(gòu)兩種。串結(jié)構(gòu)文件的檢索只能逐個記錄遍歷，而對順序結(jié)構(gòu)文件可有更好的檢索效率。順序文件的優(yōu)點是對諸數(shù)據(jù)進(jìn)行批量存取時效率最高，并且只有順序文件能存儲在磁帶上。缺點是在文件較大時，查找或修改單個記錄性能很差，尤其是采用變長記錄的順序文件開銷更大；并且，增加或刪除一個記錄都比較困難。索引文件:對于定長記錄的順序文件可較方便地實現(xiàn)直接存取，但變長記錄的直接存取是十分低效的，檢索時間太長。所以可為其建立一張索引表，而索引表本身是一個定長記錄的順序文件。對索引文件檢索分為兩步，第一步可用折半查找法檢索索引表

31、，找到相應(yīng)表項；第二步利用該表項指向記錄的指針，訪問該條記錄。索引文件可用于對信息處理及時性要求較高的場合。缺點是存儲費(fèi)用高。索引順序文件:索引順序文件可能是最常見的一種邏輯文件形式，可看作是順序文件和索引文件的折衷。它將順序文件中的所有記錄分為若干個組，為順序文件建立一張稀疏索引表，在稀疏索引表中為每組中的第一個記錄建立一個索引項，其中含有該記錄的鍵值和指向該記錄的指針。檢索時，首先利用用戶提供的關(guān)鍵字(鍵值) 檢索稀疏索引表，再利用順序查找法查找主文件。其中，順序文件的檢索性能最差，索引文件的存儲成本最高，索引順序文件是前兩者的折中。常用的外存分配方法有連續(xù)分配、鏈接分配和索引分配三種。文

32、件的物理結(jié)構(gòu)：文件的物理結(jié)構(gòu)直接與外存分配方式有關(guān)。采用連續(xù)分配方式時，形成順序式的文件物理結(jié)構(gòu)；鏈接分配方式形成鏈接式文件物理結(jié)構(gòu)；索引分配方式形成索引式文件物理結(jié)構(gòu)。連續(xù)分配(順序結(jié)構(gòu))：連續(xù)分配(Continuous Allocation)為每個文件分配一組相鄰接的盤塊。此時的物理文件稱為順序文件。應(yīng)在目錄項的文件物理地址字段中，記錄該文件第一個記錄所在的盤塊號和文件長度(以盤塊數(shù)進(jìn)行計量)。優(yōu)點：順序訪問容易，且順序訪問速度快(磁頭移動距離最短)。缺點： 要求有連續(xù)的存儲空間，與內(nèi)存動態(tài)分配類似，會產(chǎn)生大量碎片，緊湊開銷很大； 必須事先知道文件長度，容易造成外存空間的嚴(yán)重浪費(fèi)。（重點）

33、鏈接分配：鏈接分配(Chained Allocation)將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，把這樣形成的物理文件稱為鏈接文件。鏈接分配屬于離散分配方式，消除了外存碎片，顯著提高了外存空間利用率，并且當(dāng)文件動態(tài)增長時可動態(tài)再分配盤塊，無需事先知道文件大小，對文件的增、刪、改也十分方便。鏈接分配又分為隱式鏈接和顯式鏈接兩種形式。1.隱式鏈接：采用隱式鏈接分配方式，在文件目錄的每個目錄項中須含有指向鏈接文件第一個盤塊和最后一個盤塊的指針，而在每個盤塊中都含有一個指向下一個盤塊的指針。2.顯式鏈接：把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張鏈接表中，該表對整個磁盤僅設(shè)置一張，稱

34、為文件分配表(File Allocation Table, FAT)。文件的第一個盤塊號，作為文件地址被填入文件的FCB的物理地址字段中。由于查找記錄的過程是在內(nèi)存中進(jìn)行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁盤的次數(shù)。FAT和NTFS技術(shù)在早期的MS-DOS的FAT文件系統(tǒng)中最早引入了卷的概念，把一個物理硬盤分成四個邏輯磁盤，分別是C: 、D: 、E: 、F: 。為了適應(yīng)磁盤容量不斷增大的需要，在進(jìn)行盤塊分配時，不再以盤塊而是以簇(cluster)為基本單位。簇是一組連續(xù)的扇區(qū)，其容量可以是一個扇區(qū)(512B)、兩個扇區(qū)、四個扇區(qū)、八個扇區(qū)(4KB)等。一個簇包含扇區(qū)的數(shù)量與最

35、大支持的磁盤容量大小直接相關(guān)。相比于FAT12、FAT16，F(xiàn)AT32可管理更多的簇，(相比于FAT16)可采用較小的簇，碎片減少，同時支持更大的磁盤空間。FAT32的每個簇固定為4KB，可管理的單個最大磁盤空間大到 4KB×232 = 16TB。缺點是不支持小分區(qū)，單個文件的長度不能大于4GB，且不能向下兼容。索引分配1. 單級索引分配：索引分配與鏈接分配同屬于離散分配方式。索引分配可克服鏈接分配方式的兩個缺點：(1) 不能高效的直接存??；(2) FAT表占用較大的內(nèi)存空間。單級索引分配方式為每個文件分配一個索引塊(表)，再把分配給該文件的所有盤塊號都記錄在該索引塊中。當(dāng)文件較大時

36、，索引分配方式優(yōu)于鏈接分配方式。但它的缺點是：對于小文件，其索引塊的利用率很低，此時索引分配方式反而不如鏈接分配方式。2. 多級索引分配：對大文件分配磁盤空間時，可采用兩級索引的方式，如果文件非常大，還可用三級、四級索引分配方式。倘若盤塊大小為4KB，每個盤塊號占4個字節(jié)，則一個索引塊中可存放1024個盤塊號，采用兩級索引最大支持的文件長度可達(dá)1024 × 1024 × 4KB = 4GB。（重點）3. 混合索引分配方式：在UNIX的文件系統(tǒng)中采用混合索引分配方式，是將多種索引分配方式相結(jié)合形成的一種分配方式。索引結(jié)點中設(shè)置了13個地址項，其中iaddr(0) iaddr(

37、9)存放直接地址；iaddr(10)提供一次間接地址，實質(zhì)上就是一級索引分配方式；iaddr(11)提供二次間接地址，實質(zhì)上就是二級索引分配方式；iaddr(12)提供三次間接地址。假設(shè)每個盤塊大小為4KB，每個盤塊號占4個字節(jié)。當(dāng)文件不大于40KB時，可從地址項iaddr(0) iaddr(9)直接讀出文件的全部盤塊號。地址項iaddr(10)提供一次間接地址，實質(zhì)上是一級索引分配方式，而一次間址塊中可存放1K個盤塊號，因此最大支持文件長度為4MB40KB。同理，iaddr(11)提供二次間接地址，實質(zhì)上是二級索引分配方式，最大支持文件長度為4GB4MB40KB。iaddr(12)提供三次間接地址，最大支持文件長度為4TB4GB4MB40KB。目錄結(jié)構(gòu)1.