操作系統(tǒng)原理課件VIP

操作系統(tǒng)的運(yùn)行環(huán)境硬體環(huán)境操作系統(tǒng)與其它系統(tǒng)軟體的關(guān)係操作系統(tǒng)與人的介面任何系統(tǒng)軟體都是硬體功能的延伸操作系統(tǒng)直接依賴於硬體條件OS的硬體環(huán)境以較分散的形式同各種管理相結(jié)合實(shí)現(xiàn)操作系統(tǒng)時(shí)必須理解的電腦基本結(jié)構(gòu)、操作系統(tǒng)管理的重要資源2.1硬體環(huán)境CPU、主存緩衝技術(shù)、中斷技術(shù)時(shí)鐘、時(shí)鐘佇列一、CPU專門設(shè)計(jì)了一系列基本機(jī)制：

-具有特權(quán)級別的處理器狀態(tài)，能在不同特權(quán)級運(yùn)行的各種特權(quán)指令。

-硬體機(jī)制使得OS可以和普通程式隔離實(shí)現(xiàn)保護(hù)和控制1、特權(quán)指令與非特權(quán)指令特權(quán)指令：僅能為操作系統(tǒng)使用的指令。使用多道程序設(shè)計(jì)技術(shù)的電腦指令系統(tǒng)必須要區(qū)分為特權(quán)指令和非特權(quán)指令特權(quán)指令一般引起處理器狀態(tài)的切換2、處理機(jī)的狀態(tài)根據(jù)運(yùn)行程式對資源和機(jī)器指令的使用權(quán)限將處理器設(shè)置為不同狀態(tài)多數(shù)系統(tǒng)將處理器工作狀態(tài)劃分為管態(tài)和目態(tài)管態(tài)：處理機(jī)執(zhí)行操作系統(tǒng)程式時(shí)的工作狀態(tài)目態(tài)：處理機(jī)執(zhí)行普通用戶程式時(shí)的工作狀態(tài)有些系統(tǒng)將處理器狀態(tài)劃分核心狀態(tài)，管理狀態(tài)和用戶程式狀態(tài)（目標(biāo)狀態(tài)）三種實(shí)例：x86系列處理器支持4個(gè)處理器特權(quá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)係：四個(gè)級別運(yùn)行不同類別的程式：R0-運(yùn)行操作系統(tǒng)核心代碼R1-運(yùn)行關(guān)鍵設(shè)備驅(qū)動(dòng)程式和I/O處理例程R2-運(yùn)行其他受保護(hù)共用代碼，如語言系統(tǒng)運(yùn)行環(huán)境R3-運(yùn)行各種用戶程式現(xiàn)有的基於x86處理器的操作系統(tǒng)，多數(shù)UNIX、Linux以及Windows系列大都只用了R0和R3兩個(gè)特權(quán)級別實(shí)例：x86系列處理器管態(tài)和目態(tài)的差別處理器處於管態(tài)時(shí)：全部指令（包括特權(quán)指令）可以執(zhí)行可使用所有資源並具有改變處理器狀態(tài)的能力處理器處於目態(tài)時(shí)：只有非特權(quán)指令能執(zhí)行高特權(quán)級別對應(yīng)的可運(yùn)行指令集合包含低特權(quán)級3、程式狀態(tài)字PSW在PSW中專門設(shè)置一位，來判斷運(yùn)行程式使用指令的許可權(quán)CPU的工作狀態(tài)碼——指明管態(tài)還是目態(tài)，用來說明當(dāng)前在CPU上執(zhí)行的是操作系統(tǒng)還是一般用戶，從而決定其是否可以使用特權(quán)指令或擁有其他的特殊權(quán)力條件碼——反映指令執(zhí)行後的結(jié)果特徵中斷遮罩碼——指出是否允許中斷4、寄存器寄存器：指令在CPU內(nèi)部作處理的過程中暫存數(shù)據(jù)、地址以及指令資訊的存儲設(shè)備

寄存器提供了一定的存儲能力速度比主記憶體快得多但是造價(jià)高，容量一般都很小兩類寄存器：用戶可見寄存器：由高級語言編譯器使用，以減少程式訪問主存次數(shù)控制和狀態(tài)寄存器：由操作系統(tǒng)使用,以控制其他程式的執(zhí)行

用戶可見寄存器機(jī)器語言直接引用包括數(shù)據(jù)寄存器、地址寄存器以及條件碼寄存器數(shù)據(jù)寄存器（dataregister）又稱通用寄存器主要用於各種算術(shù)邏輯指令和訪存指令地址寄存器（addressregister）用於存儲數(shù)據(jù)及指令的物理地址、線性地址或者有效地址，用於某種特定方式的尋址。條件碼寄存器保存CPU操作結(jié)果的各種標(biāo)記位。如算術(shù)運(yùn)算產(chǎn)生的溢出、符號等控制和狀態(tài)寄存器用於控制處理器的操作大部分對於用戶是不可見的一部分可以在特權(quán)模式下訪問常見的控制和狀態(tài)寄存器:程式計(jì)數(shù)器PC：記錄將要取出的指令的地址指令寄存器IR：包含最近取出的指令程式狀態(tài)字PSW：記錄處理器的運(yùn)行模式資訊二、主存支持OS運(yùn)行硬體環(huán)境的一個(gè)重要方面：作業(yè)必須把它的程式和數(shù)據(jù)存放在主記憶體（記憶體）中才能運(yùn)行多道程系統(tǒng)中，若干個(gè)程式和相關(guān)的數(shù)據(jù)要放入主記憶體操作系統(tǒng)要管理、保護(hù)程式和數(shù)據(jù)，使它們不至於受到破壞操作系統(tǒng)本身也要存放在主記憶體中並運(yùn)行記憶體的類型：讀寫型、只讀型存儲分塊存儲保護(hù)界地址寄存器存儲鍵1、記憶體的類型兩類記憶體：讀寫型的記憶體（RAM）只讀型的記憶體（ROM）變型:PROM和EPROMPROM:可編程只讀記憶體，使用特殊PROM寫入器寫入數(shù)據(jù)EPROM:用特殊的紫外線光照射此晶片，以“擦去”資訊，恢復(fù)原來狀態(tài)，然後使用特殊EPROM寫入器寫入數(shù)據(jù)2、存儲分塊存儲最小單位:“二進(jìn)位”最小編址單位:位元組主流個(gè)人電腦主存:128MB～512MB之間輔助記憶體:在20GB～70GB工作站、伺服器主存:512MB～4GB之間硬碟容量:數(shù)百GB為簡化分配和管理，將記憶體分成塊塊的大?。?12B、1K、4K、8K3、存儲保護(hù)措施對主存中的資訊加以嚴(yán)格的保護(hù)，使操作系統(tǒng)及其它程式不被破壞，是其正確運(yùn)行的基本條件之一多用戶,多任務(wù)操作系統(tǒng)：

OS給每個(gè)運(yùn)行進(jìn)程分配一個(gè)存儲區(qū)域問題：多個(gè)程式同時(shí)在同一臺機(jī)器上運(yùn)行怎樣才能互不侵犯？

存儲保護(hù)措施：界地址寄存器、存儲鍵界地址寄存器優(yōu)點(diǎn)機(jī)制比較簡單，易於實(shí)現(xiàn)實(shí)現(xiàn)方法：在CPU中設(shè)置一對上下限寄存器，分別存放用戶作業(yè)在主存中的上下限地址或?qū)⒁粋€(gè)寄存器作為基址寄存器，另一寄存器作為限長寄存器CPU訪問主存時(shí)，硬體自動(dòng)將被訪問的主存地址與界地址寄存器內(nèi)容比較，判斷是否越界未越界：按此地址訪問主存越界：產(chǎn)生存儲保護(hù)中斷界地址寄存器存儲保護(hù)技術(shù)存儲鍵每個(gè)存儲塊有一個(gè)由二進(jìn)位組成的存儲保護(hù)鍵當(dāng)作業(yè)進(jìn)入主存，OS分給它唯一的存儲鍵號將分配給該作業(yè)各存儲塊存儲鍵置成同樣鍵號當(dāng)OS挑選該作業(yè)運(yùn)行時(shí)，OS將它的存儲鍵號放入程式狀態(tài)字PSW存儲鍵域中當(dāng)CPU訪問主存，將該主存塊的存儲鍵與PSW中的存儲鍵域進(jìn)行比較如匹配，則允許訪問，否則，拒絕並報(bào)警

