第2章

進程管理1本章學習目標本章主要介紹進程的概念、狀態(tài)、構成以及

Linux進程的相關知識。掌握進程的概念掌握進程的描述、狀態(tài)及轉換理解進程的特征了解Linux進程的描述及進程通信掌握進程的同步與互斥，并能靈活運用理解線程的概念及特征第2章

進程管理教學內容2進程的基本概念進程的描述進程控制進程的同步與互斥進程同步問題舉例進程通信線程

本章小結2.1

進程的基本概念32.1.1

程序的順序執(zhí)行及其特征程序的順序執(zhí)行程序是人們要計算機完成的一些指令序列，是一個按嚴格次序、順序執(zhí)行的操作序列，是一個靜態(tài)的概念。我們把一個具有獨立功能的程序獨占處理機，直到最后結束的過程稱為程序的順序執(zhí)行。程序順序執(zhí)行時的特征順序性。封閉性?？稍佻F(xiàn)性。第2章

進程管理2.1.2

程序的并發(fā)執(zhí)行及其特征41．并發(fā)執(zhí)行的概念所謂程序的并發(fā)性，是指多道程序在同一時間間隔內同時發(fā)生。程序的并發(fā)執(zhí)行可總結為：一組在邏輯上互相獨立的程序或程序段在執(zhí)行過程中，其執(zhí)行時間在客觀上互相重疊，即一個程序段的執(zhí)行尚未結束，另一個程序段的執(zhí)行已經(jīng)開始的一種執(zhí)行方式。第2章

進程管理2．程序并發(fā)執(zhí)行時的特征5間斷性程序在并發(fā)執(zhí)行時，由于它們共享系統(tǒng)資源，以及為完成同一項任務而相互合作，致使這些并發(fā)執(zhí)行的程序之間，形成了相互制約的關系。相互制約將導致并發(fā)程序具有“執(zhí)行——暫停——執(zhí)行”這種間斷性的活動規(guī)律。失去封閉性某程序在執(zhí)行時，必然會受到其它程序的影響。不可再現(xiàn)性在并發(fā)環(huán)境下，同一個程序執(zhí)行多次，執(zhí)行的過程可能不同。用程序作為描述其執(zhí)行過程以及共享資源的基本單位是不合適的。因此引入了進程作為描述程序的執(zhí)行過程、共享資源的基本單位。第2章

進程管理2.1.3

進程的定義與特征6進程的定義人們對進程下過許多定義?，F(xiàn)列舉其中的幾種：進程是程序的一次執(zhí)行。進程是可以和別的進程并發(fā)執(zhí)行的計算。進程就是一個程序在給定活動空間和初始條件下，在一個處理機上的執(zhí)行過程。進程是程序在一個數(shù)據(jù)集合上的運行過程，它是系統(tǒng)進行資源分配和調度的一個獨立單位進程是動態(tài)的，有生命周期的活動。內核可以創(chuàng)建一個進程，最終將由內核終止該進程使其消亡。第2章

進程管理進程和程序之間的關系7進程和程序是兩個完全不同的概念，但又有密切的聯(lián)系。它們之間的主要區(qū)別是：程序是靜態(tài)的概念，；而進程則是程序的一次執(zhí)行過程。它是動態(tài)的概念。進程是一個能獨立運行的單位，能與其它進程并發(fā)執(zhí)行；而程序是不能作為一個獨立運行的單位而并發(fā)執(zhí)行的。程序和進程無一一對應的關系。各個進程在并發(fā)執(zhí)行過程中會產(chǎn)生相互制約關系，而程序本身是靜態(tài)的，不存在這種異步特征。第2章

進程管理2．進程的特征8從進程與程序的區(qū)別可以看出，進程具有如下特征：動態(tài)性動態(tài)性是進程最基本的特性。進程由創(chuàng)建而產(chǎn)生，由調度而執(zhí)行，因得不到資源而暫停執(zhí)行，以及因撤消而消亡。并發(fā)性這是指多個進程實體，同存于內存中，能在一段時間段內同時執(zhí)行。并發(fā)性是進程的重要特征，同時也是操作系統(tǒng)的重要特征。提高并發(fā)性，可以提高系統(tǒng)的效率。獨立性進程是一個能獨立運行的基本單位，同時也是系統(tǒng)中獨立獲得資源和獨立調度的基本單位。異步性這是指進程按各自獨立的、不可預知的速度向前推進；或者說，進程按異步方式運行。結構特征從結構上看，進程實體是由程序段、數(shù)據(jù)段及進程控制塊三部分組成，也稱這三部分為進程映像。第2章

進程管理2.1.4

