第二章進(jìn)程§2.1進(jìn)程概念§2.2進(jìn)程的狀態(tài)§2.3進(jìn)程控制塊§2.4進(jìn)程控制原語(yǔ)*§2.5進(jìn)程同步§2.6經(jīng)典進(jìn)程同步問(wèn)題§2.1進(jìn)程概念一、順序程序設(shè)計(jì)順序程序(馮諾伊曼)Vonnevman

匈牙利數(shù)學(xué)家1946年

程序是算法的形式化描述，一個(gè)程序的執(zhí)行過(guò)程即一個(gè)“計(jì)算”，即算法的實(shí)現(xiàn)。(1)計(jì)算:

對(duì)某一有限數(shù)據(jù)的集合所施行的，目的在于解決某一問(wèn)題的一組有限操作的集合?！?.1進(jìn)程概念(2)順序執(zhí)行：I1C1O1I2C2O2job1job2順序處理模式計(jì)算中的各個(gè)操作有一定順序，否則無(wú)法正確執(zhí)行。§2.1進(jìn)程概念2.

順序程序的特點(diǎn)：(1).順序性處理機(jī)嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每個(gè)操作必須在下一個(gè)操作開(kāi)始之前結(jié)束。(2).封閉性程序在封閉環(huán)境下運(yùn)行，獨(dú)占全機(jī)資源。封閉性指的是程序一旦開(kāi)始運(yùn)行，其計(jì)算結(jié)果就只取決于程序本身，除了人為地改變機(jī)器的運(yùn)行狀態(tài)或機(jī)器故障以外，沒(méi)有其它因素能夠?qū)Τ绦虻倪\(yùn)行過(guò)程施加影響(3).可再現(xiàn)性程序執(zhí)行的結(jié)果與初始條件有關(guān)，而與執(zhí)行時(shí)間無(wú)關(guān)。即只要程序的初始條件相同，它的執(zhí)行結(jié)果是相同的，不論它在什么時(shí)間執(zhí)行，也不管計(jì)算機(jī)的運(yùn)行速度?！?.1進(jìn)程概念例：(a+b)(c+d)(e/f)t1=a+bt2=c+dt3=e/ft4=t1t2t5=t4–t3–/++abcdSt1t2t3t4t5F二、前趨圖§2.1進(jìn)程概念前趨圖是一個(gè)有向無(wú)循環(huán)圖，用于描述進(jìn)程之間的前后關(guān)系。圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程，乃至一條語(yǔ)句；結(jié)點(diǎn)間的有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序或前趨關(guān)系?！?.1進(jìn)程概念每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。Ii→Ci→Pi和S1→S2→S3圖2-2前趨圖§2.1進(jìn)程概念三.程序的并發(fā)運(yùn)行

系統(tǒng)中有2個(gè)或2個(gè)以上的程序同處于運(yùn)行、但尚未結(jié)束的狀態(tài)，并且次序不是事先確定的。機(jī)器不再是簡(jiǎn)單地順序執(zhí)行一道程序。也就是說(shuō)，當(dāng)一道程序的前一條指令結(jié)束后，系統(tǒng)不一定立即執(zhí)行其后面一條指令，而可能轉(zhuǎn)而執(zhí)行其它程序的某一操作。“執(zhí)行的順序性”被打破了?！?.1進(jìn)程概念例：在系統(tǒng)中有n個(gè)作業(yè)，每個(gè)作業(yè)都有三個(gè)處理步驟，輸入數(shù)據(jù)、處理、輸出，即Ii,Ci,Oi(i=1,2,3,...,n)。

這些作業(yè)系統(tǒng)中執(zhí)行時(shí)是對(duì)時(shí)間的偏序，有些操作必須在其它操作之前執(zhí)行，這是有序的，但有些操作是可以同時(shí)執(zhí)行的。如:I1、C1、O1的執(zhí)行必須嚴(yán)格按照I1，C1，O1的順序，而O1與I2，C1與I2，I3與O1是可以同時(shí)執(zhí)行的?！?.1進(jìn)程概念I(lǐng)1、C1、O1的執(zhí)行必須嚴(yán)格按照I1，C1，O1的順序，而O1與I2，C1與I2,I3與O1是可以同時(shí)執(zhí)行的。I1I2I3C1C2C3O1O2O3t并發(fā)§2.1進(jìn)程概念例：2個(gè)循環(huán)程序A和B，共享變量N。A:while(1)B:while(1){{N=N+1；print(N)；

}N=0；}

A和B并發(fā)執(zhí)行，其計(jì)算結(jié)果與執(zhí)行速度有關(guān)，不唯一，有三種情況（假設(shè)某時(shí)刻N(yùn)值為n）?！?.1進(jìn)程概念(1)N=N+1在print(N)和N=0之前即：N=N+1；print(N)；N=0；則N值分別是：n+1,n+1,0(2)N=N+1在print(N)和N=0之后即：print(N)；N=0；N=N+1；

N值分別是：n,0,1(3)N=N+1在print(N)和N=0之間即：print(N)；N=N+1；N=0；

N值分別是：n,n+1,0§2.1進(jìn)程概念程序并發(fā)執(zhí)行，失去了封閉性，雖然執(zhí)行環(huán)境和初始條件相同，但其計(jì)算結(jié)果與并發(fā)程序的執(zhí)行速度有關(guān)，從而失去了可再現(xiàn)性，有可能發(fā)生“與時(shí)間有關(guān)的錯(cuò)誤”。因而，必須采取某種措施，使得并發(fā)程序能夠保持其“可再現(xiàn)性”。程序的運(yùn)行，并不僅僅是一些代碼的執(zhí)行，還包括執(zhí)行環(huán)境（與每個(gè)正在執(zhí)行的程序相關(guān)的一組寄存器、程序計(jì)數(shù)器、變量的當(dāng)前值等等）?！?.1進(jìn)程概念特征：（1）不可再現(xiàn)性同一程序的多次執(zhí)行，雖然執(zhí)行環(huán)境和初始條件相同，但得到的結(jié)果各不相同。并發(fā)程序執(zhí)行的結(jié)果與其執(zhí)行的相對(duì)速度有關(guān)，是不確定的（2）間斷性

并發(fā)程序之間存在相互制約關(guān)系，導(dǎo)致它們都具有“執(zhí)行-暫停-執(zhí)行”活動(dòng)規(guī)律?！?.1進(jìn)程概念（3）資源共享

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

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

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

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

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

（5）程序和計(jì)算不再對(duì)應(yīng)

（計(jì)算：一個(gè)程序的執(zhí)行）

四、進(jìn)程的引入§2.1進(jìn)程概念進(jìn)程的概念是操作系統(tǒng)中最基本、最重要的概念。它是在多道程序系統(tǒng)出現(xiàn)后，為了刻劃系統(tǒng)內(nèi)部出現(xiàn)的情況，描述系統(tǒng)內(nèi)部各作業(yè)的活動(dòng)規(guī)律而引進(jìn)的一個(gè)新的概念。程序在多道程序環(huán)境中的并發(fā)運(yùn)行，是一件復(fù)雜的事情。經(jīng)過(guò)努力，研究OS的專(zhuān)家們發(fā)展了“進(jìn)程”這一模式，使并發(fā)容易實(shí)現(xiàn)。60年代初，MIT首先提出“進(jìn)程”這一計(jì)算機(jī)術(shù)語(yǔ)。為使程序在多道程序環(huán)境下能并發(fā)執(zhí)行，并能對(duì)并發(fā)執(zhí)行的程序加以控制，OS將用戶(hù)提交運(yùn)行的程序先組織成“進(jìn)程”，再投入運(yùn)行。OS具體做法是：當(dāng)用戶(hù)向OS提交一個(gè)程序要求運(yùn)行，OS即為提交運(yùn)行的程序構(gòu)筑一個(gè)稱(chēng)為“進(jìn)程控制塊”的數(shù)據(jù)結(jié)構(gòu)，其中存放了該程序執(zhí)行過(guò)程中的動(dòng)態(tài)變化信息（程序和數(shù)據(jù)的地址、程序運(yùn)行時(shí)CPU的環(huán)境信息等等）。進(jìn)程的定義§2.1進(jìn)程概念

進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次可以并發(fā)執(zhí)行的運(yùn)行活動(dòng)。進(jìn)程的概念來(lái)自于麻省理工的MULTICS、IBM的

TSS/360，在IBM的OS/360/370系統(tǒng)中也曾叫過(guò)任務(wù)（task)。§2.1進(jìn)程概念行為的一個(gè)規(guī)則叫做程序，程序在處理機(jī)上執(zhí)行時(shí)所發(fā)生的活動(dòng)稱(chēng)為進(jìn)程（Dijkstra)。進(jìn)程是這樣的計(jì)算部分，它是可以和其它計(jì)算并行的一個(gè)計(jì)算。(Donovan)進(jìn)程（有時(shí)稱(chēng)為任務(wù)）是一個(gè)程序與其數(shù)據(jù)一道通過(guò)處理機(jī)的執(zhí)行所發(fā)生的活動(dòng)。（Alan.C.Shaw)進(jìn)程是執(zhí)行中的程序。（KenThompsonandDennisRitchie)教材上給出的進(jìn)程的定義：P30

