操作系統(tǒng)課件(第三章)：進(jìn)程管理與調(diào)度

操作系統(tǒng)

OperatingSystemsWINDOWSUNIXLINUXOS2VxWorksMacOS第三章進(jìn)程管理與調(diào)度

3.1中央處理器3.2中斷3.3進(jìn)程及其實(shí)現(xiàn)3.4進(jìn)程的控制3.5進(jìn)程切換與模式切換3.6處理器調(diào)度3.7作業(yè)的管理與調(diào)度3.8低級(jí)調(diào)度3.9線程及其基本概念3.10Linux進(jìn)程管理3.1中央處理器任何系統(tǒng)軟件都是硬件功能的延伸操作系統(tǒng)直接依賴于硬件條件OS的硬件環(huán)境以較分散的形式同各種管理相結(jié)合實(shí)現(xiàn)操作系統(tǒng)時(shí)必須理解的計(jì)算機(jī)基本結(jié)構(gòu)操作系統(tǒng)管理的重要資源3.1中央處理器3.1.1CPU的構(gòu)成與基本工作方式3.1.2特權(quán)指令和非特權(quán)指令3.1.3處理器狀態(tài)3.1.4程序狀態(tài)字3.1.1CPU的構(gòu)成與基本工作方式

處理器由運(yùn)算器、控制器、一系列的寄存器以及高速緩存構(gòu)成運(yùn)算器實(shí)現(xiàn)指令中的算術(shù)和邏輯運(yùn)算，是計(jì)算機(jī)計(jì)算的核心控制器負(fù)責(zé)控制程序運(yùn)行的流程，包括取指令、維護(hù)CPU狀態(tài)、CPU與內(nèi)存的交互等等寄存器是指令在CPU內(nèi)部作處理的過程中暫存數(shù)據(jù)、地址以及指令信息的存儲(chǔ)設(shè)備在計(jì)算機(jī)的存儲(chǔ)系統(tǒng)中它具有最快的訪問速度兩類寄存器用戶可見寄存器

高級(jí)語言編譯器通過算法分配并使用之，以減少程序訪問主存次數(shù)控制寄存器

用于控制處理器的操作，由OS的特權(quán)代碼使用，以控制其它程序的執(zhí)行3.1.1CPU的構(gòu)成與基本工作方式

處理器由運(yùn)算器、控制器、一系列的寄存器以及高速緩存構(gòu)成3.1.1CPU的構(gòu)成與基本工作方式

處理器由運(yùn)算器、控制器、一系列的寄存器以及高速緩存構(gòu)成用戶可見寄存器

高級(jí)語言編譯器通過算法分配并使用之，以減少程序訪問主存次數(shù)

包括通用寄存器、數(shù)據(jù)寄存器、地址寄存器數(shù)據(jù)寄存器（dataregister）主要用于存放操作數(shù)地址寄存器（addressregister）用于存儲(chǔ)數(shù)據(jù)及指令的物理地址、線性地址或者有效地址，用于某種特定方式的尋址。如indexregister、segmentpointer、stackpointerI/O地址寄存器I/O緩沖寄存器3.1.1CPU的構(gòu)成與基本工作方式

處理器由運(yùn)算器、控制器、一系列的寄存器以及高速緩存構(gòu)成控制寄存器

用于控制處理器的操作,大部分對(duì)于用戶是不可見的,一部分可以在某種特權(quán)模式（由OS使用）下訪問常見的控制和狀態(tài)寄存器:程序計(jì)數(shù)器（PC：ProgramCounter），記錄將要取出的指令的地址指令寄存器（IR：InstructionRegister），包含最近取出的指令程序狀態(tài)字（PSW：ProgramStatusWord），記錄處理器的運(yùn)行模式信息等等中斷寄存器存儲(chǔ)器和I/O模塊控制的寄存器3.1.1CPU的構(gòu)成與基本工作方式

處理器由運(yùn)算器、控制器、一系列的寄存器以及高速緩存構(gòu)成高速緩存(內(nèi)、外）處于CPU和物理內(nèi)存之間一般由控制器中的內(nèi)存管理單元（MMU：MemoryManagementUnit）管理訪問速度快于內(nèi)存，低于寄存器利用程序局部性原理使得高速指令處理和低速內(nèi)存訪問得以匹配，從而提高CPU的效率3.1中央處理器3.1.1CPU的構(gòu)成與基本工作方式3.1.2特權(quán)指令和非特權(quán)指令3.1.3處理器狀態(tài)3.1.4程序狀態(tài)字3.1.2特權(quán)指令和非特權(quán)指令特權(quán)指令：只能由操作系統(tǒng)使用的指令使用多道程序設(shè)計(jì)技術(shù)的計(jì)算機(jī)指令系統(tǒng)必須要區(qū)分為特權(quán)指令和非特權(quán)指令具體特權(quán)指令如啟動(dòng)I/O設(shè)備、設(shè)置時(shí)鐘、控制中斷屏蔽位、清內(nèi)存、建立存儲(chǔ)鍵，加載PSW等。常引起處理器狀態(tài)的切換?

CPU如何知道當(dāng)前運(yùn)行的是操作系統(tǒng)還是一般應(yīng)用軟件？有賴于處理器狀態(tài)的標(biāo)識(shí)3.1中央處理器3.1.1CPU的構(gòu)成與基本工作方式3.1.2特權(quán)指令和非特權(quán)指令3.1.3處理器狀態(tài)3.1.4程序狀態(tài)字3.1.3處理器狀態(tài)

根據(jù)運(yùn)行程序?qū)Y源和機(jī)器指令的使用權(quán)限將處理器設(shè)置為不同狀態(tài)多數(shù)系統(tǒng)將處理器工作狀態(tài)劃分為管態(tài)和目態(tài)管態(tài)：操作系統(tǒng)管理程序運(yùn)行的狀態(tài)，較高的特權(quán)級(jí)別，又稱為特權(quán)態(tài)（特態(tài)）、系統(tǒng)態(tài)目態(tài)：用戶程序運(yùn)行時(shí)的狀態(tài)，較低的特權(quán)級(jí)別，又稱為普通態(tài)（普態(tài)）、用戶態(tài)有些系統(tǒng)將處理器狀態(tài)劃分核心狀態(tài)，管理狀態(tài)和用戶程序狀態(tài)（目標(biāo)狀態(tài)）三種3.1.3處理器狀態(tài)處理器處于管態(tài)時(shí)：全部指令（包括特權(quán)指令）可以執(zhí)行可使用所有資源并具有改變處理器狀態(tài)的能力處理器處于目態(tài)時(shí)：只有非特權(quán)指令能執(zhí)行特權(quán)級(jí)別不同，可運(yùn)行指令集合也不同特權(quán)級(jí)別越高，可以運(yùn)行指令集合越大高特權(quán)級(jí)別對(duì)應(yīng)的可運(yùn)行指令集合包含低特權(quán)級(jí)的3.1.3處理器狀態(tài)實(shí)例：x86系列處理器386、486、Pentium系列都支持4個(gè)處理器特權(quán)級(jí)別（特權(quán)環(huán)：R0、R1、R2和R3）從R0到R3特權(quán)能力依次降低R0相當(dāng)于雙狀態(tài)系統(tǒng)的管態(tài)R3相當(dāng)于目態(tài)R1和R2則介于兩者之間，它們能夠運(yùn)行的指令集合具有包含關(guān)系3.1.3處理器狀態(tài)目態(tài)--管態(tài)其轉(zhuǎn)換的唯一途徑是通過中斷管態(tài)--目態(tài)可用設(shè)置PSW(修改程序狀態(tài)字)可實(shí)現(xiàn)3.1中央處理器3.1.1CPU的構(gòu)成與基本工作方式3.1.2特權(quán)指令和非特權(quán)指令3.1.3處理器狀態(tài)3.1.4程序狀態(tài)字3.1.4程序狀態(tài)字處理器狀態(tài)是在PSW中專門設(shè)置一位，根據(jù)運(yùn)行程序使用指令的權(quán)限而設(shè)置，PSW(ProgramStatusWord)。PSW用來控制指令執(zhí)行順序并保留和指示與程序有關(guān)的系統(tǒng)狀態(tài)，主要作用是實(shí)現(xiàn)程序狀態(tài)的保護(hù)和恢復(fù)。每個(gè)進(jìn)程都有一個(gè)與其執(zhí)行相關(guān)的PSW，每個(gè)處理器都設(shè)置一個(gè)PSW寄存器。進(jìn)程占有處理器執(zhí)行，它的PSW將占有PSW寄存器。3.1.4程序狀態(tài)字PSW寄存器包括以下內(nèi)容：程序基本狀態(tài)：(1)程序計(jì)數(shù)器；(2)條件碼；(3）處理器狀態(tài)位。中斷碼。保存程序執(zhí)行時(shí)當(dāng)前發(fā)生的中斷事件。中斷屏蔽位。指明程序執(zhí)行中發(fā)生中斷事件時(shí)，是否響應(yīng)出現(xiàn)的中斷事件。第三章進(jìn)程管理與調(diào)度

3.1中央處理器3.2中斷3.3進(jìn)程及其實(shí)現(xiàn)3.4進(jìn)程的控制3.5進(jìn)程切換與模式切換3.6處理器調(diào)度3.7作業(yè)的管理與調(diào)度3.8低級(jí)調(diào)度3.9線程及其基本概念3.10Linux進(jìn)程管理3.2中斷3.2.1中斷的概念3.2.2中斷的分類3.2.1中斷的概念什么是中斷?指CPU對(duì)系統(tǒng)中或系統(tǒng)外發(fā)生異步事件的響應(yīng)異步事件是指無一定時(shí)序關(guān)系的隨機(jī)發(fā)生事件CPU暫停正在執(zhí)行的程序，保留現(xiàn)場(chǎng)后自動(dòng)轉(zhuǎn)去執(zhí)行相應(yīng)事件的處理程序，處理完成后返回?cái)帱c(diǎn)，繼續(xù)執(zhí)行被打斷的程序如外部設(shè)備完成數(shù)據(jù)傳輸，實(shí)時(shí)設(shè)備出現(xiàn)異常等“中斷”名稱源于：當(dāng)異步事件發(fā)生后，打斷了對(duì)當(dāng)前程序的執(zhí)行而轉(zhuǎn)去處理該異步事件直到處理完了后，再轉(zhuǎn)回原程序中斷點(diǎn)繼續(xù)執(zhí)行3.2.1中斷的概念3.2.2中斷的分類——從中斷的性質(zhì)和激活的手段來分(IBM)：強(qiáng)迫性中斷正在運(yùn)行的程序所不期望的，由于某種硬件故障或外部請(qǐng)求引起的自愿性中斷用戶在程序中有意識(shí)安排的中斷，是由于用戶在編制程序時(shí)因?yàn)橐蟛僮飨到y(tǒng)提供服務(wù)，有意使用“訪管”指令或系統(tǒng)調(diào)用，使中斷發(fā)生3.2.2中斷的分類——按事件來源和實(shí)現(xiàn)手段分類(MS/LINUX)：硬中斷軟中斷外中斷(中斷、異步中斷)內(nèi)中斷(異常、同步中斷)信號(hào)軟件中斷按事件來源和實(shí)現(xiàn)手段分類中斷和異常要通過硬件設(shè)施來產(chǎn)生中斷請(qǐng)求，是硬中斷。軟中斷是利用硬中斷的概念，用軟件方法對(duì)中斷機(jī)制進(jìn)行模擬，實(shí)現(xiàn)宏觀上的異步執(zhí)行效果。3.2.2中斷的分類——按事件來源和實(shí)現(xiàn)手段分類(MS/LINUX)：“中斷”(硬中斷)用于外部設(shè)備對(duì)CPU的中斷(中斷的是正在運(yùn)行的任何程序)，轉(zhuǎn)向中斷處理程序上半部分執(zhí)行；“異?！?硬中斷)因指令執(zhí)行不正常而中斷CPU(中斷的是正在執(zhí)行這條指令的程序)，轉(zhuǎn)向異常處理程序；“軟件中斷”(軟中斷)用于硬中斷服務(wù)程序?qū)?nèi)核的中斷，在上半部分中發(fā)出軟件中斷(即標(biāo)記下半部分)，使得中斷下半部分在適當(dāng)時(shí)刻獲得處理；“信號(hào)”(軟中斷)用于內(nèi)核或進(jìn)程對(duì)某個(gè)進(jìn)程的中斷，通知進(jìn)程某個(gè)特定事件發(fā)生或迫使進(jìn)程執(zhí)行信號(hào)處理程序。3.2.2中斷的分類——按事件來源和實(shí)現(xiàn)手段分類(MS/LINUX)：?

