操作系統復習指導操作系統基本概念操作系統是控制和管理計算機系統的硬件和軟件資源，合理地組織計算機工作流程及方便用戶使用的程序和數據的集合。操作系統的功能和主要特征主要功能:處理機管理存儲管理設備管理文件管理用戶接口主要特征并發性共享性虛擬性不確定性（隨機性）單用戶操作系統批處理操作系統分時操作系統實時操作系統網絡操作系統分布式操作系統多處理操作系統操作系統的分類五大類型(批處理、實時、分時、網絡、分布)用戶與操作系統的接口用戶與操作系統的三級接口作業（命令）控制級接口程序級接口圖形級接口四個概念:系統態、用戶態、特權指令、訪管制令作業的概念、組成以及作業控制塊的內容作業：由不同的順序相連的作業步組成。作業步：在一個作業的處理過程中，計算機所做的相對獨立的工作。作業流：一次有一批作業進入系統，并在操作系統控制下，一個接一個地順序進行處理。作業的類別批處理作業交互式作業(終端作業)作業由程序、數據和作業說明書三部分組成。系統調用的實現過程實際上系統調用語句本身是硬件提供的（機器指令），但其所調用的功能是操作系統提供的。每種機器的機器指令集中都有一條系統調用指令。陷入指令系統子程序sub0A0sub1A1subnAnsubiAi......陷入處理機構1)保護處理機現場2)取系統調用功能號并尋找子程序入口3)恢復處理機現場并返回入口地址表A0A2Ai......An....系統調用....用戶程序作業調度作業調度性能衡量指標(1)作業平均周轉時間T(Ti為每個作業的周轉時間；tc作業完成時刻；ts作業進入系統時刻)(2)平均帶權周轉時間W（Ti為每個作業的周轉時間；tr為作業實際運行時間）高響應比優先（HRF:HighestResponseRatioNext）：響應比最高的作業優先啟動。響應比=周轉時間/估計運行時間

=（等待時間+估計運行時間）/估計運行時間

=1+等待時間/估計運行時間高優先級優先（HPF：HighestPriorityFirst）：由用戶指定作業優先級，優先級高的作業啟動。假設在單道批處理環境下有四個作業，已知它們進入系統的時間、估計運行時間，應用先來先服務、最短作業優先和最高響應比優先作業調度算法，分別計算出作業的平均周轉時間和帶權的平均周轉時間。最短作業優先算法結果最高響應比優先算法結果順序程序特征：程序執行的順序性程序執行的封閉性程序執行結果的確定性（可再現性）

多道程序設計的特征并發性獨立性動態隨機性相互制約性進程定義：Process

進程是一個具有一定獨立功能的程序在一個數據集合上的一次動態執行過程，是系統進行資源分配和調度的獨立單位進程進程的組成要素：用戶程序用戶數據進程控制塊PCB進程的特征動態性獨立性并發性、異步性

結構化進程與程序的區別進程是動態的，程序是靜態的;進程是暫時的，程序的永久的;進程與程序的組成不同;進程可以創建其它進程，而程序不能；進程與程序的對應關系：通過多次執行，一個程序可對應多個進程；通過調用關系，一個進程可包括多個程序。進程狀態轉換圖

中斷、內核、原語基本概念中級調度新建態掛起就緒態掛起等待態高級調度低級調度運行態就緒態等待態終止態處理機調度的層次

