第4章資源管理技術所謂操作系統就是能有效地管理計算機系統中的各種軟、硬件資源，合理地組織計算機的工作流程，為用戶創造良好工作環境的系統軟件。4.1操作系統的概念一、操作系統的功能與任務

OS是最基本的、核心的系統軟件，是加在系統硬件上的第一層軟件，是硬件的首次擴充。其作用有如下幾個方面：（1）管理系統資源（2）為用戶提供資源共享的條件和環境，并對資源的使用進行合理調度（3）提供輸入輸出的方便環境，提供良好的用戶界面（4）規定用戶的接口，進行各種錯誤處理操作系統的五大功能

操作系統功能：文件管理進程管理存儲器管理作業管理設備管理二、OS的發展過程1、第一階段（手工操作階段）輸入紙帶（卡片）、電傳打字機輸出結果、在控制臺上用搬鍵輸入命令等；沒有OS，只能用機器指令控制、操作計算機；用戶獨占整個系統資源，利用率低；CPU等待人工操作；用戶既是操作員又是程序員；既用戶必須是計算機專家；主要用于科學計算。面臨的問題：人機矛盾日益突出、系統資源利用率低。2、第二階段（成批處理系統）

為解決人機矛盾，提高資源利用率，人們很自然想到：讓計算機保持不間斷工作、減少人工干預程度。于是產生了把“零散的單一程序處理”變為“集中的成批程序處理”的處理方式。“批處理”操作系統由此而產生；被稱為“第1代操作系統”。面臨的問題：

高速CPU和低速I/O的矛盾加劇。由于計算機技術的發展，CPU處理速度提高很快，但I/O的速度卻很慢，系統整體效率沒有得到應有的提高。3、第3階段（執行程序系統和多道的引入)

為解決高速CPU和低速I/O不匹配的矛盾，在硬、軟件資源方面做了巨大的改進，由此誕生了許多新技術：

高質量、高效率的高級語言編譯器：

FORTRAN、COBOL、PASCAL等；分時系統將CPU劃分為很小的時間片，采用循環輪作方式處理多道程序；CPU和I/O的并行處理技術；包括：通道技術、緩沖技術、多道處理技術、中斷技術等。

由此產生了第三代操作系統。系統特點：多道處理一個CPU同時處理多個程序；同時將多個程序裝入內存、并同時運行的機制；大大提高了CPU的利用率；通道技術將I/O處理從CPU的控制下獨立出來的一套處理機制，也稱為“I/O處理機”；CPU不再直接控制I/O設備，而是通過通道去控制，從而實現了CPU和I/O設備之間的并行工作，緩解了CPU和I/O速度不匹配的矛盾；中斷技術在程序運行中，出現了某種緊急事件，必須暫時中止現行程序，轉去處理此事件，然后再恢復中斷程序的運行技術。操作特點：操作更加簡單；例如，MS-DOS、UNIX、WINDOWS；功能更加強大；五大功能由此實現；應用程序豐富多彩；計算機應用已廣泛涉及到各行各業、各個領域。面臨的問題：CPU利用率低的矛盾更加激化。現有處理技術和手段已不適應應用的實時處理需求。三、操作系統的分類（訪問方式）

1、多道批處理操作系統(BatchProcessing)2、分時操作系統(TimeSharing)3、實時系統(RealTime)4、通用操作系統5、多窗口系統批處理操作系統：解決：用戶操作速度太慢與計算機處理速度極快之間的矛盾，提高了計算機系統的吞吐量，提高了系統資源的利用率。特點：不需人工干預，進行批量處理。批處理系統又分為單道批處理系統和多道批處理系統。

缺點：處理過程中，用戶不能干預。分時系統：分時系統是多道程序的變種，每個用戶都通過一個聯機終端使用計算機系統。

