操作系統(tǒng)第三章

操作系統(tǒng)第三章程序執(zhí)行分析程序順序執(zhí)行將具有獨(dú)立功能的程序獨(dú)占處理機(jī)運(yùn)行直到得到最終結(jié)果稱為程序順序執(zhí)行特點(diǎn)順序性：程序按預(yù)先的邏輯順序依次執(zhí)行封閉性：程序的執(zhí)行結(jié)果由初始條件確定，不受外界影響可再現(xiàn)性：程序的執(zhí)行結(jié)果與它執(zhí)行的速度、環(huán)境無關(guān)資源獨(dú)占：程序執(zhí)行時(shí)獨(dú)占CPU假設(shè)程序A={IA（輸入），PA（計(jì)算處理），OA（輸出）}，B={IB，PB，OB}。A、B的順序執(zhí)行為：IAPAOA

IBPBOB總的執(zhí)行時(shí)間TS=TA+TB§1、進(jìn)程及其基本特征程序并行（回憶并行和并發(fā)區(qū)別）執(zhí)行多個(gè)程序的執(zhí)行與其它程序無關(guān)，相互無任何依賴，它們獨(dú)占各自的CPU特點(diǎn)：順序、封閉、可再現(xiàn)、資源獨(dú)占、多個(gè)CPU對(duì)前述的程序A、B，其并行執(zhí)行為：

IAPAOA

IBPBOB總的執(zhí)行時(shí)間TP=max{TA，TB}程序并發(fā)執(zhí)行例對(duì)前述的程序A、B，若執(zhí)行為：

IAPAOA

IBPBOB即：PA與IB，OA與PB在時(shí)間上重疊，這時(shí)只需一個(gè)CPU就可以了?？偟膱?zhí)行時(shí)間TM=T(IA)+max{T(PA),T(IB)}+max{T(OA),T(PB)}+T(OB)(設(shè)IO設(shè)備只有一個(gè))顯然:TS

>TM>TP,在不增加系統(tǒng)資源的條件下，TM對(duì)應(yīng)的執(zhí)行方式較順序執(zhí)行（TS）效率高一組在邏輯上互相獨(dú)立的程序（程序段）在執(zhí)行過程中其執(zhí)行時(shí)間在客觀上互相重疊，即一個(gè)程序（程序段）的執(zhí)行尚未結(jié)束，另一個(gè)程序（程序段）的執(zhí)行就已開始的執(zhí)行方式稱為程序的并發(fā)執(zhí)行。思考：因?yàn)榧僭O(shè)處理機(jī)，IO設(shè)備各只有一個(gè)。所以O(shè)A和PB最早開始的時(shí)刻，就是PA和IB最晚結(jié)束的時(shí)刻。OB開始的時(shí)刻，必然是OA和PB最晚結(jié)束的時(shí)刻特點(diǎn)間斷性：就CPU來看程序的執(zhí)行是不連續(xù)的非封閉性：程序的執(zhí)行結(jié)果與初始條件相關(guān)，同時(shí)受外界影響不可再現(xiàn)性：程序的執(zhí)行結(jié)果與它執(zhí)行的速度、環(huán)境有關(guān)資源共享：多個(gè)程序的執(zhí)行共享CPU例:proceduregetdata(a)beginL1:a(top)L2:toptop-1endproceduresetdata(b)beginL3:toptop-1L4:(top)bend當(dāng)getdata與setdata并發(fā)執(zhí)行時(shí)其結(jié)果不再具有封閉性和可再現(xiàn)性。考慮如下執(zhí)行序列時(shí)的結(jié)果：L1

L2

L3

L4L1

L3

L2

L4（前兩者執(zhí)行效果一樣，B存入了倒數(shù)第三個(gè)位置）L1

L3

L4

