1、 順序處理模式順序處理模式 每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。 IiCiPi和S1S2S3 圖 2-2 前趨圖 阻塞阻塞（不能占用（不能占用CPU）就緒就緒（尚未占（尚未占用用CPU）運(yùn)行運(yùn)行（正在占（正在占用用CPU）資源不足或資源不足或等待某事件等待某事件發(fā)生發(fā)生得到資源得到資源或某事件或某事件發(fā)生發(fā)生時(shí)間片到時(shí)間片到調(diào)度選中進(jìn)入調(diào)度選中進(jìn)入進(jìn)進(jìn)入入完完成成執(zhí)行執(zhí)行掛起狀態(tài)掛起狀態(tài)引入掛起狀態(tài)的原因引入掛起狀態(tài)的原因 終端用戶的請(qǐng)求。 (2) 父進(jìn)程請(qǐng)求。 (3) 負(fù)荷調(diào)節(jié)的需要。 1) (4) 操作系統(tǒng)的需要。 具有掛起狀態(tài)的進(jìn)程狀態(tài)圖

2、 1. 進(jìn)程控制塊進(jìn)程控制塊的作用的作用 進(jìn)程控制塊的作用是使一個(gè)在多道程序環(huán)境進(jìn)程控制塊的作用是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序下不能獨(dú)立運(yùn)行的程序(含數(shù)據(jù)含數(shù)據(jù))，成為一個(gè)能獨(dú)，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f(shuō)，的進(jìn)程?；蛘哒f(shuō)，OS是根據(jù)是根據(jù)PCB來(lái)對(duì)并發(fā)執(zhí)行來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。的進(jìn)程進(jìn)行控制和管理的。2. 進(jìn)程控制塊中的信息進(jìn)程控制塊中的信息 1) 進(jìn)程標(biāo)識(shí)符進(jìn)程標(biāo)識(shí)符 進(jìn)程標(biāo)識(shí)符用于惟一地標(biāo)識(shí)一個(gè)進(jìn)程。一個(gè)進(jìn)程通常進(jìn)程標(biāo)識(shí)符用于惟一地標(biāo)識(shí)一個(gè)進(jìn)程。一個(gè)進(jìn)程通常有兩種標(biāo)識(shí)符：有兩種標(biāo)識(shí)

3、符： (1) 內(nèi)部標(biāo)識(shí)符。在所有的操作系統(tǒng)中，都為每一個(gè)進(jìn)內(nèi)部標(biāo)識(shí)符。在所有的操作系統(tǒng)中，都為每一個(gè)進(jìn) 程賦予一個(gè)惟一的數(shù)字標(biāo)識(shí)符，它通常是一個(gè)進(jìn)程的序號(hào)。程賦予一個(gè)惟一的數(shù)字標(biāo)識(shí)符，它通常是一個(gè)進(jìn)程的序號(hào)。 設(shè)置內(nèi)部標(biāo)識(shí)符主要是為了方便系統(tǒng)使用。設(shè)置內(nèi)部標(biāo)識(shí)符主要是為了方便系統(tǒng)使用。 (2) 外部標(biāo)識(shí)符。它由創(chuàng)建者提供，通常是由字母、數(shù)外部標(biāo)識(shí)符。它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶字組成，往往是由用戶(進(jìn)程進(jìn)程)在訪問(wèn)該進(jìn)程時(shí)使用。為了在訪問(wèn)該進(jìn)程時(shí)使用。為了描述進(jìn)程的家族關(guān)系，描述進(jìn)程的家族關(guān)系， 還應(yīng)設(shè)置父進(jìn)程標(biāo)識(shí)及子進(jìn)程標(biāo)識(shí)。還應(yīng)設(shè)置父進(jìn)程標(biāo)識(shí)及子進(jìn)程標(biāo)識(shí)。此外，還可

