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

1、三條主線：一、操作系統(tǒng)的功能: 資源管理+接口二、操作系統(tǒng)的實(shí)現(xiàn)： 數(shù)據(jù)結(jié)構(gòu)+算法三、一個(gè)進(jìn)程的生命周期進(jìn)程是有生命周期的，產(chǎn)生、運(yùn)行、暫停、終止。對進(jìn)程的這些操作叫進(jìn)程控制。貫穿始終的一些概念:時(shí)間與空間邏輯與物理第一章：1、什么是OS，操作系統(tǒng)的功能。OS是計(jì)算機(jī)系統(tǒng)資源的管理者處理機(jī)管理： 用于分配和控制處理機(jī)（對進(jìn)程、線程的管理）；存儲(chǔ)器管理： 主要負(fù)責(zé)內(nèi)存的分配與回收；I/O設(shè)備管理： 負(fù)責(zé)I/O設(shè)備的分配與操縱；文件管理： 負(fù)責(zé)文件的存取、共享和保護(hù)。2、了解操作系統(tǒng)的發(fā)展過程，了解分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)、批處理系統(tǒng)及特點(diǎn)。分時(shí)系統(tǒng)：是指在一臺(tái)主機(jī)上連接了多個(gè)帶有顯示器和鍵盤的終端，同

2、時(shí)允許多個(gè)用戶共享主機(jī)中的資源，每個(gè)用戶都可以通過自己的終端以交互方式使用計(jì)算機(jī)。(1) 多路性 (2) 獨(dú)立性 (3) 及時(shí)性 (4) 交互性實(shí)時(shí)系統(tǒng)：是指系統(tǒng)能及時(shí)(或即時(shí))響應(yīng)外部事件的請求，在規(guī)定的時(shí)間內(nèi)完成對該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。 (1) 多路性 (2)獨(dú)立性 (3)及時(shí)性 (4)交互性 (5)可靠性。單道批處理：是指系統(tǒng)中有一個(gè)監(jiān)控程序，它負(fù)責(zé)完成用戶程序的調(diào)入、啟動(dòng)運(yùn)行、輸出運(yùn)行結(jié)果等工作。(1) 自動(dòng)性 (2)順序性 (3)單道性3、理解多道程序設(shè)計(jì)概念。后備隊(duì)列作業(yè)調(diào)度外存內(nèi)存4、現(xiàn)代操作系統(tǒng)的特點(diǎn)。 并發(fā) 共享 異步 虛擬5、操作系統(tǒng)的作用，操作系

3、統(tǒng)作為硬件與用戶間接口的觀點(diǎn)。*操作系統(tǒng)作為計(jì)算機(jī)系統(tǒng)資源的管理者。*操作系統(tǒng)是用戶與計(jì)算機(jī)硬件之間的接口，操作系統(tǒng)向用戶提供各種服務(wù)。*操作系統(tǒng)實(shí)現(xiàn)了對計(jì)算機(jī)資源的抽象，擴(kuò)充了機(jī)器功能。第二章：進(jìn)程管理1、理解并發(fā)與并行的區(qū)別與聯(lián)系。并發(fā)：同一個(gè)cpu上在多個(gè)程序間切換運(yùn)行多個(gè)程序并行：每個(gè)cpu運(yùn)行一個(gè)程序宏觀上兩者都是同時(shí)執(zhí)行。2、程序與進(jìn)程及線程的關(guān)系。程序是一組用計(jì)算機(jī)語言編寫的命令序列的集合。進(jìn)程是已運(yùn)行程序的實(shí)體，是線程的容器。線程是進(jìn)程中某個(gè)單一順序的控制流，指運(yùn)行中的程序的調(diào)度單位。不能單獨(dú)執(zhí)行，必須組成進(jìn)程。一個(gè)程序至少有一個(gè)進(jìn)程，一個(gè)進(jìn)程至少有一個(gè)線程。 3、原

