作業(yè)組織和管理主要內(nèi)容一、作業(yè)的概念二、批處理作業(yè)的組織和管理三、交互型作業(yè)的組織和管理一、作業(yè)的概念作業(yè)、進(jìn)程和線程是操作系統(tǒng)中不同級別的任務(wù)單位。任務(wù)單位作業(yè)對應(yīng)一個(gè)完整的業(yè)務(wù)處理過程，該過程包含若干個(gè)相對獨(dú)立又相互關(guān)聯(lián)的順序加工步驟，每個(gè)加工步驟稱為一個(gè)作業(yè)步。進(jìn)程或線程對應(yīng)一個(gè)作業(yè)步的處理過程。作業(yè)和作業(yè)步任務(wù)單位分解關(guān)系作業(yè)作業(yè)步進(jìn)程線程線程……進(jìn)程線程線程…………分解分解作業(yè)實(shí)例一個(gè)完整業(yè)務(wù)處理過程：開發(fā)和運(yùn)行程序作業(yè)任務(wù)：開發(fā)和運(yùn)行程序編輯源程序作業(yè)步1運(yùn)行編輯進(jìn)程作業(yè)步(工序)子任務(wù)任務(wù)實(shí)施編譯源程序作業(yè)步2運(yùn)行編譯進(jìn)程鏈接目標(biāo)程序作業(yè)步3運(yùn)行鏈接進(jìn)程獲得運(yùn)算結(jié)果作業(yè)步4運(yùn)行目標(biāo)進(jìn)程二、批處理作業(yè)的組織和管理（1）批處理作業(yè)的組成結(jié)構(gòu)（2）作業(yè)控制塊的內(nèi)容（3）批處理作業(yè)的調(diào)度主要內(nèi)容（1）批處理作業(yè)的組成結(jié)構(gòu)作業(yè)控制塊（JCB）程序數(shù)據(jù)作業(yè)說明書按規(guī)定格式書寫的一個(gè)文件，描述用戶對系統(tǒng)的各種請求和對作業(yè)的控制要求，與程序和數(shù)據(jù)一起提交給系統(tǒng)（管理員）作業(yè)實(shí)體結(jié)構(gòu)批處理作業(yè)被放到輸入井，然后成批執(zhí)行。（2）批處理作業(yè)的創(chuàng)建多道批處理操作系統(tǒng)的作業(yè)管理模塊為每一個(gè)作業(yè)建立作業(yè)控制塊（JCB）。批作業(yè)進(jìn)入系統(tǒng)時(shí)，Spooling（假脫機(jī)）系統(tǒng)建立JCB，它是作業(yè)存在于系統(tǒng)的標(biāo)志，作業(yè)撤離時(shí)，JCB也被撤銷。作業(yè)控制塊的內(nèi)容作業(yè)控制塊（JCB）程序數(shù)據(jù)作業(yè)說明書①作業(yè)情況（用戶名、作業(yè)名、語言名）②資源需求（估計(jì)CPU運(yùn)行時(shí)間、最遲截止期、主存量、設(shè)備類型/臺數(shù)、文件數(shù)和數(shù)據(jù)量、函數(shù)庫/實(shí)用程序等）③資源使用情況（進(jìn)入系統(tǒng)時(shí)間、開始運(yùn)行時(shí)間、己運(yùn)行時(shí)間），作業(yè)控制（優(yōu)先數(shù)、控制方式、操作順序、出錯處理等）、作業(yè)類型（CPU繁忙型、I/O繁忙型、批量型、終端型）等信息。作業(yè)實(shí)體結(jié)構(gòu)（3）批處理作業(yè)的調(diào)度執(zhí)行…磁盤后備作業(yè)隊(duì)列作業(yè)1作業(yè)n內(nèi)存選擇和裝入作業(yè)善后處理①選擇作業(yè)根據(jù)資源狀況和多道程序道數(shù)選擇②分配資源分配內(nèi)存、設(shè)備③創(chuàng)建進(jìn)程進(jìn)程調(diào)度程序?yàn)樽鳂I(yè)進(jìn)程分配處理器④作業(yè)控制Spooling根據(jù)作業(yè)控制塊控制作業(yè)的啟動、作業(yè)步轉(zhuǎn)接、程序調(diào)入、數(shù)據(jù)I/O、異常處理⑤后續(xù)處理作業(yè)正常結(jié)束或出錯終止時(shí)，作業(yè)調(diào)度程序回收資源、撤銷作業(yè)控制塊，并選擇新作業(yè)進(jìn)入主存三、交互型作業(yè)的組織和管理操作系統(tǒng)啟動時(shí)，為連接至系統(tǒng)的每個(gè)終端創(chuàng)建一個(gè)終端進(jìn)程，該進(jìn)程接收用戶輸入的交互型命令、解釋和執(zhí)行命令。用戶輸入退出命令則結(jié)束本次上機(jī)過程。處理器調(diào)度算法主要內(nèi)容一、低級調(diào)度的主要功能二、調(diào)度機(jī)制的邏輯功能模塊三、低級調(diào)度的基本類型四、作業(yè)調(diào)度和低級調(diào)度算法一、低級調(diào)度的主要功能處理器調(diào)度算法的功能處理器調(diào)度算法是對一批進(jìn)程或者線程確定處理器分配順序的方法，即在眾多進(jìn)程或者線程中，當(dāng)前選擇哪個(gè)進(jìn)程或者線程運(yùn)行。處理器調(diào)度算法作業(yè)調(diào)度算法中級調(diào)度算法低級調(diào)度算法處理器調(diào)度算法執(zhí)行的時(shí)機(jī)用戶進(jìn)程P1操作系統(tǒng)中斷處理程序用戶進(jìn)程P2指令流中斷進(jìn)程切換處理器調(diào)度算法分派實(shí)現(xiàn)處理器的分配和綁定工作，將處理器分配給被選中的進(jìn)程或線程，處理進(jìn)程或線程上下文交換細(xì)節(jié)。1、調(diào)度調(diào)度實(shí)現(xiàn)進(jìn)程/線程選擇算法，選中者獲得處理器。2、分派二、調(diào)度機(jī)制的邏輯功能模塊從就緒隊(duì)列中選擇下個(gè)運(yùn)行的進(jìn)程/線程。1、隊(duì)列管理程序進(jìn)程/線程狀態(tài)變化時(shí)，將該進(jìn)程/線程從一個(gè)隊(duì)列中取出來，修改其PCB后加入另一個(gè)隊(duì)列。2、上下文切換程序負(fù)責(zé)進(jìn)程/線程上下文切換。3、任務(wù)選擇程序（調(diào)度程序）三、低級調(diào)度的基本類型1、剝奪方式剝奪原則：高優(yōu)先級剝奪原則和時(shí)間片剝奪原則剝奪調(diào)度是在進(jìn)程自身具備執(zhí)行條件的情況下，由于外部原因而失去處理器。三、低級調(diào)度的基本類型進(jìn)程或線程一旦獲得處理器開始執(zhí)行，該進(jìn)程或線程在運(yùn)行到結(jié)束或者阻塞或者出錯等不能繼續(xù)運(yùn)行下去的事件前，處理器將不會切換到另一個(gè)進(jìn)程或線程。但進(jìn)程仍然可以被中斷，只是中斷處理后不做進(jìn)程切換。2、非剝奪方式非剝奪調(diào)度是因進(jìn)程/線程自身原因無法執(zhí)行下去而不得不放棄處理器三、低級調(diào)度的基本類型1、低級調(diào)度中的剝奪調(diào)度或非剝奪調(diào)度方式針對的是各種資源。錯。低級調(diào)度針對的是處理器，不是其它資源。處理器可剝奪，也可不剝奪。無論處理器采用剝奪還是被剝奪調(diào)度方式，設(shè)備等資源的調(diào)度幾乎總是采用非剝奪調(diào)度方式。也即，設(shè)備調(diào)度不受處理器調(diào)度方式的影響。低級調(diào)度的幾種誤解三、低級調(diào)度的基本類型2、在非剝奪調(diào)度方式中，進(jìn)程一旦獲得處理器，將一直運(yùn)行到阻塞、結(jié)束或者出錯事件發(fā)生時(shí)。錯。進(jìn)程一旦獲得處理器，在運(yùn)行到阻塞、結(jié)束或者出錯事件發(fā)生前，仍可被中斷，但中斷處理后不做進(jìn)程切換。低級調(diào)度的幾種誤解剝奪調(diào)度方式非剝奪方式進(jìn)程/線程的處理器I/O設(shè)備等慢速資源適合適合剝奪和非剝奪調(diào)度各自適用的資源四、作業(yè)調(diào)度和低級調(diào)度算法先來先服務(wù)算法（FCFS）多級反饋隊(duì)列調(diào)度算法（反饋循環(huán)隊(duì)列或多隊(duì)列策略）最短作業(yè)優(yōu)先算法（SJF）最短剩余時(shí)間優(yōu)先算法（SRTF）優(yōu)先級調(diào)度算法輪轉(zhuǎn)調(diào)度算法響應(yīng)比最高者優(yōu)先算法（HRRF）實(shí)際采用理論研究作業(yè)調(diào)度和低級調(diào)度算法執(zhí)行的時(shí)機(jī)用戶進(jìn)程P1操作系統(tǒng)中斷處理程序用戶進(jìn)程P2指令流中斷進(jìn)程切換處理器調(diào)度算法先來先服務(wù)優(yōu)先級輪轉(zhuǎn)最短作業(yè)最短剩余時(shí)間響應(yīng)比最高者多級反饋隊(duì)列有3個(gè)作業(yè)P1、P2、P3分別在時(shí)刻0、1、2先后到達(dá)多道程序系統(tǒng)，各作業(yè)處理流程如下。1、先來先服務(wù)算法（FCFS）按照作業(yè)進(jìn)入系統(tǒng)的先后次序挑選作業(yè)，按照進(jìn)程/線程請求資源的順序?yàn)槠浞峙滟Y源。FCFS算法舉例P1：I1（10ms），I2（10ms），C（5ms）；P2：I2（10ms），C（20ms）；P3：I2（10ms），C（5ms）；其中I1（10ms）、I2（10ms）分別表示在輸入設(shè)備I1、I2上執(zhí)行操作10ms，C（5ms）表示在處理器上執(zhí)行5ms。設(shè)備及CPU均按請求順序分配。每個(gè)作業(yè)的內(nèi)部處理流程以順序方式使用各個(gè)資源。采用先來先服務(wù)算法調(diào)度3個(gè)作業(yè)，計(jì)算各作業(yè)的周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。解：3個(gè)作業(yè)的調(diào)度時(shí)序及每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間如圖所示。有3個(gè)作業(yè)P1、P2、P3分別在時(shí)刻0、1、2先后到達(dá)多道程序系統(tǒng)，各作業(yè)處理流程如下。P1：C（5ms），I1（5ms），I2（10ms），C（12ms）；P2：C（8ms），I2（12ms）；P3：C（5ms），I2（8ms），C（10ms）；2、最短作業(yè)優(yōu)先算法（SJF）SJF算法舉例最短作業(yè)優(yōu)先算法選取估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行其中I1（5ms）、I2（5ms）分別表示在輸入設(shè)備I1、I2上執(zhí)行操作5ms，C（5ms）表示在處理器上執(zhí)行5ms。每個(gè)作業(yè)的內(nèi)部處理流程以順序方式使用各個(gè)資源。采用最短作業(yè)優(yōu)先算法分配處理器，采用FCFS算法分配設(shè)備。如果作業(yè)同時(shí)請求設(shè)備，則采用最短作業(yè)優(yōu)先算法分配設(shè)備。計(jì)算各作業(yè)的周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。解：3個(gè)作業(yè)的調(diào)度時(shí)序及每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間如圖所示。有3個(gè)作業(yè)P1、P2、P3分別在時(shí)刻0、3、6先后到達(dá)多道程序系統(tǒng)，各作業(yè)處理流程如下。3、最短剩余時(shí)間優(yōu)先算法（SRTF）最短剩余時(shí)間優(yōu)先算法是剝奪式的最短時(shí)間優(yōu)先調(diào)度算法。如果新作業(yè)需要的CPU時(shí)間比當(dāng)前正在執(zhí)行的作業(yè)剩余所需CPU時(shí)間短，新作業(yè)將搶占當(dāng)前作業(yè)的處理器。SRTF算法舉例P1：C（11ms），I1（6ms），C（3ms）；P2：C（7ms），I2（5ms）；P3：C（3ms），I2（8ms），C（10ms）；其中I1（6ms）、I2（3ms）分別表示在輸入設(shè)備I1、I2上執(zhí)行操作6ms、3ms，C（8ms）表示在處理器上執(zhí)行8ms。每個(gè)作業(yè)的內(nèi)部處理流程以順序方式使用各個(gè)資源。采用最短剩余時(shí)間優(yōu)先算法調(diào)度3個(gè)作業(yè)，計(jì)算各作業(yè)的周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。解：3個(gè)作業(yè)的調(diào)度時(shí)序及每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間如圖所示。有3個(gè)作業(yè)P1、P2、P3分別在時(shí)刻0、1、2先后到達(dá)多道程序系統(tǒng)，各作業(yè)處理流程如下。4、響應(yīng)比最高者優(yōu)先算法（HRRF）響應(yīng)比

