1、基礎班講義操作系統主講：歡迎使用1目錄第一章 操作系統概述 考綱要求5操作系統的概念、特征、功能和提供的服務5操作系統的發展與分類6操作系統的發展6操作系統的分類6操作系統的運行環境6內核態與用戶態6中斷、異常7系統調用7操作系統體系結構7第二章 進程管理 考綱要求2.1 進程與線程（理解概念、掌握原理、綜合應用）進程的概念9進程的狀態與轉換9進程控制10進程組織10進程通信11線程概念與多線程模型112.2 處理機調度 調度的基本概念12調度的時機、切換和過程12調度的基本準則13調度方式132.3 同步與互斥 進程同步與互斥的基本概念13實現臨界區互斥的基本方法14信號量142.3.4 管

2、程142.3.5 經典的同步與互斥問題152.4 死鎖 2.4.1 死鎖的概念182死鎖處理策略18死鎖忽略18死鎖檢測和恢復19死鎖避免19死鎖預防20第三章 內存管理 考綱要求3.1 內存管理基礎 內存管理概念21交換與覆蓋213.1.3分配方式22連續分配管理方式22非連續分配管理方式223.2 虛擬內存管理 虛擬內存基本概念23請求分頁管理方式24頁面置換算法25頁面分配策略25工作集253.2.6 抖動25第四章 文件管理 考綱要求4.1 文件系統基礎 文件的概念27文件結構27目錄結構28文件共享29文件保護294.2 文件系統實現 文件系統層次結構29目錄實現29文件實現304.

3、3 磁盤組織與管理 磁盤的結構30磁盤調度算法30磁盤的管理313第五章 輸入輸出（I/O）管理 考綱要求5.1 I/O 管理概述 5.1.1 I/O 控制方式325.1.25.2 I/O5.2.1I/O層次結構33子系統 I/O 調度概念33高速緩存與緩沖區33設備分配與回收34假脫機技術（SPOOLing）34出錯處理354第一章 操作系統概述考綱要求（一）操作系統的概念、特征、功能和提供的服務（二）操作系統的發展與分類（三）操作系統的運行環境（四）操作系統體系結構本章的內容在統一般出 1 題選擇題，分值 2 分。1.1 操作系統的概念、特征、功能和提供的服務1.1.1 操作系統的概念操作

4、系統是計算機系統中最重要、最基本的系統作系統位于硬件和用戶程序之間。一方面，它能向用戶提供使用計算機的接口；另一方面，它能管理計算機軟硬件資源，提高其利用率；再者，利用虛擬技術，擴展了計算機的功能和使用范圍。因此，操作系統的定義為：操作系統是控制和管理計算機軟、硬件資源，以盡可能合理、高效的方法為不同用戶及其應用程序提供服務的一種系統程序。1.1.2 操作系統的特征操作系統具有并發、共享、虛擬和不確定性四大特征。其中，最重要的是并發特征，其他三個特征都是以并發為前提的。1.1.3 操作系統的功能操作系統主要有進程管理、管理、文件管理、輸入/輸出管理和作業管理五大功能。1.1.4 操作系統所能提

5、供的服務操作系統為用戶程序和系統程序提供了一系列的服務，這些服務可使使用計算機的人更快捷、高效和簡單地完成自己的工作。1命令輸入提供人機。52系統調用服務提供編的系統服務。1.2 操作系統的發展與分類1.2.1 操作系統的發展操作系統的發展目前呈現出多樣化的局面，大型計算機、巨型計算機需要滿足其集群計算，高性能計算的需求；計算機、工業控制計算機希望操作系統能實時響應；嵌入式計算機要求精簡、功能專一；便攜式設備要求省電，電池持續耐力強等等。因此，操作系統將會隨著用戶對系統不斷的新要求，在硬件的支持下，得到更加快速、強大地發展。1.2.2 操作系統的分類單用戶操作系統批處理操作系統批處理系統又分為

6、以下兩類。單道批處理系統多道批處理系統 3分時操作系統實時系統網絡操作系統分布式操作系統并行操作系統1.3 操作系統的運行環境1.3.1 內核態與用戶態多數系統將處理器工作狀態劃分為內核態和用戶態。前者一般指操作系統管理程序運行的狀態，具有較高的級別，又稱為態、系統態或管態；后者一般指用戶程序運行時的狀態，具有較低的級別，又稱為普通態、目態。61.3.2 中斷、異常所謂中斷（ errupt）是指處理機對系統中或系統外發生的異步事件的響應。異常（有時也稱為陷阱 trap）是指由系統發起的一次確定的服務過程。中斷與異常的區別與聯系：就比較通用的觀點來看，中斷是強迫性的，異常是自愿性的；中斷一般外來

7、的，異常是程序發出的，中斷服務于所有程序，異常一般為發出異常的程序服務。1.3.3 系統調用系統調用的處理過程是這樣的，當系統調用發生時，處理器通過一種特殊的機制，通常是中斷或者異常處理，把控制流程轉移到程序內的一些特定的位置。同時，處理器模式轉變成模式。其次，由程序執行被請求的功能代碼。這個功能代碼代表著對一段標準程序段的執行，用以完成所請求的功能。第三，處理結束之后，程序恢復系統調用之前的現場；把運行模式從的用戶程序。系統調用與一般程序調用的不同：模式恢復成為用戶方式；最后將控制權轉移回原來運行在不同的系統狀態。調用的程序是運行在用戶態，被調用的程序運行在系統態。進入的方式不同。過程調用語