外中斷(中斷或異步中斷)--是指來自處理器之外的中斷信號(hào)，包括時(shí)鐘中斷、鍵盤中斷、它機(jī)中斷和設(shè)備中斷等；外中斷又分可屏蔽中斷和不可屏蔽中斷，每個(gè)不同中斷具有不同的中斷優(yōu)先級(jí)，表示事件的緊急程度，在處理高一級(jí)中斷時(shí)，往往會(huì)屏蔽部分或全部低級(jí)中斷。?

內(nèi)中斷(異常或同步中斷)--是指來自處理器內(nèi)部，通常由于程序執(zhí)行中，發(fā)現(xiàn)與當(dāng)前指令關(guān)聯(lián)的、不正常的、或是錯(cuò)誤的事件。

3.2.2中斷的分類——按事件來源和實(shí)現(xiàn)手段分類(MS/LINUX)：?

中斷是由與現(xiàn)行指令無關(guān)的中斷信號(hào)觸發(fā)的(異步的)，且中斷的發(fā)生與CPU處在用戶模式或內(nèi)核模式無關(guān)，在兩條機(jī)器指令之間才可響應(yīng)中斷，一般來說，中斷處理程序提供的服務(wù)不是為當(dāng)前進(jìn)程所需的；?

異常是由處理器正在執(zhí)行現(xiàn)行指令而引起的，一條指令執(zhí)行期間允許響應(yīng)異常，異常處理程序提供的服務(wù)是為當(dāng)前進(jìn)程所用的。異常包括很多方面，有出錯(cuò)(fault)，也有陷入(trap)等。3.2.2中斷的分類——按事件來源和實(shí)現(xiàn)手段分類(MS/LINUX)：?Linux為例，異常按錯(cuò)誤報(bào)告方式分四種：

故障、陷阱、終止、編程異常。?故障發(fā)生時(shí)保存的返回指令地址指向觸發(fā)異常的當(dāng)前那條指令，故障處理后會(huì)重新執(zhí)行。編程異常和陷阱是由于執(zhí)行訪管指令引起的同步操作，異常返回時(shí)，回到觸發(fā)異常的下一條指令。第三章進(jìn)程管理與調(diào)度

3.1中央處理器3.2中斷3.3進(jìn)程及其實(shí)現(xiàn)3.4進(jìn)程的控制3.5進(jìn)程切換與模式切換3.6處理器調(diào)度3.7作業(yè)的管理與調(diào)度3.8低級(jí)調(diào)度3.9線程及其基本概念3.10Linux進(jìn)程管理3.3進(jìn)程及其實(shí)現(xiàn)3.3.1進(jìn)程定義3.3.2進(jìn)程的類型和特性3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換3.3.4進(jìn)程控制塊3.3.5進(jìn)程要素3.3.1進(jìn)程定義

進(jìn)程是為了描述程序在并發(fā)執(zhí)行時(shí)對(duì)系統(tǒng)資源的共享，所需的一個(gè)描述程序執(zhí)行時(shí)動(dòng)態(tài)特征的概念定義：Process(“任務(wù)”（task）或“活動(dòng)”（active）)

進(jìn)程是具有獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合上的一次運(yùn)行活動(dòng)，是系統(tǒng)進(jìn)行資源分配、調(diào)度和保護(hù)的獨(dú)立單位3.3.1進(jìn)程定義操作系統(tǒng)為什么要引入進(jìn)程概念?原因1-刻畫系統(tǒng)的動(dòng)態(tài)性，發(fā)揮系統(tǒng)的并發(fā)性，提高資源利用率。原因2-它能解決系統(tǒng)的“共享性”，正確描述程序的執(zhí)行狀態(tài)?！翱稍儆谩背绦颉翱稍偃搿背绦?.3.1進(jìn)程定義“可再入”程序編譯程序P編譯源程序甲，從A點(diǎn)開始工作，執(zhí)行到B點(diǎn)時(shí)需將信息記到磁盤上，且程序P在B點(diǎn)等待磁盤傳輸。為提高系統(tǒng)效率，利用編譯程序的“可再入”性，讓編譯程序P再為源程序乙進(jìn)行編譯，仍從A點(diǎn)開始工作。編譯程序P(P的入口,處理源程序乙)(P把源程序甲的信息記盤等磁盤完成)AB源程序甲源程序乙3.3.1進(jìn)程定義“可再入”程序把編譯程序P，與服務(wù)對(duì)象聯(lián)系起來，P為甲服務(wù)就說構(gòu)成進(jìn)程P甲，P為乙服務(wù)則構(gòu)成進(jìn)程P乙。兩個(gè)進(jìn)程雖共享程序P，但它們可同時(shí)執(zhí)行且彼此按各自的速度獨(dú)立執(zhí)行。可見程序與計(jì)算(程序的執(zhí)行)不再一一對(duì)應(yīng)，進(jìn)程是一個(gè)既能用來共享資源，又能描述程序并發(fā)執(zhí)行過程的一個(gè)基本單位。編譯程序P(P的入口,處理源程序乙)(P把源程序甲的信息記盤等磁盤完成)AB源程序甲源程序乙3.3進(jìn)程及其實(shí)現(xiàn)3.3.1進(jìn)程定義3.3.2進(jìn)程的類型和特性3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換3.3.4進(jìn)程控制塊3.3.5進(jìn)程要素3.3.2進(jìn)程的類型和特性

1、進(jìn)程分類：系統(tǒng)進(jìn)程用戶進(jìn)程（系統(tǒng)進(jìn)程優(yōu)先于用戶進(jìn)程）3.3.2進(jìn)程的類型和特性

2、進(jìn)程的屬性

?結(jié)構(gòu)性

?共享性

?動(dòng)態(tài)性

?獨(dú)立性

?制約性

?并發(fā)性3.3.2進(jìn)程的類型和特性

3、程序與進(jìn)程之間的區(qū)別進(jìn)程更能真實(shí)地描述并發(fā)，而程序不能進(jìn)程是由程序和數(shù)據(jù)和控制塊三部分組成的程序是靜態(tài)的，進(jìn)程是動(dòng)態(tài)的進(jìn)程有生命周期，有誕生有消亡，短暫的；而程序是相對(duì)長(zhǎng)久的一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程，反之亦然進(jìn)程具有創(chuàng)建其他進(jìn)程的功能，而程序沒有3.3進(jìn)程及其實(shí)現(xiàn)3.3.1進(jìn)程定義3.3.2進(jìn)程的類型和特性3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換3.3.4進(jìn)程控制塊3.3.5進(jìn)程要素3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換1、三種進(jìn)程狀態(tài)運(yùn)行態(tài)（Running）：進(jìn)程占有CPU，并在CPU上運(yùn)行就緒態(tài)（Ready）： 一個(gè)進(jìn)程已經(jīng)具備運(yùn)行條件，但由于無CPU暫時(shí)不能運(yùn)行的狀態(tài)（當(dāng)調(diào)度給其CPU時(shí)，立即可以運(yùn)行）等待態(tài)（Blocked）：

又叫阻塞態(tài)、封鎖態(tài)、睡眠態(tài)指進(jìn)程因等待某種事件的發(fā)生而暫時(shí)不能運(yùn)行的狀態(tài)（即使CPU空閑，該進(jìn)程也不可運(yùn)行）運(yùn)行就緒等待

3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換1、三種進(jìn)程狀態(tài)運(yùn)行就緒等待

就緒-->運(yùn)行調(diào)度程序選擇一個(gè)新的進(jìn)程運(yùn)行運(yùn)行-->就緒運(yùn)行進(jìn)程用完了時(shí)間片運(yùn)行進(jìn)程被中斷，因?yàn)橐桓邇?yōu)先級(jí)進(jìn)程

處于就緒狀態(tài)運(yùn)行-->等待當(dāng)一進(jìn)程必須等待時(shí)OS尚未完成服務(wù)對(duì)一資源的訪問尚不能進(jìn)行初始化I/O且必須等待結(jié)果等待某一進(jìn)程提供輸入(IPC)等待-->就緒當(dāng)所等待的事件發(fā)生時(shí)3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換2、五種進(jìn)程狀態(tài)三種進(jìn)程狀態(tài)->五狀態(tài)進(jìn)程模型增加:創(chuàng)建狀態(tài)，終止?fàn)顟B(tài)創(chuàng)建(新new)狀態(tài)OS已完成為創(chuàng)建一進(jìn)程所必要的工作已構(gòu)造了進(jìn)程標(biāo)識(shí)符已創(chuàng)建了管理進(jìn)程所需的表格但還沒有允許執(zhí)行該進(jìn)程(尚未同意)

因?yàn)橘Y源有限終止（退出exit)狀態(tài)中止后進(jìn)程移入該狀態(tài)它不再有執(zhí)行資格表格和其它信息暫時(shí)由輔助程序保留一旦其他進(jìn)程完成了對(duì)終止態(tài)進(jìn)程的信息抽取之后，系統(tǒng)將刪除該進(jìn)程。3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換2、五種進(jìn)程狀態(tài)三種進(jìn)程狀態(tài)->五狀態(tài)進(jìn)程模型NULL→新建態(tài)：創(chuàng)建一個(gè)子進(jìn)程。新建態(tài)→就緒態(tài)：系統(tǒng)完成了進(jìn)程創(chuàng)建操作，且當(dāng)前系統(tǒng)的性能和內(nèi)存的容量均允許。運(yùn)行態(tài)→終止態(tài)：一個(gè)進(jìn)程到達(dá)自然結(jié)束點(diǎn)，或出現(xiàn)了無法克服的錯(cuò)誤，或被操作系統(tǒng)所終結(jié)，或被其他有終止權(quán)的進(jìn)程所終結(jié)。終止態(tài)→NULL：完成善后操作。就緒態(tài)→終止態(tài)：某些操作系統(tǒng)允許父進(jìn)程終結(jié)子進(jìn)程。等待態(tài)→終止態(tài)：某些操作系統(tǒng)允許父進(jìn)程終結(jié)子進(jìn)程。3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換3、七種進(jìn)程狀態(tài)五狀態(tài)進(jìn)程模型->七狀態(tài)進(jìn)程模型增加:“掛起”狀態(tài)活動(dòng)掛起事件發(fā)生事件發(fā)生等待事件掛起調(diào)度超時(shí)釋放活動(dòng)掛起3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換3、七種進(jìn)程狀態(tài)五狀態(tài)進(jìn)程模型->七狀態(tài)進(jìn)程模型增加:“掛起”狀態(tài)

為什么要有“掛起”狀態(tài)?

由于進(jìn)程的不斷創(chuàng)建，系統(tǒng)資源已不能滿足進(jìn)程運(yùn)行的要求，就必須把某些進(jìn)程掛起（suspend），對(duì)換到

磁盤鏡像區(qū)中，暫時(shí)不

參與進(jìn)程調(diào)度，起到平

