高等学校 操作系统课程庐山研讨班 北京大学信息学院 陈向群 2005，07

Presentation on theme: "高等学校 操作系统课程庐山研讨班 北京大学信息学院 陈向群 2005，07"— Presentation transcript:

1 高等学校 操作系统课程庐山研讨班 北京大学信息学院 陈向群 2005，07
高等学校 操作系统课程庐山研讨班 北京大学信息学院 陈向群 2005，07

2 操作系统课程暑期研讨班 第五单元 OS课程习题、小测验、考试与小论文设计

3 习题设计与安排 课程形式 主课、习题课、专题课、课堂讨论 作业、小论文、源代码分析、上机实习 考试：笔试 小考试（3次） 期末考试

4 常见题型 选择题（单选题、多选题） 填空题 判断题 简答题（问答题） √ 应用题 √ 综合题 √ Liunx源代码题 √
Windows实习题 √ P、V操作题 √

5 应用题-1 作业管理 进程管理 存储管理 作业调度算法应用（单道、多道） 进程调度算法应用 可变分区存储管理方案
空闲区分配与回收、移动技术应用 页式存储管理方案（页表构成、页面分配回收） 虚拟页式存储管理方案 页面置换算法应用（FIFO、LRU、OPT）

6 应用题-2 文件管理 死锁 文件目录检索、改善 文件的物理结构 记录的成组和分解 磁盘空间管理 文件系统可靠性
文件系统性能（磁盘调度[移臂调度、旋转调度]，信息的优化分布） 死锁 银行家算法应用 死锁检测 资源分配图

7 1、单道批处理方式下的作业调度 - 1 假设有三个作业，它们的进入时间及估计运行时间如下： 作业号 进入时刻 估计运行时间
作业号 进入时刻 估计运行时间 ： 分钟 ： 分钟 ： 分钟 在单道批处理方式下，采用先来先服务算法和最短作业优先算法进行作业调度。请给出它们的调度顺序，并分别计算出作业平均周转时间和带权平均周转时间。请对计算结果进行解释。

8 1、单道批处理方式下的作业调度 - 2 答案：先来先服务算法 平均周转时间：93.33分钟 平均带权周转时间：3.39 1 10：00
作业号 进入时间 执行时间 开始时间 完成时间 周转时间 带权周转时间 1 10：00 60分钟 11：00 1.0 2 10：10 12：00 110分钟 11/6 3 10：25 15分钟 12：15 110/15 平均周转时间：93.33分钟 平均带权周转时间：3.39

9 1、单道批处理方式下的作业调度 - 3 最短作业优先算法 调度顺序：1，3，2 平均周转时间：78.33分钟 平均带权周转时间：2.14
作业号 进入时间 执行时间 开始时间 完成时间 周转时间 带权周转时间 1 10：00 60分钟 11：00 1.0 2 10：10 11：15 12：15 125分钟 25/12 3 10：25 15分钟 50分钟 10/3 调度顺序：1，3，2 平均周转时间：78.33分钟 平均带权周转时间：2.14

10 2、两道批处理方式下的作业调度 - 1 有一个两道的批处理操作系统，作业调度采用最短作业优先的调度算法，进程调度采用基于优先数的抢占式调度算法，有如下的作业序列： 作业 进入时间 估计运行时间 优先数 JOB ： 分钟 JOB ： 分钟 JOB ： 分钟 JOB ： 分钟 其中，优先数数值越小优先级越高。 （1）列出所有作业进入内存时间及运行结束时间； （2）计算作业平均周转时间和带权平均周转时间。

11 2、两道批处理方式下的作业调度 - 2 答案： 两道批处理作业，作业调度采用最短作业优先，进程调度采用基于优先级的抢占式调度同时允许两个程序存在于主存中 进入内存 运行时间段 周转时间 Job1 10:00 10:00-10:20 10:50-11:10 70 Job2 10:20 10:20-10:50 30 Job3 11:10 11:10-12:00 90 Job4 10:50 12:00-12:20 平均周转时间： ( )/4=70 带权平均周转时间： (70/40+30/30+90/50+90/20)/4=2.26

12 3、多道批处理方式下的作业调度 - 1 某系统采用不能移动已在内存储器中作业的可变分区方式管理内存储器，现有供用户使用的内存空间100K，系统配有4台磁带机，有一批作业如下： 作业 进入时间 估计运行时间 内存需要 磁带机需要 JOB ： 分钟 K 台 JOB ： 分钟 K 台 JOB ： 分钟 K 台 JOB ： 分钟 K 台 JOB ： 分钟 K 台

