第一章

多道批處理系統的定義

? 用戶所提交的作業都先存放在外存上并排成一個佇列，稱為“后備佇列”；然后由作業調度程式按一定的演算法從后備佇列中選擇若干個作業調入記憶體，使它們共享CPU和系統中的各種資源，

分時系統的定義

? 在一臺主機上連接了多個帶有顯示幕和鍵盤地終端，以互動方式使用計算機，按照時間片輪轉原則實作主機資源共享，是秒級OS，

實時系統地定義

? 是指系統能及時(或即時)回應外部事件地請求，在規定地時間內完成對該事件地處理，并控制所有實時任務協調一致地運行，是毫秒級OS，

作業系統的定義

? 作業系統是一組能有效地組織和管理計算機硬體和軟體資源，合理的對各類作業進行調度，以及方便用戶使用的程式的集合，

作業系統的作用

? 是配置在計算機硬體上的第一層軟體，是對硬體系統地首次擴充，其主要作用是管理好這些設備，提高它們的利用率和系統的吞吐量，并為用戶和應用程式提供一個簡單的介面，便于用戶使用，

作業系統的四大特征

并發

? 并發性，是指兩個或多個事件在同一時間間隔內發生，

• 為提高CPU的作業效率，多道程式同時在記憶體中，為多道程式環境，
• 在多道程式環境下，在一段時間內，宏觀上有多個程式在同時運行，但在處理機系統中，每一時刻卻僅能有一程式執行，故微觀上這些程式只能是分時的交替運行，

共享

? 指系統中的資源可供記憶體中多個并發執行的行程(執行緒)共同使用，

• 互斥共享方式：系統中的某些資源，雖然可以提供給多個行程(執行緒)使用，但應規定在一段時間內，只允許一個行程訪問該資源，
• 同時訪問方式：系統中的某些資源，允許在一段時間內由多個行程“同時”對它們進行訪問，這里所謂的“同時”，在單處理機環境下是宏觀意義上的，而在微觀上，這些行程對該資源的訪問是交替進行的，

  并發和共享是多用戶(多任務)OS的兩個最基本的特征，它們是互為存在的條件，

  1.資源共享是以行程的并發執行為條件的，若系統不允許并發執行也就不存在資源共享問題；

  2.若系統不能對資源共享實施有效管理，以協調好諸行程對共享資源的訪問，也必然會影響到諸行程間并發執行的行程，甚至根本無法并發執行，

異步

? 行程是以人們不可預知的速度向前推進，此即行程的異步性，

虛擬

? 在OS中，把通過某種技術將一個物理物體變為若干個邏輯上對應的物的功能稱為“虛擬”，

• 時分復用技術：利用某設備唯一用戶服務的空閑時間，又轉去為其他用戶服務，使設備得到最充分的利用，
• 空分復用技術：利用存盤器的空閑空間磁區域存放和運行其他的多道程式，以此來提高記憶體的利用率，

第二章

行程的定義

? 行程是行程物體(程式段、PCB<行程控制塊>、資料段)的運行程序，是系統進行資源分配和調度的一個獨立單位，

行程的特征

• 動態性：行程的實質是行程物體的執行程序，動態性是行程的最基本的特征，
• 并發性：指多個行程物體同存與記憶體中，且能在一段時間內同時運行，
• 獨立性：指行程物體是一個能獨立運行、獨立獲得資源和獨立接受調度的基本單位，
• 異步性：指行程是按異步方式運行的，即按各自獨立的、不可預知的速度向前推進，

行程物體的組成

1. 程式段
2. 相關的資料段
3. PCB(行程控制塊)

行程的基本狀態的定義、轉化、轉化原因

基本狀態的定義

? 就緒狀態(Ready)：指行程已處于準備好運行的狀態，即行程已分配到除CPU以外的所有必要資源后，只要再獲得CPU，便可立即執行，
? 執行狀態(Running)：指行程已獲得CPU，其程式正在執行的狀態，
? 阻塞狀態(Block)：指正在執行的行程由于發生某事件(如I/O、申請緩沖區失敗等)暫時無法繼續執行時的狀態，亦即行程的執行受到阻塞，

基本狀態的轉化/基本狀態的轉化原因

