計(jì)算機(jī)操作系統(tǒng)第四章ppt課件

1、操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM第4章 并發(fā)與互斥 根本概念 互斥：軟件方法 硬件方法 信號量機(jī)制 管程 死 鎖 主主 要要 內(nèi)內(nèi) 容容操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.1 4.1 根本概念根本概念4.1.1 4.1.1 臨界資源和臨界區(qū)臨界資源和臨界區(qū) 臨界資源臨界資源Critical ResourcesCritical Resources：一種一次只：一種一次只能為一個(gè)進(jìn)程效力的資源。能為一個(gè)進(jìn)

2、程效力的資源。 臨界區(qū)臨界區(qū)Critical SectionCritical Section：進(jìn)程中訪問臨界：進(jìn)程中訪問臨界資源的程序。每個(gè)運(yùn)用該資源的進(jìn)程都要包含一資源的程序。每個(gè)運(yùn)用該資源的進(jìn)程都要包含一個(gè)臨界區(qū)。個(gè)臨界區(qū)。 操作系統(tǒng)在管理可控制資源分配與運(yùn)用方面，操作系統(tǒng)在管理可控制資源分配與運(yùn)用方面，該當(dāng)保證進(jìn)程對臨界資源的訪問滿足以下該當(dāng)保證進(jìn)程對臨界資源的訪問滿足以下3 3點(diǎn)：點(diǎn)： l l 互斥訪問要求。互斥訪問要求。 l l 不致于產(chǎn)生不致于產(chǎn)生“死鎖。死鎖。 l l 不能有不能有“饑餓進(jìn)程。饑餓進(jìn)程。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一

3、世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.1.2 4.1.2 互斥管理準(zhǔn)那么互斥管理準(zhǔn)那么 空閑讓進(jìn)：當(dāng)沒有進(jìn)程在臨界區(qū)時(shí)，任何需求進(jìn)空閑讓進(jìn)：當(dāng)沒有進(jìn)程在臨界區(qū)時(shí)，任何需求進(jìn)入臨界區(qū)的進(jìn)程都允許立刻進(jìn)入。入臨界區(qū)的進(jìn)程都允許立刻進(jìn)入。 忙那么等待：在共享同一對象的一切進(jìn)程中，一忙那么等待：在共享同一對象的一切進(jìn)程中，一次只能有一個(gè)進(jìn)程進(jìn)入臨界區(qū)。其它要求進(jìn)入臨次只能有一個(gè)進(jìn)程進(jìn)入臨界區(qū)。其它要求進(jìn)入臨界區(qū)的進(jìn)程只能等待。界區(qū)的進(jìn)程只能等待。 有限等待：任何一個(gè)進(jìn)程經(jīng)有限時(shí)間等待后都能有限等待：任何一個(gè)進(jìn)程經(jīng)有限時(shí)間等待后都能進(jìn)入臨界區(qū)，不允許出現(xiàn)進(jìn)程死鎖或饑餓的情況進(jìn)入臨界區(qū)，

4、不允許出現(xiàn)進(jìn)程死鎖或饑餓的情況發(fā)生。發(fā)生。 讓權(quán)等待：當(dāng)一個(gè)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)要立刻讓權(quán)等待：當(dāng)一個(gè)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)要立刻阻塞本人，釋放處置機(jī)讓其它進(jìn)程運(yùn)用，防止阻塞本人，釋放處置機(jī)讓其它進(jìn)程運(yùn)用，防止“忙忙等。等。 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.2 4.2 互斥：軟件方法互斥：軟件方法 第一次嘗試 算法中設(shè)計(jì)了一個(gè)變量turn保管允許進(jìn)入臨界區(qū)的進(jìn)程編號初值為1，表示進(jìn)程1可以首先進(jìn)入。當(dāng)一個(gè)進(jìn)程要求進(jìn)入臨界區(qū)時(shí)，先檢查turn的值。假設(shè)turn保管的不是本人的進(jìn)程編號就進(jìn)展循環(huán)等待

5、；否那么進(jìn)入臨界區(qū)。訪問完成后退出臨界區(qū)，再將turn設(shè)置為對方的進(jìn)程編號。 第二次嘗試 算法中定義了一個(gè)標(biāo)志數(shù)組flag。當(dāng)flagi=true，表示進(jìn)程i正在臨界區(qū)。初始時(shí)Flag的各分量值皆為false，表示尚無進(jìn)程進(jìn)入。當(dāng)一個(gè)進(jìn)程要求進(jìn)入臨界區(qū)時(shí)，先檢查能否有進(jìn)程已進(jìn)入。假設(shè)有進(jìn)程進(jìn)入，就循環(huán)等待；否那么，設(shè)置本人的標(biāo)志為真，立刻進(jìn)入。訪問完成后再將本人的標(biāo)志設(shè)為假。4.2.1 Dekker4.2.1 Dekker方法方法操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM算法如下：Process P (1)

