1基礎知識總結考核要點：進程的定義及特征、進程與程序的異同、進程的狀態及引起狀態轉換的典型原因?；A要點：（1）進程的并發執行是指若干個進程在執行時間上是重疊的。（2）進程是一個程序對某個數據集的一次運行活動。（3）并發進程在訪問共享變量時，可能會出現與時間有關的錯誤（4）程序并發執行與順序執行相比產生了一些新特征，分別是：間斷性，失去封閉性和不可再現性。2（5）前趨圖展示了語句間的一種執行順序關系，而進程圖展示的是進程之間的家族關系。（6）進程的基本特征是：動態性，并發性，獨立性，異步性和結構特征。（7）程序的順序執行通常是在單道程序的工作環境中，具有運行結果可再現的特點。（8）進程的基本狀態有執行、就緒和阻塞。（9）進程是動態的概念，而程序是靜態的概念。3（10）進程控制塊的初始化工作包括初始化標識符信息、初始化處理機狀態信息、初始化處理機控制信息。（11）在進程管理中，當進程等待某一事件時，將執行狀態從變為阻塞狀態。（12）當進程執行的時間片用完時，進程從執行狀態變成就緒狀態。（13）分配到必要資源并獲得處理機時的進程狀態是執行狀態。4（14）進程從結構上講，包括程序段、數據段和進程控制塊這幾部分。（15）在一個單處理機系統中，若有4個用戶進程且假定當前時刻有一個進程處于執行狀態，同處于就緒狀態的進程最多有3個，最少有0個。（16）在操作系統中，不可中斷的操作稱為原語。（17）進程控制就是對系統中的進程實施有效的管理，通過使用進程創建、進程撤消、進程阻塞、進程喚醒等控制原語實現。5（18）在操作系統引入線程概念的主要目的是減少程序并發執行時所需付出的時空開銷，提高程序執行的并發程度。（19）線程是進程內一個相對獨立的、可調度的執行單元。（20）線程是系統進行調度的基本單位。6常見考試知識點分析1、多道程序設計(1)定義：是在主存中同時存放多個用戶的作業，使之同時處于運行狀態而共享系統資源。實現的前提是：中斷和通道技術的出現。(2)多道程序的特點：并行性、共享性。(3)多道程序的目標目標：是充分使用系統所有資源并盡可能地使它們并行工作。把硬件的代價交叉分頁在大量并行用戶之間，而使計算機系統的代價極小化。7(4)多道程序設計的實現解決的3個問題：存儲保護、程序浮動處理機的管理和調度、系統資源的管理和調度。(5)多道程序系統所必須解決的問題：提出解決各種沖突的策略；協調并發活動的關系；保證數據的一致性；實現數據的存取控制。2、進程(1)定義與特征83、進程的狀態及轉換：4、進程控制塊PCB：最重要的記錄型數據結構，記錄了操作系統所需要的、用于描述進程情況及控制進程運行所需要的全部信息。是使用一個在多道程序環境下不能獨立運行的程序，成為一個能獨立運行的基本單位，一個能與其他進程并發執行的進程。5、進程隊列：就緒隊列和等待隊列，隊列的入隊和出隊。97、中斷及中斷響應(1)定義：是指CPU對系統中發生的異步事件的響應或處理，異步事件是指無一定時序關系而隨機發生的事件。10(2)中斷在操作系統中的作用與地位：能充分發揮處理機的使用效率；提高系統的實時處理的能力。(3)中斷的功能：發現中斷源，提出中斷請求；保護現場；啟動并運行處理中斷事件的程序。(4)中斷響應和處理中斷響應：是指處理器每執行一條指令后，硬件的中斷裝置立即檢查有無中斷事件發生，若有，則暫停現行進程的執行，而讓OS的中斷處理程序應用處理器的過程。中斷處理：OS的中斷處理程序對中斷事件進行處理時所要做的3方面工作：11保護被中斷進程的現場信息：把中斷時的通用寄存器、控制寄存器內容以及舊程序狀態字PSW保存到被中斷進程的進程控制塊中。分析中斷原因：根據舊程序狀態字的中斷可知發生中斷的具體原因。處理發生的中斷事件：由相應的程序去做。8、中斷優先級和中斷屏蔽中斷優先級：中斷裝置按預定的順序來響應同時出現的中斷事件，這個順序稱為中斷優先級。高低順序：硬件故障中斷、自愿中斷、程序性中斷、外部中斷和輸入/輸出中斷。1210、進程的并發性（1）進程的順序性：封閉性和可再現性（2）進程的并發性11、與時間有關的錯誤12、臨界區與P、V操作（1）臨界區：并發進程中與共享變量有關的程序段。相關臨界區：并發進程中涉及相同變量的那些程序段。（2）P、V操作1313、進程的互斥與同步（1）進程的互斥：指當有若干個進程使用某一共享資源時，任何時刻最多只允許一個進程使用，而其他要使用該資源的進程必須等待，直到占用資源者釋放該資源（2）進程的同步：指并發進程之間存在一種制約關系，一個進程的執行依賴另一個進程的消息，當一個進程沒有得到另一進程的消息時應等待，直到消息到達才被喚醒。14（3）同步與互斥的混合問題：進程的互斥是進程間競爭共享資源的使用權，這種競爭沒有固定的必然關系；進程同步，涉及共享資源的并發進程之間有一種必然的依賴關系。15實戰練習現代計算機系統一般都采用(A)，其基本思想是在主存中同時存放多個用戶的作業，使之同時處于運行狀態而共享資源。A

