操作系统例题讲解

操作系统例题讲解

一、调度算法

对如下表所示的5个进程:

进程到达时间(ms)优先级CPU阵发时间(ms)

P1233

P2012

P3443

P4024

P5552

采用可剥夺的静态最高优先数算法进行调度(不考虑系统开销)。

问题：⑴画出对上述5个进程调度结果的Gantt图：

⑵计算5个进程的平均周转时间、平均带权周转时间。

解：⑴调度结果的Gantt图如下：

P4PIP3P5P3PlP4P2

024579101214

⑵时间计算：

到达时间运行时间开始时间完成时间周转时间带权周转

*程优先级

(ma)(ma)(ma)(me)(me)Rt1H1(me)

Pl23321088/3

P201212K147

P34434955/3

P4024012123

P55525721

平均周转时间=(8+14+5+12+2)/5=41/5=8.2(ms)

平均带权周转时间=(8/3+7+5/3+3+1)/5=46/1507(ms)

二、存储管理

某系统采用虚拟页式存储管理方式，页面大小为2KB,每个进程分配的页框数固定为4页。采用周部置

换策略，置换算法采用改进的时钟算法，当有页面新装入内存时，页表的时钟指针指向新装入页面的下•个

在内存的表项。设当前进程P的页表如下(“时钟”指针指向逻辑页面3的表项)：____________________

页框号访问位r修改位m内外标识

101H001

—0

110H101

138H001

——0

100H111

问题：⑴当进程P依次对逻辑地址执行下述操作：

①引用4C7H：②修改19B4H：③修改0C9AH：

写出进程P的页表内容：

⑵在⑴的基础上，当P对逻辑地址27A8H进行访问，

该逻辑地址对应的物理地址是多少？

页面大小为2KB,2KB=2X2>o=2»,

即逻辑地址和物理地址的地址编码的低11位为页内偏移；

⑴①逻辑地址4c7H=01001100(HUB,高于11位为0,所以该地址访问逻辑页面0；

引用4C7H,页表表项0：r=l；

②逻辑地址19B4H=00011001101101(H)B,高于11位为3,所以该地址访问逻辑页面3：

修改19B4H,页表表项3：r=I.m=1;

③逻辑地址0C9AH=0000110010011010B,高于11位为I,所以该地址访问逻辑页面1:

逻辑页1不在内存，发生玦页中断：

①、②两操作后，P的页表如下：

逻辑页号页框号访问位r修改位m内外标识

0101H101

1—0

2110H101

—►3138H111

4——0

5100H111

按改进的时钟算法，且时钟指针指向表项3,应淘汰0页面，

即把P的逻辑页面1读到内存页框101H,页表时钟指针指向表项2»

并执行操作：修改0C9AH,

经上述3个操作后，P的页表如下：

逻辑页号页框号访问位r修改位m内外标识

0—000

1I01H111

♦2110H001

3I38H011

4—0

5100H011

<2)逻辑地址27A8H=0010011110101000B,高于11位为4,所以该地址访问逻辑页面4：

页面4不在内存，发生缺页中断；按改进的时钟算法，淘汰页面2,页面4读到1IOII页框，

所以，逻辑地址27A8H对应的物理地址为：

00010001000011110101000B=887A8H.

三、设备与"0管理

设系统磁盘只有一个移动磁头，磁道由外向内编号为：0、1、2、……、199：磁头移动一个磁道所需时

间为1毫秒；每个磁道有32个扇区；磁盘转速R=7500r/min.系统对磁盘设备的I/O请求采用N-StepLook

(即N-StepScan,但不必移动到磁道尽头)，N=5。设当前磁头在60号磁道，向内移动：每个I/O请求访问

遨道上的1个扇区。现系统依次接收到对磁道的I/O请求序列如下：

50,20,60.30,75,30.10,65,20,80,15,70

问题：

(1)写出对上述I/O请求序列的调度序列，并计算磁头引臂的移动量：

(2)计算：总寻道时间(启动时间忽略)、总旋转延迟时间、总传输时间和总访问处理时间。

解：⑴考虑序列中有重复磁道的I/O请求，调度序列为：

60-75—50-30-20-15-10-65-70-80

磁头移动—=(75-60)+(75-50)+(50-30)+(30-20)+

(20-15)+(15-10)+(65-10)+(70-65)+(80-70)

=15+25+20+10+5+5+55+5+10=155(磁道)

