（筆記更新到第三章 咕咕咕）

操作系統(tǒng)序論：

定義：軟件

地位

基本特征

并行和并發(fā)的區(qū)別：

并行：同一個(gè)時(shí)刻兩個(gè)進(jìn)程同時(shí)進(jìn)行

并發(fā)：給定的時(shí)間間隔中兩個(gè)進(jìn)程同時(shí)進(jìn)行

最基本特征：并發(fā)、共享

主要功能：處理機(jī)管理、存儲(chǔ)器管理、文件管理、設(shè)備管理

發(fā)展歷程：

手工操作階段（此階段無操作系統(tǒng))

缺：人機(jī)速度矛盾

批處理階段(操作系統(tǒng)開始出現(xiàn))

1.單道批處理階段

2.多道批處理階段(操作系統(tǒng)正式誕生)

目的:提高系統(tǒng)資源的利用率

多道批優(yōu)缺點(diǎn)：

優(yōu):多道程序并發(fā)執(zhí)行，資源利用率高

缺:不提供人機(jī)交互能力(缺少交互性)

分時(shí)操作系統(tǒng)(不可以插隊(duì)，有了人機(jī)交互)

為不同程序分配了不同的時(shí)間片，提供了順序執(zhí)行的方法

優(yōu):提供人機(jī)交互(交互性)

缺:不能優(yōu)先處理緊急事務(wù)

實(shí)時(shí)操作系統(tǒng)(可以插隊(duì))

硬實(shí)時(shí)系統(tǒng):必須在被控制對(duì)象規(guī)定時(shí)間內(nèi)完成(火箭發(fā)射 不發(fā)射后果嚴(yán)重)

軟實(shí)時(shí)系統(tǒng):可以松一些(訂票時(shí)的網(wǎng)絡(luò)如果略微延遲并不會(huì)很大的影響程序執(zhí)行)

優(yōu):能優(yōu)先處理緊急任務(wù)

從可靠性看實(shí)時(shí)操作系統(tǒng)更強(qiáng)，從交互性看分時(shí)操作系統(tǒng)更強(qiáng)

概念須知：

兩種指令：

特權(quán)指令:不允許用戶程序使用(只允許操作系統(tǒng)使用）。如IO指令、置中斷指令

非特權(quán)指令:普通的運(yùn)算指令

兩種程序：

內(nèi)核程序:系統(tǒng)的管理者，可執(zhí)行一切指令、運(yùn)行在核心態(tài)

應(yīng)用程序:普通用戶程序只能執(zhí)行非特權(quán)指

令，運(yùn)行在用戶態(tài)

處理機(jī)狀態(tài)：

用戶態(tài)(目態(tài)):CPU只能執(zhí)行非特權(quán)指令

核心態(tài)(又稱管態(tài)、內(nèi)核態(tài)):可以執(zhí)行所有指令

用戶態(tài)到核心態(tài):

用戶只有執(zhí)行非特權(quán)指令權(quán)限，但要執(zhí)行特權(quán)指令，此時(shí)硬件需要通過中斷完成處理機(jī)狀態(tài)的轉(zhuǎn)化

核心態(tài)到用戶態(tài):特權(quán)指令psw的標(biāo)志位0用戶態(tài)1核心態(tài)常考誰在用戶態(tài)執(zhí)行，誰在核心態(tài)執(zhí)行

原語（類比于原子）

1)處于操作系統(tǒng)的最低層，是最接近硬件的部分。

2)這些程序的運(yùn)行具有原子性，其操作只能一氣呵成（程序在運(yùn)行時(shí)不能被打斷

3)這些程序的運(yùn)行時(shí)間都較短，而且調(diào)用頻繁。

中斷和異常

內(nèi)中斷（異常，信號(hào)來自內(nèi)部）：

①自愿中斷——指令中斷——如︰系統(tǒng)調(diào)用時(shí)使用的訪管指令（又叫陷入指令，trap指令)

②強(qiáng)迫中斷

硬件中斷故障———如︰缺頁

軟件中斷——如︰整數(shù)除以0

外中斷（中斷，信號(hào)來自外部）

①外設(shè)請(qǐng)求：如:I/O操作完成發(fā)出的中斷信號(hào)

②人工干預(yù)：如用戶強(qiáng)行終止一個(gè)進(jìn)程

系統(tǒng)調(diào)用

系統(tǒng)給程序員(應(yīng)用程序)提供的唯一接口，可獲得OS的服務(wù)。在用戶態(tài)發(fā)生，核心態(tài)處理

體系結(jié)構(gòu)

①大內(nèi)核：高性能

②微內(nèi)核：維護(hù)方便

第2章 進(jìn)程調(diào)度

進(jìn)程管理

引入進(jìn)程目的：為了更好地描述和控制程序并發(fā)執(zhí)行，實(shí)現(xiàn)操作系統(tǒng)的并發(fā)性和共享性（進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的)

進(jìn)程的定義：是計(jì)算機(jī)中的程序關(guān)于某數(shù)據(jù)集合上的一次運(yùn)行活動(dòng)，是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位（沒有引入線程時(shí) ）

進(jìn)程的組成：

PCB：保存進(jìn)程運(yùn)行期間相關(guān)的數(shù)據(jù)，是進(jìn)程存在的唯一標(biāo)志

（PCB常駐內(nèi)存，進(jìn)程創(chuàng)立之時(shí)即常駐內(nèi)存）

程序段：能被進(jìn)程調(diào)度到CPU的代碼

