【精選】操作系統(tǒng)復(fù)習(xí)文件

1、操作系統(tǒng)的主要功能從資源管理觀點(diǎn)看，操作系統(tǒng)具有五大功能：? 處理機(jī)管理? 存儲器管理? 設(shè)備管理? 文件管理? 作業(yè)管理1.處理機(jī)管理 主要任務(wù)：是對處理機(jī)的分配和運(yùn)行實(shí)施有效管理。對處理機(jī)管理，可歸結(jié)為對進(jìn) 程的管理。進(jìn)程管理的主要功能? 進(jìn)程控制：當(dāng)用戶作業(yè)要運(yùn)行時(shí)，應(yīng)為之建立一個(gè)或多個(gè)進(jìn)程，并為它分配除處理 機(jī)以外的所有資源， 將它放入進(jìn)程就緒隊(duì)列。 當(dāng)進(jìn)程運(yùn)行完成時(shí)， 立即撤消該進(jìn)程， 以便及時(shí)釋放其所占有的資源。進(jìn)程控制的基本功能就是創(chuàng)建和撤消進(jìn)程以及控制 進(jìn)程的狀態(tài)轉(zhuǎn)換。? 進(jìn)程同步：所謂進(jìn)程同步是指系統(tǒng)對并發(fā)執(zhí)行的進(jìn)程進(jìn)行協(xié)調(diào)。最基本的進(jìn)程同步 方式是使諸進(jìn)程以互斥方式訪問臨界

2、資源。? 此外，對于彼此相互合作、去完成共同任務(wù)的諸進(jìn)程，則應(yīng)由系統(tǒng)對它們的運(yùn)行速 度加以協(xié)調(diào)。? 進(jìn)程通信： 對于相互合作的進(jìn)程， 在它們運(yùn)行時(shí)， 相互之間往往要交換一定的信息， 這種進(jìn)程間所進(jìn)行的信息交換稱為進(jìn)程通信。? 進(jìn)程調(diào)度：當(dāng)一個(gè)正在執(zhí)行的進(jìn)程已經(jīng)完成，或因某事件而無法繼續(xù)執(zhí)行時(shí)，系統(tǒng) 應(yīng)進(jìn)行進(jìn)程調(diào)度，重新分配處理機(jī)。進(jìn)程調(diào)度是指按一定算法，如最高優(yōu)先算法， 從進(jìn)程就緒隊(duì)列中選出一進(jìn)程，把處理機(jī)分配給它，為該進(jìn)程設(shè)置運(yùn)行現(xiàn)場，并使 之投入運(yùn)行。2.存儲器管理 存儲器管理的主要任務(wù)? 為多道程序的并發(fā)運(yùn)行提供良好環(huán)境；? 便于用戶使用存儲器；? 提高存儲器的利用率；? 為盡量多的用戶

3、提供足夠大的存儲空間。存儲器管理的功能? 內(nèi)存分配：多道程序能并發(fā)執(zhí)行的首要條件是，各道程序都有自己的內(nèi)存空間，因 此，為每道程序分配內(nèi)存是存儲器管理的最基本功能。? 內(nèi)存保護(hù)：為保證各道程序都能在自己的內(nèi)存空間運(yùn)行而互不干擾，要求每道程序 在執(zhí)行時(shí)能隨時(shí)檢查對內(nèi)存的所有訪問是否合法。必須防止因一道程序的錯(cuò)誤而擾 亂了其它程序，尤其應(yīng)防止用戶程序侵犯操作系統(tǒng)的內(nèi)存區(qū)。? 地址映射：在多道程序的系統(tǒng)中，操作系統(tǒng)必須提供把程序地址空間中的邏輯地址 轉(zhuǎn)換為內(nèi)存空間對應(yīng)的物理地址的功能。地址映射功能可使用戶不必過問物理存儲 空間的分配細(xì)節(jié)，從而為用戶編程提供了方便。內(nèi)存擴(kuò)充：由于物理內(nèi)存的大小可能限制