(2)总寻道时间=1X155=155(ms)

一次访盘的旋转时间=l/(2R)=l/(2X7500/min)=(60X1000)/(2X7500)ms=4(ms)

请求序列共12次访盘，总旋转延迟时间=4XI2=48(ms)

1次访盘的传输时间=l/(RX32)=(60X1000)/(7500X32)=l/4ms

12次访盘总传输时间=1/4X12=3(ms)

总访盘处理时间=155+48+3=206(ms)

四、文件系统

(1)给出“用户打开文件表”和“系统打开文件表”的形式，并图示二者之间的联系:

(2)说明“写文件”系统调用命令write(fd.buf.count)的实现过程。

解：⑴用户打开文件表和系统打开文件表图示如下：

FCB主部文件号共享计数修改标志

1520/1

系统打开文件表

(2)write(fd,buf,count)的实现过程如下:

参数含义：fd：文件描述符：count：写出记录个数：buf：内存起始位置：

执行步骤：①由fd查找用户打开文件表，找到对应的系统打开文件表入口；

②根据用户打开文件表中所记录的打开方式和存取方式核查访问的合法性；

③查系统打开文件表，找到文件的地址；

④计算欲访问起蛤记录的地址：

⑤如果需要，申清存储块：

⑥将内存中由buf起始的811nl个记录写到文件中由当前写指针所确定的区域：

⑦调整用户打开文件表的读写指针。

五、死锁问题

某系统采用死锁检测发现死锁。设系统有资源类集合为R={A,B,C),6个进程PO、Pl、P2、P3、P4、

P5并发运行。当前系统状态如下：

allocationreauestavailabe

ABcABCABc

P0100000221

P1321000

P2012202

P3000000

P4210031

P5001000

问题：

⑴任上述状态下，系统依次接收请求:request⑼=(1,。仞、request11j=(2.1.0)requestL3]=(U,U,2)»

给出系统状态变化情况，并说明没有死锁。

⑵在⑴所确定的状态下，系统接收请求：request|01=(0,3J)»说明此时己经发生死锁，并找出参与死钱的

进程。

解：(1)在上述情况下，系统依次接收请求：request(OJ=(1.0.0)request[I]=(2,1.0)、request[3]=(0.0,2),

系统状态变化如下：

allocationrequestavaiiabc

ABCABCABc

P0200000121

Pl321210

P2012202

P3000002

P4210031

P5001000

上一状态没有死锁。

因为，用死锁检测算法，进程P5、P0、P1、P2、P3,P4能依次运行完。

⑵在⑴所确定的状态下，系统接收请求：request[0J=(0,3J),系统状态变化如下：

allocationrequestavaiiabe

ABCABCABc

P0200031121

Pl321210

P2012202

P3000002

P4210031

P5001000

对上一状态用死锁检测算法，P5、P3能完成，P0,Pl、P2、P4不能完成,

发生死锁,参与死锁的进程为P0、Pl、P2、P4。

六、信号量与P/V操作

•南北流向的小河上有•座独木桥，如下图所示:

该独木桥宽度只能容纳•人，且该桥最多只能承重4人：东、西两方向过桥人只能前进、不能后退。

问题：写出用信号量和PV操作实现东、西两方向行人过桥没有死锁、没有饿死的并发运行算法。

要求：给出定义的各信号量和变量的含义及其初值：算法用类C伪代码描述。

解：共享变量定义：

intwest_crossing=0,east_crossing=0,west_wait=0,east_wait=0;

semaphorewq,eq;/*初值均为0*/

semaphoremutex;/*初值均为1,用广共享变量的互斥*/

semaphorenum;/*初值为4,用于限制过河人数*/

semaphorewwait,ewait;/*初值均为1,防止对方饿死*/

西面过河者算法：东面过河者算法：

P(w_wait);/*后续过桥者将在此等待刊P(cast_wait);/*后续过桥者将在此等待*/

P(mutex);P(mutex);

if(east_crossing>0)if(west_crossing>0)

{west_wait++;{east_wait++;

if(west_wail==1)P(e_wait);if(east_wait==1)P(w_wait);

〃西边有等待，东边后续过桥者将等待〃东边有等待，西边后续过桥者将等待

七、进程互斥

并发进程P0和P1关于共享变量的临界区分别为region。和regionI。用软件方法解决P0和PI互斥进入其

临界区的不.宛鹫的C伪代码如下：

intflag[2]={0,0};/*公共变量*/

intturn:/*公共变量*/

进程PO：进程P1：

do{flagll]=l;tum=②：

do{flag[O]=l;tum=①；

while(③1)docontinue;while()docontinue;

<rej»ionO>：<regionl>；

flag|O]=O:flag[1]=0;

〈其余代码〉;(其余代码〉；

}while(l);}while(l);

问题：

1.在①、②处分别填上正确的数：在③、④处分别填上正确的C表达式，使PO、P1满足临界区管理的互

斥性、进展性、有限等待性原则；

2.当P0和P1两进程都要进入临界区，并分别执行完各自有关lum的赋值语句后，哪个进程先进入临界区？

说明理由。

解：I.完善进程：①=1、②=0：l^)=flag[1]&&turn==I、@=flagfO]&&turn==O;

2.当PO和Pl两进程都要进入临界区，并分别执行完①、②处的有关turn的赋值语句后，哪个进程先

执行完〔urn的赋值语句，哪个进程就先进入临界区。理由如下：

假设P0先执行tum=l,Pl后执行tum=0,执行各自的while语句之前，tum==0,使P0的while循

环条件为假、P1的while循环条件为真，所以P0不用while循环等待，直接跳出循环先进入临界区。

八、文件系统

在UNIX系统中，进程P部分程序如下：

Intpidl,pid2;

Intfd⑵；

Charbuf|50];