L2（B存入了倒數(shù)第二個(gè)位置）為確保并發(fā)執(zhí)行的程序其結(jié)果具有封閉性和可再現(xiàn)性，必須協(xié)調(diào)各程序間的執(zhí)行速度，即對(duì)并發(fā)執(zhí)行進(jìn)行一定的限制。順序執(zhí)行與并發(fā)執(zhí)行的比較進(jìn)程定義一個(gè)具有獨(dú)立功能的程序（程序段）對(duì)某個(gè)數(shù)據(jù)集在處理機(jī)上的執(zhí)行過程，和分配資源的單位——稱進(jìn)程程序（程序段）——一個(gè)操作序列數(shù)據(jù)集——接受程序規(guī)定操作的一組存儲(chǔ)單元的內(nèi)容特征動(dòng)態(tài)性：進(jìn)程是程序在并發(fā)系統(tǒng)的一次執(zhí)行，一個(gè)進(jìn)程有一個(gè)從產(chǎn)生到消失的生命期；并發(fā)性：正是為了描述程序在并發(fā)系統(tǒng)內(nèi)執(zhí)行的動(dòng)態(tài)特征才引入了進(jìn)程，沒有并發(fā)就沒有進(jìn)程獨(dú)立性：每個(gè)進(jìn)程的程序都是相對(duì)獨(dú)立的順序程序，可以按自己的方向和速度獨(dú)立地向前推進(jìn)制約性：進(jìn)程之間的相互制約，主要表現(xiàn)在互斥地使用資源和相關(guān)進(jìn)程之間必要的同步和通訊結(jié)構(gòu)性：進(jìn)程=PCB（進(jìn)程控制塊）+程序+數(shù)據(jù)集合。程序與進(jìn)程的對(duì)比程序與進(jìn)程的類比§2、進(jìn)程的描述及狀態(tài)系統(tǒng)為感知、操作、控制進(jìn)程，需要對(duì)其描述，以說明其執(zhí)行環(huán)境。描述的含義系統(tǒng)中用于描述進(jìn)程存在和反映其變化的物理實(shí)體——進(jìn)程靜態(tài)描述描述的內(nèi)容進(jìn)程控制塊（PCB，Processcontrolblock）——系統(tǒng)感知進(jìn)程的唯一實(shí)體程序（程序段）——進(jìn)程完成的功能數(shù)據(jù)結(jié)構(gòu)集——執(zhí)行時(shí)的工作區(qū)和操作對(duì)象進(jìn)程控制塊（PCB）作用系統(tǒng)感知進(jìn)程的標(biāo)識(shí)反映進(jìn)程的動(dòng)態(tài)特征與進(jìn)程一一對(duì)應(yīng)，常駐內(nèi)存進(jìn)程控制塊將構(gòu)成并發(fā)執(zhí)行控制和維護(hù)系統(tǒng)工作的依據(jù)組成（比較作業(yè)控制塊）描述信息進(jìn)程名或進(jìn)程標(biāo)識(shí)號(hào)——識(shí)別進(jìn)程用戶名或用戶標(biāo)識(shí)號(hào)——進(jìn)程隸屬的用戶家族關(guān)系——進(jìn)程樹（父子進(jìn)程….）控制信息當(dāng)前狀態(tài)優(yōu)先級(jí)別程序開始地址計(jì)時(shí)信息通信信息資源管理信息占用內(nèi)存大小及管理用數(shù)據(jù)結(jié)構(gòu)指針對(duì)換(swap)或覆蓋(overlay)信息共享程序段大小及起始地址I/O設(shè)備相關(guān)信息指向文件系統(tǒng)的指針及有關(guān)標(biāo)識(shí)CPU現(xiàn)場保護(hù)區(qū)PCB基本信息LINUX的進(jìn)程控制塊結(jié)構(gòu)概念：是進(jìn)程執(zhí)行活動(dòng)全過程的描述，包括計(jì)算機(jī)中與執(zhí)行進(jìn)程有關(guān)的各種寄存器的值，程序段在經(jīng)過編譯后形成的機(jī)器指令代碼集（正文段）、數(shù)據(jù)集及各種堆棧值及PCB結(jié)構(gòu)。進(jìn)程上下文動(dòng)態(tài)部分：指在進(jìn)入和退出不同的上下文時(shí)，系統(tǒng)為各層上下文中相關(guān)聯(lián)的寄存器值所保存和恢復(fù)的記錄（其值動(dòng)態(tài)變化）。（用于現(xiàn)場保護(hù)和恢復(fù)）進(jìn)程上下文靜態(tài)部分：包括PCB結(jié)構(gòu)、將進(jìn)程虛地址空間映射到物理空間用的有關(guān)表格和核心棧（用于系統(tǒng)調(diào)用）。進(jìn)程上下文進(jìn)程上下文進(jìn)程上下文是進(jìn)程執(zhí)行活動(dòng)全過程的靜態(tài)描述進(jìn)程上下文結(jié)構(gòu)層次結(jié)構(gòu)PCB結(jié)構(gòu)虛存與實(shí)存映射表核心棧：系統(tǒng)調(diào)用序列進(jìn)程上下文用戶級(jí)上下文系統(tǒng)級(jí)上下文用戶程序段用戶數(shù)據(jù)段用戶堆?！o態(tài)部分動(dòng)態(tài)部分：相關(guān)寄存器及其值正文集PCB各種控制表指針數(shù)據(jù)集棧區(qū)各種寄存器進(jìn)程上下文切換過程進(jìn)程狀態(tài)一般來說，一個(gè)進(jìn)程在它的生命周期有三種基本狀態(tài)，分別為就緒(ready)、執(zhí)行(execute)和等待(waiting)。除此之外，一個(gè)進(jìn)程在剛創(chuàng)建初期處于“進(jìn)入”狀態(tài)，在運(yùn)行終止后處于“完成”狀態(tài)。就緒——進(jìn)程具備運(yùn)行條件，但尚未占用CPU，即進(jìn)程已擁有除CPU外運(yùn)行所需的全部資源執(zhí)行——進(jìn)程正在占用CPU等待——進(jìn)程由于等待某一事件不能享用CPU，即進(jìn)程除CPU外還等待獲得其它資源進(jìn)程狀態(tài)轉(zhuǎn)換隨著資源在進(jìn)程間的重新分配，進(jìn)程的狀態(tài)將發(fā)生變化。引起狀態(tài)變化的原因有：CPU調(diào)度（低級(jí)調(diào)度）：CPU調(diào)度按某種原則從就緒隊(duì)列中調(diào)度一個(gè)進(jìn)程到CPU上運(yùn)行，該進(jìn)程就從就緒狀態(tài)變?yōu)檫\(yùn)行狀態(tài)；與此同時(shí)，原運(yùn)行進(jìn)程從運(yùn)行狀態(tài)變?yōu)榫途w狀態(tài)。因此，這兩種狀態(tài)變化是同時(shí)發(fā)生的。進(jìn)程在運(yùn)行過程中需要等待某一事件，例如，等待分配某一資源，等待I/O操作完成等。一個(gè)進(jìn)程在需要等待某一事件時(shí)主動(dòng)退出CPU，并使自己處于阻塞狀態(tài)，引起狀態(tài)變化。如果進(jìn)程所等待的事件發(fā)生了變化，例如，一次I/O完成了，于是進(jìn)程便被解除阻塞狀態(tài)，變?yōu)榫途w狀態(tài)。一個(gè)具體的進(jìn)程在任何一個(gè)指定的時(shí)刻必須而且只能處于一種狀態(tài)。高級(jí)調(diào)度作業(yè)調(diào)度中級(jí)調(diào)度內(nèi)存對(duì)換低級(jí)調(diào)度進(jìn)程調(diào)度調(diào)度級(jí)別的比較：狀態(tài)轉(zhuǎn)換圖撤消就緒執(zhí)行等待創(chuàng)建調(diào)度/獲得CPU阻塞/等待資源喚醒/獲得資源時(shí)間片用完或其他原因失去CPU進(jìn)程除上述基本狀態(tài)外，不同的OS為更好地管理系統(tǒng)資源擴(kuò)展了一些狀態(tài)，如：就緒內(nèi)存就緒外存就緒執(zhí)行管態(tài)目態(tài)設(shè)備等待文件等待數(shù)據(jù)等待內(nèi)存等待等待含有掛起狀態(tài)的狀態(tài)轉(zhuǎn)換（掛起：進(jìn)程從內(nèi)存中退出，對(duì)比“就緒”）就緒執(zhí)行等待創(chuàng)建撤消調(diào)度/獲得CPU阻塞/等待資源喚醒/獲得資源失去CPU就緒掛起等待掛起掛起掛起掛起釋放釋放進(jìn)程狀態(tài)轉(zhuǎn)換的說明進(jìn)程之間的狀態(tài)轉(zhuǎn)換并非都是可逆的。進(jìn)程既不能從等待變?yōu)檫\(yùn)行，也不能從就緒變?yōu)榈却瑥膱?zhí)行變?yōu)閽炱鸷蟛荒苤苯臃祷貓?zhí)行進(jìn)程之間的狀態(tài)轉(zhuǎn)換并非都是主動(dòng)的，在很多情況下都是“它動(dòng)的”。事實(shí)上，只有運(yùn)行到等待的轉(zhuǎn)換是進(jìn)程的主動(dòng)行為（主動(dòng)調(diào)用調(diào)度管理程序），其它都是它動(dòng)的，例如，從執(zhí)行到就緒，通常是時(shí)鐘中斷引起的，從等待到就緒，是一個(gè)進(jìn)程把另一個(gè)進(jìn)程喚醒。進(jìn)程組織進(jìn)程家族相關(guān)進(jìn)程按父子關(guān)系組織成層次結(jié)構(gòu)子進(jìn)程由父進(jìn)程創(chuàng)建并繼承父進(jìn)程的資源撤消一個(gè)進(jìn)程時(shí)，其子孫進(jìn)程一并被撤消狀態(tài)隊(duì)列進(jìn)程按其狀態(tài)形成隊(duì)列一種狀態(tài)一個(gè)隊(duì)列§3、進(jìn)程控制進(jìn)程控制的任務(wù)創(chuàng)建、撤消進(jìn)程及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的原語（類似于數(shù)據(jù)庫中的原子操作和事務(wù)的概念）系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段——原語分類機(jī)器指令級(jí)：執(zhí)行期間不允許中斷功能級(jí)：不允許并發(fā)執(zhí)行特點(diǎn)：不可分割，或者全執(zhí)行或者不執(zhí)行作用：在系統(tǒng)態(tài)下執(zhí)行，且都是為了完成某個(gè)系統(tǒng)管理所需要的功能和被高層軟件調(diào)用在操作系統(tǒng)中，一般都把進(jìn)程控制用的程序段做成原語，用于進(jìn)程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等進(jìn)程的創(chuàng)建創(chuàng)建方式由系統(tǒng)統(tǒng)一創(chuàng)建。例如在批處理系統(tǒng)中，由操作系統(tǒng)的作業(yè)調(diào)度程序?yàn)橛脩暨M(jìn)程創(chuàng)建相應(yīng)的進(jìn)程以完成用戶作業(yè)所要求的功能。由父進(jìn)程創(chuàng)建。例如在UNIX操作系統(tǒng)中，父進(jìn)程創(chuàng)建子進(jìn)程以完成并行工作。創(chuàng)建原語入口查PCB鏈表有空PCB取空表PCB(i)將參數(shù)添入PCB(i)PCB(i)入就緒隊(duì)列PCB(i)入進(jìn)程家族或進(jìn)程鏈返回創(chuàng)建失敗有無撤消進(jìn)程原因該進(jìn)程已完成所要求的功能——正常終止（自身調(diào)用）由于某種錯(cuò)誤導(dǎo)致進(jìn)程撤消——非正常終止（系統(tǒng)調(diào)用）祖先進(jìn)程要求撤消子孫進(jìn)程——非正常終止（祖先進(jìn)程調(diào)用）方法調(diào)用撤消原語注意：誰調(diào)用撤消原語撤消原語入口查進(jìn)程鏈表或進(jìn)程家族有此PCB釋放該進(jìn)程占有的資源釋放該P(yáng)CB結(jié)構(gòu)返回出錯(cuò)處理有無該P(yáng)CB有子進(jìn)程無進(jìn)程阻塞原因：資源請(qǐng)求且未被滿足。資源可以是：輸入數(shù)據(jù)，寫數(shù)據(jù)到設(shè)備，與其它進(jìn)程交換數(shù)據(jù)，……注意：誰調(diào)用阻塞原語（進(jìn)程自己調(diào)用）阻塞原語入口保存當(dāng)前進(jìn)程的CPU現(xiàn)場置該進(jìn)程的狀態(tài)進(jìn)程入等待隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度進(jìn)程喚醒原因：請(qǐng)求的資源被滿足進(jìn)程喚醒方法由系統(tǒng)進(jìn)程喚醒：系統(tǒng)統(tǒng)一控制事件的發(fā)生并將“事件發(fā)生”這一消息通知等待進(jìn)程。由事件發(fā)生進(jìn)程喚醒：在這種情況下，事件發(fā)生進(jìn)程和喚醒進(jìn)程之間是合作關(guān)系。喚醒原語入口從等待隊(duì)列中摘下被喚醒進(jìn)程置被喚醒進(jìn)程的狀態(tài)被喚醒進(jìn)程入就緒隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度或返回§4、進(jìn)程調(diào)度進(jìn)程調(diào)度被認(rèn)為是系統(tǒng)中的低級(jí)調(diào)度，其目的是按照一定的策略和方法將處理機(jī)分配給某個(gè)就緒進(jìn)程并為該進(jìn)程的執(zhí)行準(zhǔn)備環(huán)境