4、語及原語的特點(diǎn)和作用。原語：一種特殊的、執(zhí)行時(shí)不可中斷的系統(tǒng)調(diào)用作用：實(shí)現(xiàn)進(jìn)程的通信和控制4、PCB及重要作用，需要聯(lián)系操作系統(tǒng)每一章來理解。進(jìn)程控制塊PCB是操作系統(tǒng)為描述和控制進(jìn)程運(yùn)行為每個(gè)進(jìn)程定義的數(shù)據(jù)結(jié)構(gòu)。PCB作為進(jìn)程實(shí)體的一部分，記錄了操作系統(tǒng)所需的，用于描述進(jìn)程的當(dāng)前情況以及管理進(jìn)程運(yùn)行的全部信息，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。OS是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。PCB的作用（1）作為獨(dú)立運(yùn)行基本單位的標(biāo)志。 PCB成為進(jìn)程存在于系統(tǒng)中的唯一標(biāo)志。（2）能實(shí)現(xiàn)間斷性運(yùn)行方式。PCB保存運(yùn)行時(shí)CPU現(xiàn)場信息。（3）提供進(jìn)程管理所需要的信息。PCB中保存了進(jìn)程資

5、源信息。（4）提供進(jìn)程調(diào)度所需要的信息。PCB中保存了進(jìn)程狀態(tài)、優(yōu)先級(jí)等信息。（5）實(shí)現(xiàn)與其它進(jìn)程的同步與通信。PCB中設(shè)置信號(hào)量、用于進(jìn)程通信的區(qū)域或通信隊(duì)列指針。5、進(jìn)程的基本狀態(tài)及狀態(tài)間的轉(zhuǎn)換，需要聯(lián)系其它章節(jié)的內(nèi)容。(1)就緒(Ready)狀態(tài)：當(dāng)進(jìn)程已分配到除CPU以外的所有資源后，只要再獲得CPU，便可立即執(zhí)行，進(jìn)程這時(shí)的狀態(tài)稱為就緒狀態(tài)。(2)執(zhí)行(Running)狀態(tài)：進(jìn)程已獲得CPU，程序正在執(zhí)行。(3)阻塞(Block)狀態(tài)：正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時(shí)無法繼續(xù)執(zhí)行時(shí)，放棄處理機(jī)而處于暫停狀態(tài)，稱為阻塞狀態(tài)（等待/封鎖狀態(tài)）。6、了解進(jìn)程控制，包括引起進(jìn)程控制的事件及

6、進(jìn)程控制的操作。進(jìn)程的創(chuàng)建(1)申請空白PCB(2)為新進(jìn)程分配資源(3)初始化進(jìn)程控制塊(4)將新進(jìn)程插入就緒隊(duì)列，如果進(jìn)程就緒隊(duì)列能夠接納新進(jìn)程，便將新進(jìn)程插入就緒隊(duì)列引起事件 (1-3系統(tǒng)內(nèi)核創(chuàng)建4基于用戶需求創(chuàng)建)(1)用戶登錄(2)作業(yè)調(diào)度(3)提供服務(wù)(4)應(yīng)用請求進(jìn)程的終止(1)根據(jù)被終止進(jìn)程的標(biāo)識(shí)符，從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài)。(2)若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。(3)若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程予以終止，以防他們成為不可控的進(jìn)程。(4)將被終止進(jìn)程所擁有的

7、全部資源，或者歸還給其父進(jìn)程， 或者歸還給系統(tǒng)。(5)將被終止進(jìn)程(它的PCB)從所在隊(duì)列(或鏈表)中移出， 等待其他程序來搜集信息。引起事件(1)正常結(jié)束(2)異常結(jié)束（進(jìn)程運(yùn)行期間，出現(xiàn)某些錯(cuò)誤和故障）(3)外界干預(yù)（操作員、操作系統(tǒng)、父進(jìn)程請求、父進(jìn)程終止）進(jìn)程的阻塞與喚醒(1)向系統(tǒng)請 求共享資源失敗(2) 等待某種操作的完成(3) 新數(shù)據(jù)尚未到達(dá) (4) 無新工作可做7、理解信號(hào)量的作用，及對信號(hào)量的PV操作（信號(hào)量值的變化），會(huì)用信號(hào)量解決進(jìn)程同步問題（包括前趨圖和進(jìn)程同步與互斥）。保證兩個(gè)或多個(gè)關(guān)鍵代碼段不被并發(fā)調(diào)用。整型信號(hào)量：整型量S僅能通過原子操作wait(S)和signa

8、l(S)來訪問分別被稱為P、V操作wait(S)while （S0）；/* do no-op*/ S- -;signal(S) S+; 進(jìn)程同步問題1、有一閱覽室，共有100個(gè)座位。讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一座位列一表目，包括座號(hào)和讀者姓名。讀者離開時(shí)要消掉登記內(nèi)容。試用P、V操作描述讀者進(jìn)程的同步結(jié)構(gòu)。varmutex: semaphere; 信號(hào)量，用于互斥full : semaphere; 信號(hào)量，用于同步table : array 0.n-1 of item; 登記表procedure reader;讀者進(jìn)程beginP(full);P(mutex);Registe

