作業系統原理知識點
第 1 章 作業系統引論
作業系統
作業系統是一組能有效地組織和管理計算機硬體和軟體資源，合理地對各類作業進行排程，以及友善使用者使用的程式的集合。
單道批處理系統
概念
系統對作業的處理是成批進行的，但在記憶體中始終隻保持一道作業。
缺點
系統中的資源得不到充分的利用。
多道批處理系統
概念
作業先存放在外存上并排成一個隊列，稱為 “後備隊列”。然後由作業排程程式按一定的算法從後備隊列中選擇若幹個作業調入記憶體，使它們共享 CPU 和系統中的各種資源。
優點
資源使用率高
系統吞吐量大
缺點
平均周轉時間長
無互動能力
硬實時任務
指系統必須滿足任務對截止時間的要求，否則可能出現難以預測的後果。
軟實時任務
同硬實時任務一樣，也聯系着一個截止時間，但并不嚴格，若偶爾錯過了任務的截止時間，對系統産生的影響也不會太大。
作業周轉時間
從作業進入系統到作業完成退出系統所用時間。
系統吞吐量
機關時間内系統所處理的作業個數。
搶占式排程
該排程方式允許排程程式根據某種原則，去暫停某個正在執行的程序，将已配置設定給該程序的處理機重新配置設定給另一程序。
非搶占式排程
采用該排程方式時，一旦把處理機配置設定給某程序後，就一直讓它運作下去，絕不會因為時鐘中斷或任何其它原因去搶占目前正在運作程序的處理機，直至該程序完成，或發生某事件而被阻塞時，才把處理機配置設定給其它程序。
第 2 章 程序的描述與控制
程式并發時的特征
間斷性
程式在并發執行時，由于它們共享系統資源，以及為完成同一項任務而互相合作，緻使在這些并發執行的程式之間形成了互相制約的關系。
失去封閉性
當系統中存在着多個可以并發執行的程式時，系統中的各種資源将為它們所共享，而這些資源的狀态也由這些程式來改變，緻使其中任一程式在運作時，其環境都必然會受到其它程式的影響。
不可再現性
程式在并發執行時，由于失去了封閉性，也将導緻其又失去可再現性。
程序
定義
程序是程序實體的運作過程，是系統進行資源配置設定和排程的一個獨立機關
特征
動态性
動态性是程序的最基本的特征。它由建立而産生，由排程而執行，由撤銷而消亡。
并發性
指多個程序實體同存于記憶體中，且能在一段時間内同時運作。
獨立性
指程序實體是一個能獨立運作、獨立獲得資源和獨立接受排程的基本機關。
異步性
指程序是按異步方式運作的，即按各自獨立的、不可預知的速度向前推進。
五個基本狀态
建立狀态
程序已擁有了自己的 PCB，但程序自身還未進入主存，即建立工作尚未完成，程序還不能被排程運作，其所處的狀态。
就緒狀态
指程序已處于準備好的狀态，即程序已配置設定到除 CPU 以外的所有必要資源後，隻要再獲得 CPU，便可立即執行。
執行狀态
指程序已獲得 CPU，其程式正在執行的狀态。
阻塞狀态
指正在執行的程序由于發生某事件（如 I/O 請求、申請緩沖區失敗等）暫時無法繼續執行的狀态，亦即程序的執行收到阻塞。
終止狀态
當一個程序到達了自然結束點，或是出現了無法克服的錯誤，或是被作業系統所終結，或是被其他有終止權的程序所終結，它将進入終止狀态。
五個基本狀态的狀态轉換圖
原語
原語是由若幹條機器指令所構成，用以完成特定功能的一段程式。
程序建立原語 Create 的功能
申請空白 PCB；
為新程序配置設定其運作所需的資源；
初始化程序控制塊 PCB；
如果程序就緒隊列能接納新程序，便将新程序插入就緒隊列。
臨界資源
一次僅允許一個程序使用的資源，如列印機、變量。
臨界區
臨界區是指每個程序中通路臨界資源的那段代碼。
臨界區管理的準則
空閑讓進
當無程序處于臨界區時，表明臨界資源處于空閑狀态，應允許一個請求進入臨界區的程序立即進入自己的臨界區，以有效地利用臨界資源。
忙則等待
當已有程序進入臨界區時，表明臨界資源正在被通路，因而其它試圖進入臨界區的程序必須等待，以保證對臨界資源的互斥通路。
有限等待
對要求通路臨界資源的程序，應保證在有限時間内能進入自己的臨界區，以免陷入 “死等” 狀态。
讓權等待
當程序不能進入自己的臨界區時，應立即釋放處理機，以免程序陷入 “忙等” 狀态。
信号量
所謂信号量，是一個僅能由同步原語對其進行操作的整型變量。
P、V 操作
指兩個标準的原子操作 wait(S)和 signal(S)，執行時不可中斷。
兩個操作的描述如下：
wait(S) {
while (S <= 0); // 不做任何操作
S–;
}
signal(S) {
S++;
}
1
2
3
4
5
6
7
8
S > 0時，S 為可用資源量；S = 0時，可用資源量用完。
利用信号量實作前驅關系
對于上圖，可用代碼架構描述：
p1() {S1; signal(a); signal(b);}
p2() {wait(a); S2; signal©; signal(d);}
p3() {wait(b); S3; signal(e);}
p4() {wait©; S4; signal(f);}
p5() {wait(d); S5; signal(g);}
p6() {wait(e); wait(f); wait(g); S6;}
main() {
semaphore a, b, c, d, e, f, g;
a.value = b.value = c.value = 0;
d.value = e.value = 0;
f.value = g.value = 0;
cobegin
p1(); p2(); p3(); p4(); p5(); p6();
coend
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
生産者 - 消費者問題
有一群生産者程序在生産産品，并将這些産品提供給消費者程序去消費。為使生産者程序與消費者程序能并發執行，在兩者之間設定了一個具有 n 個緩沖區的緩沖池，生産者程序将其所生産的産品放入一個緩沖區中；消費者程序可從一個緩沖區中取走産品去消費。盡管所有的生産者程序和消費者程序都是以異步方式運作的，但它們之間必須保持同步，既不允許消費者程序到–個空緩沖區去取産品，也不允許生産者程序向一個已裝滿産品且尚未被取走的緩沖區中投放産品。
利用記錄型信号量解決
int in = 0, out = 0;
item buffer[n];
semaphore mutex = 1, empty = n, full = 0;
void producer() {
do {
producer an item nextp;
…
wait(empty);
wait(mutex);
buffer[in] = nextp;
in := (in + 1) % n;
signal(mutex);
signal(full);
} while(TRUE);
}
void consumer() {
do {
wait(full);
wait(mutex);
nextc = buffer[out];
out = (out + 1) % n;
signal(mutex);
signal(empty);
consumer the item in nextc;
…
} while (TRUE);
}
void main() {
cobegin
producer();
consumer();
coend
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
利用 AND 型信号量解決
int in = 0, out = 0;
item buffer[n];
semaphore mutex = 1, empty = n, full = 0;
void producer() {
do {
producer an item nextp;
…
Swait(empty, mutex);
buffer[in] = nextp;
in := (in + 1) % n;
Ssignal(mutex, full);
} while(TRUE);
}
void consumer() {
do {
Swait(full, mutex);
nextc = buffer[out];
out = (out + 1) % n;
Ssignal(mutex, empty);
consumer the item in nextc;
…
} while (TRUE);
}
void main() {
cobegin
producer();
consumer();
coend
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
哲學家進餐問題
有五個哲學家共用一張圓桌，分别坐在周圍的五張椅子上，在圓桌上有五個碗和五隻筷子，他們的生活方式是交替地進行思考和進餐。平時，一個哲學家進行思考，饑餓時便試圖取用其左右最靠近他的筷子，隻有在他拿到兩隻筷子時才能進餐。進餐畢，放下筷子繼續思考。
利用記錄型信号量解決
semaphore chopstick[5] = {1, 1, 1, 1, 1};
do {
wait(chopstick[i]);
wait(chopstick[(i + 1) % 5]);
…
// eat
…
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
…
// think
…
} while(TRUE);
1
2
3
4
5
6
7
8
9
10
11
12
13
利用 AND 型信号量解決
semaphore chopstick[5] = {1, 1, 1, 1, 1};
do {
…
// think
…
Swait(chopstick[(i + 1) % 5], chopstick[i]);
…
// eat
…
Ssignal(chopstick[(i + 1) % 5], chopstick[i]);
} while(TRUE);
1
2
3
4
5
6
7
8
9
10
11
讀者 - 寫者問題
利用記錄型信号量解決
semaphore rmutex = 1, wmutex = 1;
int readcount = 0;
void reader() {
do {
wait(rmutex);
if (readcount == 0) {
wait(wmutex);
}
readcount++;
signal(rmutex);
…
perform read operation;
…
wait(rmutex);
readcount–;
if (readcount == 0) {
signal(wmutex);
}
signal(rmutex);
} while(TRUE);
}
void writer() {
do {
wait(wmutex);
perform write operation;
signal(wmutex);
} while(TRUE);
}
void main() {
cobegin
reader();
writer();
coend
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
利用信号量集機制解決
int RN;
semaphore L = RN, mx = 1;
void reader() {
do {
Swait(L, 1, 1);
Swait(mx, 1, 0);
…
perform read operation;
…
Ssignal(L, 1);
} while(TRUE);
}
void writer() {
do {
Swait(mx, 1, 1, L, RN, 0);
perform write operation;
Ssignal(mx, 1);
} while(TRUE);
}
void main() {
cobegin
reader();
writer();
coend
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
使用者态和系統态
概念
使用者态：
當程序在執行使用者自己的代碼時，則稱其處于使用者運作态（使用者态）。
系統态：
當一個任務（程序）執行系統調用而陷入核心代碼中執行時，我們就稱程序處于核心運作态（或稱為核心态、系統态、管态）。
優先級
第 3 章 處理機排程與死鎖
處理機排程的層次
進階排程（長程排程）
排程對象：作業；
主要功能：根據某種算法，決定将外存上處于後備隊列中的哪幾個作業調入記憶體，為他們建立程序、配置設定必要的資源，并将它們放入就緒隊列。
中級排程（記憶體排程）
實際上就是存儲器管理中的對換功能。
排程對象：程序；
主要功能：将那些暫時不能運作的程序，調至外存等待（挂起）；将外存上已具備運作條件的就緒程序再重新調入記憶體（就緒）。
低級排程（短程排程）
是最基本的一種排程，運作頻率最高。
排程對象：程序（或核心級程序）；
主要功能：根據某種算法，決定就緒隊列中的哪個程序應獲得處理機，并由分派程式将處理機配置設定給被選中的程序。
處理機排程算法的目标
共同目标
資源使用率
使系統中的處理機和其他所有資源都盡可能地保持忙碌狀态。
公平性
使諸程序都獲得合理的 CPU 時間，不會發生程序饑餓現象。
平衡性
使系統中的 CPU 和各種外部裝置都能經常處于忙碌狀态，盡可能保持系統資源使用的平衡性。
政策強制執行
對所制訂的政策其中包括安全政策，隻要需要，就必須予以準确地執行，即使會造成某些工作的延遲也要執行。
批處理系統的目标
平均周轉時間短
系統吞吐量高
處理機使用率高
分時系統的目标
響應時間快
均衡性
指系統響應時間的快慢應與使用者所請求服務的複雜性相适應。
實時系統的目标
截至時間的保證
可預測性
程序排程算法
先來先服務排程算法（FCFS）
英文全稱：Firs-Come First-Served
排程原理：按照作業（程序）進入後備隊列（就緒隊列）的先後次序來挑選作業（程序），先進入先被挑選。
優點：算法容易實作，有利于長作業（程序）和 CPU 繁忙型作業。
缺點：效率不高，隻顧及作業（程序）等候時間，沒考慮作業（程序）要求服務時間的長短。不利于短作業（程序）和 I/O 繁忙型作業。
短作業優先排程算法（SJF）
英文全稱：Short Job First
排程原理：以作業的長短來計算優先級，作業越短，其優先級越高，就越先被排程。
優點：降低作業的平均等待時間，提高系統吞吐量。
缺點：
必須預知作業 / 程序的運作時間，很難估計準确；
歧視長作業，導緻其長期等待，得不到排程；（最大缺點）
人機無法互動；
完全不考慮作業的緊迫程度，不能保證緊迫性作業能得到及時處理，無法用于實時系統。
優先級排程算法（PSA）
英文全稱：Priority-Scheduling Algorithm
排程原理：作為作業排程算法時，系統将從後備隊列中選擇若幹個優先級最高的作業裝入記憶體；作為程序排程算法時，該算法把處理機配置設定給就緒隊列中優先級最高的程序。
高響應比優先排程算法（HRRN）
英文全稱：Highest Response Ratio Next
排程原理：即考慮等待時間，也考慮運作時間。每當要進行排程時，系統計算每個作業的響應比 R，選擇其中 R 最大者投入執行。
優點：既照顧了短作業，又考慮了作業到達的先後順序，還不會使長作業長期得不到服務。
缺點：每次要進行排程之前，都需要先做響應比的計算，增加了系統開銷。
輪轉排程算法
排程原理：将 CPU 的處理時間分成固定大小的時間片，系統将所有就緒程序按先來先服務的原則排成隊列。排程時，把 CPU 配置設定給隊首程序，令其執行一個時間片，時間片用完後，若程序未結束，則重新排入就緒隊列尾部。
優點：可以保證就緒隊列中所有程序在一給定時間内，均能獲得一時間片的處理機執行時間。
多隊列排程算法
排程原理：将系統中的程序就緒隊列從一個拆分為若幹個，将不同類型或性質的程序固定配置設定在不同的就緒隊列，不同的就緒隊列采用不同的排程算法，一個就緒隊列中的程序可以設定不同的優先級，不同的就緒隊列本身也可以設定不同的優先級。
優點：系統針對不同使用者程序的需求，很容易提供多種排程政策。
多級回報隊列排程算法
排程原理：
設定多個就緒隊列，優先級越高的隊列中，為每個程序所規定的執行時間片就越小。
新程序進入記憶體後，放入第一隊列末尾，按 FCFS 原則等待排程，當輪到該程序執行，一個時間片能完成則撤離系統；否則，将該程序轉入第二隊列末尾重新等待排程執行，以此類推。
僅當第一隊列空閑時，排程程式才排程第二隊列中的程序運作，以此類推。如果處理機正在為某隊列的程序服務，又有新程序插入到較高優先級的隊列中，則新程序将搶占正在運作程序的處理機。
優勢：
較好的性能，終端使用者互動一般在第一隊列就能完成，能夠照顧到使用者的利益；
短作業、長作業都能得到比較滿意的處理。
最早截止時間優先排程算法（EDF）
英文全稱：Earliest Deadline First
排程原理：根據任務截止時間來确定任務的優先級，任務截止時間越早，優先級越高，具有最早截止時間的任務排在隊列的隊首。排程程式在選擇任務時，總是選擇就緒隊列中的第一個任務，為之配置設定處理機。
缺點：隻考慮了截止時間，沒有考慮執行時間。如果本身要求執行時間較多，很可能被錯過。
最低松弛度優先排程算法（LLF）
英文全稱：Least Laxity First
排程原理：根據任務緊急（或松弛）的程度來确定優先級，緊急程度越高（松弛程度愈低）優先級越高，越先執行。
優先級倒置
形成原因
高優先級程序（線程）被低優先級程序（線程）延遲或阻塞：共享臨界資源，低優先級的先進入臨界區，導緻高優先級的阻塞.
解決方法
進入臨界區的程序所占用的處理機不允許被搶占。
當高優先級進入臨界區時，如果已有一個低優先級程序正在使用該資源，低優先級程序繼承高優先級程序的優先級，并一直保持到其退出臨界區。
死鎖
概念
所謂死鎖，是指多個程序在運作過程中因争奪資源而造成的一種僵局，當程序處于這種僵持狀态時，若無外力作用，他們都将無法再向前推進。
如果一組程序中的每一個程序都在等待僅由該組程序中的其他程序才能引發的事件，那麼該組程序是死鎖的。
産生死鎖的必要條件
互斥條件（不能被破壞）
程序互斥使用資源，即在一段時間内，某資源隻能被一個程序占用。
請求和保持條件
程序申請新資源時不釋放已占有資源。
不可搶占條件
一個程序不能搶奪其他程序占有的資源。
循環等待條件
存在一組程序循環等待資源的環形鍊。
處理死鎖的方法
預防死鎖
通過設定某些限制條件，破壞産生死鎖四個必要條件中的一個或幾個來預防産生死鎖。
避免死鎖
在資源的動态配置設定過程中，用某種方法防止系統進入不安全狀态。
檢測死鎖
通過檢測機構及時地檢測出死鎖的發生，然後采取适當的措施，把程序從死鎖中解脫出來。
解除死鎖
檢測到已發生死鎖時，采取适當的措施，把程序從死鎖中解脫出來。
預防死鎖
破壞 ”請求和保持“ 條件
靜态資源配置設定法：
第 1 種協定：一個程序必須在執行前就申請它所要的全部資源，并且直到它所要的資源都得到滿足後才開始執行。
（優點：簡單易行。缺點：資源浪費嚴重，程序時常饑餓。）
第 2 種協定：允許程序隻獲得運作初期所需的資源，便開始運作。這些資源使用完畢并全部釋放，再申請新的所需資源。
（優點：資源使用率有所提高，減少饑餓現象。）
破壞 ”不可搶占“ 條件
采用剝奪控制：
當程序在申請資源未獲準許時，先主動釋放已占有的資源，然後才去等待，以後再一起向系統提出申請。
（缺點：代價較高，如列印機，可能造成前面的列印工作全部白做，或者資訊不連續，還可能因為反複請求和釋放資源而導緻程序無限期被推遲。）
破壞 ”循環等待“ 條件
順序資源配置設定法：
對系統的全部資源編号，并規定程序申請資源時隻能按升序進行。如果申請了一個較高序号資源後，又想申請低序号資源，那麼必須釋放所有相同或者更高序号的資源後，才能申請低序号資源。
（優點：資源使用率和系統吞吐量都有明顯提高。缺點：資源序号設定不易，且相對固定，不适用于新資源增加；作業使用資源順序可能與系統規定不同，造成資源浪費；限制使用者程式設計自由度）
銀行家算法
安全序列的求法
資源配置設定
優點
資源使用率比靜态資源配置設定法高，同時又避免了死鎖。
缺點
對資源配置設定過于保守；計算太多，并且需知道對資源的最大需求量，不太實際。
第 4 章 存儲器管理
存儲器的層次結構
動态重定位
位址變換過程是在程式執行期間，随着對每條指令或資料的通路自動進行的，稱為動态重定位。
對換
概念
所謂 “對換（交換）”， 是指把記憶體中暫時不能運作的程序或者暫時不用的程式和資料，調出到外存上，以便騰出足夠的記憶體空間，再把已具備運作條件的程序或程序所需要的程式和資料換入記憶體。
類型
整體對換
頁面（分段）對換
分頁存儲管理方式
概念
在該方式中，将使用者程式的位址空間分為若幹個固定大小的區域，稱為 “頁” 或 “頁面”。典型的頁面大小為 1 KB。相應地，也将記憶體空間分為若幹個實體塊或頁框，頁和塊的大小相同。這樣可将使用者程式的任一頁放入任一實體塊中，實作了離散配置設定。
位址結構
前一部分為頁号 P，後一部分為位移量W，即頁内位址。圖中的位址長度為 32 位，其中 0 ~ 11 位為頁内位址，即每頁的大小為 4 KB；12 ~ 31 位為頁号，位址空間最多允許有 1 M 頁。
對某特定機器，其位址結構是一定的。 若給定一個邏輯位址空間中的位址為 A，頁面
的大小為 L，則頁号 P 和頁内位址 d 可按下式求得：
P = I N T [ A L ] (1) P = INT\left[\dfrac{A}{L}\right]\tag1
P=INT
L
A
d = [ A ] m o d L (2) d = \left[A\right] mod\ L\tag2
d=[A]mod L(2)
例如：系統頁面大小為 1 KB，設 A = 2170 B，則由上式可以求得 P = 2，d = 122。
頁表
位址變換機構
當程序要通路某個邏輯位址中的資料時，分頁位址變換機構會自動地将有效位址（相對位址）分為頁号和頁内位址兩部分，再以頁号為索引去檢索頁表。
在執行檢索之前，先将頁号與頁表長度進行比較，如果頁号大于或等于頁表長度，則表示本次所通路的位址已超越程序的位址空間，于是出現越界錯誤，并産生位址越界中斷。
若未出現越界錯誤，則将頁表始址與頁号和頁表項長度的乘積相加，便得到該表項在頁表中的位置，于是可從中得到該頁的實體塊号，将之裝入實體位址寄存器中。
與此同時，再将有效位址寄存器中的頁内位址送入實體位址寄存器的塊内位址字段中。這樣便完成了從邏輯位址到實體位址的變換。
分段存儲管理方式
概念
在分段存儲管理方式中，作業的位址空間被劃分為若幹個段，每個段定義了一組邏輯資訊。每個段都從 0 開始編址，并采用一段連續的位址空間。每個段既包含了一部分位址空間，又辨別了邏輯關系。其邏輯位址由段号和段内位址所組成。
位址結構
該位址結構中，允許一個作業最長有 64 K 個段，每個段的最大長度為 64 KB。
段表
用于實作從邏輯段到實體記憶體的映射。
位址變換機構
在進行位址變換時，系統将邏輯位址中的段号與段表長度 TL進行比較。
若 S > TL，表示段号太大，是通路越界，于是産生越界中斷信号。
若未越界，則根據段表的始址和該段的段号，計算出該段對應段表項的位置，從中讀出該段在記憶體的起始位址。
然後，再檢查段内位址 d 是否超過該段的段長 SL。若超過，即 d > SL，同樣發出越界中–斷信号。若未越界，則将該段的基址 d 與段内位址相加，即可得到要通路的記憶體實體位址。
第 5 章 虛拟存儲器
虛拟存儲器的定義和特征
定義
所謂虛拟存儲器，是指具有請求調入功能和置換功能，能從邏輯上對記憶體容量加以擴充的一種存儲器系統。其邏輯容量由記憶體容量和外存容量之和所決定，其運作速度接近于記憶體速度，而每位的成本卻又接近于外存。
特征
多次性
作業無需一次性裝入，可以分多次調入記憶體；每次隻需調入需要的程式和資料。
對換性
作業的程式和資料也無需常駐記憶體，暫時不用的部分可以調出，需要時候再調入。
虛拟性
邏輯上擴充記憶體，從磁盤借用空間（機械磁盤和 SSD）
影響缺頁率的因素
頁面大小
頁面劃分較大，則缺頁率較低；反之，缺頁率較高。
程序所配置設定實體塊的數目
所配置設定的實體塊數目越多，缺頁率越低；反之則越高。
頁面置換算法
算法的優劣決定了程序執行過程中缺頁中斷的次數，是以缺頁率是衡量頁面置換算法的重要名額。
程式固有特性
程式本身的編制方法對缺頁中斷次數有影響，根據程式執行的局部性原理，程式編制的局部化程度越高，相應執行時的缺頁程度越低。
頁面置換算法
最佳置換算法（Optimal）
原理：所選擇的被淘汰頁面将是以後永不使用的，或許是在未來最長時間内不再被通路的頁面。
優點：可保證獲得最低的缺頁率。
缺點：為理想算法。由于無法預知未來的頁面通路情況，實際上無法實作。
先進先出置換算法（FIFO）
原理：總是淘汰最先進入記憶體的頁面，即選擇在記憶體中駐留時間最久的頁面予以淘汰。
優點：實作簡單。
缺點：與程序實際運作的規律不适應，因為在程序中，有些頁面經常被通路。
最近最久未使用置換算法（LRU）
英文全稱：Least Recently Used
原理：該算法賦予每個頁面一個通路字段，用來記錄一個頁面自上次被通路以來所經曆的時間 t。當需淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最久未使用的頁面予以淘汰。
影響頁面換進換出效率的因素
頁面置換算法
寫回磁盤的頻率
讀入記憶體的頻率
抖動
概念
在虛拟記憶體中，頁面在記憶體與外存之間頻繁排程，以至于排程頁面所需時間比程序實際運作的時間還多，此時系統效率急劇下降，甚至導緻系統崩潰。這種現象稱為颠簸或抖動。
産生抖動的原因
同時在系統中運作的程序太多，由此配置設定給每一個程序的實體塊太少，不能滿足程序正常運作的基本要求，緻使每個程序在運作時，頻繁地出現缺頁，必須請求系統将所缺之頁調入記憶體。
這會使得在系統中排隊等待頁面換進 / 換出的程序數目增加。
顯然，對磁盤的有效通路時間也随之急劇增加，造成每個程序的大部分時間都用于頁面的換進 / 換出，而幾乎不能再去做任何有效的工作，進而導緻發生處理機的使用率急劇下降并趨于 0 的情況。
第 6 章 輸入輸出系統
與裝置的無關性
概念
指應用程式獨立于具體使用的實體裝置。
設定裝置無關性的優點
裝置配置設定時的靈活性；
易于實作 I/O 重定向。
塊裝置
概念
所謂塊裝置，是指資料的存儲和傳輸都是以資料塊為機關的裝置。
典型的塊裝置是磁盤。
特點
傳輸速率較高
可尋址
字元裝置
概念
所謂字元裝置，是指資料的存取和傳輸是以字元為機關的裝置。
典型的字元裝置是鍵盤、列印機等。
特點
傳輸速率較低
不可尋址
I/O 裝置的控制方式
使用輪詢的可程式設計 I/O 方式
在處理機向控制器發出一條 I/O 指令，啟動輸入裝置輸入資料時，要同時把狀态寄存器中的忙 / 閑标志 busy 置為 1，然後便不斷地循環測試 busy（稱為輪詢）。當 busy = 1 時，表示輸入機尚未輸完一個字元， 處理機應繼續對該标志進行測試，直至 busy = 0，表明輸入機已将輸入資料送入控制器的資料寄存器中。于是處理機将資料寄存器中的資料取出，送入記憶體指定單元中，這樣便完成了一個字元的 I/O。接着再去啟動讀下一個資料，并置 busy = 1。
特點：CPU 和 I/O 裝置串行工作，使主機不能充分發揮效率，外圍裝置也不能得到合理使用，整個系統效率很低。
使用中斷的可程式設計 I/O 方式
當某程序要啟動某個 I/O 裝置工作時，便由 CPU 向相應的裝置控制器發出一條 I/O 指令，然後立即傳回繼續執行原來的任務。裝置控制器于是按照該指令的要求去控制指定 I/O 裝置。此時 CPU 與 I/O 并行操作。
特點：
不必忙式查詢 I/O 準備情況，CPU 和 I/O 裝置可實作部分并行，與程式查詢的串行工作方式相比，使 CPU 資源得到較充分利用；
I/O 操作直接由 CPU 控制，每傳送一個字元或字，要發生一次中斷，仍然消耗大量 CPU 時間。
直接存儲器（DMA）通路方式
I/O 裝置直接與主存交換資料，不占用 CPU。
特點：
資料傳輸的基本機關是資料塊；
所傳送的資料塊是從裝置直接送入記憶體，或者相反；
在傳送一個或多個資料塊的開始和結束才需 CPU 幹預，傳送過程是在控制器的控制下完成。
I/O 通道控制方式
由通道管理和控制 I/O 操作，減少了外圍裝置和 CPU 的邏輯聯系。把 CPU 從瑣碎的 I/O 操作中解放出來。
特點：實作 CPU、通道和 I/O 裝置三者的并行操作，進而更有效地提高整個系統的資源使用率。
SPOOLing 技術——假脫機系統
概念
多道程式環境中，用程式模拟外圍控制機功能。
輸出時把處理機資料快速寫入磁盤，之後再從磁盤輸出到外圍低速裝置；
輸入時把外圍 I/O 裝置資料先讀入磁盤，CPU 再脫機從磁盤讀入資料。
特點
提高了 I/O 的速度
将獨占裝置改造為共享裝置
實作了虛拟裝置功能
緩沖
概念
改善中央處理器與外圍裝置之間速度不配的沖突，凡是資料到達和離去速度不比對的地方均可采用緩沖技術。
作用
緩和 CPU 與 I/O 裝置間速度不比對的沖突；
減少對 CPU 的中斷頻率，放寬對 CPU 中斷響應時間的限制；
解決資料粒度不比對的問題；
提高 CPU 和 I/O 裝置之間的并行性。
磁盤排程算法
先來先服務（FCFS）
原理：根據程序請求通路磁盤的先後次序進行排程。
優點：公平、簡單，且每個程序的請求都能依次地得到處理，不會出現某一程序的請求
長期得不到滿足的情況。
缺點：由于未對尋道進行優化，緻使平均尋道時間可能較長。
平均尋道長度舉例：
最短尋道時間優先（SSTF）
原理：選擇距目前磁頭所在磁道最近的磁道進行通路。
優點：比 FCFS 有更好的尋道性能。
缺點：可能導緻某個程序發生饑餓現象。
平均尋道長度舉例：
掃描算法（SCAN）
又名電梯排程算法。
原理：選擇與目前磁頭移動方向一緻且距離最近的程序。一個方向資料讀完再掉頭，避免了程序饑餓。
優點：尋道性能較好，避免出現饑餓現象。
缺點：當磁頭移動時，剛好跨過的某一磁道，被一程序請求，則該程序會被迫等待較長時間，産生饑餓。
平均尋道長度舉例：
循環掃描算法（CSCAN）
原理：磁頭單向移動，循環執行。
平均尋道長度舉例：
NStepSCAN 算法
原理：将磁盤請求隊列分成若幹個長度為 N 的子隊列，磁盤排程将按 FCFS 算法依次處理這些子隊列。而每個隊列的處理是按 SCAN 算法，一個處理完畢再處理下一個隊列。
FSCAN算法
原理：是 NStepSCAN 算法的簡化，隻分為兩個子隊列。一個是由目前所有請求磁盤 I/O 的程序形成的隊列，由磁盤排程按 SCAN 算法進行處理。另一個是在掃描期間，将新出現的所有請求磁盤 I/O 的程序放入等待處理的請求隊列。
第 7 章 檔案管理
檔案、記錄和資料項之間的層次關系
記錄
記錄是一組相關資料項的集合，用于描述一個對象在某方面的屬性。
在記錄的各個資料項中，能唯一地辨別一個記錄的一個或幾個資料項，稱為關鍵字。
檔案
檔案是指由建立者所定義的、具有檔案名的一組相關元素的集合，可分為有結構檔案和無結構檔案兩種。
檔案的邏輯結構
概念
從使用者觀點出發所觀察到的檔案組織形式，即檔案是由一系列的邏輯記錄組成的，是使用者可以直接處理的資料及其結構，它獨立于檔案的實體特性，又稱為檔案組織。
分類
按檔案是否有結構分類：
有結構檔案
有标準格式，各種屬性項描述檔案的一個實體，分為定長記錄，變長記錄。例如：各種資料庫檔案
無結構檔案
流式檔案。無法直接讀取查詢，隻能靠指針移動定位。
按檔案的組織方式分類：
順序檔案
指由一系列記錄按某種順序排列所形成的檔案，其中的記錄可以是定長記錄或可變長記錄。
索引檔案
指為可變長記錄檔案建立一張索引表，為每個記錄設定一個表項，以加速對記錄的檢索速度。
索引順序檔案
建立一張索引表時，并不是為每一個記錄建立一個索引表項，而是為一組記錄中的第一個記錄建立一個索引表項。
第 8 章 磁盤存儲器的管理
外存的組織方式
連續組織方式
原理：為每個檔案配置設定連續的磁盤空間。（基本不可能）
優點：
順序通路容易；
順序通路速度快。
缺點：
要求為一個檔案配置設定連續的存儲空間，進而産生大量碎片；
必須事先知道檔案的長度；
不能靈活地删除和插入記錄；
不便于動态增長的檔案。
連結組織方式
概念：為檔案配置設定多個不連續的盤塊，再通過每個盤塊上的連結指針，将同屬于一個檔案的多個離散的盤塊連結成一個連結清單， 由此所形成的實體檔案稱為連結檔案。
優點：
消除了磁盤的外部碎片，提高了外存的使用率。
對插入、删除和修改記錄都非常容易。
能适應檔案的動态增長，無需事先知道檔案的大小。
隐式連結
原理：每個目錄項含有指向檔案第一個和最後一個塊的指針。每個盤塊中含有指向下一個盤塊的指針。
缺點：隻能順序通路，随機通路效率極低，同時也很不安全，中間連結斷開，後面全部都找不到了。
顯式連結
原理：
建構一張連結表，把檔案各實體塊的指針顯式存放，該表在整個磁盤中僅僅有一張，即檔案配置設定表 FAT。鍊首指針對應的盤塊号，作為檔案位址填入 FCB 的實體位址字段中。
索引組織方式
将檔案和對應的盤塊号集中放在一起，通路檔案時将該檔案說對應的盤塊号一起調入記憶體。
在索引配置設定中，為每個檔案配置設定一個索引塊（表），檔案盤塊号都在該索引表中。建立檔案時，隻需要在建立的目錄項中填上指向索引表達指針即可。
單級索引組織方式
優點：支援直接通路，不會産生外部碎片。當檔案較大時，索引方式要優于鍊式配置設定方式。
缺點：每一個檔案都需要一個索引表。對于小檔案來說，索引配置設定使用率低，浪費空間建立索引。
多級索引組織方式
優點：對大型檔案查找迅速。
缺點：随着索引級數增多，所需啟動磁盤的次數增加。對小檔案來說浪費資源，隻适合大型檔案。
FAT 技術
原理
在 FAT 中引入 “卷” 的概念，支援将實體磁盤分為四個邏輯磁盤，每個邏輯磁盤就是一個卷，也叫分區。
每個卷都是能被單獨格式化和使用的邏輯單元，卷中包含了檔案系統資訊、一組檔案以及空閑空間。每個卷都有專門區域存放 FAT 表和檔案目錄表，以及自己的邏輯驅動器字母。
一個實體磁盤可以分為多個邏輯卷，一個邏輯卷也可以由多個實體磁盤組成。
FAT 表大小的計算
對于 1.2 MB 的軟碟，每個盤塊的大小為 512 B，在每個 FAT 中共含有 2.4 K 個表項，由于每個 FAT 表項占 12 位（1.5個B），故 FAT 表占用 3.6 KB 的存儲空間。
NTFS 的新特征
使用了 64 位磁盤位址；
可以很好地支援長檔案名，單個檔案名限制在 255 個字元以内，全路徑名為 32767 個字元；
具有系統容錯功能，即在系統出現故障或差錯時，仍能保證系統正常運作；
能保證系統中的資料一緻性，這是一個非常有用的功能；
提供了檔案加密、檔案壓縮等功能。
NTFS 的磁盤組織
分區稱為卷 。
NTFS 以族為磁盤空間配置設定和回收的基本機關，又稱為卷因子。
卷因子是實體磁盤扇區的整數倍，是格式化指令時候确定的。
————————————————
版權聲明：本文為CSDN部落客「Kisaragi」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。
原文連結：https://blog.csdn.net/qq_43331488/article/details/111617013
![ubuntu12.04 minicom安裝和使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)