基本構(gòu)成

• 處理器（CPU），由控制器，運(yùn)算器，一組寄存器組成

• 主存儲器（只讀：ROM，隨機(jī)存取：RAM）

• 輸入輸出模塊

• 系統(tǒng)總線

操作系統(tǒng)的特征

• 并發(fā)性，共享性，隨機(jī)性

操作系統(tǒng)的功能

• 文件管理
• 進(jìn)程調(diào)度
• 用戶接口

程序順序執(zhí)行的特征

• 順序性，封閉性，可再現(xiàn)性

作業(yè)吞吐量：所完成作業(yè)的數(shù)量/給定的時(shí)間間隔

CPU利用率：所完成作業(yè)的時(shí)間/給定的時(shí)間間隔

進(jìn)程與程序的區(qū)別

• 動(dòng)態(tài)性，并發(fā)性，非對應(yīng)性，異步性

進(jìn)程的基本特征

• 動(dòng)態(tài)性，并發(fā)性，調(diào)度性

進(jìn)程的狀態(tài)

• 新建狀態(tài)，就緒狀態(tài)，運(yùn)行狀態(tài)，阻塞狀態(tài)，終止?fàn)顟B(tài)

進(jìn)程映像

• 程序，數(shù)據(jù)集合，棧，進(jìn)程控制塊（進(jìn)程描述塊，PCB（進(jìn)程的唯一標(biāo)識））

進(jìn)程的控制

• 進(jìn)程阻塞：運(yùn)行狀態(tài)轉(zhuǎn)等待狀態(tài)（等待某事件發(fā)生）
• 進(jìn)程喚醒：等待狀態(tài)轉(zhuǎn)就緒狀態(tài)
• 進(jìn)程創(chuàng)建：新建進(jìn)程轉(zhuǎn)就緒狀態(tài)
• 進(jìn)程調(diào)度：就緒狀態(tài)轉(zhuǎn)運(yùn)行狀態(tài)（分配CPU）

進(jìn)程通信

• 低級：互斥和同步機(jī)構(gòu)
• 高級：共享存儲，管道文件，消息傳遞

線程的組成

• 線程標(biāo)識符，調(diào)度狀態(tài)信息，核心棧指針，用戶棧指針，私有存儲區(qū)

線程與進(jìn)程的比較

• 調(diào)度單位：進(jìn)程是資源分配的基本單位，線程作為調(diào)度和分派的基本單位
• 資源分配給進(jìn)程，進(jìn)程的所有線程共享該資源

調(diào)度的層次

• 高級調(diào)度（作業(yè)調(diào)度）：分配內(nèi)存等資源，為進(jìn)程活動(dòng)做準(zhǔn)備
• 中級調(diào)度（內(nèi)存調(diào)度，進(jìn)程掛起與對換）：將暫時(shí)不能運(yùn)行的進(jìn)程掛起
• 低級調(diào)度（進(jìn)程調(diào)度）：將CPU分派給就緒隊(duì)列的一個(gè)進(jìn)程，執(zhí)行頻繁

進(jìn)程調(diào)度的方式

• 非搶占方式：一直保持CPU到完成或者等待狀態(tài)
• 搶占方式：可被搶占

調(diào)度的基本準(zhǔn)則

• 周轉(zhuǎn)時(shí)間：完成時(shí)間減到達(dá)時(shí)間
• 平均周轉(zhuǎn)時(shí)間
• 帶權(quán)周轉(zhuǎn)時(shí)間：W=T（周轉(zhuǎn)時(shí)間）/R（運(yùn)行時(shí)間）
• 平均帶權(quán)周轉(zhuǎn)時(shí)間
• 就緒等待時(shí)間：在就緒隊(duì)列的等待時(shí)間
• 響應(yīng)時(shí)間：從輸入到首次響應(yīng)的時(shí)間

調(diào)度算法

