ch3西安電子科技大學操作系統(tǒng)課件

計算機操作系統(tǒng)第三章進程管理1計算機操作系統(tǒng)第三章進程管理1標題添加點擊此處輸入相關(guān)文本內(nèi)容點擊此處輸入相關(guān)文本內(nèi)容前言點擊此處輸入相關(guān)文本內(nèi)容標題添加點擊此處輸入相關(guān)文本內(nèi)容標題添加點擊此處輸入相點擊此處輸入前言點擊此處輸入標題添加點第三章進程管理進程的定義與控制進程調(diào)度進程間的相互作用進程通信線程UNIX和Windows的進程和線程模型3第三章進程管理進程的定義與控制33.1進程的引入在早期計算機系統(tǒng)中，多道程序設計還未出現(xiàn)之前，程序是順序執(zhí)行的。多道程序設計出現(xiàn)后，操作系統(tǒng)可以實現(xiàn)多個進程的并發(fā)執(zhí)行。進程（process）一詞在20世紀60年代初首先出現(xiàn)的MIT的MULTICS系統(tǒng)中。進程是程序的一次執(zhí)行，多個進程可以并發(fā)執(zhí)行。43.1進程的引入在早期計算機系統(tǒng)中，多道程序設計還未出現(xiàn)之3.1進程的引入程序的順序執(zhí)行和并發(fā)執(zhí)行

程序的執(zhí)行有兩種方式：順序執(zhí)行和并發(fā)執(zhí)行。順序執(zhí)行是單道批處理系統(tǒng)的執(zhí)行方式，也用于簡單的單片機系統(tǒng)；現(xiàn)在的操作系統(tǒng)多為并發(fā)執(zhí)行，具有許多新的特征。引入并發(fā)執(zhí)行的目的是為了提高資源利用率。程序順序執(zhí)行：一個較大的程序通常由若干個程序段組成，程序在執(zhí)行時，各程序段必須按照先后次序逐個執(zhí)行。程序各程序段的這種先后次序可用前趨圖表示。53.1進程的引入程序的順序執(zhí)行和并發(fā)執(zhí)行53.1進程的引入前趨圖是一個有向無循環(huán)圖，圖由結(jié)點和結(jié)點間的有向邊組成，結(jié)點代表各程序段操作，而結(jié)點間的有向邊代表程序段操作之間存在的前趨關(guān)系。兩程序段Pi和Pj的前趨關(guān)系表示成

Pi是Pj的前趨，Pj是Pi的后繼I1C1P1I2C263.1進程的引入前趨圖是一個有向無循環(huán)圖，圖由結(jié)點和結(jié)點間3.1進程的引入順序執(zhí)行的特征順序性：CPU嚴格按照程序結(jié)構(gòu)所指定的次序執(zhí)行。封閉性：獨占全部資源，資源的狀態(tài)只能由該程序本身改變，不受其它程序和外界因素影響?？稍佻F(xiàn)性：如果程序執(zhí)行環(huán)境和初始條件相同，則其執(zhí)行的結(jié)果相同。73.1進程的引入順序執(zhí)行的特征73.1進程的引入多道程序設計：把一個以上的程序放入內(nèi)存中，并且同時處于運行狀態(tài)，這些程序共享CPU和其它資源。特點如下：多道：內(nèi)存中有多道程序，它們在任一時刻必須處于就緒、運行、阻塞三種狀態(tài)。宏觀上并行：從宏觀上看，它們在同時執(zhí)行。微觀上串行：從微觀上看，它們在交替、穿插執(zhí)行。83.1進程的引入多道程序設計：把一個以上的程序放入內(nèi)存中，3.1進程的引入多道程序設計優(yōu)點：CPU利用率高。設備利用率高。系統(tǒng)吞吐量大。P1P2tI/OCPU兩個進程執(zhí)行示意圖93.1進程的引入多道程序設計優(yōu)點：P1P2tI/OCPU兩3.1進程的引入并發(fā)執(zhí)行的特征：失去封閉性：共享資源，程序之間互相制約。間斷性：程序之間的制約關(guān)系致使程序執(zhí)行時間不連貫。不可再現(xiàn)性：失去封閉性，也就失去了可再現(xiàn)性，程序執(zhí)行的結(jié)果隨速度、環(huán)境的不同而不同。

可見，并發(fā)和并行是不同的概念：并行是并發(fā)的特例，并發(fā)是并行的拓展。103.1進程的引入并發(fā)執(zhí)行的特征：10觀察者begin repeat waitforacarthrough N=N+1 untilend報告者begin repeat delay printN N=0 untilend初始N=n時不同執(zhí)行序列，結(jié)果各不相同執(zhí)行序列123程序N=N+1printNN=0printNN=0N=N+1printNN=N+1N=0結(jié)果打印n+1,N=0打印n,N=1打印n,N=0例子：觀察者與報告者11觀察者報告者初始N=n時不同執(zhí)行序列，結(jié)果各不相同執(zhí)行序列13.1進程的引入 綜上所述，由于程序的并發(fā)執(zhí)行破壞了程序的封閉性和可再現(xiàn)性，使得程序和程序的執(zhí)行不再一一對應，因此，程序這個靜態(tài)的概念已經(jīng)不能切實反映程序執(zhí)行的各種特征。 于是，引入“進程”，能夠反映程序執(zhí)行的獨立性、并發(fā)性和動態(tài)性等特征。123.1進程的引入 綜上所述，由于程序的并發(fā)執(zhí)行破壞了3.2進程定義與控制進程定義進程是程序的一次執(zhí)行進程是可以和別的計算并發(fā)執(zhí)行的計算進程是定義在一個數(shù)據(jù)結(jié)構(gòu)上并能在其上進行操作的一個程序進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位133.2進程定義與控制進程定義133.2進程定義與控制進程與程序的區(qū)別進程是動態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進程是程序的一次執(zhí)行。進程是暫時的，程序的永久的：進程是一個狀態(tài)變化的過程，程序可長久保存。進程與程序的組成不同：進程的組成包括程序、數(shù)據(jù)和進程控制塊（即進程狀態(tài)信息）。進程與程序的對應關(guān)系：通過多次執(zhí)行，一個程序可對應多個進程；通過調(diào)用關(guān)系，一個進程可包括多個程序。143.2進程定義與控制進程與程序的區(qū)別143.2進程定義與控制