分時系統與批處理系統的區別：在批處理系統中，一個作業可以長時間地占用CPU直至該作業執行完成；而在分時系統中，一個作業只能在屬于它的那個時間片內使用CPU，時間一到，系統將剝奪作業的CPU使用權，把CPU分配給其他的作業使用。特點：同時性、獨立性、及時性、交互性必須考慮：系統的響應時間。系統核心：時間片輪流調度技術。影響系統響應時間的因素：用戶數目，時間片的長短以及作業調度所必須的系統開銷等。例：有人說：“分時系統中分時時間片的長短問題無所謂，并不影響終端用戶得到的及時響應。”結論：分時時間片的長短問題是一個重要問題，它將直接影響用戶得到的及時響應。”實時系統：（特殊的分時系統）分類：實時過程系統、實時信息處理系統。

特點：對時間有嚴格的限制，要求計算機能對外部隨機事件做出及時響應，并處理。

采用：時間片分時技術。

特點：及時性、同時性、獨立性、交互性。

實時系統與分時系統的區別：實時系統專用性很強，交互能力較差，用戶數量有限；分時系統通用性很強，交互能力很強，允許用戶運行或修改應用程序。

最大區別：系統的響應時間。分時系統的響應時間可以長一點，以用戶可以忍受的范圍為限，一般2--3秒；實時系統的響應時間短得多，一般毫秒級，甚至微秒級。通用操作系統：

兼有批處理、分時處理和實時處理三者或其中的兩者的功能。5。多窗口操作系統集成開發環境信息共享界面友好4.2多道程序設計程序單道程序、多道程序、順序程序、并發程序順序程序與并發程序的特征進程進程的特征、性質、狀態及轉換、線程1、程序的有關概念程序（Program）

是為解決某個問題用計算機語言或命令設計、編寫的一系列指令的有序集合。程序的順序執行

一個程序通常分為若干個具有一定獨立性的程序段，這些程序段是按邏輯步驟編排的，只有當當前程序段執行完成后，才將控制權轉交到下一個程序段并執行下一個程序段。程序順序執行舉例一設有一個程序有三個程序段，分別執行

I（輸入）、C（計算）和P（輸出）操作。執行順序為：

ICP

只有‘輸入’了數據，才能‘計算’這些數據，也只有‘計算’產生了結果，才能‘輸出’它們。這些邏輯關系（順序）是不能隨意改變的。

結果

數據

程序順序執行舉例二

假設有n個作業，每個作業都由三個程序段：輸入段Ii、計算段Ci、輸出段Pi。在早期單道程序系統中，作業執行流為：作業1I1C1P1

作業2I2C2P2

作業nInCn

Pn作業執行順序單道程序處理及特性一次只處理一個程序。該程序獨享系統資源。單個程序的特性：

1、順序性操作按程序規定的順序執行。2、封閉性程序在執行過程中獨享系統資源，不受外界因素的干擾和影響。3、可再現性只要初始條件相同，無論以何種方式、速度、重復執行多少次，結果是相同的。多道程序處理及特性同時將多個程序裝入內存，并同時處理它們，整個系統資源為多個程序共享。由于多道程序具有并發的特點，在任一時刻，系統內部（內存）同時運行著多個程序；受系統資源的制約，每個程序處理過程的行為是不確定的（系統內部狀態因此而不同）。例如，第Ii個程序的Ci

這次是在時刻Ti開始的，那么，下一次運行同樣的程序組時，第Ii個程序的Ci

就不一定是在Ti時刻開始。

程序并發執行舉例設有三個程序，它們的執行步驟和順序相同，都是Ii（輸入）、Ci（計算）、Pi（輸出）。當第1個程序的輸入操作I1執行完、執行C1時，輸入機空閑，這時候可以執行第2個程序的輸入操作I2；在時間上，操作C1和I2時重疊的。當C1執行完、執行P1時，處理機空閑，若這時I2已完成，就可以執行C2，與此同時，輸入機又空閑，可以執行第3個程序的I3。這樣一來，在時間上，P1、C2和I3是重疊操作的。