滑系統(tǒng)操作負(fù)荷的目的。3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換3、七種進(jìn)程狀態(tài)五狀態(tài)進(jìn)程模型->七狀態(tài)進(jìn)程模型掛起（Suspend）：把一個(gè)進(jìn)程從內(nèi)存轉(zhuǎn)到外存可能有以下幾種情況阻塞→阻塞掛起：沒有進(jìn)程處于就緒狀態(tài)或就緒進(jìn)程要求更多內(nèi)存資源時(shí)，發(fā)生這種轉(zhuǎn)換，以提交新進(jìn)程或運(yùn)行就緒進(jìn)程就緒→就緒掛起：當(dāng)有高優(yōu)先級(jí)阻塞（系統(tǒng)認(rèn)為會(huì)很快就緒的）進(jìn)程和低優(yōu)先級(jí)就緒進(jìn)程時(shí)，系統(tǒng)會(huì)選擇掛起低優(yōu)先級(jí)就緒進(jìn)程運(yùn)行→就緒掛起：對(duì)搶占式系統(tǒng)，當(dāng)有高優(yōu)先級(jí)阻塞掛起進(jìn)程因事件出現(xiàn)而進(jìn)入就緒掛起時(shí)，系統(tǒng)可能會(huì)把運(yùn)行進(jìn)程轉(zhuǎn)到就緒掛起狀態(tài)3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換3、七種進(jìn)程狀態(tài)五狀態(tài)進(jìn)程模型->七狀態(tài)進(jìn)程模型激活（Activate）：把一個(gè)進(jìn)程從外存轉(zhuǎn)到內(nèi)存；可能有以下幾種情況：就緒掛起→就緒：沒有就緒進(jìn)程或掛起就緒進(jìn)程優(yōu)先級(jí)高于就緒進(jìn)程時(shí)，發(fā)生轉(zhuǎn)換阻塞掛起→阻塞：當(dāng)一個(gè)進(jìn)程釋放足夠內(nèi)存時(shí)，系統(tǒng)會(huì)把一個(gè)高優(yōu)先級(jí)阻塞掛起（系統(tǒng)認(rèn)為會(huì)很快出現(xiàn)所等待的事件）進(jìn)程轉(zhuǎn)換為阻塞狀態(tài)。3.3進(jìn)程及其實(shí)現(xiàn)3.3.1進(jìn)程定義3.3.2進(jìn)程的類型和特性3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換3.3.4進(jìn)程控制塊3.3.5進(jìn)程要素3.3.4進(jìn)程控制塊1、定義進(jìn)程控制塊（ProcessControlBlock）是系統(tǒng)為了管理進(jìn)程設(shè)置的一個(gè)專門的數(shù)據(jù)結(jié)構(gòu)，用它來記錄進(jìn)程的外部特征，描述進(jìn)程的運(yùn)動(dòng)變化過程系統(tǒng)利用PCB來控制和管理進(jìn)程，所以PCB是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志進(jìn)程與PCB是一一對(duì)應(yīng)的3.3.4進(jìn)程控制塊2、構(gòu)成3.3.4進(jìn)程控制塊2、構(gòu)成1、進(jìn)程描述信息：進(jìn)程標(biāo)識(shí)符(processID)，唯一，通常是一個(gè)整數(shù)進(jìn)程名，通?；诳蓤?zhí)行文件名（不唯一）用戶標(biāo)識(shí)符(userID)進(jìn)程組關(guān)系3.3.4進(jìn)程控制塊2、構(gòu)成2、進(jìn)程控制信息：當(dāng)前狀態(tài)優(yōu)先級(jí)(priority)代碼執(zhí)行入口地址程序的外存地址運(yùn)行統(tǒng)計(jì)信息（執(zhí)行時(shí)間、頁(yè)面調(diào)度）進(jìn)程間同步和通信阻塞原因進(jìn)程的隊(duì)列指針進(jìn)程的消息隊(duì)列指針3.3.4進(jìn)程控制塊2、構(gòu)成3、所擁有的資源和使用情況：虛擬地址空間的現(xiàn)狀打開文件列表4、CPU現(xiàn)場(chǎng)保護(hù)信息：寄存器值（通用、程序計(jì)數(shù)器PC、狀態(tài)PSW，地址包括棧指針）指向賦予該進(jìn)程的段/頁(yè)表的指針3.3.4進(jìn)程控制塊3、組織系統(tǒng)把所有PCB組織在一起，并把它們放在內(nèi)存的固定區(qū)域，就構(gòu)成了PCB表PCB表的大小決定了

系統(tǒng)中最多可同時(shí)

存在的進(jìn)程個(gè)數(shù)，

稱為系統(tǒng)的并發(fā)度運(yùn)行隊(duì)列就緒隊(duì)列等待隊(duì)列3.3進(jìn)程及其實(shí)現(xiàn)3.3.1進(jìn)程定義3.3.2進(jìn)程的類型和特性3.3.3進(jìn)程的狀態(tài)和轉(zhuǎn)換3.3.4進(jìn)程控制塊3.3.5進(jìn)程要素3.3.5進(jìn)程要素1、構(gòu)成進(jìn)程程序進(jìn)程數(shù)據(jù)棧用于系統(tǒng)調(diào)用、過程調(diào)用時(shí)的參數(shù)存儲(chǔ)和傳遞進(jìn)程控制塊PCB(進(jìn)程屬性)處于核心段用戶進(jìn)程不能直接訪問、修改自己的PCB3.3.5進(jìn)程要素2、虛存中的進(jìn)程映象3.3.5進(jìn)程要素3、進(jìn)程上下文（1）進(jìn)程上下文：進(jìn)程本身＋運(yùn)行環(huán)境對(duì)進(jìn)程執(zhí)行活動(dòng)全過程的靜態(tài)描述由進(jìn)程的用戶地址空間內(nèi)容、硬件寄存器內(nèi)容及與該進(jìn)程相關(guān)的核心數(shù)據(jù)結(jié)構(gòu)組成用戶級(jí)上下文：進(jìn)程的用戶地址空間（包括用戶棧各層次），包括用戶正文段、用戶數(shù)據(jù)段和用戶棧寄存器級(jí)上下文：PSW寄存器、處理器狀態(tài)寄存器、棧指針、通用寄存器的值系統(tǒng)級(jí)上下文：靜態(tài)部分（PCB和資源表格）動(dòng)態(tài)部分：核心棧（核心過程的棧結(jié)構(gòu)，不同進(jìn)程在調(diào)用相同核心過程時(shí)有不同核心棧）3.3.5進(jìn)程要素3、進(jìn)程上下文（2）進(jìn)程上下文切換進(jìn)程切換是讓處于運(yùn)行態(tài)的進(jìn)程中斷運(yùn)行，讓出處理器，這時(shí)要做一次進(jìn)程上下文切換、即保存老進(jìn)程狀態(tài)而裝入被保護(hù)了的新進(jìn)程的狀態(tài)，以便新進(jìn)程運(yùn)行。

3.3.5進(jìn)程要素3、進(jìn)程上下文（2）進(jìn)程上下文切換——進(jìn)程切換的步驟保存被中斷進(jìn)程的處理器現(xiàn)場(chǎng)信息。修改被中斷進(jìn)程的進(jìn)程控制塊的有關(guān)信息，如進(jìn)程狀態(tài)等。把被中斷進(jìn)程的進(jìn)程控制塊加入有關(guān)隊(duì)列。選擇下一個(gè)占有處理器運(yùn)行的進(jìn)程。修改被選中進(jìn)程的進(jìn)程控制塊的有關(guān)信息。根據(jù)被選中進(jìn)程設(shè)置操作系統(tǒng)用到的地址轉(zhuǎn)換和存儲(chǔ)保護(hù)信息。根據(jù)被選中進(jìn)程恢復(fù)處理器現(xiàn)場(chǎng)。第三章進(jìn)程管理與調(diào)度

3.1中央處理器3.2中斷3.3進(jìn)程及其實(shí)現(xiàn)3.4進(jìn)程的控制3.5進(jìn)程切換與模式切換3.6處理器調(diào)度3.7作業(yè)的管理與調(diào)度3.8低級(jí)調(diào)度3.9線程及其基本概念3.10Linux進(jìn)程管理3.4

進(jìn)程的控制1、概述處理器管理的一個(gè)主要工作是對(duì)進(jìn)程的控制。進(jìn)程控制是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。

包括：創(chuàng)建進(jìn)程、阻塞進(jìn)程、喚醒進(jìn)程、掛起進(jìn)程、激活進(jìn)程、終止進(jìn)程和撤銷進(jìn)程等2、原語這些控制和管理功能是由操作系統(tǒng)的原語來實(shí)現(xiàn)。原語(Primitive)是在管態(tài)下執(zhí)行、完成系統(tǒng)特定功能的過程。原語和機(jī)器指令類似，其特點(diǎn)是執(zhí)行過程中不允許被中斷，是一個(gè)不可分割的基本單位，原語的執(zhí)行是順序的而不可能是并發(fā)的。一種原語的實(shí)現(xiàn)方法是以系統(tǒng)調(diào)用方式提供原語接口，且采用屏蔽中斷的方式來實(shí)現(xiàn)原語功能，以保證原語操作不被打斷的特性。3.4

進(jìn)程的控制3.4.1進(jìn)程的創(chuàng)建3.4.2進(jìn)程的阻塞和喚醒3.4.3進(jìn)程的撤消3.4.3進(jìn)程的掛起和激活3.4

進(jìn)程的控制3.4.1進(jìn)程的創(chuàng)建1、進(jìn)程創(chuàng)建方式（1）由系統(tǒng)程序模塊統(tǒng)一創(chuàng)建，例如在批處理系統(tǒng)中，由操作系統(tǒng)的作業(yè)調(diào)度程序?yàn)橛脩糇鳂I(yè)創(chuàng)建相應(yīng)的進(jìn)程以完成用戶作業(yè)所要求的功能。（2）由父進(jìn)程創(chuàng)建，例如在層次結(jié)構(gòu)的系統(tǒng)中，父進(jìn)程創(chuàng)建子進(jìn)程以完成并行工作。進(jìn)程創(chuàng)建來源于以下事件：提交一個(gè)批處理作業(yè)。在終端上交互式的登錄。操作系統(tǒng)創(chuàng)建一個(gè)服務(wù)進(jìn)程。存在的進(jìn)程孵化（spawn）新的進(jìn)程。3.4.1進(jìn)程的創(chuàng)建2、進(jìn)程創(chuàng)建過程父進(jìn)程(ParentProcess)建子進(jìn)程(ChildProcess)時(shí)，系統(tǒng)在進(jìn)程表中增加一項(xiàng)，并從PCB池中取一個(gè)空白PCB。為新進(jìn)程的進(jìn)程映像分配地址空間。傳遞環(huán)境變量，構(gòu)造共享地址空間。為新進(jìn)程分配資源，除內(nèi)存空間外，還有其他各種資源。查找輔存，找到進(jìn)程正文段并裝到正文區(qū)。初始化進(jìn)程控制塊，為新進(jìn)程分配進(jìn)程標(biāo)識(shí)符，初始化PSW。加入就緒進(jìn)程隊(duì)列,將進(jìn)程投入運(yùn)行。通知操作系統(tǒng)的某些模塊，如記賬程序、性能監(jiān)控程序。3.4.1進(jìn)程的創(chuàng)建3、UNIX/Linux進(jìn)程創(chuàng)建實(shí)例在UNIX系統(tǒng)中，只有0進(jìn)程是在系統(tǒng)引導(dǎo)時(shí)被創(chuàng)建的，在系統(tǒng)初啟時(shí)由0進(jìn)程創(chuàng)建1進(jìn)程，以后0進(jìn)程變成對(duì)換進(jìn)程，1進(jìn)程成為系統(tǒng)中的始祖進(jìn)程。UNIX利用fork()為每個(gè)終端創(chuàng)建一個(gè)子進(jìn)程為用戶服務(wù)，如等待用戶登錄、執(zhí)行SHELL命令解釋程序等，每個(gè)終端進(jìn)程又可利用fork()來創(chuàng)建其子進(jìn)程，從而形成一棵進(jìn)程樹。可以說，系統(tǒng)中除0進(jìn)程外的所有進(jìn)程都是用fork()創(chuàng)建的。系統(tǒng)調(diào)用fork()的源代碼參見：

