操作系统例题讲解

更新时间：2023-11-27 16:53:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

操作系统例题讲解

一、调度算法

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

进程 P1 P2 P3 P4 P5 到达时间（ms） 2 0 4 0 5 优先级 3 1 4 2 5 CPU阵发时间（ms） 3 2 3 4 2 采用可剥夺的静态最高优先数算法进行调度（不考虑系统开销）。问题： ⑴ 画出对上述5个进程调度结果的Gantt图；

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

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

P4 2

P1 4 P3 5 P5 7

P3 9 P1 10

P4 12

P2 14

(2) 时间计算：进程 P1 P2 P3 P4 P5 到达时间（ms） 2 0 4 0 5 优先级 3 1 4 2 5 运行时间（ms） 3 2 3 4 2 开始时间（ms） 2 12 4 0 5 完成时间（ms） 10 14 9 12 7 周转时间（ms） 8 14 5 12 2 带权周转时间（ms） 8/3 7 5/3 3 1 平均周转时间=(8+14+5+12+2)/5=41/5=8.2 (ms) 平均带权周转时间=(8/3+7+5/3+3+1)/5=46/15≈3.07(ms)

二、存储管理

某系统采用虚拟页式存储管理方式，页面大小为2KB，每个进程分配的页框数固定为4页。采用局部置换策略，置换算法采用改进的时钟算法，当有页面新装入内存时，页表的时钟指针指向新装入页面的下一个在内存的表项。设当前进程P的页表如下（“时钟”指针指向逻辑页面3的表项）：

逻辑页号

0 1 2 3 4 5 页框号 101H — 110H 138H — 100H 访问位r 0 1 0 1 修改位m 0 0 0 1 内外标识 1 0 1 1 0 1 问题： ⑴ 当进程P依次对逻辑地址执行下述操作：

① 引用 4C7H； ② 修改 19B4H； ③ 修改 0C9AH；写出进程P的页表内容；

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

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

- 1 -

解：页面大小为2KB，2KB=2×2=2，

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

⑴ ① 逻辑地址4C7H=0100 1100 0111B，高于11位为0，所以该地址访问逻辑页面0；

引用4C7H，页表表项0：r=1；

② 逻辑地址19B4H=0001 1001 1011 0100B，高于11位为3，所以该地址访问逻辑页面3；

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

③ 逻辑地址0C9AH=0000 1100 1001 1010B，高于11位为1，所以该地址访问逻辑页面1；

逻辑页1不在内存，发生缺页中断； ①、②两操作后，P的页表如下：

1011

逻辑页号

0 1 2 3 4 5

页框号 101H — 110H 138H — 100H 访问位r 1 1 1 1 修改位m 0 0 1 1 内外标识 1 0 1 1 0 1 按改进的时钟算法，且时钟指针指向表项3，应淘汰0页面，即把P的逻辑页面1读到内存页框101H，页表时钟指针指向表项2。并执行操作：修改 0C9AH。经上述3个操作后，P的页表如下：

逻辑页号

0 1 2 3 4 5

页框号 — 101H 110H 138H — 100H 访问位r 0 1 0 0 0 修改位m 0 1 0 1 1 内外标识 0 1 1 1 0 1 ⑵ 逻辑地址27A8H=0010 0111 1010 1000B，高于11位为4，所以该地址访问逻辑页面4；页面4不在内存，发生缺页中断；按改进的时钟算法，淘汰页面2，页面4读到110H页框，所以，逻辑地址27A8H对应的物理地址为：

0001 0001 0000 111 1010 1000B=887A8H。

三、设备与I/O管理

设系统磁盘只有一个移动磁头，磁道由外向内编号为：0、1、2、……、199；磁头移动一个磁道所需时间为1毫秒；每个磁道有 32 个扇区；磁盘转速R=7500r/min. 系统对磁盘设备的I/O请求采用N-Step Look（即N-Step Scan，但不必移动到磁道尽头），N=5。设当前磁头在60号磁道，向内移动；每个I/O请求访问磁道上的1个扇区。现系统依次接收到对磁道的I/O请求序列如下：

50, 20, 60, 30, 75, 30, 10, 65, 20, 80, 15, 70

问题：

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

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

解：⑴ 考虑序列中有重复磁道的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 -

⑵ 总寻道时间=1×155=155（ms）