數(shù)據(jù)段

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

狀態(tài)種類：

創(chuàng)建狀態(tài)：進(jìn)程在被創(chuàng)建

就緒態(tài)：進(jìn)程已處于準(zhǔn)備運(yùn)行的狀態(tài)，即進(jìn)程獲得了除處理機(jī)外的一切所需資源，一旦得到處理機(jī)即可運(yùn)行。

運(yùn)行態(tài)：進(jìn)程正在占用cpu

阻塞態(tài)：

結(jié)束狀態(tài)：進(jìn)程正在從系統(tǒng)消失，被調(diào)出內(nèi)存

狀態(tài)變化：

就緒態(tài)→運(yùn)行態(tài)

運(yùn)行態(tài)→就緒態(tài)：

運(yùn)行態(tài)→阻塞態(tài)：進(jìn)程需要的某一資源還沒有準(zhǔn)備好

阻塞態(tài)→就緒態(tài)：由于已經(jīng)阻塞，離開了cpu，需要重新調(diào)度

進(jìn)程狀態(tài)轉(zhuǎn)化圖：

線程：

引入目的：為了更好的使用多道程序并發(fā)執(zhí)行，提高資源利用率和系統(tǒng)吞吐量

特點(diǎn)：是程序執(zhí)行的最小單位，基本不擁有任何系統(tǒng)資源（調(diào)度的基本單位)。但由于線程不擁有系統(tǒng)資源，因此資源分配的最小單位還是進(jìn)程。

?處理機(jī)調(diào)度（大題）：

概念：是對(duì)處理機(jī)進(jìn)行分配，即從就緒隊(duì)列中按照定的算法(公平、高效)選擇一個(gè)進(jìn)程并將處理機(jī)分配給它運(yùn)行，以實(shí)現(xiàn)進(jìn)程并發(fā)地執(zhí)行。

分類：

高級(jí)調(diào)度（作業(yè)調(diào)度)（次數(shù)少)

中級(jí)調(diào)度（內(nèi)存對(duì)換)(次數(shù)中等)

低級(jí)調(diào)度(進(jìn)程調(diào)度)（次數(shù)多)

1、高級(jí)調(diào)度：

又稱為：作業(yè)調(diào)度

調(diào)度對(duì)象：作業(yè)

功能：根據(jù)算法，決定將外存上處于后備隊(duì)列的哪幾個(gè)作業(yè)調(diào)入內(nèi)存，為他們創(chuàng)建進(jìn)程、分配必要的資源，并將它們放入就緒隊(duì)列。

適用系統(tǒng)：適合多道批處理系統(tǒng)，不適合分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)。

運(yùn)行頻率：較低

2、低級(jí)調(diào)度

又稱為：進(jìn)程調(diào)度?

調(diào)度對(duì)象：進(jìn)程

功能：根據(jù)算法，決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，并由分派程序?qū)⑻幚頇C(jī)分配給被選中的進(jìn)程。

適合系統(tǒng)：適合多道批處理系統(tǒng)，分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)。

運(yùn)行頻率：中

3、中級(jí)調(diào)度

又稱為：內(nèi)存調(diào)度

調(diào)度對(duì)象：進(jìn)程

功能：把那些內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程調(diào)至外存等待?，此時(shí)進(jìn)程的狀態(tài)為就緒駐外存狀態(tài)（掛起狀態(tài)），相當(dāng)于存儲(chǔ)器管理中的對(duì)換功能，目的就是提高內(nèi)存利用率和系統(tǒng)吞吐量。

運(yùn)行頻率：最高

調(diào)度方式：

剝奪式（搶占式）：進(jìn)程1在運(yùn)行，進(jìn)程2優(yōu)先級(jí)比進(jìn)程1高，進(jìn)程2直接上處理器

（原則1：優(yōu)先級(jí)原則，允許優(yōu)先級(jí)高的并且是新到的進(jìn)程可以搶占當(dāng)前進(jìn)程的處理機(jī)。

原則2：短進(jìn)程原則

原則3：時(shí)間片原則）

非剝奪式（非搶占式）：進(jìn)程1在運(yùn)行，即使進(jìn)程2優(yōu)先級(jí)比進(jìn)程1高，進(jìn)程2也得等待進(jìn)程1執(zhí)行完上處理器

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

CPU利用率

系統(tǒng)吞吐量：?jiǎn)挝粫r(shí)間內(nèi)cpu完成作業(yè)的數(shù)目

周轉(zhuǎn)時(shí)間：作業(yè)的完成時(shí)間-提交時(shí)間

等待時(shí)間：進(jìn)程與等待處理機(jī)的時(shí)間之和

響應(yīng)時(shí)間：從提交到第一次開始運(yùn)行的時(shí)間

算法：

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

算法原理：按照作業(yè)（進(jìn)程）到達(dá)的先后次序來進(jìn)行調(diào)度，誰先來，誰就先被調(diào)度。

缺點(diǎn)：忽略了作業(yè)的運(yùn)行時(shí)間

短作業(yè)優(yōu)先（SJF)：

算法原理：以作業(yè)的長(zhǎng)短來計(jì)算優(yōu)先級(jí)，作業(yè)越短優(yōu)先級(jí)越高，作業(yè)長(zhǎng)短以所要求的運(yùn)行時(shí)間來衡量。

?缺點(diǎn)：必須預(yù)先知道作業(yè)的運(yùn)行時(shí)間、對(duì)長(zhǎng)作業(yè)不利，未考慮作業(yè)的緊迫程度。