＝

作業(yè)的響應(yīng)時(shí)間/作業(yè)處理時(shí)間

＝1+已等待時(shí)間/作業(yè)處理時(shí)間HRRF算法舉例響應(yīng)比最高者優(yōu)先算法選擇等待時(shí)間和需要CPU時(shí)間都較短的作業(yè)優(yōu)先調(diào)度，非剝奪調(diào)度作業(yè)處理時(shí)間由用戶給出，是一個(gè)常量P1：C（11ms），I（15ms），C（12ms）；P2：C（4ms），I（4ms），C（3ms）；P3：C（3ms），I（8ms），C（3ms）；其中I（15ms）表示在輸入設(shè)備I上執(zhí)行操作15ms，C（11ms）表示在處理器上執(zhí)行11ms。每個(gè)作業(yè)的內(nèi)部處理流程以順序方式使用各個(gè)資源。采用響應(yīng)比最高者優(yōu)先算法調(diào)度作業(yè)、分配資源，計(jì)算各作業(yè)的周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。解：在時(shí)刻11，P1第1階段的CPU時(shí)間11ms用完，P2等候第1階段CPU時(shí)間4ms的響應(yīng)比=1+(11–1)

4=3.5。P3等候第1階段CPU時(shí)間3ms的響應(yīng)比=1+(11–2)

3=4。P3響應(yīng)比大于P2響應(yīng)比，因此，在時(shí)刻11，P3開始在CPU上運(yùn)行。在時(shí)刻14，P3用完CPU，P2開始在CPU上運(yùn)行。如圖2-24所示，在時(shí)刻26，P1在設(shè)備I上的運(yùn)行結(jié)束，P2等候設(shè)備I的響應(yīng)比=1+(26–18)