8、句直接跳轉到被調用過程；而系統調用則必須通過運行系統調用命令。返回方式不同。過程調用直接返回；系統調用則不直接返回，有重新調度過程。代碼層次不同。過程調用是用戶級程序，而系統調用是系統級程序。系統調用一般不能嵌套或遞歸。1.4 操作系統體系結構常見的操作系統體系結構有整體式結構、層次式結構和微內核（客戶/服務器）結構等。本節對這些常見的操作系統體系結構做簡要的介紹。整體式結構首先確定操作系統的總體功能，然后將總功能分解為若干個子功能，實現每個子功能的程序稱為模塊。它的主要優點是：結構緊密，接口簡單直接，系統效率較高。層次式結構所謂層次式結構就是把操作系統的所有功能模塊，按功能流圖的調用次序，分

9、別將這些模塊排列成若干層，各層之間的模塊只能是單向依賴或單向調用關系。這樣不但操作系7統的結構清晰，而且不循環。微內核（客戶/服務器）結構這種模式內核提供所有操作系統基本都具有的那些操作，如線程調度、虛擬、消息傳遞、設備驅動以及內核的原語操作集和中斷處理等。這些部分通常采用層次結構并構成了基本操作系統。8第二章 進程管理考綱要求（一）進程與線程（二）處理機調度（三）同步與互斥（四）死鎖本章是統考的重點，出題分數在 10-16 分，一般會出 1 題綜合題，2-5 題選擇題。2.1 進程與線程（理解概念、掌握原理、綜合應用）進程的概念進程概念的定義進程是并發程序的動態運行，是多道程序系統中程序的動

10、態運行過程。進程是一個活動的實體，除了指令代碼，進程通常還包括進程堆段、棧段（包含臨時數據，如方法參數、返回地址和局部變量）和數據段（包含常量或全局變量等）。進程是程序在數據集合上運行的過程，它是系統進行資源分配和調度的一個獨立2進程的特征。動態性：動態性是進程最基本的特征。即進程由創建而產生，由調度而運行，因得不到資源而暫停運行，以及由撤銷而消亡。并發性：多進程同時存在于內存中，在一段時間內，同時運行。獨立性；進程是自我封閉的，有共享代碼段的進程互相之間也是獨立的。異步性：進程按各自獨立的、不可預知的速度向前推進，導致程序具有不可再現性。因此，在操作系統中，必須采取某種措施來保證各程序之間能

11、協調運行。結構性：由程序代碼（段）、數據（段）和進程控制塊組成。進程的狀態與轉換進程的基本狀態包括有以下幾種（三狀態模型）：運行狀態（Running）：進程占用處理機正在運行其程序。單處理機系統中只能有一個進程處于運行狀態，多處理機系統中可能有多個進程處于運行狀態。阻塞狀態（Blocked）：也叫等待或睡眠狀態，是進程由于等待某種事件的發生而處于暫停運行的狀態。如進程因等待輸入/輸出的完成、等待數據到達、等待緩沖空間等。9就緒狀態（Ready）：進程已分配到除處理機以外的所有必要資源，具備了運行的條件，可能會有多個進程處于就緒狀態，排成就緒隊列。圖 2-1 說明了三狀態進程模型及其轉換。進程還

12、有五狀態和七狀態模型，需要作一般了解。而三狀態的模型是最基本的模型。調度就緒時間到事件發事件等阻塞圖 2-1 三狀態進程模型4進程狀態的轉換(1)就緒狀態到運行狀態：調度程序為就緒狀態的進程分配處理機后，進入運行狀態。 (2)運行狀態到阻塞狀態：正在運行的進程因需要等待某事件而無法運行，讓出處理機。 (3)阻塞狀態到就緒狀態：進程所等待的事件發生了，進程就從阻塞狀態進入就緒狀態。 (4)運行狀態到就緒狀態：正在運行的進程因時間片用完而被暫停運行；或者在可搶先式調度方式中，一個優先級高的進程到來后，正在運行的優先級低的進程被強制撤下處理機，轉換為就緒狀態。進程控制進程原語所謂原語即原子操作，要么

13、全做，要么不做，一般是通過中斷來完成的。進程創建。進程撤銷。進程阻塞。進程喚醒。進程掛起。進程激活。進程組織進程實體程序：描述進程所要完成的功能，特指二進制的指令代碼。數據集合：程序運行所需要的數據結構。包括常數，變量，堆，數據棧等。進程控制塊：進程控制塊包含了進程的描述信息、控制信息和資源信息。102進程控制塊（PCB）PCB 是保存進程狀態和進程控制的標識，也是進程存在的唯一標識（也稱進程表 PT）。創建進程則產生 PCB，撤銷進程則系統就要回收 PCB。PCB 表項如圖 2-2。圖 2-2 PCB 表項內容系統中 PCB 采用適當的方式組織起來，對其進行管理。圖 2-3 所示。方式索引方