程序并發執行舉例示意圖程序1：I1C1P1程序2：I2C2P2程序3：I3C3P3

從示意圖中可以看出，C1和I2、P1、C2和I3、P2和C3在時間上都是重疊操作的。Tt1t3t2單道和多道程序處理的區別在單道程序處理環境下，各邏輯步驟之間的關系是確定的、不受外界影響而改變的。在多道程序處理環境下，并發處理機制中必然存在著直接或間接的相互依賴和相互制約的關系，從而使被處理的多道程序失去了程序固有的特性：封閉性、可再現性。

程序與計算結果不再一一對應程序在順序執行時，程序與“計算”間有著一一對應的關系。在并發執行時，一個共享程序可為多個用戶作業調度，而使程序處于多個執行中，從而形成了多個“計算”。因此，程序和計算間一一對應的關系不復存在。2、進程及有關概念進程（Process）就是程序的一次執行過程，是系統進行資源分配和調度的一個獨立單位。“進程”這個概念是1966年美國麻省理工學院的J.H.Sallexer提出的。進程管理也被稱為處理機管理。處理機是計算機系統中的重要資源，所以它管理的好壞在很大程度上直接影響系統的效率。處理機管理又分兩個部分：作業管理和進程管理。進程管理是由程序管理進化而來，是和程序管理密不可分的。進程的概念

由于并發活動的復雜性，不同學者研究和討論的側重點不同，對進程的定義也不盡相同。幾種不同的定義為：

進程是可以和別的計算并發執行的計算；進程是程序的一次執行，亦即進程是在給定內存區域中的一組指令序列的執行過程；所謂進程，就是一個程序在給定活動空間和初始環境下，在一個處理機上的執行過程；進程是程序在一個數據集合上運行的過程，是系統資源分配和調度的一個獨立單位。進程的特征進程具有兩個重要特征：（1）動態性：表現在它由“創建”而產生，由“調度”而執行，因得不到資源而“暫停”執行，最后由“撤消”而消亡。進程有自己的生命周期。（2）并發性：在系統中可以同時存在幾個進程。在單CPU系統中，任何時刻只有一個進程占用CPU，其它進程處于等待狀態。進程有著走走停停的活動規律。引入進程的目的是為了程序的并發執行，以提高資源的利用率。進程的性質1）動態性描述程序在執行過程中的全部活動；2）并發性

OS同時接受和處理多個進程；3）異步性不同進程在邏輯上相互獨立，有各的運行“軌跡”；4）制約性由于計算機資源是有限的，不同進程共享CPU和I/O通道及設備，因此相互制約。

進程的狀態進程在其存在的過程中，它們的狀態是不斷發生變化的。一般來說，進程有三種基本狀態：就緒狀態、運行狀態、等待狀態。就緒狀態

已經獲得投入運行所必需的一切資源，一旦分配到CPU，就可以立即執行。這是一種邏輯上可運行狀態。運行狀態進程獲得了CPU及其它一切所需資源，正在CPU上運行著。等待狀態

由于資源得不到滿足，進程運行受阻，處于暫停狀態，等待資源分配后，再投入運行。進程狀態轉換示意圖

運行狀態等待狀態

就緒狀態

進程調度

等待資源時間用完獲得資源

進程調度程序

來自作業調度

交作業管理進程在整個生存周期中，由進程調動程序控制，在這三種狀態之間進行轉換。四、死鎖

１、什么是死鎖現象：每個進程所要求的資源都已被另一個進程占用，出現沒有一個進程能繼續運行，這種情況稱“死鎖”。２、死鎖產生的原因

（Ａ）資源不能共享（資源獨占性）。（Ｂ）資源的不可剝奪性。（C）資源采用動態分配原則：允許一個進程不釋放已占有的資源，就又去申請別的資源。（D）允許進程間非法交叉推進順序的存在：導致循環等待資源，無法前進。