進程的基本狀態(tài)及轉換9進程的三個基本狀態(tài)進程通常至少有三種基本狀態(tài)：就緒狀態(tài)（ready）進程運行所需的外部條件滿足，但因為其它進程已占用CPU，所以暫時不能運行。執(zhí)行狀態(tài)(running)外部條件滿足，進程已獲得CPU，其程序正在執(zhí)行。在單處理機系統(tǒng)中，只有一個進程處于執(zhí)行狀態(tài)。阻塞狀態(tài)(blocked)進程因等待某種事件發(fā)生，而暫時不能運行的狀態(tài)，稱為阻塞狀態(tài)，也稱為等待狀態(tài)。系統(tǒng)中處于這種狀態(tài)的進程可能有多個，通常將它們排成一個隊列，也有的系統(tǒng)則根據(jù)阻塞原因的不同將這些進程排成多個隊列。第2章

進程管理2．進程狀態(tài)的轉換10對于一個系統(tǒng)中處于就緒狀態(tài)的進程，在調度程序為之分配了處理機之后，該進程便可執(zhí)行，相應地，它由就緒態(tài)轉變?yōu)閳?zhí)行狀態(tài)。正在執(zhí)行的進程也稱為當前進程，如果因分配給它的時間片已用完而被暫停執(zhí)行時，該進程便由執(zhí)行狀態(tài)又回到就緒狀態(tài)；一個處在執(zhí)行狀態(tài)的進程，如果因發(fā)生某事件而使進程的執(zhí)行受阻，使之無法繼續(xù)執(zhí)行，該進程將由執(zhí)行狀態(tài)轉變?yōu)樽枞麪顟B(tài)。一個處于阻塞狀態(tài)的進程，當它所需的外部事件滿足，它應由阻塞狀態(tài)變?yōu)榫途w狀態(tài)。第2章

進程管理程執(zhí)行完成或撤消阻塞狀態(tài)就緒狀態(tài)調度用片間時進程創(chuàng)建進等待某事件發(fā)生如I/O請求外部事件發(fā)生圖2-1進程的基本狀態(tài)及轉換圖11完第2章

進程管理3．引入掛起狀態(tài)時的進程狀態(tài)12所謂掛起狀態(tài)，實際上就是一種靜止的狀態(tài)。一個進程被掛起后，不管它是否在就緒狀態(tài)，系統(tǒng)都不分配給它處理機。在引入掛起狀態(tài)后，進程之間的狀態(tài)轉換除了四種基本狀態(tài)轉換以外，又增加了以下幾種：活動就緒——靜止就緒?；顒幼枞o止阻塞。靜止就緒——活動就緒。靜止阻塞——活動阻塞。第2章

進程管理執(zhí)行外部事件滿足外掛起激活掛激活活動就緒靜止就緒活動阻塞靜止阻塞調度圖2-2具有掛起狀態(tài)的進程狀態(tài)轉換等部事件外待起件滿部條掛起足完成或撤消第2章

進程管理132.1.5

Linux進程的狀態(tài)14Linux系統(tǒng)的一個任務總體上有以下幾種狀態(tài)：運行狀態(tài)（running）該狀態(tài)對應state取值為TASK_RUNNING。等待狀態(tài)（waiting）中斷處理狀態(tài)（interrupt

routine）此狀態(tài)對應state取值TASK_RUNNING。系統(tǒng)調用期間（system

call）此狀態(tài)對應state取值TASK_RUNNING。從系統(tǒng)調用返回（return

from

system

call）第2章

進程管理（6）就緒態(tài)（ready）15處于此狀態(tài)的進程正在競爭處理機，但此刻處理機正在為另一個進程服務。此狀態(tài)對應state取值TASK_RUNNING。Linux系統(tǒng)內核在進程控制塊中用state成員描述進程當前的狀態(tài)，并明確定義了5種進程狀態(tài)。它們分別是：TASK-RUNNING狀態(tài)，Linux系統(tǒng)中的運行狀態(tài)實際包含了上述基本狀態(tài)中的執(zhí)行和就緒兩種狀態(tài)。TASK-INTERRUPTIBLE狀態(tài)，可中斷的等待態(tài)。進程正在等待某些事件。TASK-UNINTERRUPTIBLE狀態(tài)，等待態(tài)，不可中斷。TASK-ZOMBIE狀態(tài)，僵死態(tài)。TASK-STOPPED狀態(tài)，暫停態(tài)。第2章

進程管理Linux任務狀態(tài)轉換圖運行態(tài)從系統(tǒng)調用返回中斷例程系統(tǒng)調用等待就緒用戶態(tài)中斷調度系統(tǒng)態(tài)圖2-3Linux任務狀態(tài)轉換圖2.2

進程的描述進程實體通常是由程序、數(shù)據(jù)集合和PCB這三部分構成，也稱為“進程映象”。PCB程序部分第2章

進程管理17圖2-4進程的一般組成模型2.2.1