A塊B塊C塊001010100101000存儲鍵保護(hù)位鍵值為0~15，其中0號鍵為萬能鍵三、緩衝技術(shù)定義：外部設(shè)備在進(jìn)行數(shù)據(jù)傳輸期間專門用於暫存這些數(shù)據(jù)的主存區(qū)域。緩衝技術(shù)三種用途:處理器與主記憶體之間處理器和其他外部設(shè)備之間設(shè)備與設(shè)備之間的通信目的：緩和CPU和外設(shè)的速度差異，減輕通道和外設(shè)的壓力。四、中斷技術(shù)中斷機(jī)制是操作系統(tǒng)得以正常工作的最重要的手段它使得OS可以捕獲普通程式發(fā)出的系統(tǒng)功能調(diào)用及時(shí)處理設(shè)備的中斷請求防止用戶程式中破壞性的活動(dòng)等等五、時(shí)鐘時(shí)鐘為電腦完成的工作時(shí)鐘的概念：是硬體時(shí)鐘寄存器，按時(shí)鐘電路所產(chǎn)生的脈衝數(shù)對時(shí)鐘寄存器進(jìn)行加1或減1的工作絕對時(shí)鐘：記錄當(dāng)時(shí)時(shí)間

絕對時(shí)鐘準(zhǔn)確，停機(jī)時(shí)絕對時(shí)鐘值仍然自動(dòng)修改相對時(shí)鐘：通過時(shí)鐘寄存器實(shí)現(xiàn)設(shè)置時(shí)間間隔初值，每經(jīng)過一個(gè)單位時(shí)間，時(shí)鐘值減1，直到該值為負(fù)時(shí)，觸發(fā)時(shí)鐘中斷，並進(jìn)行相應(yīng)中斷處理硬體時(shí)鐘：用某個(gè)寄存器來模擬（定時(shí)加1或減1）軟體時(shí)鐘：用記憶體單元來模擬時(shí)鐘。分配給每個(gè)進(jìn)程一時(shí)間片。時(shí)間片到，發(fā)時(shí)鐘中斷，控制權(quán)交給操作系統(tǒng)。時(shí)鐘佇列：一種實(shí)現(xiàn)軟體時(shí)鐘的方法佇列頭指針A50B10C5D0X2.2、操作系統(tǒng)與其它系統(tǒng)軟體的關(guān)係

作業(yè)、作業(yè)步和進(jìn)程重定位的概念絕對裝入程式和相對裝入程式一、作業(yè)、作業(yè)步和進(jìn)程作業(yè)：用戶要求電腦所做的一個(gè)相對獨(dú)立的任務(wù)。

作業(yè)步：一個(gè)作業(yè)可劃分成若干部分，

每個(gè)部分稱為一個(gè)作業(yè)步。

典型的作業(yè)控制過程：“編譯”、“連接裝配”、“運(yùn)行”

進(jìn)程：OS將一個(gè)作業(yè)步劃分為若干作業(yè)步任務(wù)。

二、重定位的概念1、絕對地址、相對地址和邏輯地址空間絕對地址：主存單元的實(shí)際地址。相對地址：相對於某個(gè)基準(zhǔn)量編址時(shí)用的地址。邏輯地址空間：目標(biāo)程式所限定的地址集合。2、重定位用戶程式裝入記憶體時(shí)對有關(guān)指令地址的修改稱重定位技術(shù)。重定位分靜態(tài)重定位，動(dòng)態(tài)重定位。靜態(tài)地址重定位在程式裝入主存過程中由裝配程式進(jìn)行的重定位。動(dòng)態(tài)地址重定位在程式執(zhí)行過程中，每次訪存時(shí)將訪問的程式地址轉(zhuǎn)換成記憶體絕對地址。三、絕對裝入程式和相對裝入程式絕對裝入程式相對裝入程式如何識別需重定位的項(xiàng)裝入過程三、操作系統(tǒng)與人的介面操作系統(tǒng)提供兩個(gè)用戶介面：程式級：系統(tǒng)調(diào)用操作命令級：作業(yè)控制語言鍵盤命令圖形用戶介面（介面）1、作業(yè)控制語言：

一種語言，用來寫程式操作步驟的程式。在早期批處理操作系統(tǒng)中使用。用戶將自己的程式、數(shù)據(jù)和用作業(yè)控制語言編寫的上機(jī)操作的步驟的程式一起提交給計(jì)算中心（或機(jī)房），隔一段時(shí)間去機(jī)房取結(jié)果。2、鍵盤命令：

用戶通過鍵盤直接向電腦發(fā)佈各種命令。以互動(dòng)式操作系統(tǒng)，分時(shí)操作系統(tǒng)為代表。分時(shí)操作系統(tǒng)誕生後，用戶可以通過用戶終端直接使用電腦，並且可與電腦“對話”，這就是所謂的互動(dòng)式電腦。用戶可通過鍵盤直接向電腦發(fā)佈各種命令，電腦可接受、執(zhí)行用戶命令。DOS系統(tǒng)把鍵盤命令分為：檔管理（COPY、COMP、TYPE、DEL、REN）磁片管理（FORMAT、CHKDSK、DISKCOPY、

DISKCOMP）目錄管理（DIR、CD、MD、RD、TREE）設(shè)備工作模式（CLS、MODE）日期、時(shí)間、系統(tǒng)設(shè)置（DATE、TIME、VER、VOL）運(yùn)行用戶程式(MASM、LINK、DEBUG)3、圖形用戶介面（UNIX、WINDOWS）以窗口（windows）,圖示（icon）、菜單（menu）為典型特徵，由APPLE公司開創(chuàng)，以Microsoft公司的MS-Windows為里程碑，在UNIX系統(tǒng)下有X-window。4、系統(tǒng)調(diào)用：

直接在程式中使用OS命令，請求操作系統(tǒng)的服務(wù)。不同的操作系統(tǒng)，系統(tǒng)調(diào)用實(shí)現(xiàn)的具體方法有所不同，但其實(shí)質(zhì)的特點(diǎn)是相同的：1、每個(gè)系統(tǒng)調(diào)用對應(yīng)一個(gè)系統(tǒng)調(diào)用號；2、每個(gè)系統(tǒng)調(diào)用有一個(gè)對應(yīng)的執(zhí)行程式段；3、每個(gè)系統(tǒng)調(diào)用要求一定數(shù)量的輸入?yún)?shù)和返回值；4、整個(gè)系統(tǒng)有一個(gè)系統(tǒng)調(diào)用執(zhí)行程式入口地址表；第3章進(jìn)程管理進(jìn)程的概念進(jìn)程的狀態(tài)進(jìn)程的描述與管理進(jìn)程控制Windows2000/XP進(jìn)程管理一、進(jìn)程的概念進(jìn)程的引入進(jìn)程的定義進(jìn)程和程式的關(guān)係1、進(jìn)程的引入（一）程式的順序執(zhí)行（二）程式的併發(fā)執(zhí)行（一）程式的順序執(zhí)行順序環(huán)境：在系統(tǒng)中只有一個(gè)程式在運(yùn)行，該程式獨(dú)佔(zhàn)系統(tǒng)所有資源，其執(zhí)行不受外界影響。特徵：程式執(zhí)行的封閉性

獨(dú)佔(zhàn)資源，執(zhí)行過程中不受外界影響程式執(zhí)行結(jié)果的確定性

程式運(yùn)行結(jié)果與程式執(zhí)行速度無關(guān)，只要初始狀態(tài)相同，結(jié)果應(yīng)相同（二）程式的併發(fā)執(zhí)行併發(fā)環(huán)境：在一定時(shí)間內(nèi)有兩個(gè)或兩個(gè)以上的程式同處於開始運(yùn)行但尚未結(jié)束的狀態(tài)，並且次序不是事先確定的ABBAABAB

特徵：（1）程式結(jié)果的不可再現(xiàn)性

併發(fā)程式執(zhí)行的結(jié)果與其執(zhí)行的相對速度有關(guān)，是不確定的（2）在併發(fā)環(huán)境下程式的執(zhí)行是間斷性的

執(zhí)行——?！獔?zhí)行（3）資源共用

系統(tǒng)中資源被多個(gè)進(jìn)程使用

（4）獨(dú)立性和制約性

獨(dú)立的相對速度、起始時(shí)間

進(jìn)程之間可相互作用（相互制約）