4、了大型作業(yè)或多個(gè)作業(yè)的并發(fā)執(zhí)行，為了 滿足用戶的要求并改善系統(tǒng)性能，必須對內(nèi)存加以擴(kuò)充。但我們無須去真正地增加 內(nèi)存空間，而只須借助于虛擬存貯技術(shù)，便可獲得這樣地效果，使系統(tǒng)能運(yùn)行內(nèi)存 要求量遠(yuǎn)比物理內(nèi)存大得多得作業(yè)，或讓更多得作業(yè)并發(fā)執(zhí)行。3.設(shè)備管理1）設(shè)備管理的主要任務(wù):? 為用戶程序分配 I/O 設(shè)備；? 完成用戶程序請求的 I/O 操作；? 提高 CPU 和 I/O 設(shè)備的利用率；? 改善人機(jī)界面。2）設(shè)備管理程序應(yīng)具有的功能? 緩沖管理：幾乎所有的外圍設(shè)備于處理機(jī)交換信息時(shí)，都要利用緩沖來緩和CPU和I/O設(shè)備間速度不匹配的矛盾，和提高CPU與設(shè)備、設(shè)備與設(shè)備間操作的并行程度，以提

5、高CPU和I/O設(shè)備的利用率。? 設(shè)備分配：系統(tǒng)根據(jù)用戶所請求的設(shè)備類型和所采用的分配算法對設(shè)備進(jìn)行分配，并將未獲得所需設(shè)備的進(jìn)程放進(jìn)相應(yīng)設(shè)備的等待隊(duì)列。I/O 操作，并對由設(shè)備發(fā)來的中? 設(shè)備處理：啟動指定的 I/O 設(shè)備，完成用戶規(guī)定的斷請求進(jìn)行及時(shí)響應(yīng)，根據(jù)中斷類型進(jìn)行相應(yīng)的處理。? 虛擬設(shè)備功能：通常，把一次僅允許一個(gè)進(jìn)程使用的設(shè)備稱為獨(dú)占設(shè)備。系統(tǒng)可通 過某種技術(shù)使該設(shè)備成為能被多個(gè)用戶共享的設(shè)備，以提高設(shè)備利用率及加速程序 的執(zhí)行過程?？墒姑總€(gè)用戶都感覺到自己在獨(dú)占該設(shè)備。4.文件管理? 文件存儲空間的管理? 目錄管理? 文件讀、寫管理? 文件保護(hù)? 向用戶提供接口5.作業(yè)管理1）

6、作業(yè)管理的主要任務(wù):是根據(jù)系統(tǒng)條件和用戶需要，對作業(yè)的運(yùn)行進(jìn)行合理的組織、調(diào)度及相應(yīng)的控制。2）作業(yè)調(diào)度：作業(yè)調(diào)度是指根據(jù)系統(tǒng)的能力和當(dāng)前作業(yè)的運(yùn)行情況，按一定策略，從后備 作業(yè)隊(duì)列中選出一批作業(yè)，為它們分配所需的 I/O 設(shè)備和存儲空間，將它們調(diào)入內(nèi)存并為 之建立相應(yīng)的進(jìn)程，使之成為具有獲得處理機(jī)資格的侯選進(jìn)程。3）作業(yè)控制：作業(yè)控制是指作業(yè)從進(jìn)入系統(tǒng)開始，直到運(yùn)行完成的整個(gè)過程中，用戶可通 過某種形式向系統(tǒng)發(fā)出各種命令，以對自己的作業(yè)進(jìn)行控制和管理。進(jìn)程狀態(tài)轉(zhuǎn)換條件在進(jìn)程運(yùn)行過程中，由于自身進(jìn)展情況及外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一定 的條件相互轉(zhuǎn)換：? 就緒 -> 運(yùn)行?