進(jìn)程調(diào)度的功能記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況(狀態(tài)跟蹤)選擇占有處理機(jī)的進(jìn)程調(diào)度策略與算法進(jìn)程上下文切換保存正在執(zhí)行進(jìn)程的現(xiàn)場，為將要執(zhí)行的進(jìn)程準(zhǔn)備現(xiàn)場處理機(jī)回收進(jìn)程被撤消后須回收被占用的處理機(jī)進(jìn)程調(diào)度的時(shí)機(jī)正在執(zhí)行中的進(jìn)程執(zhí)行完畢正在執(zhí)行中的進(jìn)程被阻塞分時(shí)系統(tǒng)中時(shí)間片用完執(zhí)行完系統(tǒng)調(diào)用等系統(tǒng)程序后返回用戶進(jìn)程時(shí)更高優(yōu)先級(jí)的進(jìn)程處于就緒狀態(tài)進(jìn)程調(diào)度中的上下文切換進(jìn)程在其上下文所確定的環(huán)境中運(yùn)行，當(dāng)執(zhí)行的進(jìn)程發(fā)生改變或出現(xiàn)進(jìn)程調(diào)度時(shí)，需要進(jìn)行上下文切換上下文切換的內(nèi)容決定是否做或是否允許做上下文切換切換上下文——原則是不破壞原進(jìn)程的上下文處理機(jī)切換進(jìn)程調(diào)度算法先來先服務(wù)（FCFS，firstcomefirstservice）這種調(diào)度算法按照進(jìn)程進(jìn)入就緒隊(duì)列的先后順序來調(diào)度進(jìn)程。獲得處理機(jī)的進(jìn)程，未遇到其他情況時(shí)，一直運(yùn)行下去。系統(tǒng)只需具備一個(gè)先進(jìn)先出的隊(duì)列，這種方法是一種最常見策略，并且在沒有其他信息時(shí)，也是一種最合理的策略。優(yōu)點(diǎn)是實(shí)現(xiàn)簡單缺點(diǎn)是對(duì)那些執(zhí)行時(shí)間較短的進(jìn)程來說，將等待較長的時(shí)間，從而降低CPU的利用率。在實(shí)際操作系統(tǒng)中，F(xiàn)CFS算法常常和其它的算法配合起來使用，例如，基于優(yōu)先級(jí)的調(diào)度算法就是對(duì)具有同樣優(yōu)先級(jí)的進(jìn)程采用FCFS算法。輪轉(zhuǎn)調(diào)度（RR，roundrobin）輪轉(zhuǎn)調(diào)度算法是系統(tǒng)把所有就緒進(jìn)程按先后次序排隊(duì)，處理機(jī)總是優(yōu)先分配給就緒隊(duì)列中的第一個(gè)就緒進(jìn)程，并分配它一個(gè)固定的時(shí)間片（如100毫秒）。當(dāng)該運(yùn)行進(jìn)程用完規(guī)定的時(shí)間片時(shí)，被迫釋放處理機(jī)給下一個(gè)處于就緒隊(duì)列中的第一個(gè)進(jìn)程，分給這個(gè)進(jìn)程相同的時(shí)間片，每個(gè)運(yùn)行完時(shí)間片的進(jìn)程，當(dāng)未遇到任何阻塞時(shí)，就回到就緒隊(duì)列的尾部，并等待下次轉(zhuǎn)到它時(shí)再投入運(yùn)行。于是，只要是處于就緒隊(duì)列中的進(jìn)程，按此種算法遲早總可以分得處理機(jī)投入運(yùn)行。輪轉(zhuǎn)法只能用來調(diào)度分配那些可以搶占的資源。這可以搶占的資源可以隨時(shí)剝奪，而且可以將它們?cè)俜峙浣o別的進(jìn)程。CPU是可搶占的資源的一種。但打印機(jī)等輸入輸出設(shè)備是不可搶占的資源。另外，時(shí)間片長度的選擇是根據(jù)系統(tǒng)對(duì)響應(yīng)時(shí)間的要求和就緒隊(duì)列中所允許的最大進(jìn)程數(shù)確定（進(jìn)程數(shù)越大，則時(shí)間片應(yīng)相應(yīng)小，確保合適的等待時(shí)間）的。多級(jí)反饋輪轉(zhuǎn)法（RRMF，roundrobinwithmultiplefeedback）把所有就緒進(jìn)程按下述方法排成多個(gè)隊(duì)列時(shí)間片用完但執(zhí)行未完成的就緒進(jìn)程時(shí)間片未用完但提前被阻塞（因?yàn)镮/O或互斥、同步），后又恢復(fù)到就緒狀態(tài)的進(jìn)程新創(chuàng)建還未執(zhí)行過的就緒進(jìn)程每個(gè)隊(duì)列內(nèi)部按照FCFS排序各個(gè)隊(duì)列的頂部進(jìn)程，設(shè)置不同的優(yōu)先級(jí)，選擇最高優(yōu)先級(jí)的進(jìn)程執(zhí)行思考：如何確保公平性，沒有考慮進(jìn)程等待時(shí)間優(yōu)先級(jí)算法算法為每個(gè)進(jìn)程分配一個(gè)優(yōu)先級(jí)，調(diào)度時(shí)總是調(diào)度優(yōu)先級(jí)最高的進(jìn)程執(zhí)行當(dāng)出現(xiàn)比當(dāng)前正在執(zhí)行的進(jìn)程優(yōu)先級(jí)更高的就緒進(jìn)程時(shí)，調(diào)度該進(jìn)程執(zhí)行，原執(zhí)行進(jìn)程的狀態(tài)轉(zhuǎn)換為就緒優(yōu)先級(jí)確定方法靜態(tài)優(yōu)先級(jí)的確定用戶指定作業(yè)的優(yōu)先級(jí)，與之相關(guān)的進(jìn)程有相同的優(yōu)先級(jí)系統(tǒng)進(jìn)程較用戶進(jìn)程有更高的優(yōu)先級(jí)系統(tǒng)根據(jù)進(jìn)程的類別設(shè)置優(yōu)先級(jí)，如：I/O繁忙程度，CPU繁忙程度，I/O與CPU均衡程度，……動(dòng)態(tài)優(yōu)先級(jí)的確定進(jìn)程占有CPU時(shí)間越長，被阻塞后再次稱為就緒狀態(tài)時(shí)，優(yōu)先級(jí)越低（公平性實(shí)現(xiàn)的機(jī)制）就緒進(jìn)程等待執(zhí)行的時(shí)間越長，其優(yōu)先級(jí)越高（考慮等待時(shí)間）線性優(yōu)先級(jí)調(diào)度算法（1）設(shè)置一個(gè)后備隊(duì)列，接納新創(chuàng)建進(jìn)程，后備隊(duì)列中最前面的進(jìn)程，在一定的情況下，進(jìn)入服務(wù)隊(duì)列；（2）兩個(gè)隊(duì)列內(nèi)部按照FCFS方式排列；（3）為每個(gè)進(jìn)程定義可變的優(yōu)先級(jí)；優(yōu)先級(jí)的變化規(guī)則：進(jìn)程在后備隊(duì)列中時(shí)，優(yōu)先級(jí)增長速度較快P(t)=a×(t-t0)其中t0為到達(dá)后備隊(duì)列的時(shí)刻在服務(wù)隊(duì)列中時(shí)，增長較慢P(t)=a×(t1-t0)+b×(t-t1)升遷規(guī)則：當(dāng)后備隊(duì)列中第一個(gè)進(jìn)程的優(yōu)先級(jí)超過了服務(wù)隊(duì)列中最后一個(gè)進(jìn)程的優(yōu)先級(jí)，則離開后備隊(duì)列而到服務(wù)隊(duì)列尾部開始排隊(duì)；若服務(wù)隊(duì)列為空，則后備隊(duì)列中第一個(gè)立即進(jìn)入服務(wù)隊(duì)列優(yōu)先級(jí)變化函數(shù)曲線最高響應(yīng)比算法R=(W+T)/T=1+W/T調(diào)度算法評(píng)價(jià)定性評(píng)價(jià)調(diào)度算法可靠性是否回引起系統(tǒng)故障，上下文破壞等調(diào)度算法簡潔性算法實(shí)現(xiàn)是否容易等定量評(píng)價(jià)CPU利用率進(jìn)程響應(yīng)時(shí)間注:m(k)qu=1，m(k)表示k的平均值，R為響應(yīng)時(shí)間(到達(dá)和離開的時(shí)間差)的數(shù)學(xué)期望短作業(yè)因?yàn)閗值小，Rrr<Rsr<Rfcfs長作業(yè)因?yàn)閗較大，Rfcfs<Rsr<Rrru為服務(wù)率，1/u為CPU完成執(zhí)行一個(gè)進(jìn)程所需的平均時(shí)間；λ為到達(dá)率，1/λ為進(jìn)程到達(dá)間隔時(shí)間的平均值參考排隊(duì)論和連續(xù)同質(zhì)馬氏模型的書籍三個(gè)算法性能比較的感性認(rèn)識(shí)：（1）為什么平均情況下，響應(yīng)時(shí)間相等（CPU一直處于忙的狀態(tài)）（2）短作業(yè)情況下（因?yàn)槎套鳂I(yè)前面的長作業(yè)用完時(shí)間片提前推出，減少了短作業(yè)的等待時(shí)間）（3）長作業(yè)情況下(分片太多，頻繁的從執(zhí)行到就緒的切換)（4）CPU占用率§5、進(jìn)程互斥與同步進(jìn)程間的制約例1進(jìn)程1、進(jìn)程2共享打印機(jī)緩沖區(qū)（公有資源），顯然它們應(yīng)互斥地向緩沖區(qū)寫數(shù)據(jù)——間接制約例2進(jìn)程1、進(jìn)程2共享它們之間的緩沖區(qū)（私有資源），顯然應(yīng)同步地使用緩沖區(qū)(須保證進(jìn)城2所讀恰為進(jìn)程1所寫)——直接制約緩沖區(qū)為進(jìn)程1和進(jìn)程2私有，不允許其他進(jìn)程干擾進(jìn)程1進(jìn)程2打印機(jī)緩沖區(qū)寫進(jìn)程1進(jìn)程2緩沖區(qū)寫讀產(chǎn)生制約的原因進(jìn)程并發(fā)執(zhí)行——>資源共享資源有限——>資源競爭制約的分類間接制約（由共享和競爭公共資源引起的制約）一組在異步環(huán)境下的并發(fā)進(jìn)程，由于不允許并發(fā)進(jìn)程交叉使用共享公有資源(只能獨(dú)占使用)，從而限制各進(jìn)程的執(zhí)行速度的過程稱為并發(fā)進(jìn)程間的間接制約直接制約（由共享和競爭私有資源引起的制約）一組在異步環(huán)境下的并發(fā)進(jìn)程，各自的執(zhí)行結(jié)果互為對(duì)方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度的過程稱為并發(fā)執(zhí)行進(jìn)程間的直接制約（一次寫后面必須緊接著一次讀，不允許第三方進(jìn)程參與）互斥：因間接制約而形成的進(jìn)程執(zhí)行方式同步：因直接制約而形成的進(jìn)程執(zhí)行方式異步：系統(tǒng)中的進(jìn)程或組件執(zhí)行步調(diào)和速度不一致，沒有統(tǒng)一的全局時(shí)鐘臨界資源與臨界區(qū)臨界資源任意時(shí)刻只允許一個(gè)進(jìn)程使用的資源如：打印機(jī)、鍵盤、一些數(shù)據(jù)、表格、隊(duì)列等臨界區(qū)訪問臨界資源的程序（程序段），即不允許并發(fā)進(jìn)程交叉執(zhí)行的程序（程序段）如：寫打印機(jī)緩沖區(qū)的程序（沒有分時(shí)的打印機(jī)），……臨界資源的訪問方式——互斥進(jìn)程互斥執(zhí)行應(yīng)滿足的準(zhǔn)則不能假設(shè)各并發(fā)進(jìn)程的相對(duì)執(zhí)行速度（因?yàn)楫惒剑└鞑l(fā)進(jìn)程享有平等的、獨(dú)立的競爭和使用共有資源的權(quán)利（實(shí)現(xiàn)互斥的策略不能犧牲任何一個(gè)進(jìn)程）在不采取任何措施的條件下，在臨界區(qū)內(nèi)任一指令結(jié)束時(shí)，其它并發(fā)進(jìn)程可以進(jìn)入臨界區(qū)并發(fā)進(jìn)程中的某個(gè)進(jìn)程不在臨界區(qū)時(shí)，它不阻止其它進(jìn)程進(jìn)入臨界區(qū)并發(fā)進(jìn)程中的若干個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)，只允許一個(gè)進(jìn)程進(jìn)入并發(fā)進(jìn)程中的某個(gè)進(jìn)程從申請(qǐng)進(jìn)入臨界區(qū)開始，應(yīng)在有限時(shí)間內(nèi)進(jìn)入臨界區(qū)，也應(yīng)在有限時(shí)間之內(nèi)退出臨界區(qū)（確保公平性）進(jìn)程互斥的實(shí)現(xiàn)方法加鎖實(shí)現(xiàn)原理鎖的初始狀態(tài)為開(s=1)當(dāng)有進(jìn)程進(jìn)入臨界區(qū)時(shí)，設(shè)置鎖的狀態(tài)為關(guān)(s=0)當(dāng)進(jìn)程從臨界區(qū)退出時(shí)，設(shè)置鎖的狀態(tài)為開(s=1)只有鎖的狀態(tài)為開時(shí)，進(jìn)程才能進(jìn)入臨界區(qū)加鎖后的臨界區(qū)程序lock(s)