? 例：處于就緒狀態的行程，在調度程式為之分配處理機之后便可執行，相應地，其狀態就由就緒狀態轉變為執行狀態；正在執行的行程(當前行程)如果因分配給它的時間片已完而被剝奪處理機暫停執行時，其狀態便由執行狀態轉為就緒狀態；如果因發生某事件，致使當前行程的執行受阻，使之無法繼續執行，則該行程狀態將由執行狀態轉變為阻塞狀態，

原語

? 原語是由若干條指令組成，用于完成一定功能的一個行程，
? 原語的特點是原子操作：指一個操作中的動作要么全做，要么全不做，它是一個不可分割的操作，行程的創建、撤銷和就緒等都是由OS的內核中的原語來實作的，

行程的原語操作

block/行程阻塞程序

? 阻塞是行程自身的一種主動行為，

1. 進入block程序后，由于行程還處于執行狀態，所以應立即停止執行，把行程控制塊中的現行狀態由“執行‘改為阻塞；
2. 將PCB插入阻塞佇列；
3. 調度程式進行重新調度，將處理機分配給另一就緒行程，并進行切換；
4. 保留被阻塞行程的處理機狀態，按新行程的PCB中的處理機狀態設定CPPU的環境，

wakeup/行程喚醒程序

? block原語和wakeup原語是一對作用剛好相反的原語，

1. 把被阻塞的行程從等待該事件的阻塞佇列中移除，將其PCB中出現的現行狀態由阻塞改為就緒；
2. 將該PCB插入到就緒佇列中，

suspend/掛起原語

? 原有狀態不變，在原有狀態之前加入“靜止”二字，
? 將記憶體中的行程調入外存中，

active/激活原語

? 原有狀態不變，在原有狀態之前加入“活動”二字，
? 將外存中的行程調入記憶體中，

行程同步：完成

? 具體的看超星上的題目，第二章《行程的描述與控制》，
? wait、signal代碼體

typedef struct{//表示資源的數目和行程串列
	int value;//資源的數目
	struct process_control_block*list;//佇列
}semaphore;
//wait(S)和signal(S)操作
wait(semaphore *S){P//分配 操作(Passeren)
  S->value--;//資源數目減一
  if(S->value<0)block(S->list);//資源不夠就阻塞
}
signal(semaphore *S){//回收 V操作(Vrijgeven)
  S->value++;//資源數目加一
  if(S->value<=0)wakeup(S->list);//有等待行程就喚醒
}

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

? 執行緒是調度和分配的單位，

作用：

1. 執行緒是調度的基本單位，
2. 引入執行緒可提高程式并發執行的程度，可進一步提高系統效率，
3. 執行緒的切換可能引起行程的切換，

行程與執行緒的區別?

引入執行緒的作業系統后，行程是資源的分配單位，執行緒是調度和分派的單位，

執行緒的切換代價小于行程，

執行緒只擁有一點必不可少的、能保證獨立運行的資源，行程擁有系統資源，

行程通信的分類

能傳送大量資料的的高級通信工具機制分為

1. 共享存盤器系統
2. 訊息傳遞系統
3. 管道通信系統

第三章

調度演算法

周轉時間=完成時間-到達時間
帶權周轉時間=周轉時間/服務時間

• 先來先服務演算法
  1. 先來先服務調度演算法容易實作，但是比較適合CPU繁忙性作業，
  2. 先來先服務演算法一般與其他演算法相結合，
• 短作業優先演算法
  1. 需要預估作業的運行時間，而且非常影響演算法，
  2. 對長作業不利，
• 高回應比優先調度演算法(非搶占式)(動態優先權)
  1. 優先權=(等待時間+要求服務時間)/要求服務時間=回應時間/要求服務時間
  2. 為每個作業引入一個動態優先級，即優先級是可以改變的，令它隨等待時間延長而增加，使長作業的優先級在等待期間不斷的增加，等到足夠時間后，必然有機會獲得處理機，
• 時間片輪轉演算法
  1. 時間片太小，利于短作業的完成，但是切換頻繁，開銷很大，時間片太大，就會退化為先來先服務演算法，不能體現互動性，
  2. 時間片非常關鍵，典型的做法是將時間片設定成一次典型的互動所需要的事件，

死鎖的定義

如果一組行程中的每一個行程都在等待僅有該組行程中的其他行程才能引發的事件，那么該組行程是死鎖的(Deadlock)，

