基礎·操作系統

基礎·操作系統

一 引論

什麼是操作系統

非形式化定義：計算機系統中的一個系統軟體，它是這樣一些程序模塊的集合——它們管理和控制計算機系統中的軟硬體資源，合理地組織計算機的工作流程，以便有效地利用這些資源為用戶提供一個功能強大、使用方便和可擴展的工作環境，從而在計算機與其用戶之間起到介面的作用。

操作系統的作用

1. 作為用戶與計算機硬體系統之間的介面

2. 是計算機系統資源的管理者

3. 實現了對計算機資源的抽象

操作系統的功能

1. 處理機管理：完成處理機資源的分配調度等功能；

2. 存儲管理：提高利用率、方便用戶使用、提供足夠的存儲空間、方便進程並發運行；

3. 文件管理：解決軟體資源的存儲、共享、保密和保護；

4. 設備管理：方便用戶使用設備、提高CPU與I/O設備利用率；

5. 用戶介面：提供一個友好的用戶訪問操作系統的介面；

操作系統常見分類

單用戶/多用戶：一台計算機在同一時間只能由一個用戶使用，用戶獨自享用系統的全部硬體和軟體資源，稱為單用戶操作系統；如果在同一時間允許多個用戶同時使用計算機，則稱為多用戶操作系統。

單任務/多任務：用戶在同一時間只能運行一個應用程序，稱為單任務操作系統；如果同一時間可以運行多個應用程序則稱為多任務操作系統。

批處理/分時/實時：採用批量處理作業技術的操作系統稱為批處理操作系統，批處理是指用戶將一批作業提交給操作系統後就不再干預，由操作系統控制它們自動運行，不具有交互性，它是為了提高CPU的利用率而提出的；採用時間片輪轉技術的操作系統稱為分時操作系統，它將系統處理機時間與內存空間按一定的時間間隔輪流地切換給各終端用戶的程序使用，由於時間間隔很短，每個用戶的感覺就像他獨佔計算機一樣，可有效增加資源的使用率；實時操作系統是能夠在指定或者確定的時間內完成系統功能以及對外部或內部事件在同步或非同步時間內做出響應的系統，提供及時響應和高可靠性是其主要特點。

MS-DOS是單用戶單任務操作系統。

Linux、Unix是多用戶多任務分時操作系統。

現代操作系統具有的基本特徵

1. 並發（Concurrence），並發性是指在一段時間內，宏觀上有多個程序在同時運行；

2. 共享（Sharing），共享是指系統中的資源可供內存中多個並發執行的作業同時使用；

3. 虛擬（Virtual），虛擬是指通過某種技術，將一個物理實體變為若干個邏輯上的對應物；

4. 非同步（Asynchronism），非同步性也稱不確定性，指進程的執行順序和執行時間的不確定性；

其他知識點：

現代操作系統通常為用戶提供三種使用界面：命令界面、圖形界面和系統調用界面。

操作系統的體系結構主要有單塊結構、層次結構和微內核結構。

多道程序設計是在計算機內存中同時存放幾道相互獨立的程序，使它們在管理程序控制之下，相互穿插的運行。引入多道程序設計技術的根本目的是為了提高CPU的利用率。

---

二 CPU

關於進程

進程是程序關於某數據集合上的一次運行活動（進程是正在運行的程序的實例）。如果說食譜是程序，原料是數據，那製作蛋糕就是進程。引入進程的目的是為了使多個程序並發執行，以改善資源利用率及提高系統的吞吐量，用進程代表運行的程序。

每個進程實體中包含了PCB、程序段和數據段三個部分。PCB（進程式控制制塊）是為了描述控制進程的運行，系統中存放進程的管理和控制信息的數據結構。PCB常駐內存，是進程存在的唯一標誌。

進程的三種基本狀態

1. 運行狀態：進程獲得CPU正在執行；

2. 就緒狀態：進程已獲得除CPU外的必要資源正在等待；

3. 阻塞狀態：遇到請求I/O，申請緩衝空間等事件使得進程執行受阻；

其相互轉換如下圖所示：

進程間的同步與互斥

一組並發進程因直接制約（時序關係或協同等待，而不是競爭資源）而進行相互合作，相互等待，使得各進程按一定速度執行的過程稱為進程間同步。

一組並發進程中的一個或多個程序段，因為共享公有資源而導致它們必須以一個不允許交叉執行的單位執行（也可以說不允許兩個以上共享資源的並發進程同時進入臨界區）稱為進程間互斥。

其中，臨界資源是指那些一次只允許一個進程使用的資源。（包括硬體資源和軟體資源，如印表機、共享變數等）；臨界區是指每個進程中訪問臨界資源的那段代碼。

信號量機制

信號量，實際上就是用來控制進程狀態的一個代表某一資源的存儲單元。它是最早出現的用來解決進程同步與互斥問題的機制，包括一個稱為信號量的變數及對它進行的兩個原語操作。

信號量有整型信號量（信號量是整數），記錄型信號量（每個信號量除一個整數值s.value（計數）外，還有一個進程等待隊列s.L，其中是阻塞在該信號量的各個進程的標識），二進位信號量（只允許信號量取0或1值）。

狄克斯特拉設計了一種同步機制叫「PV操作」，P操作和V操作是執行時不被打斷的兩個操作系統原語。執行P操作時申請一個空閑資源（把信號量減1），若結果不為負則執行完畢，否則執行P操作的進程被阻塞；執行V操作時釋放一個被佔用的資源（把信號量加1），若結果大於0則喚醒一個因執行P而阻塞的進程。通常P操作對應wait（等信號，也叫做掛起），V操作對應signal（給信號，也叫發信號）。P、V是荷蘭語翻譯。

