很多小夥伴私信要word下載下傳，我就整理出來了一份pdf，是和線上的完全一樣，建議大家看線上的，因為pdf下載下傳需要收費，但是下載下傳有好處就是可以列印出來複習，各位夥伴自行選擇吧。現在這裡給出pdf完整下載下傳： 作業系統（第四版）期末複習總結.pdf_作業系統複習-OS文檔類資源-CSDN下載下傳
作業系統（第四版）期末複習總結（上）
作業系統（第四版）期末複習總結（下）
銜接我的上一篇博文，這片從第三章開始
第三章：處理機排程與死鎖
1、處理機排程的三個層次
- 進階排程（也稱為作業排程、宏觀排程、長程排程）：用于決定外存上處于後備隊列中的哪些作業調入記憶體，并為他們建立程序、配置設定必要的資源，再将新建立的程序排在就緒隊列上，準備執行。
作業排程應解決的兩個問題：
接納多少作業？ 取決于多道程式度
接納哪些作業？ 取決于所采用的排程算法，如先來先服務排程算法、短作業有限排程算法等
- 中級排程（又稱中程排程）：涉及程序在内、外存間的交換，從存儲器資源管理的角度來看，把程序的部分或全部換出到外存上，可為目前運作程序的執行提供所需記憶體空間。
- 低級排程（也稱程序排程、微觀排程、短程排程）：用來決定就緒隊列中哪個程序應獲得處理機，再有分派程式執行把處理機配置設定給改程序
程序排程的兩種方式：
非搶占式：不允許某程序搶占已經配置設定出去的處理機
搶占方式：允許排程程式根據某種原則，暫停正在執行的程序，将處理機重新配置設定給另一程序
搶占原則：優先權原則、短作業（程序）優先原則、時間片原則
程序排程要解決的問題：
按什麼原則配置設定CPU ——排程算法
何時配置設定CPU——排程的時機
如何配置設定CPU——CPU排程過程
程序排程的時機
a、一個程序運作完畢，或因某種錯誤而終止運作
b、當一個程序在運作時變為等待狀态（等待I/O）
c、分時系統中時間片到
d、當有一個優先級更高的程序就緒（搶占式）
例：新建立一個程序；一個等待程序變成就緒
e、在程序通信中，執行中的程序執行了某種原語操作（P操作，阻塞原語）
2、排程算法——排程算法是指根據系統的資源配置設定政策所規定的資源配置設定算法。
送出時間Si（并不是開始執行時間）；運作結束時間Ei；
周轉時間：Ti=Ei-Si
則作業平均周轉時間T：
平均帶權周轉時間W：
（Ts：服務時間）
- 先來先服務排程算法（FCFS）——
應用範圍與含義
作業排程：完成選擇一個或多個最先進入後備隊列的作業，将它們調入記憶體，為它們配置設定資源、建立程序，并放入就緒隊列。
程序排程：按照程序就緒的先後次序來排程程序，為之配置設定處理機
優缺點
FCFS排程算法比較有利于長作業（程序），而不利于短作業（程序）。
FCFS排程算法有利于CPU繁忙型的作業，不利于I/O繁忙型的作業。
- 短作業優先排程算法（SJF）——
SJ(P)F排程算法的優缺點
優點：能有效地降低作業的平均等待時間，提高系統吞吐量。
缺點：
對長作業不利
未考慮作業的緊迫程度
作業的估計運作時間不準确
- 高響應比排程算法（HRRN）——響應比Rp = 1 +（作業等待時間 / 作業處理時間）
如作業等待時間相同，則處理時間越短，響應比越高，有利于短作業。
對于長作業，随等待時間增加，響應比增高，最後同樣可獲得處理機。
如處理時間相同，等待時間越長，響應比越高，實作的是先來先服務。
幾種排程算法執行個體：
FCFS算法：JOB1-JOB2-JOB3-JOB4
SJF算法：JOB1-JOB3-JOB4-JOB2
HRRN算法：JOB1-JOB3-JOB2-JOB4
3、死鎖
一組程序中，每個程序都無限等待被該組程序中另一程序所占有的資源，因而永遠無法得到該資源，這種現象稱為程序死鎖(Deadlock)，這一組程序就稱為死鎖程序。
3.1、死鎖産生的原因
- 競争資源引起程序死鎖（資源配置設定政策）（可剝奪和非剝奪資源）
- 程序推進順序不當引起死鎖
PS：關于死鎖的一些結論：
- 參與死鎖的程序最少是兩個（兩個以上程序才會出現死鎖）
- 參與死鎖的程序至少兩個已經占有資源
- 參與死鎖的所有程序都在等待資源
- 參與死鎖的程序是目前系統中所有程序的子集
- 如果死鎖發生，會浪費大量的系統資源，甚至導緻系統崩潰
3.2、死鎖的四個必要條件
- 互斥條件：設計的資源是非共享的
- 不可搶占條件：不能強行剝奪程序擁有的資源
- 請求和保持條件：程序在等待一新資源時繼續占有已配置設定的資源
- 環路條件：存在一種程序的循環鍊，鍊中的每一個程序已獲得的資源同時被下一個程序所請求
3.3、處理死鎖的方法
- 預防死鎖：通過設定某些限制條件，去破壞死鎖四個必要條件中的一個或多個，來防止死鎖。
- 避免死鎖：不事先設定限制條件去破壞産生死鎖的條件，而是在資源的動态配置設定過程中，用某種方法去防止系統進入不安全狀态，進而避免死鎖的發生。
- 檢測死鎖：允許死鎖發生，但可通過檢測機構及時檢測出死鎖的發生，并精确确定與死鎖有關的程序和資源，然後采取适當措施，将系統中已發生的死鎖清除掉。
- 解除死鎖：與檢測死鎖相配套，用于将程序從死鎖狀态解脫出來。常用的方法是撤消或挂起一些程序。以回收一些資源，再将它們配置設定給處于阻塞狀态的程序，使之轉為就緒狀态
3.4、避免死鎖——銀行家算法
- 可利用資源向量Available。它是一個含有 m個元素的數組，其中每個元素代表一類 可利用資源的數目。
- 最大需求矩陣Max。n*m矩陣，表示n個程序的每一個對m類資源的最大需求。
- 配置設定矩陣Allocation 。n*m矩陣，表示每個程序已配置設定的每類資源的數目。
- 需求矩陣Need 。n*m矩陣，表示每個程序還需要各類資源數。
銀行家算法步驟：
當程序Pi提出資源申請時，執行下列步驟：
（1）若Requesti[j]≤Need[i,j],轉（2）；
否則錯誤傳回
（2）若Requesti[j] ≤Available[j],
轉（3）；否則程序等待
（3）假設系統配置設定了資源，則有：
Available [j] :=Available [j] -Requesti[j];
Allocation[i,j]:=Allocation[i,j]+Requesti[j];
Need[i,j]:=Need[i,j]-Requesti[j]
（4）執行安全性算法。
若系統新狀态是安全的，則完成配置設定；
若系統新狀态是不安全的，則恢複原狀态，程序等待
安全性算法步驟：
(1) Work[j]:=Available[j];
Finish[i]:=false;
(2) 尋找滿足下列條件的i：
a). Finish[i]=false;
b). Need[i,j]≤Work[j];
如果不存在，則轉(4)
(3) Work[j] :=Work[j]+Allocation[i,j];
Finish[i]:=true;
轉(2)
(4) 若對所有i,Finish[i]=true,則系統處于安全狀态，否則處于不安全狀态
可得： Need[i,j]= Max[i,j]- Allocation[i,j]
例：
設系統有五個程序和三類資源，每類資源分别有10、5、7。在T0時刻資源配置設定情況如下：
T0時刻可以找到一個安全序列<P1, P3, P4, P2, P0>，系統是安全的。
P1送出請求Request(1,0,2)，執行銀行家算法
可以找到一個安全序列{P1,P3,P4,P0,P2}，系統是安全的，可以将P1請求資源配置設定給它。
若是：P4送出請求Request(3,3,0), 執行銀行家算法
Available=（2 3 0）
不能通過算法第2步（ Requesti[j]≤Available[j] ），是以P4等待。
例：如下：若P0送出請求Request(0,2,0)，執行銀行家算法
Available{2,1,0}已不能滿足任何程序需要，是以系統進入不安全狀态，P0的請求不能配置設定。
練習題：有三類資源A(17)、B(5)、C(20)。有5個程序P1~P5。T0時刻系統狀态如下：
問:
(1)、T0時刻是否為安全狀态，給出安全系列。
(2)、T0時刻，P2: Request(0,3,4)，能否配置設定，為什麼？
(3)、在(2)的基礎上P4：Request(2,0,1)，能否配置設定，為什麼？
(4)、 在(3)的基礎上P1：Request(0,2,0)，能否配置設定，為什麼？
解：(1) T0時刻的出安全系列
先求出Need和Work
(2) P2: Request(0,3,4)
因（Available =2 3 3）< Request(0,3,4) 是以不能配置設定。
(3) P4：Request(2,0,1) Available =2 3 3
有安全序列P4 P5 P3 P2 P1 可以配置設定
(4) P1：Request(0,2,0)
0 1 2 已不能滿足任何程序的需要，不能配置設定
第四章：存儲器管理
存儲器的層次結構
1、連續配置設定存儲管理方式
-
單一連續配置設定——最簡單，适用于單使用者、單任務的OS。
優點：
易于管理。
缺點：
對要求記憶體空間少的程式，造成記憶體浪費；程式全部裝入，很少使用的程式部分也占用記憶體。
- 固定分區配置設定——把記憶體劃分為個數固定、大小相等或不等的多個區域。分區的劃分由計算機的操作員或者由作業系統給出，并給出分區說明表。
優點：易于實作，開銷小。
缺點：
記憶體碎片（零頭）造成浪費
分區總數固定，限制了并發執行的程式數目。
可以和覆寫、交換技術配合使用。
- 動态分區配置設定——指在系統運作的過程中建立分區，并使分區的大小剛好與作業的大小相等。這種存儲管理的方法解決了固定分區嚴重浪費記憶體的問題。是一種較為實用的存儲管理方法。
基于順序搜尋的動态分區配置設定方法
首次适應法（FF）：要求空閑分區按首址遞增的次序組織空閑分區表（隊列）。
注意：每次配置設定和回收後空閑分區表或空閑 分區隊列都要按首址遞增的次序排序。
下次适應法(NF)（循環首次适應算法）：按分區的先後次序，從上次配置設定的分區起查找（到最後分區時再回到開頭），找到符合要求的第一個分區。
最佳适應法(BF) ：要求按空閑區大小遞增的次序組成空閑分區表（隊列）。
注意：配置設定和回收後要對空閑區表(隊列)重新排序
優點：
在系統中若存在一個與申請分區大小相等的空閑區，必定會被選中，而首次适應法則不一定。
若系統中不存在與申請分區大小相等的空閑區，則選中的空閑區是滿足要求的最小空閑區，而不緻于毀掉較大的空閑區。
缺點：
空閑區的大小一般與申請分區大小不相等，是以将其一分為二，留下來的空閑區一般情況下是很小的，以緻無法使用。随着時間的推移，系統中的小空閑區會越來越多，進而造成存儲區的大量浪費
最壞适應法(WF)：要求空閑區按大小遞減的順序組織空閑區表（或隊列）
例：有作業序列：作業A要求18K；作業B要求25K，作業C要求30K。系統中空閑區按三種算法組成的空閑區隊列：
經分析：最佳适應法對這個作業序列是合适的，而其它兩種對該作業序列是不合适的。
- 可重定位分區配置設定
2、基本分頁存儲管理方式——把使用者程式按邏輯頁劃分成大小相等的部分，稱為頁（page） 。從0開始編頁号，頁内位址是相對于0編址
2.1、頁表
頁表包含以下幾個表項：
頁号：登記程式位址空間的頁号。
塊号：登記相應的頁所對應的記憶體塊号。
其它：登記與存儲資訊保護有關的資訊
例：作業1有2頁分别裝入記憶體的第5、6塊；作業2有3頁裝入記憶體的第2、4、7塊；作業3有1頁裝入記憶體的第8塊
頁的大小是2K ， k: 9~16。
第五章：虛拟存儲器-具有請求調入功能和置換功能，能從邏輯上對記憶體容量加以擴充的一種存儲器系統。
1、交換技術
1.1、選擇原則
即：将哪個程序換出記憶體？
1.2、選擇時機
隻要不用（或很少再用）就換出；
隻在記憶體空間不夠或有不夠的危險時換出；
1.3、交換時需要做哪些工作？
換出和換入過程，需要一個磁盤交換區：
必須足夠大以存放使用者程式記憶體映像的拷貝；
必須對這些記憶體映像直接存取。
1.4、換回記憶體時位置的确定
2、虛拟存儲的實作方法
2.1、請求分頁系統
在分頁系統的基礎上增加請求調頁功能和置換功能所形成的頁式虛拟存儲器系統。
硬體支援：請求分頁的頁表機制、缺頁中斷機構、位址變換機構。
軟體支援
2.2、請求分段系統
請求分段的段表機制、缺段中斷機構、位址變換機構
3、請求分業存儲管理方式
在程序開始運作之前，不是裝入全部頁面，而是裝入幾個或零個頁，之後根據程序運作的需要，動态裝入其它頁；
在程序開始運作之前，不是裝入全部頁面，而是裝入幾個或零個頁，之後根據程序運作的需要，動态裝入其它頁；
3.1、頁表機制
狀态位：表示該頁是否裝入記憶體；
通路位：此頁在一段時間被通路的次數，可用來決定淘汰哪頁（由不同的算法決定）；
修改位：檢視此頁是否在記憶體中被修改過；
外存位址：該頁在外存上的位置。
3.2、缺頁中斷處理
在位址映射過程中，在頁表中發現所要通路的頁不在記憶體，則産生缺頁中斷。
作業系統接到此中斷信号後，就調出缺頁中斷處理程式，根據頁表中給出的外存位址，準備将該頁調入記憶體。
此時應将缺頁的程序挂起（調頁完成喚醒）
如果記憶體中有空閑塊，則配置設定一個塊，将要調入的頁裝入該塊，并修改頁表中相應頁表項的狀态位及相應的記憶體塊号；
若此時記憶體中沒有空閑塊，則要淘汰某頁（若被淘汰頁在記憶體期間被修改過，則要将其寫回外存）。
4、頁面置換算法
- 功能：需要調入頁面時，選擇記憶體中哪個實體頁面被置換。稱為replacement policy。
- 目标：把未來不再使用的或短期内較少使用的頁面調出，通常隻能在局部性原理指導下依據過去的統計資料進行預測；
- 頁面鎖定(frame locking)：必須常駐記憶體的OS關鍵部分或時間關鍵(time-critical)的應用程序。實作方法為在頁表中加上鎖定标志位(lock bit)。
4.1幾種算法
- 最佳頁面算法（OPT）——選擇“未來不再使用的”或“在離目前最遠位置上出現的”頁面被置換。
PS：是一種理想情況，實際執行中是無法預知的，因而不能實作。
可用作其他算法性能評價的依據
- 先進先出頁面置換算法（FIFO）——選擇建立最早的頁面被置換。可以通過連結清單來表示各頁的建立時間先後。
特點：性能較差。較早調入的頁往往是經常被通路的頁，這些頁在FIFO算法下被反複調入和調出。并且有Belady現象。
Belady現象：采用FIFO算法時，如果對一個程序未配置設定它所要求的全部頁面，有時就會出現配置設定的頁面數增多，缺頁率反而提高的異常現象。
Belady現象的描述：一個程序P要通路M個頁，OS配置設定N個記憶體頁面給程序P；對一個通路序列S，發生缺頁次數為PE（S,N）。當N增大時，PE(S, N)時而增大，時而減小。
Belady現象的原因：FIFO算法的置換特征與程序通路記憶體的動态特征是沖突的，即被置換的頁面并不是程序不會通路的。
例：有一虛拟存儲系統，采用先進先出的頁面淘汰算法。在記憶體中為每個程序配置設定3塊。程序執行時使用頁号的順序為 4 3 2 1 4 3 5 4 3 2 1 5
(1) 該程序運作時總共出現幾次缺頁。
(2) 若每個程序在記憶體有4塊，又将産生幾次缺頁。
(3) 如何解釋所出現的現象。
（1）m=3
（2）、m=4
m=3時，缺頁中斷9次
m=4時，缺頁中斷10次
（3）、FIFO頁面淘汰算法會産生異常現象（Belady現象），即：當配置設定給程序的實體頁面數增加時，缺頁次數反而增加
- 最近最久未使用頁面置換算法（LRU）——選擇最後一次通路時間距離目前時間最長的一頁并淘汰之。即淘汰沒有使用的時間最長的頁。
特點：局部性原理的合理近似，性能接近最佳置換（OPT）算法。 實作代價很高（軟體方法或硬體方法）
- 輪轉算法（clock）（也稱最近未使用算法(NRU, Not Recently Used)）
- 最不經常使用（LFU）——選擇到目前時間為止被通路次數最少的頁面被置換；
例：某程式在記憶體中配置設定三個塊，通路頁的走向為4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、 LRU、OPT算法分别計算缺頁次數。
假設開始時所有頁均不在記憶體。
eg:某程式在記憶體中配置設定四個塊，通路頁的走向為4，3，2，1，4，3，5，4，3，2，1，5，按LRU、OPT算法分别計算缺頁次數
假設開始時所有頁均不在記憶體
章節練習：
1、有一頁式系統，其頁表存放在主存中。
(1) 如果對主存的一次存取要3us，問實作一次頁面通路要多長時間。
(2) 如系統有快表，平均命中率為97%，假設通路快表的時間忽略為0，問此時一次頁面通路要多長時間。
（1）、2*3=6us
（2）、0.97*3+0.03*6=3.09us
2、在分頁存儲管理系統中，有一作業大小為4頁，頁長為2K，頁表如下：
試借助位址變換圖（即要求畫出位址變換圖）求出邏輯位址4635所對應的實體位址。
3、如果記憶體劃分為100KB、500KB、200KB、300KB、600KB首次适應、最佳适應和最差适應算法各自将如何放置大小分别為212KB、417KB、112KB、426KB的程序？哪種算法的記憶體使用率最高？
答：
（1）首次适應：212KB放在500KB分區（剩餘288KB）；417KB放在600KB分區；112KB放在剩餘的288KB分區；而426KB程序必須等待。
（2）最佳适應：212KB放在300KB分區；417KB放在500KB分區；112KB放在200KB分區；426KB放在600KB分區。
（3）最差适應：212KB放在600KB分區（剩餘388KB）；417KB放在500KB分區；112KB放在剩餘388KB分區；而426KB程序必須等待。
綜上可以看出，最佳适應算法的記憶體使用率最高。
5、一個32位位址的計算機使用兩級頁表，虛位址被分為9位的頂級頁表域，11位的二級頁表域和偏移，請問，頁面長度是多少？在位址空間中，共存在多少頁？
答：9位作頂級頁表域，11位作二級頁表域，是以剩餘32-(9+11)=12位作偏移，是以頁面長度是212=4K，在位址空間中共存在220個頁面。
第三四五章重點：
第三章 處理機排程與死鎖
1.處理機排程的層次
2.作業排程及算法
(FCFS SJF HRRN)
3.死鎖的概念、産生原因、必要條件、預防死鎖
4.避免死鎖-銀行家算法，安全性算法
第四章 存儲器管理
1.連續配置設定的存儲管理方式
2.動态分區配置設定算法
（首次适應法、最佳适應法、最壞适應法）
3.分頁存儲管理方式
第五章 虛拟存儲器
1.交換技術
2.請求分頁系統
3.頁面置換算法（先進先出、最優、最近未使用）