7、運(yùn)行->調(diào)度程序選擇一個(gè)新的進(jìn)程運(yùn)行就緒運(yùn)行進(jìn)程用完了時(shí)間片精品? 運(yùn)行->? 等待->運(yùn)行進(jìn)程被中斷，因?yàn)橐桓邇?yōu)先級進(jìn)程處于就緒狀態(tài) 等待當(dāng)一進(jìn)程必須等待時(shí)? OS尚未完成服務(wù)? 對一資源的訪問尚不能進(jìn)行? 初始化 I/O 且必須等待結(jié)果? 等待某一進(jìn)程提供輸入 就緒當(dāng)所等待的事件發(fā)生時(shí)(IPC)其他狀態(tài)? 創(chuàng)建狀態(tài)? 終止?fàn)顟B(tài)? 掛起狀態(tài)調(diào)節(jié)負(fù)載，對換，父進(jìn)程，操作系統(tǒng)，終端用戶） 創(chuàng)建（新new狀態(tài)-OS已完成為創(chuàng)建一進(jìn)程所必要的工作? 已構(gòu)造了進(jìn)程標(biāo)識符? 已創(chuàng)建了管理進(jìn)程所需的表格但還沒有允許執(zhí)行該進(jìn)程? 因?yàn)橘Y源有限（ 尚未同意 ）終止（退出 exit） 狀態(tài) 中

8、止后進(jìn)程移入該狀態(tài)- 它不再有執(zhí)行資格- 表格和其它信息暫時(shí)由輔助程序保留? 例子: 為處理用戶帳單而累計(jì)資源使用情況的財(cái)務(wù)程序當(dāng)數(shù)據(jù)不再需要后，進(jìn)程 （和它的表格）被刪除五狀態(tài)進(jìn)程模型?阻塞-> 阻塞掛起- 當(dāng)所有進(jìn)程都阻塞，OS會安排空間讓一就緒進(jìn)程進(jìn)入內(nèi)存?阻塞掛起-> 就緒掛起- 當(dāng)?shù)却氖录l(fā)生時(shí)（狀態(tài)信息已在 OS中）?就緒掛起-> 就緒- 當(dāng)內(nèi)存中沒有就緒進(jìn)程時(shí)?就緒-> 就緒掛起（較少見）- 當(dāng)沒有被阻塞的進(jìn)程，而為了性能上的考慮，必須釋放一些內(nèi)存時(shí)七狀態(tài)進(jìn)程模型m 上(livatr>、uspvdSttq>cndk went(VcttrsXf

9、iockcd Swpviidd、 vth altBlocked i1 illHOUtbACllt Occurst*cnlExil )進(jìn)程控制塊（PCB? 系統(tǒng)為了管理進(jìn)程設(shè)置的一個(gè)專門的數(shù)據(jù)結(jié)構(gòu)，存放了用于描述該進(jìn)程情況和控制進(jìn)程運(yùn)行所需的全部信息。? 系統(tǒng)利用 PCB來控制和管理進(jìn)程，所以? 進(jìn)程與PCB是PCB是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志對應(yīng)的進(jìn)程控制塊的內(nèi)容? 進(jìn)程標(biāo)識符：標(biāo)識一個(gè)進(jìn)程的編號，也稱為進(jìn)程的內(nèi)部名;? 現(xiàn)性狀態(tài)：說明進(jìn)程的當(dāng)前狀態(tài);? 現(xiàn)場保留區(qū)：保存進(jìn)程由執(zhí)行狀態(tài)變?yōu)槠渌鼱顟B(tài)時(shí)的? 程序與數(shù)據(jù)地址：該進(jìn)程的程序和數(shù)據(jù)所在位置信息;? 互斥與同步機(jī)構(gòu)：實(shí)現(xiàn)進(jìn)程間互斥與同步時(shí)

