精选操作系统习题答案.docx

资源描述

精选操作系统习题答案.docx

《精选操作系统习题答案.docx》由会员分享，可在线阅读，更多相关《精选操作系统习题答案.docx（19页珍藏版）》请在冰点文库上搜索。

精选操作系统习题答案.docx

精选操作系统习题答案

习题一（前三章）

1、系统如何由目态转为管态？

如何由管态转为目态？

目态到管态的转换（中断，trap）：

修改处理机状态字指令属于特权指令，只能在管态执行，目态程序无法直接控制处理机状态的转换。

处理机状态由目态转换为管态的唯一途径是中断，中断发生时，中断向量中的PSW标识处于管态，这个标识一般由操作系统初始化程序设置的。

管态到目态的转换（置程序状态字）：

通过修改程序状态字（置PSW）来实现，操作系统运行于管态，该状态转换伴随着由操作系统程序到用户程序的转换。

2、为什么有硬件时钟，有时还要设置软件时钟？

解：

硬件时钟由硬件提供，保存在硬件寄存器中，开机由电源供电，关机由机内电池供电，可由程序设定和修改，一般通过特权指令完成，应用程序可读取该值。

不发生中断。

间隔时钟：

定时发生中断，一般间隔单位为“毫秒”。

中断发生后，操作系统获得系统的控制权，以便运行系统管理和实现程序并发。

是实现多道程序的基础—保证操作系统获得控制权。

软件时钟：

利用间隔时钟实现，主要用于定时启动一些服务，如定时备份，软件时钟通过赋内存的一个单元一个初值，通过间隔时钟中断，对该单元值减一，减到0就启动相应的服务，这是间隔时钟做不到的。

3、通过一个案例分析进程的状态转换过程。

比如用播放器播放音乐，当启动播放器，产生播放器进程，进入挂起就绪状态，当用户点击播放按钮时，进入就绪状态，当被处理机调度时，处于运行态，当需要听歌曲，且歌曲还在外存时，该进程启动磁盘读进程，然后自己进入等待态，当磁盘读进程将相应歌曲读进内存时，向处理机发出中断，该中断进程将播放器进程送入就绪队列，当被处理机调度时，开始播放歌曲，处于运行态，如此反复，直到关闭播放器，进程结束。

单击暂停键，进入挂起就绪队列

4、通过一个案例描述可以由用户处理的中断的处理过程。

比如在一个C语言程序中发生除零错误

（1）发生出除零中断

（2）保存旧PSW和PC（入系统栈）

（3）取中断向量

（4）转到中断处理程序

（5）访问中断续元表（假定非0）

（6）系统栈中现场转移到用户栈

（7）中断续元入口送寄存器（OS中断处理完成）

（8）执行中断续元

中断续元的执行同目态子程序

（9）用户栈PSW和PC送寄存器

（10）中断执行完，遇RET指令由用户栈弹出现场信息送入处理机

（11）返回中断断点

5、下表列出了四个进程到达时间和执行时间，使用先来先服务算法、循环（时间片2）、短作业优先、响应比高者优先的调度算法的调度过程，分别计算每个调度算法的周转时间、平均周转时间、带权周转时间、带权平均周转时间.画出相应的Gantt图．

进程

到达时间

执行时间

解：

先来先服务算法

0391315

进程

到达时间

运行时间

开始时间

完成时间

周转时间

带权周转时间

8/6=1.33

9/4=2.25

9/2=4.5

平均周转时间=（3+8+9+9）/4=7.25

平均带权周转时间=（1+1.33+2.25+4.5）/4=2.27

循环（时间片2）

024689111315

周转时间:

由就绪开始时刻到处理完毕时刻的时间

带权周转时间：

周转时间/运行时间

等待时间（waitingtime）：

周转时间与处理时间之差

进程

到达时间

运行时间

开始时间

完成时间

周转时间

等待时间

带权周转时间

9/3=3

14/6=2.33

9/4=2.25

2/2=1

平均周转时间=（9+14+9+2）/4=8.5

平均等待时间=（6+8+5+0）/4=4.75

平均带权周转时间=（3+2.33+2.25+1）/4=2.145