進程控制塊PCB18PCB集中反映一個進程的動態(tài)特征，當系統(tǒng)創(chuàng)建了一個新進程時，就為它建立一個PCB；當進程終止后，系統(tǒng)回收其PCB，該進程在系統(tǒng)中就不存在了。所以，PCB是進程存在的惟一標志?？梢园凑展δ軐CB分成四個組成部分：進程標識符、處理機狀態(tài)、進程調度信息、進程控制信息。第2章

進程管理1．進程標識符19進程標識符用于惟一地標識一個進程。一個進程通常有兩種標識符：進程內部標識符。進程外部標識符。處理機狀態(tài)：由各種寄存器中的內容組成。進程調度信息進程狀態(tài)。進程優(yōu)先級。進程調度所需要的其它信息。事件，或阻塞原因。進程控制信息，包括：程序和數(shù)據(jù)的地址；進程同步和通信機制；資源清單；鏈接指針。第2章

進程管理2.2.2

進程控制塊的組織方式20各進程的PCB有如下幾種組織方式：線性方式、鏈接方式和索引方式。1．線性方式將各進程的PCB依次放入一個表中，結構如下圖所示。PCB1PCB2PCB3……PCBn-1PCBn第2章

進程管理圖2-5PCB的線性組織方式2．鏈接方式運行隊列指針就緒隊列指針PCBPCBPCB0阻塞隊列1指針阻塞隊列2指針鏈接方式是經(jīng)常采用的方式。其原理是：按照進程的不同狀態(tài)分別將其放在不同的隊列。Linux操作系統(tǒng)就是應用這種進程控制塊組織方式。PCB0PCBPCBPCB0PCBPCBPCB0圖2-6

PCB鏈接隊列示意圖21第2章

進程管理3．索引方式系統(tǒng)根據(jù)所有進程的狀態(tài)建立幾張索引表。執(zhí)行指針就緒索引表PCB1PCB2PCB3就緒表指針PCB4PCB5阻塞索引表阻塞表指針PCB6PCB7圖2-7

PCB索引結構示意圖第2章

進程管理222.2.3

Linux進程的PCB23Linux系統(tǒng)中的進程稱為任務。該系統(tǒng)的進程控制塊PCB用一個稱為task-struct的結構體來描述，Linux系統(tǒng)

PCB包含以下信息：進程描述信息進程標識號（pid，process

identifier）用戶和組標識（user

and

group

identifier）連接信息（Links）進程控制信息進程當前狀態(tài)調度信息記時信息通信信息第2章

進程管理Linux支持典型的UNIX進程間通信機制——信號、管道24，也支持SystemⅤ通信機制——共享內存、信號量和消息隊列。進程資源信息記錄了與該進程有關的存儲器的各種地址和資料、文件系統(tǒng)以及打開文件的信息等等。CPU現(xiàn)場信息第2章

進程管理2.3

進程控制25所謂進程控制，就是系統(tǒng)使用一引起具有特定功能的程序段來創(chuàng)建、撤消進程以及完成進程各狀態(tài)間的轉換，從而達到多進程高效率并發(fā)執(zhí)行和協(xié)調、實現(xiàn)資源共享的目的。原語：把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能并且不可被中斷的程序段稱為原語。原語的特點是：系統(tǒng)程序、不可被中斷。系統(tǒng)在創(chuàng)建、撤消一個進程以及要改變進程的狀態(tài)時，都要調用相應的程序段來完成這些功能。用于進程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等。第2章

進程管理2.3.1

進程的創(chuàng)建與終止26進程的創(chuàng)建導致進程創(chuàng)建的事件有：用戶登錄、作業(yè)調度、為用戶提供服務等。創(chuàng)建原語Creat()，通過下述步驟創(chuàng)建一個進程。申請空白PCB。為新進程分配資源。初始化進程控制塊。將新建進程插入就緒態(tài)隊列。進程的終止過程在進程中，操作系統(tǒng)調用進程終止原語，終止本進程。過程如下：根據(jù)被終止進程的標識符，從PCB隊列中檢索出該進程的PCB，從中讀出該進程的狀態(tài)。。若被終止進程正處于執(zhí)行狀態(tài)，應立即終止該進程的執(zhí)行，該進程被終止后應重新進程調度。檢查該進程有無子孫進程，若有，則應將其所有子孫進程終止。釋放終止的進程所占有的資源，將其歸還它的父進程或者系統(tǒng)。將被終止的進程從它的PCB隊列中移出。第2章

進程管理3．進程阻塞與進程喚醒27進程狀態(tài)的轉換需要通過進程之間的同步或通信機構來實現(xiàn)，也可直接使用“阻塞原語”和“喚醒原語”來實現(xiàn)。進程的阻塞當一個進程所等待的某一事件尚未發(fā)生時，該進程調用阻塞原語block()將自己阻塞，轉換為等待狀態(tài)。進程的喚醒處于等待狀態(tài)的進程，只有當該進程所等待的外部事件發(fā)生時，才由發(fā)生該事件的進程調用喚醒原語wakeup()將它喚醒。第2章