4、設(shè)置用戶標(biāo)識(shí)，以指示擁有該進(jìn)程的用戶。此外，還可設(shè)置用戶標(biāo)識(shí)，以指示擁有該進(jìn)程的用戶。 2) 處理機(jī)狀態(tài)處理機(jī)狀態(tài) 處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的。組成的。 通用寄存器，又稱為用戶可視寄存器，它們是通用寄存器，又稱為用戶可視寄存器，它們是用戶程序可以訪問(wèn)的，用于暫存信息，用戶程序可以訪問(wèn)的，用于暫存信息， 在大多數(shù)處理機(jī)中，在大多數(shù)處理機(jī)中，有有 832 個(gè)通用寄存器，在個(gè)通用寄存器，在RISC結(jié)構(gòu)的計(jì)算機(jī)中可超過(guò)結(jié)構(gòu)的計(jì)算機(jī)中可超過(guò) 100 個(gè)；個(gè)； 指令計(jì)數(shù)器，其中存放了要訪問(wèn)的下一條指令的地指令計(jì)數(shù)器，其中存放了要訪

5、問(wèn)的下一條指令的地址；址； 程序狀態(tài)字程序狀態(tài)字PSW，其中含有狀態(tài)信息，如條件碼、，其中含有狀態(tài)信息，如條件碼、執(zhí)行方式、執(zhí)行方式、 中斷屏蔽標(biāo)志等；中斷屏蔽標(biāo)志等； 用戶棧指針，用戶棧指針， 指每個(gè)用戶指每個(gè)用戶進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的系統(tǒng)棧，用于存放過(guò)程和進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的系統(tǒng)棧，用于存放過(guò)程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。 3) 進(jìn)程調(diào)度信息進(jìn)程調(diào)度信息 在在PCB中還存放一些與進(jìn)程調(diào)度和進(jìn)程對(duì)換有關(guān)的信中還存放一些與進(jìn)程調(diào)度和進(jìn)程對(duì)換有關(guān)的信息，包括：息，包括： 進(jìn)程狀態(tài)，指明進(jìn)程的當(dāng)前狀態(tài)，進(jìn)程狀態(tài)，指

6、明進(jìn)程的當(dāng)前狀態(tài)， 作為進(jìn)作為進(jìn)程調(diào)度和對(duì)換時(shí)的依據(jù)；程調(diào)度和對(duì)換時(shí)的依據(jù)； 進(jìn)程優(yōu)先級(jí)，用于描述進(jìn)程使進(jìn)程優(yōu)先級(jí)，用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù)，用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù)， 優(yōu)先級(jí)高的進(jìn)程應(yīng)優(yōu)先優(yōu)先級(jí)高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī)；獲得處理機(jī)； 進(jìn)程調(diào)度所需的其它信息，它們與所采進(jìn)程調(diào)度所需的其它信息，它們與所采用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待CPU的時(shí)間總的時(shí)間總和、和、 進(jìn)程已執(zhí)行的時(shí)間總和等；進(jìn)程已執(zhí)行的時(shí)間總和等； 事件，是指進(jìn)程由執(zhí)事件，是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生

7、的事件，即阻塞原因。 4) 進(jìn)程控制信息進(jìn)程控制信息 進(jìn)程控制信息包括：進(jìn)程控制信息包括： 程序和數(shù)據(jù)的地址，程序和數(shù)據(jù)的地址， 是指進(jìn)是指進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地程的程序和數(shù)據(jù)所在的內(nèi)存或外存地(首首)址，以便再調(diào)度址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從到該進(jìn)程執(zhí)行時(shí)，能從PCB中找到其程序和數(shù)據(jù)；中找到其程序和數(shù)據(jù)； 進(jìn)程進(jìn)程同步和通信機(jī)制，指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)同步和通信機(jī)制，指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制，制， 如消息隊(duì)列指針、信號(hào)量等，它們可能全部或部分地如消息隊(duì)列指針、信號(hào)量等，它們可能全部或部分地放在放在PCB中；中； 資源清單，是一張列出了除資源清單，是

