緒論

作業系統的定義

作業系統是管理計算機系統的全部硬體資源zhi包括軟體資源及資料資源；控制程式運行；改善人機界面；為其它應用軟體提供支持等，使計算機系統所有資源最大限度地發揮作用，為用戶提供方便的、有效的、友善的服務界面，

作業系統的特征

1、并發性
2、共享性
3、虛擬性
4、不確定性

作業系統的功能

1、處理機管理
2、檔案管理
3、存盤管理
4、設備管理
5、作業管理

作業系統的分類

1、批處理作業系統
2、分時作業系統
3、實時作業系統
4、網路作業系統
5、分布式作業系統
6、微機作業系統
7、嵌入式作業系統

硬體

處理機的狀態及分類

作業系統，至少需要區分兩種狀態:管態和用戶態，

管態(uperitor Mode )

又稱為系統態，是作業系統的管理程式執行時機器所處的狀態，在此
狀態下中央處理機可以使用全部機器指令，包括組特權指令 (例如，涉及外部設備的輸入輸出指令、改變機器狀態或修改存盤保護的指令), 可以使用所有的資源，允許訪問整個存盤區，
有的系統還將管理程式執行時的機器狀態進一步分為核態和管態，

核態( Kemel Mode )

就具有上述管態所具有的所有權限，

管態

管態的權限有所變化，管態允許使用些在用戶態 下所不能使用的資源，但不能使用修改機器的狀態指令，而無核態的系統，管態執行核態的全部功能，管志比核態權限要低，用戶態更低，

用戶態(User Mode)

:又稱為目態，是用戶程式執行時機器所處的狀態，在此狀態下禁止使用特權指令，不能直接取用資源與改變機器狀態，并且只允許用戶程式訪問自己的存盤區域，

指令分類

特權指令

是指有特權權限的指令，由于這類指令的權限最大，如果使用不當，將導致整個系統崩潰，比如：清記憶體、置時鐘、分配系統資源、修改虛存的段表和頁表，修改用戶的訪問權限等，
為了保證系統安全，這類指令只能用于作業系統或其他系統軟體，不直接提供給用戶使用，因此，特權執行必須在核心態執行，

非特權指令

為了防止用戶程式中使用特權指令，用戶態下只能使用非特權指令，核心態下可以使用全部指令，當在用戶態下使用特權指令時，將產生中斷以阻止用戶使用特權指令，所以把用戶程式放在用戶態下運行，而作業系統中必須使用 特權指令的那部分程式在核心態下運行，保證了計算機系統的安全可靠，從用戶態轉換為核心態的唯一途徑是中斷或例外，

中斷的定義

中斷是指程式執行程序中，遇到急需處理的事件時，暫時中止CPU上現行程式的運行，轉去執行相應的事件處理程式，待處理完成后再回傳原程式被中斷處或調度其他程式執行的程序

用戶介面

用戶介面的定義及分類

定義

作業系統的用戶介面是作業系統提供給用戶與計算機打交道的外部機制，用戶能夠借助這種機制和系統提供的手段來控制用戶所在的系統，

分類

操作介面

用戶通過這個操作介面來組織自己的 作業流程和控制程式的運行;

程式介面

任何個用戶程式在其運行程序中， 可以使用作業系統提供的功能呼叫來請求作業系統的服務(如申請主存、使用各種外設、創建行程或執行緒等)不論哪類作業系統都必須同時提供操作介面和程式介面，

系統呼叫的定義及實作

定義

在計算機中，系統呼叫（英語：system call），又稱為系統呼叫，指運行在使用者空間的程式向作業系統內核請求需要更高權限運行的服務，系統呼叫提供了用戶程式與作業系統之間的介面（即系統呼叫是用戶程式和內核互動的介面），
通俗來說
就是應用程式有時會需要一些危險的、權限很高的指令，如果把這些權限放心地交給用戶程式是很危險的(比如一個行程可能修改另一個行程的記憶體區，導致其不能運行)，但是又不能完全不給這些權限，于是有了系統呼叫，危險的指令被包裝成系統呼叫，用戶程式只能呼叫而無權自己運行那些危險的指令，

實作