14、式圖 2-3 PCB 表組織方式2.1.5 進程通信進程間的信息交換工作稱為進程間的通信。P、V 操作稱為低級通信。高級通信是指進程之間以較高的效率傳送大量數據的通信方式。高級通信方式可分為三大類：共享內存、消息傳遞以及管道機制。線程概念與多線程模型線程的發明線程是進程中的一個實體，它是操作系統進行獨立調度和分派的基本，但不是資源分配的基本。線程自己不擁有系統資源，只擁有在運行中必不可少的資源，它同樣有就緒、阻塞和運行三種基本狀態。并且它與同屬一個進程的其他線程共享本進程所擁有的全部資源（內存、文件以及設備）。2線程實現方式11進程描述 信息進程控制和管理信息資源分 配處理機相 關信息進程標識

15、 符（）用戶標識 符進程當前狀態進程優先級代碼運行地址程序的外存地址進入內存時間處理機占用時間信號量使用代碼段 指針數據段 指針堆棧段 指針文件描 述符鍵盤鼠標通用寄存 器值地址寄存 器值控制寄存 器值標志寄存 器值狀態字內核線程：由操作系統根據內部需求進行創建和撤銷，內核線程依賴于操作系統內核的運行，因此操作系統知道內核線程的存在。也可以被用戶所調用。用戶線程：與操作系統內核無關，用戶程序利用操作系統提供的線程編寫形成，它的創建、同步、調度和管理等諸多工作均由用戶來實現。調度由用戶編寫的應用程序內部進行。但是由于操作系統不知道用戶線程的存在，所以用戶線程一旦因而阻塞，則其所在的整個進程也會阻

16、塞。操作系統僅把處理機時間分配給進程，所以用戶多線每個線程共個進程的時間，運行會變慢。2.2 處理機調度調度的基本概念作業調度作業調度又稱宏觀調度或高級調度。對處于后備狀態的作業進行選擇，并建立相應的進程。一般在批處理系統中，大多配有作業調度，而在其它系統中，通常不需配置作業調度。作業調度的運行頻率較低，通常為幾分鐘一次。進程調度進程調度是指決定就緒隊列中哪個進程將獲得處理機，并實際將處理機分配給該進程的操作。交換調度交換調度又稱中級調度。其主要任務是按照給定的原則和策略，將處于外存對換區中，且具備運行條件的就緒進程調入內存，或將處于內存就緒狀態或內存阻塞狀態的進程交換到外存對換區。調度的時機

17、、切換和過程引起進程調度的事件正在運行的進程運行完畢或發生某事件而不能再繼續運行；運行中的進程因提出輸入/輸出請求而暫停運行；在進程通信或同步過程中運行了某種原語操作，如 P 操作等；在可搶先式調度中，有一個比當前進程優先級更高的進程進入就緒隊列；在時間片輪轉法中，時間片用完。調度隊列在單處理機系統中，只有一個進程處于運行狀態。 3分派程序（dispatcher）進程調度算法只是決定哪一個進程將獲得處理機，是策略的制定者，而將處理機分配給該進程的具體操作是由分派程序完成的。分配程序是機制，是實際操作者，因此其運行效率較高。這里充分體現了策略與機制分離的設計。122.2.3 調度的基本準則調度的

18、基本準則包括：處理機利用率：盡可能讓昂貴的處理機處于繁忙中。吞吐量：時間內所完成進程的數量盡量多。周轉時間：從作業提交到作業完成所花費的時間。要讓周轉時間盡可能地小。后備時間：是指作業抵達系統后在外存等待進入內存的時間，越小越好。等待時間：是指在就緒隊列中等待調度進入處理機的時間。響應時間：是指從提交請求到產生第一響應輸出的時間。調度方式不可搶先方式可搶先方式進程調度算法比較先來先服務（FCFS）。短作業或短進程優先（SJF&SPF）。高響應比優先調度（HRRN）算法。響應比 Rp =（等待時間+預計運行時間）/高優先級優先調度算法。分靜態優先級和動態優先級。時間片輪轉調度算法（RR）。多級反

19、饋隊列調度算法。預計運行時間 =周轉時間/ 預計運行時間2.3 同步與互斥進程同步與互斥的基本概念基本概念在多道程序系統中，由于進程，各進程之間有兩種形式的制約關系：間接相互制約：源于資源共享。直接相互制約：源于進程合作。進程同步：主要源于進程合作，為進程之間的直接制約關系。進程互斥：主要源于資源共享，是進程之間的間接制約關系。臨界資源：一次只允許一個進程使用的資源稱為臨界資源，如、公共變量等。臨界區：在每個進程中，2同步機制應遵循的準則臨界資源的那段程序稱為臨界區。同步機制應遵循下述四條準則：13空閑則進：當臨界區空閑時，進程可以立即進入，以便有效地利用臨界資源。遇忙等待：當已有進程進入其臨

20、界區時，其它進程必須等待，以保證互斥。有限等待：對要求進入的進程，應在有限的時間內使之進入，以免陷入“死等”。（4）讓權等待：對于等待的進程，它必須立即處理機，以避免進程忙等。2.3.2 實現臨界區互斥的基本方法1用實現的同步互斥機制算法一：單標志法算法二：雙標志檢查算法三：雙標志法后檢查算法四：Petersons Algorithm 2進程互斥的硬件方法檢測和設置（TS）指令swap 指令（或 exchange 指令）該指令的作用是交換兩個字（字節）的內容2.3.3 信號量對信號量 S 進行P 操作，記為 P（S），處理過程如下-S.Q；if (S.Q 0)/表示申請一個資源/表示沒有空閑資