信號量會有初值（>0），每當有進程申請使用信號量，通過一個P操作來對信號量進行-1操作，當計數器減到0的時候就說明沒有資源了，其他進程要想訪問就必須等待，當該進程執行完這段工作（我們稱之為臨界區）之後，就會執行V操作來對信號量進行+1操作。

例如為了使多個進程能互斥的訪問某臨界資源，只須為該資源設置一互斥信號量，並設其初始值為1，然後將各進程訪問該資源的臨界區置於wait(mutex)和signal(mutex)操作之間即可。wait(mutex)和signal(mutex)必須在同一個進程中成對地出現。

生產者與消費者問題

一個生產者進程和一個消費者進程共享一個初始為空，大小為n的緩衝區。只有當緩衝區沒滿的時候，生產者才能將消息放進去，滿時休眠（要麼乾脆就放棄數據）。同理，只有當緩衝區不空的時候，消費者才能從中取消息，否則必須休眠等待。這兩個進程存在著互斥關係和同步關係。

可以三個信號量：mutex、full和 empty來解決這個問題。信號量mutex作為互斥信號量，它用於控制互斥訪問緩衝池，互斥信號量初值為1；信號量 full 用於記錄當前緩衝池中「滿」緩衝區數，初值為0；信號量 empty 用於記錄當前緩衝池中「空」緩衝區數，初值為n。新的數據添加到緩存中後，full 在增加，而 empty 則減少。如果生產者試圖在 empty 為0時減少其值，生產者就會被「催眠」。下一輪中有數據被消費掉時，empty就會增加，生產者就會被「喚醒」。

哲學家進餐問題

有五個哲學家共用一張圓桌，分別坐在周圍的五張椅子上，在圓桌上有五個碗和五支筷子。平時哲學家進行思考，飢餓時便試圖取其左、右最靠近他的筷子，只有在他拿到兩支筷子時才能進餐，進餐完畢放下筷子又繼續思考。

解決哲學家問題的一個方法是，用一個信號量表示一隻筷子，五個信號量構成信號量數組，有：

wait(chopstick[i mod 5])