13 3、多道批处理方式下的作业调度 - 2 该系统采用多道程序设计技术，对磁带机采用静态分配，忽略设备工作时间和系统进行调度所共花的时间，请分别写出采用“先来先服务调度算法”和“最短作业优先算法”选中作业执行的次序以及作业平均周转时间。 若允许移动已在内存中的作业，则作业被选中的次序又是怎样的呢？计算出作业平均周转时间。 答案： 先来先服务： （25＋35＋70＋40＋50）/5=44 最短作业优先： ( )/5=43

14 4、多道系统进程平均周转时间的计算 有5个批处理作业A到E几乎同时到达计算中心。它们的估计运行时间分别为10，6，2，4和8分钟。其优先数（由外部设定）分别为3，5，2，1和4，其中5级为最高优先级。对于下列每种调度算法，计算其平均进程周转时间，可忽略进程切换的开销。 （1）优先级调度 （2）先来先服务（按照次序10，6，2，4，8运行） （3）最短作业优先 对（1）到（3）假设任一时刻只有一个作业运行，直到结束。所有的作业都是CPU密集型作业。 答案： （1）（ ）/5=20分钟 （2）（ ）/5=19.2分钟 （3）（ ）/5=14分钟

15 5、可变分区存储管理方案 内存管理 空闲块表——记录了空闲区起始地址和长度 已分配区表 内存分配 动态分配
三种分配算法：首先适配、最佳适配、最差适配

16 空闲区表 已分配区表 0K 15K 38K 48K 68K 80K 110K 120K 始址 长度 标志 15K 23K 未分配 48K
J1 38K 10K J2 68K 12K J3 110K J4 空 68K 80K 110K 120K

17 空闲区表 已分配区表 0K 15K 38K 48K 68K 80K 85K 98K 110K 120K 始址 长度 标志 15K 23K
未分配 48K 20K 98K 12K 空 0K 15K 38K 48K 已分配区表 始址 长度 标志 0K 15K J1 38K 10K J2 68K 12K J3 110K J4 80K 5K J5 85K 13K J6 68K 80K 85K 98K 110K 120K

18 6、段式存储管理方案下，空闲块分配的计算 - 1
有一个操作系统采用段式存储管理方案，用户区内存为512K，分配时截取空闲块的前半部分(小地址部分)。初始时内存全部空闲。系统执行如下申请、释放操作序列。 申请300K，申请100K，释放300K，申请150K，申请50K，申请90K （1）若采用首先适应算法，空闲块表中有哪些空块？ 请指出大小，地址； （2）若采用最佳适应算法，空闲块表中有哪些空块？ 指出大小，地址； （3）若随后又申请80K，针对上述两种情况说明结果？其结果说明了什么问题？

19 6、段式存储管理方案下，空闲块分配的计算 - 2
答案： （1）200K-300K为空闲块，490K-512K为空闲块 （2）240K-300K为空闲块，450K-512K为空闲块 （3）若在申请80K，两种算法都不能满足要求，这说明段式存储存在碎片，也就是虽然整个空闲空间满足用户要求，但是空闲块不连续不能分配。

20 7、移动技术 J1 J2 J3 0K 4K 6K 12K 13K 22K 23K 30K 32K 假定计算机系统的内存容量为32K，对内存采用动态可变分区分配算法。现已有3个作业在内存中，当作业J2执行时要求扩充3K内存。为满足此要求，应移动哪个作业的信息。

21 8、页面置换算法-1 例1：某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5，计算缺页次数

22 页面置换算法-2 FIFO 页 页 页 x x x x x x x   x x  共缺页中断9次

23 页面置换算法-3 LRU 页 页 页 x x x x x x x   x x x 共缺页中断10次

24 页面置换算法-4 OPT 页 页 页 x x x x   x   x x  共缺页中断7次

25 页面置换算法-5 例2：某程序在内存中分配m页初始为空，页面走向为1，2，3，4，1，2，5，1，2，3，4，5。当m=3，m=4时缺页中断分别为多少？用FIFO算法计算缺页次数。解释说明出现的结果。 m=3时，缺页中断9次，m=4时，缺页中断10次 FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加

26 例子3：内存分配一页，初始时第一页在内存；页面大小为128个整数；矩阵A128X128按行存放
页面置换算法-6 例子3：内存分配一页，初始时第一页在内存；页面大小为128个整数；矩阵A128X128按行存放 程序编制方法1： For j:=1 to 128 For i:=1 to 128 A[i,j]:=0; 程序编制方法2： For i:=1 to 128 For j:=1 to 128 A[i,j]:=0; 分配给进程的物理页面数 页面本身的大小 程序的编制方法 页面淘汰算法 影响缺页次数的因素

27 9、利用索引文件结构管理存储块时，计算读盘量
假定一个文件系统用索引文件结构管理存储块。每个文件有一个目录项，存放文件名、第一个索引块、以及文件长度。第一索引块指向248个文件块和下一个索引块。如果一个文件当前在第2009逻辑块，而下一个操作是访问第306个逻辑块，那么必须从磁盘上读多少个物理块？ 答案： 3个物理块