一次访盘的旋转时间=1/(2R)=1/(2×7500/min)=(60×1000)/(2×7500)ms=4(ms) 请求序列共12次访盘，总旋转延迟时间=4×12=48(ms) 1次访盘的传输时间=1/(R×32)=(60×1000)/(7500×32)=1/4ms 12次访盘总传输时间=1/4×12=3(ms) 总访盘处理时间=155+48+3=206(ms)

四、文件系统

（1）给出“用户打开文件表”和“系统打开文件表”的形式，并图示二者之间的联系；（2）说明“写文件”系统调用命令write(fd,buf,count)的实现过程。解：⑴ 用户打开文件表和系统打开文件表图示如下：

文件打开描述符方式 fd1

文件打开描述符方式 fd2

（2）write(fd,buf,count)的实现过程如下：

参数含义：fd：文件描述符；count：写出记录个数；buf：内存起始位置；执行步骤：① 由fd查找用户打开文件表，找到对应的系统打开文件表入口；

② 根据用户打开文件表中所记录的打开方式和存取方式核查访问的合法性； ③ 查系统打开文件表，找到文件的地址； ④ 计算欲访问起始记录的地址； ⑤ 如果需要，申请存储块；

⑥ 将内存中由buf起始的count个记录写到文件中由当前写指针所确定的区域； ⑦ 调整用户打开文件表的读写指针。

读写指针系统打开文件表入口读写指针系统打开文件表入口 FCB主部文件号共享计数修改标志 15 系统打开文件表

2 0/1 进程P1的用户打开文件表进程P2的用户打开文件表

五、死锁问题

某系统采用死锁检测发现死锁。设系统有资源类集合为R＝｛A，B，C｝，6个进程P0、P1、P2、P3、P4、P5并发运行。当前系统状态如下：

P0 P1 P2 P3 P4 P5

A allocation

B C A request B C A available B C 1 3 0 0 2 0 0 2 1 0 1 0 0 1 2 0 0 1 0 0 2 0 0 0 0 0 0 0 3 0 0 0 2 0 1 0 2 2 1 - 3 -

问题：

⑴ 在上述状态下，系统依次接收请求：request[0]=(1,0,0)、request[1]=(2,1,0)、request[3]=(0,0,2)，

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

⑵ 在⑴所确定的状态下，系统接收请求：request[0]=(0,3,1)，说明此时已经发生死锁，并找出参与死锁的

进程。

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

系统状态变化如下：

P0 P1 P2 P3 P4 P5

A allocation

B C A request B C A available B C 2 3 0 0 2 0 0 2 1 0 1 0 0 1 2 0 0 1 0 2 2 0 0 0 0 1 0 0 3 0 0 0 2 2 1 0 1 2 1 上一状态没有死锁。

因为，用死锁检测算法，进程P5、P0、P1、P2、P3、P4能依次运行完。 ⑵ 在⑴所确定的状态下，系统接收请求：request[0]=(0,3,1)，系统状态变化如下：

P0 P1 P2 P3 P4 P5

A allocation

B C A request B C A available B C 2 3 0 0 2 0 0 2 1 0 1 0 0 1 2 0 0 1 0 2 2 0 0 0 3 1 0 0 3 0 1 0 2 2 1 0 1 2 1 对上一状态用死锁检测算法，P5、P3能完成，P0、P1、P2、P4不能完成，发生死锁，参与死锁的进程为P0、P1、P2、P4。

六、信号量与P/V操作

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

该独木桥宽度只能容纳一人，且该桥最多只能承重4人；东、西两方向过桥人只能前进、不能后退。问题：写出用信号量和PV操作实现东、西两方向行人过桥没有死锁、没有饿死的并发运行算法。要求：给出定义的各信号量和变量的含义及其初值；算法用类C伪代码描述。

西东

解：共享变量定义：

int west_crossing=0,east_crossing=0,west_wait=0,east_wait=0; semaphore wq , eq; /*初值均为0*/

semaphore mutex; /*初值均为1，用于共享变量的互斥*/ semaphore num;/*初值为4，用于限制过河人数*/

semaphore w_wait, e_wait; /*初值均为1，防止对方饿死*/

- 4 -

西面过河者算法：

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

if (east_crossing > 0) { west_wait ++ ;

if (west_wait= =1) P(e_wait);

//西边有等待，东边后续过桥者将等待 V ( mutex ) ;

P ( wq ); /*西边第一位过桥者在此等待*/ } else