進(jìn)程，是進(jìn)程實(shí)體的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位?？梢詮?個(gè)方面來(lái)描述進(jìn)程

進(jìn)程是程序的一次運(yùn)行活動(dòng)進(jìn)程的運(yùn)行活動(dòng)是建立在某個(gè)數(shù)據(jù)集合之上的進(jìn)程要在獲得資源的基礎(chǔ)上從事自己的運(yùn)行活動(dòng)進(jìn)程同程序的區(qū)別與聯(lián)系§2.1進(jìn)程概念程序是指令的集合，是靜態(tài)的概念。進(jìn)程是程序在處理機(jī)上的一次執(zhí)行的過(guò)程，是動(dòng)態(tài)的概念。程序的存在是永久的。程序可以作為軟件資料長(zhǎng)期保存。進(jìn)程的存在是暫時(shí)的。進(jìn)程是有生命周期的?！耙淮芜\(yùn)行活動(dòng)”，誕生(建立)、死亡(撤消)。進(jìn)程＝程序+數(shù)據(jù)+PCB(進(jìn)程控制塊，processcontrolblock)，即進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序地執(zhí)行時(shí)所發(fā)生的活動(dòng)。進(jìn)程是一個(gè)獨(dú)立的運(yùn)行單位，能與其它進(jìn)程并行（并發(fā)）活動(dòng)。而程序則不是。進(jìn)程是競(jìng)爭(zhēng)計(jì)算機(jī)系統(tǒng)有限資源的基本單位，也是進(jìn)行處理機(jī)調(diào)度的基本單位。一個(gè)程序可以作為多個(gè)進(jìn)程的運(yùn)行程序，一個(gè)進(jìn)程也可以運(yùn)行多個(gè)程序?！?.1進(jìn)程概念程序進(jìn)程唱歌的曲譜或音樂(lè)樂(lè)器的樂(lè)譜演出或演奏劇本演出菜譜烹調(diào)實(shí)例§2.1進(jìn)程概念舉例做蛋糕程序：食譜數(shù)據(jù)：原料（雞蛋、面粉、糖等）CPU：廚師進(jìn)程：廚師閱讀食譜，將原料加工成蛋糕的一系列活動(dòng)的總和做到一半，他兒子玩耍受傷進(jìn)來(lái)，廚師記錄下他照著食譜做到第幾步（保存當(dāng)前進(jìn)程狀態(tài)等現(xiàn)場(chǎng)信息）；然后找出急救手冊(cè)（調(diào)進(jìn)另一道程序），按其指示處理傷情?！?.1進(jìn)程概念關(guān)鍵思想：一個(gè)進(jìn)程是某種類(lèi)型的一個(gè)活動(dòng)，它包括程序、輸入\輸出、狀態(tài)。單個(gè)CPU被多個(gè)進(jìn)程共享。CPU遵循某種調(diào)度算法，以決定何時(shí)暫停一個(gè)進(jìn)程的工作，并轉(zhuǎn)而為另一個(gè)進(jìn)程提供服務(wù)。程序：急救手冊(cè)CPU：廚師進(jìn)程：廚師閱讀急救手冊(cè)，實(shí)施救治的一系列活動(dòng)的總和（該進(jìn)程優(yōu)先級(jí)別高，單CPU）這里CPU從一個(gè)進(jìn)程切換到另一個(gè)進(jìn)程，每個(gè)進(jìn)程都有各自的程序。廚師處理完傷情，又去做蛋糕，是從他離開(kāi)的那一步繼續(xù)做下去。四、進(jìn)程的五個(gè)基本特征§2.1進(jìn)程概念動(dòng)態(tài)性：進(jìn)程是程序在并發(fā)系統(tǒng)內(nèi)的一次執(zhí)行，一個(gè)進(jìn)程有一個(gè)從產(chǎn)生到消失的生命期；并發(fā)性：正是為了描述程序在并發(fā)系統(tǒng)內(nèi)執(zhí)行的動(dòng)態(tài)特性才引入了進(jìn)程，沒(méi)有并發(fā)就沒(méi)有進(jìn)程；獨(dú)立性：每個(gè)進(jìn)程的程序都是相對(duì)獨(dú)立的順序程序，可以按照自己的方向和速度獨(dú)立地向前推進(jìn)；制約性：進(jìn)程之間的相互制約，主要表現(xiàn)在互斥地使用資源和相關(guān)進(jìn)程之間必要的同步和通訊；結(jié)構(gòu)性：進(jìn)程

=PCB+程序+數(shù)據(jù)集合。§2.1進(jìn)程概念動(dòng)態(tài)性是進(jìn)程最基本的特征表現(xiàn)為：由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，因得不到資源而暫停執(zhí)行，由撤消而消亡。有一定的生命期，動(dòng)態(tài)存在。（與程序比較）1、動(dòng)態(tài)性§2.1進(jìn)程概念并發(fā)性是進(jìn)程的重要特征，也是OS的重要特征。多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中，在一段時(shí)間內(nèi)同時(shí)處于運(yùn)行狀態(tài)。并發(fā)處理的真正含義是：把系統(tǒng)作為一個(gè)整體來(lái)觀察，則在任一時(shí)刻有若干進(jìn)程存在于系統(tǒng)的內(nèi)部，這些進(jìn)程都處在其起點(diǎn)和終點(diǎn)之間。我們把所有這些進(jìn)程都看成是正在系統(tǒng)中運(yùn)行著。2、并發(fā)性§2.1進(jìn)程概念進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行的基本單位，也是系統(tǒng)中獨(dú)立獲得資源和獨(dú)立調(diào)度的基本單位。沒(méi)有建立進(jìn)程的程序，不能作為獨(dú)立單位參加運(yùn)行。3、獨(dú)立性§2.1進(jìn)程概念進(jìn)程在系統(tǒng)中按異步方式運(yùn)行，即進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。該特征導(dǎo)致程序執(zhí)行的不可再現(xiàn)性。因此，各個(gè)進(jìn)程也就在不可預(yù)測(cè)的次序中前進(jìn)。操作系統(tǒng)外部表現(xiàn)出來(lái)的不確定性，就是內(nèi)部動(dòng)作序列不可預(yù)測(cè)、不易復(fù)現(xiàn)的反應(yīng)。4、制約性（互斥性）§2.1進(jìn)程概念4、結(jié)構(gòu)性進(jìn)程實(shí)體由程序段、數(shù)據(jù)段、進(jìn)程控制塊（PCB）三者組成。程序：描述了進(jìn)程所要完成的功能數(shù)據(jù)集合：程序運(yùn)行時(shí)所需的數(shù)據(jù)和工作區(qū)。程序和數(shù)據(jù)集合是進(jìn)程存在的物質(zhì)基礎(chǔ)PCB：包含進(jìn)程的描述信息和控制信息（是進(jìn)程動(dòng)態(tài)特性的集中體現(xiàn)）§2.1進(jìn)程概念OS必須交替執(zhí)行多個(gè)進(jìn)程，以便最大程度的使用CPU，同時(shí)提供合理的響應(yīng)時(shí)間OS必須將資源分配給進(jìn)程，同時(shí)避免死鎖OS必須支持進(jìn)程間通信以及用戶(hù)進(jìn)程創(chuàng)建OS對(duì)進(jìn)程的要求§2.1進(jìn)程概念作業(yè)調(diào)度用戶(hù)登錄由OS創(chuàng)建，用以向一用戶(hù)提供服務(wù)(如：打印文件)由已存在的一進(jìn)程創(chuàng)建一個(gè)用戶(hù)程序可創(chuàng)建成多個(gè)進(jìn)程進(jìn)程何時(shí)創(chuàng)建?§2.1進(jìn)程概念批處理作業(yè)發(fā)出暫停（Halt）指令用戶(hù)退出登錄出錯(cuò)及失敗因素缺少內(nèi)存、存儲(chǔ)器出界、保護(hù)性出錯(cuò)（寫(xiě)只讀文件）、算術(shù)錯(cuò)、超出時(shí)間、

進(jìn)程等待超過(guò)對(duì)某事件的最大值、無(wú)效指令（如：試圖執(zhí)行數(shù)據(jù)）、特權(quán)指令進(jìn)程何時(shí)終止?外界干預(yù)操作系統(tǒng)干預(yù)如：當(dāng)死鎖發(fā)生時(shí)父進(jìn)程請(qǐng)求終止某一子進(jìn)程父進(jìn)程終止，所以子進(jìn)程也終止進(jìn)程的狀態(tài)及變化§2.2進(jìn)程的狀態(tài)進(jìn)程有著“執(zhí)行－暫停－執(zhí)行”的活動(dòng)規(guī)律，一般說(shuō)來(lái)一個(gè)進(jìn)程不是自始至終一口氣運(yùn)行到底的。各進(jìn)程相互制約，當(dāng)使它暫停的原因消失后，它又可準(zhǔn)備運(yùn)行。因此進(jìn)程有多種狀態(tài)?！?.2進(jìn)程的狀態(tài)(1)、就緒狀態(tài)（Ready)