例題：

解：“作業(yè)被調(diào)度進(jìn)入運(yùn)行后不再退出"意為非搶占式調(diào)用，job2到來時(shí)也得等待job1執(zhí)行完

①job1最先達(dá)到，運(yùn)行60分鐘，此時(shí)job2-6已經(jīng)全部提交，此時(shí)從job2-6中挑選運(yùn)行時(shí)間最短的，那么順序依次為1→5→6→3→4→2

標(biāo)準(zhǔn)流程如圖（要寫出作業(yè)號(hào)、提交時(shí)間、運(yùn)行時(shí)間、開始時(shí)刻、完成時(shí)刻、周轉(zhuǎn)時(shí)間）：

②周轉(zhuǎn)時(shí)間=完成時(shí)間-提交時(shí)間

平均周轉(zhuǎn)時(shí)間=1/n *(N1+N2+……+Nn）

(n為作業(yè)過程總數(shù)，N1、N2為周轉(zhuǎn)時(shí)間）

優(yōu)先級(jí)調(diào)度算法：

算法原理：FCFS、SJF兩種算法都不能反映進(jìn)程的緊迫程度。而優(yōu)先級(jí)調(diào)度算法是外部賦予進(jìn)程相應(yīng)的優(yōu)先級(jí)，來體現(xiàn)出進(jìn)程的緊迫程度，緊迫性進(jìn)程優(yōu)先運(yùn)行

（如何確定優(yōu)先級(jí)：

1、利用某一范圍內(nèi)的一個(gè)整數(shù)，優(yōu)先數(shù)

2、響應(yīng)比的大小，誰響應(yīng)比大，誰優(yōu)先級(jí)就大——高響應(yīng)比優(yōu)先調(diào)度算法）

高響應(yīng)比優(yōu)先調(diào)度算法

時(shí)間片輪轉(zhuǎn)

適合系統(tǒng)：分時(shí)系統(tǒng)

算法原理：基于時(shí)間片的輪轉(zhuǎn)，非常公平，就緒隊(duì)列中的每一個(gè)進(jìn)程每次僅僅運(yùn)行一個(gè)時(shí)間片，并且每個(gè)進(jìn)程是輪流運(yùn)行。

首先按照FCFS策略把就緒進(jìn)程排成一個(gè)就緒隊(duì)列，設(shè)置時(shí)間片，從第一個(gè)進(jìn)程開始分配處理機(jī)，第一個(gè)進(jìn)程的時(shí)間片執(zhí)行完后，再?gòu)木途w隊(duì)列中新的隊(duì)首進(jìn)程開始。若進(jìn)程已經(jīng)運(yùn)行完，注意此時(shí)第一個(gè)進(jìn)程就已經(jīng)不在就緒隊(duì)列的隊(duì)首，而是從就緒隊(duì)列中刪除。若未執(zhí)行完只是時(shí)間片完了，則是調(diào)度程序把它送往末尾去了。

多級(jí)反饋隊(duì)列調(diào)度算法

算法原理（調(diào)度機(jī)制）：

設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)，第一個(gè)隊(duì)列優(yōu)先級(jí)最高，并且首先調(diào)度最高優(yōu)先級(jí)，也就是第一個(gè)隊(duì)列里面的所有進(jìn)程，僅當(dāng)?shù)谝粋€(gè)隊(duì)列空閑時(shí)，才開始調(diào)度第二個(gè)隊(duì)列中的進(jìn)程運(yùn)行。優(yōu)先級(jí)越高的隊(duì)列，時(shí)間片越小。

多進(jìn)程同步

引入原因：協(xié)調(diào)進(jìn)程之間的相互制約關(guān)系

制約關(guān)系：

①同步：亦稱直接制約關(guān)系，是指為完成某種任務(wù)而建立的兩個(gè)或多個(gè)進(jìn)程，這些進(jìn)程因?yàn)樾枰谀承┪恢蒙蠀f(xié)調(diào)它們的工作次序而等待、傳遞信息所產(chǎn)生的制約關(guān)系。

②互斥:也稱間接制約關(guān)系。當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)使用臨界資源時(shí)，另一個(gè)進(jìn)程必須等待，當(dāng)占用臨界資源的進(jìn)程退出臨界區(qū)后，另進(jìn)程才允許去訪問此臨界資源。

臨界資源:—次僅允許一個(gè)進(jìn)程使用的資源(打印機(jī)，共享緩沖區(qū)，共享變量，公用隊(duì)列等)

臨界區(qū):在每個(gè)進(jìn)程中訪問臨界資源的那段程序

（是程序段，非區(qū)域）

臨界區(qū)互斥（必背）：

原則：

空閑讓進(jìn):如果有若干進(jìn)程要求進(jìn)入空閑的臨界區(qū)，次僅允許一個(gè)進(jìn)程進(jìn)入。

忙則等待:任何時(shí)候，處于臨界區(qū)內(nèi)的進(jìn)程不可多于一個(gè)。如已有進(jìn)程進(jìn)入自己的臨界區(qū)，則其它所有試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待。

有限等待:進(jìn)入臨界區(qū)的進(jìn)程要在有限時(shí)間內(nèi)退出，以便其它進(jìn)程能及時(shí)進(jìn)入自己的臨界區(qū)。

讓權(quán)等待:如果進(jìn)程不能進(jìn)入自己的臨界區(qū)，則應(yīng)讓出CPU，避免進(jìn)程出現(xiàn)“忙等”現(xiàn)象。