短作业优先

进程

到达时间

执行时间

1391115

进程

到达时间

运行时间

开始时间

完成时间

周转时间

带权周转时间

3/3=1

8/6=1.33

11/4=2.75

5/2=2.5

平均周转时间=（3+8+11+5）/4=6.75

平均带权周转时间=（1+1.33+2.75+2.5）/4=1.895

响应比高者优先

RR=1+WT/BT

在9时刻出现了D和C

C的响应比=1+5/4=2.25

D的响应比=1+3/2=2.5

1391115

进程

到达时间

运行时间

开始时间

完成时间

周转时间

带权周转时间

3/3=1

8/6=1.33

11/4=2.75

5/2=2.5

平均周转时间=（3+8+11+5）/4=6.75

平均带权周转时间=（1+1.33+2.75+2.5）/4=1.895

7、在一个使用多级反馈队列的系统中，一个只使用CPU的进程的执行时间为40秒，如果第1队列时间片为2，每级时间片增加5个时间单元，那么这个作业运行结束前会被中断多少次，结束时处于哪级队列？

解3：

进程被中断的情况有：

在时刻2（第1队列），在时刻2+7（第2队列），在时刻9+12（第3队列），在时刻21+17（第4队列），当该进程结束时位于第5队列，中断4次。

练习二互斥、同步与通信

1、设有3个进程R、W1和W2，共享缓冲区B，B中每次只能存放一个数，当B中无数据时，可以从输入设备上读数据到B中，若数为奇数时允许W1取出打印，否则允许W2取出打印，W1和W2每次仅能打印一次，它们不能从空的B中取数据。

解：

设信号量sr表示是否可读，初值为1

设信号量sp1表示w1进程是否可打印，初值为0

设信号量sp2表示w2进程是否可打印，初值为0

cobegin

sr,sp1,sp2:

semaphore:

=1,0,0;

integer;

processreaderprocessw1processw2

beginbeginbegin

repeatrepeatreapet

p（sr）;p（sp1）;p（s2p）;

读入一个数放入x;打印x1;打印x1;

ifxmod2=0thenv（sp2）v（sr）;v（sr）;

elseuntilfalse;untilfalse;

v（sp1）;end;end;

untilfalse;

end;

2、有3个好朋友预定在一个地方集合，然后一起去看电影，请用PV描述他们的同步操作。

解：

定义一个计数器，统计到达的人数：

count，初值为0

定义三个同步信号量s1，s2，s3，表示是否可以去看电影，初值都不可以看，为0

定义一个互斥信号量mutex，用于对count的互斥访问

var

count:

integer:

=0;

s1,s2,s3,mutex:

semaphore:

=0,0,0,1;

P1进程P2进程P3进程

P（mutex）p（mutex）p（mutex）

Count:

=count+1;count:

=count+1

V（mutex）;v（mutex）v（mutex）

Ifcount=3thenifcount=3thenifcount=3then

Beginbeginbegin

V（s2）;v（s1）;v（s1）;

V（s3）;v（s3）;v（s2）;

Endendend

Elseelseelse

P（s1）;p（s2）;p（s3）;

练习三互斥、同步与通信

1、两进程PA，PB通过两FIFO缓冲区队列连接（如图），每个缓冲区长度等于传送消息长度。

进程PA，PB之间的通信满足如下条件：

buf[0]

buf[1]

（1）至少有一个空缓冲区存在时，相应的发送进程才能发送一个消息。

（2）当缓冲队列中至少存在一个非空缓冲区时，相应的接收进程才能接收一个消息。

试描述发送过程send（i,m）和接收过程receive（i,m）。

这里i代表缓冲区。

解：

bufempty[0]、bufempty[1]表示缓冲区是否空，初值为n

buffull[0]、buffull[1]表示缓冲区是否满，初值为0

buf[0]、buf[1]表示两个缓冲区

Send（i,m）

Begin

localx

P（bufempty[i]）

按FIFO方式选择一个空缓冲区

buf[i]（x）=m

buf[i]（x）置满标记

V（buffull[i]）

End

Receive（i,m）

Begin

Lccalx