wait(chopstick[(i+1)mod 5]）

進餐

signal(chopstick[i mod 5])

signal(chopstick[(i+1)mod 5]）

上述情況會引起死鎖（比如所有人都拿起了自己左邊的筷子）。解決死鎖的辦法有：僅當哲學家的左、右兩隻筷子均可用時，才允許他拿起筷子進餐；或是至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，並在用畢時能釋放出他用過的兩隻筷子，從而使更多的哲學家能夠進餐。等等。

關於線程

線程，有時被稱為輕量級進程，是程序中一個單一的順序控制流程，是進程內一個相對獨立的、可調度的執行單元，是系統獨立調度和分派CPU的基本單位。線程自己不擁有系統資源，只擁有一點兒在運行中必不可少的資源，如線程式控制制塊、PC、寄存器和堆棧等。但它可與同屬一個進程的其它線程共享進程所擁有的全部資源。

一個線程可以創建和撤消另一個線程，同一進程中的多個線程之間可以並發執行。每一個程序都至少有一個線程，若程序只有一個線程，那就是程序本身。

在單個程序中同時運行多個線程完成不同的工作，稱為多線程。

線程同樣具有就緒、阻塞和執行三種基本狀態。

進程與線程對比

1.進程是資源分配的基本單位，線程是運算調度的基本單位；

2.一個進程可以包含多個線程，一個進程最少包含一個線程；

3.同一進程中的多個線程共享該進程的全部系統資源，如虛擬地址空間、文件描述符等，但有著自己的獨立資源如堆棧、寄存器等；

4.比起進程，線程創建開銷小，線程間切換速度快且通信方便；

關於死鎖

生活中最常見的死鎖：

在操作系統裡面，死鎖是指多個並發進程彼此等待對方所擁有的資源（比如印表機、磁帶機），且這些並發進程在得到對方的資源之前不會釋放自己所擁有的資源，從而使得各進程不能繼續向前推進。系統資源不足或進程推進順序不合適是導致死鎖的原因。

死鎖的四個必要條件

互斥條件：並發進程所要求和佔有的資源是不能同時被兩個以上進程訪問；

不剝奪條件：進程所獲得的資源在未使用完畢之前，不能被其他進程強行剝奪，而只能由獲得該資源的進程自己釋放；

請求和保持條件：進程已經佔有了至少一個資源，但又申請新的資源，而申請的資源已被其他進程佔有，該進程在等待新資源的同時繼續佔有已分配的資源；

環路等待條件：存在一種進程循環鏈，鏈中每一個進程已獲得的資源同時被下一個進程所請求。

解決死鎖的辦法

1. 設置某些限制條件，去破壞四個必要條件中的一個或幾個。比如規定只能一次性申請所有資源；

2. 分配資源的時候用某種方法防止其進入不安全的狀態。比如採用銀行家演算法；

3. 死鎖發生後恢復。比如剝奪資源或撤銷進程；

4. 鴕鳥演算法（忽略所有問題，假設系統不會死鎖）。

銀行家演算法

一個銀行家共有20億財產，3個開發商客戶。第一個開發商：已貸款15億，資金緊張還需3億；第二個開發商：已貸款5億，運轉良好能收回；第三個開發商：欲貸款18億。

在這種情況下，如果你是銀行家會怎麼處理？一個常規的想法就是先等著第二個開發商把錢收回來，然後手裡有了5個億，再把3個億貸款給第一個開發商，等第一個開發商收回來18個億，然後再把錢貸款給第三個開發商。

這個故事的意義就是眼光放長一點，不要只看著手裡有多少錢，同時要注意到別人欠自己的錢怎麼能收回來。同理，在操作系統中，有內存，硬碟等等資源被眾多進程渴求著，也可以通過類似的合理安排先後順序來防止死鎖。

首先定義安全序列：對當前申請資源的進程排出一個序列，保證按照這個序列分配資源能完成所有進程。假設有進程P1,P2,.....Pn，則安全序列要求滿足：Pi(1<=i<=n)需要資源<=剩餘資源 + 分配給Pj(1

<= j < i)資源。

存在安全序列則不會發生死鎖，不存在安全序列則可能發生死鎖。安全序列未必唯一。

其次定義需要的數據結構：

int n,m; //系統中進程總數n和資源種類總數m

int Available[1..m]; //每種資源當前可用總量

int Allocation[1..n,1..m]; //當前給分配給每個進程的各種資源數量

int Need[1..n,1..m];//當前每個進程還需分配的各種資源數量

int Work[1..m]; //當前可分配的資源

bool Finish[1..n]; //進程是否結束

判定安全序列的演算法為：

1. 初始化

Work = Available（動態記錄當前剩餘資源）

Finish[i] = false（設定所有進程均未完成）

2. 查找可執行進程Pi（未完成但目前剩餘資源可滿足其需要，這樣的進程是能夠完成的）

Finish[i] = false

Need[i] <= Work

如果沒有這樣的進程Pi，則跳轉到第4步

3. 若有則Pi一定能完成，且完成後會歸還其佔用的資源，即：

Finish[i] = true

Work = Work +Allocation[i]

GOTO 第2步，繼續查找

4. 如果所有進程Pi都是能完成的，即Finish[i]=ture，則系統處於安全狀態，否則系統處於不安全狀態。

內核態與用戶態

處理器主要有兩種許可權狀態，一種是內核態，一種是用戶態。內核態可以無限制地對系統存儲、外部設備進行訪問，用戶態則是非特權的執行狀態。通過這兩種狀態的劃分，可防止用戶程序破壞os內核代碼和數據。

系統在運行時由用戶態轉到內核態有3種最主要方式：

1. 系統調用。用戶態進程通過系統調用申請使用操作系統提供的服務程序完成工作；

2. 異常。當CPU在執行運行在用戶態下的程序時，發生了某些事先不可知的異常，這時會觸發由當前運行進程切換到處理此異常的內核相關程序中，比如缺頁異常；

3. 外圍設備的中斷。當外圍設備完成用戶請求的操作後，會向CPU發出相應的中斷信號，這時CPU會暫停執行下一條即將要執行的指令轉而去執行與中斷信號對應的處理程序，比如硬碟讀寫操作完成，系統會切換到硬碟讀寫的中斷處理程序中執行後續操作。

其中系統調用可以認為是用戶進程主動發起的，異常和外圍設備中斷則是被動的。

處理機調度

處理機調度分為高級調度、中級調度和低級調度。

高級調度又稱作業調度，用於決定把外存上處於後備隊列中的哪些作業調入內存，為它們分配必要的資源，並創建進程。

中級調度又稱交換調度，它按一定的演算法將外存中處於靜止就緒狀態或靜止阻塞狀態的進程換入內存，而將內存中處於活動就緒狀態或活動阻塞狀態的某些進程換出至外存。交換調度的目的是為了解決內存緊張問題。

低級調度又稱進程調度，主要任務是按照一定的策略選取就緒隊列中的一個進程獲得處理機。進程調度是最基本的調度，在os中必須配置它。

其中進程調度可採用下述兩種方式：非搶佔方式。一旦進程獲得cpu，它將一直執行，直至該進程完成或發生事件而阻塞時，才將cpu分配給其他進程；搶佔方式。當一進程正在處理機上執行時，系統可根據某種原則暫停它的執行，並將已分配給它的處理機重新分配給另一個進程。搶佔的原則有：優先權原則，短作業（進程）原則，時間片原則等。

進程調度演算法

先來先服務調度演算法（FCFS）：按進程創建的時間先後排序調度；

短作業優先調度演算法（SJF）：按進程運行的時間長短排序調度；

時間片輪轉調度演算法（RR）：將所有的就緒進程按照FCFS原則排成一個隊列，每次調度時將CPU分派給隊首進程，讓其執行一個時間片（幾個ms到幾百ms）。在一個時間片結束時發生時鐘中斷，將其送到就緒隊列的末尾，並通過上下文切換執行當前的隊首進程；

優先順序調度演算法（PSA）：就緒隊列按進程的優先順序排序調度，有非搶佔式優先權和搶佔式優先權兩種。另外優先順序也分靜態（不變）和動態（變）兩種；

高響應比優先調度演算法（HRRF）：HRRF是介於FCFS與SJF之間的折中演算法，既考慮作業等待時間又考慮作業運行時間，既照顧短作業又不使長作業等待時間過長。響應比 =（等待時間+要求服務時間）/ 要求服務時間；

多級反饋隊列調度演算法（MFQ）：也叫動態優先數輪轉調度演算法，既能使高優先順序的作業得到響應又能使短作業迅速完成，在Unix中使用。具體可表述為：

1. 進程在進入待調度的隊列等待時，首先進入優先順序最高的Q1等待；

2. 優先調度優先順序高的隊列中的進程。若高優先順序中隊列中已沒有調度的進程，則調度次優先順序隊列中的進程。例如Q1,Q2,Q3三個隊列，只有在Q1中沒有進程等待時才去調度Q2；

3. 對於同一個隊列中的各個進程，按照時間片輪轉法調度。比如Q1隊列的時間片為N，若Q1中的作業在經歷了N個時間片後還沒有完成，則進入Q2隊列等待，若Q2的時間片用完後作業還不能完成，一直進入下一級隊列，直至完成；

4. 在低優先順序的隊列中的進程在運行時，又有新到達的作業，那麼在運行完這個時間片後，CPU馬上分配給新到達的作業（搶佔式）。

其他知識點：

原語是指由若干條指令組成、用來實現某個特定操作的一個過程。原語的執行具有原子性，即原語在執行的過程中不能被分割。

進程間通信方式有直接與間接兩種。直接通信方式是指將發送進程利用OS所提供的發送命令，直接把消息發送給目標進程；間接通信方式是指進程間需要通過某種中間實體（即信箱）來進行通信，發送進程將消息投入，接受進程則從信箱中取得消息。比如管道、消息隊列、共享內存等。

作業調度中，周轉時間是指從進程提交到進程完成的時間間隔，響應時間是指作業等待時間+作業計算時間，運行時間是指作業計算時間。

---

三 內存

邏輯地址與物理地址

邏輯地址（也叫相對地址，虛地址）是程序經過彙編或編譯後形成目標代碼中的地址，其首地址為0，其餘指令中的地址都相對於首地址來編址。

物理地址（也叫絕對地址，實地址）是內存中存儲單元的地址，可用於直接定址。

地址映射（也叫重定位）是將用戶程序中的邏輯地址轉換為運行時由機器直接定址的物理地址。當程序裝入內存時, 操作系統要為該程序分配一個合適的內存空間，由於程序的邏輯地址與分配到內存物理地址不一致, 而CPU執行指令時，是按物理地址進行的，所以要進行地址轉換。

程序裝入的三種方式

程序裝入有絕對裝入、可重定位裝入與動態運行時裝入三種方式。

絕對裝入指直接將程序的符號地址轉換成絕對地址；

可重定位裝入指當用戶程序裝入內存時，由裝入程序一次性完成邏輯地址到物理地址的轉換，以後不再轉換；

動態運行時裝入指重定位不是在裝入時進行，而是將它推遲到程序真正執行時進行。為了不影響指令的執行速度，在系統中增設一個重定位寄存器，用它來存放程序（數據）在內存中的起始地址。程序執行時，真正訪問的內存地址是相對地址與重定位寄存器中的地址相加而成的。

程序鏈接的三種方式

程序鏈接是將編譯後得到的各個目標模塊以及所需的庫函數連接在一起，形成一個完整的裝入模塊，有靜態鏈接，裝入時動態鏈接和運行時動態鏈接三種方式。

靜態鏈接是指在程序運行之前，將各目標模塊及它們所需的庫函數，連接成一個完整的裝入模塊；

裝入時動態鏈接是指鏈接在裝入時進行，即在裝入一個目標時，若發生一個外部模塊的調用事件，則由裝入程序去找出相應的外部模塊，將它裝入內存，並把它鏈接到調用者模塊上；

運行時動態鏈接是指鏈接在運行時進行，即在執行過程中，當發現一個被調用模塊還沒有裝入內存時，立即由os找出該模塊，將它裝入內存，並把它鏈接到調用者模塊上。

內存的連續分配方式

單一連續分配：只能用於單用戶、單任務的操作系統中。把內存分為系統區和用戶區兩部分，系統區僅提供給OS使用，通常是放在內存的低址部分；用戶區是指除系統區以外的全部內存空間，提供給用戶使用。

固定分區分配：最簡單的一種多道程序存儲管理方式，它將用戶內存空間劃分為若干個固定大小的區域，每個分區只裝入一道作業。當有空閑分區時，便可以再從外存的後備作業隊列中選擇適當大小的作業裝入該分區，如此循環。

動態分區分配：又稱為可變分區分配，不預先將內存劃分，而是在進程裝入內存時，根據進程的大小動態地建立分區，並使分區的大小正好適合進程的需要。因此系統中分區的大小和數目是可變的。

可重定位分配：為了解決「外部碎片」的問題，將內存中的所有作業進行移動，從而將分散的多個空閑分區移到同一端拼接成一個大的空閑分區。這種技術稱為「拼接」或「緊湊」。可重定位分區分配方式就是在動態分區分配方式的基礎上增加了緊湊功能。

動態分區分配演算法

首次適應演算法（First Fit）：空閑分區以地址遞增的次序鏈接，分配內存時順序查找，找到大小能滿足要求的第一個空閑分區分配。目的在於盡量減少查找時間。

循環首次適應演算法（Next Fit）：基於首次適應演算法，每次分配從上次分配的位置開始查找。

最佳適應演算法（Best Fit）：空閑分區按容量遞增的次序鏈接，找到第一個能滿足要求的空閑分區（也就是能滿足作業需求的容量最小空閑區）分配。目的在於使碎片盡量小。

最壞適應演算法（Worst Fit）：又稱最大適應(Largest Fit)演算法，空閑分區以容量遞減的次序鏈接，用滿足要求的最大分區分配。目的在於使剩下的空區依然大，減少碎片機會。

關於虛擬內存

虛擬內存是一種內存管理技術，它使得應用程序認為它擁有連續的可用的內存（一個連續完整的地址空間），而實際上是勻出一部分硬碟空間來充當內存使用。

在程序裝入時，不必將其全部讀入到內存，而只需將當前需要執行的部分頁或段讀入到內存，就可讓程序開始執行。在程序執行過程中，如果需執行的指令或訪問的數據尚未在內存（稱為缺頁或缺段），則由處理器通知操作系統將相應的頁或段調入到內存，然後繼續執行程序。內存中暫時不使用的頁或段調出保存在外存上，從而騰出內存空間。

內存的離散分配方式

在存儲器管理中，連續分配方式會形成許多「碎片」，雖然可通過「緊湊」方法將碎片拼接成可用的大塊空間，但須為之付出很大開銷。如果允許將一個進程直接分散地裝入到許多不相鄰的分區中，則無須再進行「緊湊」。

基於這一思想產生了離散分配方式，包括：基本分頁式存儲管理、基本分段式存儲管理、基本段頁存儲管理；請求分頁式存儲管理、請求分段式存儲管理。

如果離散分配的基本單位是頁，則稱為分頁存儲管理方式，如果不具備頁面對換功能，則稱為基本分頁存儲管理方式，或稱為純分頁存儲管理方式。它不具有支持實現虛擬存儲器的功能，它要求把每個作業全部裝入內存後方能運行。請求分頁式存儲管理是在基本分頁存儲管理的基礎上，增加請求調頁和頁面置換功能。

這種方式將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，並為各頁加以編號，從0開始，如第0頁、第1頁等。相應地，也把內存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)，也同樣為它們加以編號，如0#塊、1#塊等等。程序載入時，分配其所需的所有頁，這些頁不必連續。每一個進程會有一個頁表，頁表是描述進程中每個頁面所對應的物理塊。頁表的作用是實現從頁號到物理塊號的地址映射。

若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則：

頁號P = A 整除 L

頁內地址d = A 對 L 取余

另外，對於邏輯地址空間太大的情況可使用二級甚至多級頁表。

如果離散分配的基本單位是段，則稱為分段式存儲管理。同理也分基本分段式存儲管理和請求分段式存儲管理。該方式將程序的地址空間劃分為若干個段(segment)，每個段定義了一組邏輯信息，例如主程序段MAIN、子程序段X、數據段D和棧段S等，每個段都有自己的名字。為了實現簡單起見，通常可用一個段號來代替段名，每個段都從0開始編址，並採用一段連續的地址空間。段的長度由相應的邏輯信息組的長度決定，因而各段長度不等。

在分段式存儲管理系統中，給每個分段分配一個連續的分區，而進程中的各個段可以離散地移入內存中不同的分區中。在系統中為每個進程建立一張段表，段表描述邏輯段與物理內存分區的映射關係，每個段在表中佔有一個表項，其中記錄了該段在內存中的起始地址(基址)和段長度。

段頁式的基本原理是分段和分頁的結合，先將用戶程序分成若干個段，再把每個段分成若干個頁。

分頁與分段對比

分頁和分段都要通過地址映射機構來實現地址變換，其區別主要表現在3個方面：

1. 頁是信息的物理單位，分頁僅僅是由於系統管理的需要；段則是信息的邏輯單位，它含有一組其意義相對完整的信息，分段的目的是為了更好的滿足用戶的需要；

2. 頁的大小固定且由系統決定，由系統把邏輯地址劃分為頁號和頁內地址兩部分，是由機器硬體實現的，因而在系統中只能有一種大小的頁面；而段的長度不固定，決定於用戶所編寫的程序，通常由編譯程序在對源程序進行編譯時，根據信息的性質來劃分；

3. 分頁的作業地址空間是一維的，只需一個記憶符即可表示一個地址；而分段的作業地址空間是二維的，既需給出段名，又需給出段內地址。

頁面置換演算法

最佳置換演算法（OPT）：一種理論上的演算法，其所選擇的被淘汰頁面，將是以後永不使用的，或是在最長(未來)時間內不再被訪問的頁面。

先進先出置換演算法（FIFO）：先進入主存的頁面先淘汰。其理由是最早調入主存的頁面不再被使用的可能性最大。

最近最久未使用置換演算法（LRU）：利用局部性原理，根據一個作業在執行過程中過去的頁面訪問歷史來推測未來的行為。它認為過去一段時間裡不曾被訪問過的頁面，在最近的將來可能也不會再被訪問。

其他知識點：

缺頁率指的是訪問頁面失敗次數除以進程頁面訪問總次數，即

缺頁率 = 缺頁次數 / 總的頁面訪問次數。

在儲存分配過程中產生的、不能供用戶作業使用的主存里的小分區稱為內存碎片，分為內碎片和外碎片。內碎片是已經被分配出去（能明確指出屬於哪個進程）卻不能被利用的內存空間，外碎片是還沒有被分配出去難以利用的空閑分區，通常是小空閑分區。

---

四 文件

關於文件

文件是以計算機硬碟為載體存儲在計算機上的信息集合。在系統運行時，計算機以進程為基本單位進行資源的調度和分配，而在用戶進行的輸入、輸出中，則以文件為基本單位。大多數應用程序的輸入都是通過文件來實現的，其輸出也都保存在文件中，以便信息的長期存及將來的訪問。

文件操作有基本文件操作（創建、刪除、讀、寫、截斷、讀寫指針定位）、打開關閉操作、其他操作（屬性操作與目錄操作）。

文件的邏輯結構從是否有結構來分，可分為有結構文件與無結構文件。無結構文件將數據按順序組織成記錄並積累保存，它是有序相關信息項的集合，以位元組為單位；有結構文件是記錄式文件，按記錄的組織形式來分可分為順序文件、索引文件、索引順序文件。

與文件管理系統相關聯的是文件目錄。目錄在用戶（應用程序）所需要的文件名和文件之間提供一種映射，為實現目錄管理，操作系統中引入了文件控制塊的數據結構。文件控制塊（FCB）是描述和控制文件的數據結構，包含基本信息（文件名、物理位置等）、存取控制信息（各用戶的存取許可權等）、使用信息（上次修改日期等）。

在檢索目錄文件的過程中只用到了文件名，僅當找到一個目錄項（查找文件名與目錄項中文件名匹配）時，才需要從該目錄項中讀出該文件的物理地址。也就是說，在檢索目錄時，文件的其他描述信息不會用到，也不需調入內存。因此，有的系統（如UNIX）釆用了文件名和文件描述信息分開的方法，文件描述信息單獨形成一個稱為索引結點的數據結構，簡稱為 i 結點。在文件目錄中的每個目錄項僅由文件名和指向該文件所對應的i結點的指針構成。每個索引節點保存了文件系統中的一個文件系統對象的元信息數據，但不包括數據內容或者文件名。

文件共享的硬鏈接與軟鏈接

文件共享使多個用戶（進程）共享同一份文件，系統中只需保留該文件的一份副本。常用的方法有基於索引結點的共享方式（硬鏈接）與利用符號鏈實現文件共享（軟鏈接）。

在硬鏈接里，諸如文件的物理地址及其他的文件屬性等信息，不是放在目錄項中而是放在索引結點中。在文件目錄中只設置文件名及指向相應索引結點的指針。在索引結點中還應有一個鏈接計數count,用於表示鏈接到本索引結點（亦即文件）上的用戶目錄項的數目。當用戶A創建一個新文件時，它便是該文件的所有者，此時將count置為1。當有用戶 B要共享此文件時，在用戶B的目錄中增加一個目錄項，並設置一指針指向該文件的索引結點。此時，文件主仍然是用戶A，count=2。如果用戶A不再需要此文件，不能將文件直接刪除，只是將該文件的count減1，然後刪除自己目錄中的相應目錄項。當count=0時，表示沒有用戶使用該文件，系統將負責刪除該文件。

在軟鏈接里，為使用戶B能共享用戶A的一個文件F,可以由系統創建一個LINK類型的新文件，也取名為F，並將文件F寫入用戶B的目錄中。新文件中只包含被鏈接文件F的路徑名，路徑名被看做是符號鏈。讀共享文件時，需要根據文件路徑名逐個地查找目錄，直至找到該文件的索引結點。在利用符號鏈方式實現文件共享時，只有文件的擁有者才擁有指向其索引結點的指針，共享該文件的其他用戶則只有該文件的路徑名。當文件的擁有者把一個共享文件刪除後，其他用戶通過符號鏈去訪問它時，會出現訪問失敗。

文件的分配方式

文件分配對應於文件的物理結構，是指如何為文件分配磁碟塊。常用的磁碟空間分配方法有三種：連續分配、鏈接分配和索引分配。

連續分配方法要求每個文件在磁碟上佔有一組連續的塊，可以用第一塊的磁碟地址和連續塊的數量來定義。其優點是實現簡單、存取速度快，缺點在於文件長度不宜動態增加。

鏈接分配釆取離散分配的方式，當文件動態增長時可以動態地再為它分配盤塊，對文件的增、刪、改也非常方便。鏈接分配又分為隱式鏈接和顯式鏈接兩種形式。

隱式鏈接每個文件對應一個磁碟塊的鏈表，除最後一個盤塊外，每一個盤塊都有指向下一個盤塊的指針。目錄包括文件第一塊的指針和最後一塊的指針。創建新文件時，目錄中增加一個新條目，每個目錄項都有一個指向文件首塊的指針。隱式鏈接分配的缺點在於無法直接訪問盤塊，只能通過指針順序訪問文件，以及盤塊指針消耗了一定的存儲空間。

顯式鏈接是指把用於鏈接文件各物理塊的指針，顯式地存放在內存一張鏈接表中。由於分配給文件的所有盤塊號都放在該表中，故稱該表為文件分配表（FAT)。每個表項中存放鏈接指針，即下一個盤塊號。在該表中凡是屬於某一文件的第一個盤塊號，或者說是每一條鏈的鏈首指針所對應的盤塊號，均作為文件地址被填入相應文件的FCB的「物理地址」欄位中。由於查找記錄的過程是在內存中進行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁碟的次數。