死鎖的必要條件

1. 互斥條件
   • 行程對資源的使用是排他性的，
2. 請求和保持條件
   • 行程已經保持了一個資源，但是還要繼續申請其他資源，
3. 不可搶占條件
   • 行程獲得資源后，在未使用完成之前，不能被搶占，
4. 回圈等待條件
   • 資源的回圈鏈，

預防死鎖的方法

使四個必要條件不能成立，但由于互斥條件使設備的固有屬性，不能改變，

1. 摒棄“請求和保持”條件；
2. 摒棄“不搶占”條件；
3. 摒棄“環路等待”條件；

銀行家演算法

Available可用資源數

Max最大需求數

Allocation已分配數

Need還需求數

Request資源請求數

設Requesti是行程Pi的請求向量，如果Requesti［j］=K，表示行程Pi需要K個Rj型別的資源，當Pi發出資源請求后，系統按下述步驟進行檢查：

(1) 如果Requesti［j］≤Need［i,j］，便轉向步驟2；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值，

(2) 如果Requesti［j］≤Available［j］，便轉向步驟(3)；否則,表示尚無足夠資源，Pi須等待，

(3) 系統試探著把資源分配給行程Pi，并修改下面資料結構中的數值：

Available［j］=Available［j］-Requesti［j］;

Allocation［i,j］=Allocation［i,j］+Requesti［j］;

Need［i,j］=Need［i,j］-Requesti［j］;

(4) 系統執行安全性演算法，檢查此次資源分配后，系統是否處于安全狀態，若安全，才正式將資源分配給行程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓行程Pi等待，

檢測死鎖的方法

1. 資源分配圖
   • 圓圈代表行程，方框代表資源，
   • 找出既不孤立，也不阻塞的行程，消除其所有連接邊，
2. 死鎖定理
   • S為死鎖狀態的充分條件：當且僅當S狀態的資源分配圖是不可完全簡化的，
   • 簡化方法：

     (1) 找出一個既不阻塞又非獨立的行程結點P i ，P i 可獲得所需資源直至運行完畢，再釋放其所占有的全部資源，相當于消去Pi所有的請求邊和分配邊，使之成為孤立結點，

     (2) 重復上述步驟，若能使所有的行程結點都成為孤立結點，則稱該圖是可完全簡化的；否則，則稱該圖不可完全簡化，

3. 死鎖檢測中的資料結構

第四-五章

固定分配磁區的管理方式

基本思想：

將記憶體用戶空間劃分為若干個固定大小的區域，稱為磁區，每個磁區中只裝入一道作業，這樣便可以實作幾道作業并發運行，

劃分磁區的方法：

1. 磁區大小相等， 所有的記憶體磁區大小相等，
2. 磁區大小不等，

具體實作：

1. 將磁區按大小排隊
2. 建立磁區使用表，表項包括：①磁區號②磁區起始地址③磁區大小④磁區狀態
3. 當程式裝入時，由記憶體分配程式檢索磁區使用表
4. 若找到符合要求的磁區，則完成記憶體分配，并進行標記；
5. 若未找到，則拒絕記憶體分配，

動態磁區分配方式

動態磁區分配是根據行程的實際需要，動態地為之分配記憶體空間，

初始記憶體用戶區全部為空閑，然后到達一個行程，為其分配相應要求的空間，

磁區個數、磁區大小不固定，

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

演算法要求空閑磁區鏈以地址遞增的次序鏈接，

在分配記憶體時，從鏈首開始順序查找，直至找到一個大小能滿足的空閑磁區位置；若找不到，則分配失敗，

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

該演算法是對FF演算法的改進，在分配記憶體時，從上次找到的空閑磁區的下一個空閑磁區開始查找，直至找到一個大小能滿足的空閑磁區位置；若找不到，則分配失敗，

最佳適應演算法（best fit，BF）

指每次為作業分配記憶體時，總是把能滿足要求，又是最小的空閑區分配給作業，避免“大材小用”，該演算法要求把所有的空閑區按其容量從小到大的順序形成一鏈表，

這個演算法從區域看似乎是最佳的，但是每次分配后，剩余下來的空閑區總是最小的，會留下很多碎片，

最壞適應演算法（worst fit，WF）