為了實作系統呼叫，作業系統設計者必須完成的作業如下，
①撰寫并除錯好能實作各種功能的例行子程式，如sub.、 sb. … sb. … subo
②撰寫并除錯好訪管中斷處理程式，其功能是:做常規的現場保護后，取i值，然后安排條
轉移指令，按A +i單元中的內容轉移，
③構造例行子程式入口地址表，假定該表首址為4,每個例行子程式的入口地址占1個字長，
將各例行子程式的入口地址#subo、#subj、 … #subj、 . #subm(即ao、 21、 . a… am)分別
送入A+0、A+1、… A+i、… A+m單元中，
在用戶程式中，需要請求作業系統服務的地方安排一條系統呼叫，這樣，當程式執行到這一-條命令時，就會發生中斷，系統由用戶態轉為管態，作業系統的訪管中斷處理程式得到控制權，它將按系統呼叫的功能號，借助例行子程式入口地址表轉到相應的例行程式去執行，在完成了用戶所需要的服務功能后，退出中斷，回傳到用戶程式的斷點繼續執行，

行程管理、調度

行程的定義

所謂行程就是一個程式在給定的活動空間和初始環境下，在一個處理機上的執行程序
1)行程是并發程式的一次執行程序
2)行程是一個具有一定獨立功能的程式關于某個資料集合的一次運行活動

行程的組成

行程物體由三部分構成：由程式段、資料段、行程控制塊PCB

行程的狀態以及之間的轉換

1)就緒態->運行態 2)運行態->就緒態 3)運行態->阻塞態 4)阻塞態->就緒態

行程控制塊的作用

1)每個行程有唯一的PCB，
2)作業系統根據PCB對行程實施控制和管理，
3)行程的動態、并發等特征是利用PCB表現出來的，
4)PCB是行程存在的唯一標志，

行程控制由什么來實作: 有哪些原語

(1)行程控制原語:對行程的行為進行控制

(2)最基本的行程控制原語：行程建立、行程調度、行程等待、行程喚醒、行程撤消

(3)行程建立中, 父行程在呼叫創建原語之前必須準備的引數：行程識別符號、行程優先級以及行程程式的起始地址

互斥、同步的概念

同步

是行程間共同完成一項任務時直接發生相互作用的關系(行程之間的一種協調配合關系)

互斥

若干行程競爭進入臨界段時，相互之間所形成的排它性關系(從廣義上講它也屬于同步關系的范疇)

臨界資源和臨界區

臨界資源（critical resource）：是一次只能被一個行程使用的資源
臨界段/臨界區(critical section)：是使用臨界資源的程式段

采用信號量和wait,signal原語來實作行程的互斥和同步

示例

原語，wait,signal原語的物理意義

原語

執行程序中不可中斷的、實作某種獨立功能的、可被其他程式呼叫的程式

wait,signal原語的物理意義

一個信號量通常對應一類臨界資源，在使用前，信號量必須經過定義并賦適當的初值，
每次對它進行wait操作意味著申請一個單位的該資源，signal操作操作意味著歸還一個單位的該類資源，當S.value>0時，它的值表示系統中該類資源當前可用的數目；S.value<=0時，表示該類資源已經分配完畢，其絕對值表示系統中因申請資源而阻塞在S.L佇列上的行程數目

行程的通信方式

訊息通信

(1)行程間的資料交換以訊息為單位

(2)用戶直接利用系統中提供的一組通信命令（原語）進行通信

(3)訊息msg通常由訊息頭和訊息正文構成：

1)訊息頭

msgsender訊息發送者

msgreceiver訊息接收者

msgnext下一個訊息的鏈指標

msgsize整個訊息的位元組數

2)訊息正文

msgtext訊息正文

(4)訊息通信分類：

1)直接通信方式

2)間接通信方式

發送行程使用發送原語直接將訊息發送到某種中間物體（郵箱）中，接收行程使用接收原語從該中間物體中取出訊息,也稱為郵箱通信

管道

(1)在兩個行程的執行程序中，如果一個行程的輸出是另一個行程的輸入，可以使用管道檔案

(2)在Linux系統中，使用符號“|”來表示已建立管道檔案

(3)管道通信

輸入行程：從行程A的輸出區讀資料，寫入管道檔案

管道檔案；這是一個臨時檔案，輸入行程向它寫資訊，輸出行程從它讀資訊

輸出行程：將管道檔案的資料讀出，寫入行程B的輸入區

(4)管道通信的關系

互斥關系——輸出和輸入行程不可能同時讀或者寫

同步關系——當管道檔案為空時，輸出行程等待輸入行程

        當管道檔案為滿時，輸入行程等待輸出行程

(4)管道:是資料流，它既可以是單向的，也可以是兩個行程間雙向的,又被分為匿名管道和命名管道

