Nowcoder專項練習：作業系統（二）

1，動态重定位分區配置設定算法

雖然動态分區法比固定分區法的記憶體使用率高，但它還是有零頭（碎片）的問題。

• 動态重定位分區配置設定算法與動态分區配置設定算法基本上相同，差别僅在于：在這種配置設定算法中，添加了緊湊功能 。
• 通常，在找不到足夠大的空閑分區來滿足使用者需求時進行緊湊。
• 在緊湊過程中，因為記憶體中已經存在的作業需要 “ 移動 ” ，因而其中所有關于位址的項均需得到相應的修改，也就是需要進行位址重定位。

2，互斥段與信号量的範圍

在有 n 個程序共享一個互斥段，如果最多允許 m 個程序 (m<n) 同時進入互斥段，則信号量的變化範圍是什麼？

允許m個程序同時進入互斥段，說明初始值為m，當進入m後，剩下n-m個等待進入，是以範圍為 -(n-m)~m 。

3，被搶占時的儲存内容

在搶占式多任務進行中，程序被搶占時，哪些運作環境需要被儲存下來？

• 所有CPU寄存器的内容
• 頁表
• 程式計數器

大多數程序是沒有特定時間限制的普通程序，但仍然可以根據重要性來配置設定優先級，這種方案稱之為"搶占式多任務處理(preemptive multitasking)"，各個程序都配置設定到一定的時間段可以執行。

時間段到期後，核心會從程序回收控制權，讓"下一個程序(由排程器決定)"。被搶占程序的運作環境，即所有CPU寄存器、頁表都會儲存起來，是以上一個程序的執行結果不會丢失。在之前被搶占的程序恢複執行時，其程序環境可以完全恢複。

簡單來說，隻儲存自己的東西，公共的東西輪不到某個程序卻儲存。

4，平均通路磁盤次數

一個檔案系統中，FCB 占64B，一個盤塊大小為1KB，采用一級目錄，假定檔案目錄中有3200個目錄項，則查找一個檔案平均需要多少次通路磁盤？

分析：FCB是存儲在磁盤盤塊的。本題主要還是考察名詞辨析：檔案目錄=FCB的集合，檔案目錄項=FCB，是以由FCB的大小以及目錄項的個數可以得到的是檔案目錄共占用多少磁盤塊。3200×64B÷1KB=200，也即共用了200個磁盤塊存儲檔案目錄項。

一個磁盤塊上存儲多個FCB，并不是每個目錄項都通路磁盤查找一次，那樣太慢了，整個機器都會被拖死。比較好的做法是将一個磁盤塊調入記憶體。實際生活中磁盤的塊大小和記憶體的頁是一緻的。是以，訪存和訪盤的次數是不一樣的，因為記憶體可以很快，是以多通路幾次沒有關系，而磁盤通路一次都是一次長途奔襲，過于辛苦，是以減少訪盤次數是需要特别考慮的。這裡我們如果明晰：把一個磁盤塊調入記憶體，那麼問題就很簡單了：平均通路200÷2=100次磁盤。

嚴格來說是201÷2=100.5次，因為按照公式，平均啟動磁盤次數為(N＋1)/2次，其中N為盤塊個數。

因為是求平均數，是以最好的情況就是一次找到，最壞的情況就是找了200次，是以是(1+200)/2 = 100.5次。

換個角度了解，一個檔案目錄項對應一個檔案控制塊，我們查找一個檔案通過查找它的目錄即可。順序查找目錄表平均需要查找1600次，一個磁盤塊大小為1KB，一個檔案控制塊大小為64B，一個磁盤塊中有1KB/64B=16個檔案控制塊，相當于查找了1600/16=100個磁盤。

5，收回空閑區的變化

可變分區存儲管理在收回一個空閑區後，空閑區數目可能會怎樣？

• 當該空閑區上下都沒有空閑區時，數目增加一個；
• 當該空閑區上下都有空閑區時，數目減少一個；
• 當該空閑區上面或者下面有空閑區時，數目不變；

在分區配置設定方案中，回收一個分區時有幾種不同的鄰接情況，在各種情況下應如何處理？ 答：有四種：上鄰，下鄰，上下相鄰，上下不相鄰。

