同步和同步機(jī)制

一個(gè)進(jìn)程在某一特殊點(diǎn)上被迫停止執(zhí)行直到接收到一個(gè)對應(yīng)的特殊變量值，通過特殊變量這一設(shè)施，任何復(fù)雜的進(jìn)程交互要求可得到滿足，這種特殊變量就是信號量(semaphore)。在操作系統(tǒng)中，信號量用以表示物理資源的實(shí)體，它是一個(gè)與隊(duì)列有關(guān)的整型變量。實(shí)現(xiàn)時(shí)，信號量是一種變量類型，常常用一個(gè)記錄型數(shù)據(jù)結(jié)構(gòu)表示，它有兩個(gè)分量：一個(gè)是信號量的值，另一個(gè)是信號量隊(duì)列的隊(duì)列指針。

原語是操作系統(tǒng)中執(zhí)行時(shí)不可中斷的過程、即原子操作(atomicoperation)。Dijkstra 發(fā)明了兩個(gè)信號量操作原語：P 操作和V 操作(荷蘭語中“測試(Proberen)”和“增量(Verhogen)”的頭字母)，此外，還常用的符號有：wait 和signal；up 和down；sleep 和wakeup 等。利用信號量和P、V 操作既可以解決并發(fā)進(jìn)程的競爭問題，又可以解決并發(fā)進(jìn)程的協(xié)作問題。

信號量按其用途可分為兩種：

􀁺 公用信號量：聯(lián)系一組并發(fā)進(jìn)程，相關(guān)的進(jìn)程均可在此信號量上執(zhí)行P 和V操作。初值常常為1，用于實(shí)現(xiàn)進(jìn)程互斥。

􀁺 私有信號量：聯(lián)系一組并發(fā)進(jìn)程，僅允許此信號量擁有的進(jìn)程執(zhí)行P 操作，而其他相關(guān)進(jìn)程可在其上施行V 操作。初值常常為0 或正整數(shù)，多用于并發(fā)進(jìn)程同步。

信號量按其取值可分為兩種：

􀁺 二元信號量：僅允許取值為0 和1，主要用于解決進(jìn)程互斥問題。

􀁺 一般信號量：允許取值為非負(fù)整數(shù)，主要用于解決進(jìn)程同步問題。

1、整型信號量

設(shè) s 為一個(gè)正×××量，除初始化外，僅能通過P、V 操作來訪問它，這時(shí)P 操作原語和V 操作原語定義如下：。

􀁺 P(s)：當(dāng)信號量s 大于0 時(shí)，把信號量s 減去l，否則調(diào)用P(s)的進(jìn)程等待直到信號量s 大于0 時(shí)。

􀁺 V(s)：把信號量s 加1。P(s)和V(s)可以寫成：

P(s)：while s≤0 do null operation

s:=s-1；

V(s)： s:=s+1；

整型信號量機(jī)制中的P 操作，只要信號量s<=0，就會(huì)不斷測試，進(jìn)程處于“忙式等待”。后來對整型信號量進(jìn)行了擴(kuò)充，增加了一個(gè)等待s 信號量所代表資源的等待進(jìn)程的隊(duì)列，以實(shí)現(xiàn)讓權(quán)等待，這就是下面要介紹的記錄型信號量機(jī)制。

2、記錄型信號量

設(shè) s 為一個(gè)記錄型數(shù)據(jù)結(jié)構(gòu)，其中一個(gè)分量為×××量value，另一個(gè)分量為信號量隊(duì)列queue，value 通常是一個(gè)具有非負(fù)初值的整型變量，queue 是一個(gè)初始狀態(tài)為空的進(jìn)程隊(duì)列。這時(shí)P 操作原語和V 操作原語的定義修改如下：

􀁺 P(s)：將信號量s 減去l，若結(jié)果小于0，則調(diào)用P(s)的進(jìn)程被置成等待信號量s 的狀態(tài)。

􀁺 V(s)：將信號量s 加1，若結(jié)果不大于0，則釋放一個(gè)等待信號量s 的進(jìn)程。

記錄型信號量和P 操作、V 操作可表示成如下的數(shù)據(jù)結(jié)構(gòu)和不可中斷過程：

type semaphore=record

value:integer;

queue: list of process;

end

procedure P(var s:semaphore);

begin

s.value:= s.value – 1; ? ? /* 把信號量減去1 */

if s.value< 0 then W(s.queue); ? ? /* 若信號量小于0，則執(zhí)行P(s)的進(jìn)程調(diào)用 W(s.queue) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 進(jìn)行自我封鎖，被置成等待信號量s 的狀態(tài)，進(jìn)入信號量隊(duì)列queue*/

end;

procedure V(var s:semaphore);

begin

s.value:= s.value + 1; ? ? /* 把信號量加1 */