6、 Process P (2)Begin begin While (Flag2) do skip; While (Flag1) do skip;Flag1 = true; Flag2 = true;Critical section; Critical section;Flag1 = false; Flag2 = false; end. end.操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM第三次嘗試第三次嘗試 在第二次嘗試的根底上，將其中的兩個(gè)語句順序交換，構(gòu)成了新的算法如下： Process P (1) Pro

7、cess P (2) Begin begin Flag1 = true; Flag2 = true; While (Flag2) do skip;While (Flag1) do skip; Critical section; Critical section; Flag1 = false; Flag2 = false; end. end.操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM 第四次嘗試 這是一個(gè)“禮讓為先的算法，每個(gè)進(jìn)程設(shè)置好本人的flag標(biāo)志，闡明希望進(jìn)入臨界區(qū)。但也預(yù)備重置flag，以表示謙讓。

8、算法如下： Process P (1) Process P (2)Begin begin Flag1 = true; Flag2 = true;While (Flag2) do While (Flag1) do flag1=false; flag2=false; flag1=true; flag2=true;Critical section; Critical section;Flag1 = false; Flag2 = false; end. end.操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM 正確的算法

9、正確的算法 為了防止過度互斥禮讓的問題，Dekker運(yùn)用第一種嘗試中的輪盤變量turn，表示哪個(gè)進(jìn)程有權(quán)進(jìn)入臨界區(qū)。讓它在兩個(gè)進(jìn)程的活動中規(guī)定一個(gè)強(qiáng)迫性的順序。算法如下：Process P (1) Process P (2)Begin begin Flag1 = true; Flag2 = true;While (Flag2) do While (Flag1) do if (turn=2) if (turn=1)flag1=false;flag2=false; while (turn=2) do skip; while (turn=1) do skip; flag1=true; flag2=t

10、rue;Critical section; Critical section;turn=2; turn=1;Flag1 = false; Flag2 = false; end. end.操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.2.2 Peterson4.2.2 Peterson算法算法 變量turn用來保管進(jìn)程的編號，當(dāng)turn=i，表示進(jìn)程i有權(quán)進(jìn)入臨界區(qū)。數(shù)組flag表示哪個(gè)進(jìn)程進(jìn)入了臨界區(qū)，F(xiàn)lagi=true，表示進(jìn)程i已進(jìn)入。初始時(shí)，標(biāo)志數(shù)組flag的各元素值皆為false，表示無進(jìn)程進(jìn)入臨

11、界區(qū)。變量turn可以不設(shè)初始值。下面是該算法的主要部分：Process P (1) Process P (2)Begin begin Flag1 = true; Flag2 = true;turn=2; turn=1;While (Flag2turn=2) While (Flag1 turn=1) do skip; do skip;Critical section; Critical section;Flag1 = false; Flag2 = false; end. end操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING S

12、YSTERM4.3 4.3 硬件方法硬件方法4.3.1 4.3.1 交換指令交換指令 將兩個(gè)指定位置上的數(shù)據(jù)進(jìn)展交換，是該指令將兩個(gè)指定位置上的數(shù)據(jù)進(jìn)展交換，是該指令實(shí)現(xiàn)的操作。微型機(jī)實(shí)現(xiàn)的操作。微型機(jī)PCPC上對應(yīng)的指令格式是上對應(yīng)的指令格式是XCHG XCHG op1op1，op2op2，用于交換兩個(gè)操作對象的值其中，用于交換兩個(gè)操作對象的值其中，opiopi是操作對象。是操作對象。 交換指令的功能可描畫為下面的過程：交換指令的功能可描畫為下面的過程： Procedure XCHG(op1,op2)Procedure XCHG(op1,op2)BeginBeginBoolean temp;

13、Boolean temp;temp = op1;temp = op1;op1 = op2;op1 = op2;op2 = temp;op2 = temp;End End 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.3.2 4.3.2 測試與設(shè)置指令測試與設(shè)置指令 該指令將形狀測試和形狀設(shè)置集于一條指令中，構(gòu)成一個(gè)原子操作。也就是說，兩個(gè)操作的執(zhí)行不受中斷信號的干擾。下面將指令格式定義為TS，功能是，讀出一個(gè)指定變量的值，同時(shí)將一個(gè)新值置入。 對于邏輯變量，比如lock，TS的測試和設(shè)置的功能可描畫為下面的

14、函數(shù)： Function TS(lock)BeginTS = Lock;Lock = true;End 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM 下面的例子中定義的全局變量是下面的例子中定義的全局變量是mutexmutex，初始值為，初始值為falsefalse表示無人進(jìn)入。表示無人進(jìn)入。 利用利用TSTS指令實(shí)現(xiàn)的互斥機(jī)制描畫如下。指令實(shí)現(xiàn)的互斥機(jī)制描畫如下。 Procedure Process (i) Begin While (TSmutex) do skip; / 循環(huán)等待 Critical sec

