第 2 章操作系統

本章主要介紹操作系統的基本概念及其形成、發展歷史和主要類型，并指出操作系統的5 大管理功能。掌握操作系統原理的關鍵在于深入理解“一個觀點、兩條線索”。一個觀點是以資源管理的觀點來定義操作系統；兩條線索是指操作系統如何管理計算機各類資源和控制程序的執行。操作系統如何實現對這些資源的管理，其內涵、設計和實現是本章的主要內容

2.1 操作系統的類型與結構

計算機系統由硬件和軟件兩部分組成。操作系統是計算機系統中最基本的系統軟件，它既管理計算機系統的軟、硬件資源，又控制程序的執行。操作系統隨著計算機研究和應用的發展逐步形成并日趨成熟，它為用戶使用計算機提供了一個良好的環境，從而使用戶能充分利用計算機資源，提高系統的效率。操作系統的基本類型有：批處理操作系統、分時操作系統和實時操作系統。從資源管理的角度看，操作系統主要是對處理器、存儲器、文件、設備和作業進行管理。

2.1.1 操作系統的定義

操作系統（Operating System，OS）是計算機系統中的核心系統軟件，負責管理和控制計算機系統中的硬件和軟件資源，合理地組織計算機工作流程和有效地利用資源，在計算機與用戶之間起接口的作用。操作系統為用戶提供的接口表現形式一般為：命令、菜單、窗口之類的，而操作系統為應用程序提供的接口為 API。操作系統與硬件/軟件的關系如圖 2-1 所示。

2.1.2 操作系統分類

按照操作系統的功能劃分，操作系統的基本類型有批處理操作系統、分時操作系統、實時操作系統、網絡操作系統、分布式操作系統、嵌入式操作系統、微內核操作系統等。

2.2 操作系統基本原理

操作系統的主要功能是進行處理機與進程管理、存儲管理、設備管理、文件管理和作業管理的工作，本節討論操作系統是如何完成這些功能的。

2.2.1 進程管理

處理機是計算機系統的核心資源。操作系統的功能之一就是處理機管理。隨著計算機的迅速發展，處理機管理顯得更為重要，這主要由于計算機的速度越來越快，處理機的充分利用有利于系統效率的大大提高；處理機管理是整個操作系統的重心所在，其管理的好壞直接影響到整個系統的運行效率；而且操作系統中并發活動的管理和控制是在處理機管理下實現的，處理機管理集中了操作系統中最復雜的部分，它設計的好壞關系到整個系統的成敗。
進程是處理機管理中最基本的、最重要的概念。進程是系統并發執行的體現。由于在多道程序系統中，眾多的計算機用戶都以各種各樣的任務，隨時隨地爭奪使用處理機。為了動態地看待操作系統，則以進程作為獨立運行的基本單位，以進程作為分配資源的基本單位，從進程的角度來研究操作系統。因此，處理機管理也被稱為進程管理。處理機管理的功能就是組織和協調用戶對處理機的爭奪使用，把處理機分配給進程，對進程進行管理和控制，最大限度也發揮處理機的作用
1．進程的概念用靜態的觀點看，操作系統是一組程序和表格的集合。用動態的觀點看，操作系統是進程的動態和并發執行的。而進程的概念實際上是程序這一概念發展的產物。因此，可以從分析程序的基本特征入手，引出“進程”的概念。
順序程序是指程序中若干操作必須按照某種先后次序來執行，并且每次操作前和操作后的數據、狀態之間都有一定的關系。在早期的程序設計中，程序一般都是按順序執行的。在多道程序系統中，程序的運行環境發生了很大的變化。主要體現在：
（1）資源共享。為了提高資源的利用率，計算機系統中的資源不再由一道程序專用，而是由多道程序共同使用。
（2）程序的并發執行或并行執行。邏輯上講允許多道不同用戶的程序并行運行；允許一個用戶程序內部完成不同操作的程序段之間并行運行；允許操作系統內部不同的程序之間并行運行。物理上講：內存儲器中保存多個程序，I/O 設備被多個程序交替地共享使用；在多處理機系統的情形下，表現為多個程序在各自的處理機上運行，執行時間是重疊的。單處
理機系統時，程序的執行表現為多道程序交替地在處理機上相互空插運行。
實際上，在多道程序系統中，程序的并行執行和資源共享之間是相輔相成的。一方面，只有允許程序并行執行，才可能存在資源共享的問題；另一方面，只有有效地實現資源共享，才可能使得程序并行執行。這樣，可增強計算機系統的處理能力和提高機器的利用率。并發操作實際上是這樣的：大多數程序段只要求操作在時間上是有序的，也就是有些操作必須在其他操作之前，這是有序的，但其中有些操作卻可以同時進行。
2．進程的狀態轉換
由進程運行的間斷性，決定了進程至少具有以下三種狀態：
（1）就緒狀態。當進程已分配了除 CPU 以外的所有必要的資源后，只要能再獲得處理機，便能立即執行，把這時的進程狀態稱為就緒狀態。在一個系統中，可以有多個進程同時處于就緒狀態，通常把它們排成一個隊列，稱為就緒隊列。
（2）執行狀態指進程已獲得處理機，其程序正在執行。在單處理機系統中，只能有一個進程處于執行狀態。
（3）阻塞狀態指進程因發生某事件（如請求 I/O、申請緩沖空間等）而暫停執行時的狀態，亦即進程的執行受到阻塞，故稱這種暫停狀態為阻塞狀態，有時也稱為“等待”狀態，或“睡眠”狀態。通常將處于阻塞狀態的進程排成一個隊列，稱為阻塞隊列。進程的狀態隨著自身的推進和外界的變化而變化。例如，就緒狀態的進程被進程調度程序選中進入執行狀態；執行狀態的進程因等待某一事件的發生轉入等待狀態；等待狀態的進程所等待事件來到便進入就緒狀態。進程的狀態可以動態地相互轉換，但阻塞狀態的進程不能直接進入執行狀態，就緒狀態的進程不能直接進入阻塞狀態。在任何時刻，任何進程都處于且只能處于這其中一種狀態。進程狀態的變化情況如下：
（1）運行態→等待態：一個進程運行中啟動了外圍設備，它就變成等待外圍設備傳輸信息的狀態；進程在運行中申請資源（主存儲空間及外圍設備因得不到滿足）時，變成等待資源狀態，進程在運行中出現了故障（程序出錯或主存儲器讀寫錯誤等），變成等待干預狀態。
（2）等待態→就緒態：外圍設備工作結束后等待外圍設備傳輸信息的進程結束等待；等待的資源能得到滿足時（另一個進程歸還了資源），則等待資源者就結束等待；故障排隊后讓等待干預的進程結束等待，任何一個結束等待的進程必須先變成就緒狀態，待分配到處理器后才能運行。
（3）運行態→就緒態：進程用完了一個使用處理器的時間后強迫該進程暫時讓出處理器，當有更優先權的進程要運行時也迫使正在運行的進程讓出處理器。由于自身或外界原因成為等待狀態的進程讓出處理器時，它的狀態就變成就緒狀態。
（4）就緒態→運行態：等待分配處理器的進程，系統按一種選定的策略從處于就緒狀態的進程中選擇一個進程，讓它占用處理器，那個被選中的進程就變成了運行態。
圖 2-2 所示為進程的三種基本狀態及各狀態之間的轉換。