多道程序設計技術B多處理機技術C分布式系統技術D分時系統技術16一個運行進程必須具有的3種基本狀態是(C)A就緒狀態、掛起狀態和執行狀態B掛起狀態、阻塞狀態和執行狀態C

就緒狀態、執行狀態和阻塞狀態D就緒狀態、執行狀態和終止狀態17進程和程序的根本區別在于(A)A靜態與動態特點B是不是被調入到內存中C是不是具有就緒、運行和等待三種狀態D是不是占有處理器下面所列的進程的3種基本狀態之間的轉換不正確的是(D)A就緒狀態→執行狀態B執行狀態→就緒狀態C執行狀態→阻塞狀態D就緒狀態→阻塞狀態1819操作系統是根據(B)來對并發執行的進程進行控制和管理的。A進程的基本狀態B進程控制塊C多道程序設計D進程的優先權在進程進程塊中，主要包括4方面用于描述和控制進程運行的信息，其中(C)主要是由處理機各種寄存器中的內容所組成。A進程標識符信息B進程調度信息C處理機狀態信息D進程控制信息2021目前，常用的PCB組織方式有兩種(A)A鏈接方式和索引方式B鏈接方式和順序方式C順序方式和索引方式D直接方式和順序方式22計算機系統采用多道程序設計技術后（D）A縮短了每個程序的執行時間B系統效率隨并行工作道數成比例增長C使用設備時不會發生沖突D提高了系統效率多道程序設計是指（D）A程序段執行不是順序的B有多個程序同時進入CPU中運行C同一個程序可以對應多個不同進程D有多個程序同時進入主存并發執行2324以下不屬于進程基本特性的是（A）A進程是具有特定功能的一組指令的集合，它指出了處理器執行操作的步驟B進程可以并發執行C進程具有動態性，多個不同的進程可以包含相同的程序D進程具有3種基本狀態：就緒狀態、運行狀態和阻塞狀態25在一個單處理器系統中，處于運行狀態的進程（C）A不能被打斷B不能請求系統調用C只有一個D可以有多個在單處理器系統中，如果同時存在有10個進程，則處于就緒隊列中的進程最多為（C）A

1

B

8

C

9

D