進程管理2.3.2

幾個相關的Linux系統(tǒng)調用28在Linux系統(tǒng)中，系統(tǒng)向用戶提供了一些對進程進行控制的系統(tǒng)調用。常用的有：fork()系統(tǒng)調用Linux利用fork()系統(tǒng)調用創(chuàng)建一個新進程。Exec系統(tǒng)調用利用exec系統(tǒng)調用執(zhí)行另一個程序。exit()系統(tǒng)調用父進程在創(chuàng)建子進程時，應在進程的末尾寫一條exit，使子進程自我終止。wait系統(tǒng)調用將調用進程掛起，直至其子進程因暫停或終止而發(fā)來軟中斷信號為止。第2章

進程管理2.3.3

進程的阻塞與喚醒保存該進程的CPU現(xiàn)場字置該進程的狀態(tài)阻塞進程PCB進入等待隊列轉進程調度實現(xiàn)進程的執(zhí)行狀態(tài)到等待狀態(tài)，又由等待狀態(tài)到就緒狀態(tài)轉換的兩種原語，分別為阻塞原語與喚醒原語。入口 入口從等待隊列取被喚醒進程將被喚醒進程置為就緒態(tài)被喚醒進程插入就緒隊列轉進程調度或返回圖2-8阻塞原語的實現(xiàn)29圖2-9喚醒原語的實現(xiàn)第2章

進程管理2.4

進程的同步與互斥302.4.1

臨界資源的概念1．臨界資源兩個或兩個以上的進程不能同時使用的資源為臨界資源。臨界資源可能是一些獨占設備，如打印機、磁帶機等；也可能是一些共享變量、表格、鏈表等。第2章

進程管理2．臨界區(qū)31每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)。在臨界區(qū)前面增加一段用于進行檢查的代碼，把這段代碼稱為進入?yún)^(qū)；相應地，在臨界區(qū)后面再加一段用于退出臨界區(qū)的代碼，稱為退出區(qū)。進程中除去上述進入?yún)^(qū)和退出區(qū)，其它部分的代碼，稱為剩余區(qū)。這樣，可將一個訪問臨界資源的進程描述如下：repeat進入?yún)^(qū)；臨界區(qū)；退出區(qū)；剩余區(qū)；until

false;第2章

進程管理2.4.2

進程的互斥與同步同步與互斥的概念所謂進程互斥，是指多個進程不能同時使用同一個臨界資源CR。即兩個或兩個以上的進程必須互斥地使用臨界資源，或不能同時進入臨界區(qū)CS。兩個邏輯上完全獨立、毫無關系的進程，由于競爭同一個資源而相互制約，就稱為進程的互斥。所謂進程同步，是指有協(xié)作關系的進程之間，要不斷地調整它們之間的相對速度或執(zhí)行過程，以保證臨界資源的合理利用和進程的順利執(zhí)行。實現(xiàn)進程同步的機制稱為進程同步機制。同步機制應遵循的規(guī)則所有同步機制都應遵循下列準則：空閑讓進。忙則等待。有限等待。（4）讓權等待。第2章

進程管理322.4.3

鎖機制實現(xiàn)互斥的一種軟件是采用鎖機制，即提供一對上鎖（Lock）和開鎖（UnLock）原語，以及一個鎖變量w（或者是鎖位１個bit）。加鎖及解鎖原語可描述如下：加鎖原語：Lock

w：L：if

w=1

then

goto

LElse

w:=1開鎖原語：UnLock

w：w：=0;第2章

進程管理332.4.4

信號量機制34申請和釋放臨界資源的兩個原語操作：wait操作和signal操作，有時也稱為Ｐ操作和Ｖ操作。信號量（Semaphore），也叫做信號燈，它是在信號量

同步機制中用于實現(xiàn)進程的同步和互斥的有效數(shù)據(jù)結構。我們可以為每類資源設置一個信號量。它有多種類型的數(shù)據(jù)結構，即：整型信號量、記錄型信號量、ＡＮＤ型信號量及信號量集等。第2章

進程管理1．整型信號量35整型信號量的數(shù)值表示當前系統(tǒng)中可用的該類臨界資源的數(shù)量。如設置整型信號量s，則s的值意義為：s>0，則s的值表示系統(tǒng)中空閑的該類臨界資源的個數(shù)；s=0，則表示系統(tǒng)中該類臨界資源剛好全部被占用，而且沒有進程在等待該臨界資源；s<0，則s的絕對值表示系統(tǒng)中的進程等待該類臨界資源的個數(shù)；第2章