臨界區(qū)unlock(s)代碼functionlock(s)functionunlock(s){{repeatuntils=1（反復(fù)檢查）s=1s=0}}分析當(dāng)Lock的執(zhí)行結(jié)束，s=0執(zhí)行之前時(shí)間片到，或者CPU被強(qiáng)占，會(huì)出現(xiàn)什么情況？如何解決？加鎖操作因?yàn)闀r(shí)間片用完而出現(xiàn)操作延遲，當(dāng)有多個(gè)進(jìn)程試加鎖時(shí)，因?yàn)镾來不及改成0，而都進(jìn)入了關(guān)鍵區(qū)（第二個(gè)進(jìn)程的執(zhí)行插在了第一進(jìn)程兩條之間,第三個(gè)進(jìn)程的執(zhí)行插在了第二個(gè)進(jìn)程兩條之間…..,每個(gè)進(jìn)程對(duì)S值進(jìn)行檢測都得到S=1結(jié)果，都進(jìn)入關(guān)鍵區(qū)）。改進(jìn)：硬件實(shí)現(xiàn)前后兩條執(zhí)行不分離其他不足：只要有一個(gè)進(jìn)程由于執(zhí)行LOCK（S）而進(jìn)入臨界區(qū)，則其它進(jìn)程在檢查鎖狀態(tài)時(shí)都將反復(fù)執(zhí)行LOCK（S）原語，從而導(dǎo)致處理機(jī)繁忙公平性問題，若程序要求一個(gè)進(jìn)程反復(fù)的調(diào)用LOCK原語和UNLOCK原語，那么S只在很短的時(shí)間間隙內(nèi)為1，其他進(jìn)程很難得到執(zhí)行權(quán)。公平性不保信號(hào)量（使用權(quán)和使用的分離，申請(qǐng)到使用權(quán)，再根據(jù)資源情況決定是否占用）例交通系統(tǒng)中的信號(hào)燈——它表示當(dāng)前道路是否可以通行信號(hào)量——某種資源可以使用的狀況，用整型變量s表示s>0——資源還有s個(gè)可供使用s=0——資源用盡，且還沒有等待進(jìn)程s<0——有|s|個(gè)進(jìn)程等待使用資源例：設(shè)S表示系統(tǒng)中可使用的打印機(jī)數(shù)量，有S=1——表示還有一臺(tái)打印機(jī)可供使用S=0——表示目前沒有打印機(jī)可供使用，且還沒有等待的進(jìn)程S=-1——表示有一個(gè)進(jìn)程等待使用打印機(jī)P、V原語（信號(hào)量操作）用P、V操作來修改信號(hào)量S的值P操作入口S=S-1調(diào)用進(jìn)程入等待隊(duì)列S>=0轉(zhuǎn)進(jìn)程調(diào)度調(diào)用進(jìn)程繼續(xù)執(zhí)行是否不管能不能得到資源，只要有申請(qǐng)S就減一V操作入口S=S+1喚醒等待隊(duì)列中的一個(gè)進(jìn)程，并置狀態(tài)為就緒S<=0調(diào)用進(jìn)程繼續(xù)執(zhí)行調(diào)用進(jìn)程繼續(xù)執(zhí)行是否（沒有等待進(jìn)程）用P、V操作實(shí)現(xiàn)進(jìn)程互斥原理設(shè)信號(hào)量S為全局變量，初值為S=1S對(duì)應(yīng)的資源同一時(shí)刻最多只能有一個(gè)進(jìn)程使用訪問資源前調(diào)用P操作，訪問結(jié)束時(shí)調(diào)用V操作使用資源的兩個(gè)互斥進(jìn)程描述為PAPB