可分為直接作用和間接作用

（5）程式和程式的執(zhí)行不再一一對應(yīng)

2、進(jìn)程（process）的定義程式在處理機(jī)上的執(zhí)行。進(jìn)程是一個(gè)可調(diào)度的實(shí)體。進(jìn)程是這樣的計(jì)算，它可以與別的計(jì)算並行運(yùn)行。進(jìn)程是邏輯上的一段程式，它在每一瞬間都含有一個(gè)程式控制點(diǎn)，指出正在執(zhí)行指令進(jìn)程是一個(gè)具有獨(dú)立功能的程式關(guān)於某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。父親食譜做蛋糕的原料CPU程式輸入數(shù)據(jù)進(jìn)程：父親閱讀食譜，取各種原料，製作蛋糕

的一系列動(dòng)作總和。急救手冊藥品進(jìn)程：父親閱讀急救手冊，取藥品，為兒子

療傷的一系列動(dòng)作總和。3、進(jìn)程和程式的關(guān)係進(jìn)程是一個(gè)動(dòng)態(tài)概念，程式是靜態(tài)概念。程式可作為資料長期保存，進(jìn)程有生命期，它能動(dòng)態(tài)產(chǎn)生，消亡。進(jìn)程的組成是程式，數(shù)據(jù)，PCB。同一程式運(yùn)行於不同數(shù)據(jù)集合，將屬於不同進(jìn)程。一個(gè)程式可對應(yīng)多個(gè)進(jìn)程，一個(gè)進(jìn)程可包含多個(gè)程式。二、進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)及變化進(jìn)程的掛起和解掛1、進(jìn)程狀態(tài)進(jìn)程的基本狀態(tài)有三個(gè)：就緒狀態(tài)運(yùn)行狀態(tài)等待狀態(tài)進(jìn)程在生命消亡前處於且僅處於三種基本狀態(tài)之一不同系統(tǒng)設(shè)置的進(jìn)程狀態(tài)數(shù)目不同運(yùn)行態(tài)（Running）：

進(jìn)程佔(zhà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）：

指進(jìn)程因等待某種事件的發(fā)生而暫時(shí)不能運(yùn)行的狀態(tài)（即使CPU空閒，該進(jìn)程也不可運(yùn)行）運(yùn)行就緒等待進(jìn)程的狀態(tài)及其轉(zhuǎn)換

就緒—運(yùn)行

運(yùn)行—就緒

運(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ìn)程處於就緒狀態(tài)進(jìn)程狀態(tài)轉(zhuǎn)換：根據(jù)進(jìn)程自身進(jìn)展情況及外界環(huán)境的變化，三種狀態(tài)可以相互轉(zhuǎn)換運(yùn)行-->等待當(dāng)一進(jìn)程必須等待時(shí)OS尚未完成服務(wù)對一資源的訪問尚不能進(jìn)行初始化I/O且必須等待結(jié)果等待某一進(jìn)程提供輸入(IPC)等待-->就緒當(dāng)所等待的事件發(fā)生時(shí)2、進(jìn)程的掛起與解掛進(jìn)程掛起的原因進(jìn)程的解掛具有掛起功能的進(jìn)程狀態(tài)轉(zhuǎn)換五狀態(tài)轉(zhuǎn)換等待-->掛起等待當(dāng)所有進(jìn)程都阻塞，OS會安排空間讓一就緒進(jìn)程進(jìn)入記憶體掛起等待-->掛起就緒當(dāng)?shù)却氖录l(fā)生時(shí)(狀態(tài)資訊已在OS中)掛起就緒-->活動(dòng)就緒當(dāng)記憶體中沒有就緒進(jìn)程時(shí)活動(dòng)就緒-->掛起就緒當(dāng)沒有被阻塞的進(jìn)程，而為了性能上的考慮，必須釋放一些記憶體時(shí)三、進(jìn)程的描述和管理1、進(jìn)程的描述進(jìn)程控制塊進(jìn)程的組成2、進(jìn)程的管理（1）進(jìn)程控制塊

（PCB：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是一一對應(yīng)的1、進(jìn)程的描述進(jìn)程映象(processimage)用戶程式用戶數(shù)據(jù)棧用於過程調(diào)用和參數(shù)傳遞進(jìn)程控制塊PCB(執(zhí)行上下文)控制進(jìn)程所需的數(shù)據(jù)(進(jìn)程屬性)，包括:進(jìn)程識別字資訊處理器狀態(tài)資訊進(jìn)程控制資訊PCB應(yīng)包含以下三類資訊：進(jìn)程標(biāo)識資訊處理器狀態(tài)資訊進(jìn)程控制資訊

進(jìn)程標(biāo)識資訊：本進(jìn)程的標(biāo)識ID索引至(直接或間接)主進(jìn)程表創(chuàng)建本進(jìn)程的某個(gè)進(jìn)程的標(biāo)識ID用戶標(biāo)識與某個(gè)作業(yè)對應(yīng)的用戶

處理器狀態(tài)資訊：用戶使用的寄存器控制和狀態(tài)寄存器堆疊指針進(jìn)程控制資訊調(diào)度和狀態(tài)資訊進(jìn)程狀態(tài)(如:運(yùn)行，就緒，阻塞...)進(jìn)程優(yōu)先順序該進(jìn)程在等待的事件(若被阻塞)數(shù)據(jù)結(jié)構(gòu)資訊進(jìn)程可能需要有指向其他PCB的指針,父-子進(jìn)程關(guān)係及其它結(jié)構(gòu)進(jìn)程控制資訊(續(xù))進(jìn)程間通信IPC可能需要標(biāo)誌和信號進(jìn)程特權(quán)如:訪問特定的記憶體地址...存儲管理指向賦予該進(jìn)程的段/頁表的指針?biāo)鶕碛械馁Y源和使用情況使用中的資源:打開的檔，I/O設(shè)備...(CPU,I/O...)的時(shí)間使用史

進(jìn)程控制塊的作用：記錄進(jìn)程的屬性資訊，以便操作系統(tǒng)對進(jìn)程進(jìn)行控制和管理標(biāo)誌進(jìn)程的存在（2）進(jìn)程的組成進(jìn)程的組成：程式，數(shù)據(jù)。PCB2、進(jìn)程管理

將PCB用適當(dāng)?shù)姆椒ńM織起來，把它們放在記憶體的固定區(qū)域，構(gòu)成PCB表

PCB的組織方法：把所有不同狀態(tài)的進(jìn)程的PCB組織在一張表格中。分別把有著相同狀態(tài)的進(jìn)程的PCB組織在同一張表格中。分別把具有相同狀態(tài)的所有進(jìn)程的PCB按優(yōu)先數(shù)排成一個(gè)或多個(gè)佇列。四、進(jìn)程的控制1、進(jìn)程控制概念2、進(jìn)程的控制原語3、進(jìn)程切換4、操作系統(tǒng)的執(zhí)行方式

1、進(jìn)程的控制概念職責(zé)：對系統(tǒng)中所有進(jìn)程實(shí)施有效管理，是處理機(jī)管理的一部分。任務(wù)：創(chuàng)建進(jìn)程，撤銷進(jìn)程，實(shí)現(xiàn)進(jìn)程間轉(zhuǎn)換。進(jìn)程控制由內(nèi)核完成。內(nèi)核有原語實(shí)現(xiàn)。原語：由若干條機(jī)器指令構(gòu)成，用以完成特定功能的一段程式。原語操作具有不可分割性。2、進(jìn)程的控制原語創(chuàng)建進(jìn)程原語掛起進(jìn)程原語解除掛起原語撤銷進(jìn)程原語改變進(jìn)程優(yōu)先數(shù)原語創(chuàng)建進(jìn)程原語創(chuàng)建一個(gè)PCB賦予一個(gè)統(tǒng)一進(jìn)程識別字為進(jìn)程分配空間初始化進(jìn)程控制塊許多默認(rèn)值(如:狀態(tài)為New，無I/O設(shè)備或檔...)設(shè)置相應(yīng)的鏈接如:把新進(jìn)程加到就緒佇列的鏈表中ProcedureCreate(n,s0,k0,m0,R0,acc)begini:=GetNewInternalName(n)；

id(i):=n；

Priority(i):=k0;Cpustate(i):=s0;MainStore(i):=m0;Resource(i):=R0;State(i):=‘Readys’;Parent(i):=*;SetAccountingData;insert(RL,i);end.掛起進(jìn)程原語：掛起命令的執(zhí)行：