3、死鎖產生必須同時具有的四個必要條件：

（Ａ）資源獨占性。（Ｂ）資源的不可剝奪性。（C）資源采用動態的部分分配原則（Ｄ）出現相關進程由于資源分配不當而出現循環等待。４、解決死鎖的辦法

（Ａ）死鎖的預防破壞產生死鎖的4個必要條件中的任何一個。·關于資源獨占性：采用假脫機技術可以使非共享設備變為共享設備。·破壞“資源的不可剝奪性”（申請不到資源時，釋放原先已占有的，進入等待，以后再一起申請）。·破壞對資源采用動態的部分分配原則（每個進程必須提出它所需要的全部資源，只有完全滿足時，才能啟動）。·破壞循環等待。

（B）死鎖的避免躲避死鎖的發生。

（C）死鎖的檢測與恢復允許死鎖產生，當死鎖發生時能檢測出來，并且有能力處理，進行恢復。采用虛擬技術，使非共享設備變成共享設備，以避免死鎖用戶1用戶2用戶3??????輸出輸出輸出打印打印機主機三、進程通信

1、同步與互斥的概念

臨界資源：一次僅允許一個進程使用的資源。如打印機、讀卡機、緩沖區、變量等。臨界區：進程中使用臨界資源的那段程序。各進程之間存在著相互制約、相互依賴的關系，例1：進程同步的例子電子郵件信箱發送進程A接收進程B當信箱滿時，發送進程只有等待接收進程取走信件，當信箱空時，接收進程必須等待發送進程發送信件。12n……四、多道程序的組織處理機調度分為作業調度和進程調度，前者是宏調度、后者是微調度，二者的調度算法類似。常用的作業調度算法：1、先來先服務2、短作業優先3、最高響應比優先：

響應比=等待時間+實際運行時間)/實際運行時間4、基于優先級的調度算法5、均衡調度算法4.3存儲空間的組織一、內存儲器的管理技術存儲器是計算機系統的重要資源之一。因為任何程序和數據以及各種控制用的數據結構都必須占用一定的存儲空間，因此，存儲管理直接影響系統的性能。存儲器由內存和外存組成。內存由順序編址的塊組成，每塊包含相應的物理單元。邏輯(相對)地址與物理(絕對)地址邏輯地址（logicaladdress、relativeaddress）程序中按邏輯順序編排的代碼及數據的地址稱為邏輯地址。物理地址（physicaladdress、absoluteaddress）程序中按代碼及數據在內存中實際存儲位置的地址成為物理地址。重定位（relocation）將邏輯地址轉化為物理地址的過程稱為重定位。一般由操作系統的鏈接過程完成。分為靜態和動態兩種。靜態鏈接是在鏈接裝入時一次集中完成，動態是在指令執行中先訪問內存后再重定位，一般由硬件完成地址轉換。重定位原理圖見圖4-1。存儲管理的功能（1）地址變換：相對地址到絕對地址（2）內存分配：（3）存儲共享與保護（4）存儲器的擴充1、界地址存儲管理又稱分區分配存儲管理

分為固定分區分配和可變式動態分區分配固定分區分配固定分區分配（fixed-sizepartition）是在處理作業前，內存事先劃分為若干個大小不等或相等的區域，一旦劃分好則固定不變，每個作業占一個分區，作業是連續存放的。分區的劃分可以由操作系統或系統管理員決定。系統對內存的管理和控制通過數據結構—分區說明表進行，分區說明表說明各分區號、分區大小、起始地址和是否是空閑區（分區狀態）。內存的分配釋放、存儲保護以及地址變換都通過分區說明表進行。分區說明表的結構如圖4-2分區說明表分區號大小始址狀態19KB20KB已分配225KB29KB可用340KB54KB可用4162KB94KB可用固定分區方法的優缺點固定分配的優點是分配回收方便，適用于用戶不多的小型系統；缺點是內存使用不充分，每一分區剩余部分無法利用。可變式動態分區分配