28 10、UNIX系统中采用索引文件结构 管理存储块的相关计算 - 1
有一个文件系统，根目录常驻内存，如图所示： 目录文件采用链接结构，规定一个目录下最多存放40个下级文件。下级文件可以是目录文件，也可以是普通文件。每个磁盘块可存放10个下级文件的描述信息，若下级文件为目录文件，则上级目录指向该目录文件的第一块，否则指向普通文件的文件控制块。

29 \A\D\G\I\K

30 10、UNIX系统中采用索引文件结构 管理存储块的相关计算 - 2
（1）普通文件采用UNIX的三级索引结构，即文件控制块中给出13个磁盘地址，前10个磁盘地址指出文件前10块的物理地址，第11个磁盘地址指向一级索引表，一级索引表给出256个磁盘地址，即指出该文件第11块至第266块的物理地址；第12个磁盘地址指向二级索引表，二级索引表中指出256个一级索引表的地址；第13个磁盘地址指向三级索引表，三级索引表中指出256个二级索引表的地址。该文件系统中的普通文件最大可有多少块？ 假设主索引表放在FCB中，若要读文件\A\D\G\I\K中的某一块，最少要启动磁盘几次？ 最多要启动磁盘几次？若要减少启动磁盘的次数，可采用什么方法？

31 10、UNIX系统中采用索引文件结构 管理存储块的相关计算 - 3
（2）普通文件采用链接结构，若要读\A\D\G\I\K的第75块最少启动硬盘几次，最多几次？ 答案： （1）一个文件的所有块可以通过下面三种途径找到：直接通过FCB找到前10块，通过一级索引找到256块，通过二级索引找到256*256块，通过三级索引找到256*256*256块，所以一个文件最大可以有 ^2+256^3=16,843,018块

32 10、UNIX系统中采用索引文件结构 管理存储块的相关计算 - 4
如果要找\A\D\G\I\K中的某一块，首先要找到其FCB，最好的情况是：每次读取目录描述信息的时候都在第一块找到下级目录或文件，所以要找到该文件至少要读取A、D、G、I四个目录项的第一块，读取K的FCB，总共5次启动硬盘；最坏情况是：每次读取目录描述信息的时候都在最后一个块找到下级的目录或文件，所以要找到该文件，所以要找到该文件至少要读取A的第一块，D、G、I三个目录项的所有四个块，在读取K的FCB，总共要1+4*3+1＝14次启动硬盘。找到FCB后在读取某一块，如果这一块在前10块之列，那么在启动一　次硬盘就可以找到这一块，如果这一块在最后一块，则可能需要通过三级索引找到这一块，这总共需要读取三级索引和最后一块共3+1次读取硬盘。综上，最好情况下只需要启动5+1次硬盘，最坏情况需要启动14+3+1＝18次硬盘

33 10、UNIX系统中采用索引文件结构 管理存储块的相关计算 - 5
若要减少硬盘启动的次数，第一可以对于经常访问的文件项或者目录进行项缓存，第二可以用散列表将常用的文件和目录进行散列，第三增减常驻内存的目录描述的数量（可以考虑将所有的一级和二级目录常驻内存），第四减少文件描述项的大小，使得每一块可以存放更多的文件描述项（更祥细的文件描述信息可以转存他处。） （2）为读取FCB所启动的硬盘次数和（1）一样，那么读取第75块最少需要5+75＝80次硬盘，最多需要启动14+75＝89次硬盘。

34 11、文件控制块分解法的计算 - 1 在实现文件系统时，为加快文件目录的检索速度，可利用“文件控制块分解法”。 假设目录文件存放在磁盘上，每个盘块512 字节。文件控制块占48 字节，其中文件名占6字节，文件号2字节。文件控制块分解后，第一部分占有8字节（包括文件名和文件内部号），第二部分占42字节（包括文件内部号和文件其他信息） （1）假设某一目录文件共有128个目录项，试分别给出采用分解法前和分解法后，查找该目录文件的一个文件控制块的平均访盘次数。 （2）一般地，若目录文件分解前占用n个盘块，分解后改用m个盘块存放文件名和文件内部号部分，请给出访盘次数减少的条件。

35 11、文件控制块分解法的计算 - 2 解：分解前：占512/48=10个FCB 分解后：占512/8=64个符号目录项
或512/42=12个基本目录项 分解前：占13块 分解后：符号文件占2块，基本文件占11块 查找一个文件的平均访盘次数 分解前：(1+13)/2=7次 分解后：(1+2)/2 +1 =2.5次 减少了访问硬盘的次数，提高了检索速度 （2）分解前：（1＋n）/2 分解后(1+m)/2+1； 访盘次数减少的条件：n-m>2