15、tion; mutex = false; End.操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.4 4.4 信號量機(jī)制信號量機(jī)制 著名的計(jì)算機(jī)學(xué)者Dijkstra經(jīng)過長期的操作系統(tǒng)研討與設(shè)計(jì)，于1965年提出了一種同步機(jī)制信號量機(jī)制。該機(jī)制由一個(gè)稱為信號量Semaphore，也譯為“信號燈的特殊變量和兩個(gè)被命名為P、V操作的原語組成。在廣泛的運(yùn)用中，該機(jī)制得到了迅速開展。 這一機(jī)制的根本原理是，為每個(gè)臨界資源設(shè)置一個(gè)信號量，擔(dān)任在多個(gè)進(jìn)程之間轉(zhuǎn)發(fā)互斥信息。當(dāng)一個(gè)進(jìn)程需求互斥運(yùn)用某個(gè)臨界資源時(shí)，可經(jīng)過對信號量

16、的P操作，了解該資源的空閑情況。當(dāng)它運(yùn)用完該臨界資源后，又可經(jīng)過對相關(guān)信號量的V操作，讓其它需求該資源的進(jìn)程感知到它的離去。 假設(shè)一個(gè)資源被視為臨界資源，就該當(dāng)為它定義一個(gè)獨(dú)立的信號量，對進(jìn)程訪問起“放行和“阻止作用，就像交通管理中每個(gè)路口設(shè)置的交通燈一樣。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.4.1 4.4.1 整型信號量整型信號量整型信號量是Dijkstra最初提出的一種信號量，被定義為整型變量。其取值范圍是0，1。其值等于1是放行形狀也稱作“綠燈，等于0為阻止形狀也稱作“紅燈。整型信號量機(jī)制中

17、的P、V操作是兩個(gè)小巧小巧的過程。它們是操作系統(tǒng)中提供的兩個(gè)原語，其代碼如下圖。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM 利用整型信號量機(jī)制實(shí)現(xiàn)進(jìn)程互斥訪問臨界資源時(shí)，需求為該資源設(shè)一個(gè)整型信號量，比如mutex。令其初始值為1，表示它的初始形狀空閑。每個(gè)要求訪問臨界資源的進(jìn)程都要在臨界區(qū)的前面經(jīng)過P操作來訪問mutex，決議能否可以立刻進(jìn)入臨界區(qū)。此外，還要在臨界區(qū)的后面運(yùn)用V操作，聲明運(yùn)用終了。程序構(gòu)造如下所示： process p ( i )beginP(mutex);Critical sectio

18、n;V(mutex);end;操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.4.2 4.4.2 記錄型信號量記錄型信號量 記錄型信號量機(jī)制是在整型信號量機(jī)制的根底上開展起來的，它實(shí)現(xiàn)了“讓權(quán)等待功能。一個(gè)記錄型信號量包含兩個(gè)分量：信號量的值、信號量的等待隊(duì)列指針，描畫如下：type semaphore = recordvalue: integer;*L: integer;end. 記錄型信號量的取值范圍是-N，+M。其值大于0時(shí)為放行形狀也稱作“綠燈形狀，小于等于0時(shí)為阻止形狀也稱作“紅燈形狀。進(jìn)程可經(jīng)過執(zhí)

19、行P操作來了解臨界資源的形狀，假設(shè)發(fā)現(xiàn)當(dāng)前為阻止形狀時(shí)，就將進(jìn)程阻塞起來。頗像是交通管理系統(tǒng)中的汽車過路口排隊(duì)等候一樣。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM消費(fèi)者消費(fèi)者- -消費(fèi)者問題消費(fèi)者問題系統(tǒng)里有假設(shè)干個(gè)協(xié)作的進(jìn)程，其中，nn0個(gè)消費(fèi)者進(jìn)程， mm0個(gè)消費(fèi)者進(jìn)程，以及由PP0個(gè)緩沖區(qū)組成的緩沖區(qū)環(huán)。任何一個(gè)消費(fèi)者進(jìn)程都可以將本人的產(chǎn)品存入環(huán)內(nèi)的一個(gè)緩沖區(qū)中；任何一個(gè)消