把本命令的進(jìn)程掛起

把具有指定識別字進(jìn)程掛起

把某進(jìn)程及其全部或部分子進(jìn)程掛起進(jìn)程的掛起完成下列狀態(tài)轉(zhuǎn)換：

就緒掛起就緒運(yùn)行掛起就緒等待掛起等待ProcedureSuspend(n,a)begini:=GetInternalName(n);s:=State(i);Ifs=‘Running’ThenStop(i);a:=CopyPCB(i);Status(i):=Ifa=‘Blockeda’Then‘Blokeds’else‘Readys’;Ifs=‘Running’ThenSCHEDULERend.解掛原語解掛原語實(shí)現(xiàn)狀態(tài)的轉(zhuǎn)化：掛起就緒

就緒掛起等待

等待一個(gè)進(jìn)程可掛起自己，但不能解掛自己。一個(gè)進(jìn)程可掛起解掛自己子孫，但不能解掛別的族系進(jìn)程。ProcedureResume(n);begini:=GetInternalName(n);Status(i):=IfStatus(i)=‘Readys’

then‘Readya’

else‘Blockeda’;

IfStatus(i)=‘Readya’thenSCHEDULERend撤銷進(jìn)程原語：進(jìn)程撤銷的原因：進(jìn)程已完成所要求的功能而正常終止由於某種錯(cuò)誤導(dǎo)致非正常終止祖先進(jìn)程要求撤銷某個(gè)子進(jìn)程進(jìn)程撤銷的策略（兩種）撤銷原語一般由其父進(jìn)程或祖先發(fā)出，不會自己撤銷自己ProcedureDestroy(n);beginSched:=false;i:=GetInternalName(n);kill(i);ifSched=truethenSCHEDULER;end(Destroy)Procedurekill(I);beginifStatus(i)=‘Running’thenbeginStop(i);Sched:=trueendRemve(Queue(i),i);forallSProgeny(i)doKill(s);forallrResources(i)doRELEASE(r);RELEASE(PCB(i));end(Kill)改變優(yōu)先數(shù)原語優(yōu)先數(shù)與下列因素有關(guān)：與作業(yè)靜態(tài)優(yōu)先數(shù)有關(guān)。與進(jìn)程類型有關(guān)：系統(tǒng)進(jìn)程>I/O進(jìn)程>CPU型進(jìn)程與進(jìn)程所用資源有關(guān)：占資源優(yōu)先數(shù)與進(jìn)程等待時(shí)間有關(guān)：等待時(shí)間優(yōu)先數(shù)UNIX系統(tǒng)的優(yōu)先數(shù)Pri=min{127,100+Pcpu/16+Pnice}Pcpu為每個(gè)進(jìn)程使用及等待CPU時(shí)間相關(guān)的量。

運(yùn)行進(jìn)程：每隔20ms加1，直至255為止非運(yùn)行進(jìn)程：每秒減10，直至小於10為止Pnice由用戶通過系統(tǒng)調(diào)用設(shè)置的初值。ProcedureChangePriority(n);begini:=GetInternalName(n);a:=CalculatePriority(i);Pri(i):=a;IfStatus(i)=‘Readya’thenbeginInsert(RL,i,Pri);forallPRunningProcessQueuedo

IfPri(p)<Pri(I)thenSCHEDULERendend進(jìn)程阻塞原語阻塞原語完成運(yùn)行狀態(tài)等待狀態(tài)流程：入口保存當(dāng)前CPU現(xiàn)場置該進(jìn)程為阻塞狀態(tài)入等待佇列轉(zhuǎn)進(jìn)程調(diào)度阻塞進(jìn)程原語

輸入?yún)?shù)：無

返回參數(shù)：轉(zhuǎn)進(jìn)程調(diào)度

功能：把現(xiàn)行進(jìn)程的PCB置為“阻塞”狀態(tài)後

加入阻塞佇列。進(jìn)程喚醒原語喚醒原語完成：

等待狀態(tài)就緒狀態(tài)掛起等待掛起就緒流程：入口判進(jìn)程狀態(tài)是掛起阻塞？

N

Y

置狀態(tài)為掛起就緒置狀態(tài)為就緒入掛起就緒佇列入就緒佇列返回進(jìn)程調(diào)度

喚醒進(jìn)程原語

輸入?yún)?shù)：進(jìn)程號

返回參數(shù)：成功或失敗標(biāo)記

功能：把指定進(jìn)程的PCB從阻塞佇列取出，改狀態(tài)為“就緒”後，列入就緒佇列。3、進(jìn)程切換進(jìn)程切換的概念：OS中斷現(xiàn)行進(jìn)程，指定另一個(gè)進(jìn)程為運(yùn)行狀態(tài)。中斷進(jìn)程執(zhí)行的可能事件：

時(shí)鐘中斷、I/O中斷、記憶體、訪管中斷3、操作系統(tǒng)的執(zhí)行方式非進(jìn)程的內(nèi)核方式用戶方式練習(xí)1．如果系統(tǒng)中有N個(gè)進(jìn)程，運(yùn)行的進(jìn)程最多幾個(gè)，最少幾個(gè)；就緒進(jìn)程最多幾個(gè)最少幾個(gè)；等待進(jìn)程最多幾個(gè)，最少幾個(gè)？2.有沒有這樣的狀態(tài)轉(zhuǎn)換，為什麼？ 等待—運(yùn)行；就緒—等待3.一個(gè)狀態(tài)轉(zhuǎn)換的發(fā)生，是否一定導(dǎo)致另一個(gè)轉(zhuǎn)換發(fā)生，列出所有的可能。4.請寫出阻塞原語和喚醒原語的程式描述。第4章線程線程的引入線程與進(jìn)程的對比線程的實(shí)現(xiàn)1、線程的引入進(jìn)程的兩個(gè)基本屬性：資源的擁有者：

給每個(gè)進(jìn)程分配一虛擬地址空間，保存進(jìn)程映像，控制一些資源（檔，I/O設(shè)備），有狀態(tài)、優(yōu)先順序、調(diào)度調(diào)度單位：

進(jìn)程是一個(gè)執(zhí)行軌跡

以上兩個(gè)屬性構(gòu)成進(jìn)程併發(fā)執(zhí)行的基礎(chǔ)線程的引入（續(xù)）系統(tǒng)必須完成的操作：創(chuàng)建進(jìn)程撤銷進(jìn)程進(jìn)程切換缺點(diǎn)：

時(shí)間空間開銷大，限制併發(fā)度的提高線程的引入（續(xù)）在操作系統(tǒng)中，進(jìn)程的引入提高了電腦資源的利用效率。但在進(jìn)一步提高進(jìn)程的併發(fā)性時(shí)，人們發(fā)現(xiàn)進(jìn)程切換開銷占的比重越來越大，同時(shí)進(jìn)程間通信的效率也受到限制線程的引入正是為了簡化進(jìn)程間的通信，以小的開銷來提高進(jìn)程內(nèi)的併發(fā)程度線程的引入（續(xù)）線程：有時(shí)稱羽量級進(jìn)程