2.5.3Windows中的行程通信
郵件位——是單向機制，一個行程留下訊息，等待另一個行程接收
對郵件位的操作：
創建郵件位CreateMailslot()
讀取郵件位資訊GetMailslotInfo()
改變郵件位資訊SetMailslotInfo()
對于郵件位中的資料，windows是通過對檔案的操作來實作資料的讀寫的

執行緒的定義，與行程的區別

執行緒

行程中的邏輯小塊，它具有掛起自身和被掛起的能力，因此執行緒的狀態是可以變化的

行程和執行緒的區別和聯系

1)行程是擁有應用程式所有資源的物件

2)執行緒是行程中一個獨立的執行路徑

3)一個行程至少要有一個執行緒，這個執行緒被叫做主執行緒

4)一個行程的執行緒越多，該行程獲得的CPU時間就越多，行程的運行時間就越快

5)所有執行緒參與對CPU時間片的競爭

6)執行緒運行時共享其對應行程所擁有的資源

處理機調度的層次：宏觀調度（作業調度）、中級調度（掛起與解掛）、微觀調度（行程調度）

.高級調度

也稱為作業調度，作業是比程式更廣泛的概念，作業不僅包含了程式與資料，還包含了對程式的控制說明；作業是用戶向計算機提交任務的任務物體，一個作業可由多個行程組成，而行程只是執行任務的物體，

. 低級調度

也稱為行程調度，行程調度是用于決定把處理機分配給哪個就緒佇列里面的行程或者說內核級執行緒，行程調度有兩種方式：一種是非搶占式，一種是搶占式，非搶占式要等行程運行完才把處理器分配給別的行程；而搶占式則是根據某種規則去暫停正在執行的行程，將處理器分配給另一個行程，

.中級調度

會把暫時不能運行的行程調到外存上去等待，等具備條件時再重新調入記憶體，

調度演算法（先來先服務、最短作業優先，最高優先比演算法，最高優先級優先演算法…，如何計算各種演算法下的平均周轉時間、帶權周轉時間等

死鎖的定義、產生的根本原因和必要條件

死鎖: 是若干行程都無知地等待對方釋放資源而處于無休止的等待狀態

產生死鎖的根本原因：資源有限且操作不當，

死鎖發生的必要條件

(1)死鎖產生的必要條件：資源的互斥使用,資源不可搶占,資源的部分分配,回圈等待

預防死鎖的方法，死鎖的避免，死鎖的檢測與解除

死鎖的檢測

如果資源分配圖中沒有環路，則系統中沒有死鎖，如果圖中存在環路則系統中可能存在死鎖，
如果每個資源類中只包含一個資源實體，則環路是死鎖存在的充分必要條件，

死鎖的解除

撤消所有的死鎖行程
連續撤消死鎖行程直至不再存在死鎖
連續剝奪資源直到不再存在死鎖
把每個死鎖行程備份到前面定義的某個檢查點，并重新啟動所有行程

預防死鎖的方法

預防死鎖的策略：資源預先分配策略、資源有序分配策略，

1)資源預先分配策略：打破占有且申請條件，行程在運行前一次性地向系統申請它所需要的全部資源，如果所序言的全部資源得不到滿足，則不分配任何資源，此行程暫不運行，

2)資源有序分配策略(序列號升序或減序)：打破回圈等待條件，把資源事先分類編號，按序分配，使行程在申請、占用資源時不會形成環路.

主存管理

磁區分配演算法：最先適應演算法（空閑磁區地址遞增排序）、最佳適應演算法（空閑磁區大小遞增排序）、最壞適應演算法（空閑磁區大小遞減排序）

（1）.首次適應演算法（first fit，FF）

：

要求，空閑磁區鏈以地址遞增的順序鏈接，每次從鏈首開始，直到找到第一個能滿足要求的空閑磁區為止，
簡單來說，就是，每次都從第一個開始順序查找，找到一塊區域可以滿足要求的，
優點：優先利用記憶體中低址部分的空閑磁區，從而保留了高址部分的大空閑區，這為以后到達的大作業分配大的記憶體空間創造了條件，
缺點：低址部分不斷被劃分，會留下許多難以利用的，很小的空閑磁區，稱為碎片，而每次查找又都是從低址部分開始的，這無疑又會增加查找可用空閑磁區時的開銷，

（2）.回圈首次適應演算法（next fit，NF）

與FF演算法區別就是，不是每次都從首次開始，而是從上次找到的空閑磁區的下一個空閑磁區開始，（第一次查找的話也是從首頁開始），
特點：能使記憶體中的空閑區分布得較均勻，