存在于處理機(jī)調(diào)度隊(duì)列中的那些進(jìn)程，它們已經(jīng)準(zhǔn)備就緒，一旦得到CPU，就立即可以運(yùn)行，這些進(jìn)程所取的狀態(tài)為就緒狀態(tài)。（有多個(gè)進(jìn)程處于此狀態(tài)）(2)、運(yùn)行狀態(tài)(Running）

當(dāng)進(jìn)程由調(diào)度/分派程序分派后，得到CPU控制權(quán)，它的程序正在運(yùn)行，該進(jìn)程所處的狀態(tài)為運(yùn)行狀態(tài)。（在系統(tǒng)中，總只有一個(gè)進(jìn)程處于此狀態(tài)）(3)、阻塞狀態(tài)（Blocked)

若一個(gè)進(jìn)程正在等待某個(gè)事件的發(fā)生（如等待I/O的完成），而暫停執(zhí)行，這時(shí)，即使給它CPU時(shí)間，它也無(wú)法執(zhí)行，則稱(chēng)該進(jìn)程處于等待狀態(tài)。又稱(chēng)為等待(Wait)狀態(tài)。1、進(jìn)程的3種基本狀態(tài)§2.2進(jìn)程的狀態(tài)阻塞（不能占用CPU）就緒（尚未占用CPU）運(yùn)行（正在占用CPU）資源不足或等待某事件發(fā)生得到資源或某事件發(fā)生時(shí)間片到調(diào)度選中進(jìn)入進(jìn)入完成執(zhí)行2、進(jìn)程的狀態(tài)模型§2.2進(jìn)程的狀態(tài)就緒→運(yùn)行處于就緒狀態(tài)的進(jìn)程，當(dāng)OS的進(jìn)程調(diào)度程序?yàn)槠浞峙淞薈PU，該進(jìn)程狀態(tài)就變換成執(zhí)行狀態(tài)，占有了CPU。運(yùn)行→阻塞處于執(zhí)行狀態(tài)的進(jìn)程由于某事件的發(fā)生而無(wú)法執(zhí)行（請(qǐng)求I/O、申請(qǐng)緩沖區(qū)、程序故障等），則進(jìn)程狀態(tài)就變換成阻塞狀態(tài)。3、進(jìn)程的狀態(tài)轉(zhuǎn)換§2.2進(jìn)程的狀態(tài)運(yùn)行→就緒被轉(zhuǎn)換進(jìn)程本身運(yùn)行條件仍然是滿足的，只是由于某種原因被暫時(shí)剝奪（搶占）。在分時(shí)系統(tǒng)中，則是分配給的時(shí)間片耗盡；在實(shí)時(shí)系統(tǒng)中，則是系統(tǒng)中一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒。阻塞→就緒服務(wù)完成、事件來(lái)到等。解除了阻塞原因?？偸怯赏饨缡录鸬摹１蛔枞倪M(jìn)程必須經(jīng)過(guò)就緒才能被重新調(diào)度。§2.2進(jìn)程的狀態(tài)4、進(jìn)程的其它狀態(tài)掛起狀態(tài)引入掛起狀態(tài)的原因

終端用戶(hù)的請(qǐng)求。(2)父進(jìn)程請(qǐng)求。(3)負(fù)荷調(diào)節(jié)的需要。(4)操作系統(tǒng)的需要。具有掛起狀態(tài)的進(jìn)程狀態(tài)圖思考1．如果系統(tǒng)中有N個(gè)進(jìn)程，處于運(yùn)行狀態(tài)的進(jìn)程最多幾個(gè)，最少幾個(gè)；就緒進(jìn)程最多幾個(gè)最少幾個(gè)；阻塞進(jìn)程最多幾個(gè)，最少幾個(gè)？2.有沒(méi)有這樣的狀態(tài)轉(zhuǎn)換？ 等待—運(yùn)行；就緒—等待3.一個(gè)狀態(tài)轉(zhuǎn)換的發(fā)生，是否一定導(dǎo)致另一個(gè)轉(zhuǎn)換發(fā)生，列出所有的可能§2.3進(jìn)程控制塊1.進(jìn)程控制塊PCB(ProcessControlBlock)的作用進(jìn)程控制塊的作用是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序(含數(shù)據(jù))，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f(shuō)，OS是根據(jù)PCB來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的?！?.3進(jìn)程控制塊進(jìn)程控制塊存放進(jìn)程的管理和控制信息的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為進(jìn)程控制塊。它是進(jìn)程管理和控制的最重要的數(shù)據(jù)結(jié)構(gòu)，在創(chuàng)建時(shí)，建立PCB，并伴隨進(jìn)程運(yùn)行的全過(guò)程，直到進(jìn)程撤消而撤消。PCB就象我們的戶(hù)口。2.進(jìn)程控制塊中的信息

1)進(jìn)程標(biāo)識(shí)符進(jìn)程標(biāo)識(shí)符用于惟一地標(biāo)識(shí)一個(gè)進(jìn)程。一個(gè)進(jìn)程通常有兩種標(biāo)識(shí)符：

(1)內(nèi)部標(biāo)識(shí)符。在所有的操作系統(tǒng)中，都為每一個(gè)進(jìn)程賦予一個(gè)惟一的數(shù)字標(biāo)識(shí)符，它通常是一個(gè)進(jìn)程的序號(hào)。設(shè)置內(nèi)部標(biāo)識(shí)符主要是為了方便系統(tǒng)使用。

(2)外部標(biāo)識(shí)符。它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶(hù)(進(jìn)程)在訪問(wèn)該進(jìn)程時(shí)使用。為了描述進(jìn)程的家族關(guān)系，還應(yīng)設(shè)置父進(jìn)程標(biāo)識(shí)及子進(jìn)程標(biāo)識(shí)。此外，還可設(shè)置用戶(hù)標(biāo)識(shí)，以指示擁有該進(jìn)程的用戶(hù)。

2)處理機(jī)狀態(tài)處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的。①通用寄存器，又稱(chēng)為用戶(hù)可視寄存器，它們是用戶(hù)程序可以訪問(wèn)的，用于暫存信息，在大多數(shù)處理機(jī)中，有8~32個(gè)通用寄存器，在RISC結(jié)構(gòu)的計(jì)算機(jī)中可超過(guò)100個(gè)；②指令計(jì)數(shù)器，其中存放了要訪問(wèn)的下一條指令的地址；③程序狀態(tài)字PSW，其中含有狀態(tài)信息，如條件碼、執(zhí)行方式、中斷屏蔽標(biāo)志等；④用戶(hù)棧指針，指每個(gè)用戶(hù)進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的系統(tǒng)棧，用于存放過(guò)程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。

3)進(jìn)程調(diào)度信息在PCB中還存放一些與進(jìn)程調(diào)度和進(jìn)程對(duì)換有關(guān)的信息，包括：①進(jìn)程狀態(tài)，指明進(jìn)程的當(dāng)前狀態(tài)，作為進(jìn)程調(diào)度和對(duì)換時(shí)的依據(jù)；②進(jìn)程優(yōu)先級(jí)，用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù)，優(yōu)先級(jí)高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī)；③進(jìn)程調(diào)度所需的其它信息，它們與所采用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待CPU的時(shí)間總和、進(jìn)程已執(zhí)行的時(shí)間總和等；④事件，是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。

4)進(jìn)程控制信息進(jìn)程控制信息包括：①程序和數(shù)據(jù)的地址，是指進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地(首)址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從PCB中找到其程序和數(shù)據(jù)；②進(jìn)程同步和通信機(jī)制，指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制，如消息隊(duì)列指針、信號(hào)量等，它們可能全部或部分地放在PCB中；③資源清單，是一張列出了除CPU以外的、進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單；④鏈接指針，它給出了本進(jìn)程(PCB)所在隊(duì)列中的下一個(gè)進(jìn)程的PCB的首地址?！?.3進(jìn)程控制塊3.進(jìn)程控制塊的組織方式一、原語(yǔ)§2.4進(jìn)程控制原語(yǔ)原語(yǔ)本身不是一條機(jī)器指令而是由若干條指令組成，因此可理解為機(jī)器指令的擴(kuò)充。在對(duì)進(jìn)程的管理中完成某種特定功能，為進(jìn)程有效管理提供的若干基本操作。一般在執(zhí)行中一次完成不能被打斷，因此設(shè)計(jì)的原語(yǔ)不能太長(zhǎng)。在許多機(jī)器中為了實(shí)現(xiàn)上的方便，規(guī)定在執(zhí)行原語(yǔ)操作的要屏蔽中斷，以保證原語(yǔ)操作的不可分割性。§2.4進(jìn)程控制原語(yǔ)用于進(jìn)程控制的原語(yǔ)有：(1)創(chuàng)建進(jìn)程原語(yǔ) (2)撤消進(jìn)程原語(yǔ)

(3)掛起進(jìn)程原語(yǔ) (4)解掛進(jìn)程原語(yǔ)

(5)阻塞進(jìn)程原語(yǔ) (6)喚醒進(jìn)程原語(yǔ)

(7)調(diào)度進(jìn)程運(yùn)行原語(yǔ) (8)改變優(yōu)先級(jí)原語(yǔ)