21、源調用進程進入等待隊列 S.Q；阻塞調用進程；對信號量 S 進行 V 操作，記為 V（S），處理過程如下+S.Q；if (S.Q = 0)/表示一個資源/表示有進程處于阻塞狀態從等待隊列 S.Q 中取出一個進程 P；進程P 進入就緒隊列；2.3.4 管程一個管程定義了一個數據結構和能為并發進程所運行的一組操作，這組操作能同步進改變管程中的數據。管程由三部分組成：局部于管程的共享數據說明；對該數據結構進行操作的一組過程；對局部于管程的數據設置初始值的語句。142.3.5 經典的同步與互斥問題1生產者-消費者問題用 C 語言和信號量機制描述生產者-消費者問題的程序如下：有界緩沖區的大小為 100。

22、#define N typedef semaphore semaphoresemaphore100semaphore； mutex = 1； empty = N； full = 0；/有界緩沖區大小/定義信號量/臨界區互斥信號量/空閑緩沖區/緩沖區初始化為空void producer(void)t item； while(1)item = produce_item()； P（empty）； P（mutex）； insert_item(item)； V（mutex）；V（full）；/局部變量/生產數據/獲取空數據槽/獲得進入臨界區的信號量/將數據放入緩沖池互斥量/數據量加一void consu

23、mer(void)t item； while(1)P（full）； P（mutex）；item = remove_item()； V（mutex）； V（empty）； consume_item(item)；/局部變量/獲取數據槽/獲得進入臨界區的信號量/將數據從緩沖池讀出互斥量/數據量減一，即空槽加一/消費數據2讀者-寫者問題設置互斥信號量 wmutex 表示寫者間、讀者和寫者間互斥，用 readcount 變量來讀者數，由于 readcount 是讀者間共享變量，屬于臨界資源，它也需互斥，為此，又增設互斥信號量 rmutex。程序如下：typedef semaphoresemaphores

24、emaphore； rmutex = 1；wmutex = 1；/定義信號量/讀者計數器的互斥量/寫-寫，讀-寫互斥量15t readcount = O； void reader(void)while (1) P(rmutex)；/讀者計數器/讀者進程/進程被調度/取得讀者計數器的互斥量/進來一個讀者，讀者數量加一readcount =readcount+1；if (readcount = 1) V(rmutex)； read_data_base()； P(rmutex)；readcount = readcountutex)；/如果是第一個讀者，取得讀-寫互斥量讀者計數器的互斥量/讀數據/讀者

25、讀完數據要離開，先取得讀者計數器的互斥量 1； /讀者數量減一if(readcount = O)V(wmutex)；/如果是最后一個離開的讀者，讀-寫互斥量V(rmutex)；use_dataread()；讀者計數器的互斥量/讀者使用數據void writer(void)while (1) think_up_data()；m tex)； write_data_base()； V(wmutex)；3哲學家進餐問題解決辦法/寫者進程/進程得到調度/寫者產生數據/獲得寫-寫，讀-寫操作互斥量/寫入數據庫寫-寫，讀-寫操作互斥量（1）至多只允許四個哲學家同時進餐，以保證至少有一個哲學家可以獲得二只筷子

26、：typedef semaphoresemaphoresemaphore；/定義信號量chopstick5=1，1，1，1，1；/初始化信號量eating = 4；/僅允許四個哲學家可以進餐/第i 個哲學家的程序void philosopher(while(1) thinking()； P(eating)；i)/工作之一/請求進餐，若是第五個則先挨餓/請求左手邊的筷子P(chopsticki)；16P(chopstick(i+1)%5)； eating()； V(chopstick(i+1)%5)； V(chopsticki)；V(eating)；/請求右手邊的筷子/進餐/右手邊的筷子/左手邊

27、的筷子信號量給其他挨餓的哲學家（2）另一種解決方法，僅當哲學家的左、右兩支筷子均可用時，才允許他拿起筷子進餐。typedef semaphoresemaphoresemaphore；/定義信號量chopstick5=1，1，1，1，1；/初始化信號量mutex = 1；/設置取筷子的信號量/第i 個哲學家的程序void philosopher(i)while(1)thinking()； P(mutex)； P(chopsticki)； P(chopstick(i+1)%5)； V(mutex)；eating()； V(chopstick(i+1)%5)； V(chopsticki)；/在取筷子