…

……P(S)

P(S)<資源調(diào)用><資源調(diào)用>

V(S)V(S)

……

……例設(shè)A，B兩站之間是單軌鐵路，用P、V操作對(duì)通過該段鐵路的列車設(shè)置安全保護(hù)注意：進(jìn)程可能被凍結(jié)入等待隊(duì)列，或被喚醒（由另一個(gè)進(jìn)程的V原語），并非從上到下自主的執(zhí)行設(shè)信號(hào)量S的初值為1，AB間列車安全運(yùn)行進(jìn)程：

……

P(S)<列車在AB間運(yùn)行>

V(S)

……設(shè)圖書館有某種圖書5本。請(qǐng)建立讀者程序和借閱程序，保證同一時(shí)刻最多能有5個(gè)讀者可以借到該書。注：讀者借還書的時(shí)間和順序是隨機(jī)的思考：分時(shí)系統(tǒng)的情況下，PV方式的進(jìn)程調(diào)度，是否會(huì)出現(xiàn)加鎖方式進(jìn)程調(diào)度遇到的問題？b進(jìn)行P原語操作時(shí)，s已經(jīng)為小于零，b直接進(jìn)入等待隊(duì)列進(jìn)程同步的實(shí)現(xiàn)例計(jì)算進(jìn)程PC將計(jì)算結(jié)果寫到緩沖區(qū)Buf中，打印進(jìn)程PP從Buf中取出數(shù)據(jù)進(jìn)行打印。要求是只有Buf為空時(shí)，PC才能寫入數(shù)據(jù)；只有Buf為滿時(shí)，PP才能取出數(shù)據(jù)從Buf中取出數(shù)據(jù)后，Buf為空初始時(shí)Buf為空分析顯然PC與PP在執(zhí)行時(shí)必須協(xié)調(diào)速度，即對(duì)Buf的操作應(yīng)該是：PC寫，PP取，PC寫，PP取，PC寫，PP取，（所讀必須與寫的內(nèi)容一一對(duì)應(yīng)）……PC與PP同步實(shí)現(xiàn)同步的方法可以是PP等PC寫之后再取PC等PP取之后再寫實(shí)現(xiàn)設(shè)Buf有兩個(gè)狀態(tài)：Bufempty，Buffull用State變量記Buf的狀態(tài)……PP與PC為PPPC

……

……repeatrepeatuntilState=BufemptyuntilState=Buffull

計(jì)算取出Buf中的內(nèi)容

Buf

計(jì)算結(jié)果Buf清空

State=BuffullState=Bufempty

……

……上述Bufempty，Buffull成為PP與PC之間的公用變量，但對(duì)系統(tǒng)或其它進(jìn)程來講并不知道它們的存在，故稱其為PP與PC的私有信號(hào)量缺點(diǎn)：反復(fù)的檢測狀態(tài)，CPU開銷很大改進(jìn)：用進(jìn)程間消息收發(fā)的方式wait(x)進(jìn)程等待x消息，未等到則處于休眠狀態(tài)，無需循環(huán)的檢測signal(x)進(jìn)程發(fā)送x消息互補(bǔ)的狀態(tài)消息對(duì)：buffempty,bufffull互補(bǔ)，一個(gè)為真則另一個(gè)為假。初始時(shí)buff為空Pc:A:wait(buffempty)

計(jì)算計(jì)算結(jié)果向buff賦值

buffempty改為假

signal(buffull)gotoAPp:B:wait(buffull)

打印buf中的數(shù)據(jù)清除buf中的數(shù)據(jù)

buffull改為假

signal(bufempty)gotoB用P、V操作實(shí)現(xiàn)進(jìn)程同步原理為并發(fā)進(jìn)程設(shè)置信號(hào)量，以表示資源的可獲得性初始化它們的值用P、V操作限定進(jìn)程的執(zhí)行順序(1)緩沖區(qū)為空，則Pb無法讀取數(shù)據(jù)(2)緩沖區(qū)為滿，則Pa無法寫數(shù)據(jù)(3)緩沖區(qū)按照FIFO隊(duì)列方式組織數(shù)據(jù)發(fā)送和接受，分別由deposit（x）和remove（x）實(shí)現(xiàn)Bufempty初始值為n，為Pa的私有信號(hào)量，用于控制PaBuffull初始值為0，為Pb的私有信號(hào)量，用于控制PbPa:deposit()beginlocalx

P(bufempty)查找緩沖區(qū)，決定放入地址x向buf(x)寫入數(shù)據(jù)標(biāo)記buf(x)為占用V(buffull)Pb:remove()beginlocalx

P(buffull)查找緩沖區(qū)，決定讀取地址x從buf(x)讀出數(shù)據(jù)標(biāo)記buf(x)為空閑V(bufempty)將“空”視為資源將“滿”視為資源喚醒喚醒生產(chǎn)者—消費(fèi)者問題進(jìn)程互斥和同步問題可以抽象為生產(chǎn)者—消費(fèi)者問題生產(chǎn)者生產(chǎn)出產(chǎn)品后，消費(fèi)者才能消費(fèi)當(dāng)部分產(chǎn)品消費(fèi)后，生產(chǎn)者才繼續(xù)生產(chǎn)一件產(chǎn)品，不能既在生產(chǎn)又在消費(fèi)該問題可形式化為有界緩沖區(qū)共n個(gè)單元生產(chǎn)者進(jìn)程向緩沖區(qū)中寫數(shù)據(jù)，每次寫一個(gè)單元消費(fèi)者進(jìn)程讀緩沖區(qū)中的數(shù)據(jù)，每次寫一個(gè)單元緩沖區(qū)至少有一個(gè)單元有數(shù)據(jù)（滿）時(shí)，才能讀緩沖區(qū)至少有一個(gè)單元無數(shù)據(jù)（空）時(shí)，才能寫生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程不能同時(shí)操作緩沖區(qū)生產(chǎn)與消費(fèi)同步生產(chǎn)與消費(fèi)互斥P1p2…Pn……P1p2…Pn假設(shè)：PA——生產(chǎn)者進(jìn)程，PB——消費(fèi)者進(jìn)程生產(chǎn)者與消費(fèi)者的互斥設(shè)公共信號(hào)量：mutex，初值為1，用于避免兩個(gè)進(jìn)程同時(shí)操作隊(duì)列

PAPB

……

……P（mutex）P（mutex）

生產(chǎn)者生產(chǎn)數(shù)據(jù)緩沖區(qū)緩沖區(qū)數(shù)據(jù)消費(fèi)者消費(fèi)

V（mutex）V（mutex）

……

……生產(chǎn)者與消費(fèi)者的同步設(shè)生產(chǎn)者進(jìn)程的私有信號(hào)量，控制生產(chǎn)者：avail——當(dāng)前可用的緩沖區(qū)單元數(shù)，初值為n設(shè)消費(fèi)者進(jìn)程的私有信號(hào)量，控制消費(fèi)者：full——緩沖區(qū)中有數(shù)據(jù)的單元數(shù)，初值為0生產(chǎn)者與消費(fèi)者的同步為：喚醒