Pipe(fd);

If((Pidl=fork())==0)

{close(fd[l]];/*关闭写端*/

read(fd[0],buf,6);

slccp(IOO);

exit(l);

I

If((pid2=fork())==0)

jclose(fd[0]);/*关闭读端*/

write(fd[1],,,Hello,\6)

sleep(lOO);

exit(2);

I

close(fd(0]);

close(fd[l]);

画图说明上述程序在exit执行前，系统中u_oflle表、file表、inode表的主要内容及表之间的联系情况，以及buf

的内容。

解：给定程序在执行exit前，各表主要内容及各表之间的关系如下图所示。

进程P和写子进程pid2的buf值不确定,pidl读子进程的buf[]={'H\£T,T,QJ0'};

“Helle”

磁盘块

九、死锁问题

设系统有资源集合为R={A,B,C},5个进程PO、PH的存囹发运行。按银行家算法，当前

系统状态如下：

P3322211

P4443002

问题：

（1）系统中各类资源总量是多少？

（2）矩阵Need的值是多少？

⑶判断当前系统状态是否安全？

（4）在当前状态下，如果进程P0提出资源请求request（O]=（lAO）,系统能否实施分配？说明原因。

解:⑴系统各类资源总量（A,B,C）=（7,5,6）:

⑵矩阵need的值如下：

Need

ABC

544

211

551

111

441

⑶在当前系统状态下，可找到进程安全状态序列：<P1,P3,P4,P0,P2>,

所以当前系统状态是安全状态；

（4）在当前系统状态下，进程P0提出资源请求request[0]=（l,0,0）,

系统预分配后的状态如下：

ClaimAllocationNeedAvaiable

ABCABCABCABC

554110444111

432221211

652101551

322211111

443002441

该系统状态可找到进程安全序列：<P3,P1,P4,PO,P2>,所以系统能满足该请求。

操作系统全真试题一及答案

一、单项选择题（每小题1分，共15分）

1.操作系统是一种（）

管理采用了（）

管理管理管理管理

工用户程序在目态下使用特权指令将引起的中断是属于（）

A.硬件故障中断B.程序中断C.外部中断D.访管中断

4.MS-DOS中用于软盘整盘复制的命令是（）

A.COMPB.DISKCOPYC.SYSD.BACKUP

5.位示图方法可用于（）

管理管理中的页面调度

6.下列算法中用于磁盘移臂调度的是（）

A.时间片轮转法B.LRU算法C.最短寻找时间优先算法D.优先级高者优先算

法

管理方案中，不适用于多道程序设计系统的是（）

管理

8.已知，作业的周转时间=作业完成时间一作业的到达时问。现有三个同时到达的作业J1,

J2和J3,它们的执行时间分别是Tl,T2和T3,且TKT2仃它系统按单道方式运行且采用短作

业优先算法，则平均周转时间是（）

A.T1+T2+T3B.（T1+T2+T3）C.T1+T2+T3D.T1+T2+T3

9.任何两个并发进程之间（）