36 12、记录的成组和分解 设磁带的记录密度为每英寸800个字符，每一个逻辑记录长为240个字符，块与块之间的间隙为0.6英寸，现有500个逻辑记录需要存储到磁带上，试问： （1）未采用成组操作时，存储信息占用的空间与间隙占用的空间之比是多少？ （2）此时，磁带空间的利用率是多少？ （3）采用以10个逻辑记录为一组的成组操作时，磁带空间的利用率是多少？ （4）为了使磁带空间的利用率大于50％，采用记录成组时其块因子至少为多少？

37 13、文件系统的可靠性-1 文件系统的一致性 磁盘块→内存→写回磁盘块 若在写回之前，系统崩溃，则文件系统出现不一致
* 设计一个实用程序，当系统再次启动时，运行该程序，检查磁盘块和目录系统

38 文件系统的可靠性-2 UNIX一致性检查工作过程： 两张表，每块对应一个表中的计数器，初值为0 表一：记录了每块在文件中出现的次数
表二：记录了每块在空闲块表中出现的次数

39 文件系统的可靠性-3

40 文件系统的可靠性-4

41 文件系统的可靠性-5

42 文件系统的可靠性-6

43 14、磁头移动量的计算 - 1 假设一个活动头磁盘有200道，编号从0-199。当前磁头正在143道上服务，并且刚刚完成了125道的请求。现有如下访盘请求序列(磁道号)： 86，147，91，177，94，150，102，175，130 试给出采用下列算法后磁头移动的顺序和移动总量(总磁道数)。 （1）最短寻道时间优先（SSTF）磁盘调度算法。 （2）扫描法（SCAN）磁盘调度算法（假设沿磁头移动方向不再有访问请求时, 磁头沿相反方向移动。）

44 磁头移动量的计算 - 2 答案： （1）最短寻道时间优先： 磁盘移动：147，150，130，102，94，91，86，175，177
移动总量：4＋3＋20＋28＋8＋3＋5＋89＋2＝162 （2）扫描磁盘调度算法：147，150，175，177，130，102，94，91，86。 总量：4＋3＋25＋47＋28＋8＋3＋5＝125

45 15、旋转调度-1 旋转调度：根据延迟时间来决定执行次序的调度 分析： 若干等待访问者请求访问同一磁道上的不同扇区
若干等待访问者请求访问不同磁道上的不同编号的扇区 若干等待访问者请求访问不同磁道上具有相同的扇区

46 旋转调度-2 解决方案： 对于前两种情况：总是让首先到达读写磁头位置下的扇区先进行传送操作
对于第三种情况：这些扇区同时到达读写磁头位置下，可任意选择一个读写磁头进行传送操作

47 旋转调度-3 请求顺序 柱面号 磁头号 扇区号 ① ② ③ ④

48 16、信息的优化分布-1 记录在磁道上的排列方式也会影响输入输出操作的时间
例子：处理程序要求顺序处理8个记录；磁盘旋转一周为20毫秒/周；花5毫秒对记录进行处理 1 2 8 7 3 4 5 6 1 4 6 3 7 2 5 8

49 17、磁盘调度综合练习 请求顺序 柱面号 磁头号 扇区号 ① 9 6 3 ② 7 5 6 ③ 15 20 6 ④ 9 4 4
请求顺序 柱面号 磁头号 扇区号 ① ② ③ ④ ⑤ ⑥ 假设磁头在8柱面，求最省时间的响应次序

50 18、串行异步通信速率和效率的计算 串行异步通信端口在现代计算机中主要用于将终端（键盘和监视器）或打印机与计算机相连。典型的信号协议用1或2个开始位和1个结束位打包每个字节。发送者向接收者发送开始位以通知它将要开始传输一个字节。然后传送字节的8个位，后面跟1个结束位。用这种协议在9，600波特率的串行线上每秒能传送多少个字节？用于传送控制字节的时间所占百分比是多少？ 答案： 假设开始位为1位，那么9600波特率的串行线上每秒能传送9600/10=960个字节。用于传送控制字节的时间为2/10=20%。

51 19、关于死锁条件的计算 一个计算机系统有某种资源6个，供n个进程使用，每个进程至少需要2个资源。当n为何值时，系统不会发生死锁？ 答案：

52 20、银行家资源分配算法的计算 - 1 某系统当前有同类资源10个，进程P，Q，R所需资源总数分别为8，4，9。它们向系统申请资源的次序和数量如图所示。 （1）系统采用银行家算法分配资源，请给出系统完成第6次请求后各进程的状态及所占资源量。 （2）在以后各次的申请中，哪次的申请要求可先得到满足？ 次序 进程 申请量 1 R 2 6 Q P 4 7 3 8 9 5