102627進程具有3種基本狀態：就緒狀態、執行狀態和阻塞狀態。進程在執行過程中，其狀態總是不停地發生變化，下面關于進程狀態變化的說法中正確的是（B）A一個進程必須經過進程的3種基本狀態才能結束B在分時系統中，一個正在運行進程的時間片如果終結，該進程將轉入就緒狀態C三種進程狀態是進程運行過程中的基本狀態，進程可能同時處于某幾種狀態中D進程一旦形成，首先進入的是運行狀態。28操作系統根據（D）控制和管理進程，它是進程存在的標志A中斷裝置B中斷寄存器C程序狀態字D進程控制塊29在任何時刻，一個進程的狀態變化（C）引起另一個進程的狀態變化A必定B一定不C不一定D不可能30對于兩個并發進程，設互斥信號量為A，若A=0，則（C）A表示有一個進程進入臨界區，另一個進程等待進入B表示有兩個進程進入臨界區C表示有一個進程進入臨界區D表示沒有進程進入臨界區31造成進程發生錯誤的因素是與進程占用處理器的時間，執行的速度及外界的影響有關。而這些錯誤都與時間有關，所以稱為（B）A時間因素B與時間有關的錯誤C時間錯誤D時間問題P、V操作是對（A）進行操作A信號量B執行速度C執行時間D執行結果3233當兩個進程合作完成一個任務，在并發執行中，一個進程要等待其合作伙伴發來消息，或者建立某個條件后再向前執行，這種制約性合作關系被稱為進程的（C）A調度B執行C同步D互斥信號量被定義為一個整型變量，其初始值是（D）A

0

B無任何限制C負整數D非負數3435在消息緩沖通信中，系統應提供若干（B），用以存放信息。A隊列緩沖區B消息緩沖區C容量大的緩沖區D容量小的緩沖區用信箱實現進程間互通信息的通信機制要有兩個通信原語，它們是（C）A“發送”原語和“執行”原語B“就緒”原語和“執行”原語C

“發送”原語和“接收”原語D“就緒”原語和“接收”原語3637對若干個并發進程共享某一變量的相關臨界區的管理，下列說法不正確的是（A）A相關的進程可以同時進入B不能強迫一個進程無限地等待進入它的臨界區C一次至多一個進程能夠進入臨界區D不能讓一個進程無限制地在臨界區執行38由于并發進程執行的隨機性，一個進程對另一個進程的影響是不可預測的，甚至造成結果的不正確，（c）A造成不正確的因素只與外界的影響有關系B造成不正確的因素只與執行的速度有關C造成不正確的因素與時間有關D造成不正確的因素只與進程占用處理器有關39并發進程之間的關系是（D）A無關的B相關的C可能相關的D可能是無關的，也可能是有交往的40下列關于P、V操作的說法中正確的是（A）A

P、V操作是兩個操作，而且都是原語操作B

P、V操作中P操作可以不用原語方式，而V操作必須使用原語操作C

P、V操作是一個過程，同一般函數，過程一樣，只是執行管理臨界區的操作D

P、V操作中P操作必須使用原語方式，而V操作可以不使用原語操作41如果有4個進程共享同一程序段，每次允許3個進程進入該程序段，若用P、V操作作為同步機制，則信號量的取值范圍是（C）A

4,3,2,1,-1

B

2,1,0,-1,-2C

3,2,1,0,-1

D

