第二章操作系統(tǒng)復(fù)習(xí)要點(diǎn)

本章每次約3題

一、資源互斥（PV）

信號(hào)量包含兩類，一類是公用信號(hào)量，他實(shí)現(xiàn)進(jìn)程間的互斥，初值為1或資源數(shù)目；另一類是私用信號(hào)量，它實(shí)現(xiàn)進(jìn)程間的同步，初值為0或某個(gè)正數(shù)。

• PV操作是對(duì)信號(hào)量的操作

• P是給信號(hào)量減1、V是給信號(hào)量+1

• P操作的是自己的私有信號(hào)量、V是操作別人的私有信號(hào)量、公有信號(hào)量每個(gè)進(jìn)程的PV都能操作

二、進(jìn)程管理

三態(tài)模型

• 就緒狀態(tài)：就是“萬(wàn)事俱備只欠東風(fēng)”的狀態(tài)，進(jìn)程已得到運(yùn)行所需資源，只等待cpu的調(diào)度便可運(yùn)行。

• 運(yùn)行狀態(tài)：進(jìn)程已得到運(yùn)行所需資源，并且得到了cpu的調(diào)度。

• 等待狀態(tài)：不具備運(yùn)行條件，等待時(shí)機(jī)的狀態(tài)，也叫阻塞狀態(tài)

引起進(jìn)程狀態(tài)轉(zhuǎn)換的具體原因：

（1）運(yùn)行態(tài)->等待態(tài)。等待使用資源；如等待外設(shè)傳輸；等待人工干預(yù)

（2）等待態(tài)->就緒態(tài)。資源得到滿足；如外設(shè)傳輸結(jié)束；人工干預(yù)完成。

（3）運(yùn)行態(tài)->就緒態(tài)。運(yùn)行時(shí)間片到；出現(xiàn)更高優(yōu)先權(quán)進(jìn)程。

（4）就緒態(tài)->運(yùn)行態(tài)。CPU空閑時(shí)選擇一個(gè)就緒進(jìn)程。

五態(tài)模型

（1）活躍阻塞態(tài)->靜止阻塞態(tài)。如果當(dāng)前不存在活躍就緒進(jìn)程，那么至少有一個(gè)等待進(jìn)程將被對(duì)換出來(lái)成為靜止阻塞態(tài)；操作系統(tǒng)根據(jù)當(dāng)前資源狀況和性能要求，可以決定把活躍阻塞態(tài)進(jìn)程對(duì)換出去成為靜止阻塞態(tài)。

（2）靜止阻塞態(tài)->靜止就緒態(tài)。引起進(jìn)程等待的事件發(fā)生之后，相應(yīng)的靜止阻塞態(tài)進(jìn)程將轉(zhuǎn)換為靜止就緒態(tài)。

（3）靜止就緒態(tài)->活躍就緒態(tài)。如果內(nèi)存中沒(méi)有活躍就緒態(tài)進(jìn)程，或者靜止就緒態(tài)進(jìn)程具有比活躍就緒態(tài)進(jìn)程更高的優(yōu)先級(jí)，系統(tǒng)將把靜止就緒態(tài)進(jìn)程轉(zhuǎn)換成活躍就緒態(tài)。

（4）活躍就緒態(tài)->靜止就緒態(tài)。操作系統(tǒng)根據(jù)當(dāng)前資源狀況和性能要求也可以決定把活躍就緒態(tài)進(jìn)程對(duì)換出去成為靜止就緒態(tài)。

（5）靜止阻塞態(tài)->活躍阻塞態(tài)。當(dāng)一個(gè)進(jìn)程等待一個(gè)事件時(shí)，原則上不需要把它調(diào)入內(nèi)存。但當(dāng)一個(gè)進(jìn)程退出后，主存已經(jīng)有了一大塊自由空間，而某個(gè)靜止阻塞態(tài)進(jìn)程具有較高優(yōu)先級(jí)，并且操作系統(tǒng)已經(jīng)得知導(dǎo)致它阻塞的事件即將結(jié)束，此時(shí)便發(fā)生這一狀態(tài)變化

三、資源安全

資源數(shù)（安全的）= 互斥進(jìn)程數(shù)X（每個(gè)進(jìn)程所需最大資源數(shù)-1）+1

如果題目給出的資源數(shù)不是安全的，則有產(chǎn)生死鎖的可能

四、磁盤讀寫時(shí)間、序列相關(guān)

讀取磁盤需要3個(gè)參數(shù)：柱面號(hào)、磁頭號(hào)（盤面號(hào)）、扇區(qū)號(hào)。

讀取順序：先根據(jù)柱面號(hào)找柱面->選定磁頭->找扇區(qū)

存取時(shí)間=尋道時(shí)間+等待時(shí)間

處理時(shí)間=等待時(shí)間+記錄處理時(shí)間

(記錄處理最少等待時(shí)間=0，最長(zhǎng)等待時(shí)間=磁盤旋轉(zhuǎn)周期N ms/周*記錄道數(shù))

移動(dòng)道數(shù)(或扇區(qū))=目標(biāo)磁道(或扇區(qū))-當(dāng)前磁道(或扇區(qū))

尋道時(shí)間=移動(dòng)道數(shù)*每經(jīng)過(guò)一磁道所需時(shí)間

等待時(shí)間=移動(dòng)扇區(qū)數(shù)*每轉(zhuǎn)過(guò)一扇區(qū)所需時(shí)間

讀取時(shí)間=目標(biāo)的塊數(shù)*讀一塊數(shù)據(jù)的時(shí)間

數(shù)據(jù)讀出時(shí)間=等待時(shí)間+尋道時(shí)間+讀取時(shí)間