53 银行家资源分配算法的计算 - 2 答案： （1）第六次请求后各进程的状态和所占资源量 （2）第4次请求可先得到满足 进程 目前占有量
最大需求量 尚需要量 P 4 8 Q R 2 9 7 （2）第4次请求可先得到满足

54 21、银行家算法应用-1 P1 0 1 0 7 5 3 已分配的资源 最大需求量 A B C A B C P2 2 0 0 3 2 2
已分配的资源 最大需求量 A B C A B C P P P P P 剩余资源 A B C

55 银行家算法应用-2 问题:此状态是否为安全状态，如果 是, 则找出安全序列 在此基础上 （1）P2 申请（1，0，2）能否分配？为什么？

56 有关OS的PV操作习题

57 题型分类 第一类：生产者-消费者问题 （共享缓冲区，一方放，一方取，同步、互斥） 第二类：读者-写者问题 （有不同优先级，主要解决互斥问题）
第三类：理发师问题、吸烟者问题 第四类：资源分配问题（阅览室问题、超市问题、银行服务问题） 第五类：纯同步问题 第六类：其他同步互斥问题

58 第一类：生产者-消费者问题-1 1、设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后再搬到缓冲区B2中，并在打印机上印出。问： （1）系统要设几个进程来完成这个任务？各自的工作是什么？ （2）这些进程间有什么样的相互制约关系？ （3）用PV操作写出这些进程的同步算法； （4）设系统中只有上述几个进程，用图表示出各自状态变迁情况及原因。

59 第一类：生产者-消费者问题 - 2 get copy put f s t g

60 第一类：生产者-消费者问题 - 3 2、进程A1、A2、……、An1通过m个缓冲区向进城B1、B2、……Bn2不断发送消息，发送和接收工作遵循如下规则： （1）每个发送进程每次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样； （2）对每一个消息，B1、B2、……、Bn2都需要各接收一次，读到各自的数据区内； （3）m个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待； 试用P、V操作组织正确的发送和接收操作。

61 第一类：生产者-消费者问题 - 4 有四个进程A、B、C、D
(1) 进程A通过一个缓冲区不断地向进程B、C、D发送信息，A 每向缓冲区送入一个信息后，必须等进程B、C、D都取走后才可以发送下一个信息, B、C、D对A 送入的每一信息各取一次，试用P、V操作实现它们之间的正确通讯。 (2) 试用最少个数的信号量实现进程A、B、C、D间的正确通讯。

62 第一类：生产者-消费者问题 - 5 3、某商店有两种食品A和B， 最大数量各为m个。该商店将A,B两种食品搭配出售, 每次各取一个。为避免食品变质，遵循先到食品先出售的原则，有两个食品公司分别不断地供应A,B两种食品(每次一个)。为保证正常销售，当某种食品的数量比另一种的数量超过k(k<m)个时，暂停对数量大的食品进货, 补充数量少的食品。 (1) 问共需设置几个进程? (2) 试用P,V操作解决上述问题中的同步和互斥关系。

63 第二类：读者-写者问题 - 2 4、设有A、B、C三个进程共享一个存储资源F。A对F只读不写，B对F只写不读，C对F先读后写。（当一个进程写F时，其他进程既不能读F，也不能写F，但多个进程同时读F是允许的）。试利用管程方法或P、V操作，写出A、B、C三个进程的框图，要求：（1）执行正确；（2）正常运行时不产生死锁；（3）使用F的并发度要高。 5、用PV操作解决写者优先的读者写者问题。

64 读者-写者问题-2 6、巴拿马运河建在太平洋和大西洋之间。由于太平洋和大西洋水面高度不同，有巨大落差，所以运河中修建有T（T>=2）级船闸，并且只能允许单向通行。船闸依次编号为1、2、……、T。由大西洋来的船需经由船闸T、T-1、……、2、1通过运河到太平洋；由太平洋来的船需经由船闸1、2、……、T-1、T通过运河到大西洋。 试用P、V操作正确解决大西洋和太平洋的船只通航问题。

65 第三类：理发师问题、吸烟者问题-1 7、在一间酒吧里有三个音乐爱好者，第一位音乐爱好者只有随身听，第二位只有音乐CD，第三位只有电池。而要听音乐就必须随身听、音乐CD和电池这三种物品俱全。酒吧老板一次出借这三种物品中的任意两种。当一名音乐爱好者得到这三种物品并听完一首乐曲后，酒吧老板才能再一次出借这三种物品中的任意两种。于是第二名音乐爱好者得到这三种物品，并开始听乐曲。整个过程就这样进行下去。 试用P，V操作正确完成这一过程。