（1）回收分區的上鄰分區是空閑的，需要将兩個相鄰的空閑區合并成一個更大的空閑區，然後修改空閑區表。

（2）回收分區的下鄰分區是空閑的，需要将兩個相鄰的空閑區合并成一個更大的空閑區，然後修改空閑區表。

（3）回收分區的上、下鄰分區都是空閑的（空閑區個數為2），需要将三個空閑區合并成一個更大的空閑區（空閑區個數為1 ），然後修改空閑區表、

（4）回收分區的上、下鄰分區都不是空閑的，則直接将空閑區記錄在空閑區表中。

6，線程的狀态

1. 建立(new) ：新建立了一個線程對象。
2. 可運作(runnable) ：線程對象建立後，其他線程(比如main線程）調用了該對象的**start()**方法。該狀态的線程位于可運作線程池中，等待被線程排程選中，擷取cpu的使用權 。
3. 運作(running) ：可運作狀态( runnable) 的線程獲得了cpu 時間片（timeslice） ，執行程式代碼。

4. 阻塞(block) ：阻塞狀态是指線程因為某種原因放棄了cpu 使用權，也即讓出了cpu timeslice，暫時停止運作。直到線程進入 可運作(runnable) 狀态，才有機會再次獲得cpu timeslice 轉到 運作(running) 狀态。阻塞的情況分三種：

   (一). 等待阻塞： 運作(running) 的線程執行o.wait()方法，JVM會把該線程放入等待隊列(waitting queue)中。

   (二). 同步阻塞： 運作(running) 的線程在擷取對象的同步鎖時，若該同步鎖被别的線程占用，則JVM會把該線程放入鎖池(lock pool)中。

   (三). 其他阻塞： 運作(running) 的線程執行Thread.sleep(long ms)或t.join()方法，或者發出了I/O請求時，JVM會把該線程置為阻塞狀态。當sleep()狀态逾時、join()等待線程終止或者逾時、或者I/O處理完畢時，線程重新轉入 可運作(runnable) 狀态。

5. 死亡(dead) ：線程run()、main() 方法執行結束，或者因異常退出了run()方法，則該線程結束生命周期。死亡的線程不可再次複生。

7，線程的共享

在支援多線程的系統中，程序P建立的若幹個線程，其中可以共享的是：

• 程序P的代碼段
• 程序P中打開的檔案
• 程序P的全局變量

而程序P中某線程的棧指針是不能共享的。

8，信号量的表示

若信号量的初始值為2，目前值為-2，則表示等待的程序個數是多少個？

若信号量為正則表示資源數，若為負則其絕對值表示等待的程序數。

是以，此時等待的程序個數為2個。

9，死鎖小結

死鎖

定義：

在一個程序集合中，所有的程序都在等待隻能由該程序集合中的其它程序才能引發的事件，這就是死鎖

解釋：

由于程序集合中的所有程序都在等待集合中的其它程序引發喚醒該程序的事件，是以所有程序都會阻塞而無法向前推進。

一般大多數的等待事件都是釋放程序集合中其它程序所占有的資源，也叫資源死鎖。

資源死鎖的四大必須條件 ：

1，互斥條件：

每個資源要麼已經配置設定給了一個程序，要麼是可用的。即就是資源非共享。

2，占有和等待條件：

已經得到資源的程序還能繼續請求新的資源。

3，不可搶占條件:

當一個資源配置設定給了一個程序後，其它需要該資源的程序不能強制性獲得該資源，除非該資源的目前占有者顯示地釋放該資源。

4，環路等待：

死鎖發生時，系統中一定有由兩個或兩個以上的程序組成的一條環路，環路上的每個程序都在等待下一個程序所占有的資源。

死鎖預防：

防止死鎖的發生隻需破壞死鎖産生的四個必要條件之一即可。

1， 破壞互斥條件

如果允許系統資源都能共享使用，則系統不會進入死鎖狀态。但有些資源根本不能同時通路，如列印機等臨界資源隻能互斥使用。是以，破壞互斥條件而預防死鎖的方法不太可行，而且在有的場合應該保護這種互斥性。

2，破壞不剝奪條件

當一個已保持了某些不可剝奪資源的程序，請求新的資源而得不到滿足時，它必須釋放已經保持的所有資源，待以後需要時再重新申請。這意味着，一個程序已占有的資源會被暫時釋放，或者說是被剝奪了，或進而破壞了不可剝奪條件。

該政策實作起來比較複雜，釋放已獲得的資源可能造成前一階段工作的失效，反複地申請和釋放資源會增加系統開銷，降低系統吞吐量。這種方法常用于狀态易于儲存和恢複的資源，如CPU的寄存器及記憶體資源，一般不能用于列印機之類的資源。

3， 破壞請求和保持條件

釆用預先靜态配置設定方法，即程序在運作前一次申請完它所需要的全部資源，在它的資源未滿足前，不把它投入運作。一旦投入運作後，這些資源就一直歸它所有，也不再提出其他資源請求，這樣就可以保證系統不會發生死鎖。

這種方式實作簡單，但缺點也顯而易見，系統資源被嚴重浪費，其中有些資源可能僅在運作初期或運作快結束時才使用，甚至根本不使用。而且還會導緻“饑餓”現象，當由于個别資源長期被其他程序占用時，将緻使等待該資源的程序遲遲不能開始運作。

4，破壞循環等待條件

為了破壞循環等待條件，可釆用順序資源配置設定法。首先給系統中的資源編号，規定每個程序，必須按編号遞增的順序請求資源，同類資源一次申請完。也就是說，隻要程序提出申請配置設定資源Ri，則該程序在以後的資源申請中，隻能申請編号大于Ri的資源。

這種方法存在的問題是，編号必須相對穩定，這就限制了新類型裝置的增加；盡管在為資源編号時已考慮到大多數作業實際使用這些資源的順序，但也經常會發生作業使用資源的順序與系統規定順序不同的情況，造成資源的浪費；此外，這種按規定次序申請資源的方法，也必然會給使用者的程式設計帶來麻煩。

死鎖避免

避免死鎖同樣是屬于事先預防的政策，但并不是事先釆取某種限制措施破壞死鎖的必要條件，而是在資源動态配置設定過程中，防止系統進入不安全狀态，以避免發生死鎖。這種方法所施加的限制條件較弱，可以獲得較好的系統性能。

1，系統安全狀态

避免死鎖的方法中，允許程序動态地申請資源，但系統在進行資源配置設定之前，應先計算此次資源配置設定的安全性。若此次配置設定不會導緻系統進入不安全狀态，則将資源配置設定給程序； 否則，讓程序等待。

所謂安全狀态，是指系統能按某種程序推進順序( P1, P2, …, Pn)，為每個程序Pi配置設定其所需資源，直至滿足每個程序對資源的最大需求，使每個程序都可順序地完成。此時稱 P1, P2, …, Pn 為安全序列。如果系統無法找到一個安全序列，則稱系統處于不安全狀态。

并非所有的不安全狀态都是死鎖狀态，但當系統進入不安全狀态後，便可能進入死鎖狀态；反之，隻要系統處于安全狀态，系統便可以避免進入死鎖狀态。

1，銀行家算法

銀行家算法是最著名的死鎖避免算法。它提出的思想是：把作業系統看做是銀行家，作業系統管理的資源相當于銀行家管理的資金，程序向作業系統請求配置設定資源相當于使用者向銀行家貸款。作業系統按照銀行家制定的規則為程序配置設定資源，當程序首次申請資源時，要測試該程序對資源的最大需求量，如果系統現存的資源可以滿足它的最大需求量則按目前的申請量配置設定資源，否則就推遲配置設定。當程序在執行中繼續申請資源時，先測試該程序已占用的資源數與本次申請的資源數之和是否超過了該程序對資源的最大需求量。若超過則拒絕配置設定資源，若沒有超過則再測試系統現存的資源能否滿足該程序尚需的最大資源量，若能滿足則按目前的申請量配置設定資源，否則也要推遲配置設定。

死鎖檢測

前面紹的死鎖預防和避免算法，都是在為程序配置設定資源時施加限制條件或進行檢測，若系統為程序配置設定資源時不釆取任何措施，則應該提供死鎖檢測和解除的手段。

資源配置設定圖：

系統死鎖，可利用資源配置設定圖來描述。如上圖所示，用圓圈代表一個程序，用框代表一類資源。由于一種類型的資源可能有多個，用框中的一個點代表一類資源中的一個資源。從程序到資源的有向邊叫請求邊，表示該程序申請一個機關的該類資源；從資源到程序的邊叫配置設定邊，表示該類資源已經有一個資源被配置設定給了該程序。

在上圖所示的資源配置設定圖中，程序P1已經分得了兩個R1資源，并又請求一個R2 資源；程序P2分得了一個R1和一個R2資源，并又請求一個R1資源。

可以通過将資源配置設定圖簡化的方法來檢測系統狀态S是否為死鎖狀态。簡化方法如下：

1. 在資源配置設定圖中，找出既不阻塞又不是孤點的程序Pi（ 即找出一條有向邊與它相連，且該有向邊對應資源的申請數量小于等于系統中已有空閑資源數量。若所有的連接配接該程序的邊均滿足上述條件，則這個程序能繼續運作直至完成，然後釋放它所占有的所有資源） 。消去它所有的請求邊和配置設定邊，使之成為孤立的結點。在圖(a)中，P1是滿足這一條件的程序結點，将P1的所有邊消去，便得到圖(b)所示的情況。
2. 程序Pi所釋放的資源，可以喚醒某些因等待這些資源而阻塞的程序，原來的阻塞程序可能變為非阻塞程序。在上圖中，程序P2就滿足這樣的條件。根據第1) 條中的方法進行一系列簡化後,若能消去圖中所有的邊，則稱該圖是可完全簡化的，如圖©所示。

   