{ P(num); /*过河人数超过4人则等待*/ west_crossing++; V ( mutex ); }

V(w_wait);

<上独木桥过河>; P ( mutex ) ;

west_crossing -- ;

V(num); /*过桥人数减少1人*/ if (west_crossing = = 0) { if (east_wait > 0) do

{ east_wait– –; east_crossing ++ ;

V ( eq ) ; /*唤醒东边第一位等待者*/ }

V(e_wait); /*唤醒东边后续的等待者*/ }

V ( mutex ) ; 东面过河者算法：

P(east_wait);/*后续过桥者将在此等待*/ P(mutex);

if (west_crossing > 0) {east_wait ++ ;

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

//东边有等待，西边后续过桥者将等待 V ( mutex ) ;

P ( eq ); /*东边第一位过桥者在此等待*/ } else

{ P(num); /*过河人数超过4人则等待*/ east_crossing++; V ( mutex ); }

V(east_wait);

<上独木桥过河>; P ( mutex ) ; east_crossing -- ;

V(num); /*过桥人数减少1人*/ if (east_crossing = = 0) { if (west_wait > 0) do

{ west_wait– –; west_crossing ++ ;

V ( wq ) ; /*唤醒西边第一位等待者*/ }

V(w_wait); /*唤醒西边后续的等待者*/ }

V ( mutex ) ;

七、处理机调度算法

某系统按最短剩余时间（Shortest Remaining Time First）优先算法调度CPU。已知四个进程P1、P2、P3、P4的到达时间和CPU阵发时间如下（时间单位：毫秒）：

Process P1 P2 P3 P4 问题：

⑴ 画出按最短剩余时间优先的CPU调度算法得到的进程调度结果的Gantt图； ⑵ 计算四个进程的平均等待时间、平均周转时间、平均带权周转时间。解：⑴ 按最短剩余时间优先调度算法的进程调度结果Gantt图：

P1 P2 P3 P4 P2 P1 Arrival time Burst time 0 3 4 7 10 6 3 4 0 3 4 7 11 16 23 ⑵ 四个进程的平均等待时间、平均周转时间、平均带权周转时间见下表：进程 P1 P2 P3 P4

到达时间运行时间开始时间完成时间等待时间周转时间 0 3 4 7 10 6 3 4 0 3 4 7 23 16 7 11 13 7 0 0 23 13 3 4 带权周转时间 23/10 13/6 1 1 - 5 -

平均等待时间=（13+7+0+0）/4=20/4=5 ms 平均周转时间=（23+13+3+4）/4=43/4=10.75 ms 平均带权周转时间=（23/10+13/6+1+1）/4=194/(30*4)≈1.62 ms 八、进程互斥

并发进程P0和P1关于共享变量的临界区分别为region0和region1。用软件方法解决P0和P1互斥进入其临界区的不完整的C伪代码如下：．．．

int flag[2]={0,0}; /*公共变量*/ int turn; /*公共变量*/

进程 P0：

do { flag[0]=1; turn= ① ;

while (

进程 P1：

do { flag[1]=1; turn= ②;

while ( ④ ) do continue; ； flag[1]=0; <其余代码>；

} while(1);

③ ) do continue;

； flag[0]=0; <其余代码>；

} while(1);

问题：

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

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

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

说明理由。

解：1. 完善进程： ①=1、②=0；③=flag[1]&&turn==1、④=flag[0]&&turn==0;

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

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

假设P0先执行turn=1，P1后执行turn=0，执行各自的while语句之前，turn==0，使P0的while循环条件为假、P1的while循环条件为真，所以P0不用while循环等待，直接跳出循环先进入临界区。

九、存储管理

设某计算机主存按字节编址，容量为512KB；系统采用虚拟页式存储管理方式，虚拟地址空间为4MB，页面大小为4KB，每个进程分配的页框数固定为4页。采用局部置换策略，置换算法采用改进的时钟算法（“时钟”指针初始指向第一个调入页面）。主存空闲区管理采用空闲页面表的结构，存储分配采用下次适应算法（即从上次分配下标的下一个表项开始分配）。系统对上次内存请求，分配了下标为1的空闲区中的页框后，空闲页面表如下（表中数字均为10进制）：问题：

