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

1、南理工紫金學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)2班操作系統(tǒng)復(fù)習(xí)資料（lm）操作系統(tǒng)復(fù)習(xí)第一章考點(diǎn)：操作系統(tǒng)的定義，基本特性以及主要功能（選擇、填空）1. 定義：操作系統(tǒng)是一組控制和管理計(jì)算機(jī)硬件和軟件資源、合理地對各類作業(yè)進(jìn)行調(diào)度、以及方便用戶使用的程序集合。2. 基本特性：并發(fā)性（最重要特征）、共享性、虛擬性、異步性所謂共享是指系統(tǒng)中的資源可供內(nèi)存中多個并發(fā)執(zhí)行的進(jìn)程(線程)共同使用。資源屬性的不同，對資源共享的方式也不同。實(shí)現(xiàn)資源共享的兩種方式：(1)互斥共享方式(2)同時訪問方式3. 主要功能：處理器管理、存儲器管理、設(shè)備管理、文件管理、用戶之間的接口第二章考點(diǎn)：進(jìn)程、程序、線程的概念（簡答）；PCB結(jié)

2、構(gòu)、進(jìn)程狀態(tài)（三種基本狀態(tài)）；進(jìn)程同步和互斥的含義（選擇，填空）；臨界資源、臨界區(qū)、以及同步機(jī)制原則；信號量P或V操作時的信號量值的變化；經(jīng)典進(jìn)程同步問題（綜合題）1. 進(jìn)程的定義：進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程(程序在并發(fā)環(huán)境中的執(zhí)行過程)，是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位。進(jìn)程的特征動態(tài)性 并發(fā)性 獨(dú)立性異步性 進(jìn)程結(jié)構(gòu) PCB進(jìn)程控制塊->動態(tài)特征的集中反映程序段->描述要完成的功能數(shù)據(jù)段->操作對象及工作區(qū)2. 程序的定義：是為實(shí)現(xiàn)特定目標(biāo)或解決特定問題而用計(jì)算機(jī)語言編寫的命令序列的集合。3. 線程的定義：它是一個基本的CPU執(zhí)行單元，也是程序執(zhí)行流的最小單元，由線程ID

3、、程序計(jì)數(shù)器、寄存器集合和堆棧組成。線程是進(jìn)程中的一個實(shí)體，一個進(jìn)程中包含多個線程，他們可以利用進(jìn)程所擁有的資源，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。4. PCB（進(jìn)程控制塊）結(jié)構(gòu)：為了描述和控制進(jìn)程的運(yùn)行，系統(tǒng)為每個進(jìn)程定義了一個數(shù)據(jù)結(jié)構(gòu)-進(jìn)程控制塊，它是進(jìn)程實(shí)體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。在進(jìn)程控制塊中，主要包含四方面信息：進(jìn)程標(biāo)識符、處理機(jī)狀態(tài)、進(jìn)程調(diào)度信息、進(jìn)程控制信息。5. 進(jìn)程三種基本狀態(tài)：就緒狀態(tài)、執(zhí)行狀態(tài)、阻塞狀態(tài)就緒->執(zhí)行 執(zhí)行->阻塞 阻塞->就緒 執(zhí)行->就緒6. 進(jìn)程的同步：進(jìn)程間共同完成一項(xiàng)任務(wù)時直接發(fā)生相互作用的關(guān)系。同步進(jìn)

4、程間具有合作關(guān)系；在執(zhí)行時間上必須按照一定的順序協(xié)調(diào)進(jìn)行；7. 進(jìn)程的互斥：并發(fā)執(zhí)行的多個進(jìn)程由于競爭同一資源而產(chǎn)生的相互排斥的關(guān)系。進(jìn)程間相互合作的關(guān)系是同步關(guān)系，而對資源爭用的關(guān)系是互斥關(guān)系。若干進(jìn)程使用同一臨界資源時必須互斥執(zhí)行。8. 臨界資源：一次僅允許一個進(jìn)程使用的共享資源如：打印機(jī)、磁帶機(jī)、表格9. 臨界區(qū)：在每個進(jìn)程中訪問臨界資源的那段程序;進(jìn)程必須互斥進(jìn)入臨界區(qū)；10. 同步機(jī)制原則:空閑讓進(jìn)、忙則等待、有限等待、讓權(quán)等待11. 信號量P操作（wait）、V操作（signal）時時的信號量值的變化：Wait操作：申請一個單位資源procedure wait(S) var S:s

