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