下标 0 1 2 3 4

空闲页面表首页框号 20 35 80 95 ??. 页框个数 4 6 3 20 0 ⑴ 该计算机内存的物理地址编码是多少位？ ⑵ 当进程P初始运行，对逻辑页面的操作依次为

修改0页；引用1页；修改2页；修改3页

写出进程P的页表内容，页表表项为：（逻辑页号、页框号、访问位r、修改位m）；

⑶ 在⑵的基础上，当P依次对逻辑地址97B0H和逻辑地址0B7B0H均进行修改访问时，这两个逻辑地址

访问的逻辑页号和物理地址各是多少？

- 6 -

解：⑴该计算机主存容量为512KB=29×2bytes＝2，

所以该机内存物理地址编码为19位；

⑵当进程P初始运行，访问的逻辑页面依次为：修改0、引用1、修改2、修改3时，

按下次适应算法应该从下标为2的空闲区开始依次分配，进程P的页表如下：

1019

逻辑页号 0 1 2 3 页框号（十进制） 80 95 20 35 访问位r 1 1 1 1 修改位m 1 0 1 1 ⑶逻辑地址97B0H=00,0000,1001,0111,1011,0000B；（4MB＝222bytes，故逻辑地址为22位）因为页面大小为4KB=212bytes，所以地址的低12位为页内偏移，高于12位的部分为逻辑页号。所以逻辑地址97B0H访问的逻辑页号为9，该逻辑页未调入内存，发生缺页；

由于固定分配4个页框，且已分配了4个页框，按局部置换的修改的时钟算法置换，时钟指针应从逻辑页号0的表项开始，9号逻辑页置换的逻辑页为1，其页框为95号页框；95=5FH，所以逻辑地址97B0H访问的19位物理地址为101,1111,0111,1011,0000B =5F7B0H 此时页表的第二项为：（9,95,1,1）

逻辑地址0B7B0H=00,0000,1011,0111,1011,0000B；

所以逻辑地址0B7B0H访问的逻辑页号为11，该页未调入内存，发生缺页；

采用局部置换改进的时钟算法，并考虑上次置换时清过的访问位，应置换逻辑页面2，由于逻辑页面2分配的是20号页框，20=14H，

所以逻辑地址0B7B0H访问的20位物理地址为001,0100,0111,1011,0000B =147B0H

十、文件系统

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

…

Int pid1,pid2; Int fd[2]; Char buf[50]; Pipe(fd);

If((Pid1=fork())==0)

{ close(fd[1]]; /* 关闭写端 */ read(fd[0],buf,6); sleep(100); exit(1); }

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

{ close(fd[0]); /* 关闭读端 */ write(fd[1],”Hello”,6); sleep(100); exit(2); }

close(fd[0]); close(fd[1]); …

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

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

进程P和写子进程pid2的buf值不确定，pid1读子进程的buf[]={‘H’,‘e’,’l’,’l’,’o’,’\\0’ };

- 7 -

fd[0] ?? fd[1] ?? ?? -1 ?? -1 ?? ? ?? ? i f_flag＝Rpipe f_count=1 ?? f_inode=k f_offset=6 k ?? ? ?? i_count=2 b “Hello” ?? j f_flag＝Wpipe i_addr[0]=b f_count=1 i_addr[1～7]=null f_inode=k ?? f_offset=6 磁盘块 ? ?? ? ?? 内存file表 P的U_ofile Fd[0] ??] Fd[1] ?? ?? i ?? -1 ?? Pid1的U_ofile Fd[0] ?? Fd[1] ?? ?? -1 ?? j ?? Pid2的U_ofile

十一、设备与I/O管理

inode表199 ；磁头移动一个磁道所需时设系统磁盘只有一个移动磁头，磁道由外向内编号为：0、1内存、2、……、间为1毫秒；每个磁道有 32 个扇区；磁盘转速R=6000r/min. 系统对磁盘设备的I/O请求采用N-Step Look（即N-Step Scan，但不必移动到磁道尽头），N=4。设当前磁头在50号磁道，向内移动。现有对磁道的I/O请求序列：12, 24, 7, 60, 30, 77, 5, 26, 61, 80, 53, 66；每个I/O请求访问磁道上的1个扇区。问题：

⑶ 写出给定磁道的I/O请求序列的调度序列，并计算磁头的移动量；