20、費(fèi)者可以將環(huán)內(nèi)的一個(gè)產(chǎn)品取出。消費(fèi)者源源不斷地消費(fèi)并存入產(chǎn)品；消費(fèi)者周而復(fù)始地從環(huán)內(nèi)取出產(chǎn)品并掉。假定運(yùn)用的約束條件是：1) 當(dāng)環(huán)中有空閑緩沖區(qū)時(shí)，允許任一消費(fèi)者進(jìn)程把它的產(chǎn)品存入。 (2) 當(dāng)環(huán)中無空閑緩沖區(qū)時(shí)，那么試圖將產(chǎn)品存入緩沖區(qū)環(huán)的任何消費(fèi)者進(jìn)程必需等待。 (3) 當(dāng)環(huán)中尙有未取出的產(chǎn)品時(shí)，允許任一個(gè)消費(fèi)者進(jìn)程把其中的一個(gè)產(chǎn)品取出。4 當(dāng)環(huán)中沒有未取出的產(chǎn)品時(shí)，試圖從該環(huán)內(nèi)取出產(chǎn)品的任何消費(fèi)者進(jìn)程必需等待。 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM圖中，左側(cè)的進(jìn)程P1Pn為消費(fèi)者進(jìn)程，右側(cè)的S1

21、Sm為消費(fèi)者進(jìn)程。圖中的緩沖區(qū)環(huán)內(nèi)有8P=8個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)可以存入一件產(chǎn)品。環(huán)上設(shè)有存入指針和讀取指針，都按順時(shí)針方向挪動。 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM消費(fèi)者進(jìn)程的同步控制程序描畫為下述過程： Semaphore: mutex,Sin,Sout1,8,0; Integer: in,out0,0; Parbegin Producer( ); Consumer( ) Parend. Process Producer( ) Begin While (true) Begin Produce_a

22、n_Item()_in_NextP1;/計(jì)算一個(gè)數(shù)據(jù) P(Sin); P(mutex); BufferinNextP1;/臨界區(qū) in(in+1) MOD 8; V(mutex); V(Sout);操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM EndEndProcess Consumer( ) Begin While (true) Begin P(Sout); P(mutex); NextP2Bufferout; / 臨界區(qū) out(out+1) MOD 8; V(mutex); V(Sin); Consum

23、e_an_Item()_in_NextP2; / 消費(fèi)一個(gè)數(shù)據(jù) EndEnd操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM 讀者讀者- -寫者問題寫者問題 有一個(gè)數(shù)據(jù)塊被多個(gè)用戶共享，其有一個(gè)數(shù)據(jù)塊被多個(gè)用戶共享，其中部分用戶是讀者，另一部分是寫者。我中部分用戶是讀者，另一部分是寫者。我們規(guī)定：讀者對數(shù)據(jù)塊是只讀的，而且允們規(guī)定：讀者對數(shù)據(jù)塊是只讀的，而且允許多個(gè)讀者同時(shí)讀；寫者對數(shù)據(jù)塊是只寫許多個(gè)讀者同時(shí)讀；寫者對數(shù)據(jù)塊是只寫的，當(dāng)一個(gè)寫者正在向數(shù)據(jù)塊寫信息的時(shí)的，當(dāng)一個(gè)寫者正在向數(shù)據(jù)塊寫信息的時(shí)候，不允許其

24、他用戶運(yùn)用，無論是讀還是候，不允許其他用戶運(yùn)用，無論是讀還是寫。寫。 該問題中的數(shù)據(jù)塊作為多個(gè)用戶共該問題中的數(shù)據(jù)塊作為多個(gè)用戶共享的資源，只需有讀者運(yùn)用時(shí)就不允許任享的資源，只需有讀者運(yùn)用時(shí)就不允許任何一個(gè)寫者運(yùn)用。當(dāng)一個(gè)寫者運(yùn)用時(shí)，不何一個(gè)寫者運(yùn)用。當(dāng)一個(gè)寫者運(yùn)用時(shí)，不允許其它寫者或讀者運(yùn)用。因此，可以將允許其它寫者或讀者運(yùn)用。因此，可以將數(shù)據(jù)塊訪問的程序視為臨界區(qū)。但是，數(shù)數(shù)據(jù)塊訪問的程序視為臨界區(qū)。但是，數(shù)據(jù)塊不是絕對的臨界資源，由于它允許多據(jù)塊不是絕對的臨界資源，由于它允許多個(gè)讀者用戶同時(shí)運(yùn)用。個(gè)讀者用戶同時(shí)運(yùn)用。 這一問題是由這一問題是由CourtoisCourtois等人提出理等

25、人提出理處理方案。首先，運(yùn)用一個(gè)互斥信號量處理方案。首先，運(yùn)用一個(gè)互斥信號量mutexmutex，實(shí)現(xiàn)讀者與寫者、寫者與寫者之間，實(shí)現(xiàn)讀者與寫者、寫者與寫者之間的互斥。由于讀者可以同時(shí)訪問數(shù)據(jù)塊，的互斥。由于讀者可以同時(shí)訪問數(shù)據(jù)塊，因此我們讓第一個(gè)預(yù)備進(jìn)入臨界區(qū)的讀者，因此我們讓第一個(gè)預(yù)備進(jìn)入臨界區(qū)的讀者，經(jīng)過經(jīng)過P Pmutexmutex侵占臨界資源，以便排斥侵占臨界資源，以便排斥寫者訪問。當(dāng)最后一個(gè)讀者分開臨界區(qū)時(shí)，寫者訪問。當(dāng)最后一個(gè)讀者分開臨界區(qū)時(shí)，經(jīng)過經(jīng)過V Vmutexmutex將臨界資源釋放，以便其將臨界資源釋放，以便其它用戶運(yùn)用。它用戶運(yùn)用。 其次，設(shè)計(jì)一個(gè)專為讀者共享的變其次