2,1,0,-2,-342下列關于進程同步和互斥的說法中錯誤的是（D）A進程互斥和進程同步有時也統稱為進程的同步B進程互斥是進程同步的特例，互斥進程是競爭共享資源的使用，而同步進程之間必然有依賴關系C進程的同步和互斥都涉及并發進程訪問共享資源的問題D進程同步是進程互斥的一種特殊情況。43在進程通信中，（B）常用信件交換信息。A低級通信B高級通信C信息緩沖D消息通信由于并發進程之間（C）不能由進程本身控制，當它們在共享某些資源的時候可能會產生與時間有關的錯誤。A分配外部設備B分配內存空間C執行的相對速度D占用存儲器的位置4445下面對線程的描述中，錯誤的是（D）A同一進程中的線程可共享該進程的主存空間B線程是調度和執行單位C不同的線程可執行相同的程序D線程是資源分配單位46P、V操作是（A）。A兩條低級進程通信原語B兩組不同的機器指令C兩條系統調用命令D兩條高級進程通信原語47進程間的同步是指進程間在邏輯上的相互（B）關系。A聯接B制約C繼續D調用下面對進程的描述中，錯誤的是（D）A進程是動態的概念B進程執行需要處理機C進程是有生命期的D進程是指令的集合4849下面所述步驟中，（A）不是創建進程所必需的。A由調度程序為進程分配CPUB建立一個進程控制塊C為進程分配內存D將進程控制塊鏈入就緒隊列50為了進行進程協調，進程之間應當具有一定的聯系，這種聯系通常采用進程間交換數據的方式進行，這種方式稱為（D）。A進程互斥B互斥C進程制約D進程通信51為使進程由活動就緒轉變為靜止就緒，應利用(A2)原語；為使進程由執行狀態轉變為阻塞狀態，應利用(B4)原語；為使進程由靜止就緒變為活動就緒，就應利用(C3)原語；為使進程從阻塞狀態變為就緒狀態，應利用(D5)原語。

A，B，C，D：(1)create(2)suspend(3)active(4)block(5)wakeup。52對于記錄型信號量，在執行一次wait操作時，信號量的值應當(A3)，當其值為(B2)時，進程應阻塞。在執行signal操作時，信號量的值應當為(C)2，當其值為(D4)時，應喚醒阻塞隊列中的進程。

A，C:(1)不變；(2)加1；(3)減1；(4)加指定數值；(5)減指定數值。

B，D:(1)大于0；(2)小于0；(3)大于等于0；(4)小于等于0。53用信號量S實現對系統中4臺打印機的互斥使用，S.value的初值應設置為(A4)，若S.value的當前值為-1，則表示S.L隊列中有(B2)個等待進程。

A：(1)1；(2)0；(3)-1；(4)4；(5)-4。

