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

操作系統(tǒng)的主要功能從資源管理觀點(diǎn)看，操作系統(tǒng)具有五大功能：處理機(jī)管理存儲(chǔ)器管理設(shè)備管理文件管理作業(yè)管理1.處理機(jī)管理主要任務(wù)：是對(duì)處理機(jī)的分配和運(yùn)行實(shí)施有效管理。對(duì)處理機(jī)管理，可歸結(jié)為對(duì)進(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)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行協(xié)調(diào)。最基本的進(jìn)程同步方式是使諸進(jìn)程以互斥方式訪問(wèn)臨界資源。此外，對(duì)于彼此相互合作、去完成共同任務(wù)的諸進(jìn)程，則應(yīng)由系統(tǒng)對(duì)它們的運(yùn)行速度加以協(xié)調(diào)。進(jìn)程通信：對(duì)于相互合作的進(jìn)程，在它們運(yùn)行時(shí)，相互之間往往要交換一定的信息，這種進(jìn)程間所進(jìn)行的信息交換稱為進(jìn)程通信。進(jìn)程調(diào)度：當(dāng)一個(gè)正在執(zhí)行的進(jìn)程已經(jīng)完成，或因某事件而無(wú)法繼續(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)場(chǎng)，并使之投入運(yùn)行。2.存儲(chǔ)器管理存儲(chǔ)器管理的主要任務(wù):為多道程序的并發(fā)運(yùn)行提供良好環(huán)境；便于用戶使用存儲(chǔ)器；提高存儲(chǔ)器的利用率；為盡量多的用戶提供足夠大的存儲(chǔ)空間。存儲(chǔ)器管理的功能內(nèi)存分配：多道程序能并發(fā)執(zhí)行的首要條件是，各道程序都有自己的內(nèi)存空間，因此，為每道程序分配內(nèi)存是存儲(chǔ)器管理的最基本功能。內(nèi)存保護(hù)：為保證各道程序都能在自己的內(nèi)存空間運(yùn)行而互不干擾，要求每道程序在執(zhí)行時(shí)能隨時(shí)檢查對(duì)內(nèi)存的所有訪問(wèn)是否合法。必須防止因一道程序的錯(cuò)誤而擾亂了其它程序，尤其應(yīng)防止用戶程序侵犯操作系統(tǒng)的內(nèi)存區(qū)。地址映射：在多道程序的系統(tǒng)中，操作系統(tǒng)必須提供把程序地址空間中的邏輯地址轉(zhuǎn)換為內(nèi)存空間對(duì)應(yīng)的物理地址的功能。地址映射功能可使用戶不必過(guò)問(wèn)物理存儲(chǔ)空間的分配細(xì)節(jié)，從而為用戶編程提供了方便。內(nèi)存擴(kuò)充：由于物理內(nèi)存的大小可能限制了大型作業(yè)或多個(gè)作業(yè)的并發(fā)執(zhí)行，為了滿足用戶的要求并改善系統(tǒng)性能，必須對(duì)內(nèi)存加以擴(kuò)充。但我們無(wú)須去真正地增加內(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è)備；完成用戶程序請(qǐng)求的I/O操作；提高CPU和I/O設(shè)備的利用率；改善人機(jī)界面。2)設(shè)備管理程序應(yīng)具有的功能緩沖管理：幾乎所有的外圍設(shè)備于處理機(jī)交換信息時(shí)，都要利用緩沖來(lái)緩和CPU和I/O設(shè)備間速度不匹配的矛盾，和提高CPU與設(shè)備、設(shè)備與設(shè)備間操作的并行程度，以提高CPU和I/O設(shè)備的利用率。設(shè)備分配：系統(tǒng)根據(jù)用戶所請(qǐng)求的設(shè)備類型和所采用的分配算法對(duì)設(shè)備進(jìn)行分配，并將未獲得所需設(shè)備的進(jìn)程放進(jìn)相應(yīng)設(shè)備的等待隊(duì)列。設(shè)備處理：?jiǎn)?dòng)指定的I/O設(shè)備，完成用戶規(guī)定的I/O操作，并對(duì)由設(shè)備發(fā)來(lái)的中斷請(qǐng)求進(jìn)行及時(shí)響應(yīng)，根據(jù)中斷類型進(jìn)行相應(yīng)的處理。虛擬設(shè)備功能：通常，把一次僅允許一個(gè)進(jìn)程使用的設(shè)備稱為獨(dú)占設(shè)備。系統(tǒng)可通過(guò)某種技術(shù)使該設(shè)備成為能被多個(gè)用戶共享的設(shè)備，以提高設(shè)備利用率及加速程序的執(zhí)行過(guò)程?？墒姑總€(gè)用戶都感覺(jué)到自己在獨(dú)占該設(shè)備。4.文件管理文件存儲(chǔ)空間的管理目錄管理文件讀、寫管理文件保護(hù)向用戶提供接口5.作業(yè)管理1）作業(yè)管理的主要任務(wù):是根據(jù)系統(tǒng)條件和用戶需要，對(duì)作業(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è)備和存儲(chǔ)空間，將它們調(diào)入內(nèi)存并為之建立相應(yīng)的進(jìn)程，使之成為具有獲得處理機(jī)資格的侯選進(jìn)程。3）作業(yè)控制：作業(yè)控制是指作業(yè)從進(jìn)入系統(tǒng)開始，直到運(yùn)行完成的整個(gè)過(guò)程中，用戶可通過(guò)某種形式向系統(tǒng)發(fā)出各種命令，以對(duì)自己的作業(yè)進(jìn)行控制和管理。───────────────────────────────────────進(jìn)程狀態(tài)轉(zhuǎn)換條件在進(jìn)程運(yùn)行過(guò)程中，由于自身進(jìn)展情況及外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一定的條件相互轉(zhuǎn)換：就緒-->運(yùn)行系統(tǒng)為了管理進(jìn)程設(shè)置的一個(gè)專門的數(shù)據(jù)結(jié)構(gòu)，存放了用于描述該進(jìn)程情況和控制進(jìn)程運(yùn)行所需的全部信息。系統(tǒng)利用PCB來(lái)控制和管理進(jìn)程，所以PCB是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志進(jìn)程與PCB是一一對(duì)應(yīng)的進(jìn)程控制塊的內(nèi)容進(jìn)程標(biāo)識(shí)符：標(biāo)識(shí)一個(gè)進(jìn)程的編號(hào)，也稱為進(jìn)程的內(nèi)部名；現(xiàn)性狀態(tài)：說(shuō)明進(jìn)程的當(dāng)前狀態(tài)；現(xiàn)場(chǎng)保留區(qū)：保存進(jìn)程由執(zhí)行狀態(tài)變?yōu)槠渌鼱顟B(tài)時(shí)的CPU現(xiàn)場(chǎng)信息；程序與數(shù)據(jù)地址：該進(jìn)程的程序和數(shù)據(jù)所在位置信息；互斥與同步機(jī)構(gòu)：實(shí)現(xiàn)進(jìn)程間互斥與同步時(shí)所必須的機(jī)構(gòu)；進(jìn)程通信機(jī)制：用于實(shí)現(xiàn)進(jìn)程間的通信所需的數(shù)據(jù)結(jié)構(gòu)；優(yōu)先級(jí)：表示進(jìn)程使用CPU時(shí)優(yōu)先級(jí)別的一個(gè)整數(shù)；資源清單：列出進(jìn)程擁有的資源的記錄；連接字：給出本進(jìn)程所在隊(duì)列中的下一個(gè)進(jìn)程的PCB首址；家族聯(lián)系：用于說(shuō)明本進(jìn)程與其它家族成員間的關(guān)系。進(jìn)程映象(進(jìn)程要素)用戶程序用戶數(shù)據(jù)棧用于過(guò)程調(diào)用和參數(shù)傳遞進(jìn)程控制塊PCB(執(zhí)行上下文)控制進(jìn)程所需的數(shù)據(jù)(進(jìn)程屬性)，包括:進(jìn)程標(biāo)識(shí)符信息處理器狀態(tài)信息進(jìn)程控制信息進(jìn)程控制塊的組織方式為了有效地對(duì)進(jìn)程控制塊進(jìn)行管理，應(yīng)該采用適當(dāng)?shù)姆绞桨阉鼈兘M織起來(lái)。目前常用的組織方式有以下兩種：按鏈接方式組織PCB(隊(duì)列)不同狀態(tài)進(jìn)程分別組成隊(duì)列 運(yùn)行隊(duì)列、就緒隊(duì)列、等待隊(duì)列按索引方式組織PCB(表)對(duì)具有相同狀態(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)程切換開銷占的比重越來(lái)越大，同時(shí)進(jìn)程間通信的效率也受到限制線程的引入正是為了簡(jiǎn)化進(jìn)程間的通信，以小的開銷來(lái)提高進(jìn)程內(nèi)的并發(fā)程度信號(hào)量的物理含義：信號(hào)量S＞0時(shí)，S的數(shù)值表示某類可用資源的數(shù)目，執(zhí)行P操作意味著申請(qǐng)分配一個(gè)單位的資源；當(dāng)S≤0時(shí)，表示無(wú)資源可用，此時(shí)S的絕對(duì)值表示信號(hào)量S的阻塞隊(duì)列中的進(jìn)程數(shù)。執(zhí)行V操作意味著釋放一個(gè)單位的資源。S>0表示有S個(gè)資源可用S=0表示無(wú)資源可用S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)P(S):表示申請(qǐng)一個(gè)資源V(S)表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于0───────────────────────────────────────處理機(jī)調(diào)度的基本概念在多道程環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目，致使它們爭(zhēng)用處理機(jī)。這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行。分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)的區(qū)別。各有什么特點(diǎn)？各自采用什么調(diào)度算法？分時(shí)系統(tǒng):時(shí)間片輪轉(zhuǎn)調(diào)度算法實(shí)時(shí)系統(tǒng):在實(shí)時(shí)系統(tǒng)中,硬實(shí)時(shí)任務(wù)和軟實(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)先權(quán)調(diào)度算法。周轉(zhuǎn)時(shí)間：作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時(shí)間。包括：在收容隊(duì)列中等待，CPU上執(zhí)行，就緒隊(duì)列和阻塞隊(duì)列中等待，結(jié)果輸出等待響應(yīng)比:(等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間產(chǎn)生死鎖的原因1.競(jìng)爭(zhēng)系統(tǒng)資源2.進(jìn)程的推進(jìn)順序不當(dāng)產(chǎn)生死鎖的必要條件互斥條件（資源獨(dú)占）請(qǐng)求和保持條件（部分分配，占有申請(qǐng)）不剝奪條件（不可強(qiáng)占）環(huán)路等待條件。預(yù)防死鎖的方法破壞產(chǎn)生死鎖的四個(gè)必要條件之一1)資源一次性分配；(破壞請(qǐng)求和保持條件)2)可剝奪資源；即當(dāng)某進(jìn)程新的資源未滿足時(shí)，釋放已占有的資源(破壞不可剝奪條件)3)資源有序分配法；做法：系統(tǒng)給每類資源賦予一個(gè)編號(hào)，每一個(gè)進(jìn)程按編號(hào)遞增的順序請(qǐng)求資源，釋放則相反(破壞環(huán)路等待條件)