• 先來先服務(wù)法（FCFS）（非搶占）
• 短作業(yè)優(yōu)先法（SJF）（非搶占）
• 最短剩余時(shí)間優(yōu)先法（SRTF）（搶占）
• 高響應(yīng)比優(yōu)先法（HRRF）（非搶占）
  • 在調(diào)度前要計(jì)算響應(yīng)比（1+等待時(shí)間/運(yùn)行時(shí)間），選擇高響應(yīng)比的作業(yè)運(yùn)行
• 優(yōu)先級法（PS）
  • 有搶占和非搶占，根據(jù)優(yōu)先級調(diào)用
• 時(shí)間片輪轉(zhuǎn)法（RR）（搶占）
  • 先按照FCFS排序，執(zhí)行一個(gè)時(shí)間片長度后當(dāng)前的加到隊(duì)尾，換下一個(gè)

進(jìn)程的關(guān)系

• 互斥，同步，通信、

臨界資源

• 一次只能被一個(gè)進(jìn)程使用的共享資源

臨界區(qū)（CS區(qū)）

• 在進(jìn)程中訪問臨界資源的那段程序

信號量

• 物理意義：S>=0時(shí)表示某資源的可用數(shù)，S<0時(shí)絕對值表示阻塞隊(duì)列的進(jìn)程數(shù)
• 組成：兩個(gè)成員組成的數(shù)據(jù)結(jié)構(gòu)，一個(gè)值為信號量的值（INT），另一個(gè)為指向PCB的指針
• 規(guī)定
• 信號量可被賦值，初始值不能為負(fù)數(shù)
• 只允許被P，V操作訪問和修改

P操作

V操作

產(chǎn)生死鎖的4個(gè)必要條件

死鎖的判斷

死鎖的處理策略

忽略死鎖條件

死鎖預(yù)防（靜態(tài)策略）

• 破壞互斥條件，破壞占有且等待條件，破壞不可搶占條件

死鎖避免（動(dòng)態(tài)策略）

• 安全狀態(tài)：進(jìn)程所需的資源不大于所有資源

• 不安全狀態(tài)是死鎖的必要條件，不是充分條件

• 拒絕分配資源法（銀行家算法）

  • 要求：

  • 必須說明自己的所需最大資源量
  • 只能一次一次的申請資源
  • 如已經(jīng)獲得資源的最大需求量，則要在規(guī)定時(shí)間內(nèi)使用完畢并歸還系統(tǒng)

  • 承諾：

  • 若一個(gè)進(jìn)程對資源的最大需求量沒有超過總量，則不能拒絕
  • 在接到資源請求時(shí)，有權(quán)阻塞該進(jìn)程，但保證在有限時(shí)間內(nèi)響應(yīng)

  • 單種銀行家算法

    Available：每類資源可用數(shù)量
    max：每個(gè)進(jìn)程對各類資源的最大需求
    allocation：當(dāng)前每個(gè)進(jìn)程分配到底各類資源數(shù)
    need：max-allocation
    work：當(dāng)前每類資源可用數(shù)
    finish：是否安全

    答題表格列序：work need allocation work+allocation finish

死鎖的檢測與恢復(fù)

邏輯空間：由程序中邏輯地址組成的范圍

內(nèi)存空間：內(nèi)存單元組成

重定位：程序裝入內(nèi)存時(shí)，把邏輯地址轉(zhuǎn)成內(nèi)存地址

單一分區(qū)存儲管理系統(tǒng)缺點(diǎn)：一次只能一個(gè)作業(yè)進(jìn)入內(nèi)存

動(dòng)態(tài)分區(qū)缺點(diǎn)：內(nèi)存利用率不高，有外部碎片

動(dòng)態(tài)分區(qū)分配算法：最先適應(yīng)，最佳適應(yīng)

可重定位分區(qū)分配算法

• 時(shí)機(jī)

• 釋放所占分區(qū)/分配進(jìn)程分區(qū)

• 缺點(diǎn)，浪費(fèi)大量CPU

分頁存儲管理

分段存儲管理

頁面置換算法