28、前獲得互斥量互斥量（3）規定奇數號哲學家先拿起其左邊筷子，然后再去拿右邊筷子；而偶數號哲學家則相反。程序代碼如下：typedefsemaphore；/定義信號量semaphore chopstick5=1，1，1，1，1；/初始化信號量void philosopher(i)while(1)thinking()； if(i%2 = 0) P(chopsticki+1%5)； P(chopsticki)；eating()；V(chopsticki+1%5)；/第i 個哲學家的程序/偶數哲學家，先右后左17V(chopsticki)；elseP(chopsticki)； P(chopsticki+1

29、%5) ; eating()； V(chopsticki)； V(chopsticki+1%5)；/奇數哲學家，先左后右2.4 死鎖死鎖的概念死鎖的概念系統中兩個或兩個以上的進程無限期地相互等待永遠不會發生的條件，系統處于一種停滯狀態，這種情況稱為死鎖。死鎖產生的原因死鎖的原因有以下二點：（1）進程推進順序不當和（2）對互斥資源的分配不當。必須要的是，系統資源不足并不是產生死鎖的原因，進程資源如果不足則進程就不會被創建，只有在資源部分分配以后，剩余的資源不能滿足某些個進程的請求，造成進程集無法推進的現象才是死鎖。3產生死鎖的四個必要條件互斥條件：任一時刻只允許一個進程使用資源。非條件：進程已經

30、占用的資源，不會被強制。占用并請求條件：進程占有部分資源，申請循環等待：請求資源的進程形成了循環。的資源，且不會已經占有的資源。2.4.2 死鎖處理策略對死鎖的處理，常用的方法有忽略死鎖、死鎖的檢測與恢復、死鎖的避免和死鎖的預防。2.4.3 死鎖忽略死鎖忽略最典型的算法是鴕鳥算法。18死鎖檢測和恢復資源分配圖算法資源矩陣法死鎖的解除與系統恢復恢復死鎖常用的方法有如下幾種：（1）資源法：掛起某些死鎖進程，并搶占它的資源。進程撤銷法：通過撤銷占有資源多的進程或代價量小的進程，以恢復死鎖。進程回退法：設置還原點，讓一個或多個進程回退到足以解除死鎖的地步。（4）重新啟動系統：代價最大，一切從頭開始。要

31、盡量避免采用此方法。死鎖避免安全與不安全狀態某一時刻，系統能按某種順序為每個進程分配其所需資源，使每個進程都能順利地完成，則稱此時系統處于安全狀態。反之，稱之為不安全狀態。家算法家算法問題描述是：一個家把他的固定借給若干顧客，使這些顧客能滿足對借走所有的要求又能完成其交易，也使后還不夠、還需要借貸，則家可以收回全部的現金。只要不出現一個顧客家的應是安全的。表 2-1 資源分配表經過分析。表2-2 用家算法進行資源分配19進程已分配資源尚需資源可用資源R1R2R3R1R2R3R1R2R3P200001021進程已分配資源尚需資源可用資源R1R2R3R1R2R3R1R2R3P1200001021P

32、2120132P3011131P4001200此時的安全序列不存在，故處于不安全狀態。2.4.6 死鎖預防所謂死鎖預防，就是采用某種策略，限制并發進程對資源的請求，使系統在任何時刻都不滿足死鎖的四個必要條件。死鎖預防主要是針對破壞四個必要條件進行的。破壞互斥條件：某些設備可以通過 SPOOLING 系統將獨享設備改造成為共享設備，以此可以解決互斥問題，例如。破壞非源。條件：資源暫時策略，申請新的資源得不到滿足則暫時已有的資破壞占用并請求條件；申請全部資源。破壞循環等待條件：資源有序申請，給資源，使用時按升序進行。201P4001200221P212013222X2P3011131第三章 內存管

33、理考綱要求（一） 內存管理基礎（二）虛擬內存管理本章也是聯考的重點，分值在 8-16 分間，1 題綜合題，或 2-5 題選擇題。3.1 內存管理基礎3.1.1 內存管理概念1管理的功能內存空間的分配與回收，包括內存的分配和共享。地址轉換：內存管理配合硬件進行地址轉換，把邏輯地址轉換成物理地址。（3）內存空間的擴充：借助于虛擬器或交換覆蓋技術來達到擴充內存容量的目的。（4）保護：為了避免相互干擾和破壞，必須提供保護功能。2地址重定位（1）邏輯地址空間物理地址空間地址重定位重定位類型地址重定位分為靜態重定位和動態重定位兩類。把作業在裝入過程中隨即進行的地址變換方式，稱為靜態重定位。在作業執行過程中

34、，當內存單元時才進行的地址變換方式，稱為動態重定位。動態重定位是在程序執行過程中由硬件地址變換機構實現的。動態重定位的主要優點如下：用戶作業在執行過程中，可以動態申請存中移動；有利于程序段的共享。3空間和在內（1）靜態。裝入時動態。運行時動態。3.1.2 交換與覆蓋覆蓋是指一個作業的某些程序段，或幾個作業的某些部分輪流使用某一段空間。21交換實質上是使用外存做緩沖，讓用戶程序在較小的空間中通過不斷地換出換入而可以運行較大的作業。交換可以是進程的整體交換，稱為“進程交換”。如果交換以進程的部分頁面或段為進行，則分別稱之為“頁面交換”或“分段交換”，又統稱為“部分交換”。這種交換方法是實現請求分頁

35、及請求分段式用了這種部分交換而得以實現。管理的基礎，虛擬系統就是采3.1.3分配方式1靜態分配在裝配程序把目標模塊進行 2動態分配裝入時確定它們在內存中的位置。其執行過程中可根據需要申請附加的空間。連續分配管理方式固定式和可變式分區管理固定式分區可變分區分配算法首次適應算法（管理（考綱不作要求）管理：根據作業的實際需要動態地劃分空間。Fit） Fit）Fit）下次適應算法（Next最佳適應算法（Best適應算法（Worst Fit）采用“內存緊縮”技術，可以把碎片集中起來形成一個大的空閑區。3分區的保護（1）界地址保護：界地址保護又稱為界限寄存器保護。界限寄存器方式：下界寄存器存放起始地址，上