26、，設(shè)計(jì)一個(gè)專為讀者共享的變量量countercounter，讓它記錄讀數(shù)據(jù)塊的人數(shù)。，讓它記錄讀數(shù)據(jù)塊的人數(shù)。CounterCounter應(yīng)視為臨界資源，應(yīng)有一個(gè)互斥信應(yīng)視為臨界資源，應(yīng)有一個(gè)互斥信號量，比如號量，比如RmutexRmutex。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM程序構(gòu)造如下：程序構(gòu)造如下： var mutex: Semaphore := 1, Rmutex: Semaphore : var mutex: Semaphore := 1, Rmutex: Semaphore : = 1;

27、= 1; var counter: Integer := 0 ; var counter: Integer := 0 ; Parbegin Writer(i) Parbegin Writer(i)；Reader(j)Reader(j)； Parend.Parend. Procedure Writer(i) Procedure Writer(i) Begin Begin while (true) while (true) Begin Begin caculate_an_data(); caculate_an_data();/計(jì)算一個(gè)數(shù)據(jù)計(jì)算一個(gè)數(shù)據(jù) P(mutex);P(mutex); Writ

28、e_the_data(); Write_the_data();/臨界區(qū)臨界區(qū) V(mutex);V(mutex); End; End; End End；操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERMProcess Reader(j) Begin While (true) Begin P(Rmutex); If counter=0 then P(mutex); counter = counter+1; V(Rmutex); Read_operation();/臨界區(qū) P(Rmutex); If counter=1

29、 then V(mutex); counter = counter-1; V(Rmutex); End;End;操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM哲學(xué)家用餐問題哲學(xué)家用餐問題 在該問題中想象有5位哲學(xué)家，他們共同坐在一張餐桌前用餐，用餐過后開場思索問題。他們的生活方式可描畫為一個(gè)單調(diào)的循環(huán)：思索-饑餓-用餐-再思索。知餐桌上擺的是面條，每個(gè)人必需左右手各拿到一把叉子才可以開場進(jìn)餐。而餐桌上只需5把叉子，任兩個(gè)哲學(xué)家之間有一把，見圖所示。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng)

30、操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM第i位哲學(xué)家的行為過程可描畫為下面的方式。 Process Philosopher ( i ) Begin While (true) Begin Thinking( ); P(mutexi);/懇求左叉子 P(mutexi+1 mod 5); /懇求右叉子 E a t i n g ( ) ; /用餐過程 V(mutexi); /釋放左叉子 V(mutexi+1 mod 5);/釋放右叉子 End; End;操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYST

31、ERM4.4.3 4.4.3 信號量集機(jī)制信號量集機(jī)制該機(jī)制可分為兩類：AND型信號量集機(jī)制和普通型信號量集機(jī)制。 一、AND型信號量集機(jī)制這種機(jī)制中，讓P原語具有同時(shí)給多個(gè)信號量減1的功能。不過，它要先判別各個(gè)信號量能否都是“綠燈。假設(shè)是，那么將各個(gè)信號量的值減1，立刻進(jìn)入臨界區(qū)。假設(shè)其中至少有一個(gè)信號量是“紅燈，進(jìn)程就要讓權(quán)等待。并將P原語的第1條指令作為斷點(diǎn)地址，保管到該進(jìn)程的PCB信息維護(hù)區(qū)中，等恢復(fù)運(yùn)轉(zhuǎn)時(shí)重執(zhí)P原語。 二、普通型信號量集機(jī)制 我們?yōu)槊恳环N臨界資源設(shè)一個(gè)記錄型信號量Si，并讓Si的值域表示當(dāng)前的可用資源數(shù)量。當(dāng)一個(gè)進(jìn)程根據(jù)需求，一次性地懇求Si類型的資源di臺時(shí)，可讓它

32、的P原語作Si = Si - di 操作。 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM3種信號量機(jī)制進(jìn)展比較 整型信號量機(jī)制比較簡單，適用面較窄 記錄型信號量機(jī)制較為靈敏，可用于多種同步場所 信號量集機(jī)制可以簡化運(yùn)用程序的設(shè)計(jì)，但系統(tǒng)的開銷較大 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.5 4.5 管程管程 這是一種具有面向?qū)ο蟪绦蛟O(shè)計(jì)思想的同步機(jī)制。它提供了與信號量機(jī)制一樣的功能。管程Monitor概念是著名學(xué)者H