10、所必須的機(jī)構(gòu);? 進(jìn)程通信機(jī)制：用于實(shí)現(xiàn)進(jìn)程間的通信所需的數(shù)據(jù)結(jié)構(gòu);? 優(yōu)先級：表示進(jìn)程使用CPU時(shí)優(yōu)先級別的一個(gè)整數(shù);? 資源清單：列出進(jìn)程擁有的資源的記錄;? 連接字：給出本進(jìn)程所在隊(duì)列中的下一個(gè)進(jìn)程的? 家族聯(lián)系：用于說明本進(jìn)程與其它家族成員間的關(guān)系。CPU現(xiàn)場信息;PCB首址;進(jìn)程映象 （ 進(jìn)程要素 ）? 用戶程序? 用戶數(shù)據(jù)? 棧- 用于過程調(diào)用和參數(shù)傳遞? 進(jìn)程控制塊 PCB 執(zhí)（ 行上下文 ）- 控制進(jìn)程所需的數(shù)據(jù)（進(jìn)程屬性），包括:? 進(jìn)程標(biāo)識符信息? 處理器狀態(tài)信息? 進(jìn)程控制信息進(jìn)程控制塊的組織方式 為了有效地對進(jìn)程控制塊進(jìn)行管理，應(yīng)該采用適當(dāng)?shù)姆绞桨阉鼈兘M織起來。目前常用

11、的組織方式有以下兩種： ? 按鏈接方式組織PCB 隊(duì)（ 列 ）不同狀態(tài)進(jìn)程分別組成隊(duì)列 運(yùn)行隊(duì)列、就緒隊(duì)列、等待隊(duì)列 ? 按索引方式組織PCB 表（ ）對具有相同狀態(tài)的進(jìn)程，分別設(shè)置各自的（其他方式：線性表或鏈表）PCB索引表，表明PCB在 PCB表中的地址為什么要線程的引入? 在操作系統(tǒng)中，進(jìn)程的引入提高了計(jì)算機(jī)資源的利用效率。但在進(jìn)一步提高進(jìn)程的 并發(fā)性時(shí)，人們發(fā)現(xiàn)進(jìn)程切換開銷占的比重越來越大，同時(shí)進(jìn)程間通信的效率也受 到限制? 線程的引入正是為了簡化進(jìn)程間的通信，以小的開銷來提高進(jìn)程內(nèi)的并發(fā)程度信號量的物理含義：精品信號量S> 0時(shí)S的數(shù)表示某可用源的數(shù)目執(zhí)行P操作意味著申請分配一

12、個(gè)單 位的蘇；當(dāng) SC 0時(shí)表示無資源可用，此時(shí)的對值示信號量 S的阻塞隊(duì)列中的進(jìn) 程數(shù)。執(zhí)t V操作意味著釋放一個(gè)位的源。S>0表示有S個(gè)源可用S=0 表示無資源 可用S<0PS |表示S等待列中的程個(gè)數(shù)P（S）: 表示申請一 個(gè)資源V（S） 表示釋放一個(gè)資源。信號量的初值應(yīng)該大于等于處理機(jī)度調(diào)的基本概念 在多道程環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目，致使它們爭用處理機(jī)。這就要求系統(tǒng)能 按某種算法，動態(tài)地把處理機(jī)分配給就隊(duì)緒列中的一個(gè)進(jìn)程，使之執(zhí)行。分配處理機(jī)的任 務(wù)是由進(jìn)程度調(diào)程序完成的。它是操作系統(tǒng)設(shè)計(jì)的中心問題之一。分時(shí)系統(tǒng)和實(shí)時(shí)統(tǒng)的系區(qū)別。各有什么特點(diǎn)？各自采用什么調(diào)度算法