最壞適應分配演算法要掃描整個空閑磁區表或鏈表，而且演算法要求把所有的空閑區按其容量從大到小的順序形成一鏈表，然后總是挑選一個最大的空閑區分割給作業使用，

其優點是產生碎片的幾率最小，但是缺乏大的空閑區，

動態分配磁區的回收程序

1. 回收記憶體塊前后無空閑塊
2. 回收記憶體塊前有后無空閑塊
3. 回收記憶體塊前無后有空閑塊
4. 回收記憶體塊前后均有空閑塊

基本分頁存盤管理思想、地址結構、頁表的作用、邏輯地址到物理地址的轉換

管理思想

將行程的邏輯地址空間按照一定的大小分成若干個頁面，

將記憶體的物理地址空間按照同樣的大小分成若干個塊，

將若干個頁面裝入到多個不相鄰的物理塊中，就稱為分頁存盤，

地址結構

頁表的作用

基本作用是將用戶地址空間中的邏輯地址映射為記憶體空間中的物理地址，

邏輯地址到物理地址的轉換

若已知一個邏輯地址空間中的地址為A ，頁面大小為L，則頁號P和頁內地址d可按下式求得：

P＝ INT [A/L]

d＝[A] MOD L

物理地址=塊號*塊大小（頁面大小）+塊內地址（頁內地址）

例題1：

如果程式中的邏輯地址為7，怎么轉換成物理地址呢？頁面大小為4.
頁號 7/4=1
頁內地址 7%4=3
所以塊號為2，
2*4+3=11

例題2：

如果程式中的邏輯地址為3470，怎么轉換成物理地址呢？頁面大小為1024，頁表如下：
頁號 3470/1024=3
頁內地址 3470%1024=398
所以塊號為8，
8*1024+398=8590

基本分段存盤管理思想、地址結構、段表的作用、邏輯地址到物理地址的轉換

管理思想

把自己的作業按照邏輯關系劃分若干個段，每個段都從0開始編址，并有自己的名字和長度，

地址結構

段號	段內地址
31-----16	15-----0

段表的作用

實作邏輯段到物理記憶體區的映射，

邏輯地址到物理地址的轉換

物理地址=段的基地址+段內地址

邏輯地址為5，則其物理地址為多少？

段號	段內地址
1	1

由此得出段的基地址為6

基地址	段內地址
5	1

物理地址=段的基地址+段內地址=6+1=7

分頁和分段的區別

1. 頁是資訊的物理單位，分頁是為實作離散分配方式，以消減記憶體的外零頭，提高記憶體的利用率，或者說，分頁僅僅是由于系統管理的需要而不是用戶的需要，段則是資訊的邏輯單位，它含有一組其意義相對完整的資訊，分段的目的是為了能更好地滿足用戶的需要，
2. 頁的大小固定且由系統決定，由系統把邏輯地址劃分為頁號和頁內地址兩部分，是由機器硬體實作的，因而在系統中只能有一種大小的頁面；而段的長度卻不固定，決定于用戶所撰寫的程式，通常由編譯程式在對源程式進行編譯時，根據資訊的性質來劃分，
3. 分頁的作業地址空間是一維的，即單一的線性地址空間，程式員只需利用一個記憶符，即可表示一個地址；而分段的作業地址空間則是二維的，程式員在標識一個地址時，既需給出段名，又需給出段內地址，

段頁式存盤管理思想

分頁存盤管理系統是為了更好的提高記憶體的使用率，分段能夠更好的滿足用戶的需要，所以可以綜合起來，形成一種新的存盤管理方式—段頁式存盤管理方式，

虛擬存盤器的定義、理論基礎

定義

虛擬存盤器是指具有請求調入功能和置換功能，能夠從邏輯上對記憶體容量加以擴充的一種存盤器系統，

理論基礎

在程式運行之前沒有必要將其全部裝入記憶體，僅需要將當前運行的少數頁面或者段裝入記憶體里，其余的留在硬碟上，等需要時再調入，如果記憶體已滿，再按照某種策略將原有的內容置換出去，

請求分頁存盤管理思想、地址結構、頁表、邏輯地址到物理地址的轉換、置換演算法(三個)、缺頁中斷

管理思想