進程管理2．記錄型信號量36記錄型信號量的數(shù)據(jù)結構由兩部分構成。例如：定義記錄型信號量Ｓ，則：s的值表示系統(tǒng)中可用的該類臨界資源的數(shù)量，而Ｌ為進程鏈表指針，指向等待該類資源的PCB隊列。設變量Ｓ為記錄型信號量，則wait（Ｓ）操作和signal（Ｓ）操作的流程如下圖所示：第2章

進程管理Wati(S)是Wati(S)s=s-1申請到資源本進程繼續(xù)本進程入阻塞隊列s≥0否轉進程調度圖2-10

Wait操作原語流是signal(S)s=s+1喚醒一阻塞態(tài)進程s≤0否圖2-11

signal操作原語流釋放該類資源本進程繼續(xù)第2章

進程管理37申請臨界資源的原語wait操作可描述為：procedure

wait(S)var

S:

semaphore;begin38s:

=s-1;if

s≥0

then本進程繼續(xù)；else{將本進程放入阻塞態(tài)隊列；轉進程調度;}end釋放臨界資源的原語signal操作可描述為：procedure

signal(S)var

S:

semaphore;begins:

=s+1;if

s≤0

then喚醒指針L所指的阻塞態(tài)進程；end第2章

進程管理3．ＡＮＤ型信號量39ＡＮＤ同步機制的基本思想是：將進程在整個運行過程中需要的所有資源，一次性全部地分配給進程，待進程使用完成后再一起釋放。只要有一個資源尚未能分配給進程，其它所有可能分配的資源，也不能分配給它。也稱為ＡＮＤ同步。AND型信號量集機制可描述如下：第2章

進程管理Swait(S1,

S2,

…,

Sn)if

Si≥1

and

…

and

Sn≥1

thenfor

i:

=1

to

n

do40Si:

=Si-1;endforelse將該進程放入阻塞態(tài)隊列；endifSsignal(S1,

S2,

…,

Sn)for

i:

=1

to

n

doSi=Si+1;喚醒所有因Si不滿足而進入阻塞隊列的進程；endfor;第2章

進程管理4．信號量集41信號量集機制的基本思想是：在AND型信號量集的基礎上進行擴充，進程對信號量Si的測試值為ti（用于信號量的判斷，即Si>=ti，表示資源數(shù)量低于ti時，便不予分配），占用值為di（用于信號量的增減，即Si=Si-d1和Si=Si+d1）Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,

d1;

...;

Sn,

dn);一般“信號量集”的幾種特定情況：Swait(S,d,d)表示每次申請d個資源，當少于d個時，便不分配；Swait(S,1,1)表示互斥信號量；Swait(S,1,0)作為一個可控開關（當S≥1時，允許多個進程進入臨界區(qū)；當S=0時，禁止任何進程進入臨界區(qū)）；“信號量集”未必成對使用Swait和Ssignal。如：一起申請，但可以不一起釋放。第2章

進程管理2.5

進程同步問題舉例422.5.1

生產(chǎn)者—消費者問題1．問題的描述有一批生產(chǎn)者進程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費者進程去消費。為方便生產(chǎn)者進程與消費者進程能并發(fā)執(zhí)行，在兩者之間設置了一個具有n個緩沖區(qū)的緩沖池，生產(chǎn)者進程將它所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中；消費者進程可從一個緩沖區(qū)中取走產(chǎn)品去消費。第2章

進程管理012……i………n-2n-1假設初始情況下緩沖池為空，即counter＝０。為在生產(chǎn)者—消費者問題中實現(xiàn)各進程的同步，可設下列信號量：（假設初始情況下沒有進程使用緩沖池，且緩沖池中各緩沖區(qū)都是空的。）mutex：互斥使用緩沖池信號量，由于初始情況下無進程使用緩沖池，故初值mutex=１；empty：使用緩沖池中空緩沖區(qū)的信號量，由于初始情況下所有緩沖區(qū)為空，故初值empty=n；full：使用緩沖池中滿緩沖區(qū)的信號量，由于初始情況下沒有緩沖區(qū)存放產(chǎn)品，故初值full＝０。設開始時生產(chǎn)者進程存放產(chǎn)品和消費者進程取產(chǎn)品時，都從第０號緩沖區(qū)開始，并設這些生產(chǎn)者和消費者地位相當，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個消息。第2章

進程管理in

out圖2-12生產(chǎn)者—消費者問題中的緩沖池43／＊定義信號量并賦初值＊／44算法及程序Var

mutex,

empty,

full:semaphore∶=1,n,0;buffer:array［0,

…,

n-1］

of

item;／＊定義存取指針的初始位置＊／in,

out:

integer∶=0,

0;beginparbegin生產(chǎn)者進程proceduer：beginrepeat…生產(chǎn)一件產(chǎn)品;…wait(empty);wait(mutex);將產(chǎn)品放入下一個緩沖區(qū);in∶=(in+1)

mod

n;signal(mutex);signal(full);until