為了對(duì)系統(tǒng)中的進(jìn)程進(jìn)行有效的管理，通常系統(tǒng)都提供了若干基本的操作，這些操作通常被稱(chēng)為原語(yǔ)。二、進(jìn)程創(chuàng)建原語(yǔ)§2.4進(jìn)程控制原語(yǔ)OS發(fā)現(xiàn)有創(chuàng)建進(jìn)程的要求，便調(diào)用進(jìn)程創(chuàng)建原語(yǔ)，創(chuàng)建新進(jìn)程。申請(qǐng)空白PCB（OS為新進(jìn)程分配唯一的內(nèi)部標(biāo)識(shí)符，即數(shù)字標(biāo)識(shí)符，從PCB集合中取得一空白PCB）為新進(jìn)程分配資源（為新進(jìn)程的程序和數(shù)據(jù)分配必要的內(nèi)存空間）初始化PCB（將標(biāo)識(shí)符填入PCB；將進(jìn)程狀態(tài)設(shè)置為就緒；等等）將新進(jìn)程插入就緒隊(duì)列三、進(jìn)程終止原語(yǔ)§2.4進(jìn)程控制原語(yǔ)一旦進(jìn)程運(yùn)行結(jié)束，或異常終止，或外界干預(yù)，OS調(diào)用進(jìn)程終止原語(yǔ)。依據(jù)進(jìn)程標(biāo)識(shí)符，從PCB中取出進(jìn)程狀態(tài)；若處于執(zhí)行狀態(tài)，中止執(zhí)行，OS另行調(diào)度一新進(jìn)程進(jìn)入執(zhí)行狀態(tài)；釋放進(jìn)程所擁有的全部資源；將該進(jìn)程從所在隊(duì)列中移出?！?.4進(jìn)程控制原語(yǔ)處于執(zhí)行狀態(tài)的進(jìn)程，當(dāng)有事件發(fā)生而無(wú)法繼續(xù)執(zhí)行下去，便調(diào)用阻塞原語(yǔ)block()把自己阻塞。阻塞是進(jìn)程自身的主動(dòng)行動(dòng)。進(jìn)程立即停止執(zhí)行；把PCB中現(xiàn)行狀態(tài)改為阻塞；插入相應(yīng)阻塞隊(duì)列；轉(zhuǎn)OS調(diào)度進(jìn)程，把CPU分配給另一就緒進(jìn)程。并進(jìn)行切換（保存舊進(jìn)程環(huán)境，恢復(fù)新進(jìn)程環(huán)境）四、進(jìn)程阻塞原語(yǔ)§2.4進(jìn)程控制原語(yǔ)當(dāng)被阻塞進(jìn)程期待事件出現(xiàn)時(shí)，由有關(guān)進(jìn)程調(diào)用喚醒進(jìn)程原語(yǔ)wakeup()將阻塞進(jìn)程喚醒。將阻塞進(jìn)程從等待隊(duì)列中移出；將PCB中現(xiàn)行狀態(tài)由阻塞改為就緒；把該進(jìn)程插入就緒隊(duì)列。五、進(jìn)程喚醒原語(yǔ)§2.4進(jìn)程控制原語(yǔ)一旦進(jìn)程運(yùn)行結(jié)束，或異常終止，或外界干預(yù)，OS調(diào)用進(jìn)程終止原語(yǔ)。依據(jù)進(jìn)程標(biāo)識(shí)符，從PCB中取出進(jìn)程狀態(tài)；若處于執(zhí)行狀態(tài)，中止執(zhí)行，OS另行調(diào)度一新進(jìn)程進(jìn)入執(zhí)行狀態(tài)；釋放進(jìn)程所擁有的全部資源；將該進(jìn)程從所在隊(duì)列中移出。六、進(jìn)程終止原語(yǔ)§2.4進(jìn)程控制原語(yǔ)請(qǐng)求系統(tǒng)服務(wù)。執(zhí)行狀態(tài)的進(jìn)程請(qǐng)求OS提供服務(wù)（如打印機(jī)），OS不能立即滿足，該進(jìn)程阻塞。只有等其它進(jìn)程釋放打印機(jī)后，再由釋放者喚醒它。啟動(dòng)某種操作。執(zhí)行狀態(tài)進(jìn)程啟動(dòng)I/O設(shè)備，須在完成指定I/O操作后才能繼續(xù)執(zhí)行，則必先阻塞。等I/O完成，由OS喚醒它。引起阻塞和喚醒的事件：相互合作的進(jìn)程間數(shù)據(jù)未到達(dá)。2個(gè)進(jìn)程相互合作，一進(jìn)程需獲得另一進(jìn)程的數(shù)據(jù)才能運(yùn)行，數(shù)據(jù)未到，只有等待。當(dāng)數(shù)據(jù)可提供時(shí)，由另一進(jìn)程喚醒它。無(wú)新工作可做系統(tǒng)中有些特定功能的進(jìn)程，每當(dāng)它們完成任務(wù)后都阻塞自己，等待下一次任務(wù)將其喚醒?！?.5進(jìn)程間的同步與互斥一、并發(fā)程序間的制約關(guān)系多個(gè)并發(fā)進(jìn)程間的制約關(guān)系，有以下2種：資源共享關(guān)系相互合作關(guān)系§2.5進(jìn)程間的同步與互斥多個(gè)進(jìn)程共處于一個(gè)系統(tǒng)中，共享系統(tǒng)中資源?；コ猓憾鄠€(gè)并發(fā)進(jìn)程共享系統(tǒng)資源，一些資源要求排它性使用，即互斥使用，諸進(jìn)程為競(jìng)爭(zhēng)這一類(lèi)資源而發(fā)生的相互制約關(guān)系。是一種特殊的同步關(guān)系。臨界資源

cr(criticalresource)：一次僅允許一個(gè)進(jìn)程使用的資源。進(jìn)程之間大量存在著互斥關(guān)系，這是由進(jìn)程競(jìng)爭(zhēng)使用臨界資源而引起的。OS的任務(wù)是：保證諸進(jìn)程互斥地訪問(wèn)臨界資源。為此，OS不允許進(jìn)程直接使用系統(tǒng)資源，而要經(jīng)OS統(tǒng)一調(diào)配。1、資源共享關(guān)系§2.5進(jìn)程間的同步與互斥例：進(jìn)程p1、p2都需要使用打印機(jī)，如果讓它們同時(shí)使用，則兩個(gè)進(jìn)程的輸出將交織在一起，打印結(jié)果根本無(wú)法使用。為此OS規(guī)定，一進(jìn)程使用打印機(jī)前，先要提出申請(qǐng)，一旦系統(tǒng)將打印機(jī)分配給它就由它獨(dú)占使用，直至使用完畢；在它使用期間，其它申請(qǐng)使用打印機(jī)的進(jìn)程則必須等待。很多物理設(shè)備都屬此類(lèi)臨界資源。例如：繪圖儀等。許多軟件資源，如變量、數(shù)據(jù)、表格、隊(duì)列等也可以由若干個(gè)進(jìn)程共享使用，也屬臨界資源?！?.5進(jìn)程間的同步與互斥臨界區(qū)cs(criticalsection)：進(jìn)程中對(duì)臨界資源進(jìn)行操作的程序代碼段。(注意：一臨界區(qū)是對(duì)某一資源而言)。例：進(jìn)程A和進(jìn)程B共享系統(tǒng)中公共變量m。進(jìn)程A：x=1;y=2;m=x;x=y;y=m;cout<<“A:”<<x<<y;進(jìn)程B：k=3;l=4;m=k;k=l;l=m;cout<<“B:”<<k<<l;臨界區(qū)臨界區(qū)§2.5進(jìn)程同步進(jìn)程A和進(jìn)程B都使用中間變量m，由于CPU的調(diào)度是隨機(jī)的，兩進(jìn)程的執(zhí)行順序可以多種多樣：

(1).進(jìn)程A→進(jìn)程B

(2).進(jìn)程B→進(jìn)程A

(3).兩進(jìn)程交替，可得到許多種不同結(jié)果§2.5進(jìn)程同步(1).進(jìn)程A→進(jìn)程B，運(yùn)行結(jié)果：

A:2,1B:4,3

(2).進(jìn)程B→進(jìn)程A，運(yùn)行結(jié)果：

B:4,3A:2,1第(1)、(2)種執(zhí)行順序符合我們的預(yù)期?！?.5進(jìn)程同步(3).兩進(jìn)程交替，有許多種情況。如不能保證對(duì)臨界區(qū)執(zhí)行上的完整性，就獲得錯(cuò)誤的結(jié)果。如執(zhí)行順序?yàn)椋哼M(jìn)程A：x=1;y=2;m=x;

進(jìn)程B：k=3;l=4;m=k;k=l;

進(jìn)程A：x=y;y=m;printf(“A:%d,%d”,x,y);

進(jìn)程B：l=m;printf(“B:%d,%d”,k,l);則運(yùn)行結(jié)果為：

A:2,3B:4,3顯然結(jié)果并非我們預(yù)期的。上述例子有可能產(chǎn)生“與時(shí)間有關(guān)的錯(cuò)誤”的原因，是與訪問(wèn)公用變量的時(shí)間有關(guān)。§2.5進(jìn)程間的同步與互斥分析：只要保證對(duì)臨界區(qū)（針對(duì)公共變量m的）執(zhí)行上的完整性，就可獲得預(yù)期的結(jié)果。不論硬件臨界資源還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地訪問(wèn)它們。顯然，每個(gè)進(jìn)程在進(jìn)入到臨界區(qū)之前，必須先檢查臨界資源是否被占用？結(jié)論：實(shí)現(xiàn)進(jìn)程互斥的做法，是由OS來(lái)協(xié)調(diào)競(jìng)爭(zhēng)各方對(duì)互斥資源的使用。每個(gè)進(jìn)程在進(jìn)入到臨界區(qū)之前，必須先檢查臨界資源是否被占用，以保證諸進(jìn)程互斥地訪問(wèn)臨界資源§2.5進(jìn)程間的同步與互斥使用臨界區(qū)的原則：