引進進程調度的時機當一個進程運行完畢，或由于某種錯誤而終止運行當一個進程在運行中處于阻塞狀態（等待I/O）當有一個優先級更高的進程就緒（可搶占式）例如：新創建一個進程，一個等待進程變成就緒在進程通信中，執行中的進程執行了某種原語操作（P操作，阻塞原語，喚醒原語）分時系統中時間片到線程的特點：是進程的一個實體，可作為系統獨立調度和分派的基本單位。不擁有系統資源（只擁有從屬進程的全部資源，資源是分配給進程）一個進程中的多個線程可并發執行。（進程可創建線程執行同一程序的不同部分）線程（Thread）定義：是進程的一個實體，是CPU調度的基本單位。線程自己基本上不擁有系統資源，只留有幾個寄存器，但它可以與同屬同一個進程的其他線程共享進程所擁有的全部資源。進程互斥：指在多道程序環境下，每次只允許一個進程對臨界資源進行訪問。進程同步：指多個相關進程在執行次序上的協調。臨界資源:一次僅供一個進程使用的資源。在進程中涉及到臨界資源的程序段叫臨界區。多個進程的臨界區稱為相關臨界區。進程互斥與同步機制V(S)：①S∶=S+1;②若S>0，則調用V(S)的進程繼續運行；③若S≤0，從等待信號量S的阻塞隊列中喚醒頭一個進程，然后調用V(S)的進程繼續運行。V操作的原語V(sem)semsem+1sem≤0?喚醒等待隊列中的一個進程繼續自己的程序執行NY利用P.V操作實現進程的同步與互斥司機與售票員問題生產者與消費者問題管程：把分散的各同類臨界區集中起來。并為每個可共享資源設立一個專門的機構來統一管理各進程對該資源的訪問。消息緩沖通訊技術的基本思想是：根據“生產者-消費者”原理，利用內存中公用消息緩沖區實現進程的信息交換。死鎖概念：如果在一個進程集合中的每個進程都在等待只能由該集合中的其他一個進程才能引發的事件，則稱這一組進程或系統此時發生了死鎖。四個必要條件：互斥控制（資源獨占）非剝奪控制（不可剝奪）逐次請求（部分分配，占有申請）環路條件（循環等待）原因： 系統資源不足； 進程推進順序不合適；對死鎖的采取的對策

(1)鴕鳥策略。(2)預防策略。(3)避免策略。(4)檢測和解除。預防死鎖破壞死鎖四個必要條件中的一個或多個，來防止死鎖。解決方法：靜態資源分配

資源有序分配法

系統中對進程發出的每一個系統能夠滿足的資源申請進行動態檢查，并根據檢查結果決定是否分配資源；如果分配后系統可能發生死鎖，則不予分配，否則予以分配。避免死鎖最具有代表性算法：銀行家算法。

例如，設系統中有10臺磁帶機，由三個進程A、B、C共享。假定A、B、C已分別占用了2臺、3臺、3臺，它們的最大需求量分別為4臺、6臺、8臺。（假定只有當滿足了最大需求量后才能釋放所占用的全部資源。）單項資源的銀行家算法進程名已分配數尚需申請數最大需求數剩余資源ABC2332354682Availabler1r2r3230maxr1r2r3P1753P2322P3902P4222P5433allocationr1r2r3P1010P2302P3302P4211P5002needr1r2r3P1743P2020P3600P4011P5431P2:532P4:743P1:753P3:1055P5:1057P2P4P1P3P5多項資源的銀行家算法地址變換(地址再定位,地址映射)直接指定方式:程序員在編序時或編譯程序對源程序進行編譯時，所用的是實際存儲地址。名空間——程序邏輯空間——邏輯地址（相對地址，虛地址）存儲空間——物理地址（絕對地址，實地址）邏輯地址（相對地址，虛地址）：用戶的程序經過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式。物理地址（絕對地址，實地址）：內存中存儲單元的地址。物理地址可直接尋址。地址映射：將用戶程序中的邏輯地址轉換為運行時由機器直接尋址的物理地址。分區存儲管理原理：把內存分為一些大小相等或不等的分區，每個應用進程占用一個或幾個分區。每個進程占據一個分區。特點：適用于多道程序系統和分時系統支持多個程序并發執行難以進行內存分區的共享問題：可能存在內碎片和外碎片。內碎片：占用分區之內未被利用的空間外碎片：占用分區之間難以利用的空閑分區。固定分區

預先把可分配的主存儲器空間分割成若干個連續區域，稱為一個分區。每個分區的大小可以相同也可以不同，但分區大小固定不變，每個分區裝一個且只能裝一個作業。相關技術：覆蓋交換可變分區按空閑塊鏈接方式不同，有四種分配算法：首次適應法下次適應法（循環首次適應法）最佳適應法最壞適應法可再定位式分區和多重分區概念和原理分頁存儲管理頁：把用戶程序按邏輯頁劃分成大小相等的部分。用戶程序分頁的劃分是由系統自動完成的，對用戶是透明的。一頁的大小為2的整數次冪。內存塊：按頁的大小劃分為大小相等的區域，稱為內存塊（又叫物理頁面，頁框）。內存分配：以頁為單位進行分配，并按作業的頁數多少來分配。邏輯上相鄰的頁，物理上不一定相鄰，通過頁表把作業的各個頁面與內存塊對應起來。頁面變換表列出了作業的邏輯地址與主存中的物理地址間的對應關系。頁面大小:頁面的大小應適中，且頁面大小應是2的冪一個頁表中包含若干個表目，自然序號對應于用戶程序中的頁號，塊號是該頁對應的物理塊號。頁面變換表的每一個表目除了包含指向頁框的指針外，還包括一個存取控制字段。請求式分頁存儲管理