將基本的分頁存盤管理與虛擬存盤器相結合起來的存盤管理方式稱為請求分頁存盤管理方式，

在請求分頁存盤管理方式下，只需要調入程式的部分頁進入到記憶體空間中，所以除了基本的分頁存盤管理，還需要增加請求調入頁面功能和頁面置換功能，

置換演算法

1. 先進先出（FIFO）頁面置換演算法

   該演算法總是淘汰最先進入記憶體的頁面，即選擇在記憶體中停留時間最久的頁面予以淘汰，該演算法實作簡單，但是置換率較高，

2. 最佳(Optimal)置換演算法

   該演算法所選擇的被淘汰頁面，將是以后永不使用的，或者是在最長(未來)時間內不再被訪問的頁面，采用最佳置換演算法，通常可保證獲得最低的缺頁率，

3. 最近最久未使用演算法 (LRU)

   根據頁面調入記憶體后的使用情況進行決策的，它總是選擇最近最久未使用的頁面予以淘汰，該演算法是一種比較好的演算法，但是需要較多硬體的支持，

缺頁中斷

1. 每當所要訪問的頁面不在記憶體中，便產生一缺頁中斷，請求OS將所缺的頁面調入記憶體，
2. 需要保護CPU環境、分析原因、轉入到缺頁中斷處理程式執行，
3. 缺頁中斷就算指令執行期間，也要立即被回應，
4. 一條指令在執行期間可能產生多次缺頁中斷，

第六章

I/O層次：設備無關性、驅動程式

設備無關性

編程時要用列印機，只要寫列印機的邏輯名字，

應用程式中所使用的設備，不局限于使用某個具體的物理設備，這個稱為設備無關性，

優點：I/O設備可以更換，而且應用程式也不需要修改，

驅動程式

1. 主要作業就是傳輸，
2. 驅動程式將對硬體操作定義為若干個函式，
3. 驅動程式與硬體緊密相關，

驅動程式的主要任務就是啟動指定設備，完成上層指定I/O作業，（先啟動列印機，然后將函式轉化為列印機聽得懂的命令，列印機中設備控制器的命令格式，比如某個暫存器的操作，這個跟硬體本身相關，）

緩沖區的管理方式及并行時間段

假脫機技術的定義

引入多道程式后，可以利用其中的一道程式來模擬時脫機輸入輸出操作時外圍控制機的功能，這樣的技術稱作為SPOOLing技術，或者稱為假脫機技術，

磁盤調度策略

先來先服務

這是一種最簡單的磁盤調度演算法，它根據行程請求訪問磁盤的先后次序進行調度，

該演算法的優點是公平，簡單，且每個行程的請求都能依次的得到處理，不會出現某一行程的請求長期得不到滿足的情況，但此演算法由于未對尋道進行優化，致使平均尋道時間可能較長，

最短尋道時間優先演算法

該演算法選擇這樣的行程：其要求訪問的磁盤與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，
該演算法相比先來先服務演算法有更好的尋道性能，曾被廣泛使用，但是會產生“饑餓”現象，距離較遠的磁道可能長時間得不到訪問，

掃描演算法（電梯演算法）

掃描（SCAN）演算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優先考慮的是磁頭當前的移動方向，該演算法的調度程序如電梯運行，所以又稱電梯演算法，

例如：

當磁頭正在自里向外移動時，掃描演算法所考慮的下一個訪問物件，是在當前磁道之外，又是距離最近的，這樣自里向外的訪問，直至再無更外的磁道需要訪問時，才將磁臂換向為自外向里移動，

該演算法可以避免饑餓現象，且訪問效率高，

回圈掃描演算法

回圈掃描演算法規定磁頭單向移動，

例如：

只是自里向外移動，當磁頭一道最外的磁道并訪問后，磁頭立即回傳到最里的欲訪問的磁道，也就是將最小磁道緊接著最大磁道構成回圈，形成回圈掃描，

磁頭單向移動可以克服以下問題：當磁頭剛從里向外移動過某一磁道時，恰有一行程請求訪問此磁道，這時該行程必須等待，待磁頭從里向外，然后再從外向里掃描完所有要訪問的磁道后，才處理該行程的請求，致使該行程的請求被嚴重地推遲，

第七-八章

檔案的定義

