操作系统期末复习资料教学内容

R进程 C进程 P进程

输入信息写入缓冲区B1 P(B1full) P(B2full)

V(B1full) 从B1中取出信息 从B2中取出信息进行打印 P(B1empty) 加工信息 V(B2empty) 结果送入B2 V(B1empty) V(B2full) P(B2empty)

解：（1）系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。

（2）信号量含义及初值：

B1full：表示缓冲区B1满，初值为0。 B1empty：表示缓冲区B1空，初值为0。 B2full：表示缓冲区B2满，初值为0。 B2empty：表示缓冲区B2空，初值为0。

145. 假定在单CPU条件下有下列要执行的作业，如下表所示。作业到来的时间是按作业编

号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。

① 用一个执行时间图描述在采用非抢占式优先级算法时这些作业的执行情况。（注：优先级数值大的作业其优先级高）

② 针对上面算法，计算作业的周转时间、平均周转时间、带权周转时间和平均带权周转时间。

作业 1 2 3 4 5 运行时间 10 1 2 1 5 优先级 3 1 3 4 2 解：① 非抢占式优先级的执行时间图，如下图所示。 作业1 作业4 作业3 作业5 作业2

0 10 11 13 18 19 t ② 计算过程如下表所示。

作业 到达时间 运行时间 完成时间 周转时间 带权周转时间 1 2 3 4 5 0 1 2 3 4 10 1 2 1 5 10 19 13 11 18 10 18 11 8 14 12.2 7.06 1.0 18.0 5.5 8.0 2.8 平均周转时间 平均带权周转时间

146. 某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻

一位用户的页表中，已调入内存页面的页号和物理块号的对照表如下：

页号 0 1 2 3 物理块号 5 10 4 7 请计算逻辑地址0A5C(H)所对应的物理地址（要求写出分析过程）。 解：

页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知页内地址占10位。由“内存为16KB”，可知有16块，块号为4位。

逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的分析，下划线部分为页内地址，编码“000 10”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00 ，拼接块内地址10 0101 1100，得物理地址为01 0010 0101 1100，即125C（H）。

147. 考虑下面存储访问序列，该程序大小为460字：

10，11, 104, 170, 73, 309, 185, 245, 246, 434, 458, 364

设页面大小是100字，请给出该访问序列的页面走向。又设该程序基本可用内存是200字，如果采用先进先出置换算法( FIFO)和最佳置换算法（OPT），求其缺页率。（注：缺页率=缺页次数/访问页面总数，要求给出计算过程）

解：根据已知条件页面大小是100字，将页面访问序列简化：0,0,1,1,0,3,1,2,2,4,4,3

又因为该程序基本可用内存是200字，可知内存块数为2。

采用先进先出置换算法( FIFO)，总共有6次缺页，缺页率为6/12=50%，具体算法如下：

页面走向 块1 块2 缺页 0 0 缺 0 1 0 1 缺 1 0 3 3 1 缺 1 2 3 2 缺 2 4 4 2 缺 4 3 4 3 缺 采用最佳置换算法（OPT），总共有5次缺页，缺页率为5/12=41.6%，具体算法如下所示：

页面走向 块1 块2 缺页

148. 考虑下述页面走向：

1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6

当内存块数量为3时，试问最近最少使用置换算法(LRU)的缺页次数是多少？（注意，所有内存块最初都是空的，所以凡第一次用到的页面都产生一次缺页。并给出解题过程。）

解： 使用最近最少使用置换算法LRU，内存块为3，共产生缺页中断15次。 页面 块1 块2 块3 1 1 2 1 2 3 1 2 3 4 4 2 3 2 1 4 2 1 5 5 2 1 6 5 6 1 2 5 6 2 1 1 6 2 2 3 1 3 2 7 7 3 2 6 7 3 6 3 2 2 3 6 1 2 3 1 2 3 6 2 3 6 缺 0 0 缺 0

1 0 1 缺 1 0

3 3 1 缺 1

2 3 2 缺 2

4 3 4 缺 4 3

缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺 149. 设Linux文件系统中的目录结构如下图所示：

(1) Linux的文件系统采用的是哪一种目录结构？有什么优点？

(2)设当前工作目录是/usr，那么，访问文件m1.c的绝对路径名和相对路径名各是什么？ (3)现在想把工作目录改到liu，应使用什么命令（写出完整命令行）?

(4)如果用ls –l /usr/mengqc/mub1命令列出指定目录的内容，其中有如下所示的一项： - r w - r - - - - - 2 mengqc group 198 Jun 23 2013 m2.c

那么，该文件m2.c对文件主、同组用户、其他用户分别规定了什么权限？ 解：

(1) UNIX的文件系统采用的是带链接的树形目录结构，即非循环图目录结构。其优点是易于实现文件共享。

(2) 访问文件m1.c的绝对路径名是： /usr/mengqc/mub1/m1.c 访问文件m1.c的相对路径名是： mengqc/mub1/m1.c (3) cd /usr/liu 或者cd liu

(4) 文件主权限是可读、可写，但不可执行；同组用户权限是只可读：其他用户权限是无，即不能读、写成执行。