/USR/SRC/LINUX/KERNEL/FORK.C3.4.1進(jìn)程的創(chuàng)建3、UNIX/Linux進(jìn)程創(chuàng)建實(shí)例實(shí)例：編寫一段程序，使用系統(tǒng)調(diào)用fork()創(chuàng)建兩個(gè)子進(jìn)程。當(dāng)此程序運(yùn)行時(shí)，在系統(tǒng)中有一個(gè)父進(jìn)程和兩個(gè)子進(jìn)程活動(dòng)。讓每一個(gè)進(jìn)程在屏幕上顯示不同的字符串：子進(jìn)程顯示'daughter…'及'son……'，父進(jìn)程顯示'parent……'。3.4.1進(jìn)程的創(chuàng)建3、UNIX/Linux進(jìn)程創(chuàng)建實(shí)例實(shí)例：（1）所涉及的系統(tǒng)調(diào)用fork()創(chuàng)建一個(gè)新進(jìn)程。系統(tǒng)調(diào)用格式：pid=fork()

參數(shù)定義：intfork()fork()返回值意義如下：0：在子進(jìn)程中，pid變量保存的fork()返回值為0，表示當(dāng)前進(jìn)程是子進(jìn)程。>0：在父進(jìn)程中，pid變量保存的fork()返回值為子進(jìn)程的id值（進(jìn)程唯一標(biāo)識(shí)符）。-1：創(chuàng)建失敗。3.4.1進(jìn)程的創(chuàng)建3、UNIX/Linux進(jìn)程創(chuàng)建實(shí)例實(shí)例：（1）所涉及的系統(tǒng)調(diào)用fork()創(chuàng)建一個(gè)新進(jìn)程。如果fork()調(diào)用成功，它向父進(jìn)程返回子進(jìn)程的PID，并向子進(jìn)程返回0，即fork()被調(diào)用了一次，但返回了兩次。此時(shí)OS在內(nèi)存中建立一個(gè)新進(jìn)程，所建的新進(jìn)程是調(diào)用fork()父進(jìn)程（parentprocess）的副本，稱為子進(jìn)程（childprocess）。子進(jìn)程繼承了父進(jìn)程的許多特性，并具有與父進(jìn)程完全相同的用戶級(jí)上下文。父進(jìn)程與子進(jìn)程并發(fā)執(zhí)行3.4.1進(jìn)程的創(chuàng)建3、UNIX/Linux進(jìn)程創(chuàng)建實(shí)例實(shí)例：#include<stdio.h>main(){intp1,p2,i;while((p1=fork())==-1);/*創(chuàng)建子進(jìn)程p1*/if(p1==0)

for(i=0;i<10;i++)printf("daughter%d\n",i);else{while((p2=fork())==-1);/*創(chuàng)建子進(jìn)程p2*/if(p2==0)

for(i=0;i<10;i++)

printf("son%d\n",i);else

for(i=0;i<10;i++)

printf("parent%d\n",i);}}3.4.1進(jìn)程的創(chuàng)建3.4.2進(jìn)程的阻塞和喚醒3.4.3進(jìn)程的撤消3.4.3進(jìn)程的掛起和激活3.4

進(jìn)程的控制3.4.2進(jìn)程的阻塞和喚醒1、進(jìn)程阻塞阻塞原語在一個(gè)進(jìn)程期待某一事件（如鍵盤輸入數(shù)據(jù)、寫盤、其他進(jìn)程發(fā)來的數(shù)據(jù)等）發(fā)生，但發(fā)生條件尚不具備，被該進(jìn)程調(diào)用來阻塞自己；阻塞原語在阻塞一個(gè)進(jìn)程時(shí)，由于該進(jìn)程正處于執(zhí)行狀態(tài)，故應(yīng)先中斷處理機(jī)和保存該進(jìn)程的CPU現(xiàn)場(chǎng)，保存現(xiàn)場(chǎng)信息到PSW；然后，將被阻塞進(jìn)程置“阻塞”狀態(tài)后插入等待隊(duì)列中，再轉(zhuǎn)進(jìn)程調(diào)度程序選擇新的就緒進(jìn)程投入運(yùn)行。3.4.2進(jìn)程的阻塞和喚醒2、進(jìn)程喚醒一種是由系統(tǒng)進(jìn)程喚醒。系統(tǒng)進(jìn)程統(tǒng)一控制事件的發(fā)生并將“事件發(fā)生”這一消息通知等待進(jìn)程，從而使得該進(jìn)程因等待事件已發(fā)生而進(jìn)入就緒隊(duì)列。另一種是由事件發(fā)生進(jìn)程喚醒。事件發(fā)生進(jìn)程和被喚醒進(jìn)程之間是合作關(guān)系。因此，喚醒原語既可被系統(tǒng)進(jìn)程調(diào)用，也可被事件發(fā)生進(jìn)程調(diào)用。3.4.1進(jìn)程的創(chuàng)建3.4.2進(jìn)程的阻塞和喚醒3.4.3進(jìn)程的撤消3.4.3進(jìn)程的掛起和激活3.4

進(jìn)程的控制3.4.3進(jìn)程的撤消1、以下情況導(dǎo)致進(jìn)程被撤消：

①該進(jìn)程已完成所要求的功能而正常終止；②由于某種錯(cuò)誤導(dǎo)致非正常終止；③祖先進(jìn)程要求撤消某個(gè)子進(jìn)程。2、撤銷原語終止進(jìn)程具體步驟：①根據(jù)撤銷進(jìn)程標(biāo)識(shí)號(hào)，從相應(yīng)隊(duì)列中找到它的PCB；②將該進(jìn)程擁有的資源歸還給父進(jìn)程或操作系統(tǒng)；③若該進(jìn)程擁有子進(jìn)程，應(yīng)先撤銷它所有子孫進(jìn)程，以防它們脫離控制；④撤銷進(jìn)程出隊(duì)，將它的PCB歸還到PCB池。3.4.1進(jìn)程的創(chuàng)建3.4.2進(jìn)程的阻塞和喚醒3.4.3進(jìn)程的撤消3.4.3進(jìn)程的掛起和激活3.4

進(jìn)程的控制3.4.3進(jìn)程的掛起和激活1、掛起原語執(zhí)行過程：掛起原語執(zhí)行過程如下：檢查要被掛起進(jìn)程的狀態(tài)，若處于活動(dòng)就緒態(tài)就修改為掛起就緒，若處于阻塞態(tài)，則修改為掛起阻塞。被掛起進(jìn)程PCB的非常駐部分要交換到磁盤對(duì)換區(qū)。3.4.3進(jìn)程的掛起和激活2、激活原語執(zhí)行過程：激活原語主要工作：把進(jìn)程PCB非常駐部分調(diào)進(jìn)內(nèi)存，修改它的狀態(tài)，掛起等待態(tài)改為等待態(tài)，掛起就緒態(tài)改為就緒態(tài)，排入相應(yīng)隊(duì)列中。掛起原語既可由進(jìn)程自己也可由其他進(jìn)程調(diào)用，但激活原語卻只能由其他進(jìn)程調(diào)用。第三章進(jìn)程管理與調(diào)度

3.1中央處理器3.2中斷3.3進(jìn)程及其實(shí)現(xiàn)3.4進(jìn)程的控制3.5進(jìn)程切換與模式切換3.6處理器調(diào)度3.7作業(yè)的管理與調(diào)度3.8低級(jí)調(diào)度3.9線程及其基本概念3.10Linux進(jìn)程管理3.5.1執(zhí)行模式3.5.2模式切換3.5.3進(jìn)程切換與模式切換比較3.5

進(jìn)程切換與模式切換3.5.1執(zhí)行模式1、處理機(jī)兩種執(zhí)行模式：特權(quán)模式又稱核心模式、系統(tǒng)模式或控制模式，操作系統(tǒng)核心程序在這種模式下運(yùn)行。某些指令只能在特權(quán)模式下執(zhí)行，如讀寫處理機(jī)狀態(tài)字PSW等控制寄存器以及存儲(chǔ)管理相關(guān)的一些指令。用戶模式就是非特權(quán)的模式，用戶程序在這個(gè)模式下運(yùn)行?，F(xiàn)代操作系統(tǒng)有許多系統(tǒng)功能也由運(yùn)行在用戶模式的程序?qū)崿F(xiàn)。如Linux操作系統(tǒng)的1號(hào)進(jìn)程，它在用戶態(tài)運(yùn)行INIT程序，負(fù)責(zé)所有用戶終端進(jìn)程的創(chuàng)建。

3.5.1執(zhí)行模式2、目的：為了保護(hù)操作系統(tǒng)和操作系統(tǒng)的數(shù)據(jù)表格不被可能出錯(cuò)的用戶程序破壞。當(dāng)進(jìn)程運(yùn)行系統(tǒng)內(nèi)核程序時(shí)，系統(tǒng)只是保存了用戶程序的運(yùn)行現(xiàn)場(chǎng)，包括所有處理機(jī)狀態(tài)、現(xiàn)場(chǎng)信息，保留原用戶程序用數(shù)據(jù)棧。核心工作狀態(tài)時(shí)處理機(jī)執(zhí)行任何特權(quán)指令或訪問系統(tǒng)的虛空間都不會(huì)報(bào)錯(cuò)，待到返回用戶態(tài)程序時(shí)，原保護(hù)的程序狀態(tài)字被恢復(fù)，處理機(jī)模式又轉(zhuǎn)到用戶態(tài)下，這以后如果執(zhí)行了特權(quán)指令，處理機(jī)即會(huì)報(bào)錯(cuò)。

3.5.1執(zhí)行模式3.5.2模式切換3.5.3進(jìn)程切換與模式切換比較3.5

進(jìn)程切換與模式切換3.5.2模式切換1、CPU模式切換定義當(dāng)中斷發(fā)生時(shí)，暫時(shí)中斷正在執(zhí)行的用戶進(jìn)程，把進(jìn)程從用戶狀態(tài)切換到內(nèi)核狀態(tài)，去執(zhí)行操作系統(tǒng)例行程序以獲得服務(wù)，這就是一次模式切換，內(nèi)核在被中斷了的進(jìn)程的上下文中對(duì)這個(gè)中斷事件作處理，即使該中斷可能不是此進(jìn)程引起的。被中斷進(jìn)程可以是正在用戶態(tài)下執(zhí)行的，也可以是正在核心態(tài)下執(zhí)行的，內(nèi)核都要保留足夠信息以便在后來能恢復(fù)被中斷了的進(jìn)程執(zhí)行。3.5.2模式切換2、CPU模式切換過程保存被中斷進(jìn)程的處理器現(xiàn)場(chǎng)信息。根據(jù)中斷號(hào)置程序計(jì)數(shù)器。把用戶狀態(tài)切換到內(nèi)核狀態(tài)，以便執(zhí)行中斷處理程序。3.5.1執(zhí)行模式3.5.2模式切換3.5.3進(jìn)程切換與模式切換比較3.5