基本方法：信號(hào)量：利用pv操作實(shí)現(xiàn)互斥

死鎖

產(chǎn)生的原因：非剝奪資源的競(jìng)爭(zhēng)和進(jìn)程的不恰當(dāng)推進(jìn)順序(與饑餓的區(qū)別)

（饑餓：缺乏某一資源并一直沒得到滿足)

定義：多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的─種僵局，如果沒有外力，這些進(jìn)程將無法推進(jìn)

解決方法：

預(yù)防死鎖（破壞死鎖的四個(gè)必要條件）：

破壞互斥條件

破壞不剝奪條件

破壞請(qǐng)求和保持條件

破壞循環(huán)等待條件

避免死鎖：

①安全狀態(tài)

②?銀行家算法

檢測(cè)死鎖:利用死鎖定理

解除死鎖：

資源剝奪法：爭(zhēng)奪資源而陷入死鎖，直接剝奪資源以解決

撤銷進(jìn)程法：直接取消發(fā)生矛盾的進(jìn)程

進(jìn)程回退法：回到死鎖前的狀態(tài)

進(jìn)程調(diào)度 練習(xí)

（不想做題 嗚嗚嗚┭┮﹏┭┮）

①短作業(yè)優(yōu)先調(diào)度算法

解：“作業(yè)被調(diào)度進(jìn)入運(yùn)行后不再退出"意為非搶占式調(diào)用，job2到來時(shí)也得等待job1執(zhí)行完

①job1最先達(dá)到，運(yùn)行60分鐘，此時(shí)job2-6已經(jīng)全部提交，此時(shí)從job2-6中挑選運(yùn)行時(shí)間最短的，那么順序依次為1→5→6→3→4→2

標(biāo)準(zhǔn)流程如圖（要寫出作業(yè)號(hào)、提交時(shí)間、運(yùn)行時(shí)間、開始時(shí)刻、完成時(shí)刻、周轉(zhuǎn)時(shí)間）：

②周轉(zhuǎn)時(shí)間=完成時(shí)間-提交時(shí)間

平均周轉(zhuǎn)時(shí)間=1/n *(N1+N2+……+Nn）

(n為作業(yè)過程總數(shù)，N1、N2為周轉(zhuǎn)時(shí)間）

②短作業(yè)優(yōu)先調(diào)度&以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度

解：“兩道作業(yè)”，即進(jìn)程只允許在內(nèi)存中同時(shí)存在兩個(gè)；優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度，其中優(yōu)先數(shù)數(shù)值越小，執(zhí)行優(yōu)先級(jí)越高（也有不一樣的，注意題目要求）；

執(zhí)行流程：

10點(diǎn)A到達(dá)進(jìn)入內(nèi)存，cpu運(yùn)行至10：20；

10：20b作業(yè)到達(dá)，b優(yōu)先數(shù)小于A（A未運(yùn)行完），因此將A擠下處理器，B開始運(yùn)行，A剩余20分鐘；

10：30C作業(yè)到達(dá)，但短作業(yè)優(yōu)先，50分鐘比AB剩余運(yùn)算時(shí)間20分鐘都長(zhǎng)，不會(huì)調(diào)用內(nèi)存，因此無事發(fā)生；

10：50：B作業(yè)執(zhí)行完成，內(nèi)存空余了1，CD都已經(jīng)到，短作業(yè)優(yōu)先結(jié)合A剩余時(shí)長(zhǎng)比較，此時(shí)A剩20，C50,D20，那么D進(jìn)入準(zhǔn)備調(diào)用處理機(jī)，但D的優(yōu)先小于A，因此A先在cpu運(yùn)行；

11:10：A作業(yè)運(yùn)行完畢，內(nèi)存空余，d作業(yè)進(jìn)入內(nèi)存，D優(yōu)先數(shù)大于C，繼續(xù)調(diào)度C，至12：00結(jié)束

12：00：D作業(yè)運(yùn)行，執(zhí)行完20分鐘至12：20結(jié)束

③最高優(yōu)先級(jí)、時(shí)間片輪轉(zhuǎn)、FIFO、短作業(yè)優(yōu)先四種情況下的平均周轉(zhuǎn)時(shí)間計(jì)算

由于幾乎同時(shí)到達(dá)：

(1)最高優(yōu)先級(jí)優(yōu)先算法：

注意周轉(zhuǎn)時(shí)間=完成時(shí)間-提交時(shí)間，建議列表，答案為110/5=22；

（2）時(shí)間片輪轉(zhuǎn)算法：首先按照FCFS（先來先處理）策略把就緒進(jìn)程排成一個(gè)就緒隊(duì)列，每個(gè)程序只執(zhí)行一個(gè)時(shí)間片的時(shí)間，完全執(zhí)行完后從就緒隊(duì)列刪除；（F應(yīng)該是E）

（2+12+20+16+30）/5=18

（3）FIFO （先到先服務(wù)）

最簡(jiǎn)單的順序運(yùn)行

注意是周轉(zhuǎn)時(shí)間，（6+14+18+28+30)/5=19.2

(4) 短作業(yè)優(yōu)先 （運(yùn)行時(shí)間短先服務(wù)）

（2+6+12+20+30）/5=14

臨界資源與臨界區(qū)

1)臨界資源:一次僅允許一個(gè)進(jìn)程使用的資源。

2）臨界區(qū)：在每個(gè)進(jìn)程中訪問臨界資源的那段程序。

進(jìn)程的同步與互斥

