第二章進(jìn)程及作業(yè)管理(編輯修改稿)
2024-11-03 14:02 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ,count A:LD count,R1 B:INC R1 B:LD count,R1 count經(jīng) A、 B訪(fǎng)問(wèn)后，只加了 1，而不是所希望的 2。為了防止發(fā)生這種與時(shí)間有關(guān)的錯(cuò)誤，變量 count必須按臨界資源處理。 第二章 進(jìn)程及作業(yè)管理 系統(tǒng)的同步機(jī)構(gòu)對(duì)解決臨界區(qū)互斥問(wèn)題應(yīng)遵循下述準(zhǔn)則： (1)當(dāng)無(wú)一進(jìn)程處于臨界區(qū)內(nèi)時(shí)，若有一進(jìn)程要求進(jìn)入臨界區(qū)，應(yīng)讓其立即進(jìn)入 (2)當(dāng)已有進(jìn)程在臨界區(qū)內(nèi)時(shí)，其他欲進(jìn)入臨界區(qū)的進(jìn)程必須等待 (3)當(dāng)無(wú)一進(jìn)程處于臨界區(qū)，而同時(shí)有多個(gè)進(jìn)程要求進(jìn)入臨界區(qū)，且僅讓其中之一進(jìn)入，其他則等待 (4)任一進(jìn)程進(jìn)入臨界區(qū)的要求應(yīng)在有限時(shí)間滿(mǎn)足 有限等 (5)處于等待進(jìn)入臨界區(qū)的進(jìn)程應(yīng)放棄占用 CPU讓權(quán)等待。 第二章 進(jìn)程及作業(yè)管理 同步機(jī)構(gòu) 1．測(cè)試與設(shè)置 (Test and Set) 這是一種借助一條硬件指令 Test and Set(簡(jiǎn)記 TS)來(lái)實(shí)現(xiàn)互斥的同步機(jī)構(gòu)。許多計(jì)算機(jī)中都提供了這種指令，在 IBM 370中稱(chēng) TS指令，在 Z 8000中稱(chēng) TSET指令，在 Intel 8086/8088中稱(chēng) XCHG指令。 TS指令的功能可用 PASCAL語(yǔ)言描述如下： 第二章 進(jìn)程及作業(yè)管理 procedure TS(vara,b:boolean)。 var temp:boolean。 begin temp:=a。 a:=b。 b:=temp end function TS(var b:boolean):boolean。 begin TS:=b。 b:=true end v 第二章 進(jìn)程及作業(yè)管理 TS指令的執(zhí)行是不可分割的，利用 TS指令可以簡(jiǎn)單而有效地實(shí)現(xiàn)互斥。 其方法是為每個(gè)臨界資源設(shè)置一個(gè)布爾變量 lock(鎖 )，其初值為 falsc，當(dāng) lock值為 false表示鎖打開(kāi)，臨界資源未被使用，進(jìn)程可進(jìn)入臨界區(qū)；反之則表示鎖關(guān)閉，進(jìn)程不能進(jìn)入。于是用 TS指令實(shí)現(xiàn)互斥的進(jìn)程的程序結(jié)構(gòu)為： 第二章 進(jìn)程及作業(yè)管理 var key: blooean。 begin … key:=true。 while key do TS(lock,key)。 （１ ′ CS (臨界區(qū) ) lock:=false。 … end begin … while TS (lock) do skip。 CS。 （２ ′ lock:=false。 … end 第二章 進(jìn)程及作業(yè)管理 2．信號(hào)量和 P、 V操作 荷蘭的著名計(jì)算機(jī)科學(xué)家 Dijkstra把互斥的關(guān)鍵含義抽象成信號(hào)量 (semaphore)概念，并引入在信號(hào)量上的 P、 V操作作為同步原語(yǔ) (P和 V分別是荷蘭文的“等待”和“發(fā)信號(hào)”兩詞的首字母 )。信號(hào)量是個(gè)被保護(hù)的量，只有 P、 V操作和信號(hào)量初始化操作才能訪(fǎng)問(wèn)和改變它的值， Dijkstra把信號(hào)量 s定義為一個(gè)非負(fù)整型量。把信號(hào)量 s上的 P操作 P(s)定義為：若 s0，則 s值減 1，否則執(zhí)行進(jìn)程等待，直到其他進(jìn)程對(duì) s進(jìn)行 V操作。把信號(hào)量 s上的 V操作 V(s)定義為： s值加 1，若有進(jìn)程在 s上等待，則喚醒其中一個(gè)進(jìn)程。 第二章 進(jìn)程及作業(yè)管理 信號(hào)量和 P、 V操作原語(yǔ)可構(gòu)成“阻塞 喚醒”同步機(jī)構(gòu)：當(dāng)一個(gè)進(jìn)程對(duì)值為 0的信號(hào)量執(zhí)行 P操作時(shí)便被阻塞以等待某個(gè)事件的出現(xiàn)；在另一進(jìn)程檢測(cè)到該事件發(fā)生時(shí)，通過(guò)執(zhí)行 V操作喚醒被阻塞的進(jìn)程。在實(shí)現(xiàn)該同步機(jī)構(gòu)時(shí)，可采取“忙等待”方式也可采取“讓權(quán)等待”方式。在忙等待方式下，被阻塞進(jìn)程在不主動(dòng)放棄處理機(jī)的情況下忙碌等待著其他進(jìn)程來(lái)喚醒它，顯然這不利于處理機(jī)的有效利用。讓權(quán)等待方式，即當(dāng)執(zhí)行進(jìn)程必須在某信號(hào)量上等待時(shí)，就將該進(jìn)程變?yōu)榈却隣顟B(tài)，并將其插入與此信號(hào)量相關(guān)的等待隊(duì)列中，以讓出處理機(jī)給其他就緒進(jìn)程。在單機(jī)系統(tǒng)中普遍采用讓權(quán)等待方式。而在多機(jī)系統(tǒng)中，為減少進(jìn)程狀態(tài)變換而引起的開(kāi)銷(xiāo)，可采取忙等待方式。另外，在具體實(shí)現(xiàn)時(shí)通常要對(duì) Dijkstra的原定義進(jìn)行改進(jìn)。 第二章 進(jìn)程及作業(yè)管理 (1)忙等待方式的 P、 V vars: integer。 P(s) :while s≤ 0 do skip。 s:=s1 V(s) :s:=s+1。 當(dāng)一進(jìn)程在值不大于 0的信號(hào)量 s上執(zhí)行 P操作時(shí)，將在循環(huán)語(yǔ)句 while上陷入忙等待，直到其他進(jìn)程在該信號(hào)量 s上執(zhí)行 V操作后，解除它的等待。不難看出這種形式的 P、 V操作完全可用硬件指令來(lái)實(shí)現(xiàn)。 第二章 進(jìn)程及作業(yè)管理 (2)讓權(quán)等待方式的 P、 V操作。采取這種方式需要對(duì)原信號(hào)量定義進(jìn)一步擴(kuò)充，把信號(hào)量由整型量擴(kuò)充成為記錄形式： type psem=semaphore semaphore=record value: integer。 qucue: pointer to WQ。 end 即信號(hào)量 s是二元組 s(v,q) , v是信號(hào)量 s的值，它是個(gè)整型量， q是指向 s等待隊(duì)列 WQ的隊(duì)首指針。于是 P、 V操作可分別描述為： 第二章 進(jìn)程及作業(yè)管理 procedure p ( s ) 。 var s: psem。 begin :=。 if 0 then block() end procedure V ( s )。 var s:psem。 begin :=+1 if ≤0 then wakeup() end 第二章 進(jìn)程及作業(yè)管理 根據(jù)上述定義， P、 V操作的物理意義可這樣來(lái)看待。0表示某類(lèi)資源的當(dāng)前可用數(shù)。 每執(zhí)行一次 P操作意味著請(qǐng)求分配一個(gè)單位的資源，因此描述為 :=。 ≤0表示該類(lèi)資源已不能供分配，因此請(qǐng)求資源的進(jìn)程將被阻塞在等待隊(duì)列 ，此時(shí) 程數(shù)。執(zhí)行一次 V操作意味著釋放一個(gè)單位資源，故描述為 .v:=+1，若 ≤0，表示在等待隊(duì)列 源不能滿(mǎn)足而被阻塞的進(jìn)程，因此喚醒等待隊(duì)列 一個(gè)或優(yōu)先數(shù)最高的進(jìn)程，允許其使用該資源。 第二章 進(jìn)程及作業(yè)管理 1．臨界區(qū)的互斥 利用信號(hào)量可方便地實(shí)現(xiàn)臨界區(qū)的互斥執(zhí)行。此時(shí)信號(hào)量是公用信號(hào)量，它的初值為 1，每個(gè)進(jìn)程均可對(duì)它施行 P、 V操作。設(shè) mutex為互斥信號(hào)量，其初值為 1，表示對(duì)應(yīng)的臨界資源 R未被占用。對(duì)于每個(gè)想使用 R的進(jìn)程，只需把它們的臨界區(qū) CS置于 P(mutex)和 V(mutex)之間，即可實(shí)現(xiàn)互斥。下面給出這種模型的大致描述： 第二章 進(jìn)程及作業(yè)管理 var mutex: psem。 procedure processl begin while true do begin … p(mutex)。 CS1。 V(mutex)。 … end end。 第二章 進(jìn)程及作業(yè)管理 pr
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1