缺頁率：缺頁次數(shù)/全部次數(shù)

有效存取時(shí)間：（1-p）X ma+p X 缺頁處理時(shí)間(處理缺頁中斷時(shí)間，調(diào)入該頁的時(shí)間，重新啟動(dòng)進(jìn)程的時(shí)間)

頁面走向：存儲訪問序列

常見的頁面置換算法

磁盤容量=磁頭數(shù)X柱面數(shù)(磁道數(shù))X(每磁道)扇區(qū)數(shù)X512B(扇區(qū)大小)

磁盤訪問時(shí)間Ta：Ts（尋道時(shí)間10ms）+Tr（旋轉(zhuǎn)時(shí)間3ms）+Tt（傳輸時(shí)間）

磁盤調(diào)度算法

先來先服務(wù)法（FCFS）

最短尋道時(shí)間優(yōu)先算法（SSTF）：選擇最近磁道

掃描法（SCAN）：電梯法：不僅考慮距離，更考慮方向

循環(huán)掃描法（C-SCAN）：移動(dòng)到最遠(yuǎn)端即可返回到另一邊的最遠(yuǎn)端

旋轉(zhuǎn)調(diào)度

時(shí)間：（掃描時(shí)間+處理時(shí)間）Xn+延遲時(shí)間X（n-1）（n為扇區(qū)數(shù)）

分類

I/O通道分類：字符多路通道，數(shù)據(jù)選擇通道，數(shù)據(jù)多路通道

I/O方式分類：程序方式，中斷方式，DMA方式

通道是獨(dú)立于CPU的，負(fù)責(zé)數(shù)據(jù)輸入輸出參數(shù)工作的處理單元

有5個(gè)任務(wù)ABCDE，它們到達(dá)時(shí)刻分別0,2,4,6,8，預(yù)計(jì)它們的運(yùn)行時(shí)間為12，5，3，7，9min。其優(yōu)先級分別為2，4，5，1，3。這里5為最高優(yōu)先級。對于下列每一種調(diào)度算法，計(jì)算其平均進(jìn)程周轉(zhuǎn)時(shí)間（進(jìn)程切換開銷可不考慮）。

先來先服務(wù)（按A,B,C,D,E）算

短作業(yè)優(yōu)先算

最短剩余時(shí)間優(yōu)先算法

高響應(yīng)比優(yōu)先算法

非搶占式優(yōu)先級調(diào)度算法

搶占式優(yōu)先級調(diào)度算法

時(shí)間片輪轉(zhuǎn)算法(令時(shí)間片為2min)

產(chǎn)生死鎖的主要原因是進(jìn)程運(yùn)行推進(jìn)的順序不合適(資源分配不當(dāng)和系統(tǒng)資源不足)

臨界區(qū)是指并發(fā)進(jìn)程中訪問共享變量的(程序)段。

通常不采用(從非死鎖進(jìn)程處搶奪資源)方法來解除死鎖。

在9個(gè)生產(chǎn)者,6個(gè)消費(fèi)者共享容量為8的緩沖區(qū)的生產(chǎn)者-消費(fèi)者問題中,互斥使用緩沖區(qū)的信號量S的初始值為(1)。

若系統(tǒng)中有五臺繪圖儀,有多個(gè)進(jìn)程均需要使用兩臺,規(guī)定每個(gè)進(jìn)程一次僅允許申請一臺,則至多允許(4)個(gè)進(jìn)程參與競爭,而不會發(fā)生死鎖。

若某系統(tǒng)中有3個(gè)并發(fā)進(jìn)程,都需要同類資源3個(gè),則該系統(tǒng)不會發(fā)生死鎖的最少資源單位數(shù)是( 7)

系統(tǒng)發(fā)生死鎖時(shí),其資源分配圖中必然存在環(huán)路。因此,如果資源分配圖中存在環(huán)路,則系統(tǒng)一定出現(xiàn)死鎖。（錯(cuò)）