動態分區的原理動態分區法在作業執行前并不建立分區，而是在處理作業的過程中按需要建立分區，而且其大小可隨作業或進程對內存的要求而改變。這就改變了固定分區中小作業占據大分區的浪費現象，從而提高了系統的利用率。動態分區的數據結構動態分區采用三張表對內存管理，分別為已分配區域說明表、未分配區域說明表（可用表）和資源請求表。動態分區的分配與回收

分配動態分區法在分配前，除操作系統本身占用外，只有一個空白區。分配時，按一定的算法從空白表區中找，看是否有滿足作業的可用分區，如果空白區存在則分配，分配后修改兩張表的內容，如果找不到滿足要求的空閑區則系統報錯。首次適應法（first-fit）要求把內存中的可用分區單獨組成可用分區表或可用分區自由鏈，按起始地址遞增的次序排列。查找的方法是每次按遞增的次序向后找，一旦找到大于或等于所要求內存長度的分區，則結束查找，從找到的分區中劃分所要求的內存長度分配給用戶，把剩余的部分進行合并（如果有相鄰的空白區存在的話），并修改可用區中的相應表項。循環適應法（circulation-fit）系統記住上一次分配區地址，每重新分配一次時，都在當前之后尋找，其目的是回收空白區。即內存所有的線性空間可能輪流使用到。分配的時間會快一些，“碎片”也可能會小一些。最佳適應法（best-fit）最佳適應法要求按空白區的大小，從小到大次序組成空白區表或自由鏈。尋找的方法是找到第一個滿足要求的空白區時停止查找，如果該空白區大于請求表中的請求長度，則將剩余空白區留在可用表中（如果相鄰有空白區，則與之合并），然后修改相關表的表項。最壞適應法（worset-fit）最壞適應法要求按空白區大小,從大到小遞減順序組成空白區可用表或自由鏈.尋找的方法是當用戶作業或進程申請一個空白區時,選擇能滿足要求的最大空白區分配，先檢查空白區可用表或自由鏈的第一個空閑區的大小是否大于或等于所要求的內存長度，若滿足，則分配相應的存儲空間給用戶，然后修改和調整空閑區可用表或自由鏈，否則分配失敗。2、頁式存儲管理

實現原理：(1)劃分實頁:將物理內存劃分成位置固定、大小相同的“塊”（實頁面）。(2)劃分虛頁:將用戶邏輯地址空間也分成同樣大小的頁面，成為虛擬空間的虛頁面(3)建立頁表:建立頁表，每個作業一張，按虛頁號進行登記(4)地址變換:將虛頁面的邏輯地址轉化為實頁面的物理地址，在程序執行時改變為物理地址，屬于作業的動態重定位，一般由地址轉換機構（硬件）完成2、頁式存儲管理

頁表的設計：(1)存儲分塊表

:整個系統一張，記錄整個內存的使用情況。主要有位示圖和空白塊鏈兩種方法。(2)作業表

:整個系統一張，每個作業占一個表項(3)頁表

:每個作業一張，其表項包括頁號（虛頁）、頁面號（實頁）中斷位、改變位、淘汰位等2、頁式存儲管理

請求淘汰換頁算法：(1)先進先出算法

:先進入內存的頁面先淘汰。實現是在頁表中登記進入的次序，并將各個已分配的頁面按分配時間順序連接起來，組成FIFO隊列。(2)循環檢測法

:讓循環多的頁面留駐內存，計算機采用記錄頁面住留內存期間對該頁的訪問時間，t為該頁上一次訪問時間，T為該頁第二次訪問時間，選用相對時間（t-T）最大的淘汰。優點是適合循環多的大程序；缺點是系統開銷大2、頁式存儲管理

請求淘汰換頁算法：(3)最近最少使用頁面先淘汰

:選擇離當時時間最近的一段時間內最久沒有使用過的頁面先