66 第三类：理发师问题、吸烟者问题-2 8、一个理发店有两件相连的屋子。一间是私室，里面有一把理发椅，另一间是等候室，有一个滑动门和N把椅子。理发师忙的时候，通向私室的门被关闭，新来的顾客找一把空椅子坐下，如果椅子都被占用了，则顾客只好离去。如果没有顾客，则理发师在理发椅上睡觉，并打开通向私室的门。理发师睡觉时，顾客可以叫醒他理发。请编写理发师和顾客的程序，正确实现同步互斥问题。

67 第四类：资源分配问题-1 9、假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上标志（进入时登记，离开时去掉登记项），而且每次只允许一人登记或去掉登记，问： （1）应编写几个程序完成此项工作，程序的主要动作是些什么？应设置几个进程？进程与程序间的对应关系如何？ （2）用P、V操作写出这些进程的同步通信关系。

68 第四类：资源分配问题-2 10、某银行有人民币储蓄业务，由n个柜员负责。每个顾客进入银行后先取一个号，并且等着叫号。当一个柜台人员空闲下来，就叫下一个号。试用P、V操作正确编写柜台人员和顾客进程的程序。 11、某麦当劳餐厅最多同时可容纳100名顾客就餐。当餐厅中就餐者少于100名时，餐厅外的顾客可进入餐厅就餐，否则需在餐厅外面等待。若把每一名就餐顾客看作一个进程，请用P、V操作正确实现这些并发进程，请给出定义的信号量，写出信号量的初值以及信号量各种取值的含义。

69 另类题 13、（书139页37题）某系统如此定义P、V操作： P(S) S = S -1; 若S<0本进程入等待队列末尾，否则继续运行
V(S) 若S<=0，释放等待队列中末尾的进程，否则继续运行 现有四个进程P1、P2、P3、P4竞争使用某一需互斥使用的资源（每个进程可能反复使用多次），试用这样的P、V操作来正确地实现互斥。

70 第五类纯同步问题 14、六个并发执行的进程P1、P2、P3、P4、P5和P6协同工作，它们的协作关系如图所示。试编写这六个进程的程序，并用P、V操作保证它们之间的正确执行。请给出设置的信号量及初值，并说明每个信号量的含义

71 第五类纯同步问题 司机进程： while (true){ 启动车辆 正常驾驶 到站停车 }… 售票员进程： 关门 售票 开门

72 小测验设计

73 小测验设计 目的 考察学习效果 督促学生学习 课程学习成绩的组成部分

74 示例： 2001级第一次小测验 - 1 1．怎样理解“用户使用的是虚拟计算机”这句话？ 2．操作系统怎样管理各种系统资源？ 3．填写下表：
分类 设计目标 批处理操作系统 分时操作系统 实时操作系统 个人计算机操作系统 网络操作系统 分布式操作系统 嵌入式操作系统

75 示例： 2001级第一次小测验 - 2 4．填写下表，在如下应用场合应该选用什么操作系统？ 应用 操作系统 银行自动取款机
国家统计局全国人口统计分析软件 火车订票系统 汽车发动机点火控制 电脑文字录入与排版服务 三星x199彩屏CDMA 手机 复杂流动的高精度计算

76 示例： 2001级第一次小测验 - 3 5．存储体系包括哪些内容？根据什么因素确定存储体系？为什么要引入存储体系？
6．中断系统中，怎样从硬件处理转向软件处理？作为操作系统设计者应该考虑哪些问题？ 7．列举5条特权指令和5条非特权指令。 8．简要描述处理机的状态，为什么要划分处理器状态？ 9．简述SPOOLing系统的工作原理。 10．简要叙述系统调用的工作过程。

77 示例： 2001级第一次小测验 - 4 11．某系统采用不能移动已在内存中作业的可变分区方式管理内存，现有供用户使用的内存空间100K，系统配有4台磁带机，有一批作业如下： 作业 进入系统时间 估计运行时间 内存需求 磁带机需求 优先数 JOB : 分钟 K 台 JOB : 分钟 K 台 JOB : 分钟 K 台 JOB : 分钟 K 台 JOB : 分钟 K 台 JOB : 分钟 K 台 该系统采用多道程序设计技术，对磁带机采用静态分配策略，忽略设备工作时间和系统进行调度所共花的时间，作业调度算法采用“最短作业优先”，进程调度算法（即被调度程序选中在处理器上执行）采用优先数法（即优先数大的首先被调度）。请写出作业执行的次序以及作业平均周转时间。

78 示例： 2004年第二次小测验 - 1 1．解释并发环境，说明并发和并行的区别。 2．什么是多道程序设计？

