【正文】 不同 且可分配的資源還存在一個臨界值時的信號量處理。 ? 信號量集的基本思路：在 AND型信號量的基礎上進行擴充，在一次原語操作完成所有的資源申請。 ? 進程對信號量 si的 ? 測試值為 ti（表示信號量的判斷條件，要求 si=ti。即當資源數(shù)量低于 ti時，便不予分配） ? 占用值為 di（表示資源的申請量，即 si=sidi） 對應的 pv原語格式為： Swait(s1,t1,d1。…。sn,tn,dn)。 Ssignal(s1,d1?！璼n,dn)。 2022/2/6 太湖學院信機系 96 信號量集可以用于各種情況的資源分配和回收，幾種特殊情況： Swait(s,d,d)：表示每次申請 d個資源，當少于 d個時，便不分配 Swait(s,1,1)： s1表示記錄型信號量， s=1表示互斥信號量 Swait(s,1,0)：可作為一個可控開關（當 s=1時，允許多個進程進入特殊區(qū)域；當 s=0時，禁止任何進程進入臨界區(qū)）不占用資源 2022/2/6 太湖學院信機系 97 第二類經(jīng)典問題： 讀者寫者問題 有兩組并發(fā)進程：讀者和寫者，共享一組數(shù)據(jù)區(qū) 要求： 允許 多個讀者同時 執(zhí)行 讀 操作 不允許讀者、寫者同時操作（讀寫互斥） 不允許多個寫者同時操作（只能一個寫 ） 2022/2/6 太湖學院信機系 98 分析： 第一類情況：讀者優(yōu)先 如果讀者來： 1)無讀者寫者，新讀者可以讀 2)有寫者等，但有其他讀者正在讀，則新讀者也可以讀 3)有寫者寫，新讀者等 如果寫者來： 1）無讀者，新寫者可以寫 2）有讀者，新寫者等待 3）有其他寫者，新寫者等待 2022/2/6 太湖學院信機系 99 第一類讀者寫者問題的解法 讀者來： While(true){ Wait(mutex)。 readcount++。 if(readcount==1) Wait(wr)。 Signal(mutex)。 讀 Wait(mutex)。 readcount。 if(readcount==0) Signal(wr)。 signal(mutex)。 } 寫者來： While(true){ Wait(wr)。 寫 Signal(wr)。 } 初值： wr=1。（讀 寫互斥，寫 寫互斥） mutex=1。（讀者統(tǒng)計數(shù)量互斥） readcount=0。 2022/2/6 太湖學院信機系 100 用信號量集解決第一類讀者寫者問題 寫者： Swait(wr,1,1)。 Swait(count,n,0)。 寫 Ssignal(wr,1)。 讀者： Swait(count,1,1)。 Swait(wr,1,0)。 讀 Ssignal(count,1)。 初值： wr:=1 count:=n最多只能 n個讀者同時讀 (空位 ) 2022/2/6 太湖學院信機系 101 (1) P1： S1； P2： S2； 并發(fā)進程： P1和 P2，各進程語句如下，要求： S1執(zhí)行結束才能執(zhí)行 S2。如何設置 P1與 P2的關系？ 2022/2/6 太湖學院信機系 102 (2) S1 S2 S3 S4 S5 S6 a b c d e g f 圖 2－ 10 前趨圖舉例 2022/2/6 太湖學院信機系 103 利用信號量來描述前趨關系 (2) Var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0。 Begin parbegin begin S1。 signal(a)。 signal(b)。 end。 begin wait(a)。S2。 signal(c)。 signal(d)。 end。 begin wait(b)。S3。 signal(e)。 end。 begin wait(c)。S4。 signal(f)。 end。 begin wait(d)。S1。 signal(g)。 end。 begin wait(e)。 wait(f)。wait(g)。S6。 end。 parend end 2022/2/6 太湖學院信機系 104 Var chopstick: array[0, …, 4] of semaphore。 Repeat wait(chopstick[i])。 wait(chopstick[(i+1)mod 5])。 … eat； … signal(chopstick[i])。 signal(chopstick[(i+1)mod 5])。 … think。 Until false 2022/2/6 太湖學院信機系 105 AND信號量解決哲學家進餐問題 Var chopstick: array[0, …, 4] of semaphore:=(1,1,1,1,1)。 processi Repeat think。 Sswait(chopstick[(i+1)mod 5],chopstick[i])。 eat； Ssignal(chopstick[(i+1)mod 5],chopstick[i])。 Until false 2022/2/6 太湖學院信機系 106 引入原因： ? 為了避免凡要使用臨界資源的進程都自備同步操作 wait(s)和 signal(s).將同步操作的機制和臨界資源結合到一起，形成管程。 2022/2/6 太湖學院信機系 107 定義： 一個數(shù)據(jù)結構和能為并發(fā)進程所執(zhí)行的一組操作，該操作能同步進程和改變進程中的數(shù)據(jù)。(P55) 由四部分組成： ? 管程的名稱 ? 局部于管程的共享變量。 ? 對該數(shù)據(jù)結構進程操作的一組過程。 ? 對局部管程數(shù)據(jù)設置初值的語句。 條件變量： x,y: 。 。 2022/2/6 太湖學院信機系 108 ——消費者問題 一、建立管程： PC（管程名） 包括 2個過程： （ 1） put(item)過程； （ 2） get(item)過程 用于解決生產(chǎn)者消費者問題的管程描述： 變量： count≥n時滿； count≤0 時空 初始： in=out=count=0 Type producerconsumer=monitor var in,out,count： integer。 buffer: array [0,…,n 1] of item。 notfull, notempty: condition。 procedure entry put (item) procedure entry get (item) 2022/2/6 太湖學院信機系 109 ——消費者問題 Procedure entry put(item) begin if count ≥n then 。 buffer(in):=nextp。 in:=(in+1)mod n count:=count+1。 if then 。 end Procedure entry get(item) begin if count ≤ 0 then 。 nextc:=buffer(out)。 out:=(out+1)mod n count:=count1。 if then 。 end Begin in:=out:=0。 count:=0 end 2022/2/6 太湖學院信機系 110 ——消費者問題 例：利用管程解決生產(chǎn)者消費者問題 producer: begin repeat produce a item nextp PC. put (item)。 until false. End Consumer: begin repeat (item)。 Consume the item in nextc。 Until false end 可見，由管程來實現(xiàn)后，進程的同步更簡單明了。 2022/2/6 太湖學院信機系 111 ? 減少并發(fā)執(zhí)行時的時空開銷，進程的創(chuàng)建、撤消、切換較費時空 ， 因它既是調(diào)度單位，又是資源擁有者。 ? 線程 是進程中的一個實體， 是系統(tǒng)獨立調(diào)度和分派的基本單位 ，其基本上不擁有系統(tǒng)資源，只有少量資源（ IP，寄存器，棧），但共享其所屬進程所擁有的全部資源。 一個線程是程序執(zhí)行的一個單獨過程。一個線程不能夠被任何底層的事件中斷，并且不包括執(zhí)行更小的過程。 2022/2/6 太湖學院信機系 112 簡而言之 ,一個程序至少有一個進程 ,一個進程至少有一個線程 . 線程的劃分尺度小于進程，使得多線程程序的并發(fā)性高。 另外，進程在執(zhí)行過程中擁有獨立的內(nèi)存單元，而多個線程共享內(nèi)存，從而極大地提高了程序的運行效率。 2022/2/6 太湖學院信機系 113 (續(xù) ) ? 輕型實體 ? 獨立調(diào)度和分派的基本單位 ? 可并發(fā)實體 ? 共享進程資源 ? 狀態(tài)參數(shù) ? 寄存器狀態(tài)、堆棧、運行狀態(tài)、優(yōu)先級、線程專有存儲器、 ? 信號屏蔽 ? 線程的運行狀態(tài) ： 執(zhí)行、就緒、阻塞 2022/2/6 太湖學院信機系 114 ?由初始化線程創(chuàng)建 ?執(zhí)行完自愿停止 ?出現(xiàn)錯誤或某種原因被其他線程強行終止 ? 擁有系統(tǒng)資源的基本單位，可包括多個線程，不再是一個可執(zhí)行的實體。 2022/2/6 太湖學院信機系 115 系統(tǒng)中實現(xiàn)線程同步和通信的機制： ? 阻塞方式 lock(mutex) 訪問 unlock(mutex) ? 非阻塞方式 if（ trylock） then else 2022/2/6 太湖學院信機系 116 申請資源： Lock mutex check data structures。 while(resourse busy)。 wait(condition variable)。 mark resource as busy。 Unlock mutex。 釋放資源： Lock mutex mark resource as free。 Unlock mutex wakeup(condition variable)。 2022/2/6 太湖學院信機系 117 ? 私用信號量（ private semaphore) ? 作用域在一個進程中 ? 公用信號量（ public semaphore) ? 作用于多個進程間