S為死鎖的條件是當且僅當S狀态的資源配置設定圖是不可完全簡化的，該條件為死鎖定理。

死鎖解除

一旦檢測出死鎖，就應立即釆取相應的措施，以解除死鎖。死鎖解除的主要方法有：

1，資源剝奪法。挂起某些死鎖程序，并搶占它的資源，将這些資源配置設定給其他的死鎖程序。但應防止被挂起的程序長時間得不到資源，而處于資源匮乏的狀态。

2，撤銷程序法。強制撤銷部分、甚至全部死鎖程序并剝奪這些程序的資源。撤銷的原則可以按程序優先級和撤銷程序代價的高低進行。

3，程序回退法。讓一個或多個程序回退到足以回避死鎖的地步，程序回退時自願釋放資源而不是被剝奪。要求系統保持程序的曆史資訊，設定還原點。

10，程序間通信

UNIX中有如下的通信方式：

1. 檔案和記錄鎖定

   為避免兩個程序間同時要求通路同一共享資源而引起通路和操作的混亂，在程序對共享資源進行通路前必須對其進行鎖定，該程序通路完後再釋放。這是UNIX為共享資源提供的互斥性保障。

2. 管道

   管道一般用于兩個不同程序之間的通信。當一個程序建立一個管道，并調用fork建立自己的一個子程序後，父程序關閉讀管道端，子程序關閉寫管道端，這樣提供了兩個程序之間資料流動的一種方式。