(3）.最佳適應演算法（best，BF）

將所有空閑磁區按照空閑磁區容量大小從小到大的順序連接起來，形成一個空閑磁區鏈，
即，每次都是找空間容量不但可以滿足要求的空閑區，而且該空閑磁區的容量還要最接近要求的容量大小，
優點：每次分配給檔案的都是最合適該檔案大小的磁區，
缺點：記憶體中留下許多難以利用的小的空閑區（外碎片），

(4).最壞適應演算法（worst，WF）

與BF演算法相反，WF演算法是按照空閑磁區容量從大到小的順序連接起來的，而且每次找空閑磁區的時候也是按照空閑磁區容量最大的，
特點：盡可能的分配大的磁區，
缺點：使得記憶體缺乏大磁區，可能使得后續到來的大作業無法裝入記憶體，

頁式管理的原理、地址結構、地址轉換 訪問資料或者指令至少訪問2次記憶體

原理

1）用戶的邏輯地址空間分頁：把用戶的邏輯地址空間劃分成若干個長度相等的頁（page,虛頁），并對其頁從0開始進行編號：0，1，2…，
2）等分主存：把主存按頁的大小劃分成存盤塊，稱為頁面(page frame，物理塊，實頁) ，它的大小對特定計算機系統而言是固定的；并給各實頁從0開始編號：0，1，…,n ，
3）邏輯地址的表示：每個邏輯地址用一個數對（p，d）來表示，p是頁號，d是該虛擬地址在頁p內的相對地址，稱為頁內地址或偏移量，

地址結構

地址轉換

將由邏輯頁號和頁內相對地址變換到記憶體物理地址，只能采取動態重定位，
由硬體地址變換機構自動完成，
將邏輯地址中的頁號與頁表地址暫存器中的頁表長度比較
如頁號超過頁表長度，則產生越界中斷
否則，根據頁表起始地址與頁號計算該頁對應頁表項的位置，從中讀出頁對應的記憶體的塊號將塊號和頁內地址組合得到物理地址
物理地址=記憶體塊號*塊長+頁內地址

段式管理的原理、地址結構、地址轉換訪問資料或者指令至少訪問2次記憶體

原理

頁式管理是把記憶體視為一維線性空間；而段式管理是把記憶體視為二維空間，與行程邏輯相一致，
把程式的地址空間按內容或程序（函式）關系分成段，每段有自己的名字；
系統按段分配記憶體空間，一個行程的各段在記憶體中可以是不連續的；
程式的虛擬地址用段名和段內地址來描述，是一個二維地址；
指令地址場中的虛擬地址用段號和段內地址來描述，為實作記憶體分配和地址變換，必須設定段表和段表地址暫存器，
物理記憶體的管理采用動態磁區，需要CPU的硬體支持，

地址結構

地址轉換

段式和頁式的區別

頁式和段式管理都提供了內外存統一管理的虛存實作，但分頁是出于系統管理的需要，分段是出于用戶應用的需要

一條指令或一個運算元可能會跨越兩個頁的分界處，而不會跨越兩個段的分界處，

頁式虛存只交換固定大小的頁，需要多次缺頁中斷才能把所需資訊完整地調入記憶體，而段式虛存每次交換得到是一段有意義的資訊，無法通過頁面共享具有完整邏輯功能的子程式或資料塊，而段則可以，

虛擬存盤器的定義、理論基礎和容量以及實作的方法

定義

所謂虛擬存盤器，是指僅把作業的一部分裝入記憶體便可以運行作業的存盤器系統，虛擬存盤器具有請求調入功能和置換功能，能從邏輯上對記憶體容量進行擴充，實際上，用戶看到的大容量只是一種感覺，是虛擬的，故而得名虛擬存盤器，其邏輯容量由記憶體和外存容量之和所決定，其運行速度接近于記憶體速度，而其成本卻接近于外存，可見，虛擬存盤技術是一種性能非常優越的存盤器管理技術，故被廣泛應用于大、中、小型計算機和微型機中，

.虛擬存盤器的實作方法

虛擬存盤器的實作都是建立在離散分配存盤管理方式的基礎上，目前的實作方法主要有以下兩種，

(1)請求分頁系統

請求分頁系統是在分頁存盤管理方式的基礎上增加了請求調頁功能、頁面置換功能所形成的頁式虛擬存盤系統，程式啟動運行時裝入部分用戶程式頁和資料頁，在以后的運行程序中，訪問到其他邏輯頁時，冉陸續將所需的頁調入記憶體，請求調頁和置換時，需要頁表機構、缺頁中斷機構、地址變換機構等軟硬體支持，

(2)請求分段系統

請求分段系統是在分段存盤管理方式的基礎上增加了請求調段及分段置換功能而形成的段式虛擬存盤系統，只需裝入部分程式和資料行程即可啟動運行，以后出現缺段時再動態調入，實作請求分段同樣需要請求分段的段表機制、缺段中斷機構、地址變換機構等軟硬體支持，

頁面置換演算法（最近最久未使用演算法、先進先出、理想置換演算法）

最近最久未使用演算法

先進先出

理想置換演算法

段頁式管理的基本原理：訪問資料或者指令至少訪問3次記憶體，

在段頁式系統中，為了獲得一條指令或資料，須三次訪問記憶體，第一次訪問是訪問記憶體中的段表，從中取得頁表始址；第二次訪問是訪問記憶體中的頁表，從中取出該頁所在的物理塊號，并將該塊號與頁內地址一起形成指令或資料的物理地址；第三次訪問才是真正從第二次訪問所得的地址中，取出指令或資料，

設備管理

I/O設備的型別

（1）按設備的功能特性分
存盤型設備
輸入輸出型設備（互動型設備）
資料通信設備
（2）按傳輸速率分類
低速設備：幾~數百 B/S，鍵盤，滑鼠、語音的I/O設備；
中速設備：數千~數十萬B/S ，列印機；
高速設備：數百KB~千MB/S ，磁帶機、磁盤機、光碟等，
（3）按設備的資訊組織方式分
字符設備：以字符為單位組織和處理資訊的設備：鍵盤、終端、列印機；傳輸速率較低，不可尋址, 在I/O時，常采用中斷驅動方式，
塊設備：以字符塊為單位組織處理資訊的設備：磁盤、磁帶，屬于有結構設備，其傳輸速率較高，可尋址，即對它可隨機地讀/寫任一塊；I/O常采用DMA方式，
（4）按設備資源的分配角度分為：獨占設備、共享設備和虛擬設備，
獨占設備： 在一段時間內只能由一個行程使用的設備，一般為低速I/O設備，靜態分配，
共享設備： 在一段時間內可有多個行程共同使用的設備，多個行程以交叉的方式來使用設備，其資源利用率高，
如硬碟的使用，在作業執行程序中，需要使用磁盤時，才會把磁盤分配給作業使用，I/O對磁盤的分配實際上就是決定某一時刻為誰服務的問題，即驅動調度問題
虛擬設備：在一類設備上模擬另一類設備，常用共享設備模擬獨占設備，用高速設備模擬低速設備，被模擬的設備稱為虛擬設備，
目的：將慢速的獨占設備改造成多個用戶可共享的設備，提高設備的利用率，
（5） 按設備的從屬關系分類：
系統設備：在OS生成時就已配置好的各種標準設備：鍵盤、存盤設備等；
用戶設備：在系統生成時沒有配置，由用戶自己安裝配置后由OS統一管理的設備：網卡、實時系統中的A/D、D/A轉換器，

I/O控制方式：程式輪詢 中斷 DMA 通道

程式輪詢

在早期的計算機中，由于無中斷機構，處理機對I/O設備的控制采用程式直接控制方式，或稱為忙-等待方式，

計算機從外部設備讀取資料到存盤器，每次讀一個字的資料，對讀入的每個字，CPU需要對外設狀態進行回圈檢查，直到確定該字已經在I/O控制器的資料暫存器中，由于CPU的高速性和I/O設備的低速性，致使CPU的絕大部分時間都處于等待I/O設備完成資料I/O的回圈測驗中，造成了 CPU資源的極大浪費，

程式直接控制方式雖然簡單易于實作，但是其缺點也是顯而易見的，由于CPU和I/O設備只能串行作業，導致CPU的利用率相當低，

中斷驅動方式

中斷驅動方式的思想是，允許I/O設備主動打斷CPU的運行并請求服務，從而“解放”CPU，使得其向I/O控制器發送讀命令后可以繼續做其他有用的作業，CPU與I/O可以并行操作，
從I/O控制器的角度來看，I/O控制器從CPU接收一個讀命令，然后從外圍設備讀資料，一旦資料讀入到該I/O控制器的資料暫存器，便通過控制線給CPU發出一個中斷信號，表示資料已準備好，然后等待CPU請求該資料，I/O控制器收到CPU發出的取資料請求后，將資料放到資料總線上，傳到CPU的暫存器中，至此，本次I/O操作完成，I/O控制器又可幵始下一次I/O操作，從CPU的角度來看，CPU發出讀命令，然后保存當前運行程式的背景關系（現場，包括程式計數器及處理機暫存器），轉去執行其他程式，在每個指令周期的末尾，CPU檢查中斷，當有來自I/O控制器的中斷時，CPU保存當前正在運行程式的背景關系，轉去執行中斷處理程式處理該中斷，這時，CPU從I/O控制器讀一個字的資料傳送到暫存器，并存入主存，接著， CPU恢復發出I/O命令的程式（或其他程式）的背景關系，然后繼續運行，中斷驅動方式比程式直接控制方式有效，但由于資料中的每個字在存盤器與I/O控制器之間的傳輸都必須經過CPU，這就導致了中斷驅動方式仍然會消耗較多的CPU時間，

DMA

在中斷驅動方式中，I/O設備與記憶體之間的資料交換必須要經過CPU中的暫存器，所以速度還是受限，而DMA（直接存盤器存取）方式的基本思想是在I/O設備和記憶體之間開辟直接的資料交換通路，徹底“解放” CPU，DMA方式的特點是：

基本單位是資料塊，
所傳送的資料，是從設備直接送入記憶體的，或者相反，
僅在傳送一個或多個資料塊的開始和結束時，才需CPU干預，整塊資料的傳送是在 DMA控制器的控制下完成的，

通道

I/O通道是指專門負責輸入/輸出的處理機，I/O通道方式是DMA方式的發展，它可以進一步減少CPU的干預，即把對一個資料塊的讀（或寫）為單位的干預，減少為對一組資料塊的讀（或寫）及有關的控制和管理為單位的干預，同時，又可以實作CPU、通道和I/O設備三者的并行操作，從而更有效地提高整個系統的資源利用率，

例如，當CPU要完成一組相關的讀（或寫）操作及有關控制時，只需向I/O通道發送一條I/O指令，以給出其所要執行的通道程式的首地址和要訪問的I/O設備，通道接到該指令后，通過執行通道程式便可完成CPU指定的I/O任務，資料傳送結束時向CPU發中斷請求，I/O通道與一般處理機的區別是：通道指令的型別單一，沒有自己的記憶體，通道所執行的通道程式是放在主機的記憶體中的，也就是說通道與CPU共享記憶體，

I/O通道與DMA方式的區別是：

DMA方式需要CPU來控制傳輸的資料塊大小、傳輸的記憶體位置，而通道方式中這些資訊是由通道控制的，
每個DMA控制器對應一臺設備與記憶體傳遞資料，而一個通道可以控制多臺設備與記憶體的資料交換，

緩沖區的作用

1、減少實際物理讀寫次數
2、緩沖區在創建時就被分配記憶體，這塊記憶體區域一直被重用，可以減少動態分配和回收記憶體的次數

SPOOLing技術和組成

SPOOLing技術

SPOOLing技術是低速輸入輸出設備與主機交換的一種技術，通常也稱為“假脫機真聯機”，他的核心思想是以聯機的方式得到脫機的效果，低速設備經通道和外設在主機記憶體的緩沖存盤器與高速設備相聯，該高速設備通常是輔存，為了存放從低速設備上輸入的資訊，或者存放將要輸出到低速設備上的資訊（來自記憶體），在輔存分別開辟一固定區域，叫“輸出井”（對輸出），或者“輸入井”（對輸入），簡單來說就是在記憶體中形成緩沖區，在高級設備形成輸出井和輸入井，傳遞的時候，從低速設備傳入緩沖區，再傳到高速設備的輸入井，再從高速設備的輸出井，傳到緩沖區，再傳到低速設備

組成

SPOOLing系統主要有以下三部分：
（1）輸入井和輸出井，這是在磁盤上開辟的兩個大存盤空間，輸入井是模擬脫機輸入時的磁盤設備，用于暫存I/O設備輸入的資料；輸出井是模擬脫機輸出時的磁盤，用于暫存用戶程式的輸出資料，
（2）輸入緩沖區和輸出緩沖區，為了緩和和CPU和磁盤之間速度不匹配的矛盾，在記憶體中要開辟兩個緩沖區；輸入緩沖區和輸出緩沖區，輸入緩沖區用于暫存由輸入設備送來的資料，以后再傳送到輸入井，輸出緩沖區用與暫存從輸出井送來的資料，以后在傳送給輸出設備，
（3）輸入行程SPi 和輸入行程SP0，這里利用兩個行程來模擬脫機I/O時的外圍控制機，其中，行程SPi模擬脫機輸入時的外圍控制機，將用戶要求的資料從輸入機通過輸入緩沖區再送到輸入井，當CPU需要輸入資料時，直接從輸入井讀入記憶體；行程SP0模擬脫機輸出時的外圍控制機，把用戶要求輸出的資料從先記憶體送到輸出井，待輸出設備空閑時，在將輸出井中的資料經過輸出緩沖區送到輸出設備上，

磁盤上資料的地址表示

磁盤設備可包括一個或多個物理盤片，每個磁盤片分一個或兩個存盤面(Surface)(見下圖)，每個盤面上有若干個磁道(Track)，磁道之間留有必要的間隙(Gap)，為使處理簡單起見，在每條磁道上可存盤相同數目的二進制位

磁盤的訪問時間

磁盤設備在作業時以恒定速率旋轉，為了讀或寫，磁頭必須能移動到所指定的磁道上，并等待所指定的扇區的開始位置旋轉到磁頭下，然后再開始讀或寫資料，
完成一次訪盤程序由三個動作組成：
尋道（seek）：磁頭移動定位到指定磁道
旋轉延遲：磁頭位于正確位置后，等待指定扇區從磁頭下旋轉經過，
資料傳輸(transfer)：資料在磁盤與記憶體之間的實際傳輸，
一次訪盤程序完成的時間由三部分組成：
尋道時間＋旋轉延遲時間＋資料傳輸時間，
分配塊時，把有可能順序存取的塊放在一起，最好在同一柱面上，從而減少磁盤臂的移動次數，

磁盤調度演算法：FCFS SSTF SCAN FSCAN

FCFS

假設磁盤訪問序列：98，183，37，122，14，124，65，67
讀寫頭起始位置：53(先來先服務)

SSTF

最短尋道時間優先SSTF （Shortest Seek Track Time First）：優先選擇距當前磁頭最近的訪問請求進行服務，主要考慮尋道時間，
優點：改善了磁盤平均服務時間；
缺點：造成某些訪問請求長期等待得不到服務，
假設磁盤訪問序列：98，183，37，122，14，124，65，67
讀寫頭起始位置：53（就近原則）

SCAN

掃描演算法（電梯演算法）
克服了最短尋道優先的缺點，既考慮了距離，同時又考慮了方向，
具體做法：當設備無訪問請求時，磁頭不動；當有訪問請求時，磁頭按一個方向移動，在移動程序中對遇到的訪問請求進行服務，然后判斷該方向上是否還有訪問請求，如果有則繼續掃描；否則改變移動方向，并為經過的訪問請求服務，如此反復，
Linux采用的就是類似于電梯演算法的磁盤調度演算法，
![在這里插入圖片描述](https://img-blog.csdnimg.cn/2020121810272636.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MDY5OQ==,size_16,color_FFFFFF,t_70

FSCAN

假設磁盤訪問序列：98，183，37，122，14，124，65，67，2
讀寫頭起始位置：53，向下掃描（先靠邊，再朝向另外一邊）

檔案系統

檔案和檔案系統的定義

檔案的定義

檔案：是被命名的資料的集合體
1)一組具有符號名相關聯字符的集合(無結構)
2)一組具有符號名相關聯記錄的集合(有結構)