平均等待時(shí)間=磁盤旋轉(zhuǎn)一周所用時(shí)間的一半

(自由選擇順逆時(shí)鐘時(shí)，最長(zhǎng)等待時(shí)間為半圈，最短為無(wú)須旋轉(zhuǎn))

平均等待時(shí)間=(最長(zhǎng)時(shí)間+最短時(shí)間)/2

平均尋道時(shí)間=(最大磁道的平均最長(zhǎng)尋道時(shí)間+最短時(shí)間)/2

最大磁道的平均最長(zhǎng)尋道時(shí)間=(最長(zhǎng)外徑+圓心)/2

位示圖計(jì)算物理塊

物理塊的編號(hào)從0開(kāi)始，實(shí)際物理塊=物理塊號(hào)+1（例4195號(hào)物理塊其實(shí)是第4196塊）

字長(zhǎng)與物理塊的關(guān)系：設(shè)字長(zhǎng)為32位，也就是說(shuō)每個(gè)字可以記錄32個(gè)物理塊的使用情況，4196/32=131.125,也就是說(shuō)4195號(hào)物理塊應(yīng)該是在第131個(gè)字中。到第130個(gè)字為止，共保存了131*32=4192個(gè)物理塊(0～4191)，所以，第4195塊應(yīng)該在第131個(gè)字的第3位記錄(要注意：0是最開(kāi)始的位)。

五、頁(yè)式存儲(chǔ)管理

基本思路：把物理內(nèi)存劃分為許多固定大小的內(nèi)存塊，稱為物理頁(yè)面；把邏輯地址空間也劃分為大小相同的塊，稱為邏輯頁(yè)面。當(dāng)一個(gè)用戶程序被裝入內(nèi)存時(shí)，不是以整個(gè)程序?yàn)閱挝?，把它存放在一整塊連續(xù)的區(qū)域，而是以頁(yè)面為單位來(lái)進(jìn)行分配的。對(duì)于一個(gè)大小為N的頁(yè)面程序，需要有N個(gè)空閑的物理頁(yè)面來(lái)把它裝載。這些物理頁(yè)面不一定是要連續(xù)的。

在頁(yè)式存儲(chǔ)管理中需要解決三個(gè)問(wèn)題：數(shù)據(jù)結(jié)構(gòu)、內(nèi)存分配與回收、地址映射。

數(shù)據(jù)結(jié)構(gòu)有兩個(gè)：頁(yè)表和物理頁(yè)面表。

• 頁(yè)表：給出了任務(wù)邏輯頁(yè)面號(hào)和內(nèi)存中物理頁(yè)面號(hào)之間的對(duì)應(yīng)關(guān)系。

• 物理頁(yè)面表：描述內(nèi)存空間中，各個(gè)物理頁(yè)面的使用情況。

內(nèi)存的分配過(guò)程：

• 對(duì)于一個(gè)新來(lái)的任務(wù)，計(jì)算它所需要的頁(yè)面數(shù)N，然后查看位示圖，看是否還有N個(gè)空閑的物理頁(yè)面。

• 如果有足夠的空閑物理頁(yè)面，就去申請(qǐng)一個(gè)頁(yè)表，其長(zhǎng)度為N，并把頁(yè)表的起始地址填入到該任務(wù)的控制塊中。

• 分配N個(gè)空閑的物理頁(yè)面，把他們的變換填到頁(yè)表中，建立邏輯頁(yè)面與物理頁(yè)面直接的對(duì) 應(yīng)關(guān)系。

• 修改位示圖，對(duì)剛剛被占用的那些物理頁(yè)面進(jìn)行標(biāo)記。

地址映射的基本思路：

• 邏輯地址分析：對(duì)邏輯地址，找到它所在的邏輯頁(yè)面，以及它在頁(yè)面內(nèi)的偏移地址。

• 頁(yè)表查找：根據(jù)邏輯頁(yè)面號(hào)，從頁(yè)表中找出它對(duì)應(yīng)的物理頁(yè)面號(hào)。

• 物理地址合成：根據(jù)物理頁(yè)面號(hào)和頁(yè)內(nèi)偏移地址，最終確定物理地址。

邏輯地址分析：頁(yè)面的大小都是2的整數(shù)次冪。對(duì)于給定的一個(gè)邏輯地址，可以直接把它的高位部分作為邏輯頁(yè)面號(hào)，把它的低位部分作為頁(yè)內(nèi)偏移地址。例如，假設(shè)頁(yè)面的大小是4KB，即2的12次冪，邏輯地址為32為，那么在一個(gè)邏輯地址當(dāng)中，最低12位為頁(yè)內(nèi)偏移地址，而剩下的20位就是邏輯頁(yè)面號(hào)。

計(jì)算方法：

• 邏輯頁(yè)面號(hào)＝邏輯地址/頁(yè)面大小

• 頁(yè)內(nèi)偏移量＝邏輯地址％頁(yè)面大小

頁(yè)表查找：

頁(yè)表作為操作系統(tǒng)的一個(gè)數(shù)據(jù)結(jié)構(gòu)，通常保存在內(nèi)核的地址空間中。

頁(yè)表基地址寄存器用來(lái)指向頁(yè)表的起始地址；頁(yè)表長(zhǎng)度寄存器用來(lái)指示頁(yè)表的大小，即對(duì)于當(dāng)前任務(wù)，它總共包含有多少個(gè)頁(yè)面。

物理地址合成：

假設(shè)物理頁(yè)面號(hào)為f，頁(yè)內(nèi)偏移地址為offset，每個(gè)頁(yè)面大小為2的n次方，那么相應(yīng)的物理地址為：f×（2的n次方）+offset。