false;end第2章

進程管理消費者進程consumer：beginrepeatwait(full);wait(mutex);45從下一個緩沖區(qū)中取走一件產(chǎn)品;out∶=(out+1)mod

n;signal(mutex);signal(empty);消費這件產(chǎn)品;until

false;endparendend第2章

進程管理4．在生產(chǎn)者—消費者問題中應注意：46（１）在每個程序中用于實現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對地出現(xiàn)。（２）對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的進程中，這樣保證生產(chǎn)者進程和消費者進程的同步及交替執(zhí)行。（３）在每個進程中，多個wait操作順序不能顛倒，而

signal操作的次序是無關緊要的。第2章

進程管理2.5.2

讀者—寫者問題47問題的提出一文件Ｆ可以被多個并發(fā)進程共享，將這些訪問該文件的進程按訪問方式分為兩類：一類只能讀共享對象的內容，把這類進程稱為讀進程或讀者；另一類進程則要更新（寫）共享對象文件F，將這些進程稱為寫進程或寫者。試用Wait、Signal操作解決各進程間的同步問題。問題的分析顯然，多個讀者同時讀一個共享對象是可以的，然而一個寫者不能與其它任何讀者或寫者同時共享該文件。亦即：在使用共享文件時，一個寫進程與其它所有進程都是互斥的。但多個讀進程之間不存在互斥的現(xiàn)象。如圖2-13所示。第2章

進程管理共享文件F寫進程W48讀進程R1…讀進程Rn圖2-13讀者—寫者問題設讀進程為reader，寫進程為writer。為實現(xiàn)reader與writer進程間的同步與互斥，設如下變量及信號量：wmutex：互斥使用該共享文件信號量。如：寫進程write與讀進程reader在使用文件時是互斥的；共享文件只有一個，設初始情況未被使用，則初值為1。readcount：整型變量，表示正在讀的進程個數(shù)。初值為0。該變量屬臨界資源。rmutex：計數(shù)器readcount的信號量。因為readcount是一個可被多個reader進程訪問的臨界資源，為此設一信號量。設初始狀態(tài)下無進程讀和寫，故rmutex的初值設為1。第2章

進程管理由于多個進程可以同時讀，因此只要有一個reader進

程在讀，其它reader進程便不必申請該共享文件，直接讀即可；若無文件在讀，則第一個讀文件的進程必須做申請該

文件的操作。只要有read進程在執(zhí)行，則不允許writer進程去寫。因此，僅當readcount=0,即無reader進程在讀時，

reader進程才需要執(zhí)行wait(wmutex)操作。若wait(wmutex)操作成功，reader進程便可去讀，相應地，做readcount+1操作。同理，僅當reader進程在執(zhí)行了readcount減1操作后其值為0時，才須執(zhí)行signal(wmutex)操作，以便讓writer進程寫。49第2章

進程管理3．算法及程序50讀者—寫者問題可描述如下：Var:rmutex,

wmutex:semaphore:=1,1;Readcount:integer:=0;beginparbegin讀者進程：Reader:beginrepeatwait(rmutex);if

readcount=0

then

wait(wmutex);readcount:=Readcount+1;signal(rmutex);第2章

進程管理第2章

進程管…理進行讀操作;…wait(rmutex);readcount:

=readcount-1;if

readcount=0

then

signal(wmutex);signal(rmutex);until

false;end寫者進程：writer:beginrepeatwait(wmutex);執(zhí)行寫操作;signal(wmutex);until

false;endparendend514．注意事項及提示52對于寫進程，共享文件是臨界資源；而對于讀進程，該文件不是臨界資源。整型變量readcount是臨界資源，所以在使用前后要進行Wait、Signal操作。第2章

進程管理2.5.3

哲學家進餐問題531．問題的提出設有5個哲學家圍坐在一張圓桌前吃飯。桌上有5只筷子，在每人之間放一只。哲學家要吃飯時，只有分別從左、右兩邊都拿到筷子時，才能吃飯。如果筷子已在他人手上，則該哲學家必須等待到他人吃完后才能拿到筷子；任何一個哲學家在自己未拿到兩只筷子吃飯之前，決不放下自己手里的筷子。試描述5位哲學家吃飯的進程。第2章

進程管理圖2-14哲學家就餐餐問題第2章

進程管理542．問題分析55放在桌子上的筷子是臨界資源，在一段時間內只允許一位哲學家使用。為了實現(xiàn)對筷子的互斥使用，可以為每一只筷子設置一個信號量，由這五個信號量構成信號量數(shù)組：Var

chopstick:

array［0,

…,

4］

of

semaphore;設初始條件下，所有哲學家都未吃，故所有信號量均被初始化為1。3．實現(xiàn)方法假設每一位哲學家拿筷子的方法都是：先拿起左邊的筷子，再拿起右邊的筷子，則第i位哲學家的活動可描述為：第2章