P（buffull[i]）

按FIFO方式选择一个装满数据的缓冲区buf[i]（x）

m=buf[i]（x）

buf[i]（x）置空标记

V（bufempty[i]）

End

Pa调用send（0,m）和receive（1,m）

Pb调用send（1,m）和receive（0,m）

2、设有三组进程PA，PB，PC，PA进程每次从磁盘中读入一条记录到缓冲区1中，缓冲区1可存放N条记录，PB进程每次只能从缓冲区1中取出一条记录到缓冲区2中，缓冲区2可存放N/2条记录，PC进程每次只能从缓冲区2中取出一条记录来打印，请用管程描述它们之间的同步操作。

解：

本题中，PA是一个生产者，PB既是生产者又是消费者，PC是消费者，

解：

条件变量：

notfull1:

表示B1是否满，notfull2：

表示B2是否满

notempty1：

表示B1是否空，notempty2：

表示B2是否空

k1,k2:

分别表示在B1中PA放记录的位置和PB取记录的位置，初值为0。

t1,t2:

分别表示在B2中PB放记录的位置和PC取记录的位置，初值为0。

count1,count2：

分别表示B1存放记录数和B2存放记录数.初值为0。

count1>=n：

表示B1已满，这时PA进程不能再读入记录到B1中，

将wait（notfull1）

count1

PA可以放1条记录到B1中，此时看是否有等待B1中记录的，

若有则将singal（notempty1）

count2>=n/2：

表示B2已满，这时PB进程不能从B1中读记录到B2中，

将wait（notfull2），当count1<=0时表示B1中无记录，PB不能

从B1中取记录，将wait（notempty1）

count20：

表示PB可以从B1中取1条记录到B2中，此时

检查是否有等待B2的记录，若有则将singal（notempty2）

count2<=0：

表示B2中无记录，PC不能打印，执行wait（notempty2）,否则从B2中取记录打印，同时检查是否有PB在等待B2中放记录，若有则执行singal（notfull2）。

过程：

get（item）：

PC从B2中取记录

put（item）：

PA从磁盘读记录到B1中。

Getput（item）：

PB从B1取记录到B2中。

TypeprocedurePC=monior

Vark1,k2,t1,t2,count1,count2:

integer

B1:

array[0…n-1]ofitem;

B2:

array[0…n/2-1]ofitem;

notfull1,notfull2,notempty1,notempty2:

condition;

procedureentryput（item）

begin

ifcount1>=nthenwait（notfull1）;

B1[k1]:

=item;

k1:

=（k1+1）modn;

count1:

=count1+1;

signal（notempty1）;

end;

procedureentrygetput（item）

begin

ifcount2>=n/2thenwait（notfull2）;

ifcount1<=0thenwait（notempty1）;

B2[t1]:

=B1[k2];

t1:

=（t1+1）modn/2;

k2:

=（k2+1）modn;

signal（notfull1）;

signal（notempty2）;

end;

procedureentryget（item）

begin

ifcount2<=0thenwait（notempty2）;

打印B2[t2];

t2:

=（t2+1）modn/2;

signal（notfull2）

end;

begin

k1=k2=t1=t1=0;

count1=-count2=0;

end;

processPAprocessPBprocessPC

beginbeginbegin

repeatrepeatrepeat

readanitem;PC.getput（item）;PC.get（item）;

PC.put（item）;untillfalse;printitem;

Untillfalse;end;untillfalse;

End;end;

练习四死锁

1、某系统采用死锁检测手段发现死锁，设系统中资源类集合为{A，B，C}，资源类A中共有17个实例，资源类B中共有5个实例，资源类C中共有20个实例．又设系统中进程集合为{p1,p2,p3,p4,p5},T0时刻系统状态如下：

Allocation Need Available

ABC ABC ABC

p1:

212 347

p2:

402 134

p3:

405 006

p4:

204 221

p5:

314 110

在T0时刻是否安全，请给出安全系列

在T0时刻若进程P2请求资源（034），能否实现分配，为什么？

在

（2）的基础上，若进程P4请求资源（201），能否实现分配，为什么？