進(jìn)程中的一個(gè)運(yùn)行實(shí)體是一個(gè)CPU調(diào)度單位資源的擁有者還是進(jìn)程或稱任務(wù)線程的引入（續(xù)）線程：有執(zhí)行狀態(tài)（狀態(tài)轉(zhuǎn)換）不運(yùn)行時(shí)保存上下文有一個(gè)執(zhí)行棧有一些局部變數(shù)的靜態(tài)存儲可存取所在進(jìn)程的記憶體和其他資源可以創(chuàng)建、撤銷另一個(gè)線程線程和進(jìn)程：單進(jìn)程、單線程單進(jìn)程、多線程多進(jìn)程、一個(gè)進(jìn)程一個(gè)線程多進(jìn)程、一個(gè)進(jìn)程多個(gè)線程PCB用戶棧單線程進(jìn)程模型用戶地址空間核心棧線程式控制制塊：包含了寄存器映像，線程優(yōu)先數(shù)和線程狀態(tài)資訊PCB多線程進(jìn)程模型用戶地址空間用戶棧核心棧線程控制塊用戶棧核心棧線程控制塊用戶棧核心棧線程控制塊引入線程的好處：創(chuàng)建一個(gè)新線程花費(fèi)時(shí)間少（結(jié)束亦如此）兩個(gè)線程的切換花費(fèi)時(shí)間少（如果機(jī)器設(shè)有“存儲[恢復(fù)]所有寄存器”指令，則整個(gè)切換過程用幾條指令即可完成）同一進(jìn)程內(nèi)的線程共用記憶體和文件，它們之間相互通信無須調(diào)用內(nèi)核適合多處理機(jī)系統(tǒng)例1：LAN中的一個(gè)檔伺服器，在一段時(shí)間內(nèi)需要處理幾個(gè)檔請求方法：為每一個(gè)請求創(chuàng)建一個(gè)線程在一個(gè)SMP機(jī)器上：多個(gè)線程可以同時(shí)在不同的處理器上運(yùn)行例2：一個(gè)線程顯示菜單，並讀入用戶輸入；另一個(gè)線程執(zhí)行用戶命令一個(gè)應(yīng)用：由幾個(gè)獨(dú)立部分組成，這幾個(gè)部分不需要順序執(zhí)行，則每個(gè)部分可以以線程方式實(shí)現(xiàn)當(dāng)一個(gè)線程因I/O阻塞時(shí)，可以切換到同一應(yīng)用的另一個(gè)線程2線程與進(jìn)程的比較調(diào)度併發(fā)性擁有資源系統(tǒng)開銷3線程的實(shí)現(xiàn)機(jī)制用戶級線程核心級線程兩者結(jié)合方法(1)用戶級線程（UserLevelThread）由應(yīng)用程式完成所有線程的管理

核心不知道線程的存在線程切換不需要核心態(tài)特權(quán)調(diào)度是應(yīng)用特定的對用戶級線程的核心活動(dòng)核心不知道線程的活動(dòng)，但仍然管理線程的進(jìn)程的活動(dòng)當(dāng)線程調(diào)用系統(tǒng)調(diào)用時(shí)，整個(gè)進(jìn)程阻塞但對線程庫來說，線程仍然是運(yùn)行狀態(tài)

即線程狀態(tài)是與進(jìn)程狀態(tài)獨(dú)立的用戶級線程的優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：線程切換不調(diào)用核心調(diào)度是應(yīng)用程式特定的：可以選擇最好的演算法ULT可運(yùn)行在任何操作系統(tǒng)上（只需要線程庫）缺點(diǎn)：大多數(shù)系統(tǒng)調(diào)用是阻塞的，因此核心阻塞進(jìn)程，故進(jìn)程中所有線程將被阻塞核心只將處理器分配給進(jìn)程，同一進(jìn)程中的兩個(gè)線程不能同時(shí)運(yùn)行於兩個(gè)處理器上(2)核心級線程（KLT）所有線程管理由核心完成沒有線程庫，但對核心線程工具提供API核心維護(hù)進(jìn)程和線程的上下文線程之間的切換需要核心支持以線程為基礎(chǔ)進(jìn)行調(diào)度例子：WindowsNT，OS/2核心級線程的優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：對多處理器，核心可以同時(shí)調(diào)度同一進(jìn)程的多個(gè)線程阻塞是線上程一級完成核心例程是多線程的缺點(diǎn)：在同一進(jìn)程內(nèi)的線程切換調(diào)用內(nèi)核，導(dǎo)致速度下降(3)兩者分析針對不同的操作系統(tǒng)開銷和性能（線程的調(diào)度和切換速度）系統(tǒng)調(diào)用線程執(zhí)行時(shí)間靈活性可擴(kuò)充性搶佔(zhàn)CPU共用進(jìn)程的資源(4)ULT和KLT結(jié)合方法線程創(chuàng)建在用戶空間完成大量線程調(diào)度和同步在用戶空間完成程式員可以調(diào)整KLT的數(shù)量可以取兩者中最好的線程庫由操作系統(tǒng)或某些語言提供，供所有用戶應(yīng)用程式共用，並支持用戶應(yīng)用程式創(chuàng)建、調(diào)度和管理自己的用戶級線程。（應(yīng)用程式中用戶級線程的微內(nèi)核）至少需提供以下功能的過程調(diào)用：建立線程、撤銷線程、阻塞線程、掛起線程、恢復(fù)線程、調(diào)度線程、線程間通訊原語、線程間同步原語WINDOWS2000/XP線程1、進(jìn)程特點(diǎn)：進(jìn)程是資源分配的基本單位，是作為對象進(jìn)行管理的一個(gè)可執(zhí)行的進(jìn)程可能包含一個(gè)或多個(gè)線程WIN32進(jìn)程控制系統(tǒng)調(diào)用有：CreateProcess、ExitProcess和TerminateProcess等2、進(jìn)程對象每個(gè)進(jìn)程由許多屬性定義，並且封裝了它可以執(zhí)行的許多動(dòng)作或服務(wù)進(jìn)程進(jìn)程ID安全描述符基本優(yōu)先順序默認(rèn)處理器仿射定額限制執(zhí)行時(shí)間I/O計(jì)數(shù)器異常/調(diào)試端口退出狀態(tài)創(chuàng)建進(jìn)程打開進(jìn)程查詢進(jìn)程資訊設(shè)置進(jìn)程資訊當(dāng)前進(jìn)程終止進(jìn)程對象類型對象體屬性服務(wù)3、線程對象線程線程ID動(dòng)態(tài)優(yōu)先順序基本優(yōu)先順序線程處理器仿射線程執(zhí)行警告狀態(tài)掛起計(jì)數(shù)器假冒標(biāo)誌終止端口線程退出狀態(tài)創(chuàng)建線程打開線程查詢線程資訊設(shè)置線程資訊當(dāng)前線程終止線程獲得上下文設(shè)置上下文掛起恢復(fù)警告線程測試線程警告寄存器終止端口對象類型對象體屬性服務(wù)4、線程狀態(tài)備用就緒運(yùn)行轉(zhuǎn)換等待終止可運(yùn)行選擇運(yùn)行資源可用解除阻塞/恢復(fù)資源可用阻塞/掛起終止解除阻塞資源不可用不可運(yùn)行切換剝奪第5章並行性：同步和互斥概述臨界段互斥信號量管程進(jìn)程間的通信5.1概述並行技術(shù)的發(fā)展併發(fā)環(huán)境中進(jìn)程間的關(guān)係進(jìn)程同步進(jìn)程互斥一、並行技術(shù)的發(fā)展多道程序設(shè)計(jì)多處理器系統(tǒng)分佈式處理系統(tǒng)二、併發(fā)環(huán)境中進(jìn)程間的關(guān)係間接制約關(guān)係：源於資源共用直接制約關(guān)係：源於進(jìn)程合作

三、進(jìn)程同步同步關(guān)係：指散佈在不同進(jìn)程中的若干程式片段，它們的運(yùn)行必須嚴(yán)格按照規(guī)定的某種先後次序來進(jìn)行，這種先後次序依賴於要完成的任務(wù)。同步機(jī)制：保證這種同步關(guān)係相應(yīng)機(jī)制為同步機(jī)制。例：一個(gè)用戶作業(yè)：兩個(gè)矩陣求逆後相加加法進(jìn)程求逆進(jìn)程求逆進(jìn)程進(jìn)程之間有一定的先後執(zhí)行次序例:

司機(jī)P1

售票員P2

while(true)while(true)

{{

啟動(dòng)車輛；關(guān)門；

正常運(yùn)行；售票；

到站停車；開門；

}}

四、進(jìn)程互斥互斥關(guān)係：（間接制約）指散佈在不同進(jìn)程中的若干程式片段，當(dāng)某個(gè)進(jìn)程運(yùn)行其中一個(gè)程式片段時(shí)，其他進(jìn)程就不能運(yùn)行它們中的任一程式片段，只能等到該進(jìn)程運(yùn)行完這個(gè)程式片段後才可運(yùn)行?；コ饪煽闯墒且环N特殊的同步關(guān)係。5.2臨界段臨界段的提出臨界段的互斥要求一、臨界段的提出兩個(gè)例子（進(jìn)程的輸出結(jié)果取決於進(jìn)程運(yùn)行的精確時(shí)序）臨界資源：一次僅能為一個(gè)進(jìn)程使用的資源。硬體資源：輸入機(jī)，印表機(jī)。軟體資源：變數(shù)，佇列，表格。臨界段：進(jìn)程中訪問共用變數(shù)的代碼段。二、使用臨界段的原則：有空讓進(jìn)：當(dāng)無進(jìn)程在臨界段時(shí)，任何有權(quán)使用臨界段的進(jìn)程可進(jìn)入無空等待：不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入臨界段多中擇一：當(dāng)無進(jìn)程在臨界段，而同時(shí)有多個(gè)進(jìn)程要求進(jìn)入臨界段，只能讓其中之一進(jìn)入臨界段，其他進(jìn)程須等待有限等待：任何進(jìn)入臨界段的要求應(yīng)在有限的時(shí)間內(nèi)得到滿足讓權(quán)等待：處於等待狀態(tài)的進(jìn)程應(yīng)放棄佔(zhàn)用CPU，