⑷ 对给定I/O请求序列，计算：总寻道时间（启动时间忽略）、总旋转延迟时间、总传输时间和总访问

处理时间。

解：⑴调度序列为（不包括括号内的磁道）：

(50)→60→24→12→7→5→26→30→77→80→66→61→53 磁头移动量=(60-50)+(60-24)+(24-12)+(12-7)+(7-5)+(26-5)

+(30-26)+(77-30)+(80-77)+(80-66)+(66-61)+(61-53) =10+36+12+5+2+21+4+47+3+14+5+8=167（磁道）

⑵总寻道时间=1×167=167（ms）

一次访盘的旋转时间=1/(2R)=1/(2×6000/min)=(60×1000)/(2×6000)ms=5(ms) 请求序列共12次访盘，总旋转延迟时间=5×12=60(ms)

1次访盘的传输时间=1/(R×32)=(60×1000)/(6000×32)=5/16(ms) 12次访盘总传输时间=5/16×12=3.75(ms) 总访盘处理时间=167+60+3.75=230.75(ms)

十二、死锁问题

设系统有资源集合为R＝｛A，B，C｝，5个进程P0、P1、P2、P3、P4并发运行。按银行家算法，当前系统状态如下：

- 8 -

P0 P1 P2 P3 P4

问题： ⑴ ⑵ ⑶ ⑷

系统中各类资源总量是多少？矩阵Need的值是多少？判断当前系统状态是否安全？

在当前状态下，如果进程P0提出资源请求request[0]=(1,0,0)，系统能否实施分配？说明原因。 ⑵矩阵need的值如下：

Need A B C A Claim B C A Allocation

B C A Available B C 5 4 6 3 4 5 3 5 2 4 4 2 2 2 3 0 2 1 2 0 1 2 0 1 0 0 1 1 1 2 2 1 1 解：⑴系统各类资源总量（A，B，C）=（7，5，6）；

5 2 5 1 4

4 1 5 1 4 4 1 1 1 1 ⑶在当前系统状态下，可找到进程安全状态序列：，所以当前系统状态是安全状态；

⑷ 在当前系统状态下，进程P0提出资源请求request[0]=(1,0,0)，

系统预分配后的状态如下： P0 P1 P2 P3 P4

A Claim B C A Allocation

B C A Need B C A Avaiable

B C 5 4 6 3 4 5 3 5 2 4 4 2 2 2 3 1 2 1 2 0 1 2 0 1 0 0 1 1 1 2 4 2 5 1 4 4 1 5 1 4 4 1 1 1 1 1 1 1 该系统状态可找到进程安全序列：，所以系统能满足该请求。

十三、信号量与P/V操作

侏罗纪公园内有一个恐龙博物馆和一个花园，游客先步行参观恐龙博物馆，然后乘游览车游览花园。设共有n辆游览车（有司机），每辆游览车一次只能搭载一位游客。试用信号量和PV操作实现游客和游览车之间的同步。要求：（1）给出信号灯及其它变量的定义；（2）分别给出游客和游览车的活动。解：设游客与游览车的进程分别为tourist和car；信号量定义及算法如下：

Int car_status[n]; /*初值为均为0，car_status[i]表示i号车的状态，0空闲，1占用。*/ semphore car_wait[n]; /*初值均为0，用于游客与i号车的上车、启动的同步。*/

- 9 -

semphore car_stop[n]; /*初值均为0，用于游客与i号车的下车、停车的同步。*/ semphore down[n]; /*初值均为0，用于游客下车与i号车空闲的同步。*/ semaphore S; /*初值为n，用于n辆游览车的管理；*/ semaphore mutex; //初值为1，用于修改车状态的互斥；

void tourist( )

<参观博物馆>； {

P(S); /*有空闲游览车？*/ P(mutex);

在car_status中找一空闲车i； car_status[1]=1; V(mutex);

上i号游览车；

V(car_wait[i])；/*游客已上车*/ 游览花园；

P(car_stop[i]); /*停车了？*/ 下i号游览车；

V(down[i]); /*游客已下车*/ }

void car( int i)

{ do {

P(car_wait[i]); /*游客上车？*/ 启动、行驶（顾客游览）；停车；

V(car_stop[i]); /*通知游客已停车*/ P(down[i]); /*游客下车？*/ P(mutex);