3．關于掛起狀態
在不少系統中，進程只有如圖 2-2 所示的三種狀態。但在另一些系統中，又增加了一些新狀態，其中最重要的是掛起狀態。引入掛起狀態的原因有：
（1）對換的需要。為了緩和內存緊張的情況，而將內存中處于阻塞狀態的進程換至外存上，使進程又處于一種有別于阻塞狀態的新狀態。因為即使該進程所期待的事件發生，該進程仍不具備執行條件而不能進入就緒隊列，稱這種狀態為掛起狀態。
（2）終端用戶的請求。當終端用戶在自己的程序運行期間，發現有可疑問題時，往往希望使自己的進程暫停下來。也就是說，使正在執行的進程暫停執行，若是就緒進程，則不接受調度以便研究其執行情況或對程序進行修改。把這種靜止狀態也稱為掛起狀態。
（3）父進程請求。父進程常希望掛起自己的子進程，以便考查和修改子進程，或者協調各子進程間的活動。
（4）負荷調節的需要。當實時系統中的工作負荷較重，有可能影響到對實時任務的控制時，可由系統把一些不重要的進程掛起，以保證系統正常運行。
（5）操作系統的需要。操作系統希望掛起某些進程，以便檢查運行中資源的使用情況及進行記賬。
綜上所述，不難了解掛起狀態具有以下三個屬性。
（1）被掛起的進程，原來可能處于就緒狀態，此時進程（被掛起）的狀態稱為掛起就緒；若被掛起的進程原來處于阻塞狀態，此時的狀態稱為掛起阻塞。不論哪種狀態，該進程都是不可能被調度而執行的。
（2）處于掛起阻塞狀態的進程，其阻塞條件與掛起條件無關；當進程所期待的事件出現后，進程雖不再被阻塞，但仍不能運行，這時，應將該進程從靜止阻塞狀態轉換為掛起就緒狀態。
（3）進程可以由其自身掛起，也可由用戶或操作系統等將之掛起。其目的都在于阻止進程繼續運行，被掛起的進程只能用顯式方式來激活，以便從掛起狀態中解脫出來。如圖 2-3 所示為具有掛起操作的進程狀態的演變情況。

4．進程互斥與同步進程互斥定義為：一組并發進程中一個或多個程序段，因共享某一共有資源而導致必須以一個不允許交叉執行的單位執行。也就是說互斥是要保證臨界資源在某一時刻只被一個進程訪問。
進程同步定義為：把異步環境下的一組并發進程因直接制約而互相發送消息而進行互相合作、互相等待，使得各進程按一定的速度執行的過程稱為進程同步。也就是說進程之間是異步執行的，同步即是使各進程按一定的制約順序和速度執行。
簡單一點來說，互斥是資源的競爭關系，而同步是進程間的協作關系。
系統中有些資源可以供多個進程同時使用，有些資源則一次僅允許一個進程使用，將一次僅允許一個進程使用的資源稱為臨界資源，很多物理設備如打印機、磁帶機等都屬于臨界資源，某些軟件的變量、數據、表格也不允許兩個進程同時使用，所以也是臨界資源。
進程在并發執行中可以共享系統中的資源。但是臨界資源的訪問則必須互斥進行，即各進程對臨界資源進行操作的那段程序的執行也必須是互斥的，只有這樣才能保證對臨界資源的互斥訪問。把一個進程訪問臨界資源的那段程序代碼稱為臨界區，有了臨界區的概念，進程間的互斥就可以描述為：禁止兩個或兩個以上的進程同時進入訪問同一臨界資源的臨界區。
為此，必須有專門的同步機構來協調它們，協調準則如下：
（1）空閑讓進。無進程處于臨界區時，若有進程要求進入臨界區則立即允許其進入；
（2）忙則等待。當已有進程進入其臨界區時，其他試圖進入各自臨界區的進程必須等待，以保證諸進程互斥地進入臨界區；
（3）有限等待。有若干進程要求進入臨界區時，應在有限時間內使一進程進入臨界區，即它們不應相互等待而誰也不進入臨界區；
（4）讓權等待。對于等待進入臨界區的進程必須釋放其占有的 CPU。信號量可以有效地實現進程的同步和互斥。在操作系統中，信號量是一個整數。當信號量大于等于 0 時，代表可供并發進程使用的資源實體數，當信號量小于零時則表示正在等待使用臨界區的進程數。建立一個信號量必須說明所建信號量代表的意義和設置初值，以及建立相應的數據結構，以便指向那些等待使用該臨界區的進程。
對信號量只能施加特殊的操作：P 操作和 V 操作。P 操作和 V 操作都是不可分割的原子操作，也稱為原語。因此，P 原語和 V 原語執行期間不允許中斷發生。 P（sem）操作的過程是將信號量 sem 值減 l，若 sem 的值成負數，則調用 P 操作的進程暫停執行，直到另一個進程對同一信號量做 V 操作。V（sem）操作的過程是將信號量sem 值加 1，若 sem 的值小于等于 0，從相應隊列（與 sem 有關的隊列）中選一個進程，喚醒它
一般 P 操作與 V 操作的定義如下所述。

 P 操作：P（sem）{ sem = sem - 1;if（sem < 0）進程進入等待狀態；else 繼續進行；} V 操作：V（sem）{ sem = sem + 1;if（sem ≤ 0）喚醒隊列中的一個等待進程；else 繼續進行；}