PAPB

……

……P（avail）P（full）

生產(chǎn)者生產(chǎn)數(shù)據(jù)緩沖區(qū)緩沖區(qū)數(shù)據(jù)消費(fèi)者消費(fèi)

V（full）V（avail）

……

……生產(chǎn)者與消費(fèi)者問題的最終解

PAPB

……

……P（avail）P（full）P（mutex）P（mutex）

生產(chǎn)者生產(chǎn)數(shù)據(jù)緩沖區(qū)緩沖區(qū)數(shù)據(jù)消費(fèi)者消費(fèi)

V（full）V（avail）V（mutex）V（mutex）

……

……思考：取消mutex有什么影響喚醒申請(qǐng)存儲(chǔ)空間申請(qǐng)數(shù)據(jù)申請(qǐng)緩沖區(qū)的操作權(quán)申請(qǐng)緩沖區(qū)的操作權(quán)問題多個(gè)生產(chǎn)者之間的生產(chǎn)互斥嗎？為什么？多個(gè)消費(fèi)者之間的生產(chǎn)互斥嗎？為什么？如何才能使得多個(gè)生產(chǎn)者可以同時(shí)生產(chǎn)？多個(gè)消費(fèi)者之間可以同時(shí)消費(fèi)？設(shè)置專門的讀寫mutexmutex_write/mutex_read初始值為n/m表示最多允許n/m個(gè)進(jìn)程同時(shí)寫。修改P原語，一旦mutex_write/mutex_read申請(qǐng)成功，則將對(duì)應(yīng)的mutex_read/write改為0。修改V原語，一旦mutex_write/mutex_read恢復(fù)初始值，則對(duì)應(yīng)的mutex_read/write也回復(fù)初始值允許多個(gè)消費(fèi)者同時(shí)消費(fèi)，或者多個(gè)生產(chǎn)者同時(shí)生產(chǎn)，但不允許消費(fèi)和生產(chǎn)同時(shí)進(jìn)行§6、進(jìn)程通信通信——指進(jìn)程間相互傳遞信息（數(shù)據(jù)）分類低級(jí)通信傳送控制信息，一般為一個(gè)或幾個(gè)字節(jié)，目的是控制進(jìn)程的速度如：信號(hào)量，鎖，……高級(jí)通信傳送大量數(shù)據(jù)，目的是交換信息（數(shù)據(jù)）例子：webservice服務(wù)進(jìn)程之間的交互如：消息，查詢結(jié)果，文件、多媒體數(shù)據(jù)……通信方式與特點(diǎn)主從式通信的進(jìn)程被分為主進(jìn)程和從進(jìn)程特點(diǎn)主進(jìn)程可以自由地使用從進(jìn)程的資源或數(shù)據(jù)從進(jìn)程的動(dòng)作受主進(jìn)程的控制主進(jìn)程與從進(jìn)程的關(guān)系是固定的例終端控制進(jìn)程與終端進(jìn)程缺乏靈活性會(huì)話式通信的進(jìn)程分別稱為調(diào)用進(jìn)程和服務(wù)進(jìn)程。調(diào)用進(jìn)程調(diào)用服務(wù)進(jìn)程提供的服務(wù)特點(diǎn)調(diào)用進(jìn)程在使用服務(wù)進(jìn)程之前必須得到服務(wù)進(jìn)程的許可服務(wù)進(jìn)程按使用進(jìn)程的要求提供服務(wù)，對(duì)所提供服務(wù)的控制由服務(wù)進(jìn)程完成在每次通信時(shí)，服務(wù)進(jìn)程與調(diào)用進(jìn)程間的關(guān)系是固定的服務(wù)進(jìn)程與調(diào)用進(jìn)程在不同的通信中關(guān)系是可變的例用戶進(jìn)程與磁盤管理進(jìn)程間的通信進(jìn)程自調(diào)用方式消息或郵箱機(jī)制通信進(jìn)程分為發(fā)送進(jìn)程和接收進(jìn)程，它們是平等的進(jìn)程間通過緩沖區(qū)或郵箱交換大量信息組成消息格式緩沖區(qū)或郵箱特點(diǎn)只要存在空緩沖區(qū)或郵箱，發(fā)送進(jìn)程就可發(fā)送消息發(fā)送與接收進(jìn)程無直接聯(lián)系，甚至可以不知道對(duì)方的存在（松散）通過緩沖區(qū)或郵箱來存放被傳送的消息發(fā)送進(jìn)程接收進(jìn)程操作數(shù)據(jù)……PSPR緩沖區(qū)或郵箱共享存儲(chǔ)區(qū)方式通信進(jìn)程通過對(duì)同一共享數(shù)據(jù)區(qū)的操作來交換信息特點(diǎn)共享數(shù)據(jù)區(qū)是每個(gè)互相通信進(jìn)程的一個(gè)組成部分（執(zhí)行內(nèi)存空間）傳送的數(shù)據(jù)量大，速度快不移動(dòng)數(shù)據(jù)，存儲(chǔ)區(qū)既是前一個(gè)進(jìn)程的輸出空間，也是后一個(gè)進(jìn)程的執(zhí)行空間注：無論那種通信方式，都需要解決進(jìn)程間的同步或互斥消息緩沖通信原理發(fā)送進(jìn)程在自己的內(nèi)存空間申請(qǐng)發(fā)送緩沖區(qū)將數(shù)據(jù)填入緩沖區(qū)發(fā)送——將緩沖區(qū)掛入消息隊(duì)列接收進(jìn)程在自己的內(nèi)存空間申請(qǐng)接收緩沖區(qū)接收——摘取消息隊(duì)列中的消息將數(shù)據(jù)填入緩沖區(qū)約束發(fā)送進(jìn)程寫緩沖區(qū)和消息隊(duì)列時(shí)，禁止其它進(jìn)程訪問該緩沖區(qū)與消息隊(duì)列(消息隊(duì)列互斥操作)接收進(jìn)程取消息隊(duì)列時(shí)，禁止其它進(jìn)程訪問該消息隊(duì)列(消息隊(duì)列互斥操作)發(fā)送進(jìn)程申請(qǐng)不到緩沖區(qū)時(shí)，不能發(fā)送消息隊(duì)列為空時(shí)，接收進(jìn)程不能接收消息甲乙兩進(jìn)程的發(fā)送與接收過程甲進(jìn)程發(fā)送過程甲進(jìn)程在發(fā)送消息前，在本進(jìn)程所占空間中開辟一發(fā)送區(qū)；使用send原語（要么成功發(fā)送完，要么不發(fā)送，不存在中間狀態(tài)）send程序向系統(tǒng)申請(qǐng)一個(gè)消息緩沖區(qū)，將發(fā)送區(qū)中消息正文、長度和發(fā)送進(jìn)程名填入；將緩沖區(qū)掛到接收消息的乙進(jìn)程消息鏈鏈尾；退出send，甲進(jìn)程繼續(xù)執(zhí)行乙進(jìn)程接收過程乙進(jìn)程在接收消息前，在本進(jìn)程所占空間中開辟一接收區(qū)；使用receive原語receive程序?qū)⒁疫M(jìn)程消息鏈區(qū)中第一個(gè)消息緩沖區(qū)中的內(nèi)容、長度、本消息發(fā)送者名字，填入接收區(qū)；將緩沖區(qū)從消息鏈中摘除，釋放緩沖區(qū)；退出read程序，乙進(jìn)程繼續(xù)執(zhí)行Send(m)：Begin

向系統(tǒng)申請(qǐng)一個(gè)消息緩沖區(qū)

P(mutex)

將發(fā)送區(qū)消息m送入新申請(qǐng)的消息緩沖區(qū)將消息緩沖區(qū)掛入接收進(jìn)程的消息隊(duì)列

V(mutex)V(SM)EndReceive(n)：BeginP(SM)P(mutex)

摘下消息隊(duì)列中的消息n

將消息n從緩沖區(qū)復(fù)制到接收區(qū)釋放緩沖區(qū)