4=3。P3等候設(shè)備I的響應(yīng)比=1+(26–14)

8=2.5。P2響應(yīng)比大于P3響應(yīng)比，因此，在時(shí)刻26，P2開始在設(shè)備I上運(yùn)行。在時(shí)刻30，P2用完設(shè)備I，P3開始在設(shè)備I上運(yùn)行。如圖2-25所示，在時(shí)刻38，P1第2階段的CPU時(shí)間12ms用完，P2等候第2階段CPU時(shí)間3ms的響應(yīng)比=1+(38–30)

3=3.66。P3等候第2階段CPU時(shí)間3ms的響應(yīng)比=1+0

3=1。P2響應(yīng)比大于P3響應(yīng)比，因此，在時(shí)刻38，P2開始在CPU上運(yùn)行。在時(shí)刻41，P2用完CPU，P3開始在CPU上運(yùn)行。在時(shí)刻44，三個(gè)作業(yè)全部運(yùn)行完畢，完整的調(diào)度時(shí)序圖如圖所示。優(yōu)先級調(diào)度算法根據(jù)確定的優(yōu)先級選取進(jìn)程/線程，每次總是選擇就緒隊(duì)列中優(yōu)先級最高者運(yùn)行。5、優(yōu)先級調(diào)度算法由系統(tǒng)綜合考慮有關(guān)因素來確定用戶進(jìn)程/線程的優(yōu)先級，稱為內(nèi)部指定法。用戶進(jìn)程/線程優(yōu)先級的規(guī)定者有兩種：（1）用戶用戶自己提出優(yōu)先級，稱為外部指定法。優(yōu)先級越高，費(fèi)用越高。（2）系統(tǒng)①正在運(yùn)行的進(jìn)程/線程隨著占有CPU時(shí)間的增加優(yōu)先級逐漸降低；②就緒隊(duì)列中等待CPU的進(jìn)程/線程隨著等待時(shí)間增加優(yōu)先級逐漸提高。根據(jù)優(yōu)先級是否隨時(shí)間而變，進(jìn)程/線程優(yōu)先級的確定有靜態(tài)和動態(tài)兩種方式。（1）靜態(tài)優(yōu)先級在進(jìn)程/線程創(chuàng)建時(shí)確定，此后不再改變。（2）動態(tài)優(yōu)先級隨時(shí)間而變，基本原則是：調(diào)度程序每次把CPU分配給就緒隊(duì)列首進(jìn)程/線程使用一個(gè)時(shí)間間隔（稱為時(shí)間片），就緒隊(duì)列中的每個(gè)進(jìn)程/線程輪流運(yùn)行一個(gè)時(shí)間片。6、輪轉(zhuǎn)調(diào)度算法（1）算法思想實(shí)現(xiàn)輪轉(zhuǎn)調(diào)度要使用一個(gè)間隔時(shí)鐘。當(dāng)一個(gè)進(jìn)程開始運(yùn)行時(shí)，將時(shí)間片的值置入間隔時(shí)鐘內(nèi)，當(dāng)發(fā)生間隔時(shí)鐘中斷時(shí)，中斷處理程序就通知處理器調(diào)度程序切換處理器。（2）實(shí)現(xiàn)原理最常用的輪轉(zhuǎn)法是等時(shí)間片輪轉(zhuǎn)法，每個(gè)進(jìn)程輪流運(yùn)行相同時(shí)間片。改進(jìn)的輪轉(zhuǎn)法對于不同的進(jìn)程分配不同的時(shí)間片，時(shí)間片的長短可以動態(tài)修改。（3）常用輪轉(zhuǎn)法時(shí)間片大小的確定要從進(jìn)程個(gè)數(shù)、切換開銷、系統(tǒng)效率和響應(yīng)時(shí)間等方面考慮。（4）時(shí)間片的選取建立兩個(gè)或多個(gè)就緒進(jìn)程隊(duì)列，每個(gè)隊(duì)列賦予不同優(yōu)先級，較高優(yōu)先級隊(duì)列一般分配給較短的時(shí)間片。開始工作時(shí)，新就緒進(jìn)程首先進(jìn)入高優(yōu)先級隊(duì)列等候調(diào)度，若能在該級隊(duì)列的一個(gè)時(shí)間片內(nèi)執(zhí)行完成，則進(jìn)程撤離系統(tǒng)，否則進(jìn)入低一級隊(duì)列等候調(diào)度。隊(duì)列級別越低，時(shí)間片越長，低優(yōu)先級隊(duì)列中的進(jìn)程獲得調(diào)度時(shí)運(yùn)行的時(shí)間就會長一些。7、多級反饋隊(duì)列調(diào)度算法（反饋循環(huán)隊(duì)列或多隊(duì)列策略）處理器調(diào)度每次先從高優(yōu)先級就緒隊(duì)列中選取可占有處理器的進(jìn)程，只有在選不到時(shí)，才從較低優(yōu)先級就緒隊(duì)列中選取進(jìn)程。同一隊(duì)列中的進(jìn)程按先來先服務(wù)原則排隊(duì)。7、多級反饋隊(duì)列調(diào)度算法（反饋循環(huán)隊(duì)列或多隊(duì)列策略）三級反饋隊(duì)列調(diào)度模型高優(yōu)先級就緒隊(duì)列（時(shí)間片20ms）新到進(jìn)程次優(yōu)先級就緒隊(duì)列（時(shí)間片40ms）第3優(yōu)先級就緒隊(duì)列（時(shí)間片100ms）P6P5P4P3P2P1完成完成完成未完成未完成未完成謝謝！并發(fā)進(jìn)程主要內(nèi)容一、程序執(zhí)行的順序性二、程序執(zhí)行的并發(fā)性三、與時(shí)間有關(guān)的錯誤四、進(jìn)程的交互：協(xié)作和競爭一、程序執(zhí)行的順序性程序執(zhí)行的順序性（1）程序內(nèi)部的順序性（2）程序外部的順序性程序內(nèi)部的順序性是指一個(gè)可獨(dú)立調(diào)度的任務(wù)（進(jìn)程或線程）內(nèi)部的語句、指令或模塊按照程序設(shè)計(jì)時(shí)規(guī)定的順序執(zhí)行，不因中斷、進(jìn)程切換以及進(jìn)程調(diào)度的順序而改變。（1）程序內(nèi)部的順序性語句1語句2語句n…進(jìn)程程序外部的順序性是指多個(gè)相關(guān)任務(wù)（進(jìn)程或線程）按照事先確定的順序逐個(gè)執(zhí)行，完成一個(gè)作業(yè)級的任務(wù)。（2）程序外部的順序性進(jìn)程1進(jìn)程2進(jìn)程n…一組順序進(jìn)程二、程序執(zhí)行的并發(fā)性進(jìn)程的并發(fā)性是指一組進(jìn)程的執(zhí)行在時(shí)間上是重疊的，即一個(gè)進(jìn)程執(zhí)行的第一條指令是在另一個(gè)進(jìn)程執(zhí)行的最后一條指令完成之前開始的。1、進(jìn)程的并發(fā)性含義進(jìn)程的并發(fā)性程序內(nèi)部的并發(fā)性程序外部的并發(fā)性并發(fā)多線程并發(fā)多進(jìn)程并發(fā)多線程語句a1語句a2語句an…語句a3語句b1語句b2語句bm…語句b3線程1線程2語句a1語句a2語句an…語句a3語句b1語句b2語句bm…語句b3進(jìn)程1進(jìn)程2并發(fā)多進(jìn)程2、并發(fā)程序設(shè)計(jì)并發(fā)多線程程序設(shè)計(jì)并發(fā)多進(jìn)程程序設(shè)計(jì)（由程序員）把一個(gè)程序編制為若干個(gè)可同時(shí)執(zhí)行的程序模塊的程序設(shè)計(jì)方法稱為并發(fā)程序設(shè)計(jì)。如果并發(fā)執(zhí)行模塊都屬于一個(gè)進(jìn)程，在進(jìn)程內(nèi)部執(zhí)行，則稱為并發(fā)多線程程序設(shè)計(jì)；若并發(fā)執(zhí)行模塊屬于不同進(jìn)程，則稱為并發(fā)多進(jìn)程程序設(shè)計(jì)。并發(fā)程序設(shè)計(jì)的好處能夠同時(shí)啟動多臺設(shè)備操作，充分利用處理器與外圍設(shè)備、外圍設(shè)備與外圍設(shè)備之間的并行工作能力，減少設(shè)備間的等待，提高資源利用率和計(jì)算機(jī)的工作效率而順序程序設(shè)計(jì)則順序操作設(shè)備，設(shè)備利用率較低while(K<Count){receive(PC);output(data[K++])}順序程序while(I<Count){input(data[I++]);send(PC)}while(J<Count){receive(PI);process(data[J++]);send(PO)}順序程序向并發(fā)程序的改造實(shí)例輸入程序PIP1=while(I<Count){input(data[I]);process(data[I]);output(data[I]);}計(jì)算程序PC輸出程序PO三個(gè)并發(fā)程序input(data[1])input(data[2]) process(data[1])input(data[3])process(data[2])output(data[1])input(data[4])process(data[3])output(data[2])input(data[5])process(data[4])output(data[3])process(data[5])output(data[4])output(data[5])三個(gè)程序的并發(fā)運(yùn)行輸入程序PI計(jì)算程序PC輸出程序PO3、并發(fā)進(jìn)程分類無關(guān)的并發(fā)進(jìn)程一組并發(fā)進(jìn)程分別在不同的變量集合上操作，一個(gè)進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無關(guān)，即一個(gè)并發(fā)進(jìn)程不會改變另一個(gè)并發(fā)進(jìn)程的變量值。協(xié)作的并發(fā)進(jìn)程一組并發(fā)進(jìn)程共享某些變量，一個(gè)進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程的執(zhí)行結(jié)果。無合作有合作設(shè)R(pi)={a1,a2,…an}是程序pi在執(zhí)行期間引用的變量集，W(pi)={b1,b2,…bm}是程序pi在執(zhí)行期間改變的變量集，若兩個(gè)程序p1、p2的引用變量集與改變變量集交集之和為空集，即R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}，則并發(fā)進(jìn)程的執(zhí)行與時(shí)間無關(guān)。Bernstein條件

