操作系統(tǒng)計算題總結(jié)

本文格式為Word版，下載可任意編輯——操作系統(tǒng)計算題總結(jié)西南石油大學軟件工程2023級王林

一、第三章的計算有點多（ＰＶ操作，銀行家算法，低級調(diào)度算法）ＰＶ操作

操作系統(tǒng)的進程管理中，PV是重點和難點信號量：信號量是個數(shù)據(jù)結(jié)構(gòu)。

structsemaphore{intvalue;pcb*blockqueue;}mutex;

其中value是信號量的值；blockqueue是等待使用該信號量的進程排成的隊列的對手指針。p操作：當一個進程對信號量mutex執(zhí)行p操作時，執(zhí)行兩個動作：mutex.valu–；//申請一個資源if(mutex.value=0)//假使有進程在等待信號量

wakeup();//從該信號量的等待隊列中喚醒一個進程

注：操作系統(tǒng)會保證PV操作的原子性，也就是說當一個進程執(zhí)行PV操作，檢測信號量時，不受中斷。

看一下PV操作實現(xiàn)的功能：

實現(xiàn)進程之間的互斥；實現(xiàn)進程之間的同步；（接下來的兩個例題是互斥與同步的典型）

區(qū)別：互斥是為了保證資源一次只能由一個進程使用，互斥進程彼此在規(guī)律上是完全無關(guān)的，它們的運的運行不具有時間次序的特征。而同步是為了實現(xiàn)進程通信，同步進程之間具有合作關(guān)系，在執(zhí)行時間上須依照一定順序協(xié)同進行。

1.互斥：進出教室問題：有一個變量count，初值為0，一個學生進入教室則count++，出

教室則count–-。mutex=1;

IN:OUT:p(mutex);p(mutex);count++;count–;v(mutex);v(mutex);

過程：一個學生進入教室執(zhí)行IN，p操作，mutex.value=0；假設(shè)在進行count++之前遇到了中斷，而中斷之后跳回來時正好這個學生又在出教室，那么這時候就會執(zhí)行OUT，mutex.value=-1，該OUT進程進入睡眠，返回IN進程，count=1，v操作，mutex.value=0（說明有等待使用count的進程）；喚醒OUT進程，count=0，v操作，mutex.value=1。注意上面劃線部分的假設(shè)。PV操作在這就是為了保證這種競爭狀況的發(fā)生。

2.同步：桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，

西南石油大學軟件工程2023級王林

兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當盤空時一次只能放一只水果供吃者取用，請用P、V原語實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步。

分析：在此題中，爸爸、兒子、女兒共用一個盤子，盤中一次只能放一個水果。當盤子為空時，爸爸可將一個水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必需等待；若放入果盤中的是蘋果，則允許女兒吃，兒子必需等待。此題實際上是生產(chǎn)者-消費者問題的一種變形。這里，生產(chǎn)者放入緩沖區(qū)的產(chǎn)品有兩類，消費者也有兩類，每類消費者只消費其中固定的一類產(chǎn)品。

解：在此題中，應(yīng)設(shè)置三個信號量S、So、Sa，信號量S表示盤子是否為空，其初值為l；信號量So表示盤中是否有桔子，其初值為0；信號量Sa表示盤中是否有蘋果，其初值為0。同步描述如下：

intS＝1;intSa＝0;intSo＝0;main(){cobeginfather();son();

daughter();coend

｝

father(){while(1){P(S);

將水果放入盤中;

if（放入的是桔子）V(So);elseV(Sa);}}son(){while(1){P(So);

從盤中取出桔子;V(S);吃桔子;｝}

daughter(){while(1){P(Sa);

從盤中取出蘋果;V(S);吃蘋果;｝｝

一些問題：為什么要設(shè)計三個信號量？由于這里盤子的狀態(tài)有三種狀況。所以在PV操作用在同步的時候，資源都多少種狀態(tài)，就應(yīng)當有多少個信號量（高并發(fā)的不一定好，需要更多

西南石油大學軟件工程2023級王林

的信號量，這樣消耗系統(tǒng)的資源就更多）。還有，有沒有留意到，每一次“吃〞的操作都是在V操作之后進行，這是為什么呢？這是由于V操作是釋放資源的一個操作，當然是越早釋放對系統(tǒng)越有利啊。

哲學家就餐問題

五個哲學家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一把叉子；解一：

設(shè)fork[5]為5個信號量，初值為均1

設(shè)信號量S，用于封鎖第5個哲學家，初值為4。Philosopheri：while(1)

{思考;P(S);P(fork[i]);

P(fork[(i+1)%5]);進食;V(fork[i]);

V(fork[(i+1)%5]);V(S);}

解二：

設(shè)fork[5]為5個信號量，初值為均1。Philosopher1：while(1){思考;P(fork[1]);P(fork[2]);進食;V(fork[2]);V(fork[1]);}

Philosopher2：while(1){思考;P(fork[3]);P(fork[2]);進食;V(fork[2]);V(fork[3]);}

西南石油大學軟件工程2023級王林

銀行家算法

?練習：有三類資源A(17)、B(5)、C(20)。有5個進程P1～P5。T0時刻系統(tǒng)狀態(tài)如下：??P1?P2?P3?P4?P5?最大需求?559?536?4011?425?424?已分派?212?402?405?204?314?問(1)T0時刻是否為安全狀態(tài)，給出安全系列。

(2)T0時刻，P2:Request(0,3,4)，能否分派，為什么？

(3)在(2)的基礎(chǔ)上P4:Request(2,0,1)，能否分派，為什么？(4)在(3)的基礎(chǔ)上P1:Request(0,2,0)，能否分派，為什么？

解析：（1）（求安全系列：說的通俗點就是把所有剩下的資源分給進程，但是要看剩下的資源數(shù)是否能滿足進程的需求量，滿足了就分給它，等它終止后釋放它所擁有的所有資源，再繼續(xù)往下分，直到所有的進程都運行成功。）

1>先求剩余量A(17)、B(5)、C(20)————三個資源的各自的總量

Work=233————分給每個進程后三個資源所剩下的量{這樣子算的：

A（17）-2-4-4-2-3=2，即總量減去已分派里邊豎起來相加的和等于剩余}2>再求每個進程T0時刻的所需量：Need=最大雪球—已分派綜上可得到如圖：最大需求已分派NeedP1P2P3P45595364011425212402405204347134006221西南石油大學軟件工程2023級王林

P5424314110觀測Need的那些值，Work=233，work能夠need的有P4跟P5，二者選哪個都可以，譬如就選擇P4，即我們把work的值分給P4，讓它運行完成，P4釋放所有資源，則work的值就變?yōu)榱藈ork=437（P4的所有資源都要釋放哦），再繼續(xù)找滿足條件的進程以此類推，可得到安全系列:{P4,P2,P5,P3,P1}(第一問在答題時只需寫出一個安全系列就行了，

且安全系列并不確定)

（2）在(2)的基礎(chǔ)上P2:Request(0,3,4)（P2的need（=134））第一次比較：Request(0,3,4)=Available(=233)由于Request(0,3,4)>=Available(=233)

所以不能分派。{Available(=2