死鎖避免死鎖避免定義:在系統(tǒng)運(yùn)行過(guò)程中，對(duì)進(jìn)程發(fā)出的每一個(gè)系統(tǒng)能夠滿足的資源申請(qǐng)進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。預(yù)防死鎖的幾種策略，會(huì)嚴(yán)重地?fù)p害了系統(tǒng)性能。因此要施加較弱的限制，從而獲得較滿意得系統(tǒng)性能來(lái)避免死鎖。由于在避免死鎖的策略中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源。因而，系統(tǒng)在進(jìn)行資源分配之前預(yù)先計(jì)算資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，進(jìn)程等待。其中最具有代表性的避免死鎖算法是銀行家算法。死鎖的解除重要的是以最小的代價(jià)恢復(fù)系統(tǒng)的運(yùn)行。方法如下：1）重新啟動(dòng)2）撤消進(jìn)程3）剝奪資源4）進(jìn)程回退───────────────────────────────────────虛擬存儲(chǔ)器的基本思想是：程序、數(shù)據(jù)、堆棧的大小可以超過(guò)內(nèi)存的大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時(shí)在內(nèi)存和磁盤之間動(dòng)態(tài)交換.虛擬存儲(chǔ)器支持多道程序設(shè)計(jì)技術(shù)虛擬存儲(chǔ)器具有請(qǐng)求調(diào)入功能和自換功能,能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的存儲(chǔ)器系統(tǒng)。虛擬存儲(chǔ)器就是一個(gè)地址空間，且具有比實(shí)存大得多的容量。對(duì)用戶：指令地址部分所限定的比實(shí)存大得多的地址實(shí)間。對(duì)系統(tǒng)：借助于各種表格機(jī)構(gòu)，體現(xiàn)虛擬實(shí)間。虛擬存儲(chǔ)器的容量一個(gè)虛擬存儲(chǔ)器的最大容量是由計(jì)算機(jī)的地址結(jié)構(gòu)確定的。如：若CPU的有效地址長(zhǎng)度為32位，則程序可以尋址范圍是0～(2^32)-1，即虛存容量為4GB。虛擬存儲(chǔ)器的容量與主存的實(shí)際大小沒(méi)有直接的關(guān)系，而是由主存與輔存的容量之和所確定。頁(yè)面置換算法 當(dāng)要放一頁(yè)面到全滿的主存塊時(shí)，系統(tǒng)需淘汰一頁(yè)。用來(lái)選取淘汰哪一頁(yè)的規(guī)則，叫置換算法。最佳置換算法先進(jìn)先出置換算法最近最久未用置換算法近似的LRU算法（NRU算法）最佳置換算法 最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的，或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。先進(jìn)先出(FIFO)頁(yè)面置換算法 置換時(shí)選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)并淘汰之最近最久未使用(LRU)置換算法選擇最后一次訪問(wèn)時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)的一頁(yè)并淘汰之。即淘汰沒(méi)有使用的時(shí)間最長(zhǎng)的頁(yè)。實(shí)現(xiàn)代價(jià)很高（時(shí)間戳或硬件方法）LRU置換算法的硬件支持1)寄存器為了記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為:R=Rn-1Rn-2Rn-3…R2R1R02)棧改進(jìn)型Clock置換算法由訪問(wèn)位A和修改位M可以組合成下面四種類型的頁(yè)面：1類(A=0,M=0):表示該頁(yè)最近既未被訪問(wèn)，又未被修改，是最佳淘汰頁(yè)。2類(A=0,M=1)：表示該頁(yè)最近未被訪問(wèn)，但已被修改，并不是很好的淘汰頁(yè)。3類(A=1,M=0)：最近已被訪問(wèn)，但未被修改，該頁(yè)有可能再被訪問(wèn)。4類(A=1,M=1):最近已被訪問(wèn)且被修改，該頁(yè)可能再被訪問(wèn)。其執(zhí)行過(guò)程可分成以下三步：(1)從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁(yè)面，將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。在第一次掃描期間不改變?cè)L問(wèn)位A。(2)如果第一步失敗，即查找一周后未遇到第一類頁(yè)面，則開始第二輪掃描，尋找A=0且M=1的第二類頁(yè)面，將所遇到的第一個(gè)這類頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間，將所有掃描過(guò)的頁(yè)面的訪問(wèn)位都置0。(3)如果第二步也失敗，亦即未找到第二類頁(yè)面，則將指針?lè)祷氐介_始的位置，并將所有的訪問(wèn)位復(fù)0。然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁(yè)。其它置換算法最少使用(LFU：LeastFrequentlyUsed)置換算法 2.頁(yè)面緩沖算法(PBA：PageBufferingAlgorithm)───────────────────────────────────────與設(shè)備無(wú)關(guān)性（設(shè)備獨(dú)立性）用戶在編制程序時(shí)，使用邏輯設(shè)備名，由系統(tǒng)實(shí)現(xiàn)從邏輯設(shè)備到物理設(shè)備的轉(zhuǎn)換用戶能獨(dú)立于具體物理設(shè)備而方便的使用設(shè)備用戶申請(qǐng)使用設(shè)備時(shí)，只需要指定設(shè)備類型，而無(wú)須指定具體物理設(shè)備，系統(tǒng)根據(jù)當(dāng)前的請(qǐng)求，及設(shè)備分配的情況，在相同類別設(shè)備中，選擇一個(gè)空閑設(shè)備，并將其分配給一個(gè)申請(qǐng)進(jìn)程引入緩沖技術(shù)

1.緩和CPU與I/O設(shè)備間速度不匹配的矛盾.2.減少對(duì)CPU的中斷頻率,放寬對(duì)CPU中斷響應(yīng)時(shí)間的限制.3.提高CPU和I/O設(shè)備之間并行性.磁盤查找算法1.(First-Come,FirstServed)FCFS調(diào)度算法2.最短尋道時(shí)間優(yōu)先SSTF(ShortestSeekTimeFirst)3.掃描(SCAN)算法 優(yōu)先考慮磁頭當(dāng)前的移動(dòng)方向,在移動(dòng)方向上沒(méi)有更外的的磁道需要訪問(wèn)時(shí),才輚換磁臂的移動(dòng)方向4.循環(huán)掃描(CSCAN)算法 磁頭單向移動(dòng),當(dāng)磁頭到最外的磁首并訪問(wèn)後,磁頭立即返回到最里的欲訪問(wèn)的磁道.5.N-Step-SCAN和FSCAN調(diào)度算法 N步SCAN算法是將磁盤請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為N的子隊(duì)列,磁盤調(diào)度將按FCFS算法依次處理這些子隊(duì)列。而每處理一個(gè)隊(duì)列時(shí)又是按SCAN算法，對(duì)一