36、界寄存器存放結束地址。基址寄存器和限長寄存器：基址寄存器存放起始地址，限長寄存器存放最大長度。（2）鍵保護：同一作業的各頁面所對應的內存塊都要指定一個相同的，但又不與其他作業相重的鍵碼。這個鍵碼存于快速寄存器和該作業的程序狀態字 PSW 中，當程序要某一塊時，將程序狀態字中的鍵碼與被，否則發出越界中斷。塊的鍵碼進行比較，若相符，則表明允許本次非連續分配管理方式簡單分頁管理分頁管理技術中的基本作法是：（1）等分內存：把內存劃分成大小相等的，稱為塊，或稱為頁框（Page Frame）。（2）用戶邏輯地址空間的分頁：把用戶的邏輯地址空間劃分成若干個與塊大小相等的，稱之為頁面或頁（Page）。并給各頁

37、從起始開始依次編以連續的頁號 0，1，2，。（3）邏輯地址的表示：用戶的邏輯地址從址“0”開始連續編址，即相對地址。22（4）內存分配原則：系統以塊為把內存分給作業或進程。（5）頁表和頁表地址寄存器：作業的一頁可以分配到內存空間中任何一個可用的塊。簡單分頁管理方法在作業或進程開始執行之前，把該作業或進程的程序段和數據全部裝入內存的各個空閑塊中，并通過頁表和硬件地址變換機構實現虛擬地址到內存物理地址的地址。（6）快表。（7）頁的共享與保護：保護的項目一般有讀、寫、運行等。2分段段式管理管理按用戶作業中的自來劃分邏輯空間，例如代碼段，數據段，堆棧段等等。每段占用連續的地址空間，因此作業的邏輯地址是

38、二維的，由段號和段內地址組成。把程序按內容或過程（函數）關系分成段，每段有自己的名字。地址轉換。段的共享與保護。（4）分段管理特點：優點是便于程序模塊化處理和便于處理變換的數據結構；便于動態限制。；便于共享分段；可以實現虛擬器，使作業的地址空間不受內存容量的3.2 虛擬內存管理虛擬內存基本概念局部性原理（1）時間局部性：程序中的某條指令一旦運行，以后該指令可能再次運行。產生時間局部性的典型原因是由于程序中存在著大量的循環操作。（2）空間局部性：一旦程序，其典型情況是程序順序運行。 2虛擬內存了某個單元，以后其附近的單元也將枝基于局部性原理，應用程序在運行之前并不必全部裝入內存，僅需將當前運行到

39、的那部分程序和數據裝入內存便可啟動程序的運行，其余部分仍駐留在外存上。當要運行的指令或的數據不在內存時，再由操作系統通過請求調入功能將它們調入內存，以使程序能繼續運行。如果此時內存已滿，則還需通過置換功能，將內存中暫時不用的程序或數據調至盤上，騰出足夠的內存空間后，再將要3實現虛擬內存的基礎的程序或數據調入內存，使程序繼續運行。硬件基礎：一定容量的內存；大容量的外存；地址變換機構（含快表）；缺頁中斷機構。基礎：虛實轉換的數據結構（頁表、段表等）；中斷服務處理程序；操作系統支持。234虛擬內存的主要特征多次性。對換性。虛擬性。請求分頁管理方式請求分頁的基本原理請求分頁管理是在簡單分頁管理基礎上發

40、展起來的。請求頁式管理在作業或進程開始執行之前，不要求把作業或進程的程序段和數據段地全部裝入內存，而只把當前需要的一部分頁面裝入內存，其它部分在作業執行過程中需要時，再從外存上調入內存。 2頁表的擴充如圖 3-1。（a） 簡單分頁系統的頁表（b）虛擬請求分頁系統的頁表圖 3-1 頁表的表項存在位（present/absent）：表示該頁是否在內存。修改位（modified）：該位為“0”時，在示訪頁面中的數據未被修改過。（3）位（referenced）：表示該頁面在最近期間是否被過。（4）外存地址(swap area address)：該頁面在外存上的存放地址。（5）其它：如頁面保護位（pro

41、tection），3地址變換緩存位（cache disabled）等。請求分頁的地址變換初始過程十分類似于簡單分頁系統的地址變換。 4缺頁中斷處理當存在位為 0 時，表示該頁不在內存，則必須確定它在外存中的存放地址。并把它從外存中調入內存。若內存中沒有空閑塊時，首先按照某種策略選擇某頁進行淘汰。以騰出空閑塊供本次調入的頁占用。這個過程也被稱之為頁面置換。若被選中淘汰的頁面中的信息修改過（修改位 = 1）還必須將其寫回外存。如內存中有空閑塊，則根據該頁在外存的地址，調入所需頁面，并更新頁表表項，最后恢復被中斷的指令重新執行。5調頁策略這是一個何時把頁面裝入內存的問題。如果出現缺頁中斷，表明企圖對

