操作系統(tǒng)復習

操作系統(tǒng)的主要功能從資源管理觀點看，操作系統(tǒng)具有五大功能：處理機管理存儲器管理設備管理文件管理作業(yè)管理1.處理機管理主要任務：是對處理機的分配和運行實施有效管理。對處理機管理，可歸結為對進程的管理。進程管理的主要功能進程控制：當用戶作業(yè)要運行時，應為之建立一個或多個進程，并為它分配除處理機以外的所有資源，將它放入進程就緒隊列。當進程運行完成時，立即撤消該進程，以便及時釋放其所占有的資源。進程控制的基本功能就是創(chuàng)建和撤消進程以及控制進程的狀態(tài)轉換。進程同步：所謂進程同步是指系統(tǒng)對并發(fā)執(zhí)行的進程進行協(xié)調。最基本的進程同步方式是使諸進程以互斥方式訪問臨界資源。此外，對于彼此相互合作、去完成共同任務的諸進程，則應由系統(tǒng)對它們的運行速度加以協(xié)調。進程通信：對于相互合作的進程，在它們運行時，相互之間往往要交換一定的信息，這種進程間所進行的信息交換稱為進程通信。進程調度：當一個正在執(zhí)行的進程已經(jīng)完成，或因某事件而無法繼續(xù)執(zhí)行時，系統(tǒng)應進行進程調度，重新分配處理機。進程調度是指按一定算法，如最高優(yōu)先算法，從進程就緒隊列中選出一進程，把處理機分配給它，為該進程設置運行現(xiàn)場，并使之投入運行。2.存儲器管理存儲器管理的主要任務:為多道程序的并發(fā)運行提供良好環(huán)境；便于用戶使用存儲器；提高存儲器的利用率；為盡量多的用戶提供足夠大的存儲空間。存儲器管理的功能內存分配：多道程序能并發(fā)執(zhí)行的首要條件是，各道程序都有自己的內存空間，因此，為每道程序分配內存是存儲器管理的最基本功能。內存保護：為保證各道程序都能在自己的內存空間運行而互不干擾，要求每道程序在執(zhí)行時能隨時檢查對內存的所有訪問是否合法。必須防止因一道程序的錯誤而擾亂了其它程序，尤其應防止用戶程序侵犯操作系統(tǒng)的內存區(qū)。地址映射：在多道程序的系統(tǒng)中，操作系統(tǒng)必須提供把程序地址空間中的邏輯地址轉換為內存空間對應的物理地址的功能。地址映射功能可使用戶不必過問物理存儲空間的分配細節(jié)，從而為用戶編程提供了方便。內存擴充：由于物理內存的大小可能限制了大型作業(yè)或多個作業(yè)的并發(fā)執(zhí)行，為了滿足用戶的要求并改善系統(tǒng)性能，必須對內存加以擴充。但我們無須去真正地增加內存空間，而只須借助于虛擬存貯技術，便可獲得這樣地效果，使系統(tǒng)能運行內存要求量遠比物理內存大得多得作業(yè)，或讓更多得作業(yè)并發(fā)執(zhí)行。

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

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

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