索引分配把每個文件的所有的盤塊號都集中放在一起構成索引塊（表），每個文件都有其索引塊，這是一個磁碟塊地址的數組。目錄條目包括索引塊的地址。索引塊的第i個條目指向文件的第i個塊，當首次寫入第i塊時，先從空閑空間中取得一個塊，再將其地址寫到索引塊的第i個條目。索引分配支持直接訪問，且沒有外部碎片問題。另外可以設計多層索引與混合索引。

文件存儲空間管理

文件存儲設備分成許多大小相同的物理塊，並以塊為單位交換信息，文件存儲設備的管理實質上是對空閑塊的組織和管理，包括組織、分配與回收等問題。

空閑表法：屬於連續分配方式，它與內存的動態分配方式類似，為每個文件分配一塊連續的存儲空間。為所有空閑區建立一張空閑盤塊表，每個空閑區對應於一個空閑表項，其中包括表項序號、該空閑區第一個盤塊號、該區的空閑盤塊數等信息。再將所有空閑區按其起始盤塊號遞增的次序排列。空閑盤區的分配與內存的動態分配類似，同樣是釆用首次適應演算法、循環首次適應演算法等。系統在對用戶所釋放的存儲空間進行回收時，也釆取類似於內存回收的方法，即要考慮回收區是否與空閑表中插入點的前區和後區相鄰接，對相鄰接者應予以合併。