檔案系統

1．檔案：是被命名的資料的集合體，
2．檔案系統：就是作業系統中負責操縱和管理檔案的一整套設施，它實作檔案的共享和保護，方便用戶“按名存取”，

檔案的結構：邏輯結構和物理結構，檔案存取方式

檔案的邏輯結構

1.用戶可見的檔案結構稱為檔案的邏輯結構

2.流式無結構檔案

1)檔案內部不再劃分記錄，它是由一組相關資訊組成的有序字符流，字符為基本管理單位

2)大量的源程式、可執行程式、庫函式等都采用流式無結構檔案形式，DOS、UNIX、Windows、Linux系統中的普通檔案都是流式檔案，

檔案的物理結構代表了資料的存盤方式，常見有以下幾種

1）連續檔案

連續檔案是指把邏輯上連續的檔案資訊依次存放到連續的物理塊中

連續檔案結構簡單，實作容易.但連續存盤空間的要求導致大量較小的區域無法分配和利用

2）串聯檔案

串聯檔案又稱為鏈接檔案，它把邏輯上連續的檔案資訊分散存放到不連續的塊中，每個物理塊最末一個字作為鏈接字指向與它鏈接的下一物理塊，檔案的結尾塊則存放結束標記“∧”，
串聯檔案只適用于磁盤，不適合磁帶，且對串聯檔案只能順序存取，