if s.value≤ 0 then R(s.queue); ? ?/* 若信號量小于等于0，則調(diào)用R(s.queue)從信號量s 隊(duì) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?列queue 中釋放一個(gè)等待信號量s 的進(jìn)程并置成就緒態(tài)*/

end;

其中W(s.queue)表示把調(diào)用過程的進(jìn)程置成等待信號量s 的狀態(tài)，并鏈入s 信號量隊(duì)列，同時(shí)釋放CPU；R(s.queue)表示釋放一個(gè)等待信號量s 的進(jìn)程，從信號量s 隊(duì)列中移出一個(gè)進(jìn)程，置成就緒態(tài)并投入就緒隊(duì)列。進(jìn)程按照什么次序從隊(duì)列中移出?公平的策略是先進(jìn)先出法，被阻塞時(shí)間最久的進(jìn)程最先從隊(duì)列釋放，該策略能保證進(jìn)程不會(huì)被餓死。

3、二元信號量

設(shè) s 為一個(gè)記錄型數(shù)據(jù)結(jié)構(gòu)，其中一個(gè)分量為value，它僅能取值0 和1，另一個(gè)分量為信號量隊(duì)列queue，這時(shí)可以把二元(binary)信號量上的P、V 操作記為BP 和BV，其定義如下：

type binary semaphore=record

value(0,1);

queue: list of process

end;

procedure BP(var s:semaphore);

if s.value=1;

then

s.value=0;

else begin

w(s.queue);

end;

procedure BV(var s:semaphore);

if s.queue is empty;

then

s.value:=1;

else begin

R(s.queue);

end;

雖然二元信號量僅能取0 和1 值，但可以證明它與記錄型信號量一樣，有著同等的表達(dá)能力。下面來看一下，如何用二元信號量實(shí)現(xiàn)記錄型信號量。

var

s1: binary-semaphore;

s2: binary-semaphore;

c:integer;

其中，初始化為s1=1，s2=0，c 被賦予記錄型信號量s 所需的值，那么，在記錄型信號量s 上的P、V 操作定義為：

P(s) ： ? ? ? ? ? ? ? ? ? ? ? ? ? ?V(s)：

begin ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? begin

BP(s1); ? ? ? ? ? ? ? ? ? ? ? ? ? ? BP(s1);

c:=c-1; ? ? ? ? ? ? ? ? ? ? ? ? ? ? c:=c+1;

if c<0 then BP(s2); ? ? ? ? ? ? ? ? if c≤0 then BV(s2);

BV(s1); ? ? ? ? ? ? ? ? ? ? ? ? ? ? BV(s1);

end ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? end

實(shí)際上把記錄型信號量s 所需的值放到c 上，把P、V 操作中對信號量s 的增、減變成為對c 的增、減，把本來應(yīng)該在s 隊(duì)列上掛起的進(jìn)程改為掛在s2 信號量上。信號量s1 的初值為1，用作為操作c 變量時(shí)的互斥信號量。

用記錄型信號量實(shí)現(xiàn)互斥

記錄型信號量和 P、V 操作可以用來解決進(jìn)程互斥問題。與TS 指令相比較，P、V操作也是用測試信號量的辦法來決定是否能進(jìn)入臨界區(qū)，但不同的是P、V 操作只對信號量測試一次，而用TS 指令則必須反復(fù)測試。用信號量和P、V 操作管理幾個(gè)進(jìn)程互斥進(jìn)入臨界區(qū)的一般形式如下：

Var mutex: semaphore;

mutex := 1;

cobegin

……

process Pi

begin

……

P(mutex);

臨界區(qū)；

V(mutex);

……

end;

……

coend;

下面的程序用記錄型信號量和P、V 操作解決了飛機(jī)票售票問題。

Var A : ARRAY[1..m] of integer;

mutex : semaphore;

mutex:= 1;

cobegin

process Pi

var Xi:integer;

begin

L1:

按旅客定票要求找到A[j];

P(mutex);

Xi := A[j];

if Xi>=1

then begin

Xi:=Xi-1;A[j]:=Xi;

V(mutex);{輸出一張票}；

end;

else begin

V(mutex);{輸出“票已售完”}；

end;

goto L1;

end;

coend.

Var A : ARRAY[1..m] of integer;

s : ARRAY[1..m] of semaphore;

s[j] := 1;

cobegin

process Pi

var Xi:integer;

begin

L1:

按旅客定票要求找到A[j];

P(s[j]);

Xi := A[j];

if Xi>=1

then begin

Xi:=Xi-1;A[j]:=Xi;

V(s[j]);{輸出一張票};

end;

else begin

V(s[j]);{輸出“票已售完”}；

end;

goto L1;

end;

coend.

記錄型信號量解決生產(chǎn)者-消費(fèi)者問題