P,V操作不僅可以實(shí)現(xiàn)并發(fā)進(jìn)程之間的同步和互斥,而且能夠防止系統(tǒng)進(jìn)入死鎖狀態(tài)。（錯(cuò)）

由于資源數(shù)少于進(jìn)程對資源的需求數(shù),因而產(chǎn)生資源的競爭,所以這種資源的競爭必然會引起死鎖。（錯(cuò)）

某采用頁式虛擬存儲管理的系統(tǒng),頁面大小為100字。現(xiàn)有一用戶作業(yè),它依次要訪問的字地址序列是:215,58,90,186,355,430,306,168,279,93,201,140。系統(tǒng)分配給該作業(yè)的主存共300字,分別使用OPT和LRU,并計(jì)算缺頁率。

根據(jù)如下段表:

段號 基地址 長度 合法(0)/非法(1)

0 300 200

1 7500 540

2 3000 1010

3 2000 90

(1)求出邏輯地址為0,100的物理地址并將其的合法性填入上表適當(dāng)位置;

(2)求出邏輯地址為3,100的物理地址并將其的合法性填入上表適當(dāng)位置;

在分頁系統(tǒng)中,邏輯空間最多可以有64個(gè)頁,每頁1KB字節(jié)。若把它映射到由32個(gè)物理塊組成的存儲器。問:(1)有效的邏輯地址有多少位?(2)有效的物理地址有多少位?

(1)16：64X1024 = 2的16次方,(2)15：32X1024

在一個(gè)請求分頁系統(tǒng)中,分別采用FIFO、OPT和LRU頁面置換算法時(shí),假如一個(gè)作業(yè)的頁面走向?yàn)?、3、2、1、4、3、5、4、3、2、1、5,當(dāng)分配給該作業(yè)的物理內(nèi)存塊數(shù)是3時(shí),分別計(jì)算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率(用畫表形式)。

(2)如果一個(gè)邏輯地址空間長度為35KB的用戶程序申請內(nèi)存,系統(tǒng)采用最佳適配算法,請畫出分配后的空閑塊的鏈表情況。

(3) 針對2)里的內(nèi)存分配情況,若該用戶程序內(nèi)有一讀取數(shù)據(jù)指令“LOAD 2,4096”,請算出該用戶程序運(yùn)行時(shí)的實(shí)際讀取地址。(240K+4096B=244K)

(1) 采用最先適配法,所得到的分區(qū)首址是多少?被分配的那個(gè)空閑分區(qū)將分別剩下多少字節(jié)?(100K, 50K)

(2) 采用最佳適配法,所得到的分區(qū)首址是多少?被分配的那個(gè)空閑分區(qū)將分別剩下多少字節(jié)?(330K, 30K)

(3) 采用最壞適配法,所得到的分區(qū)首址是多少?被分配的那個(gè)空閑分區(qū)將分別剩下多少字節(jié)?(410K,72K)

假設(shè)一個(gè)磁盤有100個(gè)柱面，每個(gè)柱面有5個(gè)磁道，每個(gè)盤面被分為4個(gè)扇區(qū)，柱面、磁頭和扇區(qū)的編號均從0開始。現(xiàn)用字長為32位的位示圖來管理磁盤空間，位示圖的字號、位號從0開始編號。

（1）每個(gè)柱面有多少個(gè)存儲塊？該磁盤組共有多少個(gè)存儲塊?

（2）求位示圖中字號為4、位號為4的二進(jìn)制位對應(yīng)塊的物理塊號？

（3）給出該塊的物理地址（柱面號、磁頭號、扇區(qū)號）?

（4）刪除文件歸還第15柱面第5磁道第2扇區(qū)，對應(yīng)的物理塊號是多少？位示圖中應(yīng)修改第幾字第幾位？

（1）每個(gè)柱面有5（道）X4 （扇區(qū)） =20個(gè)存儲塊，磁盤共有20X100=2000個(gè)存儲塊。

（2）位示圖中字號為4、位號為4的二進(jìn)制位對應(yīng)塊的塊號是4*32+4=132。