串聯檔案實作了檔案的非連續存盤，提高存盤空間利用率，消除了外部碎片，

3）檔案映照

在系統中建立一張檔案映照表，把所有盤塊的指標都存放在該表中，每個指標占一個表項，
用戶目錄中存放檔案的第一個塊號，利用這一塊號到檔案映造表中找到下一塊號，檔案的結尾塊則存放結束標記“∧”，通過檔案映照表可獲得該檔案占用的所有塊號，

大容量磁盤的檔案映照表很大，一般被作為檔案保存在磁盤中，需要時，調入記憶體即可，

檔案映照方式只適用于磁盤，既可進行順序存取，又能進行隨機存取，

檔案映照表既保持了鏈接檔案的優點，又克服了其缺點，但是增加了檔案映照表的存盤開銷，訪問速度的提高是用存盤空間的增加來換取的，

在DOS系統中，使用稱為FAT的檔案映照表來完成檔案的映照；而在Windows中使用FAT32來完成檔案的映照，

4）索引檔案

索引檔案的思想類似于存盤管理中的分頁管理，
系統為每個檔案建立一張索引表，給出邏輯塊號和分配給它的物理塊號的對應資訊，

索引檔案只適用于磁盤，對索引檔案除了能進行順序存取外，也可較方便實作隨機存取，