有空讓進(jìn)：當(dāng)無(wú)進(jìn)程在臨界區(qū)時(shí)，任何有權(quán)使用臨界區(qū)的進(jìn)程可進(jìn)入

無(wú)空等待：不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入臨界區(qū)多中擇一：當(dāng)沒(méi)有進(jìn)程在臨界區(qū)，而同時(shí)有多個(gè)進(jìn)程要求進(jìn)入臨界區(qū)，只能讓其中之一進(jìn)入臨界區(qū)，其它進(jìn)程必須等待有限等待：任何進(jìn)入臨界區(qū)的要求，應(yīng)在有限的時(shí)間內(nèi)得到滿足讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPU，以使其它進(jìn)程有機(jī)會(huì)得到CPU的使用權(quán)§2.5進(jìn)程間的同步與互斥系統(tǒng)中多個(gè)進(jìn)程之間存在某種時(shí)序關(guān)系，需要相互合作，共同完成一項(xiàng)任務(wù)。同步：多個(gè)并發(fā)進(jìn)程的相關(guān)進(jìn)程在執(zhí)行速度上的制約。OS的任務(wù)是：使它們同步，保證其在執(zhí)行次序上的協(xié)調(diào)，不會(huì)出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤。2、相互合作關(guān)系§2.5進(jìn)程間的同步與互斥例：一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于阻塞狀態(tài)，獲得消息后被喚醒進(jìn)入就緒狀態(tài)。單緩沖Buffer計(jì)算進(jìn)程將處理好數(shù)據(jù)放入Buffer打印進(jìn)程從Buffer中取走已處理數(shù)據(jù)§2.5進(jìn)程間的同步與互斥進(jìn)程互斥的解決具體方法:軟件（用編程解決，但常常忙等待）硬件（當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū),就屏蔽所有中斷，但成本高）二、進(jìn)程互斥的解決§2.5進(jìn)程間的同步與互斥進(jìn)程互斥的軟件方法其基本思路是在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志，如果已有進(jìn)程在臨界區(qū)，則在進(jìn)入?yún)^(qū)通過(guò)循環(huán)檢查進(jìn)行等待；在退出區(qū)修改標(biāo)志其中的主要問(wèn)題是設(shè)置什么標(biāo)志和如何檢查標(biāo)志軟件解法(1)free:表示臨界區(qū)標(biāo)志

true:有進(jìn)程在臨界區(qū)

false:無(wú)進(jìn)程在臨界區(qū)(初值)

while(free);

free=false;

臨界區(qū)

free=true;§2.5進(jìn)程間的同步與互斥軟件解法的缺點(diǎn)：

1.忙等待

2.實(shí)現(xiàn)過(guò)于復(fù)雜，需要高的編程技巧§2.5進(jìn)程間的同步與互斥硬件解法“開(kāi)關(guān)中斷”指令進(jìn)入臨界區(qū)前執(zhí)行：執(zhí)行“關(guān)中斷”指令離開(kāi)臨界區(qū)后執(zhí)行：執(zhí)行“開(kāi)中斷”指令缺點(diǎn)：(1)關(guān)閉中斷為特權(quán)指令，給用戶(hù)使用可能導(dǎo)致嚴(yán)重后果，如忘記開(kāi)中斷了，則使系統(tǒng)無(wú)法運(yùn)行。(2)僅適合單CPU系統(tǒng)，而在多CPU系統(tǒng)中，其它CPU上的進(jìn)程仍可能進(jìn)入CS段，而導(dǎo)致競(jìng)爭(zhēng)狀態(tài)的出現(xiàn)?！?.5進(jìn)程間的同步與互斥

信號(hào)量是荷蘭的計(jì)算機(jī)科學(xué)家Dijkstra于1965年提出的，也是最早的同步方法。所謂信號(hào)量：是一個(gè)僅能由同步原語(yǔ)對(duì)其進(jìn)行操作的整型變量。用變量S表示。Dijkstra將這兩個(gè)同步原語(yǔ)命名為“P操作（荷蘭語(yǔ)proberen測(cè)試）”，“V操作”。分別表示為wait(S)和signal(S)。一、信號(hào)量§2.5進(jìn)程間的同步與互斥

intS；

S=資源初值；

1.整型信號(hào)量wait(S):whileS<=0dono_op;S--;signal(S):S++;2、記錄型信號(hào)量semaphore是一個(gè)數(shù)據(jù)結(jié)構(gòu),結(jié)構(gòu)型定義如下：

strucsemaphore{

intvalue; pointer_PCBqueue;}信號(hào)量說(shuō)明：

semaphores;§2.5進(jìn)程間的同步與互斥Wait(s)操作Wait(s){

s.value=s.value--;if(s.value<0){

該進(jìn)程狀態(tài)置為等待狀態(tài)將該進(jìn)程的PCB插入相應(yīng)的等待隊(duì)列末尾s.queue;}}①wait操作一次，請(qǐng)求分配一資源，s.value

=s.value

-1）②s.value≥0表示有資源，當(dāng)前進(jìn)程可執(zhí)行③s.value

＜0無(wú)資源，則當(dāng)前進(jìn)程進(jìn)入Q隊(duì)列的隊(duì)尾等待，等另一進(jìn)程執(zhí)行signal(S)操作后釋放資源。此時(shí)，|s.value

|絕對(duì)值表示等待資源進(jìn)程的個(gè)數(shù)。例：S=4S=0S=–2P1P2Signal(s)操作Signal(s){

s.value=s.value++;if(s.value<=0){

喚醒相應(yīng)等待隊(duì)列s.queue中等待的一個(gè)進(jìn)程改變其狀態(tài)為就緒態(tài)并將其插入就緒隊(duì)列

}}①signal操作一次，釋放一單位量資源（s.value

=s.value

+1）②s.value

＞

0

（有資源，告訴其它進(jìn)程可以繼讀）③s.value

≤0

（喚醒等待隊(duì)列中另一進(jìn)程執(zhí)行）§2.5進(jìn)程間的同步與互斥P，V操作的功能描述見(jiàn)下圖：入口

S–1SS0

入信號(hào)量等待隊(duì)列

置“等待”狀態(tài)

轉(zhuǎn)進(jìn)程調(diào)度<0返回P入口

S+1SS0

入就緒隊(duì)列

置“就緒”狀態(tài)

0VS0

從該信號(hào)量的等待

隊(duì)列中取出首元素

返回>0§2.5進(jìn)程間的同步與互斥

P，V操作可用軟件和硬件來(lái)執(zhí)行。無(wú)論P(yáng)操作和V操作，它們的執(zhí)行都必須是一個(gè)不可被中斷的整體。[注]：物理意義：S>0時(shí)，S為可用資源量；S=0時(shí)，可用資源量正好用完；S<0時(shí)，|S|為等待資源的隊(duì)列長(zhǎng)度，即還欠資源數(shù)(在信號(hào)量上等待的進(jìn)程數(shù))§2.5進(jìn)程間的同步與互斥AND型信號(hào)量集是指同時(shí)需要多種資源且每種占用一個(gè)時(shí)的信號(hào)量操作

AND型信號(hào)量集的基本思想：在一個(gè)原語(yǔ)中申請(qǐng)整段代碼需要的多個(gè)臨界資源，要么全部分配給它，要么一個(gè)都不分配AND型信號(hào)量集P原語(yǔ)為SwaitAND型信號(hào)量集V原語(yǔ)為Ssignal3.AND型信號(hào)量集§2.5進(jìn)程間的同步與互斥Swait(S1,S2,…,Sn) //P原語(yǔ)；{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //滿足資源要求時(shí)的處理；

for(i=1;i<=n;++i)--Si;//注：與P的處理不同，這里是在確信可滿足

//資源要求時(shí)，才進(jìn)行減1操作；break;}else{ //某些資源不夠時(shí)的處理；調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號(hào)量的等待隊(duì)列Sj.queue;

阻塞調(diào)用進(jìn)程;}}}§2.5進(jìn)程間的同步與互斥Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //釋放占用的資源；

for(在Si.queue中等待的每一個(gè)進(jìn)程P)//檢查每種資源的等待隊(duì)列的所有進(jìn)程；

{

從等待隊(duì)列Si.queue中取出進(jìn)程P;

§2.5進(jìn)程間的同步與互斥if(判斷進(jìn)程P是否通過(guò)Swait中的測(cè)試)//注：與signal不同，這里要進(jìn)行重新判斷；

{//通過(guò)檢查（資源夠用）時(shí)的處理；進(jìn)程P進(jìn)入就緒隊(duì)列;}else{//未通過(guò)檢查（資源不夠用）時(shí)的處理；進(jìn)程P進(jìn)入某等待隊(duì)列；

}}}}