1)同步:同步亦稱直接制約關(guān)系，是指為完成某種任務(wù)而建立的兩個(gè)或多個(gè)進(jìn)程，這些進(jìn)程因?yàn)樾枰谀承┪恢蒙蠀f(xié)調(diào)它們的工作次序而等待、傳遞信息所產(chǎn)生的制約關(guān)系。

2)互斥:互斥也稱間接制約關(guān)系。當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)使用臨界資源時(shí),另一個(gè)進(jìn)程必須等待，當(dāng)占用臨界資源的進(jìn)程退出臨界區(qū)后，另進(jìn)程才允許去訪問此臨界資源。

同步機(jī)制應(yīng)遵循以下準(zhǔn)則:

(1)空閑讓進(jìn)∶如果有若干進(jìn)程要求進(jìn)入空閑的臨界區(qū)，一次僅允許一個(gè)進(jìn)程進(jìn)入。

(2)忙則等待:任何時(shí)候，處于臨界區(qū)內(nèi)的進(jìn)程不可多于一個(gè)。如已有進(jìn)程進(jìn)入自己的臨界區(qū)，則其它所有試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待。

(3有限等待:進(jìn)入臨界區(qū)的進(jìn)程要在有限時(shí)間內(nèi)退出，以便其它進(jìn)程能及時(shí)進(jìn)入自己的臨界區(qū)。

(4)讓權(quán)等待∶如果進(jìn)程不能進(jìn)入自己的臨界區(qū)，則應(yīng)讓出CPU，避免進(jìn)程出現(xiàn)“忙等”現(xiàn)象。

（先前已經(jīng)總結(jié)過，因此不標(biāo)黑劃重點(diǎn)）

信號(hào)量：

信號(hào)量機(jī)制是一種有效實(shí)現(xiàn)進(jìn)程同步和互斥的工具

信號(hào)量的物理意義∶

(1)信號(hào)量的值：

大于0:表示當(dāng)前資源可用數(shù)量

小于0︰其絕對(duì)值表示等待使用該資源的進(jìn)程個(gè)數(shù)

(2)信號(hào)量初值為非負(fù)整數(shù)變量，代表資源數(shù)。

(3)信號(hào)量值可變，但僅能由P、V操作改變。

P/V操作原語

1)P操作原語 P(S)

(1)P操作一次，S值減1，即S=S-1(請(qǐng)求分配一資源 即消耗一個(gè)資源); 如S=5P(S),那么S=4

(2)如果S≥0，則該進(jìn)程繼續(xù)執(zhí)行;如果S<0表示無資源，則該進(jìn)程的狀態(tài)置為阻塞態(tài)，把相應(yīng)的PCB連入該信號(hào)量隊(duì)列的末尾，并放棄處理機(jī)，進(jìn)行等待(直至另一個(gè)進(jìn)程執(zhí)行v (S）操作)。

2) V操作原語(荷蘭語的等待)V(S)

(1)v操作一次，s值加1，即S=S+1(釋放一單位量資源); S=5。.V(S),S=6;

(2)如果S>0，表示有資源，則該進(jìn)程繼續(xù)執(zhí)行; 如果S<0，則釋放信號(hào)量隊(duì)列上的第一個(gè)PCB所對(duì)應(yīng)的進(jìn)程(阻塞態(tài)改為就緒態(tài))，執(zhí)行V操作的進(jìn)程繼續(xù)執(zhí)行。

進(jìn)程間簡(jiǎn)單同步與互斥的實(shí)現(xiàn)

1)用P,V原語實(shí)現(xiàn)互斥的一般模型

設(shè)互斥信號(hào)量mutex初值為1

2)用P、V原語操作實(shí)現(xiàn)簡(jiǎn)單同步的例子

S1緩沖區(qū)是否空(0表示不空，1表示空)，初值S1=0;

S2緩沖區(qū)是否滿(0表示不滿，1表示滿)，初值S2=0;

3)生產(chǎn)者——消費(fèi)者問題(os典型例子) ︰ mutex互斥信號(hào)量，初值為1;full滿緩沖區(qū)數(shù)，初值為0; empty空緩沖區(qū)數(shù)，初值為N;

什么是死鎖

死鎖:多個(gè)進(jìn)程循環(huán)等待它方占有的資源而無限期地僵持下去的局面。

產(chǎn)生死鎖的原因：

1）系統(tǒng)資源的競(jìng)爭(zhēng)

通常系統(tǒng)中擁有的不可剝奪資源，其數(shù)量不足以滿足多個(gè)進(jìn)程運(yùn)行的需要，使得

進(jìn)程在運(yùn)行過程中，會(huì)因爭(zhēng)奪資源而陷入僵局，如磁帶機(jī)、打印機(jī)等。只有對(duì)不可剝奪資源的競(jìng)爭(zhēng)才可能產(chǎn)生死鎖，對(duì)可剝奪資源的競(jìng)爭(zhēng)是不會(huì)引起死鎖的。

2)進(jìn)程推進(jìn)順序非法

進(jìn)程在運(yùn)行過程中，請(qǐng)求和釋放資源的順序不當(dāng)，也同樣會(huì)導(dǎo)致死鎖。

例：并發(fā)進(jìn)程P1、P2分別保持了資源R1、R2,而進(jìn)程P1申請(qǐng)資源R2,進(jìn)程P2申請(qǐng)資源R1時(shí)，兩者都會(huì)因?yàn)樗栀Y源被占用而阻塞。