并發(fā)進(jìn)程的執(zhí)行順序是否任意的判定方法S1：a=x+y;S2：b=z+1;S3：c=a

b;S4：w=c+1;語句執(zhí)行時(shí)序關(guān)系分析設(shè)一個(gè)程序PS有如下四條語句：S1S2Bernstein條件應(yīng)用實(shí)例順序程序的并行化改造方法S1：a=x+y;S2：b=z+1;前趨圖S1、S2訪問的變量無交集S1、S2為并行關(guān)系S1：a=x+y;S2：b=z+1;S3：c=a

b;S4：w=c+1;語句執(zhí)行時(shí)序關(guān)系分析S1S2S1：a=x+y;S3：c=a

b;前趨圖S1、S3對變量a一讀一寫，執(zhí)行順序不可顛倒S1、S3為順序關(guān)系S3S1：a=x+y;S2：b=z+1;S3：c=a

b;S4：w=c+1;語句執(zhí)行時(shí)序關(guān)系分析S1S2S2：b=z+1;S3：c=a

b;前趨圖S2、S3對變量b一讀一寫，執(zhí)行順序不可顛倒S2、S3為順序關(guān)系S3S1：a=x+y;S2：b=z+1;S3：c=a

b;S4：w=c+1;語句執(zhí)行時(shí)序關(guān)系分析S1S2S3：c=a

