1. 某个采用段式存储管理的系统为装入主存的一个作业建立了段表SMT，如表1所示。
段号 段长 主存起始地址 0 1 2 3 4
660 140 100 580 960 2219 3300 90 1237 1959 次序 进程 申请量 1 2 3 4 5 6 … R P Q P R Q … 2 4 2 2 1 2 … 表1段表 表2进程资源申请表 (1) 给出段式地址转换过程。
(2) 计算该作业访问的内存地址(0，432) ，(1，10) ，(2，500)，(3，400) 时的绝对地址。
2. 假设系统有同类资源10个，供P、Q、R三个进程共享，P、Q、R所需资源总数分别为8、4、9，它们申请资源的次序和数量如表2所示。
按银行家算法为它们分配资源：
(1) 写出执行完序号为6的申请时，各进程的状态和已占的资源数。 (2) 请估计系统是否会出现死锁，并简要说明理由。
3. 有一个理发师，一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发椅子上睡觉；当一个顾客到来时，必须唤醒理发师，进行理发；如果理发师正在理发时，又有顾客来到，则如果有空椅子可坐，他就坐下来等，如果没有空椅子，他就离开。为理发师和顾客各编一段程序描述他们的行为，要求不能带有竞争条件。
二、综合题(50分)
1. 计算进程PC和打印进程P01、P02共享一个单缓冲区，计算进程负责计算，并把计算结果放入单缓冲中；打印进程P01、P02则负责从单缓冲中取出计算结果进行打印，而且对每个计算结果，P01和P02都需分别打印一次。请用记录型信号量描述上述进程间的同步关系。
2. 假设磁盘有200个磁道，磁盘请求队列中是一些随机请求，它们按照到达的次序分别处于98、183、37、122、14、124、65、67号磁道上，当前磁头在53号磁道上，并向磁道号减小的方向上移动。请给出按FCFS、SSTF、SCAN及CSCAN算法进行磁盘调度时满足请求的次序，并计算出它们的平均寻道长度。
3. 假设某多道程序设计系统中有供用户使用的内存100KB，打印机1台。系统采用可变分区方式管理内存：对打印机采用静态分配，并假设输入输出操作的时间忽略不计；采用最短剩余时间优先的进程调度算法，进程剩余执行时间相同时采用先来先服务算法；进程调度时机选择在执行进程结束时或有新进程到达时。现有一进程序列如表3所示：
进程号 进程到达时间/s 要求执行时间/s 要求主存量/B 申请打印机数/台 1 2 3 4 5 0 4 10 11 16 8 4 1 20 14 15K 30K 60K 20K 10K 1 1 0 1 1 假设系统优先分配内存的低地址区域，且不许移动己在主存中的进程，请问： (1) 给出进程调度算法选中进程的次序，并说明理由。 (2) 全部进程执行结束所用的时间是多少
三、综合题(50分)
1. 在一个分页存储管理系统中，页面大小为4KB，系统中的地址寄存器占24位．假定页表如表6所示： 现假定一逻辑地址，页号为3，页内地址为20，试设计相应的物理地址，并画图说明地址变换过程。
2. 假定磁盘的存取臂现在正处于8号柱面上，有如表7所示的四个请求者等待访问磁盘，试写出最省时的响应顺序，并计算存取臂移动的总量：
页号 块号 0 3 1 4 2 9 3 7 请求者 柱面号 磁道号 块号 1 9 6 3 表1 2 3 4 7 20 15 5 20 15 6 6 2 表2 3. 有一只笼子，每次只能放一只动物，猎手向笼中放猴子，农民向笼中放猪，动物园等买笼中的猴子，饭店等买
笼中的猪，试用P、V操作写出它们能同步执行的程序。
四、综合题(50分)
1. 有三个进程Pl，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源Sl和S2；进程P3需用资源S2和Sl。回答；
(1) 若对资源分配不加限制，会发生什么情况 为什么
(2) 为保证进程正确工作，应采用怎样的资源分配策略 为什么
2. 设有五道作业，它们的提交时间和运行时间见下表，试给出在如表8所示的两种调度算法下，作业的执行顺序和平均周转时间：
(1) 先来先服务调度算法。 (2) 短作业优先调度算法 作业名 提交时间/h 需执行时间/h J1 J2 J3 J4 J5 表2 时间 1 2 3 4 5 6 7 8 9 10 P M=3 F 6 0 1 2 0 3 0 4 2 3 表3 3. 在一个请求分页存储管理中，一个程序的页面走向为6，0，1，2，0，3，0，4，2．3，采用LRU页面置换算法，设分配给该程序的存储块数M=3，每调进一个新页就发生一次缺页中断。
(1) 试完成表9：
(2) 求：缺页中断次数F=______。 缺页率 f=______。
五、综合题(50分)
1. 系统采用不能移动己在主存中的作业的可变分区管理主存。现有用户可用空间100KB，系统有4台打印机。有一批作业如表13所示： 作业号 到达时间 运行时间/s 需主存量/KB 需打印机数 1 2 3 4 5 10：00 10：20 10：30 10：35 10：40 25 30 10 20 15 15 60 50 10 30 2 1 3 2 2 系统采用多道程序设计技术，资源的静态分配法，忽略设备工作时间和系统进行调度所花的时间。请分别给出采用FCFS、短作业优先调度算法运行时作业的调度顺序和其平均周转时间。
2. 请用信号量解决以下的“过独术桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。
3. 某个文件系统，采用混合索引分配方式，其FCB中共有13个地址项，每个盘块的大小为512字节，回答问题： (1) 如果每个盘块号只需要用2个字节来描述，则该系统需要设置几次间址项
(2) 如果每个盘块号需要用3个字节来描述，并允许每个盘块中存放170个盘块地址，而且系统采用10个直接地址项、1个一次间址项、1个二次间址项和1个三次间址项，则对某个长度为B的文件．它需占用多少个盘块(包括间址块)
六、综合题(30分)
1. 设有两个进程P1和P2的程序如下，其信号量的初始值S1=S2=0，试求P1，P2并发执行结束后的x，y，z的值，并对结果加以解释。
进程l 进程2
页号 块号 状态 y=1 x=1 1 2 3 4 5 6 7 8 请求次序 0 24 1 y=y+2； x=x+1； 访问的柱面号 73 68 100 120 60 108 8 50 1 26 1 V(S1) ； P(Sl) ；
2 32 1 z=y+1; x=x+y;
表3 3 0 P(S2) ； V(S2) ；
4 0 表2 y=y+z; z=z+x；
2. 在一个请求分页管理的系统中，主存容量为1MB，被划分为256块，每块为4KB。现有一作业，它的页面变换表如下：
(1) 若给定一逻辑地址为9016，其物理地址为多少
(2) 若给定一逻辑地址为12300，给出其物理地址的计算过程。
3. 假定在某移动臂磁盘上，刚刚处理了访问75号柱面的请求，目前正在80号柱面读信息，并且有下述请求序列等待访问磁盘：
试用电梯调度算法和最短寻找时间优先算法，分别列出实际处理上述请求的次序。
七、综合题(30分)
1. 在银行家算法中，若出现以下资源分配情况； 试问：(1) 该系统状态是安全的吗
(2) 如果进程依次有如下资源请求，系统将怎样进行资源分配 P1：(1，0，2)、P4：(3，3，0)、P0：(0，2，0)
2. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：
(1) 用P、V操作管理这些并发进程时，应怎样定义信号量写出信号量的初值以及信号量各种取值的含义。 (2) 根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。 COBEGIN PROCESS PI(I=l，2，…) Begin 进程 需要的最大资源数 已分配资源 剩余资源 [ ]； P0 7，5，3 0，1，0 3，3，2 进入售票厅； P1 3，2，2 2，0，0 购票： P2 9，0，2 3，0，2 [ ]： P3 2，2，2 2，1，1 退出； P4 4，3，3 0，0，2 End
表1 COEND
(3) 若欲购票者最多为n个大，写出信号量可能的变化范围(最大值和最小值)
八、综合题(30分)
1. 如磁盘的每个磁道分成9个块，现有一文件共有A，B，…，I，9个记录，每个记录的大小与块的大小相等，设磁盘转速为27ms/转，每读出一块后需要2ms的处理时间。若忽略其他辅助时间，试问：
(1) 如果顺序存放这些记录并顺序读取，处理该文件要多少时间 (2) 如果要顺序读取该文件，记录如何存放处理时间最短
2. 在UNIX System V中，如果一个盘块的大小为1KB，每个盘块号占4B，那么，一个进程要访问偏移量为263168B处的数据时，需要经过几次间址
3. 设公共汽车上，司机和售票员的活动如图9-2所示。
在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系 用信号量和P、V操作实现它们的同步。
司机的活动售票员的活动启动车辆关车门正常行驶售票到站停车开车门九、综合题(30分)
1. 讨论操作系统可以从哪些角度出发，如何把它们统一起来 2. 某系统的进程状态转换图如图3所示，请说明：
进 已分配 (1) 引起各种状态转换的典型事件有哪些
程 A B C D (2) 当我们观察系统中某些进程时，能够看到某一进程产生的
P0 0 0 3 2 一次状态转换能引起另一进程作一次状态转换。在什么情况下，
P1 1 0 0 0 当一个进程发生转换3时能立即引起另一个进程发生转换
P2 1 3 5 4 (3) 试说明是否会发生下述因果转换：
P3 0 3 3 2 2→1 3→2 4→1
P4 0 0 1 4 3. 在银行家算法中，若出现下述资源分配情况：
试问：(1) 该状态是否安全
(2) 如果进程P2提出请求Request(1，2，2，2) 后，系统能否将资源分配给它
需要 剩余 A B C D A B C D 0 0 1 2 1 7 5 0 2 3 5 6 0 6 5 2 0 6 5 6 表2 1 6 2 2 十、综合题(30分)
1. 山上有一个隧道，规定每次只允许一列火车过隧道，现在南方北方都有车要过隧道。如果把每个过隧道者看作一个进程，为保证安全，请用P、V操作实现正确管理。
2. 什么叫联想存储器 试说明利用联想存储器在页式管理方案中实现动态地址变换的过程。
3. 一个好的页面替换算法应使缺页中断次数最少，一种方法是将正使用的页均匀地分散在整个存储区中。可以给每一页块附加一个计数器，用它记录与该页块相关的页的个数。当进行页面替换时，选择其计数器之值最小的那个页块。
(1) 利用上述思想，提出一个页面昔换算法，并回答下面的问题： A. 该计教器的初值是多少 B. 该计数器何时增值 C. 该计数器何时减值 D. 如何选择被替换的页
(2) 若有4个页块，给定下面的页访问串，使用你的算法将会出现多少次缺页中断 1、2、3、4、5、3、4、1、6、7 8、9、7、8、9、5、4、5、4、2
(3) 给定(2) 中同样的条件和访问串，若采用最佳页面替换算法，其缺页中断次数的最小值是多少
4. 进程A1，A2，…，An1，通过m个缓冲区向进程B1，B2，…．Bn2不断地发送消息。发送和接收工作遵循如下规则：
(1) 每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度。 (2) 对每一个消息，B1，B2，…，Bn2都须各接收一次，读入各自的数据区内。 (3) m个缓冲区都满时，发送进程等待：没有可读的消息时．接收进程等待。 试用P、V操作组织正确的发送和接收工作。
2、有一个系统其内存容量为1024KB，有8个作业同时到达，各作业需要的内存量和运行时间如表所示：
作业编号 需要内存量（KB） 运行时间（s） 1 2 3 4 5 6 7 8 140 80 100 60 50 30 15 20 3 1 3 2 1 3 2 3 表2 页号 页框号 装入时刻 0 1 2 3 7 4 2 9 130 230 200 160 有效位 （存在位） 1 1 1 1 表3 假定系统初启时，将内存1024KB按作业的编号顺序分给各道作业，并假定是多CPU下，分配到内存的作业都可以立即运行。问：（1）1s后，内存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接（2）2s后，其内存空白区按上述两种算法如何链接（3）在（2）后，此时有一个作业9要求进入内存，它需要内存量为12KB，按上述两种算法，将把哪一块空白区分给它
3、设某计算机的逻辑地址空间和物理地址空间都是64KB，按字节编址。若某进程最多需要6页（page）数据存储空间，每页大小为1KB。操作系统采用固定分配局部淘汰策略为此进程分配4个页帧（page frame）。
当该进程执行到时刻260时，需要访问逻辑地址17CAH的数据，请回答下列问题： （1）该逻辑地址对应的页号是多少
（2）若采用先进先出（FIFO）换页算法，该逻辑地址对应的物理地址是多少要求给出计算过程。 （3）若采用时钟（Clock）换页算法，该逻辑地址对应的物理地址是多少要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指示第2页，示意图如下）
随机分布的扇区0号磁道图4 图3 3号页2号页磁头移动方向0号页1号页100号磁道
4、假设计算机系统采用C-LOOK磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。 （1）请说明在上述条件下应如何管理磁盘空闲空间
（2）设磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻磁头位于100号磁道，并沿着磁道号增大的方向移动（如下图所示）。磁道号请求队列为90、30、50、120。对请求队列中每个磁道需读取一个随机分布的扇区，则读完这些扇区共需要多少时间要求给出计算过程。
5、假设系统中有三类资源（A，B，C）和三个进程（P1，P2，P3），假设在某时刻系统有如下状态
Allocation Max Request Available A B C A B C A B C A B C P1 1 2 4 2 5 8 1 2 1 1 3 3 P2 0 3 3 4 4 4 3 0 0 P3 4 1 1 5 4 4 1 2 2
请问为了使系统保持安全状态，应该如何处理P1、P2、P3的资源请求说明理由。 6、在一个单道批处理系统中，一组进程的提交时间和运行时间如下表所示 试计算以下三种进程调度算法的平均周转时间和平均带权周转时间： （1）先来先服务； （2）短作业优先； （3）响应比高者优先。
7. 某个采用段式存储管理的系统为装入主存的一个作业建立了段表SMT，如表9-1所示。 (1) 给出段式地址转换过程。
(2) 计算该作业访问的内存地址(0，432) ，(1，10) ，(2，500，(3，400) 时的绝对地址。
进程 提交时间 运行时间 1 2 3 4 8：00 8：50 9：00 9：10 段号 段长 主存起始地址 表6 0 1 2 3 4 660 140 100 580 960 2219 3300 90 1237 1959 表7 14、有座东西方向架设、可双向通行的单车道简易桥，最大载重负荷为4辆汽车。请定义合适的信号量正确使用wait操作、signal操作，实现双向车辆的过桥过程。
15、现有文件P供多个进程共享，将这些进程分成A、B两组，同组进程可以同时读文件P，当有A组（或B组）进程在读文件P时，不允许B组（或A组）进程读文件P。试用wait、signal操作实现两组进程对文件的读过程。
因篇幅问题不能全部显示，请点此查看更多更全内容