記錄型信號量和 P、V 操作不僅可以解決進(jìn)程的互斥，而且更是實(shí)現(xiàn)進(jìn)程同步的有力工具。進(jìn)程的同步是指一個(gè)進(jìn)程的執(zhí)行依賴于另一個(gè)進(jìn)程的信號或消息，當(dāng)一個(gè)進(jìn)程沒有得到來自于另一個(gè)進(jìn)程的信號或消息時(shí)則等待，直到信號或消息到達(dá)才被喚醒。生產(chǎn)者和消費(fèi)者問題就是一個(gè)典型的進(jìn)程同步問題，出現(xiàn)不正確結(jié)果的原因在于它們訪問緩沖器的相對速率。為了能使它們正確工作，生產(chǎn)者和消費(fèi)者必須按一定的生產(chǎn)率和消費(fèi)率來訪問共享的緩沖器。用P、V 操作來解決生產(chǎn)者和消費(fèi)者共享一個(gè)緩

沖器的問題，可以使用兩個(gè)信號量empty 和full，它們的初值分別為1 和0，empty 指示能否向緩沖器內(nèi)存放產(chǎn)品，full 指示是否能從緩沖器內(nèi)取出產(chǎn)品。于是生產(chǎn)者和消費(fèi)者問題的程序如下所示。

var B : integer;

empty:semaphore; /* 可以使用的空緩沖區(qū)數(shù)*/

full:semaphore; /* 緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)*/

empty:= 1; /* 緩沖區(qū)內(nèi)允許放入一件產(chǎn)品*/

full:= 0; /* 緩沖區(qū)內(nèi)沒有產(chǎn)品*/

cobegin

process producer

begin

L1:

Produce a product;

P(empty);

B := product;

V(full);

Goto L1;

end;

process consumer

begin

L2:

P(full);

Product:= B;

V(empty);

Consume a product;

Goto L2;

end;

coend.

要提醒注意的是P、V 操作使用不當(dāng)?shù)脑?#xff0c;仍會(huì)出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤。例如，有m 個(gè)生產(chǎn)者和n 個(gè)消費(fèi)者，它們共享可存放k 件產(chǎn)品的緩沖器。為了使它們能協(xié)調(diào)的工作，必須使用一個(gè)信號量mutex(初值為1)，以限制它們互斥地對緩沖器進(jìn)行存取，另用兩個(gè)信號量empty(初值為k)和full(初值為0)，以保證生產(chǎn)者不往滿的緩沖器中存產(chǎn)品，消費(fèi)者不從空的緩沖器中取產(chǎn)品。程序如下：

var B : array[0..k-1] of item;

empty:semaphore:=k; /* 可以使用的空緩沖區(qū)數(shù)*/

full:semaphore:=0; /* 緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)*/

mutex:semaphore:=1; /* 互斥信號量

in :integer:= 0; /* 放入緩沖區(qū)指針*/

out :integer:= 0; /* 取出緩沖區(qū)指針*/

cobegin

process producer_i

begin

L1:produce a product;

P(empty);

P(mutex);

B[putptr] := product;

in:=(in+1) mod k;

V(mutex);

V(full);

goto L1;

end;

process consumer_j

begin

L2:P(full);

P(mutex);

Product:= B[out];

out:=(out+1) mod k;

V(mutex);

V(empty);

consume a product;

goto L2;

end;

coend.

記錄型信號量解決讀者-寫者問題

讀者與寫者問題(reader-writer problem)(Courtois，1971)也是一個(gè)經(jīng)典的并發(fā)程序設(shè)計(jì)問題。有兩組并發(fā)進(jìn)程：讀者和寫者，共享一個(gè)文件F，要求：(1)允許多個(gè)讀者可同時(shí)對文件執(zhí)行讀操作；(2)只允許一個(gè)寫者往文件中寫信息；(3)任一寫者在完成寫操作之前不允許其他讀者或?qū)懻吖ぷ?#xff1b;(4)寫者執(zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出。單純使用信號量不能解決讀者與寫者問題，必須引入計(jì)數(shù)器rc 對讀進(jìn)程計(jì)數(shù)，mutex 是用于對計(jì)數(shù)器rc 操作的互斥信號量，W 表示是否允許寫的信號量，于是管理該文件的程序可如下設(shè)計(jì)：

var rc: integer;

W，mutex: semaphore;

rc := 0; /* 讀進(jìn)程計(jì)數(shù) */

W := 1;

mutex := 1;

procedure read;

begin

P(mutex);

rc := rc + 1;

if rc=1 then P(W)；

V(mutex);

讀文件；

P(mutex);

rc := rc - 1;

if rc = 0 then V(W)；

V(mutex);

end;

procedure write;

begin

P(W);

寫文件;

V(W);

end;

cobegin

process readeri;

process writerj;

coend.

process readeri;

begin

read;

end.

process writerj

begin

write;

end.

總結(jié)

以上是生活随笔為你收集整理的计算机操作系统pv实验,计算机操作系统笔记--信号量与PV 操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。