b;S4：w=c+1;前趨圖S3、S4對變量c一讀一寫，執(zhí)行順序不可顛倒S3、S4為順序關(guān)系S3S4S1;S2S3;S4;改造后的并行程序執(zhí)行時(shí)序三、與時(shí)間有關(guān)的錯誤1、結(jié)果不唯一對數(shù)據(jù)重疊修改導(dǎo)致修改信息丟失，結(jié)果不唯一。例如，多人搶購到一張車票，一票售給多人。當(dāng)合作進(jìn)程之間等待、喚醒之類的同步信號發(fā)送次序顛倒時(shí)，等待進(jìn)程因錯過了喚醒信號而永遠(yuǎn)等待。2、永遠(yuǎn)等待例如，歸還資源的進(jìn)程喚醒尚未等待資源的進(jìn)程，喚醒信號丟失。四、進(jìn)程的交互：協(xié)作和競爭并發(fā)進(jìn)程之間的競爭關(guān)系是由于并發(fā)進(jìn)程共用一套計(jì)算機(jī)系統(tǒng)資源引起的，一個(gè)進(jìn)程的執(zhí)行可能影響與其競爭資源的其它進(jìn)程。1、并發(fā)進(jìn)程之間的競爭關(guān)系資源競爭產(chǎn)生兩個(gè)問題死鎖問題饑餓問題進(jìn)程直接或間接互相等待對方的資源一些進(jìn)程總是優(yōu)先于另一些進(jìn)程FCFS資源分配策略解決進(jìn)程競爭關(guān)系（間接制約關(guān)系）的手段臨界區(qū)管理可以解決進(jìn)程互斥問題。進(jìn)程互斥進(jìn)程互斥是指若干進(jìn)程要使用同一共享資源時(shí)，任何時(shí)刻最多允許一個(gè)進(jìn)程使用，其他要使用該資源的進(jìn)程必須等待，直到占有資源的進(jìn)程釋放該資源。解決概念管理工具2、并發(fā)進(jìn)程之間的協(xié)作關(guān)系某些并發(fā)進(jìn)程為完成同一任務(wù)而共享某些數(shù)據(jù)，形成協(xié)作關(guān)系協(xié)作進(jìn)程之間需要同步，即一個(gè)進(jìn)程在接收到伙伴進(jìn)程發(fā)來的信號之前需要等待協(xié)作產(chǎn)生原因協(xié)作方法進(jìn)程間協(xié)作關(guān)系（直接制約關(guān)系）的手段進(jìn)程同步進(jìn)程同步是指協(xié)作進(jìn)程之間通過收發(fā)信號協(xié)調(diào)彼此活動的行為，一個(gè)進(jìn)程的執(zhí)行依賴于協(xié)作進(jìn)程的消息或信號，收到協(xié)作進(jìn)程的消息或信號之前等待，收到后才被喚醒。解決概念謝謝！臨界區(qū)管理主要內(nèi)容一、臨界區(qū)調(diào)度原則二、實(shí)現(xiàn)臨界區(qū)管理的硬件設(shè)施一、臨界區(qū)調(diào)度原則并發(fā)進(jìn)程中與共享變量有關(guān)的程序段叫做臨界區(qū)，共享變量代表的資源叫做臨界資源。1、臨界區(qū)與臨界資源例如，車票銷售進(jìn)程中代表剩余可售票數(shù)的變量即為臨界資源；讀寫該變量的程序段即為臨界區(qū)。并發(fā)進(jìn)程中訪問共享變量部分的程序段必須順序執(zhí)行，才能保證數(shù)據(jù)一致性。（1）一旦臨界區(qū)空閑，應(yīng)該允許進(jìn)程進(jìn)入。（2）一次至多允許一個(gè)（或不超過規(guī)定數(shù)目的）進(jìn)程進(jìn)入臨界區(qū)內(nèi)執(zhí)行。（3）如果位于臨界區(qū)的進(jìn)程數(shù)已達(dá)最大限定值，則其他試圖進(jìn)入的進(jìn)程應(yīng)等待。（4）進(jìn)入臨界區(qū)內(nèi)的進(jìn)程應(yīng)在有限時(shí)間內(nèi)退出，以便使等待進(jìn)程中的一個(gè)進(jìn)入。2、臨界區(qū)的調(diào)度原則二、實(shí)現(xiàn)臨界區(qū)管理的硬件設(shè)施進(jìn)程在進(jìn)入臨界區(qū)之前先關(guān)中斷，退出臨界區(qū)時(shí)開中斷。在關(guān)中斷期間，進(jìn)度調(diào)度程序失去中斷激活的機(jī)會，不會切換進(jìn)程，保證了臨界區(qū)的互斥執(zhí)行。1、關(guān)中斷（1）關(guān)中斷時(shí)間過長會影響系統(tǒng)效率，限制處理器交叉執(zhí)行程序的能力；（2）關(guān)中斷方法不適用于多CPU系統(tǒng)，因?yàn)?，在一個(gè)處理器上關(guān)中斷，并不能防止進(jìn)程在其他處理器上執(zhí)行相同的臨界區(qū)代碼；（3）關(guān)中斷權(quán)利賦予用戶很危險(xiǎn)，如果用戶未開中斷，系統(tǒng)可能因此終止。關(guān)中斷方法的缺點(diǎn)TS(x){

若x=true，則{x=false；returntrue；}

否則returnfalse；}2、測試并建立指令硬件提供的測試并建立指令的過程如下：bools=true;cobeginprocessPi(){//i=1,2,...,n while(!TS(s));//上鎖 {臨界區(qū)}; s=true;//開鎖}coend利用TS指令實(shí)現(xiàn)進(jìn)程互斥的算法如下：s=T,F,T,F,TP1P2變量值while(!TS(s));s=F臨界區(qū)while(!TS(s));//等待s=true;s=Twhile(!TS(s));s=F臨界區(qū)s=true;s=T對換（Swap）指令的功能是交換兩個(gè)字的內(nèi)容在Intel80x86中，對換指令為XCHG指令。3、對換指令boollock=false;cobeginProcessPi(){//i=1,2,...,n boolkeyi=true; do { SWAP(keyi,lock); }while(keyi);//上鎖 {臨界區(qū)}; SWAP(keyi,lock);//開鎖}coend用對換指令實(shí)現(xiàn)進(jìn)程互斥的程序如下：lock=F,T,T,Fkeyi=T,F,T,Fkeyi=TP1P2變量值do{SWAP(keyi,lock);}while(keyi);lock=TP1.keyi=F臨界區(qū)do{SWAP(keyi,lock);}while(keyi);//等待lock=TP2.keyi=TSWAP(keyi,lock);lock=FP1.keyi=Tdo{SWAP(keyi,lock);}while(keyi);lock=TP2.keyi=F臨界區(qū)SWAP(keyi,lock);lock=FP2.keyi=T謝謝！信號量與PV操作的概念主要內(nèi)容一、同步與同步機(jī)制二、信號量與PV操作一、同步與同步機(jī)制典型的進(jìn)程同步問題：生產(chǎn)者-消費(fèi)者問題生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程向其它進(jìn)程輸出或者發(fā)送數(shù)據(jù)的進(jìn)程從其它進(jìn)程接收數(shù)據(jù)的進(jìn)程生產(chǎn)者-消費(fèi)者問題描述數(shù)據(jù)結(jié)構(gòu)操作有一環(huán)形緩沖池，包含n個(gè)緩沖區(qū)（0~n-1）。有兩類進(jìn)程：m個(gè)生產(chǎn)者進(jìn)程和n個(gè)消費(fèi)者進(jìn)程，生產(chǎn)者進(jìn)程按照編號順序向空的緩沖區(qū)中投放產(chǎn)品，消費(fèi)者進(jìn)程按照投放順序從滿的緩沖區(qū)中取走產(chǎn)品。要求采用算法描述生產(chǎn)者進(jìn)程、消費(fèi)者進(jìn)程通過緩沖池交互的行為。生產(chǎn)者1消費(fèi)者1生產(chǎn)者2消費(fèi)者2生產(chǎn)者3消費(fèi)者3產(chǎn)品1產(chǎn)品1產(chǎn)品2產(chǎn)品2intk; //緩沖池中緩沖區(qū)個(gè)數(shù)typedefanyitemitem; //產(chǎn)品類型itembuffer[k]; //緩沖池intin=0,out=0,counter=0; //讀寫指針和滿緩沖區(qū)個(gè)數(shù)processproducer(void)

//生產(chǎn)者進(jìn)程{

while(true)

{

//無限循環(huán)

{produceaniteminnextp}; //生產(chǎn)一個(gè)產(chǎn)品

if(counter==k)sleep(producer); //緩沖滿時(shí)，生產(chǎn)者睡眠

buffer[in]=nextp; //將一個(gè)產(chǎn)品放入緩沖區(qū)

in=(in+1)%k; //指針推進(jìn)

counter++; //緩沖內(nèi)產(chǎn)品數(shù)加1

if(counter==1)wakeup(consumer); //緩沖池非空后喚醒消費(fèi)者

}}未考慮進(jìn)程互斥的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程交互算法processconsumer(void) //消費(fèi)者進(jìn)程{while(true){//無限循環(huán)

if(counter==0)sleep(consumer);//緩沖區(qū)空，消費(fèi)者睡眠

nextc=buffer[out]; //取一個(gè)產(chǎn)品到nextc

out=(out+1)%k; //指針推進(jìn)

counter--; //取走一個(gè)產(chǎn)品，計(jì)數(shù)減1

if(counter==k-1)wakeup(producer);//緩沖不滿，喚醒生產(chǎn)者

{consumetheiteminnextc}; //消耗產(chǎn)品

}}進(jìn)程對緩沖池的競爭關(guān)系生產(chǎn)者與生產(chǎn)者生產(chǎn)者與消費(fèi)者消費(fèi)者與消費(fèi)者進(jìn)程并發(fā)執(zhí)行時(shí)可能出現(xiàn)的錯誤多個(gè)生產(chǎn)者將多個(gè)產(chǎn)品放入同一個(gè)緩沖區(qū)中生產(chǎn)者無法正常喚醒消費(fèi)者，導(dǎo)致緩沖區(qū)滿，所有進(jìn)程睡眠多個(gè)消費(fèi)者從同一個(gè)滿緩沖區(qū)中取產(chǎn)品結(jié)果不唯一永遠(yuǎn)等待同步機(jī)制信號量與PV操作消息傳遞管程進(jìn)程并發(fā)錯誤的解決方法利用進(jìn)程同步機(jī)制控制進(jìn)程的相對速率二、信號量與PV操作（1）對不能進(jìn)入臨界區(qū)的進(jìn)程，采用忙式等待測試法，浪費(fèi)CPU時(shí)間。（2）將測試能否進(jìn)入臨界區(qū)的責(zé)任推給各個(gè)競爭的進(jìn)程會削弱系統(tǒng)的可靠性，加重用戶編程負(fù)擔(dān)。1、臨界區(qū)調(diào)度嘗試算法中存在的問題1965年荷蘭計(jì)算機(jī)科學(xué)家E.W.Dijkstra提出新的同步工具