5、emaphore;/*定義記錄型信號量*/ begin S.value:=S.value-1; /*如果資源不足則阻塞該進(jìn)程*/ if S.value<0 then block(S.L); endSignal操作：釋放一個單位資源procedure Signal(S) var S:semaphore;/*定義記錄型信號量*/ begin S.value:=S.value+1; /*如果阻塞隊(duì)列中有進(jìn)程，則喚醒該進(jìn)程*/ if S.value0 then wakeup(S.L); endS.value 0時，代表系統(tǒng)中可用資源的數(shù)目；S.value<0時, 絕對值表示已阻塞的進(jìn)程數(shù)量

6、（等待使用資源的進(jìn)程個數(shù)）；S.value的初始值為1時：只允許一個進(jìn)程訪問臨界資源，是互斥信號量；12. 經(jīng)典進(jìn)程同步問題前趨圖是一個有向無循環(huán)圖，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。利用p、v操作實(shí)現(xiàn)進(jìn)程同步（前驅(qū)圖）S1 a=x+y; s1->s2 S2 b=a+3;A=0(信號量)P1 p2S1; P(A);V(A); S2;第三章考點(diǎn)：作業(yè)經(jīng)歷的三級調(diào)度各種調(diào)度算法基本思想，計(jì)算周轉(zhuǎn)時間，平均周轉(zhuǎn)時間死鎖概念、產(chǎn)生原因以及死鎖的必要條件，死鎖的預(yù)防、避免處理方法（簡答，填空）銀行家算法（作業(yè)）1. 處理機(jī)調(diào)度的層次（三級調(diào)度）：高級調(diào)度（創(chuàng)建）、低級調(diào)度（找進(jìn)程執(zhí)行）、中級調(diào)度（激

7、活掛起）2. 短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法基本思想：從后備隊(duì)列中選擇一個或多個若干運(yùn)行時間最短的作業(yè)調(diào)入內(nèi)存運(yùn)行。3. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法基本思想：從后備隊(duì)列中選擇優(yōu)先級高的的作業(yè)調(diào)入內(nèi)存運(yùn)行。4.死鎖的概念：多個進(jìn)程在運(yùn)行過程中因競爭資源而造成的一種僵局。 各并發(fā)進(jìn)程彼此等待對方擁有的資源，且在得到對方資源前不釋放自己的資源。5. 死鎖產(chǎn)生原因：競爭資源。 資源（打印機(jī)、公用隊(duì)列）數(shù)目不能滿足進(jìn)程的需要； 進(jìn)程間推進(jìn)順序非法。進(jìn)程在運(yùn)行過程中，請求和釋放資源的順序不當(dāng)，也同樣會導(dǎo)致進(jìn)程死鎖。競爭資源引起死鎖：可剝奪和非可剝奪性資源 競爭非可剝奪性資源 競爭臨時性資源6. 產(chǎn)生死鎖的必要條件：

8、(1) 互斥條件 (2) 請求和保持條件 (3) 不剝奪條件 (4) 環(huán)路等待條件 7.處理死鎖的基本方法(1) 預(yù)防死鎖。-摒棄“請求和保護(hù)”條件互斥條件（ 錯 ）請求和保持條件（ 對 ）不剝奪條件（ 對 ）環(huán)路等待條件（ 對 ）預(yù)防死鎖的方法 1.摒棄“請求和保持”條件 解決方案（and型信號量）AND型信號量基本思想：將進(jìn)程在整個運(yùn)行中需要的所有資源，一次性全部分配給進(jìn)程，待進(jìn)程使用完后一起釋放。 2.摒棄“不剝奪”條件 解決方案（強(qiáng)制回收） 3.摒棄“環(huán)路等待”條件 解決方案（資源按序分配策略）(2) 避免死鎖。-銀行家算法 (3) 檢測死鎖。 (4) 解除死鎖。-剝奪資源死鎖的解除常

9、采用的兩種方法：剝奪資源（基本方法）撤銷進(jìn)程系統(tǒng)不發(fā)生死鎖，滿足不等式：n(k-1)+1m（n是進(jìn)程個數(shù)，k是進(jìn)程所需最大資源數(shù)，m是系統(tǒng)提供資源數(shù)）8.銀行家算法(1)可利用資源向量Available；(2) 最大需求矩陣Max；(3) 分配矩陣Allocation；(4) 需求矩陣Need；Needi,j=Maxi,j-Allocationi,j 設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requestij=K，表示進(jìn)程Pi需要K個Rj類型的資源。Pi發(fā)出資源請求后，按下述步驟進(jìn)行檢查： (1)如果RequestijNeedi,j，轉(zhuǎn)向步驟2；否則認(rèn)為出錯，因?yàn)樗枰馁Y源數(shù)已超過它所