33、ore于1974年提出的，并在很多系統(tǒng)中得到實(shí)現(xiàn)，諸如Pascal、Java、Modula-3等。 管程是由部分?jǐn)?shù)據(jù)構(gòu)造、多個(gè)處置過程和一套初始化代碼組成的模塊。 管程的特征為： 1管程內(nèi)的數(shù)據(jù)構(gòu)造只能被管程內(nèi)的過程訪問，任何外部訪問都是不允許的； 2進(jìn)程可經(jīng)過調(diào)用管程的一個(gè)過程進(jìn)入管程； 3任何時(shí)間只允許一個(gè)進(jìn)程進(jìn)入管程，其他要求進(jìn)入管程的進(jìn)程統(tǒng)統(tǒng)被阻塞到等待管程的隊(duì)列上。 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM以下圖是管程的一個(gè)構(gòu)造模型操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng)

34、操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERMl Pc：當(dāng)遇到同步約束，就將進(jìn)程阻塞在條件變量c關(guān)聯(lián)的等待隊(duì)列上。l Vc：從條件變量c關(guān)聯(lián)的等待隊(duì)列上喚醒一個(gè)進(jìn)程，讓它恢復(fù)運(yùn)轉(zhuǎn)。假設(shè)隊(duì)列上沒有進(jìn)程在等待，就什么也不做。管程的言語構(gòu)造可描畫為下屬方式： Type 管程名 = Monitor Begin 數(shù)據(jù)構(gòu)造定義； 部分變量定義； 條件變量定義； Porcedure 過程名方式參數(shù) Begin / 過程體 End; End;操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM利用管程PC處理消費(fèi)

35、者-消費(fèi)者問題的算法如下。Procedure Producer() Begin Var char: x; While (true) Begin Produce_an_item_in_x(); PUT(x); End; End;Procedure Consumer() Begin Var char: x; While (true) Begin GET(x); Consume_the_item_in_x(); End End;操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.6 4.6 進(jìn)程通訊進(jìn)程通訊4.1.1

36、4.1.1 共享存儲器系統(tǒng)共享存儲器系統(tǒng) 這種通訊需求在內(nèi)存中開辟一個(gè)共享的存儲空這種通訊需求在內(nèi)存中開辟一個(gè)共享的存儲空間，供進(jìn)程之間進(jìn)展數(shù)據(jù)傳送。比如計(jì)算進(jìn)程將間，供進(jìn)程之間進(jìn)展數(shù)據(jù)傳送。比如計(jì)算進(jìn)程將所得的結(jié)果送入內(nèi)存共享區(qū)的緩沖區(qū)環(huán)中，打印所得的結(jié)果送入內(nèi)存共享區(qū)的緩沖區(qū)環(huán)中，打印進(jìn)程從中將結(jié)果取出來，就是一個(gè)利用共享存儲進(jìn)程從中將結(jié)果取出來，就是一個(gè)利用共享存儲器進(jìn)展通訊的例子。這種通訊方式在器進(jìn)展通訊的例子。這種通訊方式在UNIXUNIX、LinuxLinux、WindowsWindows及及OS/2OS/2等系統(tǒng)中都有詳細(xì)的實(shí)現(xiàn)。等系統(tǒng)中都有詳細(xì)的實(shí)現(xiàn)。 共享存儲器系統(tǒng)中，共享的

37、空間普通該當(dāng)是共享存儲器系統(tǒng)中，共享的空間普通該當(dāng)是需求互斥訪問的臨界資源。諸多進(jìn)程為了防止喪需求互斥訪問的臨界資源。諸多進(jìn)程為了防止喪失數(shù)據(jù)或反復(fù)取數(shù)，需求執(zhí)行特定的同步協(xié)議。失數(shù)據(jù)或反復(fù)取數(shù)，需求執(zhí)行特定的同步協(xié)議。 在利用共享存儲器進(jìn)展通訊之前，信息的發(fā)在利用共享存儲器進(jìn)展通訊之前，信息的發(fā)送者和接納者都要將共享空間納入到本人的虛地送者和接納者都要將共享空間納入到本人的虛地址空間中，讓它們都能訪問該區(qū)域。存儲器管理址空間中，讓它們都能訪問該區(qū)域。存儲器管理模塊將共享空間映射成實(shí)踐的內(nèi)存空間。模塊將共享空間映射成實(shí)踐的內(nèi)存空間。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng)

38、 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM1創(chuàng)建或刪除共享存儲區(qū)2共享存儲區(qū)的附接與斷接 3共享存儲區(qū)形狀查詢 4共享存儲區(qū)管理 共享存儲器系統(tǒng)的特點(diǎn)： 利用共享存儲器系統(tǒng)進(jìn)展通訊的效率特別高，適用于通訊速度要求特別高的場所。 這種同步與互斥機(jī)制的實(shí)現(xiàn)普通要由程序員來承當(dāng)，系統(tǒng)僅僅提供一個(gè)共享內(nèi)存空間的管理機(jī)制。 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.6.2 管道通訊 管道Pipe是可供進(jìn)程共享的一種外存文件，主要用于銜接一個(gè)寫入進(jìn)程和一個(gè)讀出進(jìn)程，以實(shí)現(xiàn)它們之間的數(shù)據(jù)通訊

