操作系统习题讲解一,进程概念二,进程同步和互斥进 程 概 念（一）
问题：如果系统中有 N个进程，
运行进程最多几个，最少几个？
就绪进程最多几个，最少几个？
等待进程最多几个，最少几个？
运行就绪 等待进程的状态及其转换
解答,运行进程最多 1个，最少 0个；
就绪进程最多 N-1个，最少 0个；
等待进程最多 N个，最少 0个；
概念,(1)进程、进程的基本状态；
单 CPU；进程切换瞬间；
系统进程、用户进程；
(2)死锁（不是,死机,）；
进 程 概 念（一）
进 程 概 念（二）
问题：
进程有无如下状态转换，为什么？
（ 1）等待 — 运行
（ 2）就绪 — 等待解答：
（ 1）不能,等待－就绪－运行
（ 2）不能,就绪－运行－等待问题,一个转换发生，是否另一个转换一定发生？找出所有的可能。
解答：
就绪 — 运行,不一定（系统中仅一个进程）
转换条件：被调度程序选中
运行 — 就绪,一定（讨论就绪队列的长度）
转换条件：时间片到时,或有更高优先级的进程出现进 程 概 念（三）
解答：
运行 — 等待,不一定（考虑死锁）
转换条件：等待某事件发生
等待 — 就绪,不一定转换条件：等待的事件发生进 程 概 念（三）
进 程 概 念（四）
问题,日常生活中的,进程,举例解答：
两个角度：,程序 -数据 -运行,
或,资源 -调度 -运行,
经典例子：,按照菜谱作菜,,乐队演奏,
或,向服务员请求服务,等进程同步和互斥（一）
问题,用 P.V操作解决下图之同步问题
get copy put
f s t g
进程同步和互斥（一）
c
p
c
g
p
c
g
pg
一个数据上的操作顺序,get - copy - put
Get不能向“满”的 S中放；
Copy不能从“空”的 S中取；不能向“满”的 T中放；
Put不能“空”的 T中取
（同步）信号量,{实际上也起到互斥作用 }
S_Empty,T_Empty,{初值为 1}
S_Full,T_Full; {初值为 0}
Get:
Begin
Repeat
P(S_Empty)
T_get_S();
V(S_Full);
Until false;
End
Copy:
Begin
Repeat
P(S_Full);
P(T_Empty);
S_copy_T();
V(T_Full);
V(S_Empty);
Until false;
End
Put:
Begin
Repeat
P(T_Full);
T_put_G();
V(T_Empty);
Until false;
End
进程同步和互斥（二）
问题：用 P.V操作解决下面问题司机进程：
REPEAT
启动车辆正常驾驶到站停车
UNTIL …
售票员进程：
REPEAT
关门售票开门
UNTIL …
信号量：
S_Door,{初值为 0}
S_Stop; {初值为 0}
司机进程,
Begin
Repeat
P(S_Door);
启动；
驾驶；
停车；
V(S_Stop);
Until false;
End
乘务员进程,
Begin
Repeat
关门；
V(S_Door);
售票；
P(S_Stop);
开门；
Until false;
End
同步要求：先关门，后开车；
先停车，后开门问题：
推广读写者问题中的消息缓冲处理。消息缓冲区为 k个，有 m个发送进程,n个接收进程，每个接收进程对发送来的消息都必须取一次进程同步和互斥（三）
Type BufferType = Record
msg:MessageType;
count:integer;
mutex:semaphore; {初值为 1}
empty,semaphore; {初值为 1}
full,array [1..n] of semaphore；
{初值全为 0}
End
Var mutex,semaphore; {初值为 1}
s,integer; {初值为 0}
buff,array [0..k-1] of BufferType;
{ k是缓冲区大小； n是接收进程个数 }
{ m是发送进程个数，通过 s 进行“写互斥” }
Procedure Sender_i(i:integer);
{ i 为发送进程的标号 }
Var s0,j,integer;
Begin
Repeat
P(mutex);
s0:=s;
s:=(s+1) mod k;
V(mutex);
P(buff[s0].empty)；
在 buff[s0].msg中写信息；
P(buff[s0].mutex)；
buff[s0].count:=n;
V(buff[s0].mutex);
For (j:=1 to n do)
V(buff[s0].full[j]);
Until false;
End
Procedure Recvr(i:integer);
{ i 为接收进程的标号 }
Var j,integer;
Begin
j:=0;
Repeat
P(buff[j].full[i]);
从 buff[j].msg中读信息；
P(buff[j].mutex)；
buff[j].count:= buff[j].count-1;
If (buff[j].count=0)
Then V(buff[j].empty)；
V(buff[j].mutex);
j:=(j+1) mod k
Until false;
End
第二类读者写者问题（写者优先）
1）共享读
2）互斥写、读写互斥
3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
进程同步和互斥（四）
Var
mutex,semaphore; {互斥信号量，初值为 1}
R,semaphore; {对应读者等待队列，初值为 0}
W,semaphore; {对应写者等待队列，初值为 0}
{一般变量,}
Writing,Boolean; {初值 false,有写者正在写 }
rc,integer; {初值 0,共享读的读者数 }
rq,integer; {初值 0,等待队列中读者数 }
wq,integer; {初值 0,等待队列中写者数 }
Begin
P(mutex);
If (Writing OR wq<>0)
Then Begin
rq:=rq+1;
V(mutex);
P(R);
P(mutex);{resume}
End;
rc:=rc+1;
V(mutex);
Read();
P(mutex);
rc:=rc-1;
If (rc=0 AND wq<>0)
Then Begin
wq:=wq-1;
Writing:=true;
V(mutex);
V(W);
End;
Else V(mutex) ;
End
读者进程
(a) 检测是否有写者并处理
(b) Inc(rc)
(c) Read()
(d) Dec(rc)
(e) 处理写者等待队列
Begin
P(mutex);
If (Writing OR rc>0)
Then Begin
wq:=wq+1;
V(mutex);
P(W);
End;
Else Begin
Writing:=true;
V(mutex);
Write();
P(mutex);
If (wq<>0)
Then Begin
wq:=wq-1;
V(mutex);
V(W);
End
Else
If (rq>0)
Then Begin
Writing:=false;
While (rq>0)
Begin
rq:=rq-1;
V(R) ;
End
End
Else Begin
Writing:=false;
V(mutex);
End
End
写者进程
(a) 检测是否有进程正在读写
(b) Writing(T); Write(); Writing(F)
(c) 处理写者等待队列 ;处理 Reader等待队列
P(s),s:=s-1;
If s<0
Then 将本进程插入相应队列 末尾 等待；
V(s),s:=s+1;
If s<=0
Then
从等待队列 队尾 取一个进程唤醒，
插入就绪队列进程同步和互斥（五）
对 P/V 操作定义作以下修改问题：
1）这样定义 P,V操作是否有问题？
不合理：先进后出；可能“无限等待”
2）用这样的 P,V操作实现 N个进程竞争使用某一共享变量的互斥机制。
思路：令等待队列中始终只有一个进程。
将,栈” 变成,队列”
Var S:array [1..n-1] of semaphore;
{ n为进程数目； S[i]初值为 i； S[n]到
S[1]的作用好象是 n 层筛子 }
Procedure Pi;
Var i:integer;
Begin
Repeat
Pre_Do_it();
For i:=n-1 Downto 1 Do
P(S[i]);
Do_It_In_Critical_Section;
For i:=1 To n-1 Do
V(S[i]);
Post_Do_it();
Until false;
End
3）对于 2）的解法，有无效率更高的方法。
如有，试问降低了多少复杂性？
上述解法每次都需要做 2n次 P/V操作，
性能低下。采用二叉树的思想，改进如下：
S[1..4]
P[1..4]
S1 S2
S3
让信号量处于不同的层次上，每个信号量至多控制两个进程（对两个进程进行同步）
P1 P2 P3 P4
Procedure P1;{ P2 is the same }
Begin
Repeat
P(S1);
P(S3);
Do_It();
V(S3);
V(S1);
Until false;
End;
Procedure P3;{ P4 is the same}
Begin
Repeat
P(S2);
P(S3);
Do_It();
V(S3);
V(S2);
Until false;
End;
不妨设有 4个进程 P1..P4，
Var S1,S2,S3,semaphore; {初值为 1}
假设共有 2N个进程争用临界区；
时间复杂性,2N vs N； 空间复杂性,2N vs 2N－ 1
理发师问题理发店里有一位理发师,一把理发椅和
N把供等候理发的顾客坐的椅子,如果没有顾客,则理发师便在理发椅上睡觉,
当一个顾客到来时,他必须先唤醒理发师,如果顾客到来时理发师正在理发，
则如果有空椅子，可坐下来等；否则离开。
进程同步和互斥（六）
顾客进程 i:
P(Sn);{门外观望 }
P(mutex);
进门；
V(mutex);
V(S);
等候；
理发；
V(Sn)
P(mutex);
出门；
V(mutex);
Var Sn,semaphore; {位子数目，初值为 n}
S,semaphore; {理发师睡觉，初值为 1}
mutex,semaphore; {初值为 1}
理发师进程,
Repeat
P(S);
P(mutex);
叫人理发；
V(mutex);
理发；
Until false;
用 P.V操作来实现 Receive原语,
Receive（ S,M）
Begin
根据 S找发送进程，
如果没找到出错返回 ;
申请缓冲区消息 P（ s-m）；
P(m-mutex);
将载有消息的缓冲区从消息链中取出 ;
V(m-mutex);
把消息从 M处 copy到 receiver的信息空间 ;
P(b-mutex);
是缓冲区为空；
V(b-mutex);
V(s-b);
End
其中 s-b初值,n ;s-m初值,0
问题：如果系统中有 N个进程，
运行进程最多几个，最少几个？
就绪进程最多几个，最少几个？
等待进程最多几个，最少几个？
运行就绪 等待进程的状态及其转换
解答,运行进程最多 1个，最少 0个；
就绪进程最多 N-1个，最少 0个；
等待进程最多 N个，最少 0个；
概念,(1)进程、进程的基本状态；
单 CPU；进程切换瞬间；
系统进程、用户进程；
(2)死锁（不是,死机,）；
进 程 概 念（一）
进 程 概 念（二）
问题：
进程有无如下状态转换，为什么？
（ 1）等待 — 运行
（ 2）就绪 — 等待解答：
（ 1）不能,等待－就绪－运行
（ 2）不能,就绪－运行－等待问题,一个转换发生，是否另一个转换一定发生？找出所有的可能。
解答：
就绪 — 运行,不一定（系统中仅一个进程）
转换条件：被调度程序选中
运行 — 就绪,一定（讨论就绪队列的长度）
转换条件：时间片到时,或有更高优先级的进程出现进 程 概 念（三）
解答：
运行 — 等待,不一定（考虑死锁）
转换条件：等待某事件发生
等待 — 就绪,不一定转换条件：等待的事件发生进 程 概 念（三）
进 程 概 念（四）
问题,日常生活中的,进程,举例解答：
两个角度：,程序 -数据 -运行,
或,资源 -调度 -运行,
经典例子：,按照菜谱作菜,,乐队演奏,
或,向服务员请求服务,等进程同步和互斥（一）
问题,用 P.V操作解决下图之同步问题
get copy put
f s t g
进程同步和互斥（一）
c
p
c
g
p
c
g
pg
一个数据上的操作顺序,get - copy - put
Get不能向“满”的 S中放；
Copy不能从“空”的 S中取；不能向“满”的 T中放；
Put不能“空”的 T中取
（同步）信号量,{实际上也起到互斥作用 }
S_Empty,T_Empty,{初值为 1}
S_Full,T_Full; {初值为 0}
Get:
Begin
Repeat
P(S_Empty)
T_get_S();
V(S_Full);
Until false;
End
Copy:
Begin
Repeat
P(S_Full);
P(T_Empty);
S_copy_T();
V(T_Full);
V(S_Empty);
Until false;
End
Put:
Begin
Repeat
P(T_Full);
T_put_G();
V(T_Empty);
Until false;
End
进程同步和互斥（二）
问题：用 P.V操作解决下面问题司机进程：
REPEAT
启动车辆正常驾驶到站停车
UNTIL …
售票员进程：
REPEAT
关门售票开门
UNTIL …
信号量：
S_Door,{初值为 0}
S_Stop; {初值为 0}
司机进程,
Begin
Repeat
P(S_Door);
启动；
驾驶；
停车；
V(S_Stop);
Until false;
End
乘务员进程,
Begin
Repeat
关门；
V(S_Door);
售票；
P(S_Stop);
开门；
Until false;
End
同步要求：先关门，后开车；
先停车，后开门问题：
推广读写者问题中的消息缓冲处理。消息缓冲区为 k个，有 m个发送进程,n个接收进程，每个接收进程对发送来的消息都必须取一次进程同步和互斥（三）
Type BufferType = Record
msg:MessageType;
count:integer;
mutex:semaphore; {初值为 1}
empty,semaphore; {初值为 1}
full,array [1..n] of semaphore；
{初值全为 0}
End
Var mutex,semaphore; {初值为 1}
s,integer; {初值为 0}
buff,array [0..k-1] of BufferType;
{ k是缓冲区大小； n是接收进程个数 }
{ m是发送进程个数，通过 s 进行“写互斥” }
Procedure Sender_i(i:integer);
{ i 为发送进程的标号 }
Var s0,j,integer;
Begin
Repeat
P(mutex);
s0:=s;
s:=(s+1) mod k;
V(mutex);
P(buff[s0].empty)；
在 buff[s0].msg中写信息；
P(buff[s0].mutex)；
buff[s0].count:=n;
V(buff[s0].mutex);
For (j:=1 to n do)
V(buff[s0].full[j]);
Until false;
End
Procedure Recvr(i:integer);
{ i 为接收进程的标号 }
Var j,integer;
Begin
j:=0;
Repeat
P(buff[j].full[i]);
从 buff[j].msg中读信息；
P(buff[j].mutex)；
buff[j].count:= buff[j].count-1;
If (buff[j].count=0)
Then V(buff[j].empty)；
V(buff[j].mutex);
j:=(j+1) mod k
Until false;
End
第二类读者写者问题（写者优先）
1）共享读
2）互斥写、读写互斥
3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
进程同步和互斥（四）
Var
mutex,semaphore; {互斥信号量，初值为 1}
R,semaphore; {对应读者等待队列，初值为 0}
W,semaphore; {对应写者等待队列，初值为 0}
{一般变量,}
Writing,Boolean; {初值 false,有写者正在写 }
rc,integer; {初值 0,共享读的读者数 }
rq,integer; {初值 0,等待队列中读者数 }
wq,integer; {初值 0,等待队列中写者数 }
Begin
P(mutex);
If (Writing OR wq<>0)
Then Begin
rq:=rq+1;
V(mutex);
P(R);
P(mutex);{resume}
End;
rc:=rc+1;
V(mutex);
Read();
P(mutex);
rc:=rc-1;
If (rc=0 AND wq<>0)
Then Begin
wq:=wq-1;
Writing:=true;
V(mutex);
V(W);
End;
Else V(mutex) ;
End
读者进程
(a) 检测是否有写者并处理
(b) Inc(rc)
(c) Read()
(d) Dec(rc)
(e) 处理写者等待队列
Begin
P(mutex);
If (Writing OR rc>0)
Then Begin
wq:=wq+1;
V(mutex);
P(W);
End;
Else Begin
Writing:=true;
V(mutex);
Write();
P(mutex);
If (wq<>0)
Then Begin
wq:=wq-1;
V(mutex);
V(W);
End
Else
If (rq>0)
Then Begin
Writing:=false;
While (rq>0)
Begin
rq:=rq-1;
V(R) ;
End
End
Else Begin
Writing:=false;
V(mutex);
End
End
写者进程
(a) 检测是否有进程正在读写
(b) Writing(T); Write(); Writing(F)
(c) 处理写者等待队列 ;处理 Reader等待队列
P(s),s:=s-1;
If s<0
Then 将本进程插入相应队列 末尾 等待；
V(s),s:=s+1;
If s<=0
Then
从等待队列 队尾 取一个进程唤醒，
插入就绪队列进程同步和互斥（五）
对 P/V 操作定义作以下修改问题：
1）这样定义 P,V操作是否有问题？
不合理：先进后出；可能“无限等待”
2）用这样的 P,V操作实现 N个进程竞争使用某一共享变量的互斥机制。
思路：令等待队列中始终只有一个进程。
将,栈” 变成,队列”
Var S:array [1..n-1] of semaphore;
{ n为进程数目； S[i]初值为 i； S[n]到
S[1]的作用好象是 n 层筛子 }
Procedure Pi;
Var i:integer;
Begin
Repeat
Pre_Do_it();
For i:=n-1 Downto 1 Do
P(S[i]);
Do_It_In_Critical_Section;
For i:=1 To n-1 Do
V(S[i]);
Post_Do_it();
Until false;
End
3）对于 2）的解法，有无效率更高的方法。
如有，试问降低了多少复杂性？
上述解法每次都需要做 2n次 P/V操作，
性能低下。采用二叉树的思想，改进如下：
S[1..4]
P[1..4]
S1 S2
S3
让信号量处于不同的层次上，每个信号量至多控制两个进程（对两个进程进行同步）
P1 P2 P3 P4
Procedure P1;{ P2 is the same }
Begin
Repeat
P(S1);
P(S3);
Do_It();
V(S3);
V(S1);
Until false;
End;
Procedure P3;{ P4 is the same}
Begin
Repeat
P(S2);
P(S3);
Do_It();
V(S3);
V(S2);
Until false;
End;
不妨设有 4个进程 P1..P4，
Var S1,S2,S3,semaphore; {初值为 1}
假设共有 2N个进程争用临界区；
时间复杂性,2N vs N； 空间复杂性,2N vs 2N－ 1
理发师问题理发店里有一位理发师,一把理发椅和
N把供等候理发的顾客坐的椅子,如果没有顾客,则理发师便在理发椅上睡觉,
当一个顾客到来时,他必须先唤醒理发师,如果顾客到来时理发师正在理发，
则如果有空椅子，可坐下来等；否则离开。
进程同步和互斥（六）
顾客进程 i:
P(Sn);{门外观望 }
P(mutex);
进门；
V(mutex);
V(S);
等候；
理发；
V(Sn)
P(mutex);
出门；
V(mutex);
Var Sn,semaphore; {位子数目，初值为 n}
S,semaphore; {理发师睡觉，初值为 1}
mutex,semaphore; {初值为 1}
理发师进程,
Repeat
P(S);
P(mutex);
叫人理发；
V(mutex);
理发；
Until false;
用 P.V操作来实现 Receive原语,
Receive（ S,M）
Begin
根据 S找发送进程，
如果没找到出错返回 ;
申请缓冲区消息 P（ s-m）；
P(m-mutex);
将载有消息的缓冲区从消息链中取出 ;
V(m-mutex);
把消息从 M处 copy到 receiver的信息空间 ;
P(b-mutex);
是缓冲区为空；
V(b-mutex);
V(s-b);
End
其中 s-b初值,n ;s-m初值,0
