進程間制約關(guān)系

操作系統(tǒng)第8課進程間的制約關(guān)系今日內(nèi)容進程的互斥進程的同步信號量和P、V操作內(nèi)容回顧:進程間的制約關(guān)系進程的并發(fā)，使一個進程何時占有處理機、占有多長時間、執(zhí)行速度的快慢、以及外界對進程產(chǎn)生作用等都帶有隨機性。因此，一個進程對其他進程的影響無法預測。進程間存在制約關(guān)系。間接制約直接制約共享變量修改引起的沖突一個飛機售票系統(tǒng)，兩個終端，運行兩個進程：例：對輸入井文件目錄的管理

為輸出井設置一張“輸出井文件目錄表”，它由若干目錄項組成。每個目錄項記錄一個要打印輸出的文件名以及該文件在磁盤的存放地址。兩個指針：out和in。兩個程序：“井管理寫程序”根據(jù)in的指點存放要求輸出的文件目錄信息，in總是指向下一個可用的目錄項位置?！熬忀敵龀绦颉备鶕?jù)out的指點進行打印，out總是指向下一個被打印的文件。bit.txt45674out7in輸出井文件目錄表例：通過雙緩沖區(qū)復制文件編寫一個復制n個記錄的程序，它把文件F中的每個記錄依次讀到輸入緩沖區(qū)R，再從R拷貝到輸出緩沖區(qū)T，最后寫到文件G中。假定R和T正好存放一個記錄。寫3個子程序作為進程來完成整個工作：GET：從文件F按照順序讀出一個記錄，然后送入輸入緩沖區(qū)R；COPY：把輸入緩沖區(qū)R里的記錄拷貝到輸出緩沖區(qū)T里；PUT：從輸出緩沖區(qū)T里讀出一個記錄，然后依照順序?qū)懭胛募礼。記錄1記錄2記錄nGETCOPYPUT文件F記錄1記錄2記錄n文件G輸入緩沖區(qū)R輸出緩沖區(qū)T例：通過雙緩沖區(qū)復制文件在復制過程中，若COPY已把R里的記錄拷貝到了T中，那么GET和PUT就可以并發(fā)執(zhí)行了。即GET從F里讀出下一個記錄送到R中的操作，與PUT從T中取出里面的內(nèi)容寫入G的操作，誰先做誰后做都沒有關(guān)系，不會影響到復制結(jié)果的正確性。由于利用了它們并發(fā)性，工作效率就會提高。但是，如果不去顧及這三者之間執(zhí)行順序的這種關(guān)系，隨意讓GET、COPY、PUT去并發(fā)執(zhí)行，那么就會產(chǎn)生錯誤。

記錄1記錄2記錄nGETCOPYPUT文件F記錄1記錄2記錄n文件G輸入緩沖區(qū)R輸出緩沖區(qū)T若不管GET、COPY、PUT的執(zhí)行關(guān)系，那么可有六種執(zhí)行可能：

1）COPY→PUT→GET；2）COPY→GET→PUT；3）PUT→COPY→GET4）PUT→GET→COPY；5）GET→COPY→PUT；6）GET→PUT→COPY.記錄3記錄4記錄n文件F記錄2記錄1文件GRT記錄1GETPUT記錄1記錄1文件GRT記錄3記錄4記錄n文件F記錄1記錄4記錄n文件F記錄3記錄1文件GRT記錄1COPY記錄1記錄4記錄n文件F記錄3記錄3文件GRT記錄1123(2)(3)(1)(4)進程的互斥共享變量在操作系統(tǒng)中，把那些可以被進程共享的資源（如文件、隊列、緩沖區(qū)、表格、變量等）統(tǒng)稱為“共享變量”或“臨界資源”。互斥與一個共享變量（或臨界資源）交往的多個進程，為了保證它們各自運行結(jié)果的正確性，當其中的一個進程正在對該變量（或臨界資源）進行操作時，就不允許其他進程同時對它進行操作。進程間的這種制約關(guān)系被稱為“互斥”。臨界區(qū)把進程程序中“真正需要保證互斥執(zhí)行”的程序，稱為該進程的“臨界區(qū)（或臨界段）”。一個飛機售票系統(tǒng)，兩個終端，運行兩個進程：臨界區(qū)a:=a-1print(a)a:=a+1print(a)P1互斥P2互斥Ifa<0thena:=a+1elsea:=a-1P3互斥