為了保護共享資源（如公共變量），使它們不被多個進程同時訪問，就要阻止這些進程同時執行訪問這些資源（臨界資源）的代碼段（臨界區）；進程互斥不允許兩個以上共享臨界資源的并發進程同時進入臨界區。利用 P、V 原語和信號量可以方便地解決并發進程對臨界區的進程互斥問題。
設信號量 mutex 是用于互斥的信號量，初值為 1，表示沒有并發進程使用該臨界區。于是各并發進程的臨界區可改寫成下列形式的代碼段：
P（mutex）；
臨界區
V（mutex）；
要用 P，V 操作實現進程同步，需要引進私用信號量。私用信號量只與制約進程和被制約進程有關，而不是與整組并發進程相關。與此相對，進程互斥使用的信號量為公用信號量。首先為各并發進程設置私用信號量，然后為私用信號量賦初值，最后利用 P，V 原語和私用信號量規定各進程的執行順序。
經典同步問題的例子是“生產者－消費者”問題。這要求存后再取，取后再存，即有兩個制約關系，為此，需要兩個信號量，表示緩沖區中的空單元數和非空單元數，記為 Bufempty 和 Buffull，它們的初值分別是 1 和 0，相應的程序段形式是：

 生產者loop生產一產品 next；P（Bufempty）；next 產品存緩沖區；V（Buffull）；endloop消費者loopP（Buffulll）；V（Bufempty）；從緩沖區中取產品；使用產品endloop

5．前趨圖
前趨圖是一個由結點和有向邊構成的有向無循環圖。該圖通常用于表現事務之間先后順序的制約關系。圖中的每個結點可以表示一個語句、一個程序段或是一個進程，結點間的有向邊表示兩個結點之間存在的前趨關系。
例：在計算機中，經常采用流水線方式執行指令，每一條指令都可以分解為取指、分析和執行三步。取指操作為 Ai，分析操作為 Bi 和執行操作為 Ci(i=1,2,3)。如圖 2-4 所示為三個任務各程序段并發執行的前驅圖。

圖中 A1 沒有前趨結點，稱為開始結點，它不受任何制約，可以直接執行；而 B1 與 A2 只能在 A1 執行完成之后才能開始，而 B2 必須在 B1 與 A2 完成之后才能開始；C3 沒有后繼結點，稱為終止結點。在前趨圖中，執行先后順序的制約關系可分為兩種：直接制約和間接制約。直接制約通常是指一個操作中，多個步驟之間的制約關系，也可以說是“同步的進程之間的制約關系”。如圖 2-4 所示，A1、B1、C1 是一條指令的取指、分析、執行的三個步驟，所以它們之間的關系是直接制約。
間接制約通常是指多個操作之間相同步驟的制約關系，也可以說是“互斥的進程之間的制約關系”。如圖 2-4 所示，A1、A2、A3 之間就存在間接制約的關系。前趨圖的應用廣泛，在項目開發中，可用前趨圖來分析哪些活動可以并行完成。同時項目管理工具：Pert 圖，單（雙）代號網絡圖等都融入了前趨圖的思想。
6．進程調度與死鎖
進程調度即處理器調度（又稱上下文轉換），它的主要功能是確定在什么時候分配處理器，并確定分給哪一個進程，即讓正在執行的進程改變狀態并轉入就緒隊列的隊尾，再由調度原語將就緒隊列的隊首進程取出，投入執行。
引起進程調度的原因有以下幾類：
（1）正在執行的進程執行完畢。
（2）執行中的進程自己調用阻塞原語將自己阻塞起來進入睡眠狀態。
（3）執行中的進程調用了 P 原語操作，從而因資源不足而阻塞；或調用 V 原語操作激活了等待資源的進程隊列。
（4）在分時系統中，當一進程用完一個時間片。
（5）就緒隊列中某進程的優先級變得高于當前執行進程的優先級，也將引起進程調度。
進程調度的方式有兩類：剝奪方式與非剝奪方式。

• 所謂非剝奪方式是指，一旦某個作業或進程占用了處理器，別的進程就不能把處理器從這個進程手中奪走，直到該進程自己因調用原語操作而進入阻塞狀態，或時間片用完而讓出處理機；
• 剝奪方式是指，當就緒隊列中有進程的優先級高于當前執行進程的優先級時，便立即發生進程調度，轉讓處理機。