B：(1)0；(2)1；(3)2；(4)3；(5)4；(6)5；(7)6。542.4經典進程的同步問題2.4.1生產者和消費者問題：是相互合作進程關系的一種抽象，是有限緩沖區問題BoundedBuffer,常用來說明同步原語的能力。有多種變型,多種不同情況。同步進程之間存在著哪些同步關系:55(1)所有進程間互斥訪問公用緩沖池:mutex=1(2)生產者速度快時，緩沖池滿，生產者等待。(先消費，后生產）:empty=n(3)消費者速度快時，緩沖池空，消費者等待。（先生產，后消費）:full=0注意：P、V操作的位置順序，一般先同步，后互斥。56ProducerConsumerRepeatRepeat

生產一個消息;P(full);P(empty);P(mutex);P(mutex)取消息；投放消息;V(mutex);V(mutex);V(empty);V(full);Untilfalse;Untilfalse572009年綜合應用題例：三個進程P1、P2、P3互斥使用一個包含N(N>0)個單元的緩沖區。P1每次用produce()生成一個正整數并用put()送入緩沖區某一空單元中；P2每次用getodd()從該緩沖區中取出一個奇數并用countodd()統計奇數個數；P3每次用geteven()從該緩沖區中取出一個偶數并counteven()統計偶數個數。請用信號量機制實現這三個進程的同步與互斥活動，并說明所定義信號量的含義。要求用偽代碼描述。58答案：定義信號量S1控制P1與P2之間的同步；S2控制P1與P3之間的同步；empty控制生產者與消費者之間的同步；mutex控制進程間互斥使用緩沖區。程序如下：

Vars1=0,s2=0,empty=N,mutex=1;ParbeginP1:beginX=produce();/*生成一個數*/P(empty);/*判斷緩沖區是否有空單元*/P(mutex);/*緩沖區是否被占用*/ put(x);Ifx%2==0V(s2);/*如果是偶數，向P3發出信號*/elseV(s1);/*如果是奇數，向P2發出信號*/V(mutex);/*使用完緩沖區，釋放*/

59P2：beginP(s1);/*收到P1發來的信號，已產生一個奇數*/P(mutex);/*緩沖區是否被占用*/Getodd();Countodd():=coutodd()+1;V(mutex);/*釋放緩沖區*/V(empty);/*向P1發信號，多出一個空單元*/End.

60P3:beginP(s2);/*收到P1發來的信號，已產生一個偶數*/P(mutex);/*緩沖區是否被占用*/Geteven();Counteven():=counteven()+1;V(mutex);/*釋放緩沖區*/V(empty);/*向P1發信號，多出一個空單元*/End.Parend.61例銀行排隊問題(北京大學2000）銀行有n個柜員,每個顧客進入銀行后先取一個號,并且等著叫號,當一個柜員空閑后，就叫下一個號。解：將顧客號碼排成一個隊列,顧客進入銀行領取號碼后,將號碼由隊尾插入;柜員空閑時,從隊首取得顧客號碼,并且為這個顧客服務,由于隊列為若干進程共享,所以需要互斥.柜員空閑時,若有顧客,就叫下一個顧客為之服務.因此,需要設置一個信號量來記錄等待服務的顧客數.62Cobeginvarmutex=1,customer_count=0:semaphore;cobeginprocesscustomerbeginrepeat

取號碼；

p(mutex);

進入隊列；

v(mutex);v(customer_count);untilfalse;end63processservers_i(i=1,...,n)beginrepeatp(customer_count);p(mutex);

從隊列中取下一個號碼；

v(mutex);

為該號碼持有者服務；

untilfalseendCoend64例交通問題有橋如圖示：（北京大學1992年研究生試題）橋北南65車流如箭頭所示。橋上不允許兩車交會，但允許同方向車輛依次通行（即橋上可以有多個同方向的車）。用P、V操作實現交通管理以防止橋上堵塞。解：設置countA和countB表示由南往北、由北往南已在橋上行駛的汽車數目，初值為0,設置SA表示對countA的互斥，初值為1，設置SB表示對countB的互斥，初值為1,設置mutex表示對橋的互斥，初值為166P1：由南往北{行駛到橋頭；

P（SA）;If(countA=0)P(mutex);countA++;V(SA);過橋；P(SA);countA--;if(countA=0)V(mutex);V(SA);}67P2：由北往南{行駛到橋頭；

P（SB）;If(countB=0)P(mutex);countB++;V(SB);過橋；P(SB);countB--;if(countB=0)V(mutex);V(SB);}68桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規定:當盤空時一次只能放一只水果供吃者取用，請用P、V原語實現爸爸、兒子、女兒三個并發進程的同步。69分析：本題中，爸爸、兒子、女兒共用一個盤子，且盤中一次只能放一個水果。當盤子為空時，爸爸可將一個水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待，若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待。本題實際是生產者—消費者問題的一種變形。這里，生產者放入緩沖區產品有兩類，消費者也有兩類，每類消費者只消費其中固定的一類產品。70解：本題中，應設置三個信號量s,so,sa，信號量s表示盤子是否為空，其初值為1，信號量so表示盤中是否有桔子，其初值為0，信號量sa表示盤中是否有蘋果，其初值為0。同步描述如下：

vars,sa,so:integer=1,0,0;father:beginp(s);

將水果放入盤中；

if(放入的是桔子)v(so);elsev(sa);end;71son:beginp(so);

從盤中取出桔子；

v(s);

吃桔子；

end72daughter:beginp(sa);

從盤中取出蘋果；

v(s);

吃蘋果；

end73(北京大學90年試題)(略)(1)寫出P、V操作的定義

(2)有三個進程PA、PB和PC合作解決文件打印問題：PA將文件記錄從磁盤讀入主存的緩沖區1，每執行一次讀一個記錄；PB將緩沖區1的內容復制到緩沖區2，每執行一次，復制一個記錄；PC將緩沖區2的內容打印出來，每執行一次打印一個記錄。緩沖區的大小等于一個記錄大小。請用P、V操作來保證文件的正確打印。74解：(2)本題中：進程PA、PB和PC之間的關系為：PA與PB共用一個單緩沖區，而PB又與PC共用一個單緩沖區，其合作方式如圖示：

從磁盤讀入復制緩沖區1緩沖區2PAPCPB打印75

當緩沖區1為空時，PA可將一個記錄讀入其中，若緩沖區1中有數據且緩沖區2為空，PB可將記錄從緩沖區1復制到緩沖區2中；若緩沖區2中有數據，則進程PC可打印記錄。其他條件下，相應進程必須等待。實際上，這是一個生產者—消費者問題。(PB既是生產者又是消費者)76

為遵循這一同步規則。應設置四個信號量empty1、empty2、full1、full2，信號量empty1和empty2分別表示緩沖區1及緩沖區2是否為空，其初值為1；信號量full1和full2分別表示緩沖區1和緩沖區2是否有記錄可供處理，其初值為0。其同步描述如下：初始化；77PA:beginrepeat

從磁盤讀一個記錄；

p(empty1);

將記錄存入緩沖區1；

v(full1);untilfalse;end78PB:beginrepeatp(full1);

從緩沖區1取出記錄；

v(empty1);p(empty2);

將記錄存入緩沖區2；

v(full2);untilfalse;end79PC:beginrepeatp(full2);

從緩沖區2中取出記錄；

v(empty2);

打印記錄；

untilfalseend80

有兩個優先級相同的并發進程m1,m2，各自計算過程如下所示。它們利用信號量s1,s2同步，信號量s1,s2初始值設置為0。x,y,z是它們共享的變量。問m1,m2運行結束后，x,y,z在理論上可能的值分別是多少?81進程m1進程m2x=1y=2V(s1)P(s1)z=x+1z=y+1P(s2)V(s2)x=z+xy=y+z82(華中理工大學99年試題)設公共汽車上，司機和售票員的活動分別是：司機的活動：啟動車輛正常行車到站停車售票員的活動：關車門售票開車門83

在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關系？用信號量和P、V操作實現它們的同步。84解：汽車行駛過程中，司機活動與售票員活動之間的同步關系為：售票員關車門后，向司機發開車信號，司機接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停后開車門讓乘客上下車。因此司機啟動車輛的動作必須與售票員關車門的動作取得同步；售票員開車門的動作也必須與司機停車取得同步。85

本題中，設置兩個信號量s1,s2，s1表示是否允許司機啟動汽車，其初值為0，s2表示是否允許售票員開門，其初值為0。描述如下：86Driver:beginrepeatp(s1);

啟動車輛；正常行駛；到站停車；

v(s2);untilfalse;endBusman:beginrepeat

關車門；

v(s1);

售票；

p(s2);

開車門；上下乘客；

untilfalse;end87(少林寺問題)某寺廟，有小和尚、老和尚若干．廟內有一水缸，由小和尚提水入缸，供老和尚飲用．水缸可容納30桶水，每次入水、取水僅為1桶，不可同時進行。水取自同一井中，水井徑窄，每次只能容納一個水桶取水。設水桶個數為5個，試用信號量和PV操作給出老和尚和小和尚的活動。88semaphoreempty=30;//表示缸中目前還能裝多少桶水，初始時能裝30桶水semaphorefull=0;//表示缸中有多少桶水，初始時缸中沒有水semaphorebuckets=5;//表示有多少只空桶可用，初始時有5只桶可用semaphoremutex_well=1;//用于實現對井的互斥操作semaphoremutex_bigjar=1;//用于實現對缸的互斥操作89young_monk(){ while(1){ P(empty); P(buckets); gotothewell; P(mutex_well); getwater; V(mutex_well); gotothetemple; P(mutex_bigjar); purethewaterintothebigjar; V(mutex_bigjar); V(buckets); V(full);}}90old_monk(){while(1){P(full);P(buckets);getabucket;P(mutex_bigjar);getwater;V(mutex_bigjar);V(buckets);V(empty);}}91有一個閱覽室，共有100個座位，讀者進入時必須先在一張登記表上登記，該表為每一座位列一表目，包括座號和讀者姓名等，讀者離開時要消掉登記的信息，試問：

（1）為描述讀者的動作，應編寫幾個程序，設置幾個進程？

（2）試用PV操作描述讀者進程之間的同步關系。92答：讀者的動作有兩個，一是填表進入閱覽室，這時要考慮閱覽室里是否有座位；一是讀者閱讀完畢，離開閱覽室，這時的操作要考慮閱覽室里是否有讀者。讀者在閱覽室讀書時，由于沒有引起資源的變動，不算動作變化。

算法的信號量有三個：seats——表示閱覽室是否有座位（初值為100，代表閱覽室的空座位數）；readers——表示閱覽室里的讀者數，初值為0；用于互斥的mutex，初值為1。93讀者進入閱覽室的動作描述getin：

while(TRUE){

P(seats);/*沒有座位則離開*/

P（mutex）/*進入臨界區*/

填寫登記表;

進入閱覽室讀書;

V（mutex）/*離開臨界區*/

V（readers）

}94讀者離開閱覽室的動作描述getout：

while(TRUE){

P（readers）/*閱覽室是否有人讀書*/

P（mutex）/*進入臨界區*/

消掉登記；

離開閱覽室；

V（mutex）/*離開臨界區*/

V（seats）/*釋放一個座位資源*/

}95某車站售票廳，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在外面等待。若把一個購票者看作一個進程，請回答下列問題：

(1)用PV操作管理這些并發進程時，應怎樣定義信號量，寫出信號量的初值以及信號量各種取值的含義。

(2)根據所定義的信號量，把應執行的PV操作填入下述方框中，以保證進程能夠正確地并發執行。96COBEGIN

PROCESS

PI(I=1，2，……)

begin；

進入售票廳；

購票；

退出；

end；

COEND

(3)若欲購票者最多為n個人，寫出信號量可能的變化范圍(最大值和最小值)。97答(1)定義一信號量S，初始值為20。(1分)

意義：S>0

S的值表示可繼續進入售

票廳的人數(1分)

S=0表示售票廳中已有20名顧客(購票者)

(1分)

S<0

|S|的值為等待進入售票廳的人數(1分)

(2)上框為P(S)

(1分)

下框為V(S)

(1分)

(3)S的最大值為20

(1分)

S的最小值為20－n

(1分)98(上海交通大學96年試題)

哲學家甲請哲學家乙、丙、丁到某處討論問題，約定全體到齊后開始討論，在討論的間隙四位哲學家進餐，每人進餐時都需使用刀、叉各一把，餐桌上的布置如圖示：請用信號量及P、V操作說明這四位哲學家的同步、互斥過程。乙丙丁甲刀1刀2叉1叉2食品99分析：本題中，這四位哲學家在討論問題期間的生活方式為交替地進行討論和進餐。由于刀、叉資源均為2，而哲學家有四位，就出現了資源競爭，為此要對他們的進餐進行同步控制。100規定：所有哲學家先申請使用刀，申請到刀后再申請使用叉，刀、叉都拿到后才能進餐。本題是標準的哲學家就餐問題。101解：設置四個信號量fork1、fork2、knife1、knife2，其初值都為1，分別表示資源叉1、叉2、刀1、刀2是否可用。同步描述如下：

乙丙丁甲刀1刀2叉1叉2食品Pa:begin甲哲學家

repeatp(knife1);p(fork1);

就餐；

v(knife1);v(fork1);

討論問題；

untilfalseend102Pb:begin乙哲學家

repeatp(knife2);p(fork1);

就餐；

v(knife2);v(fork1);

討論問題；

untilfalse;end

乙丙丁甲刀1刀2叉1叉2食品103乙丙丁甲刀1刀2叉1叉2食品Pc:begin丙哲學家

repeatp(knife2);p(fork2);

就餐；

v(knife2);v(fork2);

討論問題；

untilfalse;end104乙丙丁甲刀1刀2叉1叉2食品Pd:begin丁哲學家

repeatp(knife1);p(fork2);

就餐；

v(knife1);v(fork2);

討論問題；

untilfalse;end105一條小河上有一座獨木橋，規定每次只允許一個人過橋，現在河東河西都有人要過橋，如果把每個過橋者看作一個進程，為保證安全，請用P、V操作實現正確管理。(本題只存在互斥,不存在同步)106semaphores=1;河東進程河西進程While(1)While(1){{p(s);p(s);過橋;過橋;v(s);v(s);}}107假設有一個成品倉庫,總共能放8臺成品,生產者進程生產產品放入倉庫,消費者進程從倉庫中取出成品消費.為了防止積壓,倉庫滿的時候就停止生產.由于倉庫搬運設備只有一套,故成品的存入和取出只能分別執行,使用P、V操作來實現該方案。108Semaphoremutex=1;//實現互斥Semaphores1,s2;//s1用來表示倉庫中可放產品的數目,s2表示倉庫中已放的產品的數目S1=8;S2=0;生產者進程消費者進程While(1)while(1){{生產產品;p(s2);p(s1);p(mutex);;p(mutex);取產品產品放入倉庫;v(mutex);v(mutex);v(s1);v(s2);消費;}}109進程同步的總結考核要點：臨界區的定義及操作原則，進程同步與互斥，用信號量描述進程同步，進程通信。基礎要點：（1）進程間的同步是指進程間在邏輯上的相互制約關系。（2）在進程中，訪問臨界資源的代碼段稱為臨界區。為保證進程互斥訪問臨界資源，應在進程的臨界區前設置進入區，在臨界區后設置退出區。（3）進程間的相互制約關系有直接關系和間接關系。（4）臨界區是一段程序。110（5）在操作系統中，解決進程間同步和互斥問題的一種方法是使用信號量。（6）并發進程之間的基本關系是合作或共享資源，其中共享資源是指進程之間的一種間接關系。（7）訪問臨界資源應遵循的準則為：空閑讓進，忙則等待，有限等待，讓權等待。（8）如果信號量的當前值為－4，則表示系統中在該信號量上有4個等待進程。（9）用P、V原語管理臨界區時，信號量的初值應定義為1111（10）在操作系統中，P、V原語是一種低級進程通信原語。（11）除初值外，信號量的值只能通過P操作和V操作來改變。（12）并發進程中涉及到相同變量的程序段叫做臨界段，對這些程序段要互斥執行。（13）對于兩個并發進程，設互斥信號量為mutex，若mutex=0則表示有一個進程進入臨界區。112（14）進程通信的類型有共享存儲器、消息傳遞、管道。（15）用P、V操作管理臨界區時，任何一個進程在進入臨界區之前應調用P操作，退出臨界區時應調用V操作。（16）信號量的物理意義是當信號量值大于零時表示可用資源的數目，當信號量值小于零時，其絕對值為在該信號量上等待的進程個數。113（17）信箱通信是一種間接通信方式。（18）利用消息機制實現通信時，應有發送原語和接收原語。（19）進程通信是指進程之間的信息交換。1142009年23、單處理機系統中，可并行的是(D)

I進程與進程II、處理機與設備

III、處理機與通道IV、設備與設備

A、I、II、和III

B、I、II和IV

C、I、III和IV

D、II、III和IV1152010年24、下列選項中，導致創建新進程的操作是（C）

I用戶登陸成功

II設備分配

III啟動程序執行A僅I和IIB僅II和IIIC僅I和IIID

I、II、III1162010年25、設與某資源相關聯的信號量初值為3，當前值為1，若M表示該資源的可用個數，N表示等待該資源的進程數，則M，N分別是（B）A

0,1B

1,0C

1,2D

2,01172011年25、在支持多線程的系統中，進程P創建的若干個線程不能共享的是()A進程P的代碼段B進程P中打開的文件C進程P的全局變量D進程P中某線程的棧指針1182011年32、有兩個并發執行的進程P1和P2，共享初值為1的變量x。P1對x加1，P2對x減1。加1和減1操作的指令序列分別如下所示。

//加1操作//減1操作

loadR1,x//取x到寄存器R1中loadR2,xincR1decR2storex,R1//將R1的內存存入xstore