8、一張列出了除CPU以外的、以外的、進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單；進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單； 鏈接指針，鏈接指針， 它給出了本進(jìn)程它給出了本進(jìn)程(PCB)所在隊(duì)列中的下一個(gè)所在隊(duì)列中的下一個(gè)進(jìn)程的進(jìn)程的PCB的首地址。的首地址。 3. 進(jìn)程控制塊的組織方式進(jìn)程控制塊的組織方式 引起阻塞和喚醒的事件：引起阻塞和喚醒的事件： 信號(hào)量是荷蘭的計(jì)算機(jī)科學(xué)家信號(hào)量是荷蘭的計(jì)算機(jī)科學(xué)家Dijkstra于于1965年提出的，年提出的，也是最早的同步方法。也是最早的同步方法。所謂信號(hào)量：是一個(gè)僅能由同步原語(yǔ)對(duì)其進(jìn)行操作的整所謂信號(hào)量：是一個(gè)僅能由同步原語(yǔ)對(duì)其進(jìn)行操作的

9、整型變量。用變量型變量。用變量S表示。表示。Dijkstra將這兩個(gè)同步原語(yǔ)命名為將這兩個(gè)同步原語(yǔ)命名為“ P操作操作”，“ V操作操作”。分別表示為分別表示為wait(S)和和signal(S)。Wait(s)操作操作Wait(s) s.value = s.value -; if (s.value 0) 該進(jìn)程狀態(tài)置為等待狀態(tài)該進(jìn)程狀態(tài)置為等待狀態(tài) 將該進(jìn)程的將該進(jìn)程的PCB插入相應(yīng)的等待隊(duì)列插入相應(yīng)的等待隊(duì)列末尾末尾s.queue; 例：例：S = 4S = 0S = 2P1P2Signal(s)操作操作Signal(s) s.value = s.value +; if (s.value

10、= 0) 喚醒相應(yīng)等待隊(duì)列喚醒相應(yīng)等待隊(duì)列s.queue中等待的一個(gè)中等待的一個(gè)進(jìn)程進(jìn)程 改變其狀態(tài)為就緒態(tài)改變其狀態(tài)為就緒態(tài) 并將其插入就緒隊(duì)列并將其插入就緒隊(duì)列 P，V操作的功能描述見(jiàn)下圖：操作的功能描述見(jiàn)下圖： 入口入口 S1 S S 0 入信號(hào)量等待隊(duì)列入信號(hào)量等待隊(duì)列 置置“等待等待”狀態(tài)狀態(tài) 轉(zhuǎn)進(jìn)程調(diào)度轉(zhuǎn)進(jìn)程調(diào)度 0 P，V操作可用軟件和硬件來(lái)執(zhí)行。無(wú)論操作可用軟件和硬件來(lái)執(zhí)行。無(wú)論P(yáng)操作操作和和V操作，它們的執(zhí)行都必須是一個(gè)操作，它們的執(zhí)行都必須是一個(gè) 不可被中斷的不可被中斷的整體。整體。注注：物理意義：物理意義：S 0時(shí)，時(shí)，S為可用資源量；為可用資源量；S = 0時(shí)，可用資源

11、量正好用完；時(shí)，可用資源量正好用完；S 0時(shí)，時(shí)，|S|為等待資源的隊(duì)列長(zhǎng)度，即還欠資源數(shù)為等待資源的隊(duì)列長(zhǎng)度，即還欠資源數(shù)(在信號(hào)量上等待的進(jìn)程數(shù)在信號(hào)量上等待的進(jìn)程數(shù)) 臨界區(qū)臨界區(qū)設(shè)有設(shè)有N個(gè)進(jìn)程共享一互斥段對(duì)如下兩種情況個(gè)進(jìn)程共享一互斥段對(duì)如下兩種情況每次只允許一個(gè)進(jìn)程進(jìn)入互斥段；每次只允許一個(gè)進(jìn)程進(jìn)入互斥段；最多允許最多允許M個(gè)進(jìn)程個(gè)進(jìn)程(MN)同時(shí)進(jìn)入互斥段；同時(shí)進(jìn)入互斥段；所采用信號(hào)量是否相同？信號(hào)量值的變化范圍如何？所采用信號(hào)量是否相同？信號(hào)量值的變化范圍如何？答：所采用的信號(hào)量相同，為答：所采用的信號(hào)量相同，為mutex。第一種情況第一種情況mutex初值為初值為1，變化范圍