3. FIFO

   FIFO是一種先進先出的隊列。它類似于一個管道，隻允許資料的單向流動。每個FIFO都有一個名字，允許不相關的程序通路同一個FIFO。是以也成為命名管。

4. 消息隊列

   UNIX下不同程序之間可實作共享資源的一種機制；UNIX允許不同程序将格式化的資料流以消息形式發送給任意程序。對消息隊列具有操作權限的程序都可以使用msget完成對消息隊列的操作控制。通過使用消息類型，程序可以按任何順序讀消息，或為消息安排優先級順序。

5. 信号燈

   作為程序間通訊的一種方法，它不是用于交換大批資料，而用于多程序之間的同步（協調對共享存儲段的存取）。

6. 共享記憶體

   通過信号燈實作存儲共享（類似“紅燈停、綠燈行”）

10，i++與雙線程

i++在兩個線程裡邊分别執行100次，能得到的最大值和最小值分别是多少？

i++隻需要執行一條指令，并不能保證多個線程i++，操作同一個i，可以得到正确的結果。因為還有寄存器的因素，多個cpu對應多個寄存器。每次要先把i從記憶體複制到寄存器，然後++，然後再把i複制到記憶體中，這需要至少3步。從這個意義上講，i++不能算做是原子操作。

當CPU是多核時，最小值為2，最大值為200。

如此，假設兩個線程的執行步驟如下：