信號量和P、V操作。他將交通管制中使用多種顏色信號燈管理交通的方法引入操作系統(tǒng)2、信號量同步機(jī)制的提出操作系統(tǒng)中信號量的物理意義在操作系統(tǒng)中，信號量是表示共享資源的數(shù)據(jù)結(jié)構(gòu)，記錄可用共享資源的數(shù)量，維護(hù)等待使用共享資源的阻塞進(jìn)程隊(duì)列。信號量實(shí)現(xiàn)為記錄型數(shù)據(jù)結(jié)構(gòu)，包含兩個(gè)分量：一個(gè)是信號量的值，另一個(gè)是信號量隊(duì)列的隊(duì)列指針信號量的實(shí)現(xiàn)結(jié)構(gòu)信號量的值(-3)信號量隊(duì)列指針等待進(jìn)程1等待進(jìn)程2等待進(jìn)程3Dijkstra發(fā)明了兩個(gè)信號量操作原語P操作原語V操作原語waitsignalupdownsleepwakeup其他符號其他符號信號量和P、V操作的功能解決并發(fā)進(jìn)程的競爭互斥問題解決并發(fā)進(jìn)程的協(xié)作同步問題3、信號量的分類按用途公用信號量私有信號量初值常常為1（或者允許的某個(gè)最大值），用來實(shí)現(xiàn)進(jìn)程間的互斥。同一進(jìn)程可對其執(zhí)行P、V操作。初值常常為可用資源數(shù)，多用來實(shí)現(xiàn)進(jìn)程同步。擁有該信號量的一類進(jìn)程可以對其執(zhí)行P操作，而另一類進(jìn)程可以對其執(zhí)行V操作。將信號量s加1，若結(jié)果不大于0，則釋放一個(gè)等待信號量s的進(jìn)程。4、一般信號量的結(jié)構(gòu)和操作描述P和V操作原語定義將信號量s減去1，若結(jié)果小于0，則調(diào)用P(s)的進(jìn)程被置成等待信號量s的狀態(tài)。設(shè)s為一個(gè)記錄型數(shù)據(jù)結(jié)構(gòu)一個(gè)分量為整型量value另一個(gè)為信號量隊(duì)列queueP(s)V(s)typedefstructsemaphore{intvalue; //信號量值

structpcb*list;//信號量隊(duì)列指針}semaphore;信號量和P、V操作描述信號量的數(shù)據(jù)結(jié)構(gòu)voidP(semaphore&s){

s.value--;

if(s.value<0)W(s.list);//將P操作調(diào)用者進(jìn)程置為阻塞狀態(tài)并移入s信號量隊(duì)列，轉(zhuǎn)進(jìn)程調(diào)度}P操作voidV(semaphore&s){

s.value++;

if(s.value<=0)R(s.list);//從信號量s隊(duì)列中釋放一個(gè)等待信號量s的進(jìn)程并轉(zhuǎn)換成就緒態(tài)，自己則繼續(xù)執(zhí)行}V操作變量說明P(s)和V(s)中的s為兩個(gè)過程的共享變量。s的初值根據(jù)其用途設(shè)置。P、V操作含義P操作意味著請求一個(gè)資源V操作意味著釋放一個(gè)資源W(s.list)和R(s.list)是操作系統(tǒng)的基本系統(tǒng)調(diào)用。推論1：若s>0，則s值代表可用物理資源數(shù)2：若s<0，則|s|代表等待s資源的進(jìn)程數(shù)3：P操作意味著請求一個(gè)資源，V操作意味著釋放一個(gè)資源。在一定條件下，P操作代表掛起進(jìn)程操作，而V操作代表喚醒被掛起進(jìn)程的操作謝謝！利用信號量實(shí)現(xiàn)互斥主要內(nèi)容一、方法二、應(yīng)用模式三、互斥細(xì)節(jié)分析一、方法為臨界資源設(shè)一互斥信號量mutex，初值為1；將臨界區(qū)置于P(mutex)和V(mutex)之間；P(mutex)和V(mutex)一定成對出現(xiàn)在同一個(gè)進(jìn)程中。二、應(yīng)用模式semaphoremutex;mutex=1;cobeginprocessPi(){//i=1,…,n P(mutex); {臨界區(qū)}; V(mutex);}coend三、互斥細(xì)節(jié)分析并發(fā)進(jìn)程變量P1P2P(mutex);臨界區(qū);//切換P(mutex);//阻塞，切換V(mutex);//喚醒P2臨界區(qū);V(mutex);mutex.value=1mutex.list=空mutex.value=0mutex.list=空mutex.value=-1mutex.list=P2mutex.value=0mutex.list=空mutex.value=1mutex.list=空謝謝！哲學(xué)家進(jìn)餐問題經(jīng)典進(jìn)程同步問題（1）哲學(xué)家進(jìn)餐問題（2）生產(chǎn)者-消費(fèi)者問題（3）讀者-寫者問題（4）睡眠理發(fā)師問題哲學(xué)家進(jìn)餐問題主要內(nèi)容一、問題描述二、算法描述三、死鎖問題解決一、問題描述為了吃面，每個(gè)哲學(xué)家必須獲得兩把叉子，且每人只能從自己左邊或右邊去取叉子。通心面叉子哲學(xué)家二、算法描述semaphorefork[5];for(inti=0;i<5;i++)fork[i]=1;cobeginprocessphilosopher_i(){//i=0,1,2,3,4 while(true) { think(); P(fork[i]); P(fork[(i+1)%5]); eat(); V(fork[i]); V(fork[(i+1)%5]); }}coend三、死鎖問題解決哲學(xué)家進(jìn)餐死鎖現(xiàn)象通心面餐盤叉子哲學(xué)家哲學(xué)家進(jìn)餐死鎖問題解決方案（1）至多允許四位哲學(xué)家同時(shí)去拿左邊的叉子通心面叉子哲學(xué)家請自行實(shí)現(xiàn)該方案（2）規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的叉子，然后再去拿右邊的叉子；偶數(shù)號哲學(xué)家先拿他右邊的叉子，然后再去拿左邊的叉子；通心面叉子哲學(xué)家01234請自行實(shí)現(xiàn)該方案01234（3）僅當(dāng)哲學(xué)家的左右兩把叉子均可用時(shí)，才允許他拿起叉子進(jìn)餐，否則一把叉子也不取。通心面叉子哲學(xué)家40123請自行實(shí)現(xiàn)該方案謝謝！生產(chǎn)者-消費(fèi)者問題主要內(nèi)容一、問題描述二、算法描述三、算法運(yùn)行場景分析四、同步與互斥關(guān)系分析一、問題描述指存在數(shù)據(jù)供給與需求關(guān)系的兩類進(jìn)程。生產(chǎn)者-消費(fèi)者實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者問題的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：含有n個(gè)緩沖區(qū)的公用緩沖池(1)臨界資源實(shí)現(xiàn)諸進(jìn)程對緩沖池的互斥訪問，一次僅允許一個(gè)進(jìn)程讀或?qū)懝镁彌_池，初值為1。(2)互斥信號量mutex記錄空緩沖區(qū)個(gè)數(shù)，初值為n(3)資源信號量empty記錄滿緩沖區(qū)個(gè)數(shù)，初值為0(4)資源信號量full二、算法描述itemB[k];semaphoreempty;empty=k; //可以使用的空緩沖區(qū)數(shù)semaphorefull;full=0;//緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)semaphoremutex;mutex=1; //互斥信號量intin=0; //寫緩沖區(qū)指針intout=0;//讀緩沖區(qū)指針cobeginprocessproducer_i(){//生產(chǎn)者進(jìn)程while(true){

produce();

P(empty);

P(mutex);

appendtoB[in];

in=(in+1)%k;

V(mutex);

V(full);

}}processconsumer_j(){//消費(fèi)者進(jìn)程

while(true)

{ P(full); P(mutex); take()fromB[out]; out=(out+1)%k; V(mutex); V(empty); consume();

}}coend三、算法運(yùn)行場景分析假定有1個(gè)生產(chǎn)者進(jìn)程P1和1個(gè)消費(fèi)者進(jìn)程C1，2個(gè)緩沖區(qū)，這樣n=2，empty初值為2。生產(chǎn)者P1消費(fèi)者C1緩沖區(qū)并發(fā)進(jìn)程共享變量P1C10110in=mutex.value=0out=B(0)=B(1)=mutex.list=0-1full.value=C1full.list=21empty.value=empty.list=produce();//產(chǎn)生’A’P(full);//阻塞P(empty);P(mutex);B(0)=‘A’;in=1;V(mutex);V(full);//喚醒C110A并發(fā)進(jìn)程共享變量P1C10110in=mutex.value=0out=AB(0)=B(1)=mutex.list=0-1full.value=full.list=21empty.value=empty.list=從B(0)取出’A’P(mutex);out=1;V(mutex);V(empty);consume();100112cobeginprocessproducer_i(){//生產(chǎn)者進(jìn)程while(true){