以使其他進(jìn)程有機(jī)會使用CPU5.3互斥進(jìn)程互斥的解決方法：1、互斥的軟體方法2、互斥的硬體方法硬體方法允許在一個(gè)存儲週期內(nèi)測試和修改一個(gè)字的內(nèi)容，或者交換兩個(gè)字的內(nèi)容，指令的執(zhí)行不可中斷。TS指令SWAP指令開關(guān)中斷指令硬體解法(1)

“測試並設(shè)置”TS指令

functionTS(varflag:boolean):booleanbeginTS:=flag;flag:=true;end;

whileTS(lock)doskip;

臨界段

lock：=false;硬體解法(2)

“交換”SWAP指令procedureSWAP(vara,b:boolean)begintemp:=a;a:=b;b:=temp;end

key:=true;repeatSWAP(lock,key);untilkey=false;

臨界區(qū)

lock:=false;硬體解法(3)

“開關(guān)中斷”指令進(jìn)入臨界區(qū)前執(zhí)行：執(zhí)行“關(guān)中斷”指令離開臨界區(qū)後執(zhí)行：執(zhí)行“開中斷”指令5.4信號量信號量概念信號量及同步原語信號量的應(yīng)用一、信號量的概念1、概念：信號量表示資源的物理實(shí)體，是一個(gè)與佇列有關(guān)的整體變數(shù)，除對其初始化外，其值僅能由wait和signal兩種不可中斷的操作來改變。2、對信號量S的操作有兩個(gè)：wait與signal。(又稱同步原語）表示為wait(s),signal(s).二、信號量及同步原語1、信號量分類二元信號量：它允許取值僅為0，1，其初始值為1，主要用於解決進(jìn)程互斥問題。一般信號量：取值不限於0和1，其初值為0或?yàn)槟硞€(gè)正整數(shù)n，主要用於進(jìn)程間的同步。2、同步原語的實(shí)現(xiàn)

同步原語的描述有兩種不同的形式：阻塞等待方式，忙等待方式。（1）阻塞等待方式WAIT（S）判斷S進(jìn)程繼續(xù)阻塞該進(jìn)程將進(jìn)程插入S的等待佇列L中，重新調(diào)度SIGNAL（S）S=S+1判斷S進(jìn)程繼續(xù)喚醒等待佇列中的一個(gè)進(jìn)程，重新調(diào)度S>0S<0S<=0

S=S-1S>=0信號量的數(shù)據(jù)結(jié)構(gòu)(將信號量定義進(jìn)一步擴(kuò)充）types=recordvalue:integer;L:pointertoPCB;指向等待佇列的指針

end一般信號量上的同步原語

wait(s):

s.value:=s.value-1;

ifs.value<0

thenbegin

Insert(CALLER,s.L);

Block(CALLER);

end

一般信號量上的同步原語

signal(s):

ifs.value=1

thenbegin

remove(s.L,id);

wakeup(id);

end

二元信號量上的同步原語

waitB(s):

ifs.value=1

then

s.value=0

elsebegin

Insert(CALLER,s.L);

Block(CALLER);

end二元信號量上的同步原語

signalB(s):

ifL.queueisempty

then

s.value=1

elsebegin

Remove(s.L,id);

wakeup(id);

end(2)忙等待方式一般信號量的同步原語二元信號量的同步原語WAIT（S）WAITB（S）

S0

SS-1N

S=0

SS-1NSIGNAL（S）SIGNALB（S）SS-1

SS-1

YY信號量定義為整型變數(shù)Wait(s):whiles<=0doskip; s:=s-1;signal(s):s:=s+1;

忙等待方式和阻塞方式的差別在於不會出現(xiàn)負(fù)值。阻塞等待方式適用於單處理機(jī)方式。忙等待方式適用於多處理機(jī)方式。(3)關(guān)於同步原語的討論1)信號量的物理含義：S>0表示有S個(gè)資源可用S=0表示無資源可用S<0則|S|表示S等待佇列中的進(jìn)程個(gè)數(shù)wait(S):表示申請一個(gè)資源signal(S)表示釋放一個(gè)資源。信號量的初值應(yīng)該大於等於02)wait,signal操作必須成對出現(xiàn)，有一個(gè)wait操作就一定有一個(gè)signal操作當(dāng)為互斥操作時(shí)，它們同處於同一進(jìn)程當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)如果wait(S1)和wait(S2)兩個(gè)操作在一起，那麼wait操作的順序至關(guān)重要,而兩個(gè)signal操作無關(guān)緊要3）同步原語的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡單，而且表達(dá)能力強(qiáng)缺點(diǎn)：不夠安全；同步原語使用不當(dāng)會出現(xiàn)死鎖；遇到複雜同步互斥問題時(shí)實(shí)現(xiàn)複雜例：同步原語使用不當(dāng)會造成死鎖A進(jìn)程 B進(jìn)程WAIT(S1) WAIT(S2)WAIT(S2) WAIT(S1)SIGNAL(S2) SIGNAL(S1)SIGNAL(S1) SIGNAL(S2)3、同步原語的不可分割性信號量上的同步原語應(yīng)該是原子的操作保證進(jìn)程間互斥地使用同步原語整體操作、不可分割、也就是不可打斷其執(zhí)行或者說不可中斷三、信號量應(yīng)用1、用信號量實(shí)現(xiàn)進(jìn)程間的互斥2、用信號量實(shí)現(xiàn)進(jìn)程間的同步1、用信號量實(shí)現(xiàn)進(jìn)程間的互斥設(shè)置互斥信號量，賦初值1，表示臨界資源未被使用。進(jìn)程描述例1設(shè)進(jìn)程P，Q共用一臺印表機(jī)，印表機(jī)任何時(shí)刻只能被一個(gè)進(jìn)程使用，而不能同時(shí)使用。試用同步原語描述進(jìn)程，保證兩個(gè)進(jìn)程不同時(shí)使用印表機(jī)。定義信號量S：表示印表機(jī)數(shù)目，初值為1；進(jìn)程P：·

·

·

wait(s);

使用打印機(jī)

signal(s);例2設(shè)n個(gè)進(jìn)程P1，P2，...，Pn共用m臺印表機(jī)，試用同步原語描述進(jìn)程。

定義信號量S

進(jìn)程描述2、用信號量實(shí)現(xiàn)進(jìn)程間的同步例1：同步關(guān)係：P1-P2定義信號量進(jìn)程描述

例2用同步原語解決司機(jī)與售票員的問題司機(jī)進(jìn)程：while(true){啟動(dòng)車輛正常駕駛到站停車}…售票員進(jìn)程：while(true){關(guān)門售票開門}…有父母子女四人圍坐一起吃水果，父親不斷削蘋果往盆中放，母親不斷削梨往盆中放，女兒則從盆中取蘋果吃，兒子則從盆中取梨吃，假如盆中最多只能放N只水果，試用同步原語協(xié)調(diào)他們的關(guān)係。四、經(jīng)典的進(jìn)程同步問題1、生產(chǎn)者和消費(fèi)者問題2、閱讀者和寫入者問題3、哲學(xué)家就餐問題1、生產(chǎn)者和消費(fèi)者問題消費(fèi)者生產(chǎn)者緩衝區(qū)1、生產(chǎn)者和消費(fèi)者問題由n個(gè)緩衝區(qū)構(gòu)成的一個(gè)緩衝記憶體，每個(gè)緩衝區(qū)可存放一個(gè)資料項(xiàng)目。生產(chǎn)者：生產(chǎn)數(shù)據(jù)並將其放入緩衝區(qū)中的進(jìn)程。消費(fèi)者：消耗並處理緩衝區(qū)中數(shù)據(jù)的進(jìn)程。（1）設(shè)置信號量

mutex：保證對該緩衝記憶體的互斥執(zhí)行。其初值為1。