空閑鏈表法：將所有空閑盤區拉成一條空閑鏈，根據構成鏈所用的基本元素不同，可把鏈表分成空閑盤塊鏈和空閑盤區鏈。空閑盤塊鏈是將磁碟上的所有空閑空間，以盤塊為單位拉成一條鏈。當用戶因創建文件而請求分配存儲空間時，系統從鏈首開始，依次摘下適當的數目的空閑盤塊分配給用戶。當用戶因刪除文件而釋放存儲空間時，系統將回收的盤塊依次插入空閑盤塊鏈的末尾；空閑盤區鏈是將磁碟上的所有空閑盤區（每個盤區可包含若干個盤塊）拉成一條鏈，在每個盤區上除含有用於指示下一個空閑盤區的指針外，還應有能指明本盤區大小（盤塊數）的信息。分配盤區的方法與內存的動態分區分配類似，通常釆用首次適應演算法。在回收盤區時，同樣也要將回收區與相鄰接的空閑盤區相合併。

位示圖法：用二進位一位來表示磁碟中一個盤塊的使用情況。所有的盤塊都有一個二進位位與之對應，0表示空閑，1表示已分配。

盤塊的分配分三步：順序掃描位示圖，找到一個或一組值為「0」的位；將找到的位轉換成與之相對應的盤塊號：b=n(i-1)+j；修改位示圖。