produce();

P(empty);

P(mutex);

appendtoB[in];

in=(in+1)%k;

V(mutex);

V(full);

}}processconsumer_j(){//消費(fèi)者進(jìn)程

while(true)

{ P(full); P(mutex); take()fromB[out]; out=(out+1)%k; V(mutex); V(empty); consume();

}}coend同步互斥互斥同步與互斥P、V操作位置的不同四、同步與互斥關(guān)系分析存在同步關(guān)系的進(jìn)程生產(chǎn)者與消費(fèi)者存在互斥關(guān)系的進(jìn)程生產(chǎn)者與生產(chǎn)者生產(chǎn)者與消費(fèi)者消費(fèi)者與消費(fèi)者同時(shí)存在同步與互斥關(guān)系的進(jìn)程生產(chǎn)者與消費(fèi)者同步操作的特征：喚醒異類，而不是同類消費(fèi)者進(jìn)程中的V(empty)只能喚醒生產(chǎn)者，不會喚醒消費(fèi)者生產(chǎn)者進(jìn)程中的V(full)只能喚醒消費(fèi)者，不會喚醒生產(chǎn)者互斥操作的特征：喚醒同類，也喚醒異類消費(fèi)者進(jìn)程中的V(mutex)既會喚醒消費(fèi)者，也會喚醒生產(chǎn)者生產(chǎn)者進(jìn)程中的V(mutex)既會喚醒生產(chǎn)者，也會喚醒消費(fèi)者謝謝！讀者-寫者問題主要內(nèi)容一、問題描述二、算法描述三、算法運(yùn)行場景分析四、同步與互斥關(guān)系分析一、問題描述若干讀者（Reader）進(jìn)程和寫者（Writer）進(jìn)程共享一個(gè)數(shù)據(jù)文件，允許多個(gè)Reader進(jìn)程同時(shí)讀該共享文件，但不允許一個(gè)Writer進(jìn)程與其它Reader進(jìn)程或Writer進(jìn)程同時(shí)訪問該共享文件。讀者-寫者問題形象描述讀者讀者讀者讀者數(shù)據(jù)文件讀者讀者讀者數(shù)據(jù)文件寫者寫者寫者寫者寫者寫者寫者讀者在讀，寫者必須等待寫者在寫，讀者、其它欲寫者必須等待二、算法描述intreadcount=0;//讀進(jìn)程計(jì)數(shù)semaphorewriteblock,mutex;writeblock=1;mutex=1;cobeginprocessreader_i()//讀者進(jìn)程