進程調度的算法是服務于系統目標的策略，對于不同的系統與系統目標，常采用不同的調度算法：
（1）先來先服務（First Come and First Serverd，FCFS）調度算法，又稱先進先出（First In
and First Out，FIFO）。就緒隊列按先來后到原則排隊。
（2）優先數調度。優先數反映了進程優先級，就緒隊列按優先數排隊。有兩種確定優先級的方法，即靜態優先級和動態優先級。靜態優先級是指進程的優先級在進程開始執行前確定，執行過程中不變，而動態優先級則可以在進程執行過程中改變。
（3）輪轉法（Round Robin）。就緒隊列按 FCFS 方式排隊。每個進程執行一次占有處理器時間都不超過規定的時間單位（時間片）若超過，則自行釋放自己所占有的 CPU 而排到就緒隊列的末尾，等待下一次調度。同時，進程調度程序又去調度當前就緒隊列中的第一個進程。
進程管理是操作系統的核心，在進程管理的實現中，如果設計不當，會出現一種尷尬的局面——死鎖。
當若干個進程互相競爭對方已占有的資源，無限期地等待，不能向前推進時會造成“死鎖”。例如，P1 進程占有資源 R1，P2 進程占有資源 R2，這時，P1 又需要資源 R2，P2 也需要資源 R1，它們在等待對方占有的資源時，又不會釋放自己占有的資源，因而使雙方都進入了無限等待狀態。
死鎖是系統的一種出錯狀態，它不僅會浪費大量的系統資源，甚至還會導致整個系統的崩潰，所以死鎖是應該盡量預防和避免的。
（1）死鎖條件。產生死鎖的主要原因是供共享的系統資源不足，資源分配策略和進程的推進順序不當。系統資源既可能是可重復使用的永久性資源，也可能是消耗性的臨時資源。產生死鎖的必要條件是：互斥條件、保持和等待條件、不剝奪條件和環路等待條件。
（2）解決死鎖的策略。處于死鎖狀態的進程不能繼續執行但又占用了系統資源，從而阻礙其他作業的執行。

• 解決死鎖有兩種策略：一種是在死鎖發生前采用的預防和避免策略；另一種是在死鎖發生后采用的檢測與恢復策略。
• 死鎖的預防主要是通過打破死鎖產生的 4 個必要條件之一來保證不會產生死鎖。采用的死鎖預防策略通常有資源的靜態分配法或有序分配法，它們分別打破了資源動態分配條件和循環等待條件，因此不會發生死鎖。但這樣做會大大降低系統資源的利用率和進程之間的并行程度。
• 死鎖避免策略，則是在系統進行資源分配時，先執行一個死鎖避免算法（典型的如銀行家算法），以保證本次分配不會導致死鎖發生。由于資源分配很頻繁，因此死鎖避免策略要耗費大量的 CPU 和時間。

實際上，系統出現死鎖的概率很小，故從系統所花的代價上看，采用死鎖發生后的檢測與恢復策略要比采用死鎖發生前的預防與避免策略代價小一些。

2.2.2 存儲管理

• 存儲器是計算機系統中最重要的資源之一。因為任何程序和數據以及各種控制用的數據結構都必須占有一定的存儲空間，因此，存儲管理直接影響系統性能。
• 存儲器由內存和外存組成。內存是由系統實際提供的存儲單元（常指字節）組成的一個連續地址空間，處理器可直接存取。外存（輔存）是指軟盤、硬盤、光盤和磁帶等一些外部存儲部件，常用來存放暫不執行的程序和數據。處理器不能直接訪問外存，需通過啟動 I/O（Input/Output，輸入/輸出）設備才能進行內存、外存交換，其訪問速度慢，但價格便宜，常用作內存的后援設備。
• 內存大小由系統硬件決定，存儲容量受到實際存儲單元的限制。虛擬存儲器（簡稱虛存）
  不考慮實際內存的大小和數據存取的實際地址，只考慮相互有關的數據之間的相對位置，其容量由計算機地址的位數決定。
• 系統中內存的使用一般分成兩部分，一部分為系統空間，存放操作系統本身及相關的系統程序；另一部分為用戶空間，存放用戶的程序和數據。
• 存儲管理主要是指對內存儲器的管理，負責對內存的分配和回收、內存的保護和內存的擴充。存儲管理的目的是盡量提高內存的使用效率。存儲管理的機制經歷了多次變遷，由以前的單一連續區管理到分區存儲管理再發展為段頁式管理。目前前兩種技術已逐步被淘汰，下面我們將詳細解讀段頁式存儲管理。
  1．頁式存儲管理
• 分頁的基本思想是把程序的邏輯空間和內存的物理空間按照同樣的大小劃分成若干頁面，并以頁面為單位進行分配。在頁式存儲管理中，系統中虛地址是一個有序對（頁號，位移）。系統為每一個進程建立一個頁表，其內容包括進程的邏輯頁號與物理頁號的對應關系、狀態等。
• 頁式系統的動態地址轉換是這樣進行的：當進程運行時，其頁表的首地址已在系統的動態地址轉換機構中的基本地址寄存器中。執行的指令訪問虛存地址（p，d）時，首先根據頁號 p 查頁表，由狀態可知，這個頁是否已經調入內存。若已調入內存，則得到該頁的內存位置 p’，然后，與頁內相對位移 d 組合，得到物理地址 r。如果該頁尚未調入內存，則產生缺頁中斷，以裝入所需的頁，如圖 2-5 所示
  