進(jìn)程切換與模式切換3.5.3進(jìn)程切換與模式切換比較1、CPU模式切換與進(jìn)程上下文切換比較模式切換不同于進(jìn)程切換，它并不引起進(jìn)程狀態(tài)變化，也不一定引起進(jìn)程的切換在完成了中斷調(diào)用之后，完全可以再通過一次逆向的模式切換來繼續(xù)執(zhí)行用戶進(jìn)程3.5.3進(jìn)程切換與模式切換比較2、UNIX進(jìn)程上下文切換和模式切換兩類進(jìn)程：系統(tǒng)進(jìn)程和用戶進(jìn)程，系統(tǒng)進(jìn)程在核心態(tài)下執(zhí)行操作系統(tǒng)代碼，用戶進(jìn)程在用戶態(tài)下執(zhí)行用戶程序。用戶進(jìn)程因中斷或系統(tǒng)調(diào)用進(jìn)入內(nèi)核態(tài)，系統(tǒng)進(jìn)程開始執(zhí)行，兩個(gè)進(jìn)程使用同一個(gè)PCB，實(shí)質(zhì)上是一個(gè)進(jìn)程。但所執(zhí)行的程序不同，映射到不同物理地址空間、使用不同堆棧。3.5.3進(jìn)程切換與模式切換比較2、UNIX進(jìn)程上下文切換和模式切換核心態(tài)運(yùn)行系統(tǒng)調(diào)用或中斷(隱含模式切換)模式切換用戶態(tài)運(yùn)行等待狀態(tài)就緒狀態(tài)發(fā)生事件喚醒調(diào)度進(jìn)程中斷、中斷返回允許的上下文切換切換第三章進(jìn)程管理與調(diào)度

3.1中央處理器3.2中斷3.3進(jìn)程及其實(shí)現(xiàn)3.4進(jìn)程的控制3.5進(jìn)程切換與模式切換3.6處理器調(diào)度3.7作業(yè)的管理與調(diào)度3.8低級(jí)調(diào)度3.9線程及其基本概念3.10Linux進(jìn)程管理3.6.1調(diào)度策略3.6.2調(diào)度模式

3.6

處理器調(diào)度3.6.1調(diào)度策略1、要解決的問題WHAT：按什么原則分配CPU

—進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU

—進(jìn)程調(diào)度的時(shí)機(jī)HOW：如何分配CPU

—CPU調(diào)度過程（進(jìn)程的上下文切換）3.6.1調(diào)度策略2、調(diào)度目標(biāo)①合理性：是在多道作業(yè)（進(jìn)程）并發(fā)時(shí)，各道作業(yè)（進(jìn)程）根據(jù)調(diào)度策略來分配處理機(jī)的使用，調(diào)度策略既要保證系統(tǒng)實(shí)現(xiàn)特殊功能要求（如實(shí)時(shí)性），同時(shí)也要使各道作業(yè)合理地分配到處理機(jī)份額。②有效性：是指通過系統(tǒng)的調(diào)度，使處理機(jī)和I/O設(shè)備得到合理有效的分配，從而使系統(tǒng)資源得到充分的利用。3.6.1調(diào)度策略3、考慮的因素①系統(tǒng)設(shè)計(jì)目標(biāo)系統(tǒng)設(shè)計(jì)目標(biāo)是決定調(diào)度策略的主要依據(jù)。批處理系統(tǒng)以充分發(fā)揮和提高計(jì)算機(jī)的效率為目的；實(shí)時(shí)系統(tǒng)更重要的問題是保證不要丟失實(shí)時(shí)信息并使之得到及時(shí)的處理；而分時(shí)系統(tǒng)則應(yīng)該優(yōu)先保證用戶的請(qǐng)求能夠及時(shí)給予響應(yīng)。②資源利用率資源利用率是系統(tǒng)性能的一個(gè)重要指標(biāo)，因此，在選擇調(diào)度策略時(shí)，應(yīng)該考慮在實(shí)現(xiàn)設(shè)計(jì)目標(biāo)的前提下，盡可能地發(fā)揮各種資源的效能。③均衡系統(tǒng)與用戶的要求系統(tǒng)對(duì)作業(yè)或進(jìn)程的調(diào)度，需要在系統(tǒng)與用戶的沖突中進(jìn)行適當(dāng)?shù)膮f(xié)調(diào)。一方面，不能因?yàn)橛脩舻囊蠖耆活櫦跋到y(tǒng)的性能，另一方面，也不應(yīng)該使一個(gè)作業(yè)的運(yùn)行被無限制地推遲。3.6.2調(diào)度模式1、處理器調(diào)度的層次中級(jí)調(diào)度新建態(tài)掛起就緒態(tài)掛起等待態(tài)高級(jí)調(diào)度低級(jí)調(diào)度運(yùn)行態(tài)就緒態(tài)等待態(tài)終止態(tài)3.6.2調(diào)度模式1、高級(jí)調(diào)度也稱為作業(yè)調(diào)度或宏觀調(diào)度分時(shí)操作系統(tǒng)中，高級(jí)調(diào)度任務(wù)：（1）是否接受一個(gè)終端用戶的連接；（2）一個(gè)程序能否被計(jì)算機(jī)系統(tǒng)接納并構(gòu)成進(jìn)程；（3）一個(gè)新建態(tài)進(jìn)程是否能夠加入就緒進(jìn)程隊(duì)列。3.6.2調(diào)度模式1、高級(jí)調(diào)度也稱為作業(yè)調(diào)度或宏觀調(diào)度分時(shí)操作系統(tǒng)中，高級(jí)調(diào)度任務(wù)：（1）是否接受一個(gè)終端用戶的連接；（2）一個(gè)程序能否被計(jì)算機(jī)系統(tǒng)接納并構(gòu)成進(jìn)程；（3）一個(gè)新建態(tài)進(jìn)程是否能夠加入就緒進(jìn)程隊(duì)列。處理器調(diào)度與進(jìn)程狀態(tài)轉(zhuǎn)換高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度運(yùn)行態(tài)就緒態(tài)終止態(tài)新建態(tài)掛起就緒態(tài)中級(jí)調(diào)度掛起等待態(tài)等待態(tài)高級(jí)調(diào)度高級(jí)調(diào)度中級(jí)調(diào)度高級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度處理器調(diào)度與進(jìn)程狀態(tài)轉(zhuǎn)換高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度運(yùn)行態(tài)就緒態(tài)終止態(tài)新建態(tài)掛起就緒態(tài)中級(jí)調(diào)度掛起等待態(tài)等待態(tài)高級(jí)調(diào)度高級(jí)調(diào)度中級(jí)調(diào)度高級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度3.6.2調(diào)度模式2、中級(jí)調(diào)度又叫平衡負(fù)載調(diào)度，中程調(diào)度。決定主存儲(chǔ)器中所能容納的進(jìn)程數(shù)，這些進(jìn)程將允許參與競(jìng)爭(zhēng)處理器資源。中級(jí)調(diào)度根據(jù)存儲(chǔ)資源量和進(jìn)程的當(dāng)前狀態(tài)來決定輔存和主存中進(jìn)程的對(duì)換。使用的方法是通過把一些進(jìn)程換出主存，使之進(jìn)入掛起狀態(tài)，起到平滑和調(diào)整系統(tǒng)負(fù)荷作用。處理器調(diào)度與進(jìn)程狀態(tài)轉(zhuǎn)換高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度運(yùn)行態(tài)就緒態(tài)終止態(tài)新建態(tài)掛起就緒態(tài)中級(jí)調(diào)度掛起等待態(tài)等待態(tài)高級(jí)調(diào)度高級(jí)調(diào)度中級(jí)調(diào)度高級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度處理器調(diào)度與進(jìn)程狀態(tài)轉(zhuǎn)換高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度運(yùn)行態(tài)就緒態(tài)終止態(tài)新建態(tài)掛起就緒態(tài)中級(jí)調(diào)度掛起等待態(tài)等待態(tài)高級(jí)調(diào)度高級(jí)調(diào)度中級(jí)調(diào)度高級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度3.6.2調(diào)度模式3、低級(jí)調(diào)度又叫進(jìn)程調(diào)度、短程調(diào)度。主要功能是按照某種原則決定就緒隊(duì)列中的哪個(gè)進(jìn)程或內(nèi)核級(jí)線程能獲得處理器,并將處理器出讓給它進(jìn)行工作。短程調(diào)度程序是操作系統(tǒng)最為核心的部分，短程調(diào)度策略的優(yōu)劣直接影響到整個(gè)系統(tǒng)的性能。低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)的。由于低級(jí)調(diào)度算法的頻繁使用，要求在實(shí)現(xiàn)時(shí)做到高效處理器調(diào)度與進(jìn)程狀態(tài)轉(zhuǎn)換高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度運(yùn)行態(tài)就緒態(tài)終止態(tài)新建態(tài)掛起就緒態(tài)中級(jí)調(diào)度掛起等待態(tài)等待態(tài)高級(jí)調(diào)度高級(jí)調(diào)度中級(jí)調(diào)度高級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度處理器調(diào)度與進(jìn)程狀態(tài)轉(zhuǎn)換高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度運(yùn)行態(tài)就緒態(tài)終止態(tài)新建態(tài)掛起就緒態(tài)中級(jí)調(diào)度掛起等待態(tài)等待態(tài)高級(jí)調(diào)度高級(jí)調(diào)度中級(jí)調(diào)度高級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度4、處理器的調(diào)度模型

中級(jí)調(diào)度處理器低級(jí)調(diào)度高級(jí)調(diào)度完成超時(shí)掛起就緒隊(duì)列掛起等待隊(duì)列等待隊(duì)列就緒隊(duì)列等待事件交互式用戶事件出現(xiàn)后備作業(yè)隊(duì)列中級(jí)調(diào)度3.6.2調(diào)度模式第三章進(jìn)程管理與調(diào)度

3.1中央處理器3.2中斷3.3進(jìn)程及其實(shí)現(xiàn)3.4進(jìn)程的控制3.5進(jìn)程切換與模式切換3.6處理器調(diào)度3.7作業(yè)的管理與調(diào)度3.8低級(jí)調(diào)度3.9線程及其基本概念3.10Linux進(jìn)程管理3.7.1作業(yè)及其調(diào)度3.7.2作業(yè)與進(jìn)程3.7.3調(diào)度原則3.7.4作業(yè)調(diào)度算法3.7.5單道程序環(huán)境下的作業(yè)調(diào)度算法3.7.6多道程序環(huán)境下的作業(yè)調(diào)度算法

3.7

作業(yè)的管理與調(diào)度3.7.1作業(yè)及其調(diào)度1、作業(yè)（1）作業(yè)用戶在一次計(jì)算過程中，或者一次事務(wù)處理過程中，要求計(jì)算機(jī)系統(tǒng)所做工作的總稱（2）作業(yè)流

若干個(gè)作業(yè)進(jìn)入系統(tǒng)并存放于主存儲(chǔ)中形成作業(yè)流（3）作業(yè)步一個(gè)作業(yè)可劃分成若干部分，每部分稱一個(gè)作業(yè)步3.7.1作業(yè)及其調(diào)度2、作業(yè)的狀態(tài)及轉(zhuǎn)換數(shù)據(jù)進(jìn)入狀態(tài)退出狀態(tài)后備狀態(tài)運(yùn)行狀態(tài)作業(yè)控制進(jìn)程…輸入設(shè)備數(shù)據(jù)源程序輸出設(shè)備作業(yè)說明書輸入井運(yùn)行等待就緒輸出井輸入程序輸出程序作業(yè)調(diào)度進(jìn)程調(diào)度一個(gè)作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束經(jīng)歷四個(gè)不同的狀態(tài)：“進(jìn)入”“后備”“運(yùn)行”“完成”

3.7.1作業(yè)及其調(diào)度3、作業(yè)的調(diào)度主要功能：審查系統(tǒng)能否滿足用戶作業(yè)的資源要求只要通過調(diào)用相應(yīng)的資源管理程序的有關(guān)部分審核其表中是否能滿足作業(yè)說明書中的要求即可按照一定的算法從輸入井中的后備作業(yè)中選取作業(yè)

調(diào)度的關(guān)鍵在選擇恰當(dāng)?shù)乃惴?.7.1作業(yè)及其調(diào)度3.7.2作業(yè)與進(jìn)程3.7.3調(diào)度原則3.7.4作業(yè)調(diào)度算法3.7.5單道程序環(huán)境下的作業(yè)調(diào)度算法3.7.6多道程序環(huán)境下的作業(yè)調(diào)度算法

3.7