§2.5進(jìn)程間的同步與互斥二、用信號(hào)量實(shí)現(xiàn)互斥§2.5進(jìn)程間的同步與互斥用信號(hào)量及wait、signal操作可以實(shí)施進(jìn)程之間的互斥。之前已有結(jié)論：實(shí)現(xiàn)進(jìn)程互斥的做法，是由OS來(lái)協(xié)調(diào)競(jìng)爭(zhēng)各方對(duì)互斥資源的使用。每個(gè)進(jìn)程在進(jìn)入到臨界區(qū)之前，必須先檢查臨界資源是否被占用。不論硬件臨界資源還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地訪問(wèn)它們。設(shè)置信號(hào)量mutex用于互斥，稱(chēng)互斥信號(hào)量，也稱(chēng)公有信號(hào)量，其初值一般為1。structsemaphoremutex;mutex.value=1表示無(wú)進(jìn)程進(jìn)入臨界區(qū)；mutex.value=0表示有一進(jìn)程在臨界區(qū)；mutex.value=-1表示有一進(jìn)程在臨界區(qū)，此外有一進(jìn)程在等待進(jìn)入臨界區(qū)。§2.5進(jìn)程間的同步與互斥struct

semaphor

mutex;main(){mutex.value=1;{{p1();//2個(gè)并發(fā)進(jìn)程

p2();}}}p1(){do{wait(mutex);

cs1;//臨界區(qū)

signal(mutex);}while(1);}p2(){do{wait(mutex);cs2;//臨界區(qū)

signal(mutex);}while(1);}wait(mutex);請(qǐng)求進(jìn)入臨界區(qū)，若不成，則等待(阻塞)signal(mutex);退出臨界區(qū)時(shí)，即刻釋放信號(hào)量，若阻塞隊(duì)列有進(jìn)程，則喚醒§2.5進(jìn)程間的同步與互斥分析：假設(shè)進(jìn)程p1先執(zhí)行wait(mutex)操作，mutex.value值減為0，則p1可進(jìn)入臨界區(qū)。然后p1執(zhí)行臨界區(qū)程序。若此時(shí)進(jìn)程p2開(kāi)始執(zhí)行wait(mutex)操作，則mutex.value的值縮減為-1。于是，進(jìn)程p2轉(zhuǎn)變?yōu)樽枞麪顟B(tài)，并進(jìn)入信號(hào)量mutex阻塞等待隊(duì)列。當(dāng)進(jìn)程p1退出臨界區(qū)，執(zhí)行signal(mutex),使mutex.value增加為0。同時(shí)signal操作中喚醒原語(yǔ)的執(zhí)行會(huì)把p2喚醒，使其從阻塞狀態(tài)轉(zhuǎn)變成就緒狀態(tài)，插入到就緒隊(duì)列中，等候CPU的調(diào)度。而一旦獲得調(diào)度，就能進(jìn)入臨界區(qū)運(yùn)行?！?.5進(jìn)程間的同步與互斥設(shè)置一個(gè)互斥信號(hào)量s，與公共變量m關(guān)聯(lián)，初值為1。進(jìn)程A：x=1;y=2;

wait(s);

m=x;x=y;y=m;signal(s);cout<<“A:”<<x<<y;進(jìn)程B：k=3;l=4;

wait(s);

m=k;k=l;l=m;

signal(s);

cout<<“B:”<<k<<l;臨界區(qū)§2.5進(jìn)程間的同步與互斥設(shè)S初始值為1A進(jìn)程：B進(jìn)程：

wait（S）wait（S）互斥工作段互斥工作段

signal（S）signal（S）

§2.5進(jìn)程間的同步與互斥§2.5經(jīng)典進(jìn)程同步問(wèn)題【思考題】設(shè)有N個(gè)進(jìn)程共享一互斥段對(duì)如下兩種情況每次只允許一個(gè)進(jìn)程進(jìn)入互斥段；最多允許M個(gè)進(jìn)程(M<N)同時(shí)進(jìn)入互斥段；所采用信號(hào)量是否相同？信號(hào)量值的變化范圍如何？§2.5經(jīng)典進(jìn)程同步問(wèn)題答：所采用的信號(hào)量相同，為mutex。第一種情況mutex初值為1，變化范圍為-(N-1)mutex1的整數(shù)，第二種情況mutex初值為M，變化范圍為M–NmutexM的整數(shù)。三、用信號(hào)量實(shí)現(xiàn)同步以2個(gè)合作進(jìn)程通過(guò)緩沖區(qū)傳送數(shù)據(jù)為例。p1是計(jì)算進(jìn)程，p2是打印進(jìn)程。單緩沖結(jié)構(gòu)。單緩沖Buffer計(jì)算進(jìn)程將處理好數(shù)據(jù)放入Buffer打印進(jìn)程從Buffer中取走已處理數(shù)據(jù)§2.5進(jìn)程間的同步與互斥規(guī)則:僅當(dāng)p1把數(shù)據(jù)送入空buffer，buffer滿時(shí)，p2才能從buffer取數(shù)，否則等待；在其送數(shù)過(guò)程中不得有另外進(jìn)程取數(shù)。僅當(dāng)p2把滿buffer中數(shù)據(jù)取走buffer變空，p1才能送數(shù)據(jù)進(jìn)入buffer，否則等待；在其取數(shù)過(guò)程中不得有另外進(jìn)程送數(shù)?！?.5進(jìn)程間的同步與互斥實(shí)現(xiàn)方法：設(shè)置2個(gè)信號(hào)量empty和full，用于同步，稱(chēng)私有信號(hào)量。empty描述p1（計(jì)算進(jìn)程）所需資源，即空buffer；初值為1，初始時(shí)buffer為空；

full

描述p2（打印進(jìn)程）所需資源，即滿buffer；初值為0，初始時(shí)buffer為空?！?.5進(jìn)程間的同步與互斥struct

semaphorempty,full;

empty.value=1;

full.value=0;{{p1()

//計(jì)算進(jìn)程

{do{producenextdata;

wait(empty);

adddatatobuffer;

signal(full);

}while(1);}

p2()//打印進(jìn)程

{do{wait(full);getdatafrombuffer;

signal(empty);}while(1);}}§2.5進(jìn)程間的同步與互斥wait(empty);請(qǐng)求空buffer，若不成，則進(jìn)程p1阻塞等待signal(full);送數(shù)完成，buffer變滿，即刻釋放滿buffer，若請(qǐng)求滿buffer的阻塞隊(duì)列內(nèi)有進(jìn)程，則喚醒，可看成向p2發(fā)信號(hào)wait(full);請(qǐng)求滿buffer，若不成，則進(jìn)程p2阻塞等待signal(empty);取數(shù)完成，buffer變空，即刻釋放空buffer,若請(qǐng)求空buffer的阻塞隊(duì)列內(nèi)有進(jìn)程，則喚醒，可看成向p1發(fā)信號(hào)§2.5進(jìn)程間的同步與互斥§3.3信號(hào)量及P-V操作現(xiàn)實(shí)生活中有許多同步的例子。例：在一輛公共汽車(chē)上，司機(jī)和售票員各有各的職責(zé)范圍。但兩者的工作又需要相互配合、協(xié)調(diào)。司機(jī)的職責(zé)是駕駛車(chē)輛，包括啟動(dòng)車(chē)輛、行車(chē)、到站停車(chē)；售票員的工作是到站開(kāi)車(chē)門(mén)、關(guān)車(chē)門(mén)、售票；車(chē)輛到站，司機(jī)停穩(wěn)車(chē)輛后，售票員才能打開(kāi)車(chē)門(mén)讓乘客上、下車(chē)，然后關(guān)車(chē)門(mén)；只有在得到車(chē)門(mén)已經(jīng)關(guān)好的信號(hào)后，司機(jī)才能啟動(dòng)汽車(chē)?yán)^續(xù)前進(jìn)?！?.3信號(hào)量及P-V操作分析結(jié)論：有2個(gè)同步過(guò)程:在司機(jī)停車(chē)和售票員開(kāi)門(mén)之間；在售票員關(guān)門(mén)和司機(jī)啟動(dòng)汽車(chē)之間。§3.3信號(hào)量及P-V操作司機(jī)進(jìn)程：售票員進(jìn)程：

↓↓

啟動(dòng)車(chē)輛關(guān)車(chē)門(mén)

↓↓

運(yùn)行賣(mài)票

↓↓

到站停車(chē)開(kāi)車(chē)門(mén)

↓↓司機(jī)和售票員的同步操作§3.3信號(hào)量及P-V操作本問(wèn)題討論可以有多種方法分析：設(shè)置2個(gè)信號(hào)量s1和s2S1表示是否允許司機(jī)啟動(dòng)汽車(chē)，初值為0S2表示是否允許售票員開(kāi)門(mén)，初值為0。§3.3信號(hào)量及P-V操作解法一：

s1=0,s2=0;//初始取車(chē)停狀態(tài)

司機(jī)進(jìn)程：

wait(s1)售票員進(jìn)程：關(guān)車(chē)門(mén) ↓↓啟動(dòng)車(chē)輛signal(s1)↓↓運(yùn)行售票↓↓

到站停車(chē)wait(s2)↓↓signal(s2)開(kāi)車(chē)門(mén)

↓↓解法二：

s1=1,s2=0;//初始取車(chē)行狀態(tài)

司機(jī)進(jìn)程：