V(mutex)End?信號(hào)量的初值確定SM初始為0，表示待接受的消息數(shù)量為0郵箱通信原理由發(fā)送進(jìn)程申請(qǐng)建立一個(gè)與接收進(jìn)程相連接的郵箱發(fā)送進(jìn)程將消息送往郵箱，接收進(jìn)程從郵箱中取走消息郵箱組成郵箱可以設(shè)置成發(fā)送與接收進(jìn)程之間大小固定的私有數(shù)據(jù)結(jié)構(gòu)郵箱由郵箱頭和郵箱體組成郵箱頭：描述郵箱名稱、大小、方向、擁有該郵箱的進(jìn)程郵箱體：存放消息發(fā)送進(jìn)程接收進(jìn)程郵箱頭

……郵箱體通信要求發(fā)送消息時(shí)，至少郵箱中有一個(gè)空格能存放該消息接收消息時(shí)，至少郵箱中有一個(gè)消息存在發(fā)送進(jìn)程與接收進(jìn)程設(shè)formnum為郵箱中空格數(shù)，mesnum為郵箱中消息數(shù)Deposit(m)Remove(m)beginbeginP(formnum)P(mesnum)

選擇一個(gè)空格x選擇一個(gè)滿格x

將消息m放入x將x中的消息放入m

置x的標(biāo)志為滿置x的標(biāo)志為空

V(mesnum)V(formnum)endend?Formnum與mesnum的初值是什么n，0Deposit與Remove之間是同步？互斥？其它？一次deposite之后并非一定要一次remove，郵箱的讀寫也可以并行，沒有mutex控置量限制。同消息緩沖方式的區(qū)別多個(gè)Deposit間是同步？互斥？其它？只要空間允許，無限制多個(gè)Remove間是同步？互斥？其它？只要消息數(shù)量允許，無限制將存儲(chǔ)空間視為資源將消息視為資源進(jìn)程通信的實(shí)例和控制臺(tái)的通信鍵盤控制進(jìn)程－－KCP(從鍵盤中取數(shù)據(jù)送入inbuf)顯示控制進(jìn)程－－DCP(取outbuf中數(shù)據(jù)到控制臺(tái)顯示器顯示)會(huì)話控制進(jìn)程—CCP(從inbuf中讀出消息放入消息隊(duì)列,把消息隊(duì)列中的消息取出寫入outbuf)系統(tǒng)操作員控制一臺(tái)“控制臺(tái)終端”，用戶進(jìn)程將消息發(fā)給控制臺(tái)，控制臺(tái)的操作員讀取到消息后做出處理?？刂婆_(tái)鍵盤的輸入數(shù)據(jù)放入隊(duì)列inbuf中，CCP可以從此中讀取消息。CCP提出的問題放入outbuf隊(duì)列，顯示器控制進(jìn)程從中讀取出，并通過顯示器輸出，供操作員觀察。和控制臺(tái)通信示例鍵盤顯示器鍵盤（KP）和鍵盤控制進(jìn)程（KCP）之間的通信信號(hào)量T-READY和T-BUSY，分別用于表示“一個(gè)單位的緩沖區(qū)中目標(biāo)數(shù)據(jù)是否到達(dá)”和“一個(gè)單位的緩沖區(qū)空間是否存在”,初始時(shí)分別為0和1KCP:(初始時(shí)inbuf和echobuf為空)Begin:localxP(T-ready)

從鍵盤緩存x中讀出字符m記為x.m

send（x.m）將x.m送入echobufV(T-busy)endKP:(初始時(shí)inbuf和echobuf為空)repeatlocalxP(T-busy)

把鍵入字符放入緩存xV(T-ready)Until鍵盤關(guān)閉讀緩沖寫緩沖顯示器（DP）和顯示器控制進(jìn)程（DCP）之間的通信DCP:(初始時(shí)outbuf為空，echo模式為0)Begin:ifoutbuf為滿

thenreceive(k)P(D-busy)

把k消息送入顯示器緩存

V(D-ready)elseecho模式改為1echobuf中字符傳入顯示器緩存

fiDP:(初始時(shí)outbuf為空，echo模式為0)repeatIfecho模式為1Then打印緩存中的字符ElseP(D-ready)

打印緩沖區(qū)中的消息