39、。寫入進(jìn)程按字符流的方式將數(shù)據(jù)寫入管道文件中，讓讀出進(jìn)程從中獲得數(shù)據(jù)。由于管道機(jī)制特別適用于大容量數(shù)據(jù)的通訊，因此在許多操作系統(tǒng)中被采用。管道通訊機(jī)制中的協(xié)調(diào)內(nèi)容包括： 1互斥問題。 2同步問題 3形狀測試 管道通訊機(jī)制分為無名管道和有名管道 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.6.3 4.6.3 音訊傳送音訊傳送 系統(tǒng)中的進(jìn)程在交互傳送數(shù)據(jù)時(shí)，涉及到對數(shù)據(jù)構(gòu)造的互斥運(yùn)用問題。為實(shí)施互斥，進(jìn)程之間需求同步。提供這寫功能的一個(gè)好方法是音訊傳送。還有一個(gè)優(yōu)點(diǎn)是，音訊傳送可較容易地在單處置機(jī)系統(tǒng)、分布式

40、系統(tǒng)、共享存儲器的多處置機(jī)系統(tǒng)中實(shí)現(xiàn)。 音訊傳送中的管理機(jī)制由操作系統(tǒng)提供，主要表達(dá)為以下兩個(gè)原語。 發(fā)送原語：send(destination, message)，其中，destination為音訊的目的地接納進(jìn)程名。該原語表示發(fā)送音訊到進(jìn)程destination。 接納原語：receive(source, message)，其中，source是音訊發(fā)出地發(fā)送進(jìn)程名。該原語表示從進(jìn)程source接納音訊。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM一、實(shí)現(xiàn)同步的方法一、實(shí)現(xiàn)同步的方法 在這種方式中要處理的關(guān)

41、鍵問題依然是同步問題：僅當(dāng)一條音訊從某個(gè)進(jìn)程發(fā)送后，其他進(jìn)程才能夠接納到音訊。那么，音訊發(fā)送者經(jīng)過send原語發(fā)出一條音訊后，該當(dāng)如何處置呢？有兩種選擇：要么將發(fā)送進(jìn)程阻塞起來，直到音訊被接納為止，再把它喚醒；要么不阻塞發(fā)送進(jìn)程。 同樣地，音訊接納者經(jīng)過receive原語要接納一條音訊時(shí)，假設(shè)能立刻收到，可繼續(xù)運(yùn)轉(zhuǎn)。假設(shè)音訊尚未發(fā)出的話，也有兩種選擇：要么阻塞發(fā)送進(jìn)程等待音訊；要么不阻塞發(fā)送進(jìn)程，放棄接納。 這樣一來，系統(tǒng)可選擇的處置有以下幾種： 會合renezvous方式 寬松同步方式 不阻塞發(fā)送者，只阻塞接納者方式 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二

42、十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM二、直接通訊和間接通訊二、直接通訊和間接通訊 在音訊傳送中，發(fā)送者需求明確音訊發(fā)往哪里，接納者需求指明音訊的來源。通常，按send和receive原語的實(shí)現(xiàn)方式可分為直接尋址和間接尋址兩類。 1. 直接尋址Direct Addressing 實(shí)現(xiàn)直接尋址的一個(gè)較為簡單的方案是，讓send原語明確指出接納者的進(jìn)程號，receive原語明確指出發(fā)送者的進(jìn)程號，系統(tǒng)根據(jù)這兩個(gè)原語實(shí)現(xiàn)直接通訊。這種一對一的通訊，用來處置并發(fā)進(jìn)程之間的協(xié)作是相當(dāng)有效的。 2. 間接尋址Indirect Addressing 在間接尋址方式中，音訊并不直接從發(fā)送進(jìn)程

43、傳到接納進(jìn)程，而是要經(jīng)過一個(gè)中間介質(zhì)暫時(shí)保管音訊的隊(duì)列，通常稱為“信箱。因此，兩個(gè)通訊進(jìn)程的操作是，一個(gè)進(jìn)程將音訊發(fā)到信箱中，另一個(gè)從信箱中取音訊。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.7 4.7 死死 鎖鎖 死鎖死鎖Dead LockDead Lock，是指系統(tǒng)中存在一組進(jìn)程，是指系統(tǒng)中存在一組進(jìn)程，其中每一個(gè)進(jìn)程都在等待組內(nèi)別的進(jìn)程占有的資源，其中每一個(gè)進(jìn)程都在等待組內(nèi)別的進(jìn)程占有的資源，這樣一來，該組進(jìn)程都不能向前推進(jìn)，墮入等待形狀。這樣一來，該組進(jìn)程都不能向前推進(jìn)，墮入等待形狀。 系統(tǒng)死鎖系