3)死鎖產(chǎn)生的必要條件

互斥條件:進(jìn)程要求對(duì)所分配的資源(如打印機(jī))進(jìn)行排他性控制，即在一段時(shí)間內(nèi)某資源僅為一個(gè)進(jìn)程所占有。此時(shí)若有其他進(jìn)程請(qǐng)求該資源，則請(qǐng)求進(jìn)程只能等待。

不剝奪條件:進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行奪走，即只能由獲得該資源的進(jìn)程自己來釋放(只能是主動(dòng)釋放)。

請(qǐng)求和保持條件:進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求。而該資源已被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程被阻塞,但對(duì)自己已獲得的資源保持不放。

循環(huán)等待條件:存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中每一個(gè)進(jìn)程已獲得的資源同時(shí)被鏈中下一一個(gè)進(jìn)程所請(qǐng)求。

當(dāng)死鎖產(chǎn)生的時(shí)候一定會(huì)有這四個(gè)條件， 有一個(gè)條件不成立都不會(huì)造成死鎖。其中互斥使用資源時(shí)無法破壞的

生產(chǎn)者消費(fèi)者問題：

一組生產(chǎn)者和一組消費(fèi)者共享一個(gè)初始為空，大小為n的緩沖區(qū)，只有當(dāng)緩沖區(qū)沒滿時(shí)，生產(chǎn)者才能把消息放入緩沖區(qū)，否則必須等待，只有當(dāng)緩沖區(qū)不空時(shí)，消費(fèi)者才能從中取出消息，否則必須等待，只允許一個(gè)生產(chǎn)者放入消息，或者一個(gè)消費(fèi)者取出消息。

①找到題目中的同步/互斥關(guān)系

生產(chǎn)者的放---消費(fèi)者的取 互斥關(guān)系

生產(chǎn)者生產(chǎn)---消費(fèi)者取 同步關(guān)系

②設(shè) ：

semaphore mutex=1（臨界區(qū)信號(hào)量 互斥）

當(dāng)semaphore mutex=1時(shí)可以調(diào)用

semaphore empty=n （空閑緩沖區(qū)）

semaphore full=0 （緩沖區(qū)）

producer（生產(chǎn)者）：

while (1)

{

produce an item in nextp;//生產(chǎn)

P（empty）//檢驗(yàn)是否有空閑緩沖區(qū)①

P（mutex）//檢驗(yàn)臨界區(qū)信號(hào)量②

add next p to buff//行為

V(mutex)

V(full)

}

①和②能互換順序嗎？

先執(zhí)行2，那么訪問緩沖區(qū)，②執(zhí)行完mutex=0，此時(shí)若①中empty已經(jīng)=0，那么p（emtpy）無法執(zhí)行（即無空閑緩沖區(qū)），此時(shí)會(huì)陷入死鎖。

consumer（消費(fèi)者）：

while （1）

{

p(full) //獲取緩沖區(qū)單元

p(mutex)//進(jìn)入臨界區(qū)

remove an item from buffer;

v(mutex);//釋放臨界區(qū)

v(empty);//消費(fèi)數(shù)據(jù)

}

解決死鎖的一般辦法：

解決死鎖的三種方法:死鎖的預(yù)防、避免、檢測(cè)與恢復(fù)。

1.死鎖預(yù)防的基本思想和可行的解決辦法

1.死鎖預(yù)防的基本思想:打破產(chǎn)生死鎖的四個(gè)必要條件的一個(gè)或幾個(gè)。

2.避免死鎖的策略:在資源的動(dòng)態(tài)分配過程中，用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖。（運(yùn)行過程盡量避免）

3.死鎖的檢測(cè)及解除 （死鎖發(fā)生后解決）

無需采取任何限制性措施，允許進(jìn)程在運(yùn)行過程中發(fā)生死鎖。通過系統(tǒng)的檢測(cè)機(jī)構(gòu)及時(shí)地檢測(cè)出死鎖的發(fā)生，然后采取某種措施解除死鎖。

具體的死鎖預(yù)防（破壞四大條件）：

1）破壞互斥條件

如果允許系統(tǒng)資源都能共享使用，則系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)。但有些資源根本不能同時(shí)訪問，如打印機(jī)等臨界資源只能互斥使用。所以，破壞互斥條件而預(yù)防死鎖的方法不太可行，而且在有的場(chǎng)合應(yīng)該保護(hù)這種互斥性。

2)破壞不剝奪條件

當(dāng)一個(gè)已保持了某些不可剝奪資源的進(jìn)程，請(qǐng)求新的資源而得不到滿足時(shí)，它必須釋放已經(jīng)保持的所有資源，待以后需要時(shí)再重新申請(qǐng)。這意味著，一個(gè)進(jìn)程已占有的資源會(huì)被暫時(shí)釋放，或者說是被剝奪了，或從而破壞了不可剝奪條件。

3）破壞請(qǐng)求和保持條件

采用預(yù)先靜態(tài)分配方法，即進(jìn)程在運(yùn)行前一次申請(qǐng)完它所需要的全部資源，在它的資源未滿足前，不把它投入運(yùn)行。一旦投入運(yùn)行后，這些資源就一直歸它所有，也不再提出其他資源請(qǐng)求，這樣就可以保證系統(tǒng)不會(huì)發(fā)生死鎖。