如果把索引表全部放入記憶體，必然占據過多記憶體空間，一般把索引表以檔案的形式存放到外存，需要時調入記憶體即可，

對于中、小型檔案，存放索引表檔案可能只需一個物理塊；

但對于大型檔案，由于索引表比較大，需要用多個物理塊來存放，物理塊之間再通過鏈接指標相互鏈接，索引表的訪問效率必然降低，

這時可采用兩級索引的方法，即為存放索引表的物理塊（簡稱索引塊）再建立索引，
索引結構是計算機作業系統中普遍采用的結構，如在Linux系統中，小型檔案采用一級索引結構，大型檔案采用二級索引結構，巨型檔案則采用三級索引結構，

檔案目錄管理的功能

檔案目錄管理的基本功能就是實作“按名存取”，

檔案目錄還要能合理組織目錄結構，使得各個檔案的查找速度較快，還要能提供對檔案的共享，即讓多個用戶共用一個檔案，

檔案目錄是一張記錄所有檔案的基本資訊的目錄表，如檔案名、檔案存放的物理位置以及檔案說明和控制方面的資訊，

檔案存盤空間的管理 ：空閑檔案目錄、位示圖、鏈接法（成組鏈接法）

空閑檔案目錄（空閑塊表 ）

將檔案存盤設備上的每個連續空閑區看作一個空閑檔案（又稱自由檔案），系統為所有空閑檔案單獨建立一個目錄，每個空閑檔案在這個目錄中占一個表目，它包括空閑塊個數，空閑塊號和第一個空閑塊號等，
適用于連續檔案結構的檔案存盤區的分配與回收，