進程管理Pi

(

)begin56Var

chopstick:

array［0,

…,

4］of

maphore=[1,1,1,1,1];repeatwait(chopstick［i］);wait(chopstick［(i+1)

mod

5］);eat;…signal(chopstick［i］);signal(chopstick［(i+1)

mod

5］);think;until

false;end第2章

進程管理以上算法存在一個問題：假設5個哲學家同時拿起左邊的筷子，那么再去拿右邊的筷子時，就會產(chǎn)生死鎖。下面給出幾種解決方法。至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。規(guī)定奇數(shù)號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號哲學家則相反。最后總會有一位哲學家能獲得兩只筷子而進餐。具體程序段參看實訓教材。57第2章

進程管理4．不產(chǎn)生死鎖的哲學家就餐問題算法2.6

進程通信58進程間的信息交換稱為進程通信。通常，進程間的通信分為兩種：控制信息的傳送與大量信息的傳送。將進程間控制信息的交換稱為低級通信，而把進程之間大批量數(shù)據(jù)的交換稱為高級通信。進程的互斥與同步為低級通信方式，相應地，也稱wait、signal操作為低級的通信原語。僅通過P、V操作或鎖的方法是無法實現(xiàn)進程的高級通信的。高級通信方式可分為三大類：共享存儲器系統(tǒng)、消息傳遞系統(tǒng)和管道通信系統(tǒng)。第2章

進程管理2.6.1

共享存儲器系統(tǒng)59共享存儲器系統(tǒng)的類型基于共享數(shù)據(jù)結構的通信方式在這種通信方式中，要使各進程共用某些數(shù)據(jù)結構，借以實現(xiàn)各進程間的信息交換。如在生產(chǎn)者—消費者問題中，就是用有界緩沖區(qū)這種數(shù)據(jù)結構來實現(xiàn)通信的。這種通信方式是低效的，只適用于傳遞相對少量的數(shù)據(jù)。基于共享存儲區(qū)的通信方式。在存儲器中劃出了一塊共享存儲區(qū)，各進程可通過對共享存儲區(qū)中的數(shù)據(jù)的讀或寫來實現(xiàn)通信。第2章

進程管理2．Linux共享存儲區(qū)通信的實現(xiàn)共享存儲區(qū)的建立利用系統(tǒng)調用shmget()建立一塊共享存儲區(qū)。該系統(tǒng)調用將返回該共享存儲區(qū)的描述符shmid；若尚未建立，便為進程建立一個指定大小的共享存儲區(qū)。共享存儲區(qū)的操縱可以用shmctl()系統(tǒng)調用對共享存儲區(qū)的狀態(tài)信息進行查詢，如其長度、所連接的進程數(shù)、創(chuàng)建者標識符等；也可設置或修改其屬性，如共享存儲區(qū)的許可權、當前連接的進程計數(shù)等；還可用來對共享存儲區(qū)加鎖或解鎖，以及修改共享存儲區(qū)標識符等。3.共享存儲區(qū)的附接與斷開在進程已經(jīng)建立了共享存儲區(qū)或已獲得了其描述符后，還須利用系統(tǒng)調用shmat()將該共享存儲區(qū)附接到用戶給定的某個進程的虛地址shmaddr上，并指定該存儲區(qū)的訪問屬性，即指明該區(qū)是只讀，還是可讀可寫。此后，此共享存儲區(qū)便成為該進程虛地址空間的一部分。進程可采取與對其它虛地址空間一樣的存取方法來訪問。當進程不再需要該共享存儲區(qū)時，再利用系統(tǒng)調用shmdt()把該區(qū)與進程斷開。4．幾個相關系統(tǒng)調用62共享存儲區(qū)通信中常用的系統(tǒng)調用：shmget

(key

,size

,flag)：功能：獲得一個共享存儲區(qū)，若成功，其返回值為該共享存儲區(qū)的描述符。shmat(id,addr

,flag)從邏輯上將一個共享存儲區(qū)附接到進程的虛擬地址空間上。shmdt(addr)：把一個共享存儲區(qū)從指定進程的虛地址空間斷開。shmctl(id,cmd,buf)對與共享存儲區(qū)關聯(lián)的各種參數(shù)進行操作，從而對共享存儲區(qū)進行控制。第2章

進程管理2.6.2

消息傳遞系統(tǒng)63在消息傳遞系統(tǒng)中，進程間的數(shù)據(jù)交換，是以格式化的消息（message）為單位的。程序員直接利用系統(tǒng)提供的一組通信命令進行通信。因實現(xiàn)方式的不同分為直接通信方式和間接通信方式。間接通信方式又稱為信箱通信方式。信箱是一種數(shù)據(jù)結構，邏輯上可分為兩部分：信箱頭和信箱體。信箱頭包含箱體的結構信息，信箱體由多個格子構成。信箱通信一般是進程之間的雙向通信。第2章

