答：（1）信号量的初值为1。信号量的变化范围是1，0，-1，…，-（n-1）。
（2）信号量的初值为m。信号量的变化范围是m,m-1,…,1,0,…,-(n-m)。
6. 何为死锁？产生死锁的原因和必要条件是什么？
此题答案为：答：（1）死锁是指多个进程因竞争资源而造成的一种僵持状态。若无外力作用，这些进程都将永远处于阻塞状态，不能再运行下去。
（2）产生死锁的原因有：资源不足、进程推进次序不当。
（3）产生死锁的必要条件有：互斥条件、请求和保持条件、环路等待条件。
7. 比较三种解决死锁的方法?
此题答案为：答：比较三种解决死锁的方法：
（1）预防死锁方法，主要是破坏产生死锁的必要条件。该方法是最容易实现的，但系统资源利用率较低。
（2）避免死锁方法，比较实用的有银行家算法（Banker Algorithm）。该算法需要较多的数据结构，实现起来比较困难，但资源利用率最高。
（3）检测死锁方法是基于死锁定理设计的。定期运行该算法对系统的状态进行检测，发现死锁便予以解除。其中，需要比较一下各咱死锁解除方案的代价，找到代价最小的方案。该方法最难实现，资源利用率较高。
8. 预防死锁方法是破坏产生死锁的必要条件?
此题答案为：答：（1）摈弃请求和保持条件。采用静态分配方案，一次性地分配给进程所请求的全部资源。进程运行过程中不可再请求新资源。
（2）摈弃不剥夺条件。采用动态分配方案，进程运行中可以请求新资源。若进程请求资源不能满足时，就应使其释放已占有的资源。
（3）摈弃环路等待条件。采用动态分配方案，要求进程请求资源时，按资源序号递增（或递减）顺序提出。（4）摈弃不可剥夺条件。利用Spooling系统将独享设备改造成共享设备。
9. I/O控制方式有几种？分别适用何种场合？
此题答案为：答：I/O控制方式共有四种：
（1）程序I/O方式，又称作"忙-等"方式。该方式执行一个循环程序，反复查询外设状态，如果外设"忙碌"则循环查询直到查得外设状态为"闲置"时止。该方式适用于机内没有中断机构得场合。
（2）中断控制I/O方式。该方式在进行I/O时，CPU向设备控制器发出I/O命令后便转其他任务得处理，外设操作由设备控制器控制，CPU于外设并行工作。当外设完成I/O后向CPU发中断信号，CPU只需花费很少的时间进行I/O的善后处理，此前无须进行干预。该方式适用于低速设备I/O，并可配合DMA和通道方式实现I/O。（3）DMA（直接内存访问）方式。该方式适用于高速外设I/O，一次可以在外设与内存之间传输一个或多个数据快，传输完毕后才需CPU干预。
（4）通道方式。该方式中系统预先要将I/O的过程实现为一段通道程序，置于内存的特定位置，而后启动通道。由通道负责执行通道程序对外设进行I/O控制，CPU转其他程序运行。I/O完成后通道向CPU发中断信号，CPU 花很少时间作善后处理。
10. 试说明DMA的工作流程。
答：DMA的工作流程如下：
（1）CPU需要访问外存时便发送。一条访问命令给DMA的命令寄存器CR、一个内存地址码给DMA的内存地址寄存器MAR、本次要传送的字节数给DMA的数据计数器DC、外存地址给DMA的I/O控制逻辑。
（2）CPU启动DMA控制器后转向其他处理。
（3）DMA控制器负责控制数据在内存与外设之间传送。每传送一个字节就需挪用一个内存周期，按MAR从内存读出或写入内存一个字节，修改MAR和计算器DC。
（4）当DC修改为0时，表示传送结束，由DMA向CPU发出中断请求。
11. 进程的三个基本状态是什么？
此题答案为：答：进程的三个基本状态是就绪态、执行态、阻塞态。
12. 操作系统的基本功能有哪些？它们各自包括哪方面的内容？
答：1、处理机管理功能进程控制，进程同步，进程通信，调度
2、存储器管理功能内存分配、内存保护、地址映射、内存扩充
3、设备管理功能缓冲管理、设备分配、设备处理
4、文件管理功能文件储存空间的管理、目录管理、文件的读写管理和保护
5、用户接口命令接口、程序接口、图形接口
13. 选择进程调度算法的准则是什么？
此题答案为：答：由于各种调度算法都有自己的特性，因此，很难评价哪种算法是最好的。一般说来，选择算法时可以考虑如下一些原则：①处理器利用率；②吞吐量；③等待时间；④响应时间。
在选择调度算法前，应考虑好采用的准则，当确定准则后，通过对各种算法的评估，从中选择出最合适的算法。
15. 磁盘移臂调度的目的是什么？常用移臂调度算法有哪些？
此题答案为：答：磁盘移臂调度的目的是尽可能地减少输入输出操作中的寻找时间。
常用的移臂调度算法有：①先来先服务算法②最短寻找时间优先算法③电梯调度算法④单向扫描算法。16. 常用的作业调度算法有哪些？
此题答案为：答：①先来先服务算法②计算时间短的作业优先算法③响应比最高者优先算法
④优先数调度算法⑤均衡调度算法
17. 简述信号量S的物理含义。
此题答案为：答：S＞0时，S表示可使用的资源数；或表示可使用资源的进程数；
S＝0时，表示无资源可供使用；或表示不允许进程再进入临界区；
S＜0时，－S表示等待使用资源的进程个数；或表示等待进入临界区的进程个数；
当S＞0时，调用P（S）的进程不会等待；调用V（S）后使可用资源数加1或使可用资源的进程数加1；
当S＜0时，调用P（S）的进程必须等待；调用V（S）后将释放一个等待使用资源者或释放一个等待进入临界区者。
18. 试说明资源的静态分配策略能防止死锁的原因。
此题答案为：答：资源静态分配策略要求每个过程在开始执行前申请所需的全部资源，仅在系统为之分配了所需的全部资源后，该进程才开始执行。
这样，进程在执行过程中不再申请资源，从而破坏了死锁的四个必要条件之一"占有并等待条件"，从而防止死锁的发生。
19. 为实现设备的有效管理，应采用怎样的数据结构？
此题答案为：答：为实现设备、控制器、通道资源的分配与回收，系统需要记录有关的信息。通常设备管理要建立以下数据结构，以实施有效的管理。
1、设备控制块
2、控制器控制块
3、通道控制块
4、系统设备表
20. 什么是设备的独立性？根据设备的类型，设备的分配策略有哪些？(独占设备、共享设备、虚拟设备与SPOOLing系统)。以磁盘为例，有哪些优化调度算法？应考虑哪些因素？
此题答案为：答：进程申请设备时，应当指定所需设备的类别，而不是指定某一台具体的设备，系统根据当前请求以及设备分配情况在相应类别的设备中选择一个空闲设备并将其分配给申请进程，这称作设备的独立性。
磁盘调度一般可采用以下几种算法：1、先来先服务磁盘调度算法（FCFS）2、最短寻道时间优先磁盘调度算法（SSTF）3、扫描算法（SCAN）
设计磁盘调试算法应考虑两个基本因素：
1、公平性
2、高效性
21. 什么叫碎片？(零散的小空闲区) 怎样解决碎片问题？(紧凑技术)。
此题答案为：答：所谓碎片是指内存中出现的一些零散的小空闲区域。
解决碎片的方法是移动所有占用区域，使所有的空闲区合并成一片连续区域。这一过程称为紧凑，这一技术就是紧凑技术。
22. 什么叫物理地址？什么叫逻辑地址？什么叫地址映射？地址映射分哪几类？(静态、动态)
答：物理地址是内存中各存储单元的编号，即存储单元的真实地址，它是可识别、可寻址并实际存在的。
用户程序经过编译或汇编形成的目标代码，通常采用相对地址形式，其首地址为零，其余指令中的地址都是相对首地址而定。这个相对地址就称为逻辑地址或虚拟地址。逻辑地址不是内存中的物理地址，不能根据逻辑地址到内存中存取信息。
为了保证CPU执行程序指令时能正确访问存储单元，需要将用户程序中的逻辑地址转运行时可由机器直接寻址的物理地址，这一过程称为地址映射或地址重定位。
地址映射可分为两类：1、静态地址映射2、动态地址映射
23. 虚存储器的含义是什么？(两层含义)
答：虚存储器有两层含义，一是指用户程序的逻辑地址构成的地址空间；二是指当内存容量不满足用户要求时，采用一种将内存空间与外存空间有机地结合在一起，利用内外存自动调度的方法构成一个大的存储器，从而给用户程序提供更大的访问空间。
答：在多道程序系统中，内存中既有操作系统，又有许多用户程序。为使系统正常运行，避免内存中各程序相互干扰，必须对内存中的程序和数据进行保护。
1、防止地址越界
对进程所产生的地址必须加以检查，发生越界时产生中断，由操作系统进行相应处理。
2、防止操作越权
对属于自己区域的信息，可读可写；
对公共区域中允许共享的信息或获得授权可使用的信息，可读而不可修改；
对未获授权使用的信息，不可读、不可写。
存储保护一般以硬件保护机制为主，软件为辅，因为完全用软件实现系统开销太大，速度成倍降低。当发生越界或非法操作时，硬件产生中断，进入操作系统处理
24. 作业调度算法是按照什么样的原则来选取作业并投入运行，调试算法的合理性直接影响系统的效率，作业调度算法有哪些？对算法的选择要考虑哪些问题？
此题答案为：答：作业调度算法：1、先来先服务算法；2、短作业优先算法；3、最高响应比作业优先算法；4、资源搭配算法；5、多队列循环算法
对算法的选择要考虑三个目标：
1、尽量提高系统的作业吞吐量，即每天处理尽可能多的作业；
2、尽量使CPU和外部设备保持忙碌状态，以提高资源利用率；
3、对各种作业公平合理，使用有用户都满意。
四、算法题
1. 假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。
表1 进程到达和需要服务时间
进程到达时间服务时间
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2
此题答案为：表2 进程的完成时间和周转时间
进程 A B C D E 平均
FCFS 完成时
间
3 9 13 18 20
周转时
间
3 7 9 12 12 8.6
带权周转时
间
1.00 1.17
2.25 2.40 6.00 2.56
SPF(非抢占) 完成时
间
3 9 15 20 11
周转时
间
3 7 11 1
4 3 7.6
带权周转时
间
1.00 1.17 1.75
2.80 1.50 1.84
SPF(抢占)
完成时
间
3 15 8 20 10
周转时
间
3 13
4 14 2 7.2
带权周转时
间
1.00
2.16 1.00 2.80 1.00 1.59
3. 一个逻辑空间最多可有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储器。问：（1）有效的逻辑地址由多少位？（2）有效的物理地址由多少位？
答：一个逻辑空间有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储嚣。64＝26，则：（1）逻辑地址有16位。（2）物理地址有15位。
说明：解此题的关键是要知道在分页管理中，"页"和"块"是一样大小的，这样才知道物理存储器是32KB。
4. 对访问串：1，2，3，4，1，2，5，1，2，3，4，5，指出在驻留集大小分别为3，4时，使用FIFO和LRU 替换算法的缺页次数。结果说明了什么？
答：首先采用FIFO，当m=3时，缺页次数＝9，当m=4时，缺页次数＝10。
采用LRU算法，当m=3时，缺页次数＝10；当m=4时，缺页次数＝8。
结果说明：FIFO有Belady奇异现象，即不满足驻留集增大，缺页次数一定减小的规律；另外在m=3时，LRU 的缺页次数比FIFO要多，所以LRU算法并不总优于FIFO，还要看当前访问串的特点。
5. 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。
此题答案为：
当M=3时，缺页次数为10次，缺页率为10/12=0.83=83%。
当M=4时，缺页次数为8次，缺页率为8/12=0.66=66%。
可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。
6. 在分页存储管理系统中，存取一次内存的时间是8ns，查询一次快表的时间是1ns，缺页中断的时间是20ns。假设页表的查询与快表的查询同时进行，当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。一个作业最多可保留3个页面在内存。现在开始执行一作业，系统连续对作业的2，4，5，2，7，6，4，8页面的数据进行一次存取，如分别采用FIFO算法和最优页面置换算法，求每种上存取这些数据需要的总时间。
答：（1）FIFO 第2页面：20＋8×3
第4页面：20＋8×3
第5页面：20＋8×3
第2页面：8＋1
第7页面：20＋8×3
第6页面：20＋8×3
第4页面：20＋8×3
第8页面：20＋8×3
因此总的时间是（20＋8×3）×7＋（8＋1）ns
(2) OPT
第2页面：20＋8×3
第4页面：20＋8×3
第5页面：20＋8×3
第2页面：8＋1
第7页面：20＋8×3
第6页面：20＋8×3
第4页面：8＋1
第8页面：8＋1
因此总的时间是（20＋8×3）×5＋（8＋1）×3ns
6. 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为1、3、2、1、1、3、5、1、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。
此题答案为：
当M=3时，缺页次数为6次，缺页率为6/12=0.5=50%。
当M=4时，缺页次数为4次，缺页率为4/12=0.33=33%。
可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。
7. 有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。
(1)试说明A、B两进程之间存在什么样的制约关系？
答：A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用
(2)为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。
此题答案为：答：mutex：用于互斥的信号量，因为只有一台打印机，所以初值为1
进程A 进程B
... ...
P(mutex)；P(mutex)；
申请打印机；申请打印机；
使用打印机；使用打印机；
V(mutex)；V(mutex)；
8. 设input进程不断向缓冲区Q写入信息，output进程不断地将刚由input进程写入的信息读出。试问：（1）这两个进程有何相互制约关系？
答：这两个进程的相互制约关系为同步关系；
（2）试用P、V操作写出这两个进程完成这项任务的代码段和信号量的含义及初值。
此题答案为：答：设两个信号量S1和S2。其中S1表示Q是否为空，初值为1，表示Q是空的；S2表示Q 中是否有信息，初值为0，表示Q中无信息。
两进程的代码段如下：
input进程output进程
…………
While 信息未处理完毕While 信息未处理完毕
{ 加工一个信息；{ P（S2）；
P（S1）；从Q中读出一个信息；
将信息放入Q中；V（S1）；}
V（S2）；} ……
9. 假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：
作业进入系统时间估计运行时间/分钟
1 8:00 40
2 8:20 30
3 8:30 12
4 9:00 18
5 9:10 5
此题答案为：(1) 如果应用先来先服务的作业调度算法，试将下面表格填写完整。
作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟
1 8:00 40 8：00 8：40 40
2 8:20 30 8：40 9：10 50
3 8:30 12 9：10 9：22 52
4 9:00 18 9：22 9：40 40
5 9:10 5 9：40 9：45 35
作业平均周转时间T= 43.4 217
（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。
作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟
1 8:00 40 8：00 8：40 40
2 8:20 30 8：52 9：22 62
3 8:30 12 8：40 8：52 22
4 9:00 18 9：27 9：4
5 45
5 9:10 5 9：22 9：27 17
作业平均周转时间T= 37.2 186
10. 在请求分页系统中，某用户的编程空间为16个页面，每页1K，分配的内存空间为8K。假定某时刻该用户的页表如下图所示，试问：
（1）逻辑地址084B（H）对应的物理地址是多少？（用十六进制表示）
（2）逻辑地址5000（十进制）对应的物理地址是多少？（用十进制表示）
（3）当该用户进程欲访问24A0H单元时，会出现什么现象？
页号块号
0 3
1 7
2 4
3 1
4 12
5 9
6 61
7 20
此题答案为：(1)答：104B(H)
(2)答：13192
(3)答：24A0（H）的页号为9，而其页面当前不在内存，所以会发一个缺页中断，请求系统调页。
11. 根据如下段表：
段号基地址长度合法（0）/非法（1）
0 300 200
1 7500 540
2 3000 1010
3 2000 100
（1）求出逻辑地址为0，100的物理地址并将其的合法性填入上表适当位置；
（2）求出逻辑地址为3，100的物理地址并将其的合法性填入上表适当位置；
此题答案为：(1)答：物理地址为：300+100=400
(2)答：物理地址为：2000+100=2100
段号基地址长度合法（0）/非法（1）
0 300 200 0
1 7500 540
2 3000 1010
3 2000 100 1
2．设在一个页面大小为1K的系统中，正在处理器上执行的一个进程的页表如图所示：
页号状态位访问位修改位物理块号
0 1 1 0 4
1 1 1 1 7
2 0 0 0 -
3 1 0 0 2
4 0 0 0 -
5 1 0 1 0
起始页号和块号均为0。
1．详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。
2．下列逻辑地址（十进制）对应与什么物理地址：5449，2221。
解：5449的物理地址为：329
2221的物理地址为：2221
3．设系统有三种类型的资源，数量为(4，2，2)，系统中有进程A，B，C按如下顺序请求资源：进程A申请(3，2，1)
进程B申请(1，0，1)
进程A申请(0，1，0)
进程C申请(2，0，0)
请你给出一和防止死锁的资源剥夺分配策略，完成上述请求序列，并列出资源分配过程，指明哪些进程需要等待，哪些资源被剥夺。(10分)
解：①分配策略为：当进程P i申请r i类资源时，检查r i中有无可分配的资源：有则分配给P i；否则将P i占有的资源全部释放而进入等待状态。(P i等待原占有的所有资源和新申请的资源)
②资源分配过程：剩余资源
进程A：(3，2，1)(1，0，1)
进程B：(1，0，1)(0，0，0)
进程A：(0，1，0)(不满足)(3，2，1)
A的所有资源被剥夺，A处于等待
进程C：(2，0，0)(1，2，1)
C，B完成之后，A可完成。
4．设公共汽车上，司机和售票员的活动分别是：
司机：启动车辆售票员：上乘客
正常行车关车门
到站停车售票
开车门
`下乘客
在汽车不断地到站，停车，行使过程中，这两个活动有什么同步关系？并用wait和signal 原语操作实现它们的同步。
解：BEGIN integer stop,run;
Stop:=0;
Run:=0;
COBEGIN
Driver: BEGIN
L1: wait(run);
启动车辆；
正常行车；
到站停车；
signal(stop);
Goto L1;
END
Conductor: BEGIN
L2：上乘客；
关车门；
signal(run);
售票；
wait(stop);
开车门；
下乘客；
Goto L2;
END
COEND
END
5、某虚拟存储器的用户编程空间共321KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：
页号物理块号
1 5
2 10
3 4
4 7
则逻辑地址0A5C（H）所对应的物理地址是什么？
答：逻辑地址0A5CH）所对应的二进制表示形式是：0000 1010 0101 1100 ，由于1K=210，下划线部分前的编码为000010，表示该逻辑地址对应的页号为3查页表，得到物理块号是4（十进制），即物理块地址为：0001 0010 0000 0000 ，拼接块内地址0000 0000 0101 1100，得0001 0010 0101 1100，即125C（H）。
6、某段表内容如下：
段号段首地址段长度
0 120K 40K
1 760K 30K
2 480K 20K
3 370K 20K
一逻辑地址为（2，154）的实际物理地址为多少？
答：逻辑地址（2154）表示段号为2，即段首地址为480K，154为单元号，则实际物理地址为480K+154。
7、设系统中有三种类型的资源（A，B，C）和五个进程（P1，P2，P3，P4，P5），A资源的数量为17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态如表1和表2所示。（共10分）
系统采用银行家算法实施死锁避免策略。
①T0时刻是否为安全状态？若是，请给出安全序列。
②在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？
③在②的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？
④在③的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配？为什么？
表1 T0时刻系统状态
最大资源需求量已分配资源数量
A B C A B C
P1 5 5 9 2 1 2
P2 5 3 6 4 0 2
P3 4 0 11 4 0 5
P4 4 2 5 2 0 4
P5 4 2 4 3 1 4
表2 T0时刻系统状态
A B C
剩余资源数 2 3 3
8．系统中有五个进程P1、P2、P3、P4、P5，有三种类型的资源：R1、R2、和R3。在T0时刻系统状态如表所示。若采用银行家算法实施死锁避免策略，回答下列问题：（共9分，每小题3分）
1．T0时刻是否为安全状态？为什么？
2．若这时P4请求资源（1，2，0），是否能实施资源分配？为什么？
3．在上面的基础上，若进程P3请求资源（0，1，0），是否能实施资源分配？为什么？
T0时刻系统状态
已分配资源数量最大资源需求量
R1 R2 R3 R1 R2 R3
P1 0 0 1 0 0 1
P2 2 0 0 2 7 5
P3 0 0 3 6 6 5
P4 1 1 5 4 3 5
P5 0 3 3 0 6 5
R1 R2 R3
剩余资源数 3 3 0
解：（共9分，每小题3分）
1．T0时刻是安全的，安全序列为：P1，P4，P5，P2，P3
2．P4请求资源（1，2，0），根据银行家算法，预分配后系统是安全的，安全序列为：P1，P4，P5，P2，P3
3．P3请求资源（1，1，0），根据银行家算法，预分配后系统不安全，所以不能实施资源分配。
9．一个进程的大小占5个页面，每页的大小为1K，系统为它分配了3个物理块。当前进程的页表如图所示：（共8分）
块号存在位P 访问位R 修改位M
0x1C 1 1 0
0x3F 1 1 1
- 0 0 0
0x5D 1 0 0
- 0 0 0
1．有那些页面不在内存？（2分）
2．请分别计算进程中虚地址为0x3B7、0x12A5、0x1432单元的物理地址（用十六进制表示），并说明理由。（6分）
解：（共8分）
不在内存的是第2和4页（按页号），或第3和5页（按序号）。（2分）
0x3B7的物理地址=0x 73 B7 （2分）
0x12 A5的物理地址=0x 176 A5，缺页，换出第三页。（2分）
0x1432地址越界，出错。（2分）
11．在一个请求分页系统中，有一个长度为5 页的进程，假如系统为它分配3 个物理块，并且此进程的
页面走向为2，3，2，1，5，2，4，5，3，2，5，2。试用FIFO 和LRU 两种算法分别计算出程序访问过程
中所发生的缺页次数。（10分）
解：FIFO：
2 3 2 1 5 2 4 5 3 2 5 2
第1页 2 2 2 5 5 5 3 3 3
第2页 3 3 3 2 2 2 5 5
第3页 1 1 1 4 4 4 2
缺页中断次数= 9
LRU：
2 3 2 1 5 2 4 5 3 2 5 2
第1页 2 2 2 2 2 3 3
第2页 3 3 5 5 5 5
第3页 1 1 4 4 2
缺页中断次数= 7
13．一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所示（都为十进制数，
且从0开始计数。）。当虚页4发生缺页时，使用下列的页面置换算法，哪一个物理块将被换出？并解释原因．（10分）
页号块号加载时间访问时间访问位R 修改位M
2 0 60 161 0 1
1 1 130 160 0 0
0 2 26 162 1 0
3 3 20 163 1 1
１．FIFO算法
２．LRU算法
３．CLOCK算法
４．当页面的访问串为：“4，0，0，0，2，4，2，1，0，3，2”的OPT算法
解：1．换出第3号虚页，因为它加载的时间最早；
2．换出第1号虚页，因为它最近最久没被访问；
3．换出第1号虚页，因为它最近既没被访问，又没被修改；
4．换出第3号虚页，因为它离访问点最远。
15．考虑一个有150个存储器单元的系统，如下分配给三个进程：
进程最大占有
————————————————————
1 70 45
2 60 40
3 60 15
使用银行家算法，以确定下面的任何一个请求是否安全：
a．第4个进程到达，最多需要60个存储单元，最初需要25个单元；
b．第4个进程到达，最多需要60个存储单元，最初需要35个单元；
如果安全给出安全序列；若不安全给出结果分配简表。（10分）
解：进程最大占有尚需可用————————————————————————
1 70 45 25 25
2 60 40 20
3 60 15 45
4 60 2
5 35
安全序列为：1、2、3、4
所以系统是安全的，可以进行分配。
b．
进程最大占有尚需可用————————————————————————
1 70 45 25 15
2 60 40 20
3 60 15 45
4 60 3
5 25
当前可用的资源不够任何一个进程运行完毕，所以不安全。
16. Jruassic 公园有一个恐龙博物馆和一个公园.有m个旅客和n辆车,每辆车只能容纳一个旅客。旅客在博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它载入一个旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客和n辆车的进程。（10分）
解：
visitors=m; cars=n; mutex=1;
Pvi() Pci()
{ repeat { repeat
wait(cars); wait(visitors);
wait(mutex); wait(mutex);
get on; start;
travell; run;
get off; stop;
signal(cars); signal(visitors);
wait(mutex); wait(mutex);
until false; until false;
} }
18、若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。
（1）先来先服务算法；
（2）最短寻道时间优先算法。
（3）扫描算法（当前磁头移动的方向为磁道递增）（10分）
解：
（1）磁道访问顺序为：20，44，40，4，80，12，76
寻道时间=（20+24+4+36+76+68+64）*3=292*3=876
（2）磁道访问顺序为：40，44，20，12，4，76，80
寻道时间=（0+4+24+8+8+72+4）*3=120*3=360
（3）磁道访问顺序为：40，44，76，80，20，12，4
寻道时间=（0+4+32+4+60+8+8）*3=116*3=348
19、生产者和消费者问题（10分）
有一组生产者P1，P2，……，PM和一组消费者C1，C2，……，CK，他们通过由n个环形缓冲区构成的
缓冲池进行通信，生产者把产品放入缓冲区，消费者从缓冲区取产品来消费。请用wait和signal原语
实现他们的同步操作。
解：生产者和消费者问题
begin
Var mutex,empty,full:semaphore:=1,n,0;
buffer:array[0,…,n-1] of item;
in,out:integer := 0,0;
parbegin
producer: begin
repeat
produce next product ;
wait (empty);
wait (mutex);
buffer(in):=nextp ;
in := (in+1) mod n ;
signal (full);
signal (mutex);
until false ;
end
consumer: begin
repeat
wait (full);
wait (mutex);
nextc := buffer(out);
out := (out+1) mod n;
signal (empty);
signal (mutex);
consume the item in nextc;
until false ;
end
parend end
21．今有三个并发进程R，M，P，它们共享了一个可循环使用的缓冲区B，缓冲区B共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“，”；进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。请用PV操作为同步机制写出它们能正确并发执行的程序。（10分）
解：（10分）
begin
Var mutex,input,calculate,output:semaphore:=1,n,0,0;
buffer:array[0,…,n-1] of item;
in,mid,out:integer := 0,0,0;
proR() { do {
wait (input);
wait (mutex);
buffer(in):=input data;
in := (in+1) mod n ;
signal (calculate);
signal (mutex);
while true ; }
proM() { do {
wait (calculate);
wait (mutex);
buffer(middle):=calculate data ;
mid := (mid+1) mod n ;
signal (output);
signal (mutex);
} while true ; }
proP() { do {
wait (output);
wait (mutex);
buffer(out):=calculate data ;
out := (out+1) mod n ;
signal (input);
signal (mutex);
} while true ; }
25、设某作业占有7个页面，如果在主存中只允许装入4个工作页面(即工作集为4)，作业运行时，实际访
问页面的顺序是：1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，1。试用FIFO、LRU
页面置换算法，列出各自的页面淘汰顺序和页面置换次数。假设开始时没有任何页在内存中。(10分)
解：FIFO：
1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，1
1 1 1 1 4 4 4 4 5 5
2 2 2 2 7 7 7 7 6
3 3 3 2 2 2 2 2
6 6 6 6 1 1 1
页面置换次数为：10次
LRU：
1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，1
1 1 1 1 4 4 4 1 1 1 1 6 6 6
2 2 2 2 7 7 7 4 4 4 4 2 2
3 3 3 3 3 3 3 7 7 7 7 7 1
6 6 6 2 2 2 2 5 5 5 5
页面置换次数为：14次
26、某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：
(1)用wait和signal操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。
(2)根据所定义的信号量，加上wait和signal原语，写出购票者进程的算法，以保证进程能够正确地并发执行。
(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。
解：(1)定义一信号量S，初始值为20。
意义：
S>0S的值表示可继续进入售票厅的人数
S=0表示售票厅中已有20名顾客(购票者)
S<0|S|的值为等待进入售票厅的人数
(2) int S=20;
COBEGIN PROCESS PI(I=1，2，……)
begin
进入售票厅；
wait(S)；
购票；
signal(S);
1.退出；
end；
COEND
(3)S的最大值为20
S的最小值为20－n
设input进程不断向缓冲区Q写入信息，output进程不断地将刚由input进程写入的信息读出。试问：
（1）这两个进程有何相互制约关系？
（2）试用P、V操作写出这两个进程完成这项任务的代码段和信号量的含义及初值。
答：（1）这两个进程的相互制约关系为同步关系；
（2）设两个信号量S1和S2。其中S1表示Q是否为空，初值为1，表示Q是空的；S2表示Q中是否有信息，初值为0，表示Q中无信息。
两进程的代码段如下：
input进程
{
……
while 信息未处理完毕{
加工一个信息；
P（S1）；
将信息放入Q中；
V（S2）；
……
} output进程
{
……
while 信息未处理完毕{
P（S2）；
从Q中读出一个信息；V（S1）；
……
}
2.两个并发执行的进程A和B的程序如下：
进程A while(true) {
N=N+5;
} 进程B
while(true) {
打印N的值；N=0；
}
其中N为整数，初值为4。若进程A先执行了三个循环后，进程A和进程B又并发执行了一个循环，写出可能出现的打印值。正确的打印值应该是多少？请用P、V操作进行管理，使进程A和B并发执行时不会出现与时间有关的错误。
答：因为N初值为4，若进程A先执行了三个循环，此时N的值为19。当进程A和进程B并发执行时可能会有如下两种执行次序，即进程A先执行一次循环，然后再进程B执行一次循环，此时打印的是正确值24，执行后N 中的值为0。但若进程B先执行一次循环，然后再进程A执行一次循环，则打印的值是19，执行后N中的值是5。这是错误的，即发生了与时间有关的错误。用P、V操作进行管理，使进程A和B并发时不会出现与时间有关的错误的程序如下：（S为互斥信号量，初值为1），
进程A while(true) {
P(S);
N=N+5;
V(S);
} 进程B
while(true) {
P(S);
打印N的值；N=0；
V(S);
}
3.假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：
作业进入系统时间估计运行时间/分钟
1 8:00 40
2 8:20 30
3 8:30 12
4 9:00 18
5 9:10 5
(1) 如果应用先来先服务的作业调度算法，试将下面表格填写完整。
作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟
1 8:00 40 8:00 8:40 40
2 8:20 30 8:40 9:10 50
3 8:30 12 9:10 9:22 52
4 9:00 18 9:22 9:40 40
5 9:10 5 9:40 9:45 35
作业平均周转时间T=
（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。
作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟
1 8:00 40 8:00 8:40 40
2 8:20 30 8:52 9:22 62
3 8:30 12 8:40 8:52 22
4 9:00 18 9:27 9:4
5 45
5 9:10 5 9:22 9:27 17
作业平均周转时间T=
答：（1）应用先来先服务的作业调度算法，表格填写如下：
作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟
1 8:00 40 8:00 8:40 40
2 8:20 30 8:40 9:10 50
3 8:30 12 9:10 9:22 52
4 9:00 18 9:22 9:40 40
5 9:10 5 9:40 9:45 35
作业平均周转时间T=43.4 217
（2）应用最短作业优先的作业调度算法，表格填写如下：
作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟
1 8:00 40 8:00 8:40 40
2 8:20 30 8:52 9:22 62
3 8:30 12 8:40 8:52 22
4 9:00 18 9:27 9:4
5 45
5 9:10 5 9:22 9:27 17
作业平均周转时间T=37.2 186
4.若在一分页存储管理系统中,某作业的页表如下所示.已知页面大小为1024字节,试将逻
辑地址1011,2148,4000,5012转化为相应的物理地址. ( 十进制除以1024 得出的整数（有余数）对应表格页号，得出相应的物理块号，
对应的物理块号*1024+余数=物理地址)
页号物理块号
0 2
1 3
2 1
3 6
答：本题中,为了描述方便,设页号为P,页内位移为D,则:
对于逻辑地址1011，P=INT(1011/1024)=0，D=1011 mod 1024=1011，查页表第0页在第2块,所以物理地址为3059.
对于逻辑地址2148，P=INT(2148/1024)=2，D=2148 mod 1024=100，查页表第2页在第1块,所以物理地址为1124.
对于逻辑地址4000，P=INT(4000/1024)=3，D=4000 mod 1024=928，查页表第3页在第6块,所以物理地址为7072.
对于逻辑地址5012，P=INT(5012/1024)=4，D=5012 mod 1024=916，因页号超过页表长度,该逻辑地址非法.
5.根据如下段表：
段号基地址长度合法（0）/非法（1）
0 300 200
1 7500 540
2 3000 1010
3 2000 100
（1）求出逻辑地址为[0，100]的物理地址并将其的合法性填入段上表适当位置；
（2）求出逻辑地址为[3，100]的物理地址并将其的合法性填入上表适当位置；
答：（1）物理地址为：300+100=400，合法性如下表所示。
（2）物理地址为：2000+100=2100，合法性如下表所示。
段号基地址长度合法（0）/非法（1）
0 300 200 0
1 7500 540
2 3000 1010
3 2000 100 1
6.在一个采用页式虚拟存储管理的系统中,有一用户作业,它依次要访问的字地址序列
是:115,228,120,088,446,102,321,432,260,167,若该作业的第0页已经装入主存,现分配给该作业的主存共300字,页的大小为100字,请回答下列问题:
(1)按FIFO调度算法将产生次缺页中断,依次淘汰的页号为,缺页中断率为.
(2)按LRU调度算法将产生次缺页中断,依次淘汰的页号为,缺页中断率为.
答：(1)按FIFO调度算法将产生5次缺页中断;依次淘汰的页号为:0,1,2;
缺页中断率为:5/10=50%
(2)按LRU调度算法将产生6次缺页中断;依次淘汰的页号为:2,0,1,3;
缺页中断率为:6/10=60%
7.某系统的进程状态图如下
(1)说明一个进程发生变迁1、3、4的原因是什么？
(2)下述因果变迁是否会发生?如果有可能的话,在什么情况下发生？
A)1-> 3 B)2->4 C) 4->1 D) 5->1 E) 3->2
低优先就绪
因I/O等待
运行
高优先就绪
2
3
1
4
5
解：（1）发生变迁1的原因是：当CPU空闲且高优先就绪队列中有进程，则从高优先就绪队列调一个进程到CPU上去执行。
发生变迁3的原因是：当一个在CPU上运行的进程用完它的时间片时，立即退出CPU 而进入低优先就绪队列。
发生变迁4的原因是：一个正在CPU上运行的进程需要输入或者输出数据时，退出CPU 而进入等待队列。
（2）A）和B）的因果变迁不可能发生。C）、D）和E）有可能发生，其原因是：
C）4->1：一个正在CPU上运行的进程需要输入或者输出数据时，退出CPU 而进入等待队列，CPU空闲，这时若高优先就绪队列中有进程，则发生调度1。
D) 5->1：当高优先就绪队列和CPU都处于空闲状态时，一个处于等待状态的进程被唤醒进入高优先就绪队列后立即被调度到CPU上去执行。
E) 3->2：当一个在CPU上运行的进程用完它的时间片退出CPU而进入低优先就绪队列时，若高优先就绪队列为空，则立即发生2（即调度低优先就绪队列中的一个进程到CPU上去执行）