wait(s1)售票員進(jìn)程：售票 ↓↓啟動(dòng)車(chē)輛wait(s2)↓↓運(yùn)行開(kāi)車(chē)門(mén)↓↓

到站停車(chē)關(guān)車(chē)門(mén)↓↓signal(s2)signal(s1)

↓↓2.利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系圖2-10前趨圖舉例§2.5進(jìn)程間的同步與互斥§2.5進(jìn)程的同步與互斥

Vara,b,c,d,e,f,g;semaphore∶=0,0,0,0,0,0,0;begin

parbegin beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(c);S4;signal(f);end; beginwait(d);S5;signal(g);end; beginwait(e);wait(f);wait(g);S6;end;

parendend§2.5信號(hào)量及P-V操作比較同步與互斥中使用的信號(hào)量

同步

互斥

私有信號(hào)量如empty、full公有信號(hào)量如

mutex聯(lián)系一組同步進(jìn)程聯(lián)系一組互斥進(jìn)程

擁有者只能做wait操作，signal操作由其它進(jìn)程完成所有進(jìn)程都可做wait、signal操作

§2.5信號(hào)量及P-V操作wait、signal操作的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡(jiǎn)單，而且表達(dá)能力強(qiáng)（用wait、signal操作可解決任何同步互斥問(wèn)題）缺點(diǎn)：不夠安全；wait、signal操作使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步互斥問(wèn)題時(shí)實(shí)現(xiàn)復(fù)雜§2.5經(jīng)典進(jìn)程同步問(wèn)題在多道程序環(huán)境下，進(jìn)程的同步與互斥十分重要，相當(dāng)復(fù)雜，吸引了不少學(xué)者對(duì)其進(jìn)行研究，由此產(chǎn)生了一些經(jīng)典的進(jìn)程同步問(wèn)題。如：“生產(chǎn)者—消費(fèi)者問(wèn)題”、“讀者—寫(xiě)者問(wèn)題”、“理發(fā)師睡覺(jué)問(wèn)題”、“哲學(xué)家就餐問(wèn)題”等等?！吧a(chǎn)者—消費(fèi)者問(wèn)題”是其中較有代表性的進(jìn)程同步問(wèn)題，是相互合作進(jìn)程的一種抽象?！?.6經(jīng)典進(jìn)程同步問(wèn)題一、《生產(chǎn)者－消費(fèi)者問(wèn)題》放產(chǎn)品取產(chǎn)品1個(gè)生產(chǎn)者與1個(gè)消費(fèi)者，共享1個(gè)單緩沖1.簡(jiǎn)單《生產(chǎn)者－消費(fèi)者問(wèn)題》單緩沖Buffer生產(chǎn)者消費(fèi)者一次只可放一個(gè)產(chǎn)品§2.6經(jīng)典進(jìn)程同步問(wèn)題簡(jiǎn)單《生產(chǎn)者─消費(fèi)者問(wèn)題》分析“生產(chǎn)者—消費(fèi)者”屬于同步問(wèn)題。生產(chǎn)者進(jìn)程需要的資源是“空緩沖”，以能在其中放置產(chǎn)品，為“空緩沖”設(shè)置信號(hào)量empty，初值為1（初始時(shí)緩沖為空）；消費(fèi)者進(jìn)程需要的資源是“滿緩沖”，以能從中取出產(chǎn)品；為“滿緩沖”設(shè)置信號(hào)量full，初值為0（初始時(shí)緩沖為空，即無(wú)滿緩沖）。§2.6經(jīng)典進(jìn)程同步問(wèn)題簡(jiǎn)單《生產(chǎn)者─消費(fèi)者問(wèn)題》解法empty=1,full=0;生產(chǎn)者進(jìn)程：消費(fèi)者進(jìn)程：while(true){while(true){

生產(chǎn)一個(gè)產(chǎn)品;wait(full);

wait(empty);從緩沖區(qū)取產(chǎn)品;

送產(chǎn)品到緩沖區(qū);signal(empty);

signal(full);消費(fèi)產(chǎn)品;};};§2.6經(jīng)典進(jìn)程同步問(wèn)題1個(gè)生產(chǎn)者與1個(gè)消費(fèi)者，共享n個(gè)緩沖生產(chǎn)者進(jìn)程將產(chǎn)品放入空Buffer消費(fèi)者進(jìn)程從滿Buffer中取走產(chǎn)品……n個(gè)Buffer2.多個(gè)緩沖區(qū)的《生產(chǎn)者－消費(fèi)者問(wèn)題》§2.6經(jīng)典進(jìn)程同步問(wèn)題多緩沖“生產(chǎn)者—消費(fèi)者”屬于同步問(wèn)題。生產(chǎn)者進(jìn)程需要的資源是“空緩沖”，為“空緩沖”設(shè)置信號(hào)量empty，初值為n（初始時(shí)n個(gè)緩沖全部為空）；消費(fèi)者進(jìn)程需要的資源是“滿緩沖”，為“滿緩沖”設(shè)置信號(hào)量full，初值為0（初始時(shí)緩沖全空,沒(méi)有一個(gè)是滿緩沖）.§2.6經(jīng)典進(jìn)程同步問(wèn)題因生產(chǎn)者不斷在生產(chǎn)，消費(fèi)者不斷在消費(fèi)，故n個(gè)緩沖區(qū)必須循環(huán)使用。為管理n個(gè)緩沖區(qū)，設(shè)置2個(gè)指針：in:

指明當(dāng)前空緩沖，生產(chǎn)者按in所指向的Buffer來(lái)存放產(chǎn)品，然后對(duì)in做操作in=（in+1）%n，以調(diào)整指針in。out:

指明當(dāng)前滿緩沖，消費(fèi)者按out所指向的Buffer來(lái)取產(chǎn)品，然后對(duì)out進(jìn)行操作out=（out+1）%n，以調(diào)整指針out?！?.6經(jīng)典進(jìn)程同步問(wèn)題多緩沖區(qū)《生產(chǎn)者—消費(fèi)者問(wèn)題》解法empty=n,full=0生產(chǎn)者進(jìn)程P：

in=0;

while(true){

生產(chǎn)一個(gè)產(chǎn)品;

wait(empty);

往Buffer[in]放產(chǎn)品;

signal(full);

in=(in+1)%n;};消費(fèi)者進(jìn)程Q：

out=0;while(true){

wait(full);

從Buffer[out]取一個(gè)產(chǎn)品;

signal(empty);

消費(fèi)產(chǎn)品;out=(out+1)%n;};§2.6經(jīng)典進(jìn)程同步問(wèn)題通過(guò)一個(gè)循環(huán)有界多緩沖區(qū)把i個(gè)生產(chǎn)者和j個(gè)消費(fèi)者聯(lián)系起來(lái)。k個(gè)緩沖區(qū)、i個(gè)生產(chǎn)者和j個(gè)消費(fèi)者3.經(jīng)典的《生產(chǎn)者—消費(fèi)者問(wèn)題》§2.6經(jīng)典進(jìn)程同步問(wèn)題要求與分析：只要緩沖區(qū)未滿，生產(chǎn)者就可將一個(gè)數(shù)據(jù)送入緩沖區(qū)，否則生產(chǎn)者因缺少“空緩沖”資源而阻塞等待。只要緩沖區(qū)未空，消費(fèi)者就可從緩沖區(qū)取走一個(gè)數(shù)據(jù)，否則消費(fèi)者因缺少“滿緩沖”資源而阻塞等待。顯然，2個(gè)進(jìn)程之間需要同步，分別在送或取數(shù)據(jù)操作之前，先要知道緩沖區(qū)情況，即所需資源情況。此外，還需互斥地訪問(wèn)緩沖區(qū)，因?yàn)橛衖個(gè)生產(chǎn)者與j個(gè)消費(fèi)者，它們?cè)诟髯韵蚓彌_區(qū)送數(shù)和取數(shù)時(shí)，必須互斥，禁止其它進(jìn)程操作。§2.6經(jīng)典進(jìn)程同步問(wèn)題buffer[k]：數(shù)組，表示具有k個(gè)（0、1、2、k-1）單位緩沖的緩沖區(qū)。in：輸入指針，指示下一個(gè)可投放數(shù)據(jù)的單位緩沖，每當(dāng)生產(chǎn)者進(jìn)程向單位緩沖投放一個(gè)數(shù)據(jù)，in加1。out：輸出指針，指示下一個(gè)可獲取數(shù)據(jù)的單位緩沖，每當(dāng)消費(fèi)者進(jìn)程從單位緩沖取走一個(gè)數(shù)據(jù)，out加1empty：資源信號(hào)量，表示緩沖區(qū)中空緩沖的數(shù)量。full：資源信號(hào)量，表示緩沖區(qū)中滿緩沖的數(shù)量。mutex：互斥信號(hào)量，使諸進(jìn)程實(shí)現(xiàn)對(duì)緩沖區(qū)的互斥使用?！?.6經(jīng)典進(jìn)程同步問(wèn)題structsemaphoremutex=1,empty=k,full=0;structmessagebuffer[k];int