進程管理1．直接通信方式這種通信是固定在一對進程之間。用來發(fā)送和接收消息。兩條原語的形式如下：send(B,message); 發(fā)送一個消息給接收進程B；receive(A,message); 接收進程A發(fā)來的消息；通常情況下，接收進程可與多個發(fā)送進程通信，因此，它不可能事先指定發(fā)送進程。對于這樣的應用，在接收進程接收消息的原語中的源進程參數(shù)，是完成通信后的返回值，接收原語可表示為：receive(id,message);其中，id為接收消息進程的標識符。2．間接通信方式間接通信方式又稱為信箱通信方式。信箱是一種數(shù)據(jù)結構，邏輯上可分為兩部分：信箱頭和信箱體。信箱頭包含箱體的結構信息，信箱體由多個格子構成，它實際上就是一個有界緩沖池。信箱通信一般是進程之間的雙向通信。如圖2-15所示。圖2-15進程的信箱通信方式進程A信箱頭進程Bsendreceivereceive信箱體send3．消息緩沖隊列通信機制（1）消息緩沖隊列通信機制中所用的主要數(shù)據(jù)結構是消息緩沖區(qū)。在設置消息緩沖隊列時，還應添

加用于對消息隊列進行操作和實現(xiàn)同步的信號量，并將它們存入進程的PCB中。當一個發(fā)送進程要

發(fā)送消息時，便形成一個消息，并發(fā)送給指定的

接收進程。接收進程將所有的消息緩沖區(qū)鏈成一

個隊列，其隊列首由接收進程PCB中的隊列隊首

指針mq來指出。（2）發(fā)送原語發(fā)送進程在發(fā)送消息之前，應先在自己的內存空間設置一發(fā)送區(qū)，然后調用發(fā)送原語，把消息發(fā)送給接收進程。（3）接收原語接收進程調用接收原語，從自己的消息緩沖隊列中，選取第一個消息緩沖區(qū)，并將其中的數(shù)據(jù)復制到指定的消息接收區(qū)內。4．Linux系統(tǒng)關于消息傳遞的相關系統(tǒng)調用msgget(key,flag):功能：獲得一個消息的描述符，該描述符指定一個消息隊列以便用于其他系統(tǒng)調用。msgsnd(id,msgp,size，flag);功能：發(fā)送一消息。msgrcv(id,msgp,size,type,flag)功能：接受一消息。msgctl(id,cmd,buf)：功能：查詢一個消息描述符的狀態(tài),設置它的狀態(tài)及刪除一個消息描述符。2.6.3

管道通信系統(tǒng)69所謂管道，是指用于連接一個讀進程和一個寫進程，以實現(xiàn)他們之間通信的一個共享文件，又名pipe文件。為了協(xié)調雙方的通信，管道機制必須提供以下三方面的協(xié)調能力：互斥，即當一個進程正在對pipe執(zhí)行讀/寫操作時，其它(另一)進程必須等待。同步，指當讀寫進程使用pipe時，需要同步使用。確定對方是否存在，只有確定了對方已存在時，才能進行通信。第2章

進程管理2.6.4信號通信機制70信號的基本概念每個信號都對應一個正整數(shù)常量，即信號編號。信號機制具有以下三方面的功能：發(fā)送信號。發(fā)送信號的程序用系統(tǒng)調用kill()實現(xiàn)；預置對信號的處理方式。接收信號的程序用signal()來實現(xiàn)預置處理方式；收受信號的進程按事先的規(guī)定完成對相應事件的處理。第2章

進程管理2．信號的發(fā)送信號的發(fā)送，是指由發(fā)送進程把信號送到指定進程的信號域的某一位上。進程用kill()向一個進程或一組進程發(fā)送一個信號。信號的處理對軟中斷信號的處理分三種情況進行：如果進程收到的軟中斷是一個已決定要忽略的信號（function=1），進程不做任何處理便立即返回；進程收到軟中斷后便退出（function=0）；執(zhí)行用戶設置的軟中斷處理程序。4．相關的Linux系統(tǒng)調用72kill(

)功能：向一個或一組進程發(fā)送一個軟中斷信號。signal(

)功能：預置對信號的處理方式，允許調用進程控制軟中斷信號。第2章

進程管理2.7 線程73線程是比進程更小的能獨立運行的基本單位。2.7.1

線程的基本概念線程（thead）是進程中執(zhí)行運算的最小單位，亦即執(zhí)行處理機調度的基本單位。在引入線程的操作系統(tǒng)中，可以在一個進程內部進行線程切換，現(xiàn)場保護工作量小。

線程與進程的比較：進程是資源分配的基本單位。同一進程的所有線程共享該進程的所有資源。線程是分配處理機的基本單位，