• 頁式虛擬存儲管理是在頁式存儲管理的基礎上實現虛擬存儲器的。首先把作業信息作為副本存放在磁盤上，作業執行時，把作業信息的部分頁面裝入內存儲器，作業執行時若所訪問的頁面已在內存中，則按頁式存儲管理方式進行地址轉換，得到欲訪問的內存絕對地址，若欲訪問的頁面不在內存中，則產生一個“缺頁中斷”，由操作系統把當前所需的頁面裝入內存儲器中。
• 為此，在裝入作業時，就應在該作業的頁表中指出哪些頁已在內存儲器中，哪些頁還沒有裝入內存。可用一個標志位指示對應頁是否在內存儲器，可假設標志位為 1 表示該頁在內存，而標志位為 0 表示該頁尚未裝入內存。為了能方便地從磁盤上找到作業信息的副本，故在頁表中還可指出每一頁副本在磁盤上的位置。
• 當要裝入一個當前需要的頁面時，如果內存儲器中無空閑塊，則可選擇一個已在內存儲器中的頁面，把它暫時調出內存。若在執行中該頁面被修改過，則把頁信息重新寫回到磁盤上，否則不必重新寫回磁盤。當一頁被暫時調出內存后，讓出的內存空間用來存放
• 當前需要使用的頁面。以后再使用被調出的頁面時，可用同樣的方法調出另一個頁面而將其再裝入內存。頁面被調出或裝入之后都要對頁表中的相應表目做修改。當內存中無空閑塊時，為了裝入一個頁面而必須按某種算法從已在內存的頁中選擇一頁，將它暫時調出內存，讓出內存空間以存放所需裝入的頁面，這個工作稱為“頁面調度”。如何選擇調出的頁面是很重要的，如果采用了一個不合適的算法，就會出現這樣的現象：剛被調出的頁面又立即要用，因而又要把它裝入，而裝入不久又被選中調出，調出不久又被裝入，如此反復，使調度非常頻繁。這種現象稱為“抖動”。一個好的調度算法應減少或避免抖動現象。常用的頁面調度算法有：
  （1）最優（OPT）算法。選擇不再使用或最遠的將來才被使用的頁，這是理想的算法，
  但是難以實現，常用于淘汰算法的比較。
  （2）隨機（RAND）算法。隨機地選擇被淘汰的頁，開銷小，但是可能選中立即就要訪
  問的頁。
  （3）先進先出算法。選擇在內存駐留時間最長的頁似乎合理，但可能淘汰掉頻繁使用的頁。另外，使用 FIFO 算法時，在未給予進程分配足夠的頁面數時，有時會出現給予進程的頁面數增多，缺頁次數反而增加的異常現象。FIFO 算法簡單，易實現。可以把裝入內存儲器的那些頁的頁號按進入的先后順序排成隊列，每次總是調出隊首的頁，當裝入一個新頁后，把新頁的頁號排到隊尾。
  （4）最近最少使用（Least Recently Used，LRU）算法。選擇離當前時間最近的一段時間內使用得最少的頁。這個算法的主要出發點是，如果某個頁被訪問了，則它可能馬上就要被訪問；反之，如果某個頁長時間未被訪問，則它在最近一段時間也不會被訪問。
  2．段式存儲管理
• 段式存儲管理與頁式存儲管理相似。分段的基本思想是把用戶作業按邏輯意義上有完整意義的段來劃分，并以段為單位作為內外存交換的空間尺度。
• 一個作業是由若干個具有邏輯意義的段（如主程序、子程序、數據段等）組成。分段系統中，容許程序（作業）占據內存中許多分離的分區。每個分區存儲一個程序分段。這樣，每個作業需要幾對界限地址寄存器，判定訪問地址是否越界也就更困難了。在分段存儲系統中常常利用存儲保護鍵實現存儲保護。分段系統中虛地址是一個有序對（段號，位移）。系統為每個作業建立一個段表，其內容包括段號、段長、內存起始地址和狀態等。狀態指出這個段是否已調入內存，即內存起始地址指出這個段，狀態指出這個段的訪問權限。
• 分段系統的動態地址轉換是這樣進行的：進程執行時，其段表的首地址已在基本地址寄存器中，執行的指令訪問虛存（s，d）（取指令或取操作數）時，首先根據段號 s 查段表，若段已經調入內存，則得到該段的內存起始地址，然后與段內相對地址（段內偏移量 d）相加，得到實地址。如果該段尚未調入內存，則產生缺段中斷，以裝入所需要的段。段式存儲與頁式存儲的地址轉換方式類似。
• 段式虛擬存儲管理仍然以段式存儲管理為基礎，為用戶提供比內存實際容量大的虛擬空
  間。段式虛擬存儲管理把作業中的各個分段信息都保留在磁盤上，當作業可以投入執行時，做如下操作：
  （1）首先把當前需要的一段或幾段裝入內存。
  （2）作業執行時，如果要訪問的段已經在內存，則按照“段式存儲管理”中的方式進行地址轉換；如果要訪問的段不在內存中，則產生一個“缺段中斷”，由操作系統把當前需要的段裝入內存。
  因此，在段表中應增設段是否在內存的標志以及各段在磁盤上的位置，已在內存中的段仍要指出該段在內存中的起始地址和占用內存區長度。
  作業執行要訪問的段時，由硬件的地址轉換機構查段表。若該段在內存中，則立即把邏輯地址轉換成絕對地址；若該段不在內存中，則形成“缺段中斷”，由操作系統處理這個中斷。
• 處理的辦法是，查內存分配表，找出一個足夠大的連續區以容納該分段，如果找不到足夠大的連續區則檢查空閑區的總和，若空閑區總和能滿足該段要求，那么進行適當移動將分散的空閑區集中；若空閑區總和不能滿足該段要求，可把內存中的一段或幾段調出，然后把當前要訪問的段裝入內存中。段被移動、調出和裝入后都要對段表中的相應表目做修改。新的段被裝入后應讓作業重新執行被中斷的指令，這時就能找到要訪問的段，也可以繼續執行下去。
  3．段頁式存儲管理
  段頁式管理是段式和頁式兩種管理方法結合的產物，綜合了段式組織與頁式組織的特點，根據程序模塊分段，段內再分頁，內存被分劃成定長的頁。段頁式系統中虛地址形式是（段號、頁號、頁內偏移），如圖 2-6 所示。系統為每個進程建立一個段表，為每個段建立一個頁表。段頁式管理采用段式分配、頁式使用的方法，便于動態連接和存儲的動態分配。這種存儲管理能提高內存空間的利用率。
  
