淮 海 工 学 院
11 - 12 学年 第 1 学期操作系统原理 试卷(B闭卷)
题号 一 A、该进程的优先级最高 B、就绪队列为空 C、该进程最早进入就绪队列 D、该进程是一个短进程
9、在操作系统中，用户程序申请使用I/O设备时，通常采用( )。 A、物理设备名 B、逻辑设备名 C、虚拟设备名 D、独占设备名
二 三 四 五 六 七 八 九 总 分 10、设3个目标模块A、B、C，起始地址都是0，长度分别是L、M、N，这3个模块按A、B、C顺序采用静态链接方式链接在一起后，模块C的起始地址变换为（ ）。
得分 一、单项选择题（本大题含20小题，每小题1分，共计20分）
答题表（将答案填入下表，否则不予评分）
题号 1 2 3 4 5 6 7 8 9 10 答案 题号 11 12 13 14 15 16 17 18 19 20 答案 1、操作系统是对（ ）进行管理的软件。 A、软件 B、硬件 C、计算机资源 D、应用程序
2、在进程管理中，当（ ）时，进程从运行状态变为就绪状态。 A、进程被调度程序选中 B、时间片用完 C、等待某一事件发生 D、等待的事件发生
3、银行家算法在解决死锁问题中是用于（ ）的。 A、预防死锁 B、避免死锁 C、检测死锁 D、解除死锁 4、下列步骤中（ ）不是创建进程所必须的。 A、建立一个进程控制块 B、为进程分配内存 C、将其控制块插入就绪队列中 D、为进程分配CPU 5、文件系统中用（ ）来管理文件。
A、作业控制块 B、外页表 C、目录 D、软硬件结合的办法 6、( )算法是设备分配常用的一种算法。
A、短作业优先 B、最佳适应 C、首次适应 D、先来先服务
7、多道程序环境下,操作系统分配资源以( )为基本单位。
A、程序
B、指令
C、进程
D、作业
8、在分时系统中，若当前运行的进程连续获得了两个时间片，原因可能是（ ）
A、L+M B、L＋M＋N C、L+M-1 D、M+N 11、操作系统最重要的特征是（ ）。
A、并发性 B、共享性 C、虚拟性 D、异步性 12、以时间换空间的技术是（ ）。
A．分时技术 B．虚拟存储技术 C．并发技术 D．缓冲技术 13、某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（ ）。 A、2 B、3 C、4 D、5 14、虚存指的是（ ）。
A、提高运算速度的设备 B、进程的地址空间及其内存扩充方法 C、容量扩大了的内存 D、实际不存在的存储器 15、在页面置换算法中，可能引起Belady现象的是（ ）。 A、FIFO B、LRU C、OPT D、CLOCK
16、在一般大型计算机系统中，主机对外设的控制可通过通道、设备控制器和设备这三个层次来实现，下面的叙述中正确的是（ ）。
A、通道和控制器分别控制设备 B、控制器可控制通道，设备在通道的控制下工作 C、通道控制控制器，设备在控制器控制下工作 D、控制器控制通道和设备工作 17、（ ）是解决进程间同步与互斥的一对低级通信原语。
A、lock和unlock B、P和V C、W和S D、send和receive 18、动态重定位技术依赖于( )。
A、重定位装入程序 B、重定位寄存器 C、地址结构 D、目标程序 19、临界区是指并发进程中共享临界资源的（ ）
A、内存区 B、数据区段 C、程序区段 D、管理信息 20、在SPOOLING系统中，用户进程实际分配得到的是（ ）。 A、用户所要求的外设 B、内存区，即虚拟设备 C、设备的一部分存储区 D、设备的一部分空间
１二、简答题（本大题共4小题，共20分）
1、什么是设备独立性？实现此功能后，可带来哪些好处？（4分）
2、简要叙述基于位示图进行盘块分配和回收的过程。（5分）
3、简述段页式管理的优缺点。（6分）
4、什么是文件的物理结构，主要有哪几类。（5分）
三、基础理论与应用题（本大题含6道小题，每题10分，共计60分）
1、三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用put()将一个正整数送入缓冲区的一个单元中，P2每次用getodd()从缓冲区中取出一个奇数，P3每次用geteven()从缓冲区中取出一个偶数。试用信号量机制实现这三个进程的互斥与同步活动，用伪代码实现。
２2、假如5个就绪进程其到达系统和所需CPU运行时间如下表所示（单位：毫秒），如果分别采用FCFS和非抢占式SPF（短进程优先调度）调度算法进行CPU调度和运行，请在表中按要求栏目给出各进程在调度和执行完成时产生的各种时间数据。
进到达运行开始时间 完成时刻 周转时间 带权周转时间 程 时刻 时间 FCFS SPF FCFS SPF FCFS SPF FCFS SPF A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 平均周转时间(FCFS)= 平均带权周转时间(FCFS)= 平均周转时间(SPF)= 平均带权周转时间(SPF)= 3、假设移动头磁盘有200个磁道(从0号到199号)。目前正在处理125号磁道上的请求，而刚刚处理结束的请求是43号，如果下面给出的顺序是按FIFO排成的等待服务队列顺序：86，147，91，167，94，150，192，175，130。若移臂调度分别用最短寻道时间优先SSTF和电梯算法SCAN，给出各种情况下的磁柱访问序列及磁头臂移动距离。
4、有一操作系统采用基本分页存储管理方式，若一进程的程序大小是10KB，页面大小为2KB，依次装入内存的第10、5、1、7、9块，试画出该进程的页表，并将虚地址7145转换成内存地址，分析执行虚地址12412所指指令时会产生什么结果。
３5、假设系统分配给某进程3个内存块，且进程开始运行时，这3个内存块是空的，按下列页号访问：2，3， 2， 1，5，2，4，5，3，2，5，2。缺页时采用局部置换方式，分别画出利用OPT和LRU页面置换算法时的置换图（或表），并计算其缺页率。
6、某系统有R1、R2、R3共3种资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况见下表，此时系统的可用资源向量为（2，1，2）。
资源 分配 进程 R1、R2、R3 R1、R2、R3 MAX ALLOCATION
４
P1 3 2 2 1 0 0 P2 6 1 3 4 1 1 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 试问：1）将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来。
2）若此时进程P1发出资源请求Request(1,0,1)，请用银行家算法讨论其资源分配及系统安全性。
淮 海 工 学 院
11 - 12学年 第 1 学期操作系统原理 试卷(B闭卷)答案 一、单项选择题（本大题共10小题，每题1分，共20分）
题号 1 2 3 4 5 6 7 8 9 10 答案 C B B D C D C B B A 题号 11 12 13 14 15 16 17 18 19 20 答案 A B C B A C B B C B 二、简答题（本大题共4小题，共20分） 1、答：设备独立性的含义是：应用程序独立于具体使用的物理设备。（2分） 好处：（1）提高了设备分配时的灵活性。（1分） （2）易于实现I/O重定向。（1分） 2、答：基于位示图的盘块分配过程为
（1）顺序扫描位示图，从中找出一个或一组值为0的二进制位（0表示空闲） （1分）
（2）将一个或一组二进制位转换成与之相应的盘块号。如第i行，第就j列，则相应的盘块号计算如下：
B=n(i-1)+j （1分）
(3)修改位示图,map(i,j)=1（1分） 盘块的回收分两步：
（1） 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：
i=(b-1)DIV n +1 （1分） j=(b-1) MOD n +1
（2）修改位示图。令map(i,j)=0（1分） 3、（6分）主要优点：a主存利用率高。（1分） b便于信息共享和存取保护。（1分）
c作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每一段分成若干个大小固定的页。对于主存空间的管理仍然和页式管理一样，将其分成若干个和页面大小相同的存储块。作业的地址结构包含三部分：段号、页号及页内偏移。（2分）
缺点：1)增加系统开销成本。（1分）2)存取时间较长。（1分） 4、5分）文件的物理结构是指一个文件在文件存贮器上存贮方式。它与文件的存取方法有密切关系。（2分）为了适应用户的应用要求，文件的物理结构基本上分
为连续、链接和索引三种。（各1分） 注：答全要点得全分，要点不全酌情减分。
三、基础理论与应用题（如遇答案不符者，请视情况酌情打分）
1、参考答案：（ 10分）
Semaphore empty=N,mutex=1,s1=s2=0; p1(){ p(empty); p(mutex); put();
if(是奇数) then v(s1); else v(s2) ; v(mutex); } p2(){
p(s1); p(mutex); getodd(); v(mutex); v(empty); } p3(){ p(s2); p(mutex); geteven(); v(mutex); v(empty); }
2、参考答案（ 10分）
进到达运行开始时间 完成时刻 周转时间 带权周转时间 程 时刻 时间 FCFS SPF FCFS SPF FCFS SPF FCFS SPF A 0 3 0 0 3 3 3 3 3/3 3/3 B 2 6 3 3 9 9 7 7 7/6 7/6 C 4 4 9 11 13 15 9 11 9/4 11/4 D 6 5 13 15 18 20 12 14 12/5 14/5 E 8 2 18 9 20 11 12 3 12/2 3/2 平均周转时间(FCFS)=（3+7+9+12+12）/5=8.6 平均带权周转时间(FCFS)= 2.56 平均周转时间(SPF)= （3+7+11+14+3）/5=7.6 平均带权周转时间(SPF)=1.84
５3、参考答案（ 10分）
SSTF移动顺序：125→130→147→150→167→175→192→94→91→86 移动距离=173
SCAN: 125→130→147→150→167→175→192→94→91→86 移动距离=173
4、参考答案（ 10分）
页号 块号 0 10 1 5 2 1 3 7 4 9 虚地址7145 P＝7145 ％ 2048 ＝3 W＝7145 mod 2048＝1001 MR=7*2048+1001=15337
虚地址7145的内存地址是：15337 虚地址12412
P＝12412 ％ 2048 ＝6
产生越界，进行异常中断处理。
5、参考答案（ 10分）
采用OPT页面置换算法，其页面置换表如下表所示： OPT 2 3 2 1 5 2 4 5 3 2 5 2 块1 2 2 2 2 2 2 4 4 4 2 2 2 块2 3 3 3 3 3 3 3 3 3 3 3 块3 1 5 5 5 5 5 5 5 5 缺Y Y Y Y Y Y 页
OPT :发生 6次缺页. f=6/12=50%
采用LRU页面置换算法，其页面置换表如下表所示：
LRU 2 3 2 1 5 2 4 5 3 2 5 2 块1 1 5 2 4 5 3 2 5 2 块2 3 2 2 1 5 2 4 5 3 2 5 块3 2 2 3 3 2 1 5 2 4 5 3 3 缺页 Y Y Y Y Y Y Y
LRU : 发生 7次缺页. f=7/12=58.3%
注：本答案为参考答案，还可能有另外的置换表，根据答题情况酌情批改
6、参考答案：（ 10分）
注本应用题答案为参考答案，根据答题情况酌情批改
６