44、統(tǒng)死鎖, ,是系統(tǒng)中是系統(tǒng)中n nn1n1個(gè)進(jìn)程因資源懇求個(gè)進(jìn)程因資源懇求得不到滿足，皆無法運(yùn)轉(zhuǎn)而出現(xiàn)的一種無限期等待景得不到滿足，皆無法運(yùn)轉(zhuǎn)而出現(xiàn)的一種無限期等待景象。這是一種極其浪費(fèi)的景象，它給系統(tǒng)帶來的損失象。這是一種極其浪費(fèi)的景象，它給系統(tǒng)帶來的損失有時(shí)比出現(xiàn)某些硬件缺點(diǎn)還要大。假設(shè)不給予有效地有時(shí)比出現(xiàn)某些硬件缺點(diǎn)還要大。假設(shè)不給予有效地制止，這種形狀將永遠(yuǎn)不能終了。制止，這種形狀將永遠(yuǎn)不能終了。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.7.1 4.7.1 產(chǎn)生死鎖的緣由產(chǎn)生死鎖的緣由 當(dāng)系統(tǒng)

45、同時(shí)滿足以下4個(gè)必要條件時(shí)，會產(chǎn)生死鎖。 (1) 互斥條件。 進(jìn)程懇求的資源屬于臨界資源，每一瞬間只能由一個(gè)進(jìn)程運(yùn)用。假設(shè)有多個(gè)進(jìn)程同時(shí)懇求運(yùn)用同一個(gè)臨界資源時(shí)，只能允許一個(gè)運(yùn)用，其它進(jìn)程等待。 (2) 不剝奪條件。進(jìn)程獲得某資源后，便不斷占有它，直到用完為止才可以釋放。其它進(jìn)程不可以剝奪某個(gè)進(jìn)程已占有的資源，即使該進(jìn)程目前無法運(yùn)轉(zhuǎn)。 (3) 懇求和堅(jiān)持條件。允許一個(gè)進(jìn)程在堅(jiān)持已有資源不放棄的情況下，進(jìn)一步懇求新資源，當(dāng)懇求資源得不到滿足而被阻塞時(shí)，也不會釋放已占有的資源。 (4) 環(huán)路條件。 一組進(jìn)程P1,Pn的占有資源情況與懇求資源情況構(gòu)成了一個(gè)環(huán)型鏈，比如P1等待P2的資源，P2等待P3

46、的資源Pn等待P1的資源。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM定義：資源分配圖定義：資源分配圖G=NG=E是一個(gè)有向圖，是一個(gè)有向圖，N N是結(jié)點(diǎn)集，是結(jié)點(diǎn)集，E E是邊集。其中：是邊集。其中： N=PR N=PR，P P為進(jìn)程集，為進(jìn)程集，R R為資源集。為資源集。 E=E1E2 E=E1E2，E1E1為資源占有邊集，為資源占有邊集，E2E2為資源懇求為資源懇求邊集。邊集。 我們用圓圈表示進(jìn)程我們用圓圈表示進(jìn)程pPpP、矩形表示資源、矩形表示資源rRrR，同時(shí)，用，同時(shí)，用rprp表示資源表示資源r

47、 r被進(jìn)程被進(jìn)程p p占有，占有，prpr表示進(jìn)程表示進(jìn)程p p懇求資源懇求資源r r。那么兩個(gè)進(jìn)程那么兩個(gè)進(jìn)程P1P1和和P2P2競爭資源競爭資源R1R1和和R2R2，及，及P1P1、P2P2和和P3P3競競爭爭R1R1、R2R2和和R3R3的環(huán)路如下圖。的環(huán)路如下圖。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.7.2 4.7.2 死鎖預(yù)防死鎖預(yù)防 預(yù)防死鎖的主要任務(wù)就是使系統(tǒng)不斷堅(jiān)持在平安形狀下運(yùn)轉(zhuǎn)。預(yù)防措施可從死鎖的4個(gè)必要條件去思索。 1資源靜態(tài)分配方案 2. 資源可剝奪方案 3. 資源有序運(yùn)用方案操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM4.7.3 4.7.3 死鎖防止死鎖防止一、平安形狀 為了研討如何防止死鎖，我們先來看一下系統(tǒng)的形狀變化情況。比如，有兩個(gè)進(jìn)程P1和P2競爭資源R1和R2，如圖。操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操 作 系 統(tǒng) 操作系統(tǒng)二十一世紀(jì)計(jì)算機(jī)本科教育OPERATING SYSTERM二、銀行家算法二、銀行家算法 該算法需求建立多種數(shù)據(jù)構(gòu)造予以支持，分別為：可用資源數(shù)組