in;out;§2.6經(jīng)典進(jìn)程同步問(wèn)題{{producer(){in=0;

while(true){

生產(chǎn)產(chǎn)品;

wait(empty);

wait(mutex);

往buffer[in]放產(chǎn)品;in=(in+1)%k;

signal(mutex);

signal(full);

};}comsumer(){out=0;while(true){

wait(full);

wait(mutex);

從buffer[out]取產(chǎn)品;out=(out+1)%k;

signal(mutex);

signal(empty);

消費(fèi)產(chǎn)品;};}}}§2.6經(jīng)典進(jìn)程同步問(wèn)題注意：（1）在每個(gè)程序中用于互斥的信號(hào)量的wait、signal操作必須成對(duì)出現(xiàn)。（2）對(duì)資源信號(hào)量empty和full的wait

、signal操作需成對(duì)出現(xiàn)，但是分別出現(xiàn)在不同的程序中。（3）在每個(gè)程序的多個(gè)wait操作，順序不能顛倒，否則死鎖?！?.6經(jīng)典進(jìn)程同步問(wèn)題有兩組并發(fā)進(jìn)程:把只想讀數(shù)據(jù)的進(jìn)程稱(chēng)之為”讀者”,想更新數(shù)據(jù)的進(jìn)程稱(chēng)之為”寫(xiě)者”,共享一組數(shù)據(jù)區(qū).基本思想:任一寫(xiě)者必須與其他寫(xiě)者或讀者互斥訪問(wèn)可供共享的數(shù)據(jù)對(duì)象.要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫(xiě)者同時(shí)操作不允許多個(gè)寫(xiě)者同時(shí)操作二、讀者寫(xiě)者問(wèn)題§2.5經(jīng)典進(jìn)程同步問(wèn)題第一類(lèi)：讀者優(yōu)先

如果讀者來(lái)：1）無(wú)讀者、寫(xiě)者，新讀者可以讀2）有寫(xiě)者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫(xiě)者寫(xiě)，新讀者等如果寫(xiě)者來(lái)：1）無(wú)讀者，新寫(xiě)者可以寫(xiě)2）有讀者，新寫(xiě)者等待3）有其它寫(xiě)者，新寫(xiě)者等待讀者優(yōu)先：當(dāng)有讀者在讀文件時(shí)，對(duì)隨后到達(dá)的讀者和寫(xiě)者，要首先滿足讀者，阻塞寫(xiě)者。

§2.5經(jīng)典進(jìn)程同步問(wèn)題第一類(lèi)讀者寫(xiě)者問(wèn)題的解法mutex=1,w=1;讀者：

while(true){

wait(mutex);

readcount++;if(readcount==1)wait(w);

signal(mutex);

讀

wait(mutex);

readcount--;if(readcount==0)signal(w);

signal

(mutex);};寫(xiě)者：

while(true){

wait(w);

寫(xiě)

signal(w);};§2.5經(jīng)典進(jìn)程同步問(wèn)題第二類(lèi)：寫(xiě)者優(yōu)先條件：1）多個(gè)讀者可以同時(shí)進(jìn)行讀2）寫(xiě)者必須互斥（只允許一個(gè)寫(xiě)者寫(xiě)，也不能讀者寫(xiě)者同時(shí)進(jìn)行）3）寫(xiě)者優(yōu)先于讀者（一旦有寫(xiě)者，則后續(xù)讀者必須等待，喚醒時(shí)優(yōu)先考慮寫(xiě)者）§2.5經(jīng)典進(jìn)程同步問(wèn)題三、哲學(xué)家就餐問(wèn)題有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤(pán)通心粉，每人面前有一只空盤(pán)子，每?jī)扇酥g放一只筷子每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子§2.5經(jīng)典進(jìn)程同步問(wèn)題fork[5]={1,1,1,1,1}voidphilosopher(inti){while(true){

思考；

wait(fork[i]);

wait(fork[(i+1)%5])；進(jìn)食；

signal(fork[i]);

signal(fork[(i+1)%5])；

}}可能發(fā)生死鎖哲學(xué)家就餐問(wèn)題解法（1）§2.5經(jīng)典進(jìn)程同步問(wèn)題

為防止死鎖發(fā)生可采取的措施：最多允許4個(gè)哲學(xué)家同時(shí)要求進(jìn)餐，以確保至少有一個(gè)人可以進(jìn)餐。一次拿到兩只筷子，否則不拿semaphoreroom=4,fork[5]={1,1,1,1,1}voidphilosopher(inti){while(true){

思考；

wait(room);

wait(fork[i]);

wait(fork[(i+1)%5])；進(jìn)食；

signal(fork[i]);

signal(fork[(i+1)%5])；

signal(room);

}}§2.5經(jīng)典進(jìn)程同步問(wèn)題哲學(xué)家就餐問(wèn)題解法（2）給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之.§2.5經(jīng)典進(jìn)程同步問(wèn)題理發(fā)店里有一位理發(fā)師，一把理發(fā)椅和N把供等候理發(fā)的顧客坐的椅子如果沒(méi)有顧客,則理發(fā)師便在理發(fā)椅上睡覺(jué)。當(dāng)一個(gè)顧客到來(lái)時(shí)，他必須先喚醒理發(fā)師如果顧客到來(lái)時(shí)理發(fā)師正在理發(fā)，則如果有空椅子，可坐下來(lái)等,否則離開(kāi)四、理發(fā)師睡覺(jué)問(wèn)題1.桌上有一空盤(pán)，允許存放一個(gè)水果。爸爸可向盤(pán)中放蘋(píng)果，或放橘子，兒子專(zhuān)門(mén)等著吃盤(pán)中的橘子，女兒專(zhuān)門(mén)等著吃盤(pán)中的蘋(píng)果。規(guī)定當(dāng)盤(pán)空時(shí)一次只能放一個(gè)水果供取用，試實(shí)現(xiàn)爸爸、兒子和女兒三個(gè)并發(fā)進(jìn)程的同步。

爸爸進(jìn)程:while(1){

wait(empty);

放水果;if(橘子)

signal(orange);if(蘋(píng)果)

signal

(apple);}兒子進(jìn)程:while(1){

wait

(orange);

取橘子;

signal

(empty);}女兒進(jìn)程:while(1){

wait

(apple);

取蘋(píng)果;

signal

(empty);}信號(hào)量:empty=1;orange=0;apple=0;

2、有一個(gè)閱覽室，共有100個(gè)座位，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一座位列一表目，包括座號(hào)和讀者姓名等，讀者離開(kāi)時(shí)要消掉登記的信息，試問(wèn)：為描述讀者的動(dòng)作，應(yīng)編寫(xiě)幾個(gè)程序，設(shè)置幾個(gè)進(jìn)程？試用wait、signal操作描述讀者進(jìn)程之間的同步關(guān)系。讀者進(jìn)入閱覽室的動(dòng)作描述getin：while(1){wait(seats);/*沒(méi)有座位則離開(kāi)*/wait（mutex）/*進(jìn)入臨界區(qū)*/填寫(xiě)登記表;進(jìn)入閱覽室讀書(shū);signal（mutex）/*離開(kāi)臨界區(qū)*/signal（readers）}讀者離開(kāi)閱覽室的動(dòng)作描述getout：while(1){wait（readers）/*閱覽室是否有人讀書(shū)*/wait（mutex）/*進(jìn)入臨界區(qū)*/消掉登記；離開(kāi)閱覽室；signal（mutex）/*離開(kāi)臨界區(qū)*/signal（seats）/*釋放一個(gè)座位資源*/}作業(yè)21.Page6822.Page6883.Page68224.Page69275.*用信號(hào)量方法，解決第二類(lèi)讀者寫(xiě)者問(wèn)題（寫(xiě)者優(yōu)先）。6.*用信號(hào)量方法，解決理發(fā)師睡覺(jué)問(wèn)題。操作系統(tǒng)術(shù)語(yǔ)31、進(jìn)程：Process2、進(jìn)程表：ProcessTables3、進(jìn)程映像：ProcessImage4、進(jìn)程控制塊：ProcessControlBlock5、并發(fā)：Concurrence6、互斥：MutualExclusion7、臨界資源：CriticalResource8、臨界段：CriticalSection理發(fā)師問(wèn)題之參考解法引入3個(gè)信號(hào)量和一個(gè)控制變量：

1)信號(hào)量customers用來(lái)記錄等候理發(fā)的顧客數(shù)，并用作阻塞理發(fā)師進(jìn)程，初值為0;

2)信號(hào)量barbers用來(lái)記錄正在等候顧客的理發(fā)師數(shù)，并用作阻塞顧客進(jìn)程，初值為0;

3)信號(hào)量mutex用于互斥，初值為1.

4)控制變量waiting用來(lái)記錄等候理發(fā)的顧客數(shù)，初值為0;

intwaiting;//等候理發(fā)的顧客數(shù)

constintCHAIRS//為顧客準(zhǔn)備的椅子數(shù)

semaphorecustomers,barbers,mutex;

customers=0;barbers=0;waiting=0;mutex=1;

理發(fā)師進(jìn)程:

wait(customers);//若無(wú)顧客,理發(fā)師睡眠

wait(mutex);//進(jìn)程互斥

waiting--;//等候顧客數(shù)少一個(gè)

cut-hair();//正在理發(fā)

signal(barbers);//喚醒等待顧客

signal(mutex);//開(kāi)放臨界區(qū)

顧客進(jìn)程:

wait(mutex);//進(jìn)程互斥ifwaiting<CHAIRS//看看有沒(méi)有空椅子

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

signal(customers);//必要的話喚醒理