E：表示空緩衝區(qū)數(shù)目，其初值為nF：表示滿緩衝區(qū)數(shù)目，其初值為0。

(2)進(jìn)程同步關(guān)係描述

生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程注意：兩個(gè)wait操作順序不能互換。例如：當(dāng)mutex=1,E=0,F=n時(shí)，則對生產(chǎn)者進(jìn)程：wait(mutex)成功，wait(E)失?。粚οM(fèi)者進(jìn)程：wait(F)成功，wait(mutex)失敗，形成互鎖。

(2)進(jìn)程同步關(guān)係描述

生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程注意：wait兩個(gè)操作不能互換。例如：當(dāng)mutex=1,E=0,F=n時(shí)，則對生產(chǎn)者進(jìn)程：wait(mutex)成功，wait(E)失?。粚οM(fèi)者進(jìn)程：wait(F)成功，wait(mutex)失敗，形成互鎖。注意：wait兩個(gè)操作不能互換。

例如：當(dāng)mutex=1,E=0,F=n時(shí)，

則對生產(chǎn)者進(jìn)程：wait(mutex)成功，wait(E)失?。?/p>

對消費(fèi)者進(jìn)程：wait(F)成功，wait(mutex)失敗，形成互鎖。

2、閱讀者和寫入者問題一個(gè)數(shù)據(jù)集為若干併發(fā)進(jìn)程共用。閱讀者：要求讀取數(shù)據(jù)寫入者：要求修改數(shù)據(jù)要求：允許多個(gè)閱讀者同時(shí)執(zhí)行讀操作不允許閱讀者、寫入者同時(shí)操作不允許多個(gè)寫入者同時(shí)操作如果閱讀者來：1）無閱讀者、寫入者，新讀者可以讀2）有寫入者等，但有其他閱讀者正在讀，則新閱讀者也可以讀3）有寫入者寫，新閱讀者等如果寫入者來：1）無閱讀者、寫入者，新寫入者可以寫2）有閱讀者，新寫入者等待3）有其他寫入者，新寫入者等待（1）信號量設(shè)置：mutex:用於閱讀者互斥地訪問共用變數(shù)wrt:用於寫入者和其他進(jìn)程互斥地訪問共用變數(shù)，初值為1。readcount普通整形變數(shù)，表示正在讀數(shù)據(jù)的閱讀者個(gè)數(shù)，初值為0。wait（mutex）readcount：=readcount+1IFreadcount=1THENwait（wrt）signal（mutex）讀數(shù)據(jù)wait（mutex）readcount；=readcount-1IFreadcount=0THENsignal（wrt）signal（mutex）（2）進(jìn)程

同步關(guān)係描述

閱讀者進(jìn)程寫入者進(jìn)程

wait（mutex）

寫數(shù)據(jù)

signal（wrt）

3、哲學(xué)家就餐問題有五個(gè)哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐，哲學(xué)家們共用一張圓桌，周圍放有五張椅子，每人坐一張，在圓桌上有五碗面和五個(gè)叉子。當(dāng)哲學(xué)家思考時(shí)，他不與同事交談。饑餓時(shí)，便試圖取用左邊和右邊的叉子，他可能一個(gè)也拿不到，只有在他拿到兩個(gè)叉子時(shí)，方能就餐，吃完後，放下叉子又繼續(xù)思考。（1）信號量設(shè)置為每個(gè)叉子設(shè)置信號量：VARfork:array[0..4]ofsemaphore信號量的初值均為1。(2)進(jìn)程描述（第I個(gè)哲學(xué)家的活動(dòng)）

WAIT(fork[I])取左邊的叉子

WAIT(fork[(I+1)mod5])取右邊的叉子就餐

SIGNAL(fork[I])放下左邊的叉子

SIGNAL(fork[(I+1)mod5])放下右邊的叉子

思考五、管程1、管程的提出2、管程的定義3、用管程實(shí)現(xiàn)同步1、管程的提出

採用信號量來編寫併發(fā)程式，對於共用變數(shù)及信號量的操作將被分散於各個(gè)進(jìn)程中缺點(diǎn)：（１）易讀性差，因?yàn)橐t解對於一組共用變數(shù)及信號量的操作是否正確，則必須通讀整個(gè)系統(tǒng)或者併發(fā)程式（2）不利於修改和維護(hù)，因?yàn)槌淌降木植啃院懿?，所以任一組變數(shù)或一段代碼的修改都可能影響全局（３）正確性難以保證，因?yàn)椴僮飨到y(tǒng)或併發(fā)程式通常很大，要保證這樣一個(gè)複雜的系統(tǒng)沒有邏輯錯(cuò)誤是很難的2、管程的定義指關(guān)於共用資源的數(shù)據(jù)及在其上操作的一組過程或共用數(shù)據(jù)結(jié)構(gòu)及其規(guī)定的所有操作管程是管理進(jìn)程間同步的機(jī)制，它保證進(jìn)程互斥地訪問共用變數(shù)，並且提供了一個(gè)方便的阻塞和喚醒進(jìn)程的機(jī)構(gòu)。管程的基本特性：局部於管程的數(shù)據(jù)只能被局部於管程內(nèi)的過程所訪問一個(gè)進(jìn)程只有通過調(diào)用管程內(nèi)的過程才能進(jìn)入管程訪問共用數(shù)據(jù)每次只允許一個(gè)進(jìn)程在管程內(nèi)執(zhí)行某個(gè)內(nèi)部過程管程的四個(gè)組成部分：管程的四個(gè)組成部分：名稱數(shù)據(jù)結(jié)構(gòu)說明對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程/函數(shù)初始化語句3、用管程實(shí)現(xiàn)同步管程中支持同步的組成部分：局限於管程並僅能從管程內(nèi)進(jìn)行訪問的若干條件變數(shù)（Condition）在條件變數(shù)上進(jìn)行操作的兩個(gè)函數(shù)過程

WaitC(C)和SignalC(C)WaitC(C):將調(diào)用此函數(shù)的進(jìn)程掛起阻塞在與該條件變數(shù)C相關(guān)的佇列中，並使管程成為可用SignalC(C)：喚醒條件變數(shù)C的等待佇列中的某個(gè)進(jìn)程；若等待佇列為空，則為空操作5.6進(jìn)程間的通信一、進(jìn)程通信的概念二、進(jìn)程通信的實(shí)現(xiàn)三、間接通信模式四、其他通信模式一、進(jìn)程通信的概念指在進(jìn)程間交換一定數(shù)量的資訊。 信號量實(shí)現(xiàn)的是進(jìn)程之間的低級通訊，只能傳遞簡單的信號，不能傳遞大量資訊。如果要在進(jìn)程間傳遞大量資訊則要使用通信原語（Send/Receive原語）二、直接通信模式1、數(shù)據(jù)結(jié)構(gòu)消息、消息緩衝、消息佇列2、通信原語發(fā)送原語：send接收原語：receivePCB......Send(R,M)......SIZE:消息長度TEXT:消息正文......消息鏈指針............Receive(pid,N)......SIZE:消息長度TEXT:消息正文......M:N:接受進(jìn)程R發(fā)送進(jìn)程S消息消息消息......三、間接通信模式發(fā)送進(jìn)程發(fā)消息時(shí)不指定接收進(jìn)程的名字，而是指定一個(gè)中間媒介，即信箱。進(jìn)程間通過信箱實(shí)現(xiàn)通信

發(fā)送原語：send(MB,Message)

接收原語：receive(MB,Message)四、其他通信模式第6章多處理器系統(tǒng)和處理器管理調(diào)度的層次和作業(yè)調(diào)度單處理器系統(tǒng)的處理器調(diào)度多處理器系統(tǒng)對稱多處理器系統(tǒng)多處理器系統(tǒng)的處理器管理和調(diào)度6.1調(diào)度的層次和作業(yè)調(diào)度一、調(diào)度層次1、作業(yè)運(yùn)行2、處理機(jī)調(diào)度3、處理機(jī)長期，短期調(diào)度關(guān)係1、作業(yè)運(yùn)行

程式員操作員輸入機(jī)磁盤作業(yè)記憶體打印結(jié)束A

B

C