79 示例： 2004年第二次小测验 - 2 3．两个并发进程的程序如下： begin N: integer; N=3; PROCESS B
cobegin PROCESS A Begin L1: N=N+5; goto L1 end; PROCESS B Begin L2: print(N); N:=0; goto L2 end; coend; 若PROCESS A 先执行了三个循环后，PROCESS A 和PROCESS B又并发执行了一个循环，写出可能出现的打印值。正确的打印值应该是多少？试分析在什么情况下会出现与时间有关的错误？怎样解决这一问题？

80 示例： 2004年第二次小测验 - 3 4．写出进程的定义，并举生活中一个进程的例子。 5．列举一个守护进程。
6．列举出一些可能的进程/线程状态，填写下表： 进程/线程状态 描述

81 示例： 2004年第二次小测验 - 4 7．一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能（只考虑基本状态）。
8．如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？ 9．列举出进程控制块的主要内容。 10．进程映像包括哪些内容？ 11．什么是进程同步？什么是进程互斥？列举两个现实生活中需要同步与互斥的例子。

82 示例： 2004年第二次小测验 - 5 12．下面是解决互斥问题的一种软件解法，请指出有什么问题？
pturn, qturn: 初值为false P Q pturn = true; pturn = true; while (qturn); while (pturn); 临界区 临界区 pturn = false; qturn = false;

83 示例： 2004年第二次小测验 - 6 13．为什么在管程中引入条件变量？在条件变量上能执行什么操作？
14．进程通信有几种方式？分别是什么？ 15．进程调度和作业调度的区别是什么？

84 示例： 2004年第二次小测验 - 7 16．某系统有如下的状态转换图，试说明该系统采用了什么进程调度策略？说出理由。

85 示例： 2004年第二次小测验 - 8 17．列举出两种一定引起进程切换的中断？ 18．为什么引入线程？实现线程有哪些方式？
19．Windows线程调度采取的是一种什么策略？

86 示例： 2004年第二次小测验 - 9 20．一个主修人类学、辅修计算机科学的学生参加了一个课题，调查是否可以教会非洲狒狒理解死锁。他找到一处很深的峡谷，在上边固定了一根横跨峡谷的绳索，这样狒狒就可以攀住绳索越过峡谷。同一时刻，只要朝着相同的方向就可以有几只狒狒通过。但如果向东和向西的狒狒同时攀在绳索上那么会产生死锁（狒狒会被卡在中间），由于它们无法在绳索上从另一只的背上翻过去。如果一只狒狒想越过峡谷，它必须看当前是否有别的狒狒正在逆向通行。利用信号量编写一个避免死锁的程序来解决该问题。不考虑连续东行的狒狒会使得西行的狒狒无限制的等待的情况。

87 示例： 2004年第二次小测验 - 10 21．某麦当劳餐厅最多同时可容纳100名顾客就餐。当餐厅中就餐者少于100名时，餐厅外的顾客可进入餐厅就餐，否则需在餐厅外面等待。若把每一名就餐顾客看作一个进程，请用P、V操作正确实现这些并发进程，请给出定义的信号量，写出信号量的初值以及信号量各种取值的含义。 22．有四个进程A、B、C、D 进程A通过一个缓冲区不断地向进程B、C、D发送信息，A 每向缓冲区送入一个信息后，必须等进程B、C、D都取走后才可以发送下一个信息，B、C、D对A 送入的每一信息各取一次。试用P、V操作实现它们之间的正确通信。（要求用最少个数的信号量）

88 示例： 2003年第三次小测验 - 1 1．存储共享的目的是什么？ 2．存储保护包括哪两个方面？ 3．填写下表： 存储管理方案 程序划分
内存空间划分 有关数据结构 内碎片/外碎片 可变分区 页式 段式 段页式

89 示例： 2003年第三次小测验 - 2 4．进行内存紧缩时要考虑什么问题？
5．页表表项由谁决定？虚拟页式存储管理方案中的页 表表项一般有哪些？ 6．谈谈快表TLB。 7．在虚拟页式存储管理中，进程在内外存中的存放有以下两种方法： （1）一部分页面放在内存，其余页面放在外存； （2）一部分页面放在内存，全部页面放在外存； 试从系统开销的角度分析两种方法各自的优缺点，并说明页表的差别。 8．给出一种第二次机会算法的具体实现方法（包括设计的数据结构和算法主要步骤）。

90 示例： 2003年第三次小测验 - 3 9．有一个虚拟页式存储管理系统，页面调度算法采用最近最少使用（LRU）算法，系统为每个程序分配5页主存，其中一页用来存放程序和变量i,j（不作他用）；每一页可存放128个整数变量。有两个程序编制如下： VAR C：ARRAY[1..128,1..256] OF integer；i,j：integer； A程序： for i:=1 to 128 do for j:=1 to 256 do C[i,j]:=0； B程序： for j:=1 to 256 do for i:=1 to 128 do C[i,j]:=0； 初始时，两个程序及变量i,j已在内存，分配给矩阵C的四页为空，且矩阵C按行编址。 试问当A和B程序执行完后，各缺页多少次？