作業(yè)的管理與調(diào)度3.7.2作業(yè)與進(jìn)程①作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體，而進(jìn)程則是完成用戶任務(wù)的執(zhí)行實(shí)體，是向系統(tǒng)申請(qǐng)分配資源的基本單位。②一個(gè)作業(yè)可由多個(gè)進(jìn)程組成。且必須至少由一個(gè)進(jìn)程組成，但反過來不成立。③作業(yè)的概念主要用在批處理系統(tǒng)中，像Linux這樣的分時(shí)系統(tǒng)中，則沒有作業(yè)概念，而進(jìn)程的概念則用在幾乎所有的多道程序系統(tǒng)中。3.7.1作業(yè)及其調(diào)度3.7.2作業(yè)與進(jìn)程3.7.3調(diào)度原則3.7.4作業(yè)調(diào)度算法3.7.5單道程序環(huán)境下的作業(yè)調(diào)度算法3.7.6多道程序環(huán)境下的作業(yè)調(diào)度算法

3.7

作業(yè)的管理與調(diào)度3.7.3調(diào)度原則1、理想目標(biāo)單位時(shí)間內(nèi)運(yùn)行盡可能多的作業(yè)使處理器盡可能保持“忙碌”響應(yīng)時(shí)間和周轉(zhuǎn)時(shí)間能夠盡可能短使各種I/O設(shè)備得以充分利用對(duì)所有的作業(yè)都是公平合理的調(diào)度實(shí)質(zhì)上是一個(gè)策略問題，設(shè)定的目標(biāo)往往相互沖突3.7.3調(diào)度原則2、設(shè)計(jì)原則要設(shè)計(jì)一個(gè)理想的調(diào)度算法是一件十分困難的事在實(shí)際系統(tǒng)中，調(diào)度算法往往折衷考慮調(diào)度算法應(yīng)與系統(tǒng)設(shè)計(jì)目標(biāo)保持一致注意系統(tǒng)資源均衡使用保證提交的作業(yè)在截止時(shí)間內(nèi)完成設(shè)法縮短作業(yè)平均周轉(zhuǎn)時(shí)間大多數(shù)操作系統(tǒng)都采用比較簡(jiǎn)單的調(diào)度算法3.7.3調(diào)度原則3、調(diào)度算法性能的衡量作業(yè)平均周轉(zhuǎn)時(shí)間假定某一作業(yè)進(jìn)入“輸入井”的時(shí)間為Si，它被選中執(zhí)行，得到計(jì)算結(jié)果的時(shí)間為Ei

它的周轉(zhuǎn)時(shí)間為Ti＝Ei–Si

則作業(yè)平均周轉(zhuǎn)時(shí)間為：

T＝（）×

n為被測(cè)定作業(yè)流中的作業(yè)數(shù)3.7.3調(diào)度原則3、調(diào)度算法性能的衡量平均帶權(quán)周轉(zhuǎn)時(shí)間

W＝（）×

ri

為某作業(yè)i的實(shí)際執(zhí)行時(shí)間T：衡量不同調(diào)度算法對(duì)同一個(gè)作業(yè)流的性能

W：同一調(diào)度算法對(duì)不同作業(yè)流的性能衡量

3.7.1作業(yè)及其調(diào)度3.7.2作業(yè)與進(jìn)程3.7.3調(diào)度原則3.7.4作業(yè)調(diào)度算法3.7.5單道程序環(huán)境下的作業(yè)調(diào)度算法3.7.6多道程序環(huán)境下的作業(yè)調(diào)度算法

3.7

作業(yè)的管理與調(diào)度3.7.4作業(yè)調(diào)度算法1、系統(tǒng)進(jìn)行作業(yè)調(diào)度的決策因素作業(yè)到達(dá)時(shí)間預(yù)先為作業(yè)確定的優(yōu)先級(jí)系統(tǒng)可測(cè)定的其他因素：作業(yè)所需的CPU時(shí)間C存儲(chǔ)要求M其他的資源要求3.7.4作業(yè)調(diào)度算法2、作業(yè)的調(diào)度算法（1）常見的批處理作業(yè)調(diào)度算法先來先服務(wù)算法（FCFS：FirstComeFirstServe）最短作業(yè)優(yōu)先算法（SJF：ShortestJobFirst）最短剩余時(shí)間優(yōu)先算法（SRTF）

SRTF把SJF算法改為搶占式。

一個(gè)新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要的CPU時(shí)間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來還需的CPU時(shí)間短，SRTF強(qiáng)行趕走當(dāng)前正在執(zhí)行作業(yè)。稱最短剩余時(shí)間優(yōu)先算法3.7.4作業(yè)調(diào)度算法2、作業(yè)的調(diào)度算法（1）常見的批處理作業(yè)調(diào)度算法最高響應(yīng)比優(yōu)先算法（HRN：HighestResponseRatioNext）響應(yīng)比R=作業(yè)周轉(zhuǎn)時(shí)間/作業(yè)處理時(shí)間

=（作業(yè)處理時(shí)間+作業(yè)等待時(shí)間）/作業(yè)處理時(shí)間

=1+（作業(yè)等待時(shí)間/作業(yè)處理時(shí)間）3.7.4作業(yè)調(diào)度算法2、作業(yè)的調(diào)度算法（1）常見的批處理作業(yè)調(diào)度算法基于優(yōu)先數(shù)調(diào)度算法（HPF：HighestPriorityFirst）（a）由用戶規(guī)定優(yōu)先數(shù)（外部?jī)?yōu)先數(shù)）

用戶提交作業(yè)時(shí)，根據(jù)急迫程度規(guī)定適當(dāng)?shù)膬?yōu)先數(shù)作業(yè)調(diào)度程序根據(jù)JCB優(yōu)先數(shù)決定進(jìn)入內(nèi)存的次序（b）由系統(tǒng)計(jì)算優(yōu)先數(shù)（內(nèi)部?jī)?yōu)先數(shù)）例：可按如下公式計(jì)算作業(yè)的優(yōu)先數(shù)：優(yōu)先數(shù)=用戶規(guī)定優(yōu)先數(shù)–作業(yè)處理時(shí)間+作業(yè)等待時(shí)間–輸出量3.7.4作業(yè)調(diào)度算法2、作業(yè)的調(diào)度算法（1）常見的批處理作業(yè)調(diào)度算法均衡調(diào)度算法(分類排隊(duì)算法)基本思想：根據(jù)系統(tǒng)運(yùn)行情況和作業(yè)屬性將作業(yè)分類輪流從不同的作業(yè)類中挑選作業(yè)目標(biāo)：力求均衡地利用各種系統(tǒng)資源，發(fā)揮資源使用效率力求使用戶滿意3.7.4作業(yè)調(diào)度算法2、作業(yè)的調(diào)度算法（1）常見的批處理作業(yè)調(diào)度算法均衡調(diào)度算法(分類排隊(duì)算法)例1：將待處理作業(yè)分成如下隊(duì)列：

隊(duì)列1：計(jì)算量大的作業(yè)

隊(duì)列2：I/O量大的作業(yè)

隊(duì)列3：計(jì)算量與I/O量均衡的作業(yè)調(diào)度時(shí)，在三個(gè)隊(duì)列中各取一些作業(yè) 在內(nèi)存中的作業(yè)有的使用處理器 有的使用外部設(shè)備使得系統(tǒng)的各種資源能得到充分利用3.7.4作業(yè)調(diào)度算法2、作業(yè)的調(diào)度算法（1）常見的批處理作業(yè)調(diào)度算法均衡調(diào)度算法(分類排隊(duì)算法)例2：將待處理作業(yè)分成如下三個(gè)隊(duì)列：

隊(duì)列1：長(zhǎng)作業(yè)

隊(duì)列2：中等長(zhǎng)度作業(yè)

隊(duì)列3：短作業(yè)調(diào)度時(shí) 取隊(duì)列1一作業(yè)，隊(duì)列2一作業(yè)，隊(duì)列3一作業(yè)長(zhǎng)作業(yè)用戶和短作業(yè)用戶均比較滿意3.7.1作業(yè)及其調(diào)度3.7.2作業(yè)與進(jìn)程3.7.3調(diào)度原則3.7.4作業(yè)調(diào)度算法3.7.5單道程序環(huán)境下的作業(yè)調(diào)度算法3.7.6多道程序環(huán)境下的作業(yè)調(diào)度算法

3.7

作業(yè)的管理與調(diào)度3.7.5單道程序環(huán)境下的作業(yè)調(diào)度算法假設(shè)在單道批處理環(huán)境下有四個(gè)作業(yè)，已知它們進(jìn)入系統(tǒng)的時(shí)間、估計(jì)運(yùn)行時(shí)間應(yīng)用先來先服務(wù)、最短作業(yè)優(yōu)先和最高響應(yīng)比優(yōu)先作業(yè)調(diào)度算法，分別計(jì)算出作業(yè)的平均周轉(zhuǎn)時(shí)間和帶權(quán)的平均周轉(zhuǎn)時(shí)間3.7.5單道程序環(huán)境下的作業(yè)調(diào)度算法先來先服務(wù)調(diào)度算法計(jì)算結(jié)果3.7.5單道程序環(huán)境下的作業(yè)調(diào)度算法最短作業(yè)優(yōu)先作業(yè)算法計(jì)算結(jié)果3.7.5單道程序環(huán)境下的作業(yè)調(diào)度算法最高響應(yīng)比優(yōu)先作業(yè)算法計(jì)算結(jié)果130502.615.13.775410102.53.7.1作業(yè)及其調(diào)度3.7.2作業(yè)與進(jìn)程3.7.3調(diào)度原則3.7.4作業(yè)調(diào)度算法3.7.5單道程序環(huán)境下的作業(yè)調(diào)度算法3.7.6多道程序環(huán)境下的作業(yè)調(diào)度算法

3.7

作業(yè)的管理與調(diào)度3.7.5多道程序環(huán)境下的作業(yè)調(diào)度算法在兩道環(huán)境下有四個(gè)作業(yè)已知它們進(jìn)入系統(tǒng)的時(shí)間、估計(jì)運(yùn)行時(shí)間系統(tǒng)采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法，作業(yè)被調(diào)度運(yùn)行后不再退出當(dāng)一新作業(yè)投入運(yùn)行后，可按照作業(yè)運(yùn)行時(shí)間長(zhǎng)短調(diào)整作業(yè)執(zhí)行的次序請(qǐng)給出這四個(gè)作業(yè)的執(zhí)行時(shí)間序列，并計(jì)算出平均周轉(zhuǎn)時(shí)間及帶權(quán)平均周轉(zhuǎn)時(shí)間3.7.5多道程序環(huán)境下的作業(yè)調(diào)度算法最短作業(yè)優(yōu)先作業(yè)算法計(jì)算結(jié)果3.7.5多道程序環(huán)境下的作業(yè)調(diào)度算法算法分析過程10：00，JOB1進(jìn)入，只有一作業(yè)，JOB1被調(diào)入執(zhí)行10：05，JOB2到達(dá)，最多允許兩作業(yè)同時(shí)進(jìn)入

所以JOB2也被調(diào)入內(nèi)存中有兩作業(yè)，哪一個(gè)執(zhí)行？題目規(guī)定當(dāng)一新作業(yè)運(yùn)行后，可按作業(yè)運(yùn)行時(shí)間長(zhǎng)短調(diào)整執(zhí)行次序即可搶占式調(diào)度策略 優(yōu)先數(shù)是根據(jù)作業(yè)估計(jì)運(yùn)行時(shí)間大小來決定的 由于JOB2運(yùn)行時(shí)間（20分）比JOB1少 （到10：05，JOB1還需25分鐘） 所以JOB2運(yùn)行，而JOB1等待3.7.5多道程序環(huán)境下的作業(yè)調(diào)度算法算法分析過程10：10，JOB3到達(dá)輸入井，內(nèi)存已有兩作業(yè)