D作業(yè)狀態(tài)提交狀態(tài)（A）：用戶將作業(yè)交給機(jī)房，輸入輸入機(jī)。後備狀態(tài)（B）：作業(yè)資訊輸入輸入機(jī)，存放在磁片的某些盤區(qū)，等待操作系統(tǒng)接受。運(yùn)行狀態(tài)（C）：作業(yè)被調(diào)度送入記憶體運(yùn)行。完成狀態(tài)（D）：作業(yè)全部完成，釋放資源，退出系統(tǒng)。2、調(diào)度層次處理器調(diào)度分為三級：長期調(diào)度（作業(yè)調(diào)度）中期調(diào)度短期調(diào)度（進(jìn)程調(diào)度）長期調(diào)度按某種原則挑選作業(yè)投入運(yùn)行為作業(yè)創(chuàng)建進(jìn)程為選中作業(yè)分配資源中期調(diào)度決定哪些作業(yè)允許參於競爭處理機(jī)資源。作用：起到短期調(diào)整系統(tǒng)負(fù)荷，以平順系統(tǒng)。方式：“掛起”，“解掛”。短期調(diào)度按某種原則將處理機(jī)分配給就緒進(jìn)程。進(jìn)程調(diào)度屬操作系統(tǒng)內(nèi)核，執(zhí)行頻率很高。3、處理機(jī)長期，短期調(diào)度關(guān)係

提交後備阻塞就緒運(yùn)行

完成作業(yè)註冊作業(yè)調(diào)度進(jìn)程調(diào)度作業(yè)終止

運(yùn)行二、作業(yè)調(diào)度1、作業(yè)調(diào)度的職能2、作業(yè)控制塊3、調(diào)度性能的衡量1、作業(yè)調(diào)度的職能記錄已進(jìn)入系統(tǒng)的作業(yè)情況JCB調(diào)度演算法：按照某種調(diào)度演算法從後備狀態(tài)挑選作業(yè)運(yùn)行。運(yùn)行準(zhǔn)備：為選中作業(yè)創(chuàng)建進(jìn)程，分配主存和外設(shè)。結(jié)束善後處理：收回資源，輸出必要資訊。作業(yè)進(jìn)入後備狀態(tài)建立作業(yè)退出系統(tǒng)時(shí)撤銷2、作業(yè)控制塊作業(yè)存在唯一標(biāo)誌作業(yè)調(diào)度的依據(jù)記錄作業(yè)的有關(guān)資訊，反映作業(yè)運(yùn)行情況內(nèi)容進(jìn)入系統(tǒng)時(shí)建立退出系統(tǒng)時(shí)撤銷作業(yè)名資源要求資源使用情況類型說明狀態(tài)3、調(diào)度性能的衡量平均周轉(zhuǎn)時(shí)間：作業(yè)k的周轉(zhuǎn)時(shí)間Tk=完成時(shí)間-提交時(shí)間=等待時(shí)間+運(yùn)行時(shí)間平均周轉(zhuǎn)時(shí)間T=Tk/作業(yè)數(shù)6.2單處理器系統(tǒng)的處理器調(diào)度處理器調(diào)度的主要功能：按一定的演算法，動(dòng)態(tài)地把處理機(jī)分配給就緒佇列中的某個(gè)進(jìn)程1、選擇調(diào)度演算法時(shí)應(yīng)考慮的問題設(shè)計(jì)目標(biāo)資源利用率均衡地處理系統(tǒng)和用戶要求優(yōu)先順序可搶佔(zhàn)和不可搶佔(zhàn)2、調(diào)度演算法先進(jìn)先服務(wù)調(diào)度演算法最短作業(yè)優(yōu)先調(diào)度演算法時(shí)間片輪轉(zhuǎn)演算法優(yōu)先順序調(diào)度演算法最短剩餘時(shí)間優(yōu)先調(diào)度演算法最高回應(yīng)比優(yōu)先多級回饋佇列調(diào)度演算法(1)先進(jìn)先出調(diào)度演算法其原則按照作業(yè)到達(dá)系統(tǒng)或進(jìn)程進(jìn)入就緒佇列先後次序來選擇。FIFO是一種非搶佔(zhàn)演算法。例題進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間優(yōu)先數(shù)10322265344346565821作業(yè)1作業(yè)2作業(yè)3作業(yè)4作業(yè)5039131820平均周轉(zhuǎn)時(shí)間T=1/5（3+7+9+12+12）=8.60（2）短作業(yè)優(yōu)先調(diào)度演算法根據(jù)JCB估算運(yùn)算時(shí)間，選取最短作業(yè)為調(diào)度對象短作業(yè)優(yōu)先調(diào)度是非搶佔(zhàn)演算法。缺點(diǎn)：會使長作業(yè)饑餓。作業(yè)1作業(yè)2作業(yè)5作業(yè)3作業(yè)4039111520T=1/5（3+7+11+14+3）=7.60（3）時(shí)間片輪轉(zhuǎn)調(diào)度演算法把CPU的時(shí)間分割成時(shí)間片，處於就緒狀態(tài)的進(jìn)程輪流獲得時(shí)間片。時(shí)間片輪轉(zhuǎn)調(diào)度演算法是搶佔(zhàn)演算法。其調(diào)度演算法的性能取決於時(shí)間片Q。Q=4（時(shí)間片為4）作業(yè)1作業(yè)2作業(yè)3作業(yè)4作業(yè)5作業(yè)2作業(yè)40371115171920T=1/5（3+17+7+14+9）=10.00（4）優(yōu)先順序調(diào)度演算法選擇優(yōu)先數(shù)高的進(jìn)程和作業(yè)作為調(diào)度對象。按搶佔(zhàn)與否優(yōu)先數(shù)可分：非搶佔(zhàn)的優(yōu)先調(diào)度演算法可搶佔(zhàn)的優(yōu)先調(diào)度演算法按靜態(tài)，動(dòng)態(tài)優(yōu)先數(shù)可分：靜態(tài)優(yōu)先數(shù)動(dòng)態(tài)優(yōu)先數(shù)非搶佔(zhàn)的優(yōu)先調(diào)度作業(yè)1作業(yè)2作業(yè)4作業(yè)3作業(yè)5039141820

T=1/5（3+7+14+8+12）=8.8可搶佔(zhàn)的優(yōu)先調(diào)度作業(yè)1作業(yè)2作業(yè)4作業(yè)2作業(yè)3作業(yè)1作業(yè)50261113171820

T=1/5（18+11+13+5+12）=11.8（5）最短剩餘時(shí)間優(yōu)先調(diào)度演算法基本思想：讓從運(yùn)行到完成所需時(shí)間最短的作業(yè)優(yōu)先得到處理。最短剩餘時(shí)間：從作業(yè)當(dāng)前運(yùn)行到完成所需時(shí)間。最短剩餘時(shí)間優(yōu)先調(diào)度是搶佔(zhàn)演算法。用於分時(shí)系統(tǒng)其輪轉(zhuǎn)時(shí)間最優(yōu)作業(yè)1作業(yè)2作業(yè)3作業(yè)5作業(yè)2作業(yè)40348101520T=1/5（3+13+4+14+2）=7.20（6）最高回應(yīng)比優(yōu)先回應(yīng)比=等待時(shí)間+服務(wù)時(shí)間服務(wù)時(shí)間最高回應(yīng)比是FIFO和短作業(yè)優(yōu)先的折中。最高回應(yīng)比是一種非搶佔(zhàn)演算法。作業(yè)1作業(yè)2作業(yè)3作業(yè)5作業(yè)4039131520T=1/5（3+7+9=9+12）=8.00（8）多級回饋佇列調(diào)度演算法系統(tǒng)中有多個(gè)就緒佇列各級就緒佇列具有不同的時(shí)間片各級佇列均按FIFO原則排隊(duì)調(diào)度方法：首先調(diào)度優(yōu)先順序高的進(jìn)程，當(dāng)優(yōu)先順序高的進(jìn)程為空，才調(diào)度下一級。例題進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間優(yōu)先數(shù)10322265344346565821作業(yè)名到達(dá)時(shí)刻完成時(shí)刻運(yùn)行時(shí)間

J1022

J223 1

J143

J3451

J262

J4671

J382

J5891

J4102

J5112

J2123

J3133

J4143

J2154

J3164

J4174

J2185

J4 195

J2206Q=1（每級回饋佇列每一級時(shí)間片為1）1121324354523423424201234567891011121314151617181920T=1/5（4+18+12+13+3）=10.00Q=2**N（每級回饋佇列每一級時(shí)間片以2冪次方遞增）1121322453344522234401234567891011121314151617181920T=1/5（4+15+14+14+6）=10.06生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混在一塊