檔案是指由創建者所定義的、具有檔案名的一組相關元素的集合，可分為具有結構檔案和無結構檔案兩種，

檔案的邏輯結構定義

從用戶觀點出發所觀察到的檔案組織形式，它獨立于檔案的物理特性，稱為檔案的邏輯結構，

檔案的邏輯組織形式：順序檔案、索引檔案、索引順序檔案

1. 順序檔案：指由一系列記錄按某種順序排列所形成的檔案，其中的記錄可以是定長記錄或可變長記錄，
2. 索引檔案：指可變長記錄檔案建立一張索引表，為每個記錄設定一個表項，以加速對記錄的檢索速度，
3. 索引順序檔案，這是順序檔案和索引檔案相結合的產物，在為每個檔案建立一張索引表時，為一組記錄中的第一個記錄建立一個索引表項，

檔案的物理結構定義

連續組織方式，鏈接組織方式，索引組織方式，都是系統將檔案存盤在外存上所形成的一種存盤組織形式，是用戶不能看見的，稱為檔案的物理結構，

檔案物理結構及其組織形式

連續組織方式(連續存盤空間)

為每一個檔案分配一組相鄰接的盤塊，這樣的外存存盤方式稱為：連續組織方式，

優點：

1. 訪問連續檔案比較容易（只要連續的訪問盤塊就可以）
2. 訪問速度快（上一塊到下一塊移動距離短）

缺點：

1. 必須事先知道檔案的長度，但是有些檔案是動態增長的，
2. 空間會浪費（小空間無法分配）
3. 不能做插入和洗掉操作，

鏈接組織方式(離散存盤空間)

將檔案裝到多個離散的盤塊中，再通過每個盤塊上的鏈接指標，將多個離散的盤塊鏈接成為一個鏈表，稱為鏈接組織方式，

優點：

洗掉、插入等操作非常容易，無需事先知道檔案的大小，

缺點：

FAT檔案分配表占記憶體較大，浪費空間，

索引組織方式(一級索引)(離散存盤空間)

索引組織方式：為每個檔案分配一個索引塊，把檔案存盤的盤塊號記錄在內，將目錄項指向索引塊即可，

例題1：假設盤塊是512 B，每個盤塊號占4B,則一個盤塊能存放多少個盤塊號 ？所指向的檔案內容塊最多是多少個？所能存盤的檔案容量最大是多少？

盤塊號個數：512/4=128（個）塊

檔案內容塊：128個塊

最大檔案容量：128*512=64KB

優點：

能夠較快的查找檔案，且靈活的進行插入和洗掉操作，

例題2：某檔案系統采用多級索引結構，若磁盤塊的大小為512B，每個塊號需占3B，那么根索引采用一級索引時的檔案最大長度為（）KB；采用二級索引時的檔案最大長度為（）KB.

A 85	B 170	C 512	D 1024
A 512	B 1024	C14450	D28900

答:

A

盤塊個數：512B/3B=170個

一級索引檔案長度：170* 512B = 87040B = 85KB
C
二級索引檔案長度：170 * 170 * 512B = 14450KB

例題3：設檔案索引節點有8個地址項，每個地址項大小為4B，其中5個地址項為直接地址索引，2個地址項為一級間接索引，1個地址項為二級間接索引，磁盤索引塊和磁盤資料塊大小為1KB，若要訪問檔案的邏輯塊號分別為8和518（塊號從0開始），

A 直接地址索引和一級間接地址索引

B 直接地址索引和二級間接地址索引

C 一級間接地址索引和二級間接地址索引

D 一級間接地址索引和一級間接地址索引

答：C

直接地址索引：5個邏輯塊:0~4

一級間接索引：1KB/4B=256 256*2=512邏輯塊:5~516

二級間接索引：256^2=65536邏輯塊:517~66051

檔案的FCB、目錄、索引結點

FCB(檔案控制塊)

對系統中的大量檔案施以有效的管理，在檔案控制塊中，通常包含三類資訊，即基本資訊、存取控制資訊和使用資訊，

目錄

把PCB(檔案控制塊)的有序集合稱為檔案目錄，即一個PCB(檔案控制塊)就是一個檔案目錄項，

索引節點

將檔案名和檔案資訊分開，然后用一個資料結構存放檔案資訊，這個資料結構稱為索引結點，