進程：是程序的一次執(zhí)行，該程序可與其它程序并發(fā)執(zhí)行；它是一個動態(tài)實體，在傳統(tǒng)的操作系統(tǒng)設計中，進程既是基本的分配單位，也是基本的執(zhí)行單位。153.2進程定義與控制 進程：是程序的一次執(zhí)行，該程序可3.2進程定義與控制進程組成：有程序段、數(shù)據(jù)段和進程控制塊(PCB)組成。程序和數(shù)據(jù)是進程存在的物理基礎(chǔ)，是進程的實體進程控制塊是進程的靈魂，是進程存在的唯一標志操作系統(tǒng)為進程創(chuàng)建進程控制塊和分配地址空間的過程就是進程創(chuàng)建的過程163.2進程定義與控制進程組成：有程序段、數(shù)據(jù)段和進程控制塊3.2進程定義與控制進程控制塊：是操作系統(tǒng)用來記錄進程詳細狀態(tài)和相關(guān)信息的基本數(shù)據(jù)結(jié)構(gòu)，包括進程的標識信息、狀態(tài)信息和控制信息。標識信息：唯一的標識一個進程，主要有進程標識、用戶標識和父進程標識。狀態(tài)信息：與CPU有關(guān)的各種現(xiàn)場信息，包括寄存器狀態(tài)、堆棧指針。以便該進程重新占用CPU后能夠繼續(xù)執(zhí)行。173.2進程定義與控制進程控制塊：是操作系統(tǒng)用來記錄進程詳細3.2進程定義與控制控制信息：操作系統(tǒng)對進程進行調(diào)度管理時用到的信息。主要有進程狀態(tài)、調(diào)度信息、隊列指針、資源占有使用信息等。進程控制塊的組織方式PCB在內(nèi)存中是以表的形式存在的－PCB表。還可以將相同性質(zhì)的進程組織在一張表中，形成多個索引表。有些操作系統(tǒng)將PCB分為常駐內(nèi)存和非常駐內(nèi)存兩部分，如UNIX。183.2進程定義與控制控制信息：操作系統(tǒng)對進程進行調(diào)度管理時3.2進程定義與控制進程基本狀態(tài)運行態(tài)（Running）：進程已經(jīng)獲得所需資源，并占有CPU就緒態(tài)（Ready）：已經(jīng)獲得所需資源，只等待CPU阻塞態(tài)（Blocked）：也稱為等待態(tài)、掛起態(tài)或睡眠態(tài)等，進程等待某個事件，如等待I/O完成，等待某個資源此外，還可以有新建態(tài)、終止態(tài)。193.2進程定義與控制進程基本狀態(tài)193.2進程定義與控制進程狀態(tài)的轉(zhuǎn)換新建終止就緒阻塞運行創(chuàng)建完畢時間片用完結(jié)束執(zhí)行選中等待事件等待結(jié)束203.2進程定義與控制進程狀態(tài)的轉(zhuǎn)換新建終止就緒阻塞運行創(chuàng)建七狀態(tài)進程模型活動掛起事件發(fā)生事件發(fā)生等待事件掛起調(diào)度超時釋放活動掛起21七狀態(tài)進程模型活動掛起事件事件等待掛起調(diào)度超時釋放活動掛起22222PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn......空PCB運行態(tài)就緒態(tài)等待1等待26751015進程控制塊（ProcessControlBlock）23PCB1PCB2PCB3PCB4PCB5PCB6PCB7PC3.2進程定義與控制進程控制－通過原語（Primitive）操作實現(xiàn)原語是指由機器指令構(gòu)成的可完成特定功能的程序段。它是一個機器指令的集合，在執(zhí)行時不能被中斷。多采用屏蔽中斷方法實現(xiàn)。進程控制原語有：進程創(chuàng)建原語（createprimitive）進程撤消原語（destroyprimitive）進程阻塞原語（blockprimitive）進程喚醒原語（wakeupprimitive）進程掛起原語（suspendprimitive）進程激活原語（activeprimitive）243.2進程定義與控制進程控制－通過原語（Primitive3.2進程定義與控制進程關(guān)系的樹型結(jié)構(gòu)AA22A21A11A2A1253.2進程定義與控制進程關(guān)系的樹型結(jié)構(gòu)AA22A21A113.2進程定義與控制進程關(guān)系的樹型結(jié)構(gòu)主要優(yōu)點資源分配嚴格：子進程僅能分配到父進程所擁有的資源，用完后歸還。進程控制靈活：可根據(jù)需要給進程以不同的控制權(quán)限。進程結(jié)構(gòu)清楚，關(guān)系明確。263.2進程定義與控制進程關(guān)系的樹型結(jié)構(gòu)263.2進程定義與控制進程特征動態(tài)性：“執(zhí)行”、“計算”、“運行過程”都強調(diào)動態(tài)性，進程的最基本特征。并發(fā)性：進程的重要特征，同時也是操作系統(tǒng)的重要特征。異步性：進程按各自獨立的不可預知的速度向前推進，即進程按異步方式進行，這導致了進程執(zhí)行的不可再現(xiàn)性，因此，操作系統(tǒng)必須采用某些措施來限制各進程推進序列以保證各程序間正常協(xié)調(diào)運行。273.2進程定義與控制進程特征273.2進程定義與控制進程特征獨立性：進程是一個獨立運行的基本單位，即是一個獨立獲得資源和獨立調(diào)度的單位。制約性：一個進程的執(zhí)行可能依賴其他進程的執(zhí)行結(jié)果。結(jié)構(gòu)性：每個進程有固定結(jié)構(gòu)，包括程序、數(shù)據(jù)和PCB三部分。283.2進程定義與控制進程特征283.3進程調(diào)度進程調(diào)度屬于低級調(diào)度，就是從就緒隊列中，按照一定的算法選擇某個進程占用CPU。進程調(diào)度時機現(xiàn)運行進程或者因任務完成而正常結(jié)束，或者因錯誤而異常結(jié)束現(xiàn)運行進程因某種原因，比如I/O請求，從運行態(tài)進入阻塞狀態(tài)現(xiàn)運行進程執(zhí)行某種原語操作，如P操作、阻塞原語等，進入阻塞狀態(tài)一個具有更高優(yōu)先數(shù)的進程要求CPU，即已進入就緒隊列分配給該進程運行的時間片已用完293.3進程調(diào)度進程調(diào)度屬于低級調(diào)度，就是從就緒隊列中，按照3.3進程調(diào)度確定調(diào)度算法的原則：面向系統(tǒng)性能：公平性、較大的吞吐量面向用戶性能：及時性、較短的周轉(zhuǎn)時間303.3進程調(diào)度確定調(diào)度算法的原則：303.3進程調(diào)度進程調(diào)度算法先來先服務進程調(diào)度算法（FCFS）基于優(yōu)先數(shù)的進程調(diào)度算法：根據(jù)優(yōu)先數(shù)大小確定優(yōu)先級高低，分為靜態(tài)優(yōu)先數(shù)法：進程創(chuàng)建時就規(guī)定好優(yōu)先數(shù)動態(tài)優(yōu)先數(shù)法：優(yōu)先數(shù)在執(zhí)行過程中根據(jù)情況改變，例如UNIX時間片輪轉(zhuǎn)進程調(diào)度算法固定時間片可變時間片多級隊列輪轉(zhuǎn)調(diào)度算法313.3進程調(diào)度進程調(diào)度算法31多級隊列輪轉(zhuǎn)調(diào)度算法32多級隊列輪轉(zhuǎn)調(diào)度算法323.3進程調(diào)度進程調(diào)度方式 當一個進程正在CPU上運行時，若有一個更為緊迫或更為重要的進程需要進行處理，或者說，如果有更高優(yōu)先數(shù)的進程進入就緒隊列時，如何分配CPU。通常有兩種方式：不可剝奪方式（不可搶占方式， non-preemptive）可剝奪方式（可搶占方式，preemptive）333.3進程調(diào)度進程調(diào)度方式333.4進程間的相互作用同步：一個進程的某個操作與協(xié)作進程的某個操作之間在時序上有一定的關(guān)系。如果協(xié)作進程的某個操作沒有完成，那么該進程就要等待這個操作完成才能繼續(xù)下去，這種需要相互合作、協(xié)同工作的進程之間的相互關(guān)系稱為進程的同步。臨界資源（獨占資源）：指在一段時間內(nèi)只允許一個進程訪問的資源?；コ猓寒攦蓚€或兩個以上進程競爭同一臨界資源時，進程間的制約關(guān)系稱為進程的互斥。343.4進程間的相互作用同步：一個進程的某個操作與協(xié)作進程的3.4進程間的相互作用進程間的同步司機和售票員的同步正常行駛開車到站停車關(guān)車門開車門售票員售票司機353.4進程間的相互作用進程間的同步正常行駛開車到站停車關(guān)車3.4進程間的相互作用又如，有用戶作業(yè)程序，其形式為：Z=fun1(x)*fun2(y)