• 段式虛擬管理還是以段為單位分配內存空間，整段的調出、裝入，有時還要移動，這些都增加了系統的開銷。如果按段頁式存儲管理的方式，把每一段再分成若干頁面，那么，每一段不必占用連續的存儲空間；甚至當內存塊不夠時，可只將一段中的部分頁面裝入內存，這種管理方式稱為“段頁式虛擬存儲管理”。
• 段頁式虛擬存儲管理為每一個裝入內存的作業建立一張段表，還要為每一段建立頁表。段表中指出該段的頁表存放位置及長度，頁表中應指出該段的各頁在磁盤上的位置以及頁是否在內存中，若在內存中則填上占用的內存塊號。作業執行時按段號查段表，找到相應的頁表再根據頁號查頁表，由標志位判定該頁是否已在內存，若是，則進行地址轉換；否則進行頁面調度。地址轉換過程如圖 2-7 所示。
  
  段頁式虛擬存儲管理結合了段式和頁式的優點，但增加了設置表格（段表、頁表）和查表等開銷，段頁式虛擬存儲器一般只在大型計算機系統中使用。

設備管理

在計算機系統中，除了處理器和內存之外，其他的大部分硬設備稱為外部設備。它包括輸入/輸出設備，輔存設備及終端設備等。這些設備種類繁多，特性各異，操作方式的差異很大，從而使操作系統的設備管理變得十分繁雜。在架構師考試中，設備管理需要掌握的知識內容較少，主要為兩個方面：
1．數據傳輸控制方式
設備管理的主要任務之一是控制設備和內存或 CPU 之間的數據傳送，本節介紹幾種常用的數據傳送控制方式。選擇和衡量控制方式的原則如下：
（1）數據傳送速度足夠高，能滿足用戶的需要但又不丟失數據。
（2）系統開銷小，所需的處理控制程序少。
（3）能充分發揮硬件資源的能力，使得 I/O 設備盡量處于使用狀態中，而 CPU 等待時間少。
外圍設備和內存之間常用的數據傳送控制方式主要有以下幾種：
（1）程序控制方式。處理器啟動數據傳輸，然后等設備完成。

（2）中斷方式。程序控制方式不能實現并發。中斷方式的數據傳輸過程是這樣的，進程啟動數據傳輸（如讀）后，該進程放棄處理器，當數據傳輸完成，設備控制器產生中斷請求，中斷處理程序對數據傳輸工作處理之后，讓相應進程成為就緒狀態。以后，該進程就可以得到所需要的數據。

（3）直接存儲訪問（Direct Memory Access，DMA）方式。指外部設備和內存之間開辟直接的數據交換通路。除了控制狀態寄存器和數據緩沖寄存器外，DMA 控制器中還包括傳輸字節計數器、內存地址寄存器等。DMA 方式采用竊取（或挪用）處理器的工作周期和控制總線而實現輔助存儲器和內存之間的數據交換。有的 DMA 方式也采用總線浮起方式傳輸大批量數據。

（4）通道方式。通道又稱為輸入/輸出處理器（Input/Output Processor，IOP），可以獨立完成系統交付的輸入/輸出任務，通過執行自身的輸入/輸出專用程序（稱通道程序）進行內存和外設之間的數據傳輸。主要有 3 種通道：字節多路通道、選擇通道和成組多路通道。

2．虛設備與 SPOOLING 技術
采用假脫機技術，可以將低速的獨占設備改造成一種可共享的設備，而且一臺物理設備可以對應若干臺虛擬的同類設備。假脫機（Simultaneous Peripheral Operation On Line，SPOOLING）的意思是外部設備同時聯機操作，又稱為假脫機輸入/輸出操作，采用一組程序或進程模擬一臺輸入/輸出處理器。

SPOOLING 系統的組成如圖 2-8 所示。該技術利用了專門的外圍控制機將低速 I/O 設備上的數據傳送到高速設備上，或者相反。但是當引入多道程序后，完全可以利用其中的一道程序來模擬脫機輸入時的外圍控制機的功能，把低速的 I/O 設備上的數據傳送到高速磁盤上；再利用另一道程序來模擬脫機輸出時外圍控制機的功能，把高速磁盤上的數據傳送到低速的 I/O 設備上。這樣便可以在主機的控制下實現脫機輸入、輸出的功能。此時的外圍操作與 CPU 對數據的處理同時進行。

采用假脫機技術，可以將低速的獨占設備改造成一種可共享的設備，而且一臺物理設備可以對應若干臺虛擬的同類設備。SPOOLING 系統必須有高速、大容量并且可隨機存取的外存（例如，磁盤或磁鼓）支持。

在現代計算機系統中，還可以用一臺設備來模擬自身。例如，常見的多窗口技術，即在一個終端上開多個窗口，每個窗口可以獨立地進行顯示，以監視用戶不
同任務的執行情況。這是通過縮小顯示區域、平鋪或重疊顯示來模擬多個顯示器的。

2.2.4 文件管理

操作系統對計算機的管理包括兩個方面：硬件資源和軟件資源。硬件資源的管理包括CPU 的管理、存儲器的管理、設備管理等，主要解決硬件資源的有效和合理利用問題。 軟件資源包括各種系統程序、各種應用程序、各種用戶程序，也包括大量的文檔材料、庫函數等。每一種軟件資源本身都是具有一定邏輯意義的相關信息的集合，在操作系統中它們以文件形式存儲。

計算機系統的重要作用之一是能快速處理大量信息，因此數據的組織、存取和保護成為一個極重要的內容。文件系統是操作系統中組織、存取和保護數據的一個重要部分。文件管理的功能包括：建立、修改、刪除文件；按文件名訪問文件；決定文件信息的存放位置、存放形式及存取權限；管理文件間的聯系及提供對文件的共享、保護和保密等。允許多個用戶協同工作又不引起混亂。文件的共享是指一個文件可以讓多個用戶共同使用，它可以減少用戶的重復性勞動，節省文件的存儲空間，減少輸入/輸出文件的次數等。文件的保護主要是為防止由于錯誤操作而對文件造成的破壞。文件的保密是為了防止未經授權的用戶對文件進行訪問。