V(D-busy)Until顯示器關(guān)閉信號(hào)量D-READY和D-BUSY，分別用于表示“一個(gè)單位的緩沖區(qū)中目標(biāo)數(shù)據(jù)是否到達(dá)”和“一個(gè)單位的緩沖區(qū)的可用空間是否存在”,初始時(shí)分別為0和1寫緩沖讀緩沖在不需要進(jìn)行緩沖讀寫時(shí)，進(jìn)行字符打印的操作CCP和KCP以及DCP之間的交互函數(shù)Read(x)將inbuf中所有的字符讀到控制終端的用戶數(shù)據(jù)區(qū)x，write(y)把用戶進(jìn)程y的消息寫到outbuf中Read(x):beginP(inbuf-full)Copy(inbufintox)V(inbuf-empty)endwrite(y):beginP(outbuf-empty)Copy(outbuffromy)V(outbuf-full)end進(jìn)程通信的實(shí)例——管道1.管道pipeUnix提供的管道有有名管道和無名管道.無名管道在邏輯上被看作是管道文件,物理上則由高速緩沖區(qū)構(gòu)成.發(fā)送進(jìn)程利用文件系統(tǒng)的系統(tǒng)調(diào)用write(fd[1],buf,size)將buf中長度為size字符的消息送入管道入口fd[1]，接收進(jìn)程則用read(fd[0])讀出處于出口位置（fd[0]）的消息。管道實(shí)行FIFO方式管理圖3.21管道通信實(shí)例，建立一個(gè)管道，進(jìn)程通信的實(shí)例——管道例2,P72父進(jìn)程生成兩個(gè)子進(jìn)程，兩個(gè)子進(jìn)程分別向管道寫數(shù)據(jù)，父進(jìn)程讀圖3.22父進(jìn)程和子進(jìn)程P1，P2通信例子由于兩個(gè)進(jìn)程須互斥對(duì)管道進(jìn)行操作，所以需要用lockf進(jìn)行加鎖§7、死鎖死鎖的概念死鎖是兩個(gè)或兩個(gè)以上的進(jìn)程中的每一個(gè)都在等待其中另一個(gè)進(jìn)程釋放資源而被封鎖，它們都無法向前推進(jìn)，陷入永久等待狀態(tài)，這種現(xiàn)象稱為死鎖。特點(diǎn)占有一定的資源，等待對(duì)方釋放資源獲得對(duì)方資源前不釋放自己占有的資源比較：死鎖與死循環(huán)，死鎖與死機(jī)P1P2S1S2擁有擁有請(qǐng)求請(qǐng)求死鎖的起因資源有限系統(tǒng)提供的資源個(gè)數(shù)少于并發(fā)進(jìn)程所需要的該類資源數(shù)資源競爭進(jìn)程的并發(fā)性造成對(duì)資源的競爭使用。一般我們不可能為所要求資源的進(jìn)程無限制地提供資源。關(guān)于死鎖的進(jìn)一步說明死鎖是進(jìn)程之間的一種特殊關(guān)系，是由資源競爭引起的僵局關(guān)系，因此，當(dāng)我們提到死鎖時(shí)，至少涉及到兩個(gè)進(jìn)程。雖然單個(gè)進(jìn)程也可能鎖住自己，但那是程序設(shè)計(jì)錯(cuò)誤而不是死鎖當(dāng)出現(xiàn)死鎖時(shí)，首先要弄清楚被鎖的是哪些進(jìn)程，因競爭哪些資源被鎖在多數(shù)情況下，系統(tǒng)出現(xiàn)死鎖，是指系統(tǒng)內(nèi)的一些而不是全部進(jìn)程被鎖，它們是因競爭某些而不是全部資源而進(jìn)入死鎖的，若系統(tǒng)的全部進(jìn)程都被鎖住，我們稱系統(tǒng)處于癱瘓狀態(tài)系統(tǒng)癱瘓意味著所有進(jìn)程都進(jìn)入了睡眠（阻塞）狀態(tài)，但所有進(jìn)程都睡眠了，如果其中至少有一個(gè)進(jìn)程可由I/O中斷喚醒的話，這并不一定就是癱瘓狀態(tài)產(chǎn)生死鎖的必要條件互斥條件在一段時(shí)間內(nèi)，一個(gè)資源只能由一個(gè)進(jìn)程獨(dú)占使用，若別的進(jìn)程也要求該資源，則須等待直至其占用者釋放——資源的互斥使用部分分配進(jìn)程每次申請(qǐng)它所需資源的一部分，在申請(qǐng)分配或等待新資源的同時(shí)繼續(xù)占有已分配的資源不剝奪條件進(jìn)程所獲得的資源在未使用完之前，不能被其它進(jìn)程強(qiáng)行奪走，而只能由獲得資源的進(jìn)程自己釋放；環(huán)路條件存在一個(gè)等待資源的進(jìn)程循環(huán)鏈，鏈中的每個(gè)進(jìn)程所獲得的資源是下一個(gè)進(jìn)程申請(qǐng)（等待）的資源顯然，上述條件中的任意一個(gè)不滿足，死鎖就不會(huì)發(fā)生死鎖的表示死鎖可以用有向圖來表示，有向圖形成環(huán)路則形成死鎖。例如，有P1，P2兩個(gè)進(jìn)程，共享一臺(tái)打印機(jī)資源R1和一臺(tái)輸入機(jī)R2，在工作使用時(shí)，共享資源被獨(dú)占。死鎖定理如果不出現(xiàn)任何環(huán)，則此時(shí)系統(tǒng)內(nèi)不存在死鎖如果出現(xiàn)了環(huán)，且處于此環(huán)中的每類資源均只有一個(gè)實(shí)體時(shí)，則有環(huán)就出現(xiàn)死鎖，此時(shí)，環(huán)是系統(tǒng)存在死鎖的充分必要條件如果系統(tǒng)資源分配圖中出現(xiàn)了環(huán)，但處于此環(huán)中的每類資源的個(gè)數(shù)不全為1(同種資源有多個(gè)副本)，則環(huán)的存在只是產(chǎn)生死鎖的必要條件而不是充分條件P1P2R1R2已占有正申請(qǐng)解決死鎖問題的基本方法解決死鎖的方法一般可分為預(yù)防、避免、檢測與恢復(fù)死鎖預(yù)防：打破造成死鎖的四個(gè)必要條件中的一個(gè)使互斥或不可剝奪條件不成立允許進(jìn)程同時(shí)訪問某些資源，如采用SPOOLING(SimultaneousPeripheralOperationOn-Line)技術(shù)問題這種方法不能解決訪問那些固有不允許被同時(shí)訪問的資源帶來的死鎖問題。使資源的部分分配條件不成立預(yù)先分配各并發(fā)進(jìn)程所需要的全部資源(見前一個(gè)圖)問題多數(shù)情況下，一個(gè)進(jìn)程在執(zhí)行前不可能提出它所需要的全部資源，資源的請(qǐng)求發(fā)生實(shí)時(shí)變化資源浪費(fèi)太大進(jìn)程的并發(fā)性降低，系統(tǒng)性能降低使環(huán)路條件不成立把資源分類，使進(jìn)程在申請(qǐng)、保持資源時(shí)不形成環(huán)路。如進(jìn)程申請(qǐng)的資源總是比已占有的資源的類別更高，釋放的次序與此相反，每個(gè)進(jìn)程按照相同的順序來進(jìn)行申請(qǐng)（見前一個(gè)圖）問題限制進(jìn)程對(duì)資源的請(qǐng)求增加系統(tǒng)開銷避免死鎖死鎖避免的基本模式：講進(jìn)程的執(zhí)行分成很多步，每個(gè)步所使用的資源是固定的，且在一個(gè)步內(nèi)，進(jìn)程保持資源數(shù)不變。資源的請(qǐng)求、使用與釋放要靠不同步完成。銀行家算法問題：一個(gè)銀行家在若干個(gè)顧客間共享他的資金(capital),每個(gè)顧客所需借款總額need<=capital.任務(wù)：銀行家應(yīng)能使他當(dāng)前的全部顧客在有限時(shí)間內(nèi)完成他們的交易（也就歸還了他們的借款?。?顧客狀態(tài)：（claim,loan）,claim=need-loan 銀行家狀態(tài)：(capital,cash),cash=capital-loan銀行家算法：保證銀行家狀態(tài)從一個(gè)安全狀態(tài)轉(zhuǎn)向另一個(gè)安全狀態(tài)——不死鎖！（判斷狀態(tài)是否安全） 從當(dāng)前狀態(tài)S（顧客狀態(tài)＋銀行家狀態(tài)）出發(fā)，逐個(gè)檢查各顧客中誰的claim<=cash,若其得到資源后能完成工作且歸還全部借款，再進(jìn)而檢查誰又能完成工作,…,如果所有顧客均能完成，則狀態(tài)是安全的。避免死鎖的算法：銀行家算法假設(shè)有三個(gè)進(jìn)程P、Q、R，系統(tǒng)只有某類資源共10個(gè)，而三個(gè)進(jìn)程合計(jì)申請(qǐng)資源數(shù)為20個(gè)。目前的分配情況如下：Claim為進(jìn)程希望下一步占有資源的情況而系統(tǒng)8+2=10此后P、R再申請(qǐng)資源就不能分配了。因?yàn)楝F(xiàn)在只剩下2個(gè)資源，不能滿足它們的最大要求(P:4,R:7)，如果將剩下2個(gè)分配給P或R，則會(huì)產(chǎn)生死鎖。注意：不允許部分分配，必須將進(jìn)程所需的資源一次性全部分配然而將2個(gè)資源分給Q(只需一個(gè))則Q可運(yùn)行結(jié)束、釋放系統(tǒng)資源回收為4個(gè)此后可將4個(gè)資源分組P…即QPR由此可見，按銀行家算法來分配資源是不會(huì)產(chǎn)生死鎖的。因?yàn)榘丛撍惴ǚ峙滟Y源時(shí)，每次分配后總存在一個(gè)進(jìn)程，如果讓它獨(dú)立單獨(dú)運(yùn)行下去，必然可獲得它所需的全部資源，也就是說它能結(jié)束。而它結(jié)束后可以歸還這類資源來滿足其它申請(qǐng)者的需要。這也說明了存在一個(gè)合理的系統(tǒng)狀態(tài)序列，可確保系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)的路徑。*單一種類資源引出的銀行家算法的基本思想也同樣適用于多種類的資源情況：ABCDEr1r2r3r4資源已分配情況r1r2r3r4下一步的資源期望還需(剩余需求)矩陣總共資源數(shù)r=(6,3,4,2)已分資源數(shù)

s=(5,3,2,2)余下資源數(shù)t=(1,0,2,0)(1)尋找剩余矩陣的某一未標(biāo)記的行x，使得它的每一個(gè)元素都不大于向量t

的對(duì)應(yīng)元素，如果找不到轉(zhuǎn)(4)。(2)對(duì)于找到的行x（上圖中的D），表示可以滿足它，標(biāo)記此進(jìn)程，并將它占有的資源加到向量t。(3)重復(fù)上述步驟，轉(zhuǎn)(1)。(4)如果所有進(jìn)程都已標(biāo)記，則狀態(tài)是安全的，否則為不安全。死鎖的檢測與恢復(fù)狀態(tài)變遷/轉(zhuǎn)移圖PETRI網(wǎng)由著名學(xué)者CarlAdamPetri于1962引入.建模并發(fā)和同步系統(tǒng)基于狀態(tài)機(jī)模型（并發(fā)和同步的狀態(tài)機(jī)）圖形化的描述方式完整的理論（邏輯、數(shù)學(xué)、形式語義）基礎(chǔ)PETRI網(wǎng)的狀態(tài)變化系統(tǒng)狀態(tài)的改變由庫所內(nèi)托肯（token）數(shù)量的變化和托肯在網(wǎng)內(nèi)的流動(dòng)所表征.變遷的觸發(fā)，表示由變遷所代表的系統(tǒng)行為的實(shí)施.變遷的觸發(fā)，受到輸入條件的限制：輸入庫所必須具有足夠數(shù)量的托肯.變遷觸發(fā)以后，托肯將從輸入庫所轉(zhuǎn)移到輸出庫所死鎖：某狀態(tài)下任何一個(gè)變遷都無法發(fā)生，系統(tǒng)陷入停頓實(shí)例:自動(dòng)售貨機(jī)售貨機(jī)出售兩種小吃：15美分的和20美分的.只有兩種硬幣：10美分和5美分的.售貨機(jī)不找零售貨機(jī)流程圖0cent5cents10cents15cents20centsDeposit5cDeposit10cDeposit10cDeposit10cDeposit5cDeposit5cDeposit5cTake20csnackbarTake15csnackbar5cTake15cbarDeposit5c0c