外存的管理方式：位示圖

位示圖是利用二進制的1位來表示磁盤中一個盤塊的使用情況，值為0，表示空閑，值為1，表示已分配，

盤塊號=n*(i-1)+j-1;

n為一行的位數，i，j為行標和列標，

行號=(盤塊號 )DIV n+1

列號=(盤塊號)MOD n+1

例題：如果是第35個盤塊，是存放在第幾行，第幾列？如果是第23個盤塊，是存放在第幾行，第幾列？

35，第三行，第四列

23，第二行，第八列

位示圖法-盤塊的分配

1. 順序掃描位示圖，從中找出一個或一組其值為“0”的二進制位(“0”表示空閑時)，
2. 將所找到的一個或一組二進制位， 轉換成與之相應的盤塊號，假定找到的其值為“0”的二進制位，位于位示圖的第i行、第j列，則其相應的盤塊號應按下式計算：b=n(i-1)+j-1， n代表每行的位數，
3. 修改位示圖， 令map［i,j］=1，

位示圖法-盤塊的回收

1. 將回收盤塊的盤塊號b轉換成位示圖中的行號和列號， 轉換公式為：

   i=(b)DIV n+1

   j=(b)MOD n+1

2. 修改位示圖, 令map ［i,j］=0，

例題2：若8個字長（假設字長為32位）組成的位示圖管理磁盤空間，用戶歸還一個塊號為100的盤塊時，它對應位示圖的位置是（）（行列號均從1開始，塊號從1開始），

A 行號為3，列號為5

B 行號為4，列號為4

C 行號為3，列號為4

D 行號為4，列號為5

答：B

行號：i==(b-1)DIV n+1=(100-1)/32+1=3+1=4

列號：j=(b-1)MOD n+1=(100-1)%32+1=3+1=4

第九章

系統呼叫

定義

系統呼叫（System Call）提供了用戶程式和OS內核之間的介面，是用戶程式獲得OS服務的唯一途徑，

實際編程中，離不開系統呼叫，

內核函式

1. 處理I/O請求：sys_read、sys_write、sys_open、sys_close
2. 行程：sys_fork、sys_execve、sys_kill
3. 時間：sys_time、sys_settimeofday
4. 記憶體：sys_mmap、sys_brk

與函式呼叫對比

1. 如果系統呼叫的實作機制與函式呼叫一樣，則：

   (1)應用程式自己也可以直接操作硬體，（CALL 需要知道函式入口）

   (2)嚴重的安全隱患：一個應用程式出現錯誤，可能導致整個計算機系統崩潰

   啟發：系統呼叫的執行需要進行CPU作業模式的切換，

2. 用戶程式可以呼叫內核的任意函式，甚至可以繞過OS的檢查，搶占硬體資源，

   啟發：保證用戶程式只能從給定的位置呼叫內核，

運行狀態

為了安全性考慮，為了防止應用程式對OS的破壞，應用程式和OS的內核是運行在不同的狀態，

從給定位置呼叫內核

OS的所有系統呼叫，都是通過同一個中斷入口來是實作的，比如，Linux是80H，

內核函式都有一個唯一的編號，系統呼叫時，將編號放入指定暫存器或者記憶體即可，即為中斷號，

系統呼叫–程序

用戶程式使用系統呼叫程序(Linux)：

?push size/將資料塊大小壓入堆疊/

?push buf/將緩沖區指標壓入堆疊/

?push fd; /將檔案名壓入堆疊/

?push num;/將read的系統呼叫編號壓入堆疊/

?int 80h;

?add esp, 10h

? iret

例題：read系統呼叫的執行程序

1. 呼叫read庫函式
2. 存盤系統呼叫的編號到暫存器中，并通過中斷指令，請求執行OS代碼
3. 從固定點OS_entry進入OS內核，通dispatcher執行系統呼叫
4. syscall_handler結束，回傳到OS_entry
5. CPU執行iret回傳到用戶空間庫函式中；
6. 庫函式執行完回傳用戶程式，繼續執行下一條陳述句

API

為了方便用戶編程，為了提高程式的移植性，提出了應用程式API（Application Programming interface），

用戶態、核心態

作業系統在系統態運行，而應用程式只能在用戶態運行，在實際運行程序中，處理機會在系統態和用戶態間切換，