在（3）的基础上，若进程P1请求资源（020），能否实现分配，为什么？

解：

（1）由已知可知，系统剩余资源为（233）

Allocation Need Available WorkFinish

ABC ABC ABC ABC

p1:

212 347 233

p2:

402 134

p3:

405 006

p4:

204 221

p5:

314 110

WorkAllocation Need Work+AllocationFinish

ABCABC ABC A BC

p1:

7411212 347 9513true3

p2:

9513402 134 13515true4

p3:

13515405 00617520true5

p4:

233204 221437true1

p5:

437314 1107411true2

可以找到一个系列p4,p5,p1,p2,p3

（2）在T0时刻若进程P2请求资源（034），因请求资源大于剩余资源（233），不能分配

（3）在

（2）的基础上，若进程P4请求资源（201），由于请求资源（201）<需求资源（221），

请求资源（201）<剩余资源（233），进行试分配

　　Allocation Need Available

ABC ABC ABC

p1:

212 347 032

p2:

402 134

p3:

405 006

p4:

405 020

p5:

314 110

再使用安全性检测算法，得到

WorkAllocation Need Work+AllocationFinish

ABCABC ABC A BC

p1:

7411212 347 9513true3

p2:

9513402 134 13515true4

p3:

13515405 00617520true5

p4:

032405 020437true1

p5:

437314 1107411true2

可以找到一个系列p4,p5,p1,p2,p3

（4）在（3）的基础上，若进程P1请求资源（020）,由于请求资源（020））<需求资源（347），请求资源（020））<剩余资源（032），进行试分配

Allocation Need Available

ABC ABC ABC

p1:

232 327 012

p2:

402 134

p3:

405 006

p4:

405 020

p5:

314 110

由于资源（012）不能满足任何进程故不能分配

2、有三类资源R1,R2,R3，R1和R2资源数分别为２，R3为１，有四个进程P1,P2,P3,P4，每个进程占用资源和等待资源的情况如下：

进程　　已占资源类　　　　已占用个数　　　等待的资源

P1R3,R21,1R1

P2R11-

P3R11R2

P4R21R3

请画出资源分配图，使用资源分配图的约简证明是否产生死锁。

解：

（1）该图中非孤立节点且没有请求边的是P2

（2）去掉分配边成为孤立节点

（3）寻找请求边可以满足的节点，并将请求边改为分配边

（4）没有请求边的是P1，去掉分配边成为孤立节点

（5）寻找请求边可以满足的节点，并将请求边改为分配边

（6）没有请求边的是P3,P4，去掉分配边成为孤立节点

（7）最后全部为孤立节点，系统没有死锁

3、在A、B两车站之间为单轨，且在中间有一个小站C，小站C为双轨道，给出一个无死锁、无饿死、并发度最高的算法，使用PV实现。

解：

若AB方向火车在小站C走上边轨道，BA方向走下边轨道，则：

当同时不超过3辆火车时，不会发生死锁设信号量train=3

AC、BC为单轨，设信号量ac=1bc=1

C站：

c1=1c2=1

A到BB到C

P（train）P（train）

p（ac）p（bc）

ac上行驶bc上行驶

p（c1）p（c2）

进入C小站进入C小站

v（ac）v（bc）

p（bc）p（ac）

出C站出C站

v（c1）v（c2）

bc上行驶ac上行驶

到达B站到达A站

v（bc）v（ac）

v（train）v（train）

若AB和BA方向在小站C不规定轨道，则：

当同时不超过2辆火车时，不会发生死锁设信号量train=2

AC、BC为单轨，设信号量ac=1bc=1

A到BB到C

P（train）P（train）

p（ac）p（bc）

ac上行驶bc上行驶

进入C小站进入C小站

v（ac）v（bc）

p（bc）p（ac）

出C站出C站

bc上行驶ac上行驶

到达B站到达A站

v（bc）v（ac）

v（train）v（train）

练习五存储

1、一个物理内存为64MB的计算机系统，该系统的内存管理模式为页式，页长为4KB，用户程序的一个逻辑地址为6D9C（16进制），进程页表如下

进程页表

222

126

…

请计算：

展开阅读全文