盤塊的回收分兩步：將回收的盤塊號轉換成位示圖中的行號和列號；修改位示圖。

i=(b-1) DIV n +1 j=(b-1) MOD n +1

位示圖優點是很容易找到一個或一組相鄰接的空閑盤塊，且佔用空間小，可常駐內存。

成組鏈接法：在UNIX系統中釆用的是成組鏈接法，把順序的n個空閑扇區地址保存在第一個空閑扇區內，其後一個空閑扇區內則保存另一順序空閑扇區的地址，如此繼續，直至所有空閑扇區均予以鏈接。通過這種方式可以迅速找到大批空閑塊地址。

---

五 I/O

I/O設備分類

按使用特性分類，可分為存儲設備與輸入/輸出設備（可細分為輸入設備、輸出設備和互動式設備，如鍵盤，滑鼠，掃描儀，印表機，顯示器等。）

按傳輸速率分類，可分為低速設備（如鍵盤、滑鼠等）、中速設備（如行式印表機、激光印表機等）、高速設備（如磁帶機、磁碟機、光碟機等。）

按信息交換的單位分類，可分為塊設備（信息以數據塊為單位，如磁碟，每個盤塊512B~4KB，傳輸速率較高，另一特徵是可定址，即對它可隨機地讀/寫任一塊）與字元設備（其基本單位是字元，屬於無結構類型，如印表機等，其傳輸速率較低，不可定址，常採用中斷驅動方式。）