10.进程从运行状态进入就绪状态的原因可能是（）

11.用磁带作为文件存贮介质时，文件只能组织成（）

12.一作业8：00到达系统，估计运行时间为1小时，若10：00开始执行该作业，其响应比

是（）

13.多道程序设计是指（）

14.文件系统采用多级目录结构后，对于不同用户的文件，其文件名（）

15.在可变式分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并,

为此需修改空闲区表，造成空闲区数减1的情况是（）

A.无上邻空闲区，也无下邻空闲区B.有上邻空闲区，但无下邻空闲区C.

有下邻空闲区，但无上邻空闲区D.有上邻空闲区，也有下邻空闲区

二、双项选择题（每小题2分，共16分）

1.能影响中断响应次序的技术是（）和（）。

2.文件的二级目录结构由（）和（）组成。

3.驱动调度算法中（）和（）算法可能会随时改变移动臂的运动方向。

管理概念的下列叙述中，（）和（）是不正确的。

A.通道是处理输入、输出的软件

管理负责处理

5.一进程刚获得三个主存块的使用权，若该进程访问页而的次序是｛1321215123｝。当采用先

进先出调度算法时，发生缺页次数是（）次，而采用LRU算法时，缺页数是（）次。

6.作业与进程的主要区别是（）和（晨

A.前者是由用户提交，后者是由系统自动生成

C.前者以用户任务为单位，后者是操作系统控制的单位D.

前者是批处理的，后者是分时的

E.后者可并发执行，前者则不行

7.下述MS-DOS的文件中（）和（）是有关设备管理的程序。

8.MS-DOS的文件类型为（）和（）的文件是不可执行的。

A..OBJB..EXEC..COMD..BAKE..BAT

三、填空题（每空1分，共15分）

1.用户程序使用请求操作系统服务。

管理应实现的功能是：主存空间的分配与保护，，主存空间的共享和。

管理中，页表是用来指出作业的与的对应关系。

4.每个索引文件都至少有一张索引表，其中的每一个表项应包括能标识该记录的

和该记录的。

5.分时系统必须为用户提供以实现控制方式。

6.斯普林系统中，作业执行时，从磁盘上的中读取信息，并把作业的执行结果暂

时存放在磁盘上的中。

7.并发进程中涉及到的程序段称为临界区，两个进程同时进入相关的临界区会造

成一的错误。

8.MS-DOS中有三个文件:DOSIP.EXE,DOSIP.DAT和DOSZP.C个,若使用系统提供的替代符'

*'和'？'，则这三个文件可统一表示为。

9.拼音码是一种汉字码。

四、改错题（每小题2分，共10分）

1.以批处理方式和交耳方式控制作业运行都需要注册（LOGON）o

2.分时系统中，时间片越小越好。

3.银行家算法是防止死锁发生的方法之一。

4.若无进程处于运行状态，则就绪队列和等待队列均为空。

5.作业控制语言是供用户编写程序以实现某项计算任务。

五、简答题（每小题4分，共20分）

1.程序状态字包含哪些主要内容？

2.什么是记录的成组和分解？

3.进程间同步和互斥的含义是什么？

4.什么是输入输出操作？什么是通道？

5.为实现分页式虚拟存贮，页表中至少应含有哪些内容？

六、综合题（每小题8分，共24分）

1.假定在某移动臂磁盘上，刚刚处理了访问75号柱面的请求，目前正在80号柱面读信息，

并且有下述请求序列等待访问磁盘：

试用：（1）电悌调度算法

(2)最短寻找时间优先算法

分别列出实际处理上述请求的次序。

2.有三个进程PLP2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2：

进程P3需用资源S2和S3。回答：

(1)若对资源分配不加限制，会发生什么情况?为什么？

(2)为保证进程正确工作，应采用怎样的资源分配策略?为什么？

3.某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，

则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问

题：

(1)用PV操作管理这些并发进程时，应怎样定义信号量：写出信号量的初值以及信号量各种

取值的含义。

(2)根据所定义的信号黄，把应执行的PV操作填入下述方框中，以保证进程能够正确地并发

执行。

COBEGINPROCESSPI(1=1,2,……)

begin；

进入售票厅：

购票；

退出：

end：

COEND

⑶若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。

答案

一、单项选择题(每题I分,共15分)

1.(1)2.(3)3.(2)4.(2)5.(1)6.(3)7.(1)8.(3)