進程的三態模型細分進程狀態圖進程的通信互斥：一次只能供一個進程使用的資源。同步：多個進程併發進行，可能需要等待。生產者與消費者 PV操作 PV操作是實現進程同步與互斥的常用方法，在執行期間不可分割。P代表申請一個資源，V代表釋放一個資源。 P操作定義：S1:=S1-1，若S>=0，則P操... ...

進程的三態模型

細分進程狀態圖

進程的通信

互斥：一次只能供一個進程使用的資源。

同步：多個進程併發進行，可能需要等待。

生產者與消費者

PV操作

PV操作是實現進程同步與互斥的常用方法，在執行期間不可分割。P代表申請一個資源，V代表釋放一個資源。

P操作定義：S1:=S1-1，若S>=0，則P操作繼續進行；若S<0，則置該進程為阻塞狀態（因為無資源可用），並將其插入阻塞隊列。

V操作定義：S2:=S2+1，若S>0，則V操作繼續進行；若S<=0，則從阻塞狀態喚醒一個進程，並將其插入就緒隊列，然後執行V操作的進程繼續。

信號量S：信號量的值表示相應資源的使用情況。所謂信號燈，實際上就是用來控制進程狀態的一個代表某一資源的存儲單元。信號量S>=0時，S表示可用資源的數量。執行一次P操作意味著請求分配一個資源，因此S的值減1；當S<0時，表示已經沒有可用資源，S的絕對值表示當前等待該資源的進程數。請求者必須等待其他進程釋放該類資源，才能繼續運行。而執行一個V操作意味著釋放一個資源，因此S的值加1；若S<=0，表示有某些進程正在等待該資源，因此要喚醒一個等待狀態的進程，使之運行下去。

臨界資源：多道程式系統環境中，各進程可以共用各類資源，但有些資源只能供一個進程使用，稱為臨界資源，如印表機、共用變數等。

臨界區：進程中對臨界資源實施操作的那段程式。

例如：設公交車司機的活動是啟動車輛，正常行車，到站停車；售票員的活動是關車門，售票，開車門，用信號量PV操作來實現他們的同步。

解析：

設置S1=0，S2=0。

司機進程：P(S1)；啟動車輛；正常行駛；到站停車；V(S2)；

售票員進程：關車門；V(S1)；售票；P(S2)；開車門；

首先，售票員執行關車門（V操作S1+1）；然後，司機執行啟動車輛（P操作S1-1）；第三步，司機停車（V操作S1+1），第四步，售票員開車門（P操作S2-1）。

若用PV操作控制進程P1,P2,P3,P4和P5併發執行的過程，需要設置5個信號量S1,S2,S3,S4和S5，且信號量S1~S5的初始值都等於零。如下的執行圖中a和b處應分別填寫（1），c和d出應分別填寫（2），e和f處應分別填寫（3）。

（1）P(S1)和V(S2)、V(S3)

（2）P(S2)和V(S4)

（3）P(S3)P(S4)和V(S5)

死鎖

電腦系統中的互斥資源，如兩個進程同時使用印表機，或同時進入臨界區必然會出現的問題。所謂死鎖是指兩個以上的進程互相都要求對方已經占有的資源導致無法繼續進行下去的現象。

如：系統有3個進程A、B、C，這3個進程都需要5個系統資源，那麼系統至少有多少個資源才不會發生死鎖。

解析：所有進程分配滿足需要的資源數減1，然後增加一個資源分配任意一個進程即可滿足條件，即3*4+1=13。

銀行家演算法

1、對於進程發出的每一個系統可以滿足的資源請求命令加以檢測，如果發現分配資源後系統進入不安全狀態，則不予分配。

2、若分配資源後系統仍處於安全狀態，則實施分配。

3、與死鎖預防相比，提高了資源利用率，但檢測分配後系統是否安全增加了系統開銷。

假設系統中有三類互斥資源R1、R2、R3，可用資源數分別是9、8、5。在T0時刻系統中有P1、P2、P3、P4、P5進程，這些進程對資源的最大需求量和已分配資源數如下圖，如果進程按（）序列執行，那麼系統狀態是安全的。

解析：

已分配資源數R1:7，R2:7，R3:5。

剩餘資源數：R1:2，R2:1，R3:0。

P1進程還需資源數：R1:5，R2:3，R3:1。

P2進程還需資源數：R1:0，R2:1，R3:0。

P3進程還需資源數：R1:6，R2:0，R3:1。

P4進程還需資源數：R1:0，R2:0，R3:1。

P5進程還需資源數：R1:2，R2:3，R3:1。

釋放的資源數量為：現有資源數+已經分配資源數

為防止死鎖進程執行順序為：P2àP4àP5àP1àP3

分區存儲管理

（1）固定分區