文件的保護、保密實際上是用戶對文件的存取權限控制問題。一般為文件的存取設置兩級控制：第 1 級是訪問者的識別，即規定哪些人可以訪問；第 2 級是存取權限的識別，即有權參與訪問者可對文件執行何種操作。

1．文件的邏輯結構
文件的結構是指文件的組織形式，從用戶角度所看到的文件組織形式，稱為文件的邏輯結構。

文件的邏輯組織是為了方便用戶使用。一般文件的邏輯結構可以分為兩種：無結構的字符流文件和有結構的記錄文件。記錄文件由記錄組成，即文件內的信息劃分成多個記錄，以記錄為單位組織和使用信息。

記錄文件有順序文件、索引順序文件、索引文件和直接文件。

（1）順序文件。大多數文件是順序文件。順序文件的記錄定長，記錄中的數據項的類型長度與次序固定，一般還有一個可以唯一標識記錄的數據項，稱為鍵（key），記錄是按鍵值的約定次序組織的。順序文件常用于批處理應用，對于查詢或更新某個記錄的處理性能不太好。

（2）索引順序文件。索引順序文件是基于鍵的約定次序組織的，而且維護鍵的索引和溢出區域。鍵的索引也可以是多級索引。索引順序文件既適用于交互方式應用，也適用于批處理方式應用。

（3）索引文件。索引文件是基于記錄的一個鍵數據項組織的。許多應用需按照別的數據項訪問文件，為此，常采用索引文件方法，即對主文件中的記錄按需要的數據項（一個或幾個）建索引，索引文件本身是順序文件組織。

（4）直接文件。直接文件又稱哈希（Hash）文件。記錄以它們在直接訪問存儲設備上的物理地址直接（隨機地）訪問。直接文件常用 于需要高速訪問文件而且每次僅訪問一條記錄的應用中。

2．文件的物理結構
文件的物理結構是指文件在存儲設備上的存放方法。文件的物理結構側重于提高存儲器的利用效率和降低存取時間。文件的存儲設備通常劃分為大小相同的物理塊，物理塊是分配和傳輸信息的基本單位。文件的物理結構涉及文件存儲設備的組塊策略和文件分配策略，決定文件信息在存儲設備上的存儲位置。常用的文件分配策略有：

（1）順序分配（連續分配）。這是最簡單的分配方法。在文件建立時預先分配一組連續的物理塊，然后，按照邏輯文件中的信息（或記錄）順序，依次把信息（或記錄）按順序存儲到物理塊中。這樣，只需知道文件在文件存儲設備上的起始位置和文件長度，就能進行存取，這種分配方法適合于順序存取，在連續存取相鄰信息時，存取速度快。其缺點是在文件建立時必須指定文件的信息長度，以后不能動態增長，一般不宜用于需要經常修改的文件。

（2）鏈接分配（串聯分配）。這是按單個物理塊逐個進行的。每個物理塊中（一般是最后一個單元）設有一個指針，指向其后續連接的下一個物理塊的地址，這樣，所有的物理塊都被鏈接起來，形成一個鏈接隊列。在建立鏈接文件時，不需要指定文件的長度，在文件的說明信息中，只需指出該文件的第一個物理塊塊號，而且鏈接文件的文件長度可以動態地增長。只調整物理塊間的指針就可以插入或刪除一個信息塊。 鏈接分配的優點是可以解決存儲器的碎片問題，提高存儲空間利用率。由于鏈接文件只能按照隊列中的鏈接指針順序查找，因此搜索效率低，一般只適用于順序訪問，不適用于隨機存取。

（3）索引分配。這是另一種對文件存儲不連續分配的方法。采用索引分配方法的系統，為每一個文件建立一張索引表，索引表中每一表項指出文件信息所在的邏輯塊號和與之對應的物理塊號。索引分配既可以滿足文件動態增長的要求，又可以方便而迅速地實現隨機存取。對一些大的文件，當索引表的大小超過一個物理塊時，會發生索引表的分配問題。一般采用多級（間接索引）技術，這時在由索引表指出的物理塊中存放的不是文件存放處而是存放文件信息的物理塊地址。這樣，如果一個物理塊能存儲 n 個地址，則一級間接索引將使可尋址的文件
長度變成 n2 塊，對于更大的文件可以采用二級甚至三級間接索引（例如，UNIX 操作系統采用三級索引結構，如圖 2-9 所示）。

索引文件的優點是既適用于順序存取，又適用于隨機存取。缺點是索引表增加了存儲 空間的開銷。另外，在存取文件時需要訪問兩次磁盤，一次是訪問索引表，另一次是根據索引表提供的物理塊號訪問文件信息。為了提高效率，一種改進的方法是，在對某個文件進行操作之前，預先把索引表調入內存。這樣，文件的存取就能直接從內存的索引表中確定相應的物理塊號，從而只需要訪問一次磁盤。

3．文件存儲設備管理
文件存儲設備管理，就是操作系統要有效地進行存儲空間的管理。由于文件存儲設備是分成許多大小相同的物理塊，并以塊為單位交換信息，因此，文件存儲設備的管理實質上是對空閑塊的組織和管理問題。它包括空閑塊的組織，空閑塊的分配與空閑塊的回收等問題。有 3 種不同的空閑塊管理方法，它們分別是索引法、鏈接法和位示圖法。

（1）索引法。索引法把空閑塊作為文件并采用索引技術。為了有效，索引對應于一個 或由幾個空閑塊構成的空閑區。這樣，磁盤上每一個空閑塊區都對應于索引表中一個條目，這個方法能有效地支持每一種文件分配方法。

（2）鏈接法。鏈接法使用鏈表把空閑塊組織在一起，當申請者需要空閑塊時，分配程 序從鏈首開始摘取所需的空閑塊。反之，管理程序把回收的空閑塊逐個掛入隊尾，這個方 法適用于每一種文件分配方法。空閑塊的鏈接方法可以按釋放的先后順序鏈接，也可以按 空閑塊區的大小順序鏈接。后者有利于獲得連續的空閑塊的請求，但在分配請求和回收空閑塊時系統開銷多一點。