這種方式實(shí)現(xiàn)簡(jiǎn)單，但缺點(diǎn)也顯而易見，系統(tǒng)資源被嚴(yán)重浪費(fèi),其中有些資源可能僅在運(yùn)行初期或運(yùn)行快結(jié)束時(shí)才使用，甚至根本不使用。而且還會(huì)導(dǎo)致“饑餓’現(xiàn)象，當(dāng)由于個(gè)別資源長(zhǎng)期被其他進(jìn)程占用時(shí)，將致使等待該資源的進(jìn)程遲遲不能開始運(yùn)行。

4)破壞循環(huán)等待條件

為了破壞循環(huán)等待條件，可采用順序資源分配法，首先給系統(tǒng)中的資源編號(hào)規(guī)定每個(gè)進(jìn)程，必須按編號(hào)遞增的順序請(qǐng)求資源，同類資源一次申請(qǐng)完。也就是說，只要進(jìn)程提出申請(qǐng)分配資源Ri,則該進(jìn)程在以后的資源申請(qǐng)中，只能申請(qǐng)編號(hào)大于Ri的資源。

死鎖避免的重要算法：銀行家算法

銀行家算法是最著名的死鎖避免算法。它提出的思想是:把操作系統(tǒng)看做是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。 操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量、如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過了該進(jìn)程對(duì)資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。

銀行家算法的描述:

設(shè)Request(i)是進(jìn)程Pi的請(qǐng)求向量，如果Request(i)[j]=k，表示進(jìn)程Pi需要K個(gè)R(j)類型的資源。當(dāng)Pi發(fā)現(xiàn)資源請(qǐng)求后系統(tǒng)將進(jìn)行下列步驟

(1)如果Request(i)[j] <= Need[i,j],邊轉(zhuǎn)向步驟2),否則認(rèn)為出錯(cuò)，因?yàn)樗?qǐng)求的資源數(shù)已超過它所宣布的最大值。

(2)如果Request(i)[j] <= Available[i,j]，便轉(zhuǎn)向步驟3)，否則，表示尚無足夠資源，Pi需等待。

(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并需要修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值；

Available[j] = Available[j] - Request(i)[j];

Allocation[i,j] = Allocation[i,j] + Request(i)[j];

Need[i,j] = Need[i,j] - Request(i)[j];

銀行家算法的數(shù)據(jù)結(jié)構(gòu)描述:

可利用資源矢量Available:含有m個(gè)元素的歎組，其中的每一個(gè)元素代表一類可用的資源數(shù)目。Availblel[j]=K,則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。(可用資源)

最大需求矩陣Max:為n*m矩陣，定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè) 進(jìn)程對(duì)m類資源的最大需求。Max[i, j]=K,則表示進(jìn)程需要Rj類資源的最大數(shù)目為K。

分配矩陣Allocation:為n*m矩陣，定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。AlloCation[i,j]= K,則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。

需求矩陣Need:為n*m矩陣，表示每個(gè)進(jìn)程尚需的各類資源數(shù)。Need[i, j]=K,則表示進(jìn)程i還需要Rj類資源的數(shù)目為K。

銀行家算法題目舉例：

①判斷該狀態(tài)是否安全&再提出請(qǐng)求能否分配

（1）第一步：未分配資源和尚需資源比較，只有p0符合，那么先運(yùn)行p0，運(yùn)行完后已分配的釋放，變?yōu)? 4 4 1

第二步：2 4 4 1滿足P3，同樣運(yùn)行完釋放，available變?yōu)? 5 7 2，只能滿足p4 重復(fù)至最終答案，可以得到一個(gè)安全序列P0→P3→P4→P2→P1,因此該狀態(tài)安全。

（2）注意更新矩陣，再提出（0，3，2，1）請(qǐng)求，那么尚需資源need=need-request，變?yōu)椋?430）；未分配資源available=available-request（2110）（此時(shí)若need、available有一項(xiàng)資源<0了，那么直接不予分配），再重復(fù)（1)中尋找安全序列的過程，但發(fā)現(xiàn)P0執(zhí)行完后無法分配，處于不安全狀態(tài)，因此不能分配。

（這題網(wǎng)上找的 還以為沒例題 尷尬）

（1）從圖中數(shù)據(jù)我們可以利用銀行家算法的四個(gè)數(shù)據(jù)結(jié)構(gòu)，來描述當(dāng)前的系統(tǒng)狀態(tài)（最大資源需求，已分配資源，需求資源數(shù)，空閑資源數(shù)）

因?yàn)橄到y(tǒng)資源R=（17,5,20）而系統(tǒng)分配給這幾個(gè)線程的資源為Allocation=(15,2,17) 則可以求出Available=（2,3,3）(1)在T0時(shí)刻，由于Availabel大于等于Need中 P5 所在行的向量，因此Availabel能滿足 P5 的運(yùn)行，在 P5 運(yùn)行后，系統(tǒng)的狀態(tài)變更為如下圖所示（即當(dāng)P5運(yùn)行完成后，其最大所需滿足，全部釋放，available變?yōu)椋?，4，7），之后依次進(jìn)行）:

因此，在T0時(shí)刻，存在安全序列：P5，P4，P3，P2，P1（并不唯一）

(2)P2請(qǐng)求資源，P2發(fā)出請(qǐng)求向量Request(i)(0,3,4),系統(tǒng)根據(jù)銀行家算法進(jìn)行檢查;?① P2 申請(qǐng)資源Reuqest(i)（0,3,4）<=Need中 P2 所在行向量Need(i)（1,3,4）

?②?P2 申請(qǐng)資源Reuqest(i)（0,3,4）>=可以利用資源向量Availabel（2,3,3），所以，該申請(qǐng)不給于分配