JOB3不能馬上進(jìn)入內(nèi)存；10：20，JOB4也不能進(jìn)入內(nèi)存10：25，JOB2運(yùn)行結(jié)束，退出，內(nèi)存中剩下JOB1

輸入井中有兩作業(yè)JOB3和JOB4，如何調(diào)度？作業(yè)調(diào)度算法：最短作業(yè)優(yōu)先 因此JOB3進(jìn)入內(nèi)存，比較JOB1和JOB3運(yùn)行時(shí)間，JOB3運(yùn)行時(shí)間短，故JOB3運(yùn)行，同樣，JOB3退出后，下一個(gè)是JOB4 JOB4結(jié)束后，JOB1才能繼續(xù)運(yùn)行3.7.5多道程序環(huán)境下的作業(yè)調(diào)度算法算法分析過程四個(gè)作業(yè)的執(zhí)行時(shí)間序列為：JOB1：10：00—10：05，10：40—11：05JOB2：10：05—10：25JOB3：10：25—10：30JOB4：10：30—10：40第三章進(jìn)程管理與調(diào)度

3.1中央處理器3.2中斷3.3進(jìn)程及其實(shí)現(xiàn)3.4進(jìn)程的控制3.5進(jìn)程切換與模式切換3.6處理器調(diào)度3.7作業(yè)的管理與調(diào)度3.8低級(jí)調(diào)度3.9線程及其基本概念3.10Linux進(jìn)程管理3.8.1低級(jí)調(diào)度功能3.8.2低級(jí)調(diào)度的方式3.8.3低級(jí)調(diào)度算法

3.8低級(jí)調(diào)度1、低級(jí)調(diào)度低級(jí)調(diào)度負(fù)責(zé)動(dòng)態(tài)地把處理器分配給進(jìn)程或內(nèi)核級(jí)線程。操作系統(tǒng)中實(shí)現(xiàn)低級(jí)調(diào)度的程序稱為進(jìn)程(線程)調(diào)度程序，或分派程序(Dispatcher)。進(jìn)程調(diào)度算法多數(shù)適用于線程調(diào)度。3.8.1低級(jí)調(diào)度功能3.8.1低級(jí)調(diào)度功能2、低級(jí)調(diào)度的時(shí)機(jī)當(dāng)一個(gè)進(jìn)程從運(yùn)行態(tài)切換成等待態(tài)時(shí);當(dāng)一個(gè)進(jìn)程從運(yùn)行態(tài)切換成就緒態(tài)時(shí);當(dāng)一個(gè)進(jìn)程從等待態(tài)切換成就緒態(tài)時(shí);當(dāng)一個(gè)進(jìn)程中止時(shí)。3.8.1低級(jí)調(diào)度功能3、低級(jí)調(diào)度的功能（1）記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況作為進(jìn)程調(diào)度的準(zhǔn)備，進(jìn)程管理模塊必須將系統(tǒng)中各進(jìn)程的執(zhí)行情況和狀態(tài)特征記錄在各進(jìn)程的PCB表中。根據(jù)各進(jìn)程的狀態(tài)特征和資源需求等、進(jìn)程管理模塊還將各進(jìn)程的PCB表排成相應(yīng)的隊(duì)列并進(jìn)行動(dòng)態(tài)隊(duì)列轉(zhuǎn)接。進(jìn)程調(diào)度模塊通過PCB變化來掌握系統(tǒng)中存在的所有進(jìn)程的執(zhí)行情況和狀態(tài)特征，并在適當(dāng)?shù)臅r(shí)機(jī)從就緒隊(duì)列中選擇出一個(gè)進(jìn)程占據(jù)處理機(jī)。3.8.1低級(jí)調(diào)度功能3、低級(jí)調(diào)度的功能（2）選擇占有處理機(jī)的進(jìn)程進(jìn)程調(diào)度的主要功能是按照一定的策略選擇一個(gè)處于就緒狀態(tài)的進(jìn)程，使其獲得處理機(jī)執(zhí)行。根據(jù)不同的系統(tǒng)設(shè)計(jì)目的，有各種各樣的選擇策略，例如系統(tǒng)開銷較少的靜態(tài)優(yōu)先數(shù)調(diào)度法，適合于分時(shí)系統(tǒng)的時(shí)間片輪轉(zhuǎn)法等。3.8.1低級(jí)調(diào)度功能3、低級(jí)調(diào)度的功能（3）進(jìn)行進(jìn)程上下文切換系統(tǒng)要首先檢查是否允許做上下文切換（在有些情況下，上下文切換是不允許的，例如系統(tǒng)正在執(zhí)行某個(gè)不允許中斷的原語時(shí)）。然后，系統(tǒng)要保留有關(guān)被切換進(jìn)程的足夠信息，以便以后切換回該進(jìn)程時(shí)，順利恢復(fù)該進(jìn)程的執(zhí)行。在系統(tǒng)保留了CPU現(xiàn)場(chǎng)之后，調(diào)度程序選擇一個(gè)新的處于就緒狀態(tài)的進(jìn)程、并裝配該進(jìn)程的上下文，使CPU的控制權(quán)掌握在被選中進(jìn)程手中。3.8.1低級(jí)調(diào)度功能3、低級(jí)調(diào)度的功能小結(jié)記住進(jìn)程的狀態(tài)。決定某個(gè)進(jìn)程什么時(shí)候獲得處理器。決定某個(gè)進(jìn)程占用處理器多長(zhǎng)時(shí)間。把處理器分配給進(jìn)程。收回處理器。3.8.1低級(jí)調(diào)度功能3.8.2低級(jí)調(diào)度的方式3.8.3低級(jí)調(diào)度算法

3.8低級(jí)調(diào)度3.8.2低級(jí)調(diào)度的方式可剝奪式（可搶占式Preemptive）：當(dāng)有比正在運(yùn)行的進(jìn)程優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，系統(tǒng)可強(qiáng)行剝奪正在運(yùn)行進(jìn)程的CPU，提供給具有更高優(yōu)先級(jí)的進(jìn)程使用,或是當(dāng)運(yùn)行進(jìn)程/線程時(shí)間片用完后被剝奪。win98/2000/xp不可剝奪式（不可搶占式Non-preemptive）：某一進(jìn)程被調(diào)度運(yùn)行后，除非由于它自身的原因不能運(yùn)行，否則一直運(yùn)行下去，win3.1折衷方式3.8.1低級(jí)調(diào)度功能3.8.2低級(jí)調(diào)度的方式3.8.3低級(jí)調(diào)度算法

3.8低級(jí)調(diào)度3.8.3低級(jí)調(diào)度算法先來先服務(wù)算法時(shí)間片輪轉(zhuǎn)調(diào)度算法優(yōu)先權(quán)調(diào)度多級(jí)反饋隊(duì)列調(diào)度保證調(diào)度算法彩票調(diào)度算法3.8.3低級(jí)調(diào)度算法1、先來先服務(wù)算法按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序分配處理器。先進(jìn)入就緒隊(duì)列的進(jìn)程優(yōu)先被挑選，運(yùn)行進(jìn)程一旦占有處理器將一直運(yùn)行直到結(jié)束或阻塞。算法容易實(shí)現(xiàn)，效率不高，不利于I/O頻繁的進(jìn)程3.8.3低級(jí)調(diào)度算法2、時(shí)間片輪轉(zhuǎn)調(diào)度算法調(diào)度程序每次把CPU分配給就緒隊(duì)列首進(jìn)程使用一個(gè)時(shí)間片，例如100ms，就緒隊(duì)列中的每個(gè)進(jìn)程輪流地運(yùn)行一個(gè)時(shí)間片。當(dāng)這個(gè)時(shí)間片結(jié)束時(shí)，強(qiáng)迫一個(gè)進(jìn)程讓出處理器，讓它排列到就緒隊(duì)列的尾部，等候下一輪調(diào)度。輪轉(zhuǎn)策略可防止那些很少使用外圍設(shè)備的進(jìn)程過長(zhǎng)的占用處理器而使得要使用外圍設(shè)備的那些進(jìn)程沒有機(jī)會(huì)去啟動(dòng)外圍設(shè)備。3.8.3低級(jí)調(diào)度算法2、時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片取選輪轉(zhuǎn)法調(diào)度是一種剝奪式調(diào)度，系統(tǒng)耗費(fèi)在進(jìn)程切換上的開銷比較大，這個(gè)開銷與時(shí)間片的大小很有關(guān)系。3.8.3低級(jí)調(diào)度算法2、時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片取選時(shí)間片取值太小，多數(shù)進(jìn)程不能在一個(gè)時(shí)間片內(nèi)運(yùn)行完畢，切換就會(huì)頻繁，開銷顯著增大，從系統(tǒng)效率來看，時(shí)間片取大一點(diǎn)好。時(shí)間片取值較大，隨就緒隊(duì)列里進(jìn)程數(shù)目增加，輪轉(zhuǎn)一次的總時(shí)間增大，對(duì)進(jìn)程的響應(yīng)速度放慢了。為滿足響應(yīng)時(shí)間要求，要么限制就緒隊(duì)列中進(jìn)程數(shù)量，要么采用動(dòng)態(tài)時(shí)間片法，根據(jù)負(fù)載狀況，及時(shí)調(diào)整時(shí)間片的大小。時(shí)間片大小的確定要從進(jìn)程個(gè)數(shù)、切換開銷、系統(tǒng)效率和響應(yīng)時(shí)間等方面考慮。3.8.3低級(jí)調(diào)度算法3、優(yōu)先權(quán)調(diào)度靜態(tài)優(yōu)先數(shù)法使用外圍設(shè)備頻繁者優(yōu)先數(shù)大，這樣有利于提高效率；重要算題程序的進(jìn)程優(yōu)先數(shù)大，這樣有利于用戶；進(jìn)入計(jì)算機(jī)時(shí)間長(zhǎng)的進(jìn)程優(yōu)先數(shù)大，這樣有利于縮短作業(yè)完成的時(shí)間；交互式用戶的進(jìn)程優(yōu)先數(shù)大，這樣有利于終端用戶的響應(yīng)時(shí)間等等。3.8.3低級(jí)調(diào)度算法3、優(yōu)先權(quán)調(diào)度

動(dòng)態(tài)優(yōu)先數(shù)法根據(jù)進(jìn)程占有CPU時(shí)間多少來決定,當(dāng)進(jìn)程占有CPU時(shí)間愈長(zhǎng),那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級(jí)就越低，反之,進(jìn)程獲得調(diào)度的可能性越大;根據(jù)進(jìn)程等待CPU時(shí)間多少來決定,當(dāng)進(jìn)程在就緒隊(duì)列中等待時(shí)間愈長(zhǎng),那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級(jí)就越高，反之,進(jìn)程獲得調(diào)度的可能性越小。3.8.3低級(jí)調(diào)度算法4、多級(jí)反饋隊(duì)列調(diào)度又稱反饋循環(huán)隊(duì)列或多隊(duì)列策略。主要思想是將就緒進(jìn)程分為兩級(jí)或多級(jí)，系統(tǒng)相應(yīng)建立兩個(gè)或多個(gè)就緒進(jìn)程隊(duì)列，較高優(yōu)先級(jí)的隊(duì)列一般分配給較短的時(shí)間片。處理器調(diào)度先從高級(jí)就緒進(jìn)程隊(duì)列中選取可占有處理器的進(jìn)程，只有在選不到時(shí)，才從較低級(jí)的就緒進(jìn)程隊(duì)列中選取。5.3BSD中采用此調(diào)度算法3.8.3低級(jí)調(diào)度算法5、保證調(diào)度算法向用戶做出明確的性能保證，然后去實(shí)現(xiàn)它。容易實(shí)現(xiàn)的一種保證是：當(dāng)工作時(shí)己有n個(gè)用戶登錄在系統(tǒng)，則將獲得CPU處理能力的1/n。類似的，如果在一個(gè)有n個(gè)進(jìn)程運(yùn)行的用戶系統(tǒng)中，每個(gè)進(jìn)程將獲得CPU處理能力的1/n。保證調(diào)度算法必須跟蹤各個(gè)進(jìn)程自創(chuàng)建以來已經(jīng)使用了多少CPU時(shí)間。計(jì)算各個(gè)進(jìn)程應(yīng)獲得的CPU時(shí)間，即自創(chuàng)建以來的時(shí)間除以n。由于各個(gè)進(jìn)程實(shí)際獲得的CPU時(shí)間已知，所以很容易計(jì)算出實(shí)際獲得的CPU時(shí)間和應(yīng)獲得的CPU時(shí)間之比，于是調(diào)度將轉(zhuǎn)向比率最低的進(jìn)程。3.8.3低級(jí)調(diào)度算法6、彩票調(diào)度算法基本思想：為進(jìn)程發(fā)放針對(duì)各種資源（如CPU時(shí)間）的彩票。調(diào)度程序隨機(jī)選擇一張彩票，持有該彩票的進(jìn)程獲得系統(tǒng)資源。進(jìn)程都是平等的，有相同的運(yùn)行機(jī)會(huì)。如果某些進(jìn)程需要更多的機(jī)會(huì)，可被給予更多彩票，增加其中獎(jiǎng)機(jī)會(huì)。彩票調(diào)度法有趣特性：反映迅速，合作進(jìn)程可交換彩票。第三章進(jìn)程管理與調(diào)度