其中，fun1(x)和fun2(y)均是一個復雜函數(shù)，為了加快本題的計算速度，可用兩個進程P1、P2各計算一個函數(shù)。進程P2計算fun2(y)，進程P1計算完fun1(x)之后，與進程P2的計算結(jié)果相乘，以獲得最終結(jié)果Z。363.4進程間的相互作用又如，有用戶作業(yè)程序，其形式為：363.4進程間的相互作用結(jié)束置計算完標志P2計算fun2(y)N計算fun1(x)取用P2計算結(jié)果P1P2算完fun2(y)Y373.4進程間的相互作用結(jié)束置計算完標志P2計算fun2(y3.4進程間的相互作用進程的互斥互斥使用資源進程A（阻塞）請求資源R進程B釋放資源R請求資源R（使用R）釋放資源RR分配拒絕喚醒383.4進程間的相互作用進程的互斥進程A（阻塞）請求資源R進

進程間的制約進程間的聯(lián)系進程間同步：相互協(xié)作的進程要共同完成一個任務，它們之間要相互配合，需要在一些動作間進行同步，即一個進程的某個動作與協(xié)作進程的某些動作之間在時序上有一定的關(guān)系。進程間互斥：當兩個或兩個以上的進程競爭同時只能被一個進程使用的資源時，例如競爭使用打印機，需要互斥使用該資源。進程的同步、互斥機制──信號量及P.V操作

39進程間的制約進程間的聯(lián)系進程的同步、互斥機制──信號量及P由于各進程要求共享資源，而有些資源需要互斥使用，因此各進程間競爭使用這些資源，進程的這種關(guān)系為進程的互斥.臨界資源：criticalresource系統(tǒng)中某些資源一次只允許一個進程使用，稱這樣的資源為臨界資源或互斥資源或共享變量臨界資源可以是一些硬件設備（如打印機、磁帶機或繪圖儀等），也可以是進程共享變量、數(shù)據(jù)、隊列、或使用權(quán)限等“有形”或“無形”的資源。進程的互斥（間接制約）mutualexclusion40由于各進程要求共享資源，而有些資源需要互斥使用，因此各進臨界區(qū)（互斥區(qū)）：criticalsection一個程序片段的集合，這些程序片段分散在不同的進程中，對某個共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進行操作.在進程中涉及到臨界資源的程序段叫臨界區(qū).多個進程的臨界區(qū)稱為相關(guān)臨界區(qū).臨界區(qū)（互斥區(qū)）：criticalsection41臨界區(qū)（互斥區(qū)）：criticalsection臨界區(qū)（互臨界區(qū)（criticalsection

）

進程的互斥（間接作用）42臨界區(qū)（criticalsection）進程的互斥4與時間有關(guān)的錯誤由于現(xiàn)在操作系統(tǒng)中的進程是并發(fā)執(zhí)行的，各進程以自己的速度向前推進，所以，運行的順序可能是：

…P1：R1=count；

P2：R2=count；

P1：R1=R1+1；

P1：count=R1；

P2：R2=R2+1；

P2：count=R2；錯誤：P1,P2執(zhí)行的結(jié)果count只加了143與時間有關(guān)的錯誤由于現(xiàn)在操作系統(tǒng)中的臨界區(qū)44臨界區(qū)44使用互斥區(qū)的原則(1)當有若干個進程要求進入臨界區(qū)時，應使一個進程進入臨界區(qū)，它們不應相互等待而使誰都不能進入，即進程不能無限地停留在等待臨界資源的狀態(tài)。(2)一次只允許一個進程進入臨界區(qū)中，即各進程互斥訪問臨界資源。(3)各進程使用臨界資源的時間是有限的，即任何一個進程都必須在有限的時間內(nèi)釋放所占資源。45使用互斥區(qū)的原則(1)當有若干個進程要求進入臨界區(qū)時，應使一解決進程互斥的方法

解決進程互斥的方法有硬件方法和軟件方法。軟件方法中著名的有Dekker算法和Peterson算法。Dekker算法設置一個整型變量turn，指示允許進入臨界區(qū)的進程標識。假設現(xiàn)有兩個進程P1和P2，當turn的值為1時，P1被允許進入；當turn的值為2時，P2被允許進入。進程退出臨界區(qū)時，要把turn的值改為對方的標識符，就等于允許對方的進入。Peterson算法它除設置整型變量turn外，還為每一個進程設置一個標志，指示該進程是否要求進入臨界區(qū)。假設還是兩個進程，都在等待進入臨界區(qū)。先檢查對方的標志，如果不在臨界區(qū)，則檢查turn的值，以確定是否可以進入。46解決進程互斥的方法解決進程互斥的方法有硬件方法和軟件方3.4進程間的相互作用信號量（semaphore）與P、V操作EdsgarWybeDijkstra（埃德斯加?狄克斯特拉）1972年ACM圖靈獎（ACMTuringAward）獲得者“一個程序的易讀性和易理解性同其中所包含的無條件轉(zhuǎn)移控制的個數(shù)成反比關(guān)系。”提出結(jié)構(gòu)化程序設計思想473.4進程間的相互作用信號量（semaphore）與P、V3.4進程間的相互作用483.4進程間的相互作用48信號量及P.V操作信號量（Semaphore）是表示資源的實體，是一個與隊列有關(guān)的整型變量，其值僅能由P、V操作改變。信號量分為：公用信號量和私用信號量。公用信號量:用于實現(xiàn)進程間的互斥，初值通常設為1，它所聯(lián)系的一組并行進程均可對它實施P、V操作；私用信號量用于實現(xiàn)進程間的同步，初始值通常設為0或n，允許擁有它的進程對其實施P操作。49信號量及P.V操作信號量（Semaphore）是表示資源的實信號量：semaphore信號量數(shù)據(jù)結(jié)構(gòu)定義如下：

structsemaphore{ intvalue; pointer_PCBqueue;}信號量說明：

semaphores;50信號量：semaphore信號量數(shù)據(jù)結(jié)構(gòu)定義如下：50P、V操作P(s){s.value=s.value-1;if(s.value<0){

該進程狀態(tài)置為等待狀態(tài);

將該進程的PCB插入相應的等待隊列末尾s.queue;}}51P、V操作P(s)51P、V操作V(s){s.value=s.value+1;if(s.value<=0){

喚醒相應等待隊列s.queue中等待的一個進程改變其狀態(tài)為就緒態(tài)并將其插入就緒隊列

}}P、V操作是原語操作（primitive）原語：是（由若干條機器指令構(gòu)成的）完成某種特定功能的一段程序，具有不可分割性。即原語的執(zhí)行必須是連續(xù)的，不允許被中斷。52P、V操作V(s){P、V操作是原語操作（primitiveP、V操作信號量值的含義：s.value>=0時，其值表示還有可用的資源數(shù)；s.value<0時，其絕對值表示有多少個進程因申請該信號量表示的資源，得不到而進入阻塞態(tài)；53P、V操作信號量值的含義：53用P、V操作解決進程間互斥問題P(S)V(S)P1P2P3互斥區(qū)P(S)P(S)V(S)V(S)設信號量:s=1;

申請進入臨界區(qū)退出臨界區(qū)54用P、V操作解決進程間互斥問題P(S)V(S)P1P2P3互進程互斥執(zhí)行序列：P255進程互斥執(zhí)行序列：P255執(zhí)行序列：P2（就緒）-P1（阻塞）-進程互斥56執(zhí)行序列：P2（就緒）-P1（阻塞）-進程互斥56進程互斥執(zhí)行序列：P2（就緒）-P1（阻塞）-P3（阻塞）57進程互斥執(zhí)行序列：P2（就緒）-P1（阻塞）-P3（阻塞）進程互斥執(zhí)行序列：P2（就緒）-P1（阻塞）-P3（阻塞）-P258進程互斥執(zhí)行序列：P2（就緒）-P1（阻塞）-P3（阻塞）執(zhí)行序列：P2（就緒）-P1（阻塞）-P3（阻塞）-P2-P1進程互斥59執(zhí)行序列：P2（就緒）-P1（阻塞）-P3（阻塞）-P2進程互斥執(zhí)行序列：P2（就緒）-P1（阻塞）-P3（阻塞）-P2-P1-P3信號量Ｓ變化范圍：Ｓ＝１,０,－１,－２即（１～１-n）60進程互斥執(zhí)行序列：P2（就緒）-P1（阻塞）-P3（阻塞）進程互斥舉例（1）例2，上述的“飛機訂票系統(tǒng)”。一個飛機訂票系統(tǒng)可以有多個訂票處的n個訂票終端?，F(xiàn)假設n=2，公共數(shù)據(jù)區(qū)為Hi（i=1,2，…,m），分別存放各次班機的現(xiàn)存票數(shù)，Pi(i=1,2,…,n)表示售票終端的進程。61進程互斥舉例（1）例2，上述的“飛機訂票系統(tǒng)”。一個飛機進程互斥舉例（2）semaphoreS;S=1;//公用信號量cobegin{processPi(i=1,2,…,n){inttemp;按照定票要求找到單元Hi；

P（S）；

temp=Hi;iftemp≥1{temp=temp-1;

Hi=temp;

V(S);

輸出一張票}else{V(S);輸出提示“票已售完”;}coned62進程互斥舉例（2）semaphoreS;if3.4進程間的相互作用進程間的同步633.4進程間的相互作用進程間的同步633.4進程間的相互作用結(jié)束置計算完標志P2計算fun2(y)N計算fun1(x)取用P2計算結(jié)果P1P2算完fun2(y)Y643.4進程間的相互作用結(jié)束置計算完標志P2計算fun2(y3.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：設置信號量S車，S門，初值均為0司機進程while(true){正常行駛；到站停車；V(S門);P(S車);離站開車；}售票員進程while(true){售票；P(S門);開車門；關(guān)車門；V(S車);}653.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：設3.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：設置信號量S車，S門，初值均為0司機到站663.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：設3.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：司機到站-想繼續(xù)開車阻塞673.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：司3.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：司機到站-想繼續(xù)開車阻塞-售票員開車門683.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：司3.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：司機到站-想繼續(xù)開車阻塞-售票員開車門-想繼續(xù)開車門阻塞693.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：司3.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：司機到站-想繼續(xù)開車阻塞-售票員開車門-想繼續(xù)開車門阻塞-司機繼續(xù)行車703.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：司3.4進程間的相互作用用P，V操作實現(xiàn)進程同步的模型P1...P(S)...P2...V(S)...713.4進程間的相互作用用P，V操作實現(xiàn)進程同步的模型P1P3.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：設置信號量S車，S門，初值均為0司機進程while(true){正常行駛；到站停車；V(S門);P(S車);離站開車；}售票員進程while(true){售票；P(S門);開車門；關(guān)車門；V(S車);}723.4進程間的相互作用用P，V操作實現(xiàn)司機－售票員同步：設3.4進程間的相互作用生產(chǎn)者-消費者問題生產(chǎn)者消費者一次只能放或取一個產(chǎn)品放產(chǎn)品取產(chǎn)品733.4進程間的相互作用生產(chǎn)者-消費者問題生產(chǎn)者消費者一次只3.4進程間的相互作用同步問題：P進程（生產(chǎn)者）不能往“滿”的緩沖區(qū)放產(chǎn)品Q進程（消費者）不能從“空”的緩沖區(qū)取產(chǎn)品743.4進程間的相互作用同步問題：743.4進程間的相互作用單緩沖區(qū)、一個生產(chǎn)者和一個消費者：設置私用信號量為S緩，S產(chǎn)，初值為1，0生產(chǎn)者進程Pwhile(true){生產(chǎn)一件產(chǎn)品;P(S緩);/*申請一個空緩沖區(qū)*/放入一件產(chǎn)品；V(S產(chǎn));/*釋放產(chǎn)品*/}消費者進程Qwhile(true){P(S產(chǎn));/*申請一個產(chǎn)品*/拿出一件產(chǎn)品;V(S緩);消費產(chǎn)品;}753.4進程間的相互作用單緩沖區(qū)、一個生產(chǎn)者和一個消費者：設3.4進程間的相互作用n個緩沖區(qū)、k個生產(chǎn)者和m個消費者：增加互斥信號量mutex，初值為1，并設S緩，S產(chǎn)，初值分別為n和0。生產(chǎn)者進程Pwhile(true){生產(chǎn)一件產(chǎn)品;P(S緩);/*申請一個空緩沖區(qū)*/P(mutex);放入一件產(chǎn)品；V(mutex);V(S產(chǎn));/*釋放產(chǎn)品*/}消費者進程Qwhile(true){P(S產(chǎn));/*申請一個滿緩沖區(qū)*/P(mutex);拿出一件產(chǎn)品;V(mutex);V(S緩);消費產(chǎn)品;}兩個P操作交換？763.4進程間的相互作用n個緩沖區(qū)、k個生產(chǎn)者和m個消費者：3.4進程間的相互作用用P，V操作實現(xiàn)進程同步的模型P1...P(S)...P2...V(S)...773.4進程間的相互作用用P，V操作實現(xiàn)進程同步的模型P1P3.4進程間的相互作用對P，V操作的使用應注意：P，V操作都是成對出現(xiàn)的：互斥操作時，它們在同一進程中；同步操作時，它們處于不同的進程。在進程中，P操作的位置和次序至關(guān)重要。一般情況下，對互斥信號量的P操作在后。而V操作沒有特別的限制。P，V操作的優(yōu)點是：原語完備，表達能力強，可以解決任何同步和互斥問題；缺點是不夠安全，實現(xiàn)復雜。783.4進程間的相互作用對P，V操作的使用應注意：783.4進程間的相互作用讀者、寫者問題

多個讀進程可以同時共享資源，但不能和寫進程共享；寫進程之間互斥，訪問時必須獨占資源。需設置一個全局變量對讀進程進行計數(shù)，當?shù)谝粋€讀進程開始進行訪問時執(zhí)行P操作，當最后一個讀進程結(jié)束訪問時執(zhí)行V操作。 現(xiàn)假設讀者優(yōu)先。使用readnum對讀者計數(shù)，初值為0；mutex是對readnum進行互斥操作的信號量，初值為1；write是寫信號量，初值為1。793.4進程間的相互作用讀者、寫者問題793.4進程間的相互作用讀者進程begin P(mutex); readnum=readnum+1; if(readnum==1)P(write); V(mutex); readfile; P(mutex); readnum=readnum－1; if(readnum==0)V(write); V(mutex);end寫者進程begin P(write); writefile; V(write);end第一個讀者來執(zhí)行P操作最后一個讀者來執(zhí)行V操作803.4進程間的相互作用讀者進程寫者進程第一個讀者來執(zhí)行P操3.4進程間的相互作用 前面程序中，寫者會出現(xiàn)“饑餓”現(xiàn)象，可以設計另一種算法，使寫者優(yōu)先，即當有進程讀文件時，如果有寫進程請求寫，那么新的讀進程被拒絕，待現(xiàn)有讀進程讀完后，立即讓寫進程開始運行，當無寫進程運行時才讓讀進程運行。 設置信號量S實現(xiàn)讀者與寫者或?qū)懻咧g的互斥，初值為1；用信號量Sn限制系統(tǒng)中最多n個進程，初值為n。813.4進程間的相互作用 前面程序中，寫者會出現(xiàn)“饑3.4進程間的相互作用讀者進程Pi(i=1,2,...,n)begin P(S); P(Sn); V(S); readfile; V(Sn); end寫者進程Pj(j=1,2,...,n)begin P(S); fori=1tondoP(Sn); writefile; fori=1tondoV(Sn); V(S);end823.4進程間的相互作用讀者進程Pi(i=1,2,...,n3.4進程間的相互作用理發(fā)師問題：

理發(fā)店里有一個理發(fā)師、一把理發(fā)椅、n把供等候理發(fā)的顧客坐的椅子。如果沒有顧客，則理發(fā)師便在理發(fā)椅上睡覺。當一個顧客到來時，他必須先叫醒理發(fā)師，進行理發(fā)。如果理發(fā)師在理發(fā)時又有顧客到來，則如果有空椅子可坐，他就坐下來等，如果沒有空椅子，他就離開。為理發(fā)師和顧客各編寫一段程序描述他們的行為，要求不能帶有競爭條件。833.4進程間的相互作用理發(fā)師問題：833.4進程間的相互作用設三個信號量：customers，用來記錄等待理發(fā)師的顧客數(shù)（不包括正在理發(fā)的顧客），初值為0；barbers，記錄正在等候顧客的理發(fā)師數(shù)，為0或1，初值為0；mutex，用于互斥，初值為1。還需一個變量waiting，初值為0，也用于記錄等候的顧客數(shù)，實際上是customers的一個副本。之所以使用waiting是因為無法讀取信號量的當前值。在該解法中，進入理發(fā)店的顧客必須先看等待的顧客數(shù)，如果少于椅子數(shù)，他留下來等，否則他就離開。843.4進程間的相互作用設三個信號量：customers，用3.4進程間的相互作用理發(fā)師進程{ while(true) { P(customers);//如果顧客為0，睡覺 P(mutex);//要求進程等候 waiting=waiting-1;//等候顧客數(shù)減1 V(barbers);//一個理發(fā)師開始理發(fā) V(mutex);//釋放等候 cuthair();//理發(fā) }}顧客進程{ P(mutex);//進入臨界區(qū)

if(waiting<CHAIRS) { waiting=waiting+1;//等候顧客數(shù)加1

V(customers);//如果必要，喚醒理發(fā)師

V(mutex);//釋放訪問等候

P(barbers);//如果barbers為0，就睡覺

get_haircut();//坐下等候服務 }else{//沒空椅子，就離開 V(mutex); }}

853.4進程間的相互作用理發(fā)師進程顧客進程853.4進程間的相互作用管程（monitor）：解決互斥問題的抽象數(shù)據(jù)類型。進程可以調(diào)用管程中的過程，但不能在管程外的過程中直接訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。基本思想是集中管理各進程臨界區(qū)，按不同的管理方式定義模塊的類型和結(jié)構(gòu)，用數(shù)據(jù)表示抽象系統(tǒng)資源，增加模塊的相對獨立性。863.4進程間的相互作用管程（monitor）：解決互斥問題3.4進程間的相互作用管程（monitor）：管程是一種編程語言構(gòu)件，進入管程的互斥由編譯器負責，用戶無需關(guān)心如何實現(xiàn)互斥。因此，編譯器必須能識別出管程并對互斥作出處理。缺點：在少數(shù)幾種編程語言外無法使用，兼容性不好。873.4進程間的相互作用管程（monitor）：管程是一種編3.5進程通信 使用信號量進行進程通信，程序難于理解且易于死鎖。而且只能傳遞信號，不能傳遞大批量的數(shù)據(jù)，顯然不能滿足某些通信需求。于是引入高級通信機制。883.5進程通信 使用信號量進行進程通信，程序難于理解且易3.5進程通信分類：低級通信和高級通信：根據(jù)交換信息量的多少和效率的高低，如P、V操作屬于低級通信；高級通信包括管道通信和信箱通信。低級通信只傳遞狀態(tài)和整數(shù)值，信息量小，效率低，傳遞較多信息需要多次通信，編程復雜，不易理解。高級通信能夠傳遞大批量數(shù)據(jù)，減輕程序編制的復雜度。包括共享內(nèi)存模式、消息傳遞模式和共享文件模式（管道）。893.5進程通信分類：893.5進程通信分類：直接通信：信息由發(fā)送方直接傳遞給接收方，如管道。間接通信：將收發(fā)雙方進程之外的共享數(shù)據(jù)結(jié)構(gòu)作為通信中轉(zhuǎn)。903.5進程通信分類：903.5進程通信(1)共享內(nèi)存模式：一種最快捷高效的方式，在UNIX系統(tǒng)中被使用。

系統(tǒng)在內(nèi)存中指定一個區(qū)域作為共享存儲區(qū)，建立一張段表進行管理，各進程可以申請其中一個存儲段，并在申請時提供關(guān)鍵字。若申請的存儲區(qū)已經(jīng)被其它進程占有，系統(tǒng)會向申請進程返回關(guān)鍵字，該存儲區(qū)就鏈接到了進程的邏輯地址空間，此后進程就可以直接存取共享存儲區(qū)中的數(shù)據(jù)了。913.5進程通信(1)共享內(nèi)存模式：一種最快捷高效的方式，在3.5進程通信(1)共享內(nèi)存模式：

若申請的存儲段尚未分配，系統(tǒng)會按照申請者的要求分配存儲段，并在段表中加入該進程的信息。使用共享存儲區(qū)進行通信時，進程間的互斥或同步要靠其它的機構(gòu)來實現(xiàn)。923.5進程通信(1)共享內(nèi)存模式：923.5進程通信(2)消息傳遞方式：

消息由發(fā)送方形成，通過一定的機制傳遞給接收方。長度可以固定，也可以變化。 每個消息都由消息頭和消息體組成，其主要結(jié)構(gòu)包含：指向發(fā)送進程的指針：Sptr指向下一消息緩沖區(qū)的指針：Nptr消息長度：Size消息正文：Text933.5進程通信(2)消息傳遞方式：933.5進程通信(2)消息傳遞方式：

基本工作原理：把消息緩沖區(qū)作為進程通信的一個基本單位，借助系統(tǒng)的發(fā)送原語Send(A)和接收原語Receive(B)，實現(xiàn)進程間的通信。每當發(fā)送進程要發(fā)送消息時，發(fā)送進程用Send(A)原語把消息從發(fā)送區(qū)復制到消息緩沖區(qū)，并把它掛在接收進程的消息隊列末尾。如果該進程因等待消息而處于阻塞狀態(tài)，則將其喚醒。每當接收進程要讀取消息時，用接收原語Receive(B)從消息隊列頭取走一個消息放到自己的接收區(qū)。943.5進程通信(2)消息傳遞方式：94PCB......Send(R,M)......SIZE:消息長度TEXT:消息正文..PCB....消息鏈指針............Receive(pid,N)......SIZE:消息長度TEXT:消息正文......M:N:接受進程R發(fā)送進程S消息消息消息......消息緩沖區(qū)結(jié)構(gòu)：消息長度消息正文發(fā)送者消息隊列指針95PCB........PCB..........M:N:接受3.5進程通信(2)消息傳遞方式：

消息隊列要看作臨界資源，需要互斥訪問，在PCB中設置了一個用于互斥的信號量。 類似于生產(chǎn)者-消費者問題。直接通信方式：

Send(P,message)：發(fā)送消息message到進程P Receive(P,message)：從進程P接收消息message間接通信方式：利用信箱作為媒介進行消息傳遞。963.5進程通信(2)消息傳遞方式：963.5進程通信(3)信箱是一個用來對一定數(shù)量的消息進行緩存的地方。是一段存儲區(qū)，每一個信箱用標識符加以區(qū)分，由信箱頭和信箱體兩部分組成。信箱頭存放控制信息，信箱體存放消息內(nèi)容。一個信箱可以被多個進程共享，就實現(xiàn)了消息的廣播發(fā)送。Send(X,mail)：郵件mail發(fā)送到信箱X中Receive(X,mail)：接收信箱X中的郵件mail973.5進程通信(3)信箱973.5進程通信(4)管道(pipe)：是一種共享文件模式，基于文件系統(tǒng)，連接于兩個進程之間，以先進先出的方式實現(xiàn)消息的單向傳送。在UNIX系統(tǒng)中，管道的創(chuàng)建用函數(shù)pipe()實現(xiàn)。該函數(shù)返回用于讀、寫操作的文件描述符fd[0],fd[1]。讀管道時調(diào)用read()函數(shù)，利用參數(shù)fd[0]從管道中讀取字節(jié)。寫管道時調(diào)用write()函數(shù)，利用參數(shù)fd[1]向管道寫信息。983.5進程通信(4)管道(pipe)：是一種共享文件模式，3.5進程通信管道(pipe)：是一種共享文件模式，基于文件系統(tǒng)，連接于兩個進程之間，以先進先出的方式實現(xiàn)消息的單向傳送。注意：通過系統(tǒng)調(diào)用write()和read()進行管道的讀寫。進程間要進行雙向通信，通常需要定義兩個管道。只適用于父子進程之間的通信。管道能夠把信息從一個進程的地址空間拷貝到另一個進程的地址空間。993.5進程通信管道(pipe)：是一種共享文件模式，基于文3.6線程進程作為調(diào)度基本單位的問題：調(diào)度工作量大，耗費系統(tǒng)資源進程間通信延遲大，頻率高的通信過程效率低下。沒有達到理想的并行度。1003.6線程進程作為調(diào)度基本單位的問題：1003.6線程線程（thread）：也叫輕型進程，是可執(zhí)行的實體單元，可代替以往的進程，是處理機調(diào)度的基本單位。多線程：單個進程中執(zhí)行多個線程。典型操作系統(tǒng)有WindowsNT、Solaris、Mach和OS/2。在多線程環(huán)境中，進程被定義為保護單位和資源分配單位，在一個進程內(nèi)部可以有多個線程。1013.6線程線程（thread）：也叫輕型進程，是可執(zhí)行的實3.6線程線程的特征：執(zhí)行狀態(tài)包括創(chuàng)建、就緒、運行、阻塞等當不處于執(zhí)行狀態(tài)時，要保存線程上下文環(huán)境一個執(zhí)行棧進程中的所有線程共享所屬進程內(nèi)的主存和其它資源。1023.6線程線程的特征：1023.6線程不同結(jié)構(gòu)中，進程和線程的區(qū)別：單進程單線程：進程就是線程，線程就是進程。單進程多線程：一個進程中包括多個線程，共享該進程的資源。當一個線程修改了數(shù)據(jù)，其它線程將讀出修改后的數(shù)據(jù)。多進程單線程：等價于單進程單線程的并發(fā)執(zhí)行。多進程多線程：多個進程并發(fā)執(zhí)行，每個進程內(nèi)多個線程并發(fā)執(zhí)行。進程內(nèi)線程也存在調(diào)度問題。1033.6線程不同結(jié)構(gòu)中，進程和線程的區(qū)別：1033.6線程引入線程的好處：創(chuàng)建和撤銷線程的開銷?。簳r間和空間切換迅速：切換內(nèi)容少通信效率高：共享相同的地址空間并發(fā)度高：線程個數(shù)沒有限制PCB多線程進程模型用戶地址空間用戶棧核心棧線程控制塊用戶棧核心棧線程控制塊用戶棧核心棧線程控制塊1043.6線程引入線程的好處：PCB多線程進程模型用戶用核3.6線程線程與進程的比較：調(diào)度方法類似：線程調(diào)度是在運行進程內(nèi)部的調(diào)度都具有并發(fā)性：進程的并發(fā)執(zhí)行轉(zhuǎn)化為線程的并發(fā)執(zhí)行同一進程中的線程共享進程的資源和狀態(tài)，但這些資源和狀態(tài)不歸線程所有。線程具有寄存器和棧，進程具有PCB、用戶地址空間、執(zhí)行程序和數(shù)據(jù)。進程調(diào)度開銷比線程調(diào)度開銷大得多。1053.6線程線程與進程的比較：105例子1：LAN中的一個文件服務器，在一段時間內(nèi)需要處理幾個文件請求因此有效的方法是：為每一個請求創(chuàng)建一個線程106例子1：LAN中的一個文件服務器，在一段時間內(nèi)需要處理幾個文線程的實現(xiàn)機制用戶級線程核心級線程兩者結(jié)合方法107線程的實現(xiàn)機制用戶級線程107一、用戶級線程（UserLevelThread）由應用程序完成所有線程的管理

通過線程庫(用戶空間)

一組管理線程的過程核心不知道線程的存在線程切換不需要核心態(tài)特權(quán)調(diào)度是應用特定的108一、用戶級線程（UserLevelThread）由應用程用戶級線程的優(yōu)點和缺點優(yōu)點：

線程切換不調(diào)用核心調(diào)度是應用程序特定的：可以選擇最好的算法ULT可運行在任何操作系統(tǒng)上（只需要線程庫）缺點：

大多數(shù)系統(tǒng)調(diào)用是阻塞的，因此核心阻塞進程，故進程中所有線程將被阻塞核心只將處理器分配給進程，同一進程中的兩個線程不能同時運行于兩個處理器上109用戶級線程的優(yōu)點和缺點優(yōu)點：109二、核心級線程（KLT）所有線程管理由核心完成沒有線程庫，但對核心線程工具提供API核心維護進程和線程的上下文線程之間的切換需要核心支持以線程為基礎(chǔ)進行調(diào)度例子：WindowsNT，OS/2110二、核心級線程（KLT）所有線程管理由核心完成110核心級線程的優(yōu)點和缺點優(yōu)點：對多處理器，核心可以同時調(diào)度同一進程的多個線程阻塞是在線程一級完成核心例程是多線程的缺點：在同一進程內(nèi)的線程切換調(diào)用內(nèi)核，導致速度下降111核心級線程的優(yōu)點和缺點優(yōu)點：111四、ULT和KLT結(jié)合方法線程創(chuàng)建在用戶空間完成大量線程調(diào)度和同步在用戶空間完成程序員可以調(diào)整KLT的數(shù)量可以取兩者中最好的例子：Solaris112四、ULT和KLT結(jié)合方法線程創(chuàng)建在用戶空間完成112實例：Solaris（續(xù)2）核心級線程：設置了大量KLT

有一個小的數(shù)據(jù)結(jié)構(gòu)和棧完成內(nèi)核的所有工作調(diào)度處理器的單位，其結(jié)構(gòu)由核心維護113實例：Solaris（續(xù)2）核心級線程：113進程1進程2進程3進程4進程5進程庫用戶內(nèi)核硬件用戶級線程內(nèi)核級線程輕型線程處理器114進程1進程2進程3進程4進程5進程庫用戶內(nèi)核硬件用提問與解答環(huán)節(jié)Questionsandanswers提問與解答環(huán)節(jié)添加標題添加標題添加標題添加標題此處結(jié)束語點擊此處添加段落文本.您的內(nèi)容打在這里，或通過復制您的文本后在此框中選擇粘貼并選擇只保留文字添加標題添加添加添加標題此處結(jié)束語點擊此處添加段落文本.感謝聆聽Theusercandemonstrateonaprojectororcomputer,orprintthepresentationandmakeitintoafilm講師：XXXX日期：20XX.X月感謝聆聽講師：XXXX日期：20XX.X月計算機操作系統(tǒng)第三章進程管理118計算機操作系統(tǒng)第三章進程管理1標題添加點擊此處輸入相關(guān)文本內(nèi)容點擊此處輸入相關(guān)文本內(nèi)容前言點擊此處輸入相關(guān)文本內(nèi)容標題添加點擊此處輸入相關(guān)文本內(nèi)容標題添加點擊此處輸入相點擊此處輸入前言點擊此處輸入標題添加點第三章進程管理進程的定義與控制進程調(diào)度進程間的相互作用進程通信線程UNIX和Windows的進程和線程模型120第三章進程管理進程的定義與控制33.1進程的引入在早期計算機系統(tǒng)中，多道程序設計還未出現(xiàn)之前，程序是順序執(zhí)行的。多道程序設計出現(xiàn)后，操作系統(tǒng)可以實現(xiàn)多個進程的并發(fā)執(zhí)行。進程（process）一詞在20世紀60年代初首先出現(xiàn)的MIT的MULTICS系統(tǒng)中。進程是程序的一次執(zhí)行，多個進程可以并發(fā)執(zhí)行。1213.1進程的引入在早期計算機系統(tǒng)中，多道程序設計還未出現(xiàn)之3.1進程的引入程序的順序執(zhí)行和并發(fā)執(zhí)行

程序的執(zhí)行有兩種方式：順序執(zhí)行和并發(fā)執(zhí)行。順序執(zhí)行是單道批處理系統(tǒng)的執(zhí)行方式，也用于簡單的單片機系統(tǒng)；現(xiàn)在的操作系統(tǒng)多為并發(fā)執(zhí)行，具有許多新的特征。引入并發(fā)執(zhí)行的目的是為了提高資源利用率。程序順序執(zhí)行：一個較大的程序通常由若干個程序段組成，程序在執(zhí)行時，各程序段必須按照先后次序逐個執(zhí)行。程序各程序段的這種先后次序可用前趨圖表示。1223.1進程的引入程序的順序執(zhí)行和并發(fā)執(zhí)行53.1進程的引入前趨圖是一個有向無循環(huán)圖，圖由結(jié)點和結(jié)點間的有向邊組成，結(jié)點代表各程序段操作，而結(jié)點間的有向邊代表程序段操作之間存在的前趨關(guān)系。兩程序段Pi和Pj的前趨關(guān)系表示成

Pi是Pj的前趨，Pj是Pi的后繼I1C1P1I2C21233.1進程的引入前趨圖是一個有向無循環(huán)圖，圖由結(jié)點和結(jié)點間3.1進程的引入順序執(zhí)行的特征順序性：CPU嚴格按照程序結(jié)構(gòu)所指定的次序執(zhí)行。封閉性：獨占全部資源，資源的狀態(tài)只能由該程序本身改變，不受其它程序和外界因素影響。可再現(xiàn)性：如果程序執(zhí)行環(huán)境和初始條件相同，則其執(zhí)行的結(jié)果相同。1243.1進程的引入順序執(zhí)行的特征73.1進程的引入多道程序設計：把一個以上的程序放入內(nèi)存中，并且同時處于運行狀態(tài)，這些程序共享CPU和其它資源。特點如下：多道：內(nèi)存中有多道程序，它們在任一時刻必須處于就緒、運行、阻塞三種狀態(tài)。宏觀上并行：從宏觀上看，它們在同時執(zhí)行。微觀上串行：從微觀上看，它們在交替、穿插執(zhí)行。1253.1進程的引入多道程序設計：把一個以上的程序放入內(nèi)存中，3.1進程的引入多道程序設計優(yōu)點：CPU利用率高。設備利用率高。系統(tǒng)吞吐量大。P1P2tI/OCPU兩個進程執(zhí)行示意圖1263.1進程的引入多道程序設計優(yōu)點：P1P2tI/OCPU兩3.1進程的引入并發(fā)執(zhí)行的特征：失去封閉性：共享資源，程序之間互相制約。間斷性：程序之間的制約關(guān)系致使程序執(zhí)行時間不連貫。不可再現(xiàn)性：失去封閉性，也就失去了可再現(xiàn)性，程序執(zhí)行的結(jié)果隨速度、環(huán)境的不同而不同。

可見，并發(fā)和并行是不同的概念：并行是并發(fā)的特例，并發(fā)是并行的拓展。1273.1進程的引入并發(fā)執(zhí)行的特征：10觀察者begin repeat waitforacarthrough N=N+1 untilend報告者begin repeat delay printN N=0 untilend初始N=n時不同執(zhí)行序列，結(jié)果各不相同執(zhí)行序列123程序N=N+1printNN=0printNN=0N=N+1printNN=N+1N=0結(jié)果打印n+1,N=0打印n,N=1打印n,N=0例子：觀察者與報告者128觀察者報告者初始N=n時不同執(zhí)行序列，結(jié)果各不相同執(zhí)行序列13.1進程的引入 綜上所述，由于程序的并發(fā)執(zhí)行破壞了程序的封閉性和可再現(xiàn)性，使得程序和程序的執(zhí)行不再一一對應，因此，程序這個靜態(tài)的概念已經(jīng)不能切實反映程序執(zhí)行的各種特征。 于是，引入“進程”，能夠反映程序執(zhí)行的獨立性、并發(fā)性和動態(tài)性等特征。1293.1進程的引入 綜上所述，由于程序的并發(fā)執(zhí)行破壞了3.2進程定義與控制進程定義進程是程序的一次執(zhí)行進程是可以和別的計算并發(fā)執(zhí)行的計算進程是定義在一個數(shù)據(jù)結(jié)構(gòu)上并能在其上進行操作的一個程序進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位1303.2進程定義與控制進程定義133.2進程定義與控制進程與程序的區(qū)別進程是動態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進程是程序的一次執(zhí)行。進程是暫時的，程序的永久的：進程是一個狀態(tài)變化的過程，程序可長久保存。進程與程序的組成不同：進程的組成包括程序、數(shù)據(jù)和進程控制塊（即進程狀態(tài)信息）。進程與程序的對應關(guān)系：通過多次執(zhí)行，一個程序可對應多個進程；通過調(diào)用關(guān)系，一個進程可包括多個程序。1313.2進程定義與控制進程與程序的區(qū)別143.2進程定義與控制

進程：是程序的一次執(zhí)行，該程序可與其它程序并發(fā)執(zhí)行；它是一個動態(tài)實體，在傳統(tǒng)的操作系統(tǒng)設計中，進程既是基本的分配單位，也是基本的執(zhí)行單位。1323.2進程定義與控制 進程：是程序的一次執(zhí)行，該程序可3.2進程定義與控制進程組成：有程序段、數(shù)據(jù)段和進程控制塊(PCB)組成。程序和數(shù)據(jù)是進程存在的物理基礎(chǔ)，是進程的實體進程控制塊是進程的靈魂，是進程存在的唯一標志操作系統(tǒng)為進程創(chuàng)建進程控制塊和分配地址空間的過程就是進程創(chuàng)建的過程1333.2進程定義與控制進程組成：有程序段、數(shù)據(jù)段和進程控制塊3.2進程定義與控制進程控制塊：是操作系統(tǒng)用來記錄進程詳細狀態(tài)和相關(guān)信息的基本數(shù)據(jù)結(jié)構(gòu)，包括進程的標識信息、狀態(tài)信息和控制信息。標識信息：唯一的標識一個進程，主要有進程標識、用戶標識和父進程標識。狀態(tài)信息：與CPU有關(guān)的各種現(xiàn)場信息，包括寄存器狀態(tài)、堆棧指針。以便該進程重新占用CPU后能夠繼續(xù)執(zhí)行。1343.2進程定義與控制進程控制塊：是操作系統(tǒng)用來記錄進程詳細3.2進程定義與控制控制信息：操作系統(tǒng)對進程進行調(diào)度管理時用到的信息。主要有進程狀態(tài)、調(diào)度信息、隊列指針、資源占有使用信息等。進程控制塊的組織方式PCB在內(nèi)存中是以表的形式存在的－PCB表。還可以將相同性質(zhì)的進程組織在一張表中，形成多個索引表。有些操作系統(tǒng)將PCB分為常駐內(nèi)存和非常駐內(nèi)存兩部分，如UNIX。1353.2進程定義與控制控制信息：操作系統(tǒng)對進程進行調(diào)度管理時3.2進程定義與控制進程基本狀態(tài)運行態(tài)（Running）：進程已經(jīng)獲得所需資源，并占有CPU就緒態(tài)（Ready）：已經(jīng)獲得所需資源，只等待CPU阻塞態(tài)（Blocked）：也稱為等待態(tài)、掛起態(tài)或睡眠態(tài)等，進程等待某個事件，如等待I/O完成，等待某個資源此外，還可以有新建態(tài)、終止態(tài)。1363.2進程定義與控制進程基本狀態(tài)193.2進程定義與控制進程狀態(tài)的轉(zhuǎn)換新建終止就緒阻塞運行創(chuàng)建完畢時間片用完結(jié)束執(zhí)行選中等待事件等待結(jié)束1373.2進程定義與控制進程狀態(tài)的轉(zhuǎn)換新建終止就緒阻塞運行創(chuàng)建七狀態(tài)進程模型活動掛起事件發(fā)生事件發(fā)生等待事件掛起調(diào)度超時釋放活動掛起138七狀態(tài)進程模型活動掛起事件事件等待掛起調(diào)度超時釋放活動掛起213922PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn......空PCB運行態(tài)就緒態(tài)等待1等待26751015進程控制塊（ProcessControlBlock）140PCB1PCB2PCB3PCB4PCB5PCB6PCB7PC3.2進程定義與控制進程控制－通過原語（Primitive）操作實現(xiàn)原語是指由機器指令構(gòu)成的可完成特定功能的程序段。它是一個機器指令的集合，在執(zhí)行時不能被中斷。多采用屏蔽中斷方法實現(xiàn)。進程控制原語有：進程創(chuàng)建原語（createprimitive）進程撤消原語（destroyprimitive）進程阻塞原語（blockprimitive）進程喚醒原語（wakeupprimitive）進程掛起原語（suspendprimitive）進程激活原語（activeprimitive）1413.2進程定義與控制進程控制－通過原語（Primitive3.2進程定義與控制進程關(guān)系的樹型結(jié)構(gòu)AA22A21A11A2A11423.2進程定義與控制進程關(guān)系的樹型結(jié)構(gòu)AA22A21A113.2進程定義與控制進程關(guān)系的樹型結(jié)構(gòu)主要優(yōu)點資源分配嚴格：子進程僅能分配到父進程所擁有的資源，用完后歸還。進程控制靈活：可根據(jù)需要給進程以不同的控制權(quán)限。進程結(jié)構(gòu)清楚，關(guān)系明確。1433.2進程定義與控制進程關(guān)系的樹型結(jié)構(gòu)263.2進程定義與控制進程特征動態(tài)性：“執(zhí)行”、“計算”、“運行過程”都強調(diào)動態(tài)性，進程的最基本特征。并發(fā)性：進程的重要特征，同時也是操作系統(tǒng)的重要特征。異步性：進程按各自獨立的不可預知的速度向前推進，即進程按異步方式進行，這導致了進程執(zhí)行的不可再現(xiàn)性，因此，操作系統(tǒng)必須采用某些措施來限制各進程推進序列以保證各程序間正常協(xié)調(diào)運行。1443.2進程定義與控制進程特征273.2進程定義與控制進程特征獨立性：進程是一個獨立運行的基本單位，即是一個獨立獲得資源和獨立調(diào)度的單位。制約性：一個進程的執(zhí)行可能依賴其他進程的執(zhí)行結(jié)果。結(jié)構(gòu)性：每個進程有固定結(jié)構(gòu)，包括程序、數(shù)據(jù)和PCB三部分。1453.2進程定義與控制進程特征283.3進程調(diào)度進程調(diào)度屬于低級調(diào)度，就是從就緒隊列中，按照一定的算法選擇某個進程占用CPU。進程調(diào)度時機現(xiàn)運行進程或者因任務完成而正常結(jié)束，或者因錯誤而異常結(jié)束現(xiàn)運行進程因某種原因，比如I/O請求，從運行態(tài)進入阻塞狀態(tài)現(xiàn)運行進程執(zhí)行某種原語操作，如P操作、阻塞原語等，進入阻塞狀態(tài)一個具有更高優(yōu)先數(shù)的進程要求CPU，即已進入就緒隊列分配給該進程運行的時間片已用完1463.3進程調(diào)度進程調(diào)度屬于低級調(diào)度，就是從就緒隊列中，按照3.3進程調(diào)度確定調(diào)度算法的原則：面向系統(tǒng)性能：公平性、較大的吞吐量面向用戶性能：及時性、較短的周轉(zhuǎn)時間1473.3進程調(diào)度確定調(diào)度算法的原則：303.3進程調(diào)度進程調(diào)度算法先來先服務進程調(diào)度算法（FCFS）基于優(yōu)先數(shù)的進程調(diào)度算法：根據(jù)優(yōu)先數(shù)大小確定優(yōu)先級高低，分為靜態(tài)優(yōu)先數(shù)法：進程創(chuàng)建時就規(guī)定好優(yōu)先數(shù)動態(tài)優(yōu)先數(shù)法：優(yōu)先數(shù)在執(zhí)行過程中根據(jù)情況改變，例如UNIX時間片輪轉(zhuǎn)進程調(diào)度算法固定時間片可變時間片多級隊列輪轉(zhuǎn)調(diào)度算法1483.3進程調(diào)度進程調(diào)度算法31多級隊列輪轉(zhuǎn)調(diào)度算法149多級隊列輪轉(zhuǎn)調(diào)度算法323.3進程調(diào)度進程調(diào)度方式 當一個進程正在CPU上運行時，若有一個更為緊迫或更為重要的進程需要進行處理，或者說，如果有更高優(yōu)先數(shù)的進程進入就緒隊列時，如何分配CPU。通常有兩種方式：不可剝奪方式（不可搶占方式， non-preemptive）可剝奪方式（可搶占方式，preemptive）1503.3進程調(diào)度進程調(diào)度方式333.4進程間的相互作用同步：一個進程的某個操作與協(xié)作進程的某個操作之間在時序上有一定的關(guān)系。如果協(xié)作進程的某個操作沒有完成，那么該進程就要等待這個操作完成才能繼續(xù)下去，這種需要相互合作、協(xié)同工作的進程之間的相互關(guān)系稱為進程的同步。臨界資源（獨占資源）：指在一段時間內(nèi)只允許一個進程訪問的資源。互斥：當兩個或兩個以上進程競爭同一臨界資源時，進程間的制約關(guān)系稱為進程的互斥。1513.4進程間的相互作用同步：一個進程的某個操作與協(xié)作進程的3.4進程間的相互作用進程間的同步司機和售票員的同步正常行駛開車到站停車關(guān)車門開車門售票員售票司機1523.4進程間的相互作用進程間的同步正常行駛開車到站停車關(guān)車3.4進程間的相互作用又如，有用戶作業(yè)程序，其形式為：Z=fun1(x)*fun2(y)

其中，fun1(x)和fun2(y)均是一個復雜函數(shù)，為了加快本題的計算速度，可用兩個進程P1、P2各計算一個函數(shù)。進程P2計算fun2(y)，進程P1計算完fun1(x)之后，與進程P2的計算結(jié)果相乘，以獲得最終結(jié)果Z。1533.4進程間的相互作用又如，有用戶作業(yè)程序，其形式為：363.4進程間的相互作用結(jié)束置計算完標志P2計算fun2(y)N計算fun1(x)取用P2計算結(jié)果P1P2算完fun2(y)Y1543.4進程間的相互作用結(jié)束置計算完標志P2計算fun2(y3.4進程間的相互作用進程的互斥互斥使用資源進程A（阻塞）請求資源R進程B釋放資源R請求資源R（使用R）釋放資源RR分配拒絕喚醒1553.4進程間的相互作用進程的互斥進程A（阻塞）請求資源R進

進程間的制約進程間的聯(lián)系進程間同步：相互協(xié)作的進程要共同完成一個任務，它們之間要相互配合，需要在一些動作間進行同步，即一個進程的某個動作與協(xié)作進程的某些動作之間在時序上有一定的關(guān)系。進程間互斥：當兩個或兩個以上的進程競爭同時只能被一個進程使用的資源時，例如競爭使用打印機，需要互斥使用該資源。進程的同步、互斥機制──信號量及P.V操作

156進程間的制約進程間的聯(lián)系進程的同步、互斥機制──信號量及P由于各進程要求共享資源，而有些資源需要互斥使用，因此各進程間競爭使用這些資源，進程的這種關(guān)系為進程的互斥.臨界資源：criticalresource系統(tǒng)中某些資源一次只允許一個進程使用，稱這樣的資源為臨界資源或互斥資源或共享變量臨界資源可以是一些硬件設備（如打印機、磁帶機或繪圖儀等），也可以是進程共享變量、數(shù)據(jù)、隊列、或使用權(quán)限等“有形”或“無形”的資源。進程的互斥（間接制約）mutualexclusion157由于各進程要求共享資源，而有些資源需要互斥使用，因此各進臨界區(qū)（互斥區(qū)）：criticalsection一個程序片段的集合，這些程序片段分散在不同的進程中，對某個共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進行操作.在進程中涉及到臨界資源的程序段叫臨界區(qū).多個進程的臨界區(qū)稱為相關(guān)臨界區(qū).臨界區(qū)（互斥區(qū)）：criticalsection158臨界區(qū)（互斥區(qū)）：criticalsection臨界區(qū)（互臨界區(qū)（criticalsection

）

進程的互斥（間接作用）159臨界區(qū)（criticalsection）進程的互斥4與時間有關(guān)的錯誤由于現(xiàn)在操作系統(tǒng)中的進程是并發(fā)執(zhí)行的，各進程以自己的速度向前推進，所以，運行的順序可能是：

…P1：R1=count；

P2：R2=count；

P1：R1=R1+1；

P1：count=R1；

P2：R2=R2+1；

P2：count=R2；錯誤：P1,P2執(zhí)行的結(jié)果count只加了1160與時間有關(guān)的錯誤由于現(xiàn)在操作系統(tǒng)中的臨界區(qū)161臨界區(qū)44使用互斥區(qū)的原則(1)當有若干個進程要求進入臨界區(qū)時，應使一個進程進入臨界區(qū)，它們不應相互等待而使誰都不能進入，即進程不能無限地停留在等待臨界資源的狀態(tài)。(2)一次只允許一個進程進入臨界區(qū)中，即各進程互斥訪問臨界資源。(3)各進程使用臨界資源的時間是有限的，即任何一個進程都必須在有限的時間內(nèi)釋放所占資源。162使用互斥區(qū)的原則(1)當有若干個進程要求進入臨界區(qū)時，應使一解決進程互斥的方法

解決進程互斥的方法有硬件方法和軟件方法。軟件方法中著名的有Dekker算法和Peterson算法。Dekker算法設置一個整型變量turn，指示允許進入臨界區(qū)的進程標識。假設現(xiàn)有兩個進程P1和P2，當turn的值為1時，P1被允許進入；當turn的值為2時，P2被允許進入。進程退出臨界區(qū)時，要把turn的值改為對方的標識符，就等于允許對方的進入。Peterson算法它除設置整型變量turn外，還為每一個進程設置一個標志，指示該進程是否要求進入臨界區(qū)。假設還是兩個進程，都在等待進入臨界區(qū)。先檢查對方的標志，如果不在臨界區(qū)，則檢查turn的值，以確定是否可以進入。163解決進程互斥的方法解決進程互斥的方法有硬件方法和軟件方3.4進程間的相互作用信號量（semaphore）與P、V操作EdsgarWybeDijkstra（埃德斯加?狄克斯特拉）1972年ACM圖靈獎（ACMTuringAward）獲得者“一個程序的易讀性和易理解性同其中所包含的無條件轉(zhuǎn)移控制的個數(shù)成反比關(guān)系?！碧岢鼋Y(jié)構(gòu)化程序設計思想1643.4進程間的相互作用信號量（semaphore）與P、V3.4進程間的相互作用1653.4進程間的相互作用48信號量及P.V操作信號量（Semaphore）是表示資源的實體，是一個與隊列有關(guān)的整型變量，其值僅能由P、V操作改變。信號量分為：公用信號量和私用信號量。公用信號量:用于實現(xiàn)進程間的互斥，初值通常設為1，它所聯(lián)系的一組并行進程均可對它實施P、V操作；私用信號量用于實現(xiàn)進程間的同步，初始值通常設為0或n，允許擁有它的進程對其實施P操作。166信號量及P.V操作信號量（Semaphore）是表示資源的實信號量：semaphore信號量數(shù)據(jù)結(jié)構(gòu)定義如下：

structsemaphore{ intvalue; pointer_PCBqueue;}信號量說明：

semaphores;167信號量：semaphore信號量數(shù)據(jù)結(jié)構(gòu)定義如下：50P、V操作P(s){s.value=s.value-1;if(s.value<0){

該進程狀態(tài)置為等待狀態(tài);

將該進程的PCB插入相應的等待隊列末尾s.queue;}}168P、V操作P(s)51P、V操作V(s){s.value=s.value+1;if(s.value<=0){

喚醒相應等待隊列s.queue中等待的一個進程改變其狀態(tài)為就緒態(tài)并將其插入就緒隊列

}}P、V操作是原語操作（primitive）原語：是（由若干條機器指令構(gòu)成的）完成某種特定功能的一段程序，具有不可分割性。即原語的執(zhí)行必須是連續(xù)的，不允許被中斷。169P、V