進程的互斥（間接作用）使用臨界區(qū)的原則：（一組并發(fā)進程互斥執(zhí)行時應滿足的準則，保證使用共享數(shù)據(jù)的進程能夠正確和高效地運行）有空讓進：當無進程在臨界區(qū)時，任何有權(quán)使用臨界區(qū)的進程之一可進入無空等待：已有進程在臨界區(qū)，其它欲進入臨界區(qū)的進程需等待有限等待：任何進入臨界區(qū)的要求應在有限的時間內(nèi)得到滿足讓權(quán)等待：處于等待狀態(tài)的進程應放棄占用CPU，以使其他進程有機會得到CPU的使用權(quán)協(xié)同工作——進程同步從文件F取出一個記錄送至輸入緩沖區(qū)R向COPY發(fā)送“可以拷貝”的消息等待COPY發(fā)來的“拷貝結(jié)束”的消息等待GET發(fā)來“可以拷貝”的消息將輸入緩沖區(qū)R里的記錄拷貝到輸出緩沖區(qū)T里向GET發(fā)送“拷貝結(jié)束”的消息GETCOPY.3.3.例：GET和COPY間的協(xié)調(diào)一致GET讀記錄到R后，給COPY發(fā)送消息，告訴它R中已有記錄，然后暫停下來，等待COPY發(fā)來“拷貝結(jié)束”的消息，只有接到這個消息，GET才能去做下一步工作。相對地，COPY也一直處于等待。只有接到GET發(fā)送來“可以拷貝”的消息才能工作，將R里的記錄拷貝到T里，然后向GET發(fā)“拷貝結(jié)束”的消息，隨之又等待GET發(fā)消息。同步、同步點、同步條件一組并發(fā)進程因直接制約而互相發(fā)送消息，進行互相合作，互相等待，使得各進程按一定的速度執(zhí)行的過程稱為進程間的同步。進程暫停等待以取得同步的那一點，稱為“同步點”。一個進程需要等待另一個進程完成的操作或發(fā)送的信息，稱為“同步條件”。實現(xiàn)進程互斥和同步的方法1、進程互斥的軟件方法通過平等協(xié)商方式實現(xiàn)進程互斥的最初方法是軟件方法其基本思路是在進入?yún)^(qū)檢查和設置一些標志，如果已有進程在臨界區(qū)，則在進入?yún)^(qū)通過循環(huán)檢查進行等待；在退出區(qū)修改標志其中的主要問題是設置什么標志和如何檢查標志軟件解法之一free:表示臨界區(qū)標志

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

false:無進程在臨界區(qū)(初值)

....

while(free);

free=true;

臨界區(qū)

free=false;2、硬件方法：TSL（“測試并上鎖”）指令

借助一條硬件指令來實現(xiàn)互斥的同步機構(gòu)。TSL指令：包括讀數(shù)和寫數(shù)兩個操作。enter_region;

臨界區(qū)

leave_region;3、信號量及P.V操作1965年，由荷蘭學者Dijkstra提出（所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)），是一種卓有成效的進程同步機制。1、信號量semphore（sem）操作系統(tǒng)中，信號量sem是一整數(shù)，大于等于0時代表可供并發(fā)進程使用的資源實體；小于0時則表示正在等待使用臨界區(qū)的進程數(shù)。信號量的使用：

通過初始化和兩個標準原語來訪問。1、必須置一次且只能置一次初值；初值不能為負數(shù)

2、只能執(zhí)行P、V操作2、P、V原語操作P(sem){

sem.value--;//表示申請一個資源

if(sem.value<0)//表示無可用資源

{

將該進程狀態(tài)置為等待狀態(tài)并將該進程插入與該信號相對應的等待隊列中;

}else//表示還有可用資源

{進程繼續(xù)運行}}V(sem){

sem.value++;//表示釋放一個資源

if(sem.value<=0)//表示有等待使用資源的進程

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

}

進程繼續(xù)運行或轉(zhuǎn)進程調(diào)度程序}用P、V操作解決進程間互斥問題為臨界資源設置一個互斥信號量mutex，并設初值（有幾個共享資源初值就為幾）；在每個進程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間。用P、V操作解決進程間互斥問題P(mutex)V(mutex)P1P2P3臨界區(qū)P(mutex)P(mutex)V(mutex)V(mutex)注意：必須成對使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）；

例：用信號量來解決飛機售票系統(tǒng)的互斥問題：

Program：

...ifcount>0then{//selltheticketcount=count-1;}

設置信號量S，s.value=1（初始值為

1）P：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)P(S): {

S.value--; if(S.value<0){

將該進程狀態(tài)置為等待狀態(tài)并將該進程插入與該信號相對應的等待隊列S.list中;

block; }}

s.value=1s.value=0P0：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)s.value=0P0：P(S)ifcount>0then

{

//selltheticketcount=count-1}V(S)P0：P(S)ifcount>0then

{

//selltheticketcount=count-1}V(S)P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)s.value=0P(S): {

S.value--; if(S.value<0){

將該進程狀態(tài)置為等待狀態(tài)并將該進程插入與該信號相對應的等待隊列S.list中;

block; }}

s.value=0P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)P(S): {

S.value--; if(S.value<0){

將該進程狀態(tài)置為等待狀態(tài)并將該進程插入與該信號相對應的等待隊列S.list中;

block; }}

s.value=-1P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)P(S): {

S.value--;

if(S.value<0)

{

將該進程狀態(tài)置為等待狀態(tài)并將該進程插入與該信號相對應的等待隊列S.list中;

block; }}s.value=-1P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=-1S.list->P1

P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)P(S): {

S.value--; if(S.value<0){

將該進程狀態(tài)置為等待狀態(tài)并將該進程插入與該信號相對應的等待隊列S.list中;

block; }}

S.value=-1S.list->P1

P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)P(S): {

S.value--; if(S.value<0){

將該進程狀態(tài)置為等待狀態(tài)并將該進程插入與該信號相對應的等待隊列S.list中;

block; }}

P0：P(S)ifcount>0then

{

//selltheticketcount=count-1}V(S)P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=-1S.list->P1

V(S):

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

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

}P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=-1S.list->P1

V(S):

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

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

}P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=0S.list->P1

V(S):

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

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

}P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=0S.list->P1

V(S):

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

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

}P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=0S.List->P1

V(S):

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

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

}P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=0喚醒

P1

P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=0喚醒P1

P1：P(S)

ifco