9、r_name(table)；V(mutex);Reading；P(mutex);Delet_name(table);V(mutex);V(full)end;beginseminitsal(mutex.v,1; full.v,100);初始化cobeginreader;reader;.coendend.2、設(shè)公共汽車上有一位司機(jī)和一位售票員，它們的活動(dòng)如下：司機(jī)： 售票員：啟動(dòng)車輛 售票 正常行車 開車門 到站停車 關(guān)車門請分析司機(jī)與售票員之間的同步關(guān)系，如何用PV操作實(shí)現(xiàn)。答：為了安全起見，顯然要求：關(guān)車門后才能啟動(dòng)車輛；到站停車后才能開車門。所以司機(jī)和售票員在到站、開門、關(guān)門、啟動(dòng)車輛這幾個(gè)

10、活動(dòng)之間存在著同步關(guān)系。用兩個(gè)信號(hào)量close,open以開車和可以開門，close,open=0,PV操作實(shí)現(xiàn)司機(jī)進(jìn)程和售票員進(jìn)程同步的算法描述如下：n Semaphore close=0，stop=0；n driver( )/*司機(jī)*/while(True) P(close);啟動(dòng)車輛;正常行車;到站停車;V(stop);n Conductor( )/*售票員*/while(True)關(guān)車門;V(close);售票;P(stop);開車門;上下乘客;3、桌上有一個(gè)盤子，每次只能放入一個(gè)水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放桔子，一個(gè)兒子專等吃盤子中的桔子，一個(gè)女兒專等吃盤子里的蘋果。