91 示例： 2003年第三次小测验 - 4 10．引入工作集模型的前提是什么？引入工作集模型的作用是什么？
11．文件系统中若文件的物理结构采用链接结构，则文件控制快FCB中关于文件的物理位置应包括哪些内容？

92 示例： 2003年第三次小测验 - 5 12．有一个文件系统，根目录常驻内存，如图所示：
目录文件采用链接结构，规定一个目录下最多存放80个下级文件。下级文件可以是目录文件，也可以是普通文件。每个磁盘块可存放20个下级文件的描述信息，若下级文件为目录文件，则上级目录指向该目录文件的第一块，否则指向普通文件的文件控制块。

93 示例： 2003年第三次小测验 - 6 （1）普通文件采用UNIX的三级索引结构，即文件控制块中给出13个磁盘地址，前10个磁盘地址指出文件前10块的物理地址，第11个磁盘地址指向一级索引表，一级索引表给出128个磁盘地址，即指出该文件第11块至第138块的物理地址；第12个磁盘地址指向二级索引表，二级索引表中指出128个一级索引表的地址；第13个磁盘地址指向三级索引表，三级索引表中指出128个二级索引表的地址。该文件系统中的普通文件最大可有多少块？ 假设主索引表放在FCB中，若要读文件\A\D\G\I\K中的某一块，最少要启动磁盘几次？ 最多要启动磁盘几次？

94 示例： 2003年第三次小测验 - 7 （2）普通文件采用顺序结构，若要读\A\D\G\I\K的第375块，最少启动硬盘几次，最多几次？

95 示例： 2003年第三次小测验 - 8 13．某文件系统把文件存储到磁盘上时采用链接结构，磁盘分块大小为512个字节，而逻辑记录的大小为250个字符。现有一个名为ABC的文件，共10个逻辑记录，回答下列问题： （1）怎样才能有效的利用磁盘空间？ （2）画出文件ABC在磁盘上的链接结构（磁盘块号自定）。 （3）若用户要求读包含第1452个字符的逻辑记录，请写出完成用户要求的主要工作步骤。

96 示例： 2003年第三次小测验 - 9 14．系统为打开的文件设置哪些数据结构？为什么？
15．一些操作系统提供了COPY系统调用给文件改名。试用基本文件操作（如建立文件、打开文件、读文件、写文件、关闭文件、删除文件等）设计出一种实现COPY（A，B）系统调用的方案，其中A为原文件名，B为新文件名。 16．什么是文件系统的一致性问题？ 17．在考虑操作系统安全问题时，应设计哪些方法进行身份识别？

97 示例： 2003年第三次小测验 - 10 18．某移动臂磁盘的柱面由外向里从0开始顺序编号，假定当前磁头停在100号柱面而且移动方向是向外的，现有一个请求队列在等待访问磁盘，访问的柱面号分别为190、10、160、80、90、125、30、20、140和25。请写出分别采用最短寻找时间优先和电梯调度算法处理上述请求的次序。 19．列举4种提高文件系统性能的方法，并简要说明其中的2种方法。 20．对课程的意见或建议（自上次测验后到现在，如果不方便回答，请到论坛上发表意见）。

98 有关学生小论文 作用与写作要求

99 学生小论文作用 帮助学生将所学内容条理化、深入化 了解学生对所学内容掌握程度以及学习态度 协助学生掌握查询科技文献能力
提高学生科技论文的写作水平

100 学生小论文写作要求 在教师提供的选题范围内自选论文题目 自行收集参考文献，独立写作完成 论文长度，一般不超过4页Word文档

101 小论文参考题目-1 高速缓存 TLB 优先级反转 RAID 虚拟机结构 Cache 可再入程序 自旋锁 时钟的作用 微内核 磁盘空间管理
逻辑I/O与物理I/O 消息 系统调用及其实现 TLB RAID Cache 自旋锁 微内核 引导程序 单调速率 伙伴系统 动态链接

102 小论文参考题目-2 Windows线程优先级提升 通信：有阻塞和无阻塞的区别 消息通信：可靠传输和不可靠传输的区别
举例说明面块的设备与面向流设备的区别？ 写时复制NTFS在系统崩溃或磁盘出现故障后如何安全恢复文件系统 描述Windows 位地址的内容 解释虚拟地址如何转换为物理地址

103 小论文作业效果 多数学生能够按照要求完成论文，论文质量尚可 少数学生的论文优秀，其特点： 内容充实、分析深入、有自己观点、叙述有条理
按照正式科技论文要求写作 附有一定数量的参考文献 极少数学生论文敷衍了事