13、？分時(shí)系 :統(tǒng)時(shí)間片轉(zhuǎn)輪度調(diào) 算法實(shí)時(shí)系:統(tǒng)在實(shí)中時(shí)系統(tǒng) , 硬實(shí)和務(wù)任時(shí)軟實(shí)時(shí)任務(wù)都聯(lián)系著一個(gè)截止時(shí)間 1）非搶占 式調(diào)度 算法:? 非搶占式輪轉(zhuǎn)調(diào)度算法搶占式優(yōu)先調(diào)度算法2）搶占式調(diào)度算法 :?基于時(shí)鐘中斷的占搶先優(yōu)度調(diào) 算法?立即搶占 先優(yōu)調(diào)權(quán)度算法。經(jīng)歷間時(shí)的CPU周轉(zhuǎn)時(shí) 間：作業(yè)從提交到完成（得到結(jié)果 ）所經(jīng)時(shí)的間歷。包括：在收容隊(duì)列 中等待， 上執(zhí)行，就緒隊(duì)列和阻塞隊(duì)列中等待，結(jié)果輸出等待響應(yīng)比 : （ 等待時(shí)間 +要求服務(wù)時(shí)間 ）/ 要求服務(wù)時(shí)間產(chǎn)生死鎖的原因1. 競爭系統(tǒng)資源2. 程進(jìn)的推進(jìn)順序不當(dāng)產(chǎn)生死的鎖必要條件? 互斥條件（資源獨(dú)占）?請求 和保持條件（部分分配，占有申請

14、 ） ? 不剝奪條 件（不可強(qiáng)占） ?路環(huán)等待條件。預(yù)防死鎖的方法破壞產(chǎn)生死鎖的四個(gè)必要條件之一1）源資一次性分配；（ 破壞請求和保持條件）2) 可剝奪資源；即當(dāng)某進(jìn)程新的資源未滿足時(shí)，釋放已占有的資源( 破壞不可剝奪條件 )3) 資源有序分配法；做法：系統(tǒng)給每類資源賦予一個(gè)編號，每一個(gè)進(jìn)程按編號遞增的順?biāo)梨i避免? 死鎖避免定義 : 在系統(tǒng)運(yùn)行過程中序請求資源，釋放則相反(破壞環(huán)路等待條件)，對進(jìn)程發(fā)出的每一個(gè)系統(tǒng)能夠滿足的資源申請 進(jìn)行動態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖， 則不予分配，否則予以分配。? 預(yù)防死鎖的幾種策略，會嚴(yán)重地?fù)p害了系統(tǒng)性能。因此要施加較弱

15、的限制，從而獲 得較滿意得系統(tǒng)性能來避免死鎖。? 由于在避免死鎖的策略中，允許進(jìn)程動態(tài)地申請資源。因而，系統(tǒng)在進(jìn)行資源分配 之前預(yù)先計(jì)算資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將 資源分配給進(jìn)程；否則，進(jìn)程等待。其中最具有代表性的避免死鎖算法是銀行家算 法。死鎖的解除1)2)重要的是以最小的代價(jià)恢復(fù)系統(tǒng)的運(yùn)行。方法如下： 重新啟動撤消進(jìn)程3)4)剝奪資源進(jìn)程回退虛擬存儲器的基本思想是： 程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi) 存，而把其它部分保存在磁盤上，并在需要時(shí)在內(nèi)存和磁盤之間動態(tài)交換. 虛擬存儲器支持多道程序設(shè)計(jì)技術(shù) 虛擬存儲器?

16、 具有請求調(diào)入功能和自換功能 , 能從邏輯上對內(nèi)存容量進(jìn)行擴(kuò)充的存儲器系統(tǒng)。虛 擬存儲器就是一個(gè)地址空間，且具有比實(shí)存大得多的容量。? 對用戶：指令地址部分所限定的比實(shí)存大得多的地址實(shí)間。? 對系統(tǒng)：借助于各種表格機(jī)構(gòu)，體現(xiàn)虛擬實(shí)間。虛擬存儲器的容量CPU的有效地址4GB。? 一個(gè)虛擬存儲器的最大容量是由計(jì)算機(jī)的地址結(jié)構(gòu)確定的。如：若 長度為32位，則程序可以尋址范圍是0(2八32)-1 ，即虛存容量為? 虛擬存儲器的容量與主存的實(shí)際大小沒有直接的關(guān)系，而是由主存與輔存的容量之 和所確定。頁面置換算法 當(dāng)要放一頁面到全滿的主存塊時(shí)，系統(tǒng)需淘汰一頁。用來選取淘汰哪一頁的規(guī)則，叫 置換算法。? 最