11、試用PV操作實(shí)現(xiàn)四個(gè)人的同步，并寫出程序描述。 Main ( )Semaphore S空=1;Semaphore S蘋果=0;Semaphore S桔子=0； cobegin father( ); mother( ); son( ); daughter( ); coendfather ( ) while(.) p(S空）； 放蘋果； v(S蘋果)； mother ( ) while(.) p(S空）； 放桔子； v(S桔子)； son ( ) while(.) p(S桔子）； 吃桔子； v(S空)； daughter( ) while(.) p(S蘋果）； 吃蘋果； v(S空)； 8、理解臨界

12、資源的概念。各進(jìn)程采取互斥的方式，實(shí)現(xiàn)共享的資源稱作臨界資源（一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源）9、進(jìn)程調(diào)度方式，進(jìn)程調(diào)度算法，會(huì)計(jì)算周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間。（1）非搶占方式（處理機(jī)一旦分配，不允許其他進(jìn)程強(qiáng)占處理機(jī)）：優(yōu)點(diǎn)：實(shí)現(xiàn)簡單、系統(tǒng)開銷小缺點(diǎn)：難以滿足緊急任務(wù)（2）搶占方式：時(shí)間片、優(yōu)先權(quán)、短進(jìn)程優(yōu)先優(yōu)點(diǎn)：公平、能滿足實(shí)時(shí)任務(wù)缺點(diǎn)：系統(tǒng)開銷大1、先來先服務(wù)（FCFS）2、短進(jìn)程優(yōu)先（SPF）周轉(zhuǎn)時(shí)間=等待時(shí)間+運(yùn)行時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間÷運(yùn)行時(shí)間10、死鎖的概念，產(chǎn)生死鎖的原因、必要條件，解決死鎖問題的方法，銀行家算法。多個(gè)進(jìn)程因競爭資源而造成的一種僵局，若無外力

13、作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。產(chǎn)生死鎖的原因 ：(1)競爭資源 (2) 進(jìn)程推進(jìn)順序非法產(chǎn)生死鎖的必要條件：（1） 互斥條件：一個(gè)資源每次只能被一個(gè)進(jìn)程使用。（2） 請求與保持條件：一個(gè)進(jìn)程因請求資源而阻塞時(shí)，對已獲得的資源保持不放。（3） 不剝奪條件：進(jìn)程已獲得的資源，在末使用完之前，不能強(qiáng)行剝奪。（4） 循環(huán)等待條件：若干進(jìn)程之間形成一種頭尾相接的循環(huán)等待資源關(guān)系。解決死鎖問題的方法：(1) 預(yù)防死鎖（加限制條件，破壞產(chǎn)生死鎖的四個(gè)條件）(2) 避免死鎖（資源分配過程中防止進(jìn)入不安全狀態(tài)） (3) 檢測死鎖、解除死鎖銀行家算法步驟：P112（

14、一）檢查資源請求的合法性：當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：(1) 如果RequestijNeedi,j，便轉(zhuǎn)向步驟（二）；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。(2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟（三）；否則， 表示尚無足夠資源，Pi須等待。（二）資源試分配。系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改相關(guān)的數(shù)據(jù)結(jié)構(gòu)（三）安全性檢查。系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。第三章：存儲(chǔ)管理。1、地址重

15、定位（靜態(tài)重定位、動(dòng)態(tài)重定位）。靜態(tài)重定位：程序裝入時(shí)對目標(biāo)程序中的指令和數(shù)據(jù)地址的修改過程動(dòng)態(tài)重定位：程序裝入時(shí)不修改地址，地址轉(zhuǎn)換推遲到程序執(zhí)行時(shí)執(zhí)行2、單一連續(xù)分配、固定分區(qū)分配、可變分區(qū)分配（算法），重點(diǎn)在內(nèi)存的分配與回收。單一連續(xù)分配：僅用戶區(qū)和OS區(qū)固定分區(qū)式分配：內(nèi)存空間劃分為若干固定大小區(qū)域，每個(gè)分區(qū)中裝入一道作業(yè)首次適應(yīng)算法：要求空閑分區(qū)鏈以地址遞增的次序鏈接，在分配內(nèi)存時(shí)，從鏈?zhǔn)组_始順序查找，直到找到一個(gè)大小能滿足要求的空閑分區(qū)為止，然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分給請求者，余下的空閑分區(qū)仍停留在空閑鏈中。循環(huán)首次適應(yīng)算法：在分配內(nèi)存空間時(shí)，不再每次從表頭

16、（鏈?zhǔn)祝╅_始查找，而是從上次找到空閑區(qū)的下一個(gè)空閑開始查找，直到找到第一個(gè)能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑區(qū)分布得較均勻。最佳適應(yīng)算法：從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進(jìn)行排序，自表頭開始查找到第一個(gè)滿足要求的自由分區(qū)分配。3、分頁存儲(chǔ)管理、分段存儲(chǔ)管理，重點(diǎn)地址變換與內(nèi)存保護(hù)。分頁存儲(chǔ)管理§ 進(jìn)程的邏輯空間分成若干個(gè)大小相等的片，稱為頁面或頁。§ 內(nèi)存空間也分成與頁相同的若干個(gè)存儲(chǔ)塊，或稱為物理塊或

17、頁框。§ 分配：以塊為單位將進(jìn)程中的若干頁分別裝入到內(nèi)存中多個(gè)不相鄰接的塊中。分段存儲(chǔ)管理：§ 程序地址空間按其內(nèi)在邏輯關(guān)系劃分成若干個(gè)相對獨(dú)立的段，如主程序段、子程序段、數(shù)據(jù)段及堆棧段等。§ 每個(gè)段從0開始編址，采用一段連續(xù)的地址空間。§ 每段分配一個(gè)連續(xù)的分區(qū)，進(jìn)程中的各個(gè)段可以離散地分配到內(nèi)存中不同的分區(qū)中。例題：假定主存為64KB,分成16塊.某進(jìn)程有4頁:0.1.2.3 分別被分配到2,4,1,6塊(1)該進(jìn)程總長度為多少?(2)該進(jìn)程每一頁在內(nèi)存中的起始地址?(3)給出邏輯地址:0,100,1,50,2,0,3,10 (頁號(hào),頁內(nèi)地址)給出其

18、對應(yīng)的內(nèi)存地址.1）每塊的大小為64KB/16=4KB因?yàn)閴K的大小與頁的大小相等，所以每頁為4KB，因此作業(yè)的總長度4KB×4=16KB2）頁表為該作業(yè)各頁在內(nèi)存的起始地址為： 第0頁起始地址為：4K×2=8K第1頁起始地址為：4K×4=16K第2頁起始地址為：4K×1=4K第3頁起始地址為：4K×6=24K3）邏輯地址0，100的內(nèi)存地址為4K×2+100=8192+100=8292邏輯地址1，50的內(nèi)存地址為4K×4+50=16384+50=16434邏輯地址2，0的內(nèi)存地址為4K×1+0=4096邏輯地址3，

19、60的內(nèi)存地址為 4K×6+60=24K+60=246364、虛擬存儲(chǔ)管理，頁面置換算法。？存儲(chǔ)虛擬化，把不同的硬件抽象出來，以管理工具來實(shí)現(xiàn)統(tǒng)一的管理先進(jìn)先出FIFO：按順序依次置換最近最久未使用LRU：置換最久未被訪問的最佳置換OPT：置換以后永不使用的， 或許是在最長時(shí)間內(nèi)不再被訪問的頁面第四章：設(shè)備管理1、了解設(shè)備控制器的作用是CPU與I/O設(shè)備之間的接口，接收CPU指令控制I/O設(shè)備工作2、緩沖技術(shù)n 緩和CPU與I/O設(shè)備間速度不匹配的矛盾。n 減少對CPU的中斷頻率， 放寬對CPU中斷響應(yīng)時(shí)間的限制。n 提高CPU和I/O設(shè)備之間的并行性。1)單緩沖2)雙緩沖3)多緩沖