3.1中央處理器3.2中斷3.3進(jìn)程及其實(shí)現(xiàn)3.4進(jìn)程的控制3.5進(jìn)程切換與模式切換3.6處理器調(diào)度3.7作業(yè)的管理與調(diào)度3.8低級(jí)調(diào)度3.9線程及其基本概念3.10Linux進(jìn)程管理3.9.1線程及其基本概念3.9.2線程的結(jié)構(gòu)3.9.3進(jìn)程與線程3.9.4線程的實(shí)現(xiàn)3.9線程及其基本概念3.9.1線程及其基本概念1、定義引入線程（Thread）的基本目的是將進(jìn)程以更細(xì)的粒度加以切分，以低開銷進(jìn)一步提高系統(tǒng)的并發(fā)度。所謂線程，有的系統(tǒng)中也稱之為輕量級(jí)進(jìn)程，是進(jìn)程中的一個(gè)運(yùn)行實(shí)體，作為CPU的調(diào)度單位。在多線程系統(tǒng)中，資源分配的單位，或是資源的擁有者還是進(jìn)程。多線程程序設(shè)計(jì)是指使單個(gè)程序中包含并發(fā)執(zhí)行的多個(gè)線程。3.9.1線程及其基本概念2、內(nèi)容線程是進(jìn)程的一條執(zhí)行路徑，它包含獨(dú)立的堆棧和CPU寄存器狀態(tài)，每個(gè)線程共享其所附屬的進(jìn)程的所有的資源，包括打開的文件、頁(yè)表（因此也就共享整個(gè)用戶態(tài)地址空間）、信號(hào)標(biāo)識(shí)及動(dòng)態(tài)分配的內(nèi)存等等。線程是屬于進(jìn)程的，線程運(yùn)行在進(jìn)程空間內(nèi)，同一進(jìn)程所產(chǎn)生的線程共享同一物理內(nèi)存空間，當(dāng)進(jìn)程退出時(shí)該進(jìn)程所產(chǎn)生的線程都會(huì)被強(qiáng)制退出并清除。線程有生命周期，即它由創(chuàng)建而產(chǎn)生，由撤消而消亡。在線程的生命期中，它總是從一種狀態(tài)變遷到另一種狀態(tài)。以JAVA語言為例，線程可分為創(chuàng)建狀態(tài)（newThread）、可運(yùn)行狀態(tài)（Runnable）、不可運(yùn)行狀態(tài)（NotRunnable）和死亡狀態(tài)（Dead）。

3.9.1線程及其基本概念3.9.2線程的結(jié)構(gòu)3.9.3進(jìn)程與線程3.9.4線程的實(shí)現(xiàn)3.9線程及其基本概念3.9.2線程的結(jié)構(gòu)1、傳統(tǒng)進(jìn)程與多線程進(jìn)程模型在傳統(tǒng)進(jìn)程模型中，進(jìn)程控制塊（PCB）記錄進(jìn)程的所有信息，進(jìn)程擁有一個(gè)虛地址空間，一個(gè)用戶棧用于執(zhí)行用戶程序，一個(gè)核心棧用于執(zhí)行核心程序。在多線程進(jìn)程模型中，

除了進(jìn)程控制塊和進(jìn)程

虛空間外，每個(gè)線程擁

有一個(gè)線程控制塊TCB，

每個(gè)線程都有一個(gè)用戶

棧和核心棧。3.9.2線程的結(jié)構(gòu)2、線程控制塊①線程標(biāo)識(shí)信息。②線程運(yùn)行狀態(tài)（如運(yùn)行、就緒等）和調(diào)度優(yōu)先級(jí)等調(diào)度信息。③分別在用戶態(tài)和核心態(tài)下使用的兩個(gè)棧。用于保存現(xiàn)場(chǎng)信息、子程序局部變量等。④一個(gè)線程關(guān)聯(lián)的私有存儲(chǔ)區(qū)。⑤與進(jìn)程描述信息的連接信息。進(jìn)程內(nèi)的每個(gè)線程都共享進(jìn)程描述信息，如地址空間、使用資源等。3.9.1線程及其基本概念3.9.2線程的結(jié)構(gòu)3.9.3進(jìn)程與線程3.9.4線程的實(shí)現(xiàn)3.9線程及其基本概念3.9.3進(jìn)程與線程1、聯(lián)系與區(qū)別①進(jìn)程是資源分配的基本單位。，進(jìn)程也是搶占處理機(jī)的調(diào)度單位，它擁有一個(gè)完整的虛擬地址空間。而線程與資源分配無關(guān)，它屬于某一個(gè)進(jìn)程，并與進(jìn)程內(nèi)的其他線程一起共享進(jìn)程的資源。②當(dāng)進(jìn)程發(fā)生調(diào)度時(shí)，不同的進(jìn)程擁有不同的虛擬地址空間，而同一進(jìn)程內(nèi)的不同線程共享同一地址空間。③線程只由相關(guān)堆棧寄存器和線程控制塊組成。寄存器可被用來存儲(chǔ)線程內(nèi)的局部變量，但不能存儲(chǔ)其他線程的相關(guān)變量。④進(jìn)程切換時(shí)涉及到有關(guān)資源指針的保存以及地址空間的變化等問題；線程切換時(shí)，由于同不進(jìn)程內(nèi)的線程共享資源和地址空間，將不涉及資源信息的保存和地址變化問題，從而減少了操作系統(tǒng)的開銷時(shí)間。而且，進(jìn)程的調(diào)度與切換都是由操作系統(tǒng)內(nèi)核完成，而線程則既可由操作系統(tǒng)內(nèi)核完成，也可由用戶程序進(jìn)行。⑤進(jìn)程間的關(guān)系比較疏遠(yuǎn)。各個(gè)進(jìn)程是在自己獨(dú)有的地址空間內(nèi)執(zhí)行，不但寄存器和堆棧是獨(dú)有的，動(dòng)態(tài)數(shù)據(jù)堆、靜態(tài)數(shù)據(jù)區(qū)和程序代碼也相互獨(dú)立。而線程間的關(guān)系則要緊密得多，雖然各線程為保持自己的控制流而獨(dú)有寄存器和堆棧，但由于兩線程從屬于同一進(jìn)程，它們共享同一地址空間，所以動(dòng)態(tài)堆、靜態(tài)數(shù)據(jù)區(qū)及程序代碼為各線程共享。3.9.3進(jìn)程與線程2、線程優(yōu)勢(shì)①快速的關(guān)聯(lián)切換由于操作系統(tǒng)級(jí)的進(jìn)程獨(dú)占自己的虛地址空間，調(diào)度進(jìn)程時(shí)，系統(tǒng)必須交換地址空間，因而進(jìn)程切換時(shí)間長(zhǎng)。在同一程序內(nèi)的多個(gè)線程共享同一地址空間，因而能使線程快速切換。②系統(tǒng)額外開銷小對(duì)多個(gè)進(jìn)程的管理（創(chuàng)建、調(diào)度等）有比較大的系統(tǒng)開銷。在需要?jiǎng)討B(tài)創(chuàng)建新進(jìn)程的應(yīng)用中，這種開銷比較顯著。而對(duì)線程的管理雖然也會(huì)有系統(tǒng)開銷，但比進(jìn)程的小得多。③通信很容易實(shí)現(xiàn)為了實(shí)現(xiàn)協(xié)作，進(jìn)程或線程之間需要進(jìn)行數(shù)據(jù)交換。對(duì)于自動(dòng)共享同一地址空間的各線程來說，所有的全局?jǐn)?shù)據(jù)都可以訪問，因而不需要什么特殊手段就能自動(dòng)實(shí)現(xiàn)數(shù)據(jù)共享。而進(jìn)程之間的通信則要復(fù)雜得多。④線程個(gè)數(shù)比進(jìn)程個(gè)數(shù)多得多許多多任務(wù)操作系統(tǒng)限制用戶進(jìn)程總數(shù)，這對(duì)許多并發(fā)應(yīng)用來說遠(yuǎn)遠(yuǎn)不夠。在多線程系統(tǒng)中，雖存在線程總數(shù)限額，但個(gè)數(shù)多得多。3.9.1線程及其基本概念3.9.2線程的結(jié)構(gòu)3.9.3進(jìn)程與線程3.9.4線程的實(shí)現(xiàn)3.9線程及其基本概念3.9.4線程的實(shí)現(xiàn)1．用戶級(jí)線程用戶級(jí)線程是在沒有操作系統(tǒng)內(nèi)核的支持下，完全在用戶級(jí)提供一個(gè)庫(kù)程序來實(shí)現(xiàn)多線程。這些庫(kù)提供了創(chuàng)建、同步、調(diào)度與管理線程的所有功能，無需操作系統(tǒng)特別支持。由于對(duì)線程的所有操作都不涉及內(nèi)核，因此，用戶級(jí)線程的創(chuàng)建、結(jié)束、調(diào)度、現(xiàn)場(chǎng)保護(hù)與切換開銷非常少。與線程相關(guān)的控制結(jié)構(gòu)TCB保存在目態(tài)空間并由運(yùn)行系統(tǒng)維護(hù)，由于線程對(duì)操作系統(tǒng)不可見，系統(tǒng)調(diào)度仍以進(jìn)程為單位。3.9.4線程的實(shí)現(xiàn)2．核心級(jí)線程核心級(jí)線程是由操作系統(tǒng)支持實(shí)現(xiàn)的線程，操作系統(tǒng)維護(hù)核心級(jí)線程的各種管理表格，負(fù)責(zé)線程在處理機(jī)上的調(diào)度和切換，線程是CPU調(diào)度的基本單位。操作系統(tǒng)提供了一系列系統(tǒng)調(diào)用界面，讓用戶程序請(qǐng)求操作系統(tǒng)進(jìn)行線程創(chuàng)建、結(jié)束、同步等操作。3.9.4線程的實(shí)現(xiàn)3．混合級(jí)線程用戶利用多線庫(kù)提供的并行程序設(shè)計(jì)界面編寫用戶并行程序，可以根據(jù)用戶應(yīng)用并行度的需要產(chǎn)生足夠的用戶級(jí)線程。核心級(jí)線程的操作系統(tǒng)調(diào)用界面只提供給多線庫(kù)使用，用戶可以完全不知多線庫(kù)使用了幾個(gè)核心級(jí)線程，也可以通過多線庫(kù)的接口申請(qǐng)更多的核心級(jí)線程。所有核心級(jí)線程都由多線