（2）可變分區

假設電腦系統的記憶體大小為128K，採用可變分區分配方式進行記憶體分配，當前系統記憶體分塊情況如下圖所示，現有作業4申請9K記憶體，不同分配方式產生的結果？

迴圈首次適應法

（3）可重定位分區

頁式存儲管理

段式存儲管理

段頁式存儲

最好的提高了主存利用率。

局部性原理

（1）時間局部性

int i,a = 0;
for(i=1;i<100;i++){
for(j=1;j<100;j++){
a+=j
}
}
printf("結果為":%d,a)

（2）空間局部性

進程P有6個頁面，頁號分別為0~5，頁面大小為4K，頁面變換表如下所示。表中狀態位等於1和0分別表示頁面在記憶體和不在記憶體。假設系統給進程P分配了4個存儲塊，進程P要訪問的邏輯地址為十六進位1165H，那麼該地址經過變換後，其物理地址應為十六進位（）；如果進程P要訪問的頁面4不存在記憶體，那麼應該淘汰頁號為（）的頁面。

解析：4K=10¹²，即12位。邏輯地址1165H，其頁號為1，查頁表後知頁幀號為3，該地址經過變換後，其物理地址應為頁幀號3拼上頁內地址165H，即十六進位3165H。

系統應該首先淘汰未被訪問的頁面，因為根據程式的局部性原理，最近被訪問的相鄰頁面下次被訪問的概率更大，所以應該淘汰5。

虛擬存儲

虛擬存儲是具有請求調入功能和置換功能，僅能把作業的一部分裝入主存便可運行作業的存儲系統。

（1）請求分頁系統。

（2）請求分段系統。

（3）請求段頁式系統。

缺頁中斷

在一臺按位元組編址的8位電腦系統中，採用虛擬頁式存儲管理方案，頁面的大小為1KB，且系統中沒有使用塊表（或聯想存儲器）。圖示的是劃分成6個頁面的用戶程式。圖中swap指令放在記憶體的1023單元中，操作數A存放在記憶體的3071單元中，操作數B存放在記憶體的5119單元中。執行swap指令將產生（）次缺頁中斷。

解析：指令只產生一次中斷，A產生2次，B產生2次，共計5次。

頁面置換演算法

（1）最佳置換演算法

（2）先進先出（FIFO）置換演算法

（3）最近最少未使用（LRU）置換演算法

（4）最近未用（NRU）置換演算法

設備管理技術

（1）通道技術

（2）DMA技術

（3）緩衝技術

（4）Spooling技術

文件的物理結構

（1）連續結構

（2）鏈接結構

（3）索引結構

（4）多個物理塊的索引結構

文件目錄

在下圖所示的樹型文件系統中，方框表示目錄，圓圈表示文件，"/"表示路徑中的分隔符，"/"在路徑之首時表示根目錄。

假設當前目錄是D2，進程A以如下兩種方式打開文件f2。

方式j fd1=open("____/f2",O_RDONLY);

方式k fd1=open("/D2/W2/f2",O_RDONLY);

其中，方式j的工作效率比方式k的工作效率高，因為採用方式j，文件系統是從____。

解析：

（1）相對路徑W2。

（2）當前路徑開始查找文件f2，系統查找時間少，讀取f2文件次數不變。

文件存儲空間管理

（1）空閑區表

（2）位示圖

位示圖是利用二進位的一位來表示磁碟中的一個盤塊的使用情況。當其值為"0"時，表示對應的盤塊空閑；為"1"時，表示已經分配。有的系統把"0"作為盤塊已分配的標記，把"1"作為空閑標誌。（它們的本質上是相同的，都是用一位的兩種狀態標誌空閑和已分配兩種情況。）磁碟上的所有盤塊都有一個二進位與之對應，這樣，由所有盤塊所對應的位構成一個集合，稱為位示圖。

某文件管理系統在磁碟上建立了位示圖（bitmap），記錄磁碟的使用情況。若磁碟上的物理塊依次編號為0,1,2,…，系統中字長32位，每一位對應文件存儲器上的一個物理塊，取值0和1分別表示空閑和占用，如下圖所示。

假設將4195號物理塊分配給某文件，那麼該物理塊的使用情況在位示圖中的第（）個字中描述，系統應該將該字的第（）位置1。

解析：

（a）(4195-0+1)/32=131.125=第132字

（b）131*32=4192，即0~4191塊，第0位4192，第1位4193，第2位4194，第三位4195。

某字長為32位的電腦的文件管理系統採用位示圖（bitmap）記錄磁碟的使用情況。若磁碟的容量為300GB，物理塊的大小為1MB，那麼位示圖的大小為（）個字。

解析：300G/32MB=9600

（3）空閑塊鏈

（4）成組鏈接法

操作系統知識