10、宣布的最大值。 (2)如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。 (3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej:=Availablej-Requestij Allocationi,j:=Allocationi,j+Requestij; Needi,j:=Needi,j-Requestij; (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才將資源分配給進(jìn)程Pi；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。 安全性算法 (1) 設(shè)置兩個向量：

11、工作向量Work:系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work:=Available; Finish:系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時先做Finishi:=false; 當(dāng)有足夠資源分配給進(jìn)程時，再令Finishi:=true。 (2) 從進(jìn)程集合中找到滿足下述條件的進(jìn)程： Finishi=false; Needi,jWorkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。(3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成， 并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj:=Worki+Allocationi,j; Fi

12、nishi:=true; go to step 2; (4) 如果所有進(jìn)程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 對待死鎖，一般應(yīng)考慮死鎖的預(yù)防、避免、檢測和解除。典型的銀行家算法屬于避免死鎖，摒棄“請求和保護(hù)”條件屬于預(yù)防死鎖，而剝奪資源是解除死鎖的基本方法。第四章考點(diǎn)：動態(tài)分區(qū)分配思想、算法、回收基本分頁系統(tǒng)的地址轉(zhuǎn)換過程基本分段系統(tǒng)的地址轉(zhuǎn)換過程段頁式存儲管理系統(tǒng)的原理虛擬存儲的概念頁面置換算法的原理（OPT、FIFO、LRU）1. 動態(tài)分區(qū)分配思想：當(dāng)有進(jìn)程需分配，以進(jìn)程為單位在內(nèi)存中找到相等大小的空間進(jìn)行切割。2. 動態(tài)分區(qū)分配算法：首

13、次適應(yīng)算法FF（每次從頭開始）循環(huán)首次適應(yīng)算法（找到下次的位置）最佳適應(yīng)算法（容量以從小到大順序）最壞適應(yīng)算法（容量以從大到小順序）快速適應(yīng)算法（分類搜索）3. 回收內(nèi)存情況1：與插入點(diǎn)的前一個空閑區(qū)F1相鄰接情況2：與插入點(diǎn)的后一個空閑區(qū)F1相鄰接情況3：同時與插入點(diǎn)的前、后兩個空閑區(qū)相鄰接情況4：既不與F1鄰接，又不與F2鄰接4. 基本分頁系統(tǒng)的地址轉(zhuǎn)換過程分頁地址中的地址結(jié)構(gòu)如下：31 12 11 0頁號P位移量W位移量W又稱頁內(nèi)地址：每頁大?。?12=4KB地址空間中最多有：220=1M頁邏輯地址A 頁面大小L 頁號P 頁內(nèi)地址d5. 基本分段系統(tǒng)的地址轉(zhuǎn)換過程31 16 15 0段號

14、段內(nèi)地址允許一個作業(yè)最多有64K個段每個段的最大長度為64KB邏輯地址A 頁面大小L 頁號P 頁內(nèi)地址d6. 段頁式存儲管理系統(tǒng)的原理分段和分頁原理結(jié)合；先將用戶進(jìn)程分成若干個段；再把每個段分成若干個頁，并為每個段賦予一個段名；段號(S)段內(nèi)頁號(P)頁內(nèi)地址(W)作業(yè)地址空間和地址結(jié)構(gòu)三次訪問內(nèi)存第一次訪問段表，從中取得頁表起始地址；第二次訪問頁表，從中取出該頁所在的物理塊號，并將該塊號與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次真正訪問數(shù)據(jù)或指令；7. 虛擬存儲的概念（局部性原理）虛擬存儲器，是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。虛擬存儲器的實(shí)現(xiàn)方

15、法 建立在離散分配的存儲管理方式基礎(chǔ)上分頁請求系統(tǒng)請求分段系統(tǒng)8.頁面置換算法的原理（OPT、FIFO、LRU）最佳置換算法（OPT）->離得最遠(yuǎn)淘汰最佳置換算法選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面；先進(jìn)先出(FIFO)頁面置換算法->最先進(jìn)內(nèi)存的淘汰淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。最近最久未使用(LRU)置換算法 ->左邊最遠(yuǎn)淘汰由于無法預(yù)測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的我將來”的近似，選擇最近最久未使用的頁面予以淘汰；第五章考點(diǎn)：I/O控制方式緩沖管理種類Spoolin

16、g技術(shù)磁盤調(diào)度算法（FCFS、SSTF、SCAN、CSCAN）1.I/O控制方式程序I/O方式CPU要不斷地測試I/O設(shè)備的狀態(tài)，因?yàn)樵贑PU中無中斷機(jī)構(gòu)，使I/O設(shè)備無法向CPU報(bào)告它已完成了一個字符的輸入操作。 中斷驅(qū)動I/O控制方式在I/O設(shè)備輸入每個數(shù)據(jù)的過程中，無須CPU干預(yù)，可使CPU與I/O設(shè)備并行工作。僅當(dāng)輸完一個數(shù)據(jù)時，才需CPU花費(fèi)極短的時間去做些中斷處理。使CPU和I/O設(shè)備都處于忙碌狀態(tài)，從而提高了整個系統(tǒng)的資源利用率及吞吐量。直接存儲器訪問（DMA） I/O控制方式數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)塊，即在CPU與I/O設(shè)備之間，每次傳送至少一個數(shù)據(jù)塊；數(shù)據(jù)傳送是從設(shè)備直接送入

17、內(nèi)存的，或者相反；僅在傳送一個或多個數(shù)據(jù)塊的開始和結(jié)束時，才需CPU干預(yù)，整塊數(shù)據(jù)的傳送是在控制器的控制下完成。I/O通道控制方式 I/O通道方式是DMA方式的發(fā)展，它可進(jìn)一步減少CPU的干預(yù)，即把對一個數(shù)據(jù)塊的讀(或?qū)?為單位的干預(yù)，減少為對一組數(shù)據(jù)塊的讀(或?qū)?及有關(guān)的控制和管理為單位的干預(yù)。 2.緩沖管理種類單緩沖用戶發(fā)出I/O請求；OS在主存中分配一緩沖區(qū)用于暫存用戶輸入的一行數(shù)據(jù)；輸入期間，用戶進(jìn)程被掛起以等待數(shù)據(jù)輸入完畢；輸出時，用戶進(jìn)程將一行數(shù)據(jù)輸入到緩沖區(qū)后，繼續(xù)執(zhí)行處理，當(dāng)戶用已有第二行數(shù)據(jù)輸出時，如果第一行數(shù)據(jù)尚未被提取完畢，則用戶進(jìn)程阻塞；雙緩沖也稱緩沖對換輸入時，將數(shù)據(jù)

18、送入第一緩沖區(qū)，裝滿后便轉(zhuǎn)向第二緩沖區(qū)。同時，從第一緩沖區(qū)中移出數(shù)據(jù)，并送入用戶進(jìn)程，接著由CPU對數(shù)據(jù)進(jìn)行計(jì)算；雙緩沖，系統(tǒng)處理一塊數(shù)據(jù)的時間可以粗略地認(rèn)為是Max(C，T)。如果C<T，可使塊設(shè)備連續(xù)輸入；如果C>T，則可使CPU不必等待設(shè)備輸入；循環(huán)緩沖多個緩沖區(qū)；多個指針；緩沖池于既可用于輸入又可用于輸出的公用緩沖池，其中至少應(yīng)含有以下三種類型的緩沖區(qū): 空(閑)緩沖區(qū)； 裝滿輸入數(shù)據(jù)的緩沖區(qū)； 裝滿輸出數(shù)據(jù)的緩沖區(qū)。3. Spooling技術(shù)是關(guān)于慢速字符設(shè)備如何與計(jì)算機(jī)主機(jī)交換信息的一種技術(shù)，通常稱為“假脫機(jī)技術(shù)”。 共享打印機(jī) 當(dāng)用戶進(jìn)程請求打印輸出時， SPOOLing系統(tǒng)同意為它打印輸出，但并不真正立即把打印機(jī)分配給該用戶進(jìn)程，而只為它做兩件事： 由輸出進(jìn)程在輸出井中為之申請一個空閑磁盤塊區(qū)， 并將要打印的數(shù)據(jù)送入其中； 輸出進(jìn)程再為用戶進(jìn)程申請一張空白的用戶請求打印表，并將用戶的打印要求填入其中， 再將該表掛到請求打印隊(duì)列上。 4.磁盤調(diào)度算法（FCFS、SSTF、SCAN、CSCAN）先來先服務(wù)（FCFS）算法