(3)P4請(qǐng)求資源，P4發(fā)出請(qǐng)求向量Request(i)(2,0,1),系統(tǒng)根據(jù)銀行家算法進(jìn)行檢查;

?①Reuqest(i)（2,0,1）<= Need(i)（2,2,1）

?②?Reuqest(i)（2,0,1?<=?Availabel（2,3,3）

?③對(duì) P4 的申請(qǐng)（2,0,1）進(jìn)行預(yù)分配后，系統(tǒng)的狀態(tài)為：

可利用資源向量Availabel=（0,3,2），大于Need中 P4 所在行的向量（0,2,0），因此可以滿足 P4 的運(yùn)行。P4 運(yùn)行結(jié)束后，系統(tǒng)的狀態(tài)變?yōu)椋?/span>

?同理依次推導(dǎo)，可計(jì)算出存在安全序列P4，P5，P3，P2，P1(并不唯一）

(4)P1請(qǐng)求資源，P1發(fā)出請(qǐng)求向量Request(i)(0,2,0),系統(tǒng)根據(jù)銀行家算法進(jìn)行檢查;

?①Request(i)(0,2,0)<= Need(i)（3,4,7）

?②?Request(i)(0,2,0)<=?Availabel（2,3,3）

?③對(duì) P1 的申請(qǐng)（0,2,0）進(jìn)行預(yù)分配后，系統(tǒng)的狀態(tài)為：

由于Availabel不大于等于 P1 到 P5 任一進(jìn)程在Need中的需求向量，因此系統(tǒng)進(jìn)行預(yù)分配后處于不安全狀態(tài)，所以對(duì)于 P1 申請(qǐng)資源（0,2,0）不給予分配。

注意:因?yàn)?4)是建立在第(3)問的基礎(chǔ)上的所以Available=（0,3,2）-（0,2,0）=（0,1,2）

第三章 內(nèi)存管理：

引入目的：更好的支持多道程序的并發(fā)執(zhí)行，提高系統(tǒng)性能

主要功能：

內(nèi)存空間的分配與回收

存儲(chǔ)的保護(hù)和共享:保證各道作業(yè)在各自的存儲(chǔ)空間內(nèi)運(yùn)行，互不干擾。

地址轉(zhuǎn)換:在多道程序環(huán)境下，程序中的邏輯地址與內(nèi)存中的物理地址不可能一致， 因此存儲(chǔ)管理必須提供地址變換功能，把邏輯地址轉(zhuǎn)換成相應(yīng)的物理地址。

內(nèi)存擴(kuò)充:利用虛擬存儲(chǔ)技術(shù)或自動(dòng)覆蓋技術(shù),從邏輯上擴(kuò)充內(nèi)存。

用戶程序的主要處理階段

1).編輯階段：創(chuàng)建源文件

2).編譯階段：由編譯程序?qū)⒂脩?strong>源代碼編譯成若干目標(biāo)模塊，生成目標(biāo)文件

3).鏈接階段：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊及所需的庫(kù)函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊。生成可執(zhí)行文件(形成邏輯地址)

4).裝入階段：由裝入程序?qū)⒀b入模塊裝入內(nèi)存運(yùn)行。

5).運(yùn)行階段：得到結(jié)果

相關(guān)概念：

程序的裝入：

①絕對(duì)裝入(邏輯地址必須和實(shí)際的內(nèi)存地址完全一樣)

②靜態(tài)重定位(地址變換在裝入時(shí)一次完成)

③動(dòng)態(tài)重定位(地址變換在執(zhí)行程序的時(shí)候再完成)

程序的鏈接：靜態(tài)鏈接、裝入時(shí)鏈接、運(yùn)行時(shí)鏈接

地址空間：

邏輯地址空間(地址空間從0開始)

物理地址空間(內(nèi)存中物理單元的集合)

管理方式：

連續(xù)分配管理方式：

單一連續(xù)分配：分配到內(nèi)存固定的區(qū)域(有內(nèi)部碎片)

固定分區(qū)分配：分配到內(nèi)存不同的固定區(qū)域，分區(qū)可以相等可

固定分區(qū)分配可以不等(內(nèi)部碎片)

動(dòng)態(tài)分區(qū)分配：

可變分區(qū)存儲(chǔ)管理:按程序需要進(jìn)行動(dòng)態(tài)劃分

★動(dòng)態(tài)分區(qū)的分配策略算法:①首次適應(yīng)（最佳）：空閑分區(qū)以地址遞增的次序鏈接。分配內(nèi)存時(shí)順序查找，找到大小能滿足要求的第一個(gè)空閑分區(qū)(增大查找開銷)。②最佳適應(yīng)空閑分區(qū)按容量遞增的方式形成分區(qū)鏈，找到第一個(gè)能滿足要求的空閑分區(qū)(外部碎片過

多)③最壞適應(yīng)：空閑分區(qū)以容量遞減的次序鏈接。找到第一個(gè)能滿足要求的空閑分區(qū)，即挑選出最大的分區(qū)(對(duì)大進(jìn)程不利)。④鄰近適應(yīng)：由首次適應(yīng)算法演變而成。不同之處是，分配內(nèi)存時(shí)從上次查找結(jié)束的位置開始繼續(xù)查找。

?非連續(xù)分配管理方式（考大題）：

?基本分頁式存儲(chǔ)管理：

基本分段式存儲(chǔ)管理：

段頁式

內(nèi)存擴(kuò)充：