（3）位示圖法。該方法是在外存上建立一張位示圖（Bitmap），記錄文件存儲器的使 用情況。每一位僅對應文件存儲器上的一個物理塊，取值 0 和 1 分別表示空閑和占用。文件存儲器上的物理塊依次編號為：0、1、2、…。假如系統中字長為 32 位，有 4096 個物理塊，那么在位示圖中的第 1 個字對應文件存儲器上的 0、1、2、…、31 號物理塊；第 2 個字對應文件存儲器上的 32、33、34、…、63 號物理塊；第 128 字對應文件存儲器上的 4064、4065、…、4095 號物理塊。這樣位示圖的大小為 32 字。

位示圖是利用二進制的一位來表示磁盤中一個盤塊的使用情況，如圖 2-10 所示。當其值為“0”時，表示對應的盤塊空閑；為“1”時表示已分配。由所有盤塊對應的位構成一個集合，稱為位示圖。位示圖也可描述為一個二維數組 map：Varmap:array[1．…m,1．…n]of bit;

4．樹型目錄結構
在計算機的文件系統中，一般采用樹型目錄結構。在樹型目錄結構中，樹的結點為根目錄，數據文件作為樹葉，其他所有目錄均作為樹的結點。

根目錄隱含于一個硬盤的一個分區中，根目錄在最頂層。它包含的子目錄是一級子目錄。每一個一級子目錄又可以包含若干二級子目錄，…，這樣的組織結構就叫作目錄樹。

當前盤和當前目錄是系統默認的操作對象。如果用戶沒有指明操作對象，系統就將用戶命令指向當前盤和當前目錄。

路徑是指從根目錄或者當前目錄開始到訪問對象（目錄或者文件），在目錄樹中路經的所有目錄的序列。例如“c:\dos\lmouse\mouse”就是 Windows 系統中的一條路徑。在樹型目錄結構中，從根目錄到任何數據文件之間，只有一條唯一的通路，從樹根開始，把全部目錄文件名與數據文件名，依次用“/”（UNIX/Linux 系統）或“\”（Windows 系統）連接起來，構成該數據文件的路徑名，且每個數據文件的路徑名是唯一的。這樣，便可以解決文件重名問題。

從樹根開始的路徑為絕對路徑，如果文件系統有很多級時，使用不是很方便，所以引入相對路徑，即從當前目錄開始，再逐級通過中間的目錄文件，最后到達所要訪問的數據文件。絕對路徑給出文件或目錄位置的完全描述，通常由層次結構的頂端開始（根目錄），通常第一個字符是“/”（UNIX/Linux 系統）或者是盤符（Windows 系統）。相對路徑通常由目錄結構中的當前位置開始，一般都比絕對路徑要短。 父目錄是指當前路徑的上一層目錄。每個目錄下都有代表當前目錄的“.”文件和代表當前目錄父目錄的“…”文件，相對路徑名一般就是從“…”開始的。

2.2.5 作業管理

從用戶的角度看，作業是系統為完成一個用戶的計算任務（或一次事務處理）所做的工作總和。例如，對于用戶編制的源程序，需經過對源程序的編譯、連接編輯或連接裝入及運行產生計算結果。這其中的每一個步驟，常稱為作業步，作業步的順序執行即完成了一個作業。

從系統的角度看，作業則是一個比程序更廣的概念。它由程序、數據和作業說明書組成。系統通過作業說明書控制文件形式的程序和數據，使之執行和操作。而且，在批處理系統中，作業是占據內存的基本單位。

用戶的作業可以通過直接的方式，由用戶自己按照作業步順序操作；也可以通過間接的方式，由用戶率先編寫的作業步依次執行的說明，一次交給操作系統，由系統按照說明依次處理。前者稱為聯機方式，后者稱為脫機方式。

1．作業狀態及其轉換
一個作業從交給計算機系統到執行結束退出系統，一般都要經歷提交、后備、執行和完成 4 個狀態。其狀態轉換如圖 2-11 所示。
（1）提交狀態。作業由輸入設備進入外存儲器（也稱輸入井）的過程稱為提交狀態。處于提交狀態的作業，其信息正在進入系統。
（2）后備狀態。當作業的全部信息進入外存后，系統就為該作業建立一個作業控制塊（Job Control Block，JCB）。系統通過 JCB 感知作業的存在。JCB 主要內容包括作業名、作業狀態、資源要求、作業控制方式、作業類型及作業優先權等。
（3）執行狀態。一個后備作業被作業調度程序選中而分配了必要的資源并進入了內存，作業調度程序同時為其建立了相應的進程后，該作業就由后備狀態變成了執行狀態。
（4）完成狀態。當作業正常運行結束，它所占用的資源尚未全部被系統回收時的狀態為完成狀態。

2．用戶接口
用戶接口也稱為用戶界面，其含義有兩種，一種是指用戶與操作系統交互的途徑和通道，即操作系統的接口；另一種是指這種交互環境的控制方式，即操作環境。
（1）操作系統的接口。操作系統的接口又可分成命令接口和程序接口。命令接口包含鍵盤命令和作業控制命令；程序接口又稱為編程接口或系統調用，程序經編程接口請求系統服務，即通過系統調用程序與操作系統通信。系統調用是操作系統提供給編程人員的唯一接口。系統調用對用戶屏蔽了操作系統的具體動作而只提供有關功能。系統調用大致分為設備管理、文件管理、進程控制、進程通信和存儲管理等。
（2）操作環境。操作環境支持命令接口和程序接口，提供友好的、易用的操作平臺。操作系統的交互界面已經從早期的命令驅動方式，發展到菜單驅動方式、圖符驅動方式和視窗操作環境。