20、：4)緩沖池。3、/控制方式1、程序I/O利用I/O測試指令測試設(shè)備的閑忙。若設(shè)備不忙，則執(zhí)行輸入或輸出指令；若設(shè)備忙，則I/O測試指令不斷對該設(shè)備進(jìn)行測試，直到設(shè)備空閑為止。2、中斷驅(qū)動(dòng)每當(dāng)設(shè)備完成I/O操作，便以中斷請求方式通知CPU，然后進(jìn)行相應(yīng)處理。但由于CPU直接控制輸入輸出操作，每傳達(dá)一個(gè)單位信息，都要發(fā)生一次中斷，仍然消耗大量CPU時(shí)間。3、DMA數(shù)據(jù)傳輸單位是數(shù)據(jù)塊，傳送數(shù)據(jù)直接從設(shè)備到內(nèi)存，僅在傳送一個(gè)或多個(gè)數(shù)據(jù)塊開始和結(jié)束時(shí)才需cpu干預(yù)4、通道控制CPU向I/O通道發(fā)送一條I/O指令，以給出其所要執(zhí)行的通道程序的首址和要訪問的I/O設(shè)備，通道接到該指令后，通過執(zhí)行通道程序

21、便可完成CPU指定的I/O任務(wù)。n 通道指令：（1）操作碼（2）內(nèi)存地址（3）計(jì)數(shù)（4）通道程序結(jié)束位P。（5）記錄結(jié)束標(biāo)志R。第五章：文件管理、文件、文件系統(tǒng)概念，文件的操作文件是具有文件名的若干相關(guān)元素的集合文件管理系統(tǒng)是指文件和對文件進(jìn)行操作和管理的軟件集合文件的操作：(1)創(chuàng)建文件。 (2)刪除文件。 (3)讀文件。 (4)寫文件。 (5)設(shè)置文件的讀/寫位置。 (6)文件的打開與關(guān)閉（文件的打開，即在用戶和文件之間建立一個(gè)連接）(7)其它文件操作、文件目錄文件控制塊的有序集合。以文件形式保存在外存，稱為目錄文件。3、文件的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)邏輯結(jié)構(gòu)1、無結(jié)構(gòu)文件（流式文件):如大量的

22、源程序、可執(zhí)行文件、庫函數(shù)等2、有結(jié)構(gòu)文件（記錄式文件）：數(shù)據(jù)庫文件等。（1）順序文件n 串結(jié)構(gòu)：各記錄之間按存入時(shí)間的先后排列n 順序結(jié)構(gòu)：文件中的所有記錄按關(guān)鍵字(詞)排列。（2）索引文件（3）索引順序文件物理結(jié)構(gòu)：1、連續(xù)分配一個(gè)文件的信息存放在若干連續(xù)的物理塊中由一組相鄰的物理塊組成，是對記錄式文件取連續(xù)區(qū)分配而構(gòu)成的文件。連續(xù)分配的主要優(yōu)點(diǎn)如下：（1）順序訪問容易 （2）順序訪問速度快連續(xù)分配的主要缺點(diǎn)如下：（1）要求有連續(xù)的存儲(chǔ)空間 （2）必須事先知道文件的長度 2、鏈接分配一個(gè)文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個(gè)物理塊指向下一個(gè)物理塊優(yōu)點(diǎn)：提高了磁盤空間利用率 不存在外部碎片問題 有利于文件插入和刪除 有利于文件動(dòng)態(tài)擴(kuò)充缺點(diǎn)：存取速度慢，不適于隨機(jī)存取 可靠性問題，如指針出錯(cuò) 更多的尋道次數(shù)和尋道時(shí)間 鏈接指針占用一定的空間鏈接結(jié)構(gòu)