鏈接法

把檔案存盤設備上的所有空閑塊鏈接在一起，當申請者需要空閑塊時，分配程式從鏈頭開始摘取所需要的空閑塊，然后調整鏈首指標，反之，當回收空閑塊時，把釋放的空閑塊逐個插入鏈尾上，
鏈接方法因系統而異，常用的鏈接方法有按空閑區大小順序鏈接、按釋放先后順序鏈接以及按成組鏈接法， 前兩種方法在增加或移動空閑塊時需對空閑塊鏈作較大的調整，因而需耗去一定的系統開銷，成組鏈接法則更優，

位示圖

空閑表和空閑塊鏈法在分配和回收空閑塊時，都需經過設備管理程式啟動外設查找空閑檔案目錄項或鏈接塊號才能完成，分配回收速度較低，
使用位示圖的方法可以提高空閑塊的分配回收速度.
系統首先從記憶體中畫出若干個位元組，為每個檔案存盤設備建立一張位示圖，在位示圖中，每個檔案存盤設備的物理塊都對應一個位元位， “0”表示所對應的塊是空閑塊，“1” 表示所對應的塊已被分配出去，
利用位示圖來進行空閑塊分配時，只需查找圖中的“0”位，并將其置為“1”位，反之，利用位示圖回收時只需把相應的位元位由“1”改為“0”即可，
描述能力強，適合各種物理結構，磁盤常用此方法，