1. 線程A執行第一次i++，取出記憶體中的i，值為0，存放到寄存器後執行加1，此時CPU1的寄存器中值為1，記憶體中為0；
2. 線程B執行第一次i++，取出記憶體中的i，值為0，存放到寄存器後執行加1，此時CPU2的寄存器中值為1，記憶體中為0；
3. 線程A繼續執行完成第99次i++，并把值放回記憶體，此時CPU1中寄存器的值為99，記憶體中為99；
4. 線程B繼續執行第一次i++，将其值放回記憶體，此時CPU2中的寄存器值為1，記憶體中為1；
5. 線程A執行第100次i++，将記憶體中的值取回CPU1的寄存器，并執行加1，此時CPU1的寄存器中的值為2，記憶體中為1；
6. 線程B執行完所有操作，并将其放回記憶體，此時CPU2的寄存器值為100，記憶體中為100；
7. 線程A執行100次操作的最後一部分，将CPU1中的寄存器值放回記憶體，記憶體中值為2；
8. 結束！

當CPU單核時，最小值是100，最大值為200。

兩個線程分别記為線程1和線程2，i++相當于取出i的值，加1，再放回去

第一種極端情況：每次線程一取出i的值後CPU時間切換到線程二，線程二也取出i的值，取到的值和線程一相等，線程二給i加一後放回去，線程一也将i加一後放回去，放回去的值也相等，相當于兩個線程都執行一次i++操作，i的值隻增加1，這樣操作100次i的值為100。

第二種極端情況：線程一和線程二間隔操作，即線程一對i++操作完成，把已經加一的資料放回去之後線程二再操作，輪流進行，最後每個線程都對i加了100次，i的值為200。

11，裝置配置設定政策

與裝置配置設定政策有關的因素有：

• 裝置固有屬性
• 裝置配置設定算法
• 裝置配置設定的安全性
• 裝置額獨立性

12，頁面置換算法的缺頁率

• FIFO：先進先出算法，這種排程算法最簡單，缺頁率最高。
• OPT：理想型淘汰算法（optimal replacement algorithm），該算法淘汰在通路串中将來再也不出現的或者在離目前最遠的位置上出現的頁，遺憾的是，這種算法無法實作，因為它要求必須預先知道每一個程序的通路串。
• LRU：最近最久未使用算法（least recently used），當需要淘汰某一頁時，選擇離目前時間最近的一段時間内最久沒有使用過的頁先淘汰。

13，PCB中的資訊

存放程序的管理和控制資訊的資料結構稱為程序控制塊（PCB）。

它是程序管理和控制的最重要的資料結構，每一個程序均有一個PCB，在建立程序時，建立PCB，伴随程序運作的全過程，直到程序撤消而撤消。

在不同的作業系統中對程序的控制和管理機制不同，PCB中的資訊多少也不一樣，通常PCB應包含如下一些資訊：

1、程序辨別符 name：

每個程序都必須有一個唯一的辨別符，可以是字元串，也可以是一個數字。UNIX系統中就是一個整型數。在程序建立時由系統賦予。

2、程序目前狀态 status：

說明程序目前所處的狀态。為了管理的友善，系統設計時會将相同的狀态的程序組成一個隊列，如就緒程序隊列，等待程序則要根據等待的事件組成多個等待隊列，如等待列印機隊列、等待磁盤I/O完成隊列等等。

3、程序相應的程式和資料位址：

以便把PCB與其程式和資料聯系起來。

4、程序資源清單：

列出所擁有的除CPU外的資源記錄，如擁有的I/O裝置，打開的檔案清單等。

5、程序優先級 priority：

程序的優先級反映程序的緊迫程式，通常由使用者指定和系統設定。UNIX系統采用使用者設定和系統計算相結合的方式确定程序的優先級 。

6、CPU現場保護區 cpustatus：

當程序因某種原因不能繼續占用CPU時（等待列印機），釋放CPU，這時就要将CPU的各種狀态資訊保護起來，為将來再次得到處理機恢複CPU的各種狀态，繼續運作。

7、程序同步與通信機制：

用于實作程序間互斥、同步和通信所需的信号量等。

8、程序所在隊列PCB的連結字：

根據程序所處的現行狀态，程序相應的PCB參加到不同隊列中。PCB連結字指出該程序所在隊列中下一個程序PCB的首位址。