（3）132/（54）=6，132%（54）=12，12/4=3，12%4=0，該塊的柱面號是6，磁頭號是3，扇區(qū)號是0。

（4） 塊號=（15柱面第5磁道第2扇區(qū)）15X5X4+5X4+2=322

某磁盤組有100個(gè)柱面，每個(gè)柱面有4個(gè)磁道，每個(gè)磁道被分為2個(gè)扇區(qū)。現(xiàn)用字長為16位的位示圖來管理磁盤空間，位示圖中的字號、位號從“0”開始編號。試問：

（1）存儲該位示圖需多少字節(jié)？

（2）位示圖中字號為6、位號為26的二進(jìn)制位所對應(yīng)盤塊的邏輯塊號是多少？它在哪個(gè)柱面、磁道號和扇區(qū)號（柱面編號從“0”開始）？

（1）100X4X2/8=100字節(jié)。

（2）位示圖中字號為6、位號為24的二進(jìn)制位所對應(yīng)盤塊的塊號是6X16+26=122, m=122/(42)=15, n=122%(42)=2, 2/8=0, 2%8=2

所以該塊在15號柱面，0號磁道號和2號扇區(qū)號。

某文件系統(tǒng)中每盤塊大小為4KB，每塊地址用4B表示，請問：

（1）若該文件系統(tǒng)采用二級和三級索引結(jié)構(gòu)，則它能管理的最大文件長度分別是多少字節(jié)？

（2）若有一個(gè)20KB大小的文件，現(xiàn)已獲取到該文件的目錄信息，如需讀取該文件最后16B的數(shù)據(jù)，當(dāng)文件系統(tǒng)分別采用連續(xù)結(jié)構(gòu)和鏈接結(jié)構(gòu)時(shí)，各需要讀取多少個(gè)盤塊？

（1）一個(gè)盤塊里的盤號數(shù)：4KB/4B=1K

（2）連續(xù)結(jié)構(gòu)：讀取1個(gè)盤塊

某磁盤磁道分成5個(gè)扇區(qū)(0～4)，每個(gè)扇區(qū)存放一個(gè)邏輯記錄。一個(gè)用戶文件有 5個(gè)記錄：A、B、C、D、E，被順序存放在一個(gè)磁道上。 假定磁盤旋轉(zhuǎn)一周的時(shí)間是 30ms， 每個(gè)記錄讀出后需9ms的時(shí)間處理。試問：

(1)順序讀出6個(gè)記錄并進(jìn)行處理，共需多少時(shí)間？

(2)給出一種在磁盤上安排記錄的策略，使整個(gè)時(shí)間盡可能少。

（1）（6+9）X 5 + 21 X 4 = 159 ms

（2）安排策略：A,D,B,E,C ，共需：（6+9）X 5 + 3 X 4 = 87 ms

有一個(gè)請求磁盤服務(wù)的隊(duì)列，要訪問的磁道分別是：97，180，30，120，16，19，78，69，設(shè)磁頭最初在35道上。請問：

（1）寫出FCFS算法的尋道序列，并算出平均尋找長度

（2）寫出SSTF算法的尋道序列，并算出平均尋找長度。

（3）當(dāng)磁頭移動(dòng)方向?yàn)?#xff1a;朝著圓心方向，寫出SCAN算法的尋道序列，并算出平均尋找長度。

（4）當(dāng)磁頭移動(dòng)方向?yàn)?#xff1a;遠(yuǎn)離圓心方向，寫出SCAN算法的尋道序列，并算出平均尋找長度。

（5）當(dāng)磁頭移動(dòng)方向?yàn)?#xff1a;1 朝著圓心方向，寫出循環(huán)SCAN算法的尋道序列，并算出平均尋找長度。

（6）當(dāng)磁頭移動(dòng)方向?yàn)?#xff1a;遠(yuǎn)離圓心方向，寫出循環(huán)SCAN算法的尋道序列，并算出平均尋找長度。