{ P(mutex); readcount++; if(readcount==1)P(writeblock); V(mutex); {讀文件}; P(mutex); readcount--; if(readcount==0)V(writeblock); V(mutex);}互斥互斥processwriter_j()//寫者進(jìn)程{ P(writeblock); {寫文件}; V(writeblock);}coend三、算法運(yùn)行場景分析假設(shè)讀者r1、r2、寫者w1依次到來，r1、r2讀完退出共享數(shù)據(jù)文件后w1可以寫，寫完之前讀者r3、寫者w2先后到來。讀者-寫者問題運(yùn)行場景模擬入口出口r1r2w1r3w2r1、r2、w1依次到來，r1、r2讀完后w1寫，寫完之前r3、w2先后到來讀者-寫者問題運(yùn)行場景細(xì)節(jié)入口出口各主要變量初始值:0readcount=1writeblock.value=writeblock.list=入口出口r1各主要變量當(dāng)前值0readcount=1writeblock.value=writeblock.list=P(mutex);if(readcount==1)P(writeblock);V(mutex);{讀文件};10readcount++;入口出口r2各主要變量當(dāng)前值0readcount=1writeblock.value=writeblock.list=P(mutex);readcount++;if(readcount==1)P(writeblock);V(mutex);{讀文件};10r12不執(zhí)行P(writeblock)入口出口r2各主要變量當(dāng)前值0readcount=1writeblock.value=writeblock.list=P(writeblock);10r12w1-1w1w1等待入口出口r2各主要變量當(dāng)前值0readcount=1writeblock.value=writeblock.list=10r12w1-1W1P(mutex);readcount--;if(readcount==0)V(writeblock);V(mutex);不執(zhí)行V(writeblock)1入口出口r2各主要變量當(dāng)前值0readcount=1writeblock.value=writeblock.list=10r12w1-1w1P(mutex);readcount--;if(readcount==0)V(writeblock);V(mutex);100{寫文件};入口出口r2各主要變量當(dāng)前值0readcount=1writeblock.value=writeblock.list=10r12w1-1100r3P(mutex);if(readcount==1)P(writeblock);//r3阻塞readcount++;1-1r3r3等待入口出口r2各主要變量當(dāng)前值0readcount=1writeblock.value=writeblock.list=10r12w1-1100r31-1r3P(writeblock);w2等待w2r3等待-2w2入口出口r2各主要變量當(dāng)前值0readcount=1writeblock.value=writeblock.list=10r12w1-1100r31-1r3V(writeblock);w2等待w2r3等待-2w2-1V(mutex);{讀文件};入口出口r2各主要變量當(dāng)前值0readcount=1writeblock.value=writeblock.list=10r12w1-1100r31-1w2等待w2-2w2-1P(mutex);readcount--;if(readcount==0)V(writeblock);V(mutex);00{寫文件};入口出口r2各主要變量當(dāng)前值0readcount=1writeblock.value=writeblock.list=10r12w1-1100r31-1w2-2-1V(writeblock);001入口出口r2各主要變量最終值0readcount=1writeblock.value=writeblock.list=r1w1r3w2各主要變量初始值0readcount=1writeblock.value=writeblock.list=入口出口r1r2w1r3w2進(jìn)程運(yùn)行前各主要變量初始值0readcount=1writeblock.value=writeblock.list=四、同步與互斥關(guān)系分析cobeginprocessreader_i(){//讀者進(jìn)程P(mutex);readcount++; if(readcount==1)P(writeblock);V(mutex);{讀文件};P(mutex);readcount--;if(readcount==0)V(writeblock);V(mutex);}processwriter_j(){//寫者進(jìn)程P(writeblock);{寫文件};V(writeblock);}coend互斥互斥互斥互斥讀者-寫者問題互斥關(guān)系的特殊性由多個(gè)讀者構(gòu)成的讀者進(jìn)程集合與單一的某個(gè)寫者進(jìn)程之間存在互斥關(guān)系。讀者-寫者問題的互斥關(guān)系特殊性在于：即互斥關(guān)系不是一對一的，而是多對一的。讀者-寫者問題互斥關(guān)系的特殊性只有第1個(gè)讀者進(jìn)程會執(zhí)行P(writeblock)雖然讀者進(jìn)程算法描述中的P(writeblock)和V(writeblock)成對出現(xiàn)，但并非每個(gè)讀者進(jìn)程都執(zhí)行P(writeblock)或V(writeblock)只有最后1個(gè)讀者進(jìn)程會執(zhí)行V(writeblock)非第1也非最后1個(gè)讀者進(jìn)程對P(writeblock)和V(writeblock)都不會執(zhí)行當(dāng)?shù)?個(gè)讀者進(jìn)程也是最后1個(gè)離開的讀者進(jìn)程時(shí)，它會執(zhí)行P(writeblock)和V(writeblock)讀者-寫者問題互斥關(guān)系的特殊性因此，各個(gè)讀者進(jìn)程與寫者進(jìn)程的關(guān)系并不都是一樣的。有些讀者進(jìn)程與寫者進(jìn)程之間沒有直接的關(guān)系，它們之間沒有共享信號量，也沒有共享變量；有些讀者進(jìn)程與寫者進(jìn)程之間共享了信號量writeblock，但是其P、V操作沒有成對執(zhí)行；讀者-寫者問題互斥關(guān)系的特殊性事實(shí)上，某個(gè)讀者進(jìn)程執(zhí)行P(writeblock)或V(writeblock)的行為代表的是整個(gè)讀者進(jìn)程集合的行為，而不僅僅是執(zhí)行該操作的那個(gè)讀者進(jìn)程的個(gè)體行為。第1個(gè)讀者進(jìn)程和最后1個(gè)讀者進(jìn)程負(fù)責(zé)執(zhí)行所有讀者進(jìn)程與某個(gè)寫者進(jìn)程之間的互斥操作，建立它們與單個(gè)寫者進(jìn)程之間的互斥關(guān)系。讀者-寫者問題互斥關(guān)系的特殊性因此，在判定進(jìn)程之間的互斥關(guān)系時(shí)，要從靜態(tài)結(jié)構(gòu)即算法描述和動態(tài)行為即進(jìn)程執(zhí)行兩方面來考察。靜態(tài)方面看算法描述中同一信號量的P、V操作是否成對出現(xiàn)在同一個(gè)進(jìn)程中；動態(tài)方面看每個(gè)進(jìn)程執(zhí)行時(shí)是否成對執(zhí)行該進(jìn)程算法描述中同一信號量的P、V操作。所有讀者與單個(gè)寫者存在互斥關(guān)系的進(jìn)程單個(gè)讀者與單個(gè)讀者單個(gè)寫者與單個(gè)寫者讀者-寫者問題同步與互斥關(guān)系總結(jié)讀者-寫者問題同步與互斥關(guān)系總結(jié)1、讀者可以喚醒讀者嗎？請思考以下問題：2、讀者可以喚醒寫者嗎？3、寫者可以喚醒讀者嗎？4、寫者可以喚醒寫者嗎？每種喚醒屬于同步操作還是互斥操作？分別使用哪個(gè)信號量執(zhí)行喚醒動作？互斥1、讀者可以喚醒讀者2、讀者可以喚醒寫者3、寫者可以喚醒讀者4、寫者可以喚醒寫者mutex互斥writeblock互斥writeblock互斥writeblock讀者-寫者問題同步與互斥關(guān)系總結(jié)互斥信號量mutexWriteblock互斥信號量mutexwriteblock屬于互斥信號量屬于有請寫出寫者優(yōu)先的讀者-寫者算法謝謝！睡眠理發(fā)師問題主要內(nèi)容一、問題描述二、算法描述三、算法運(yùn)行場景分析四、同步與互斥關(guān)系分析五、Linux系統(tǒng)中的同步互斥功能六、Linux進(jìn)程同步與互斥實(shí)驗(yàn)：信號量解決生產(chǎn)者-消費(fèi)者問題一、問題描述理發(fā)店有一位理發(fā)師、一把理發(fā)椅和n把椅子供顧客等候理發(fā)休息。如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。一個(gè)顧客到來時(shí)，他必須叫醒理發(fā)師。如果理發(fā)師正在理發(fā)時(shí)又有顧客到來，則如果有空椅子可坐，顧客就坐下來等待，否則離開。理發(fā)師睡眠理發(fā)師問題同步互斥演示二、算法描述intwaiting=0;//等候理發(fā)的顧客數(shù)intCHAIRS=N;//供顧客坐的椅子總數(shù)semaphorecustomers,barbers,mutex;customers=0;barbers=0;mutex=1;cobeginprocessbarber() //理發(fā)師進(jìn)程{while(true){P(customers);//有顧客可供消費(fèi)嗎？若無顧客，理發(fā)師睡眠P(mutex);//若有顧客時(shí)，以顧客當(dāng)產(chǎn)品，取一個(gè)顧客消費(fèi)waiting--;//等候顧客數(shù)少一個(gè)V(barbers);//理發(fā)師喊一個(gè)顧客來準(zhǔn)備為他理發(fā)V(mutex);//退出臨界區(qū)cut_hair();//理發(fā)師正在理發(fā)（非臨界區(qū)）}}processcustomer_i() //顧客進(jìn)程{ P(mutex); //進(jìn)入臨界區(qū) if(waiting<CHAIRS) {//若有空椅子，則等候顧客數(shù)加1，否則顧客離開 waiting++; V(customers); //可用顧客數(shù)增1 V(mutex); //退出臨界區(qū) P(barbers);//理發(fā)師忙，顧客坐下等待 get_haircut(); //否則顧客坐下理發(fā) } else V(mutex); //人滿了，走吧！}coend三、算法運(yùn)行場景分析假設(shè)現(xiàn)有一個(gè)理發(fā)師（b）、一把理發(fā)椅、2個(gè)顧客凳子。尚未有顧客到來。理發(fā)椅理發(fā)師各變量初值0customers=0barbers=1mutex=b0waiting=2CHAIRS=顧客凳子假設(shè)理發(fā)師進(jìn)程首先調(diào)度運(yùn)行理發(fā)師各變量當(dāng)前值0customers=0barbers=1mutex=b0waiting=2CHAIRS=P(customers);-1(b)第1個(gè)顧客c1到來理發(fā)師各變量當(dāng)前值0custom