【正文】 … while (counter==n)（ 滿） do noop。 //計數(shù) consume the item in nextc。若有，則進(jìn)程必須等待；否則，允許進(jìn)程進(jìn)入臨界區(qū)，同時設(shè)置標(biāo)志表示有進(jìn)程正在臨界區(qū)內(nèi)。section。同步機制應(yīng)遵循的規(guī)則117何謂 “忙等 ”？它有什么缺點？v 所謂 “忙等 ”是指 “不讓權(quán) ”的等待，即進(jìn)程因某事件的發(fā)生而無法繼續(xù)執(zhí)行時，它仍占有 CPU，并通過不斷地執(zhí)行循環(huán)測試指令來等待該事件的完成。v P操作和 V操作是執(zhí)行時不被打斷的兩個操作系統(tǒng)原語。s++。{}}wait(s)。semaphore=recordifs。if當(dāng)然，共享數(shù)據(jù)都應(yīng)作為臨界資源。A:wait(Dmutex)。v 要么全分配，要么一個也不分配。sn=1thetheprogramoftheSi因而，在每次分配之前，都必須測試該資源的數(shù)量是否大于測試值 t。amp。(i=1。PlaceofitsSwaitSsignal(s1,d1,…sn,dn)forqueue（ 2） Swait(S,1,1):此時的信號量集已蛻化為一般的記錄型信號量 (S1時 )或互斥信號量（ S=1）。sectioncoend}利用信號量實現(xiàn)進(jìn)程互斥131wait(mutex)和 signal(mutex)必須成對出現(xiàn)。cobegin{signal(c)}。wait(d)。wait(g)。coend}F一個結(jié)點對應(yīng)一個進(jìn)程；F一條邊對應(yīng)一個信號量；F可以少用幾個信號量 133學(xué)生自己設(shè)計的實例Varsignal(c)。{signal(g)。wait(d)。signal(l)。coend}S1S2 S3 S4S5 S6S8S7134 管程機制? 信號量機制的優(yōu)點– 一種既方便又有效的進(jìn)程同步機制? 信號量機制的缺點– 每個要訪問臨界資源的進(jìn)程都必須 自備 同步操作 wait(s)和 signal(s)。release。procedure……function? 信息掩蔽。僅當(dāng)另一進(jìn)程訪問完并釋放之后，管程又調(diào)用signal原語，喚醒等待隊列中的隊首進(jìn)程。因為，后者總是要執(zhí)行s++操作，因而總會改變信號量的狀態(tài)。讀者 — 寫者問題利用記錄型信號量解決讀者 — 寫者問題利用信號量集機制解決讀者 —— 寫者問題147 生產(chǎn)者 — 消費者問題利用記錄型信號量解決生產(chǎn)者 — 消費者問題利用 AND信號量解決生產(chǎn)者 — 消費者問題利用管程解決生產(chǎn)者 — 消費者問題148利用記錄型信號量解決生產(chǎn)者— 消費者問題? 假定，在生產(chǎn)者和消費者之間的公用緩沖池中，具有 n個緩沖區(qū)，可利用互斥信號量 mutex使諸進(jìn)程實現(xiàn)對緩沖池的互斥使用；? 利用資源信號量 empty和 full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。in=0,out=0。in while(true){nextc=buffer(out)。signal(mutex)。}consumer:wait(empty)。an{生產(chǎn)者 — 消費者問題利用記錄型信號量解決生產(chǎn)者 — 消費者問題利用 AND信號量解決生產(chǎn)者 — 消費者問題利用管程解決生產(chǎn)者 — 消費者問題此時， wait原語應(yīng)改為 ，相應(yīng)地， signal應(yīng)改為 。144v 在利用管程實現(xiàn)進(jìn)程同步時，必須設(shè)置兩個同步操作原語wait和 signal。? 抽象數(shù)據(jù)類型。usedefinemonitorname=MONITOR。– FIFO隊列（軟件資源）：可用其隊長、隊首和隊尾以及在該隊列上所執(zhí)行的一組操作來描述。S8。wait(k)。}。wait(c)。signal(e)。signal(a)。wait(e)。}。signal(e)。wait(a)。section}}}sectionprocess1:{}。readyinsi=si+di。ofandwaitingsn=tn)if當(dāng)一次需 N個某類臨界資源時，便需要進(jìn)行 N次 wait(s)操作，顯然這是低效的。associatedRemovethesetassociatedamp。B阻塞死鎖 AND型信號量124v 將進(jìn)程在整個運行過程中所需要的所有臨界資源， 一次性 地全部 分配 給進(jìn)程，待該進(jìn)程使用完后再 一起釋放 。wait(Dmutex)。在有些應(yīng)用場合，一個進(jìn)程需要先獲得兩個或更多的共享資源后，方能執(zhí)行其任務(wù)。資源數(shù)目加 1endprocedure整型信號量的應(yīng)用S1S2semaphore整型信號量記錄型信號量 AND型信號量信號量集119v 整型信號量定義為一個整型量，除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作 Wait(S)同步機制應(yīng)遵循的規(guī)則116（ 3）有限等待section。v剩余區(qū)：其他代碼 臨界區(qū) (critical section)113v為了互斥地訪問臨界資源，系統(tǒng)必須保證進(jìn)程互斥地進(jìn)入臨界區(qū)。 out=(out+1)% n。n 是代碼n 進(jìn)程內(nèi)的代碼n 一段或多段n 不一定連續(xù)n 不一定相同v若能保證諸進(jìn)程互斥地進(jìn)入自己的臨界區(qū)，便可實現(xiàn)諸進(jìn)程對臨界資源的互斥訪問。register2=counter。register2。register1++。condition //計數(shù) }consumer: while(true){ … while (counter==0)（空） do noop。in,out。 減 1：消費者進(jìn)程從緩沖中取走一個產(chǎn)品u生產(chǎn)者和消費者兩進(jìn)程共享下面的變量intn167。216。（ 3）流水線生產(chǎn)的各道工序是直接制約，各道工序間需要相互合作，每道工序的開始都依賴于前一道工序的完成。? 例如，有 2個進(jìn)程 A和 B，如果在 A進(jìn)程提出打印請求時，系統(tǒng)已將惟一的一臺打印機分配給了進(jìn)程 B，則此時進(jìn)程 A只能阻塞；一旦進(jìn)程 B將打印機釋放，則 A進(jìn)程才能由阻塞改為就緒狀態(tài)。? 進(jìn)程與程序的組成不同。? 假如采用的是 搶占調(diào)度 策略，則每當(dāng)有新進(jìn)程進(jìn)入就緒隊列時，應(yīng)檢查是否要進(jìn)行重新調(diào)度，即由調(diào)度程序?qū)⒈患せ钸M(jìn)程與當(dāng)前進(jìn)程進(jìn)行優(yōu)先級的比較，如果被激活進(jìn)程的優(yōu)先級更低，就不必重新調(diào)度；否則，立即剝奪當(dāng)前進(jìn)程的運行，把處理機分配給剛被激活的進(jìn)程。進(jìn)程的激活過程931. 進(jìn)程的掛起? 當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時，比如，用戶進(jìn)程請求將自己掛起，或父進(jìn)程請求將利用掛起原語 Suspend()將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。? 進(jìn)入 block過程后，由于此時該進(jìn)程還處于執(zhí)行狀態(tài)，所以應(yīng)先立即停止執(zhí)行，把 PCB中的現(xiàn)行狀態(tài)由 “執(zhí)行 ”改為 “阻塞 ”，并將 PCB插入阻塞隊列。在 I/O操作完成后，再由 中斷處理程序 或 中斷進(jìn)程將該進(jìn)程 喚醒 。（ 5）將被終止進(jìn)程（ PCB）從所在隊列（鏈表）中移出，等待其他程序來搜集信息。由于父進(jìn)程具有終止自己的任何子孫進(jìn)程的權(quán)力，因而當(dāng)父進(jìn)程提出終止該進(jìn)程（子孫進(jìn)程）的請求時，系統(tǒng)將終止該進(jìn)程（子孫進(jìn)程）。– 算術(shù)運算錯。出現(xiàn)該錯誤的原因，可能是程序錯誤地轉(zhuǎn)移到數(shù)據(jù)區(qū)，把數(shù)據(jù)當(dāng)成了指令。 off去表示進(jìn)程運行完畢，此時同樣可產(chǎn)生一個中斷，去通知 OS進(jìn)程已運行完畢。如新進(jìn)程要共享某個已在內(nèi)存的地址空間，則必須建立相應(yīng)鏈表。該應(yīng)用進(jìn)程為使這幾個操作能并發(fā)執(zhí)行，以加速任務(wù)的完成，可以分別建立鍵盤輸入進(jìn)程、 數(shù)據(jù)處理進(jìn)程、 表格輸出進(jìn)程等。? 進(jìn)程：結(jié)點? 父進(jìn)程：在進(jìn)程 D創(chuàng)建了進(jìn)程 I后，稱 D是 I的父進(jìn)程? 子進(jìn)程： I是 D的子進(jìn)程? 祖父進(jìn)程? 祖先：樹的根節(jié)點是進(jìn)程家族的祖先66AB CD E F G HL MI J K1. 進(jìn)程圖? 繼承（資源）– 子進(jìn)程可以繼承父進(jìn)程所擁有的資源（打開的文件、緩沖區(qū)等）– 當(dāng)子進(jìn)程被撤消時，應(yīng)將從父進(jìn)程那里獲得的資源歸還給父進(jìn)程– 在撤消父進(jìn)程時，也必須同時撤消其所有的子進(jìn)程– 為了標(biāo)識進(jìn)程之間的家族關(guān)系，在 PCB中都設(shè)置了家族關(guān)系表項，以標(biāo)明自己的父進(jìn)程及所有的子進(jìn)程672. 引起創(chuàng)建進(jìn)程的事件? 在多道程序環(huán)境中，只有進(jìn)程才能在系統(tǒng)中運行。? 原語的作用是為了實現(xiàn)進(jìn)程的通信和控制，系統(tǒng)對進(jìn)程的控制如不使用原語，就會造成其狀態(tài)的不確定性，從而達(dá)不到進(jìn)程控制的目的。– 創(chuàng)建一個新進(jìn)程– 終止一個已完成的進(jìn)程– 終止一個因出現(xiàn)某事件而無法運行下去的進(jìn)程– 負(fù)責(zé)進(jìn)程運行中的狀態(tài)轉(zhuǎn)換? 當(dāng)一個正在執(zhí)行的進(jìn)程因等待某事件而暫時不能繼續(xù)執(zhí)行時，將其轉(zhuǎn)換為阻塞狀態(tài)? 當(dāng)該進(jìn)程所期待的事件出現(xiàn)時，又將該進(jìn)程轉(zhuǎn)換為就緒狀態(tài)等等。9 11…60P215隱式鏈接、顯式鏈接按索引方式組織 PCB執(zhí)行指針就緒表指針阻塞表指針PCB1 4PCB54處理機狀態(tài)? 這些寄存器包括：– 通用寄存器（用戶可視寄存器）：是用戶程序可以訪問的，用于暫存信息，在大多數(shù)處理機中，有 8~32個寄存器，在 RISC結(jié)構(gòu)的計算機中可超過 100個；– 指令計數(shù)器 PC：下一條指令的地址；– 程序狀態(tài)字 PSW：含有狀態(tài)信息，如條件碼、執(zhí)行方式、中斷屏蔽標(biāo)志等；– 用戶棧指針：指每個用戶進(jìn)程都有一個或若干個與之相關(guān)的系統(tǒng)棧，用于存放過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址，棧指針指向該棧的棧頂。? 一個進(jìn)程通常有兩種標(biāo)識符：– 內(nèi)部標(biāo)識符： OS中為每個進(jìn)程賦予惟一的數(shù)字標(biāo)識符，它通常是一個進(jìn)程的序號。– 當(dāng) OS要調(diào)度某進(jìn)程執(zhí)行時，要從該進(jìn)程的 PCB中查出其現(xiàn)行狀態(tài)及優(yōu)先級；– 在調(diào)度到某進(jìn)程后，要根據(jù)其 PCB中所保存的處理機狀態(tài)信息，設(shè)置該進(jìn)程恢復(fù)運行的現(xiàn)場，并根據(jù)其PCB中的程序和數(shù)據(jù)的內(nèi)存始址，找到其程序和數(shù)據(jù)；– 進(jìn)程在執(zhí)行過程中，當(dāng)需要和與之合作的進(jìn)程實現(xiàn)同步、通信或訪問文件時，也都需要訪問 PCB；– 當(dāng)進(jìn)程由于某種原因而暫停執(zhí)行時，又須將其斷點的處理機環(huán)境保存在 PCB中。一旦其他進(jìn)程完成了對終止?fàn)顟B(tài)進(jìn)程的信息提取之后， OS將刪除該進(jìn)程。（ 4） 靜止阻塞 → 活動阻塞–處于 Blockeds狀態(tài)的進(jìn)程，若用激活原語 Active激活后，進(jìn)程將轉(zhuǎn)變?yōu)?Blockeda狀態(tài)。（ 4）操作系統(tǒng)的需要： OS有時希望掛起某些進(jìn)程，以便檢查運行中的資源使用情況或進(jìn)行記賬。?另外，狀態(tài)轉(zhuǎn)換 4還可能同時引發(fā)狀態(tài)轉(zhuǎn)換 1和 2：若系統(tǒng)采用搶占調(diào)度方式，而新就緒的進(jìn)程具備搶占 CPU的條件（如其優(yōu)先權(quán)很高），則它可立即得到 CPU轉(zhuǎn)換成執(zhí)行狀態(tài)，而原來正在執(zhí)行的進(jìn)程則轉(zhuǎn)換成就緒狀態(tài)。? 阻塞狀態(tài) ?就緒狀態(tài)（ I/O完成）– 當(dāng)進(jìn)程等待的事件到來時，如 IO操作結(jié)束或中斷結(jié)束時，中斷處理程序必須把相應(yīng)進(jìn)程的狀態(tài)由阻塞狀態(tài)轉(zhuǎn)換為就緒狀態(tài)。? 致使進(jìn)程阻塞的典型事件– 請求 I/O– 申請緩沖空間等? 阻塞隊列：將處于阻塞狀態(tài)的進(jìn)程排成的隊列。? 運行狀態(tài)? 就緒狀態(tài)? 阻塞狀態(tài)? 創(chuàng)建狀態(tài)? 結(jié)束狀態(tài)18運行狀態(tài)（ Running）p 也叫執(zhí)行狀態(tài)。– 進(jìn)程由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤消而消亡，進(jìn)程實體有一定的生命期，而程序則只是一組有序指令的集合，并存放在某種介質(zhì)上，其本身并不具有運動的含義，因而是靜態(tài)的。進(jìn)程的三種基本狀態(tài)3.d=c+6S1S2S3 S49程序并發(fā)執(zhí)行時的特征? 間斷性– 程序在并發(fā)執(zhí)行時，由于它們共享系統(tǒng)資源，以及為完成同一項任務(wù)而相互合作，致使在這些并發(fā)執(zhí)行的程序之間，形成相互制約的關(guān)系。Ci?Ci+1, S2?S3, S3?S2S1S2S37 進(jìn)程的基本概念Node：沒有后繼的結(jié)點v Weight：結(jié)點所含的程序量或結(jié)點的執(zhí)行時間v上圖的前趨關(guān)系： Ii?Ci?Pi may)Graphv有向無循環(huán)圖 DAG程序的順序執(zhí)行及其特征程序的順序執(zhí)行程序順序執(zhí)行時的特征2程序的順序執(zhí)行? 一個較大的程序通常都由若干個程序段組成? 程序在執(zhí)行時，必須按照某種先后次序逐個執(zhí)行，僅當(dāng)前一操作執(zhí)行完后，才能執(zhí)行后繼操作。Graph)，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。)Pj的 直接 前趨 ?Pi+1而 Ii+1和 Ci及 Pi1是重迭的，亦即在 Pi1和 Ci以及 Ii+1之間，可以并發(fā)執(zhí)行。? 不可再現(xiàn)性– 程序經(jīng)過多次執(zhí)行后，雖然其執(zhí)行時