與純分頁存儲管理不同，請求式分頁管理系統在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據進程運行的需要，動態裝入其它頁面；當內存空間已滿，而又需要裝入新的頁面時，則根據某種算法淘汰某個頁面，以便裝入新的頁面。缺頁中斷當要訪問的頁面不在內存時，便產生一缺頁中斷，請求OS將所缺的頁面調入內存。頁面置換算法先進先出置換算法最近最久未用置換算法(LRU)近似的LRU算法（NRU算法）先進先出(FIFO)頁面置換算法基本思想：置換時首先淘汰在內存中駐留時間最長的頁面，即最早進入主存的頁面。時刻123456789101112P432143543215M4+3+42+3④1+2③4+1②3+4①5+3453453④2+5③1+25125F+++++++++FIFOM=3缺頁中斷次數：F=9缺頁率：f=9/12=75%最近最久未用(LRU)置換算法

基本思想：當需要置換一頁時，選擇在最近一段時間最久未用的頁予以淘汰。時刻123456789101112P432143543215M4+3+42+3④1+2③4+1②3+4①5+3445334⑤2+3④1+2③5+12F++++++++++LRUM=3缺頁中斷次數：F=10缺頁率：f=10/12=83%分段存儲管理原理：按程序自身的邏輯關系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段也從0開始編址，段內地址是連續的。內存劃分內存空間被動態的劃分為若干個長度不相同的區域，稱為物理段，每個物理段由起始地址和長度確定。內存分配以段為單位分配內存，每一個段在內存中占據連續空間（內存隨機分割，需要多少分配多少），但各段之間可以不連續存放。段表

記錄了段號，段的首（地）址和長度之間的關系。每一個程序設置一個段表，放在內存，屬于進程的現場信息。分頁與分段的主要區別段是信息的邏輯單位，它是根據用戶的需要劃分的，因此段對用戶是可見的；頁是信息的物理單位，是為了管理主存的方便而劃分的，對用戶是透明的。頁的大小固定不變，由系統決定。段的大小是不固定的，它由其完成的功能決定。段式向用戶提供的是二維地址空間，頁式向用戶提供的是一維地址空間，其頁號和頁內偏移是機器硬件的功能。由于段是信息的邏輯單位，因此便于存貯保護和信息的共享，頁的保護和共享受到限制。

段頁式存儲管理

段頁式管理吸收了分段的地址空間按邏輯意義分段的優點和分頁在存儲空間管理上的優點，不把段看成一個單一的連續整體來實現，而是將每個段分成若干頁面來管理。進程的邏輯地址由三個部分組成：即段號s，頁號p，和頁內相對地址w。段號段內地址頁號頁內地址段表長度段表控制寄存器段號頁表長度(頁數)內外標志頁表始址0L111L202L313段表…內存起始地址頁號內外頁面01121119215。。。第0段頁表頁號內外頁面012010216。。。

第2段頁表56…12…1920…段頁式地址映像段表長度指某個作業進程所含段的數量；頁表長度指一個段所占用的頁的數量。設備管理設備的分類:按照功能、數據組織、資源分配和數據傳輸速率設備的獨立性設備的統一性設備控制器的組成程序直接控制方式。(2)程序中斷I/O方式。(3)DMA方式。(4)通道方式。I/O控制方式DMA方式下的數據傳輸

通道分類:字節多路通道選擇通道數組多路通道

通道通道工作原理：CPU、通道I／O軟件的層次中斷處理程序設備驅動程序與設備無關的I/O軟件用戶層的輸入/輸出軟件設備管理中的四種控制塊

表目1┇表目i┇設備類型設備標識獲得設備的進程DCT指針

系統設備表STD控制器標識控制忙/閑標記CHCT指針控制器等待隊列首控制器等待隊列尾┇COCT

通道標識通道忙/閑標記通道等待隊列首通道等待隊列尾┇CHCT

設備類型設備標識設備忙/閑標記COCT指針設備等待隊列首設備等待隊列尾驅動程序地址DCT

I/O系統的設備分配按如下步驟實施設備分配：分配設備。(2)分配控制器。(3)分配通道。I/O控制中斷