9、與程序有關的其他資訊。：

如程序記賬資訊，程序占用CPU的時間等

14，程序優先級

确定程序優先級的三個方面：

1. 程序類型，系統程序（如接受程序，對換程序，磁盤I/o程序）的優先權高于一般使用者程序的優先權。
2. 程序對資源的需求，程序估計執行時間及記憶體需要量少的程序應賦予較高優先權。
3. 使用者要求。

一般來說，計算程序會占用大量的cpu時間，而i/o大的會占用較少的cpu資源，相當于短作業，是以應該優先權更高。

15，寄存器、頁号與分塊

某頁式存儲管理系統中，位址寄存器長度為24位，其中頁号占14位，則主存的分塊大小是多少位元組？

位址寄存器長度為24位，其中頁号占14位，則頁内位址占10位，分頁大小與主存塊大小相同，是以， 主存的分塊大小是210位元組。

16，線程相關

對于線程而言：

• 線程不擁有系統資源，但是可以擁有一點運作時必不可少的資源（比如線程棧），但它可以使用所屬程序的資源。
• 由于同一程序中的多個線程共享該程序的位址空間，是以它們間的同步和通信也易于實作。
• 程序建立與線程建立以及程序切換與線程切換的時空開銷并不相同。

17，信号量

信号量是表示資源的實體量，它隻能供P操作和V操作使用，利用信号量S的取值表示共享資源的使用情況，或用它來訓示程序之間交換的資訊。在具體使用中，把信号量S放在程序運作的環境中，賦予其不同的初值，并在其上實施P操作和V操作，以實作程序間的同步和互斥。P、V操作是定義在信号量S上的兩個操作原語：

P(S)：

(1) S←S-1；

(2) 若S≥0，則調用P(S)的這個程序繼續被執行；

(3) 若S＜0，則調用P(S)的這個程序被阻塞，并将其插入到等待信号量S的阻塞隊列中。

V(S)：

(1) S←S+1；

(2) 若S＞0，則調用P(S)的這個程序繼續被執行；

(3) 若S≤0，則先從等待信号量S的阻塞隊列中喚醒隊首程序，然後調用V(S)的這個程序繼續執行。

信号量S＞0時的數值表示某類資源的可用數量，執行P操作意味着申請配置設定一個機關的資源，故執行S減l操作，若減1後S＜0，則表示無資源可用，這時S的絕對值表示信号量S對應的阻塞隊列中程序個數。執行一次V操作則意味着釋放一個單元的資源，故執行S增1操作，若增1後S≤0，則表示信号量S的阻塞隊列中仍有被阻塞的程序，故應喚醒該隊列上的第一個阻塞程序。

信号量大于0 表示該資源的可用數目

信号量小于0 表示等待該資源的程序數為絕對值的s

信号量等于0 表示該時刻系統中既沒有剩餘該資源可以利用也沒有等待該資源的程序

• 對于記錄型信号量，當 s<0 的時候，請求程序會阻塞；s=0，表示資源全部用完，沒有程序阻塞。
• 對于整型信号量，當s<=0的時候，請求程序不會阻塞，而是進入盲等狀态。

18，資訊表

作業系統為了管理程序和資源，需要構造和維護的資訊表有：

• I/O表
• 檔案表
• 記憶體表
• 程序表

19，臨界區

臨界區：每個程序中通路臨界資源的那段程式叫做臨界區。

程序對臨界區的通路必須互斥，每次隻允許一個程序進去臨界區，其他程序等待

20，内部碎片與外部碎片

在記憶體管理中：

• 内部碎片是已經被配置設定出去的的記憶體空間大于請求所需的記憶體空間。
• 外部碎片是指還沒有配置設定出去，但是由于大小太小而無法配置設定給申請空間的新程序的記憶體空間空閑塊。

存在内部碎片	存在外部碎片
固定分區	可變式分區
頁式虛拟存儲系統	段式虛拟存儲系統

為了有效的利用記憶體，使記憶體産生更少的碎片，要對記憶體分頁，記憶體以頁為機關來使用，最後一頁往往裝不滿，于是形成了内部碎片。 為了共享要分段，在段的換入換出時形成外部碎片，比如5K的段換出後，有一個4k的段進來放到原來5k的地方，于是形成1k的外部碎片。