12、為，變化范圍為-(N-1) mutex 1的的整數(shù)，第二種情況整數(shù)，第二種情況mutex初值為初值為M，變化范圍變化范圍為為 MN mutex M的整數(shù)。的整數(shù)。圖 2-10 前趨圖舉例 放產(chǎn)品放產(chǎn)品取產(chǎn)品取產(chǎn)品1個(gè)生產(chǎn)者與個(gè)生產(chǎn)者與1個(gè)消費(fèi)者，共享個(gè)消費(fèi)者，共享1個(gè)單緩沖個(gè)單緩沖生產(chǎn)者進(jìn)程將產(chǎn)生產(chǎn)者進(jìn)程將產(chǎn)品放入空品放入空Buffer消費(fèi)者進(jìn)程從滿消費(fèi)者進(jìn)程從滿Buffer中取走產(chǎn)品中取走產(chǎn)品n個(gè)個(gè)Buffer k k個(gè)緩沖區(qū)、個(gè)緩沖區(qū)、i i個(gè)生產(chǎn)者和個(gè)生產(chǎn)者和j j個(gè)消費(fèi)者個(gè)消費(fèi)者1. 桌上有一空盤，允許存放一個(gè)水果。爸桌上有一空盤，允許存放一個(gè)水果。爸爸可向盤中放蘋果，或放橘子，兒子專

13、門爸可向盤中放蘋果，或放橘子，兒子專門等著吃盤中的橘子，女兒專門等著吃盤中等著吃盤中的橘子，女兒專門等著吃盤中的蘋果。規(guī)定當(dāng)盤空時(shí)一次只能放一個(gè)水的蘋果。規(guī)定當(dāng)盤空時(shí)一次只能放一個(gè)水果供取用，試實(shí)現(xiàn)爸爸、兒子和女兒三個(gè)果供取用，試實(shí)現(xiàn)爸爸、兒子和女兒三個(gè)并發(fā)進(jìn)程的同步。并發(fā)進(jìn)程的同步。 爸爸進(jìn)程爸爸進(jìn)程:while(1) wait(empty); 放水果放水果; if (橘子橘子) signal(orange); if(蘋果蘋果) signal(apple);兒子進(jìn)程兒子進(jìn)程:while(1) wait(orange); 取橘子取橘子; signal(empty);女兒進(jìn)程女兒進(jìn)程:while

14、(1) wait(apple); 取蘋果取蘋果; signal(empty);信號(hào)量信號(hào)量:empty=1;orange=0;apple=0;signal (x);2.7 進(jìn)進(jìn) 程程 通通 信信 2.7.1 進(jìn)程通信的類型進(jìn)程通信的類型 1. 共享存儲(chǔ)器系統(tǒng)共享存儲(chǔ)器系統(tǒng)(Shared-Memory System) 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。 (2) 基于共享存儲(chǔ)區(qū)的通信方式。 2. 消息傳遞系統(tǒng)消息傳遞系統(tǒng)(Message passing system) 不論是單機(jī)系統(tǒng)、多機(jī)系統(tǒng)，還是計(jì)算機(jī)網(wǎng)絡(luò)，消息傳遞機(jī)制都是用得最廣泛的一種進(jìn)程間通信的機(jī)制。在消息傳遞系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換，是以格式

15、化的消息(message)為單位的；在計(jì)算機(jī)網(wǎng)絡(luò)中，又把message稱為報(bào)文。程序員直接利用系統(tǒng)提供的一組通信命令(原語(yǔ))進(jìn)行通信。操作系統(tǒng)隱藏了通信的實(shí)現(xiàn)細(xì)節(jié)，大大減化了通信程序編制的復(fù)雜性，而獲得廣泛的應(yīng)用。消息傳遞系統(tǒng)的通信方式屬于高級(jí)通信方式。又因其實(shí)現(xiàn)方式的不同而進(jìn)一步分成直接通信方式和間接通信方式兩種。 3. 管道管道(Pipe)通信通信 所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫進(jìn)程)， 以字符流形式將大量的數(shù)據(jù)送入管道；而接受管道輸出的接收進(jìn)程(即讀進(jìn)程)，則從管道中接收(讀)數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故又稱為管道通信。這種方式首創(chuàng)于U