17、佳置換算法? 先先出置攥法? 最近最久未用置換算法? 近似的 LRU算法（NRU算法） 最佳置換算法其所;擇的被淘汰頁最佳置換算法是由Belady于1966年提出的一種理論上的算法。面，將是以后永不使用的，或是在最長未來）1時(shí)為不再被訪。采用最佳置換算法，通?？杀ＷC獲得最氐的缺頁。先先出（FIFO面置換法置時(shí)擇在內(nèi)存中留間頁淘汰之最近最久未使用（LRU置換法選撮后一次訪問時(shí)距離當(dāng)前長一并淘汰之。即淘汰沒有使用的時(shí)間?，F(xiàn)代價(jià)很高（間戳或硬件方法）LRU置算法的硬件支持1）寄存器程在內(nèi)存中各頁勺使用情況，須每個(gè)在內(nèi)存中的面配置一個(gè)移 位寄存器，可表示為R=Rn-lR-2R-3 ? R2RRK.R,

18、RiR：J.11111rJ010*_1C1110f3C0aP11）4C1Hr111II11c10111011c1c11齊 f00QL(11I 11*1f 11I! *012)棧改型Clock置算法由位 A和修改位 M可以合成下面四種類型的面:類 (A=0, M=0):類 (A=0, M=1) ：類 (A=1, M=0) ：類 (A=1, M=1):是最佳淘汰頁。并不是很好的淘汰頁。該頁有可能再被訪問。該頁可能再被訪問。表示該頁最近既未被訪問，又未被修改，表示該頁最近未被訪問，但已被修改，最近已被訪問， 但未被修改， 最近已被訪問且被修改，精品其執(zhí)行過程可分成以下三步： 從指針?biāo)甘镜漠?dāng)前位置開

19、始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁在第一次掃描期間不改變訪問位 則開始第二輪掃描，尋 在第二輪掃描期間，(1)面， 將所遇到的第一個(gè)頁面作為所選中的淘汰頁。(2) 如果第一步失敗，即查找一周后未遇到第一類頁面，找A=0且M=1的第二類頁面，將所遇到的第一個(gè)這類頁面作為淘汰頁。將所有掃描過的頁面的訪問位都置0。(3) 如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。 然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁。A。其它置換算法1. 最少使用 (LFU： Least Frequently Used) 置換算法2.

20、頁面緩沖算法 (PBA： Page Buffering Algorithm)與設(shè)備無關(guān)性(設(shè)備獨(dú)立性)? 用戶在編制程序時(shí)，使用邏輯設(shè)備名，由系統(tǒng)實(shí)現(xiàn)從邏輯設(shè)備到物理設(shè)備的轉(zhuǎn)換? 用戶能獨(dú)立于具體物理設(shè)備而方便的使用設(shè)備? 用戶申請使用設(shè)備時(shí)，只需要指定設(shè)備類型，而無須指定具體物理設(shè)備，系統(tǒng)根據(jù) 當(dāng)前的請求，及設(shè)備分配的情況，在相同類別設(shè)備中，選擇一個(gè)空閑設(shè)備，并將其 分配給一個(gè)申請進(jìn)程引入緩沖技術(shù)1. 緩和CPU與I/O設(shè)備間速度不匹配的矛盾.2. 減少對CPU的中斷頻率，放寬對CPU中斷響應(yīng)時(shí)間的限制3. 提高CPU和I/O設(shè)備之間并行性 .磁盤查找算法1. (First-Come, First Served)2. 最短尋道時(shí)間優(yōu)先SSTF(Shortest Seek Time First)3. 掃描(SCAN)法優(yōu)先考慮磁頭當(dāng)前的移動方向 臂的移動方向4. 循環(huán)掃描(CSCA算法磁頭單向移動 , 當(dāng)磁頭到最外的磁首并訪問後5. N-SteP-SCA和 FSCAN調(diào)