42、一個不存在于內存的頁面要求。顯然，應該立即裝入該頁面。這種僅當需要時才調取頁面的策略，稱為請求式調頁，采用請求式調頁策略的分頁系統稱為請求式分頁；而把事先調取頁面的策略稱為預調頁。24外存地址其它擴展讀寫控制修改位引 用位存在位頁框號讀寫控制頁框號頁面置換算法隨機淘汰算法在無法確定那些頁被的概率較低時，隨機地選擇某個用戶的頁面并將其換出。2先進先出算法（FIFO）FIFO(inout)算法：總是選擇駐留內存時間最長的頁面進行淘汰。其理由是：最早調入內存的頁面，其不再被使用的可能性最大。FIFO 算法忽略了一種現象的存在，就是在內存中停留時間最長的頁往往也是經常被訪問的頁。將這些頁淘汰，很可能剛

43、置換出去，又請求調用該頁，致使缺頁中斷較頻繁，嚴重降低內存的利用率。FIFO 的另一缺點是它有一種異常現象。稱為 Belady 異常。3最佳置換算法（OPT）最佳置換算法的基本是：從內存中移出永遠不再需要的頁面。4最近最久未使用頁面置換算RU）這種算法的基本是，利用局部性原理，根據一個作業在執行過程中過去的頁面訪問歷史來推測未來的行為。它認為過去一段時間里不曾被過的頁面，在最近的將來可能也不會再被。5最近沒有使用頁面置換算法（NRU）該算法只要求對應于每個塊（頁面）設置一個“位”和“修改位”。利用這二位組織成四種狀態，“位”：“修改位”=0：0；0：1；1：0；1：1。每次置換時，總取最小值的

44、頁面置換，若相同則隨機置換或先進先出置換。 6時鐘算法（CLOCK）時鐘算法是將作業已調入內存的頁面鏈成循環隊列，使用頁表中的“指針指向循環隊列中的下一個將被替換的頁面。位”，用一個頁面分配策略固定分配局部置換策略可變分配全局置換策略可變分配局部置換策略3.2.5 工作集工作集也稱為駐留集，是某一個進程調入物理內存的頁面的集合，這些頁面是頻繁地被使用到的，因此長期駐留內存是有利于提高處理機的效率。工作集模型是基于局部性原理假設的。3.2.6 抖動如果分配給進程的塊數量小于進程所需要的最小值，進程的運行將很頻繁地產生缺頁中斷。這種頻率非常高的頁面置換現象稱之為抖動（也稱為顛簸）。往往是剛被淘汰的

45、25頁面馬上被選中調頁而進入內存。抖動將引起嚴重的系統性能下降。防止抖動現象有多種辦法，例如，采取局部替換策略，引入工作集算法，掛起或撤銷若干進程等。26第四章 文件管理考綱要求（一） 文件系統基礎（二）文件系統實現（三）磁盤組織與管理本章在操作系統中也居于重點位置，選擇題。考題在 8-16 分間，通常綜合題 1 題，其它為4.1 文件系統基礎文件的概念文件定義文件是具有符號名的一組信息的集合。 2文件屬性文件的屬性是指與文件的數據相關的所有相關信息，包括：基本信息：文件名，文件別名，文件類型等；地址信息：文件物理位置，文件長那些用戶能夠讀寫或運行；文件使度；文件控制信息：文件的創建者，所有者

46、，用信息：文件創建的時間日期，最近的使用日期時間等。 3文件操作對文件操作有創建文件、讀文件、寫文件、截斷文件、設置文件的位置等。對的操作有、修改、刪除、檢索等。文件結構文件邏輯結構文件邏輯結構指用戶概念中的文件，獨立于物理結構，又稱邏輯文件。一般常用的文件其結構主要分為如下三類：（1）無結構文件：把文件看作是命名了相關聯的字符流集合，或稱流式文件。（2）累積文件：文件體為無結構序列，通過特定分隔符來劃分，各大小和組成可變。新總是添加到文件末尾。（3）索引文件：大小不必相同，不必排序，存放在主文件中。索引文件主文件不排序。另外建立索引，每個索引項指向一個，索引項按照中的某個關鍵字域排序。272

47、文件物理結構文件物理結構是指文件在理文件。常用的文件物理結構有：介質上的組織方式，它依賴于物理的設備，又稱物（1）順序結構：是把一個邏輯上連續的的文件分配到連續的物理塊中。（2）結構：把文件信息存放在非連續的物理塊中，每個物理塊均設有一個指針指向其后續連續的另一個物理塊，從而使得存放同一文件的物理塊成一個串聯隊列。鏈接方式又分為顯式和隱式。顯式的指針在專門的表中，隱式的指針在存放文件信息的物理塊中。（3）索引結構：指為每個文件建立一個索引表，其中每一個表項文件所在的物理塊號，表項按邏輯編寫，順序或按內某一關鍵字順序排列，對于大文件，為檢索方便，可以建立多級索引，還可以把文件索引表也作為一個文件

48、，稱為索引表文件。多重索引結構（混合索引結構）采用了間接索引方式，第一級索引表的表項下一級索引表的位置（物理塊號），下一級索引表的表項再下一級索引表的位置，這樣間接幾級，最末級索引表的表項則指向相應所在的物理塊號。目錄結構為實現“按名存取”，必須建立文件名與外存空間中的物理地址的對應關系，體現這種對應關系的數據結構稱為目錄。文件目錄管理基本要求實現“按名存取”：用戶只需提供文件名，即可對文件進行存取，這是目錄管理基本功能。實現文件共享：允許不同的用戶使用同一個文件。允許文件重名：采用多級目錄。 2文件組成文件包含兩部分內容：文件說明（或稱文件頭）與文件體。文件體是文件本身的信息，可能是式文件或

49、是字符流式文件。文件說明就是文件控制塊。目錄是由一組文件的文件說明（即文件控制塊 FCB）組成的文件，它本身也是一種文件。 3文件控制塊（FCB）組成（1）基本信息類：文件名、文件外存地址、文件邏輯結構、文件物理結構。（2）控制信息類：文件擁有者的權限、核準用戶的權限、一般用戶的權限。（3）使用信息類：文件建立的日期與時間，上一次修改的日期與時間、當前的使用信息。4文件目錄組織形式單級目錄結構二級目錄結構多級目錄結構多級目錄由稱為樹形目錄，將文件的多級目錄結構以圖形化表示，即是圖形化目錄。284.1.4 文件共享文件共享是指在不同用戶之間共同使用某些文件。實現文件共享主要有三種方式：（1）繞道

50、法（軟法）：路徑名是由當前目錄到信息文件通所有各級目錄的目錄名加上該信息文件的符號名組成。（2）法（硬法）：即一個目錄中的一個表項直接指向被共享文件所在的目錄表項，而不是直接指向文件。（3）基本目錄表方法基本文件目錄和符目錄結構是把所有文件目錄的內容分成兩部分：一部分包括文件的結構信息、物理塊號、存取控制和管理信息等文件說明，并用文件系統賦予的唯一的內部標識符來標識；另一部分包括符這兩部分分別稱為基本文件目錄表(BFD)和符名和系統賦予的該文件的內部標識符組成。目錄表(SFD)。4.1.5 文件保護1類型通過限制可進行的文件類型，保護機制可提供控制（特別地為防止文件被破壞，一般對寫和修改操作需

51、要特別控制）。類型有：讀；寫；修改；運行；添加；刪除；列表。2控制解決文件保護問題最為常用的是根據用戶進行控制。實現基于的最普通方法是為每個文件或目錄增加一個控制列表。所有用戶組對文件權限的集合形成了一個二維表即文件控制表，不同用戶對同一文件或目錄需要不同類型的。3文件系統安全為了盡量減少在系統發生故障時文件信息破壞，最簡便的措施是為重要的文件保存多個副本，即“定期轉儲”，當系統出現故障，就可以裝入轉儲的文件來恢復文件系統。（1）全量轉儲：把文件上。器中的全部文件定期（例，每周、每天）到備份磁帶（2）增量轉儲：全量轉儲只能恢復上次轉儲時的狀態。4.2 文件系統實現4.2.1 文件系統層次結構文

52、件系統的層次結構指明其調用結構。目錄實現線性列表292散列表4.2.3 文件實現文件的實現是依據文件的物理結構來實施的。文件的實現要使用多個磁盤和內存結構。不同的操作系統采用不同的方法。雖然這些結構因操作系統和文件系統而異，但還是有一些通用規律。4.3 磁盤組織與管理4.3.1 磁盤的結構圖 4-1 磁盤結構磁盤調度算法讀寫一次磁盤所需的時間可分為以下幾種：設備等待：設備或總線忙，需要等候。尋道時間：將讀/寫磁頭移動到相應的柱面所花費的時間。旋轉延遲時間：扇區轉到磁頭位置所需的時間。傳輸時間：數據寫入磁盤或從磁盤讀出的時間。常用的磁臂調度算法有：1先來先服務（FCFS）調度根據進程請求磁盤的時

53、間順序，先來先服務。2最短尋道時間優先（SSTF）調度根據磁頭的當前位置首先將請求隊列中距磁頭最短的請求為之服務。 3掃描算法（SCAN）調度也叫“電梯”算法，磁頭固定從外向內然后從內向外逐柱面運動。如此往復。4循環掃描（C-SCAN）調度30循環掃描算法，即磁頭從盤面上的一端向另一端移動，遇到請求立即服務，返回是直接快速移至起始端，而 務于任何請求。5察看（LOOK）調度通常磁頭只移動到一個方向上最遠的請求為之。接著馬上回頭，而不是繼續到磁盤的盡頭。這種形式的 SCAN 和 C-SCAN 稱為察看 LOOK 和循環察看 C-LOOK 調度，這是因為它們在朝個給定方向移動前會察看是否有請求。注意，部分將 SCAN 和 LOOK 算法都稱為掃描算法，考生應該根據題意，合理選擇相應的算法，做出符合題意的結果。4.3.3 磁盤的管理31第五章 輸入輸出（I/O）管理考綱要求（一） I/O 管理概述（二） I/O子系統出題量在 2-4 分，1 到 2 題選擇題。本章在聯5.1 I/O 管理概述I/O 控制方式I/O 設備概念I/O 設備：是指計算機系統中除控制器、運算器（通常