操作系统应用题
- 格式：pdf
- 大小：231.62 KB
- 文档页数：8
操作系统应⽤题
1.2.3设有两道程序按A，B的优先次序运⾏，其内部计算和I/O操作的时间如下：
程序A使⽤30 ms CPU后使⽤40 ms I/OA，最后使⽤20 ms CPU；
程序B使⽤60 ms CPU后使⽤20 ms I/OB，最后使⽤30 ms CPU。(1) 试画出按多道程序运⾏的时间关系图。
(2) 完成两道程序共花多少时间？它⽐单道运⾏节省多少时间？
分析：本题是关于多道程序设计的计算题。通过计算，可以更好地理解为什么要引⼊多道程序设计。
解：(1) 多道程序运⾏的并发执⾏时间关系如下图所⽰。CPU
进程A进程A结束
进程B进程B结束
图多道程序运⾏的并发执⾏时间关系图(2) 按单道程序运⾏时需花时间为：
30ms + 40ms + 20ms + 60ms +20ms + 30ms = 200ms
两道程序并发运⾏共花时间为：30ms + 40ms + 20ms + 20ms + 30ms = 140ms
所以，完成两道程序并发运⾏共花140ms，它⽐单道运⾏节省60 ms时间。3.2.2桌上有⼀个空盘，允许存放⼀个⽔果。爸爸可向盘中放苹果，也可向盘中放橘⼦，⼉⼦专等吃盘中的橘⼦，⼥⼉专等吃盘中的苹果。规定当盘空时⼀次放⼀个⽔果供吃者取⽤，请⽤P，V原语实现爸爸、⼉⼦、⼥⼉三个并发进程的同步。
分析：本题是检查对P，V原语掌握情况。本题的题意是：
①爸爸、⼉⼦、⼥⼉共⽤⼀个盘⼦，且盘中⼀次只能放⼀个⽔果。
②当盘空时，爸爸可将⼀个⽔果放⼊果盘中。
③若放⼊盘中的是橘⼦，允许⼉⼦吃，⼥⼉必须等待。
④若放⼊盘中的是苹果，允许⼥⼉吃，⼉⼦必须等待。
因此，上述问题实际上是⽣产者⼀消费者问题的⼀种变形。这⾥，⽣产者放⼊缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的⼀类产品。P(S) :
S := S – 1
若S >= 0，则进程继续运⾏
若S < 0，则进程被阻塞，并将它插⼊该信号量的等待队列中。V(S) :
S := S + 1若S > 0，则进程继续运⾏
若S <= 0，则从信号量的等待队列中移出第⼀个进程，使其变为就绪状态，然后再返回原进程继续执⾏。
解：设置三个信号量：S，初值为1，⽤于爸爸、⼉⼦、⼥⼉三个进程间的互斥，表⽰盘中是否为空。
SO ，初值为0，⽤于爸爸、⼥⼉两个进程间的同步，表⽰盘中是否有橘⼦。 SA ，初值为0，⽤于爸爸、⼉⼦两个进程间的同步，表⽰盘中是否有苹果。 三个进程之间的同步描述如下： father 进程 daughter 进程 son 进程 L1： L2： L3： P(S) P(SO)P(SA) 将⽔果放⼊盘中 从盘中取出橘⼦ 从盘中取出苹果 if (放⼊是橘⼦) V(SO) V(S) V(S) else V(SA) 吃橘⼦ 吃苹果 goto L1goto L2 goto L3
3.2.3 如下图所⽰的是⾼级通讯原语SEND 和RECEIVE 不完整的框图。请填充适当的P ，V 操作，并说明所⽤信号量的意义和初值。
发送者 申请⼀消息区
消息送消息区V(S2)
接收者
从消息链上摘下⼀消息
释放消息区3.2.7 分析下⾯信号量解决五位哲学家进餐问题的同步算法是否满⾜同步机制的准则。若不满⾜，说明为什么，并给出满⾜同步机制准则的同步算法。V AR fork;
ARRAY[0..4] OF semaphore;fork[0] := fork[1] := fork[2] := fork[3] := fork[4] := 1;
Cobegin
Pi: REPEA T /第i个哲学家的⽣活过程/
Think FOR While;
P(fork[i] ) ;
P(fork[(i+1) MOD 5] ) ;
Eat FOR WHILE;
V(foth[i]) ;
V(fork[(i+1) MOD 5] ) ;
UNTIL false
Cbend
解：当每个哲学家都只拿到⼀把⼜⼦时，上述同步算法不满⾜同步机制的准则中的“有限等待”准则，故发⽣死锁。//每次⼀个进程
⼀种改进的算法如下：V AR fork: ARRAY[0..4] of semaphore;
V AR mutex : semaphore;
fork[0] := fork[1] := fork[2] := fork[3] := fork[4] := 1;
mutex := l;
Cobegin
Pi: REPEA T /第i个哲学家的⽣活过程/
Think FOR While;
P(mutex) ;
P(fork[i] ) ;
P(fork[(i+1) MOD 5] ) ;
V(mutex) ;
Eat FOR WHILE;
V(foth[i]) ;
V(fork[(i+1) MOD 5] ) ;
UNTIL false
Cbend
应⽤题1. 设公共汽车上，司机和售票员的活动如下图所⽰。 在汽车不断地到站、停车、⾏驶过程中，这两个活动有什么同步关系？并⽤信号量的P ，V 操作实现它的同步。. S1:启动车辆与关车门 S2:开车门与下乘客 s3:开车门与上乘客
S1:启动车辆与关车门 S2:开车门与下乘客 s3:开车门与上乘客 Driver ： conductor:
Do{ P(s3) 上乘客 Do{ 关车门
P （s1）; V(s1)
启动车辆 售票 正常⾏车 P(s2) 到站停车 下乘客}while(1); 开车门 V(s2) V(s3) }while(1);
9. 假设⼀个信箱只能存放⼀封信件，只要信箱为空，进程P1就产⽣信件并送⼊信箱，只要信箱中有信件，进程P2就不断从信箱中取出信件并进⾏处理。开始时，信箱为空。试⽤P ，V 操作表达进程P1，P2之间的关系。 Empty=1; full=0;mutax=1;P1: p2: 产⽣信件
P(empty) P （full ）
司机
售票员P（mutax）p(mutax)
放⼊信件取出信件V(mutax) V(mutax)
V(full) v(empty)
10. 进程P1和P2利⽤公共缓冲池交换数据。设缓冲池有N个缓冲块，进程P1每次⽣成⼀数据块存⼊⼀空缓冲区，进程P2每次从缓冲池中取出⼀个装满数据的缓冲块。试⽤信号量及P，V操作实现进程P1和P2的同步。Mutax=1;empty=N;full=0;
P1: P2:
Do :⽣成数据块P(full)
P（empty）P(mutax)
P（mutax）取出数据块
放⼊缓冲区v(mutax)v（mutax）v(empty)
v(full) while(1)while(1);
11.有⼀银⾏家，有资⾦共10亿，有A,B,C三位顾客要贷款，A代8亿，B代3亿，C代9亿，(1)当前系统状态为：A=4,B=2,C=3,Banker=1，问此时银⾏家是否会亏本。(2)若当前状态为：A=4,B=2,C=2 ,Banker=2，若B再申请1亿的贷款，问银⾏家是否应该满⾜B的请求，为什么need alloc availableA: 8 4 1
B 3 2
C 9 3
(1) 是，银⾏家将1亿给B后，收回3亿，⽆法满⾜A和C
need alloc available
A: 8 4 2
B 3 2
C 9 2
（2）若借给B 1亿后，能收回3亿，加上剩余的共4亿，再借给A，最后借给C
系统处于安全状态，所以应该满⾜B的请求12当前系统状态如下,⽤银⾏家算法判断：
1）求系统四类资源的总数分别是多少？每个进程的need各为多少？
1):3 A:0 0 1 2
2):12 B:1 7 5 0
3):15 C:2 3 5 6
4):16 D:0 6 5 2
E:0 6 5 6
2）判断该系统当前是否处于安全状态？
安全3）如果进程C提出请求requestC(1,3,2,2)，系统能否满⾜其资源请求？
max allocation available
A B C D E
0 0 4 4
2 7 5 0
3 6 10 10
0 9 8 4
0 6 6 10
0 0 3 2
1 0 0 0
1 3 5 4
0 3 3 2
0 0 1 41 6 3 4
若满⾜的话：A B C D E
0 0 4 4
2 7 5 0
3 6 10 10
0 9 8 4
0 6 6 10
0 0 3 2
1 0 0 0
2 6 7 6
0 3 3 2
0 0 1 4
0 3 1 2
A:0 0 1 2
B:1 7 5 0
C:1 0 3 4
D:0 6 5 2
E:0 6 5 6
系统状态不安全，所以不能满⾜13设有三道程序按A，B，C的优先次序运⾏，采⽤剥夺⽅式，其内部计算和I/O操作的时间如下（A、B、C分别使⽤不同的I/O设备）：
程序A使⽤30ms CPU后使⽤30ms I/OA，最后使⽤20ms CPU；
程序B使⽤20ms CPU后使⽤20ms I/OB，最后使⽤40ms CPU。
程序C使⽤20ms CPU后使⽤20ms I/OC，最后使⽤25ms CPU。(1) 试画出按多道程序运⾏的时间关系图。
(2)完成三道程序共花多少时间？它⽐单道运⾏节省多少时间？
共花费160
节省65ms14. 有8个协作任务(A, B, C, D, E, F, G, H) 分别完成各⾃的任务。它们之间有⼀定的制约关系：任务A必须先于B, C, E；任务E和D必须先于任务F；任务B和C必须先于任务D；任务F必须先于任务G和H。请写出并⾏程序，使得在任何情况下他们都能正确的⼯作。A
B c E
D F
G H
var a, b, c, d, e, f, g, h: semaphore (初值=0)