按設備的共享屬性分類，可分為獨佔設備，共享設備，虛擬設備（通過虛擬技術將一台設備變換為若干台邏輯設備，供若干個用戶（進程）同時使用。）

關於設備控制器

設備控制器是計算機中的一個實體，其主要職責是控制一個或多個I/O設備，以實現I/O設備和計算機之間的數據交換。它是CPU與I/O設備之間的介面，它接收從CPU發來的命令，並去控制I/O設備工作。其是一個可編址的設備，當它僅控制一個設備時，它只有一個唯一的設備地址，若控制器可連接多個設備時，則應該含有多個設備地址，並使每個設備地址對應一個設備。

由於設備控制器位於CPU與設備之間，既要與CPU通信，又要與設備通信，還應具有按照CPU所發來的命令去控制設備工作的功能，因此，現有的大多數控制器都是由如下的三部分組成：

1. 設備控制器與處理機的介面，共有三類信號線：數據線、地址線、控制線，數據線與兩類寄存器相連接，第一類是數據寄存器，第二類是控制/狀態寄存器。

2. 設備控制器與設備的介面，設備控制器可以連接一個或多個設備，相應地，在控制器中便有一個或多個設備介面，一個介面連接一台設備，在每個介面中都存在數據、控制和狀態三種類型的信號，控制器中的I/O邏輯根據處理機發來的地址信號去選擇一個設備介面。

3. I/O邏輯，用於實現對設備的控制，通過一組控制線與處理機交互，每當CPU要啟動一個設備時，一方面將啟動命令發送給控制器，另一方面又同時通過地址線把地址發送給控制器，由控制器的I/O邏輯對收到的地址進行解碼，再根據所譯出的命令對所選設備進行控制。

I/O控制方式

設備管理的主要任務之一是控制設備和內存或CPU之間的數據傳送，常用控制方式有4種：程序I/O控制，中斷驅動I/O控制，直接存儲器訪問（DMA）I/O控制和通道I/O控制。原則是盡量減少主機對I/O控制的干預。

程序I/O控制：由用戶進程來直接控制。CPU首先向設備控制器的控制寄存器發出一條I/O指令，硬體同時把狀態寄存器中的忙/閑標誌busy置為1，表示該I/O設備尚未輸入完一個字(符)。接著CPU應重複讀取狀態寄存器忙/閑標誌busy進行測試（cpu不能執行其他進程），直至busy=0，表示該I/O設備已將輸入數據送入到I/O控制器的數據寄存器中，於是CPU取出數據送入內存。然後再啟動去讀下一個數據並置busy=1。由於CPU的速度遠遠高於I/O設備，會造成CPU浪費。

中斷驅動I/O控制：當某進程要啟動某個I/O設備時，便由CPU向相應的設備控制器的控制寄存器發出一條I/O命令，然後立即返回繼續執行原來的任務。設備控制器按照該命令的要求去控制I/O設備，若I/O設備忙，則由驅動程序將請求插入設備等待隊列。此時，CPU與I/O設備處於並行工作狀態。一旦數據進入數據寄存器，控制器便通過中斷請求線INT向CPU發送一中斷信號，中斷子程序由CPU讀取狀態寄存器忙/閑標誌busy進行測試檢查輸入過程中是否出錯，若無錯，便從數據寄存器中讀出數據，寫入指定內存單元。

直接存儲器訪問（DMA）I/O控制：中斷控制每完成一個字（節）的傳送便要向CPU請求一次中斷，為進一步減少CPU對I/O的干預，引入了直接存儲器訪問DMA控制方式。DMA方式是一種完全由硬體執行I/O數據交換的工作方式，它需要使用一個專門的DMA控制器（DMAC），內含於設備控制器。DMAC中有控制狀態寄存器、傳送位元組計數器、內存地址寄存器和數據緩衝寄存器。數據傳輸的基本單位是數據塊，成批的數據交換不經過CPU而直接在內存和I/O設備之間進行，僅在傳送一個或多個數據塊的開始和結束時才需CPU干預。

通道I/O控制：由於DMA每次只能執行一條I/O指令，不能滿足複雜的I/O操作要求，在大、中型計算機系統中普遍採用通道技術。通道是一個獨立於CPU的專管輸入輸出控制的處理機，它控制設備與內存直接進行數據交換。它有自己的通道指令，這些通道指令受CPU啟動，並在操作結束時向CPU發中斷信號。通道技術可以把對一個數據塊為單位的讀（或寫）的干預，減少到對一組數據塊為單位的讀（或寫）的有關的控制和管理的干預，實現 CPU、通道和I/O設備三者之間的並行工作，更有效地提高了整個系統的資源利用率和運行速度。

緩衝管理

在設備管理中，為了緩和CPU與I/O設備速度不匹配的矛盾，提高CPU與I/O設備的並行性，在I/O設備與處理機交換數據時都用到了緩衝區。

單緩衝：每當用戶進程發出一個I/O請求時，操作系統便在主存中為之分配一個緩衝區，假定從磁碟把一塊數據輸入到緩衝區的時間為T，操作系統將該緩衝區中的數據傳送到用戶區的時間為M，而CPU對這一塊數據處理（計算）的時間為C，由於T和C是可以並行的，系統對每一塊數據的處理時間為Max(C，T) + M。在字元設備輸入時，緩衝區用於暫存用戶輸入的一行數據，在輸入期間用戶進程被掛起以等待數據輸入完畢，在輸出時，用戶進程將一行數據輸入到緩衝區後，繼續進行處理，當用戶進程已有第二行數據輸出時，如果第一行數據尚未被提取完畢，則此時用戶進程應該阻塞。

雙緩衝：雙緩衝區機制又稱為緩衝對換。在設備輸入時，先將數據送入第一個緩衝區，裝滿後便轉向第二個緩衝區，此時操作系統可以從第一緩衝區中移出數據，並送入用戶進程，接著由CPU對數據進行計算。在雙緩衝時，系統處理一塊數據的時間可以粗略地認為是Max(C，T)，如果C<T，可使塊設備連續輸入，如果C>T，則可使CPU不必等待設備輸入。

循環緩衝：當輸入與輸出或生產者與消費者的速度基本相匹配時，採用雙緩衝能獲得較好的效果，但若兩者速度相差甚遠，雙緩衝的效果則不夠理想，因此，引入了多緩衝機制，可將多個緩衝組織成循環緩衝形式。輸入進程不斷向空緩衝去輸入數據，而計算進程則從中提取數據進行計算。

循環緩衝區的組成包括：

多個緩衝區，在循環緩衝區中包括多個緩衝區，每個緩衝區的大小相同，作為輸入的多緩衝區可分為三種類型，用於裝輸入數據的空緩衝區R、已裝滿數據的緩衝區G以及計算進程正在使用的先行工作緩衝區C；

多個指針，作為輸入的緩衝區可設置三個指針，用於指示計算進程下一個可用緩衝區G的指針Nextg、指示輸入進程下次可用的空緩衝區R的指針Nexti、以及用於指示計算進程正在使用的緩衝區C的指針Current。

緩衝池：上述的緩衝區僅適用於某特定的I/O進程和計算進程，因而它們屬於專用緩衝，當系統較大時，將會有許多這樣的循環緩衝，這樣會消耗大量的內存空間，而且利用率不高，為了提高緩衝區的利用率，引入緩衝池，在池中設置了多個可供若干個進程共享的緩衝區。

對於既可以用於輸出的共用緩衝池，其中至少包含有一下三種類型的緩衝區：空（閑）緩衝區、裝滿輸入數據的緩衝區、裝滿輸出數據的緩衝區。為了管理方便，將相同類型的緩衝區鏈成一個隊列，形成了空緩衝隊列emq、輸入隊列inq、輸出隊列outq。還具有四種工作緩衝區，用於收容輸入數據的工作緩衝區、用於提取輸入數據的工作緩衝區、用於收容輸出數據的工作緩衝區、用於提取輸出數據的工作緩衝區。

磁碟與磁碟調度演算法

磁碟是由表面塗有磁性物質的金屬或塑料構成的圓形碟片，通過一個稱為磁頭的導體線圈從磁碟中存取數據。在讀/寫操作期間，磁頭固定，磁碟在下面高速旋轉。磁碟的盤面上的數據存儲在一組同心圓中，稱為磁軌。每個磁軌與磁頭一樣寬, 一個盤面有上千個磁軌。磁軌又劃分為幾百個扇區，每個扇區固定存儲大小（通常為512B),

一個扇區稱為一個盤塊。相鄰磁軌及相鄰扇區間通過一定的間隙分隔開，以避免精度錯誤。由於扇區按固定圓心角度劃分，所以密度從最外道向里道增加，磁碟的存儲能力受限於最內道的最大記錄密度。

常見的磁碟調度演算法有：

先來先服務演算法（FCFS）：根據進程請求訪問磁碟的先後次序進行調度。

最短尋道時間優先演算法（SSTF）：選擇要求訪問的磁軌與當前磁頭所在的磁軌距離最近的進程（磁碟請求），使每次的尋道時間最短。

掃描演算法（Scan）：又稱電梯調度演算法，磁頭每次只作單方向移動，直到到達邊緣磁軌為止，然後再作反向移動。

循環掃描演算法（CScan）：磁頭只作由內向外的單方向掃描，到達外邊緣後，則返回最內側的磁軌重新進行下一輪掃描。

其他知識點：

尋道時間是指把磁臂（磁頭）移動到指定磁軌上所經歷的時間，包含啟動磁臂和磁頭移動n條磁軌所花費的時間。

（2017年12月19日更新）

推薦閱讀：