学 院 班 级 东北大学考试试卷（A卷） … 总分 一 二 三 四 … … 2007—2008 学年第 二 学期
…课程名称：操作系统 …○┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄ … …学 号 …… …密姓 名 …… …… …○…………
…
封…
…
…
…
…○…………线………………………
………
得 分 一、在下列A、B、C、D答案中，选择一个最适合的填入（ ）中（共5分，每题1分） 1、以下调度算法中，为了使系统的吞吐量达到最大，应选择（ ）。 A. 先来先服务调度算法 B. 基于优先级的调度算法 C. 响应比高者优先调度算法 D. 短作业优先调度算法
2、CPU输出数据的速度远远高于打印机的打印速度，为了解决这一矛盾，可采用
（ ）。
A. 通道技术 B. 缓冲技术 C. 虚存技术 D. 并行技术
3、使用虚存或自动覆盖技术提供比实际内存更大的空间。其中，由操作系统控制的方式包括（ ） A. 交换 B. 请求调入 C. 预调入 D. A、B、C均是 4、在生产者—消费者进程中，采用P、V原语实现，设：Full是缓冲区“满”数目，
Empty是缓冲区“空”数目，Mutex用于访问缓冲区时的互斥，则下列进程描述
（ ）是正确的。 A. 生产者：P(Empty); P(Mutex); …; V(Mutex); V(Full) 消费者：P(Full); P(Mutex); …; V(Mutex); V(Empty) B. 生产者：P(Mutex); P(Empty); …; V(Mutex); V(Full) 消费者：P(Full); P(Mutex); …; V(Mutex); V(Empty) C. 生产者：P(Empty); P(Mutex); …; V(Mutex); V(Full) 消费者：P(Mutex); P(Full); …; V(Mutex); V(Empty) D. A、B、C均不正确 5、为解决不同用户文件的“命名冲突”问题，通常在文件系统中采用（ ）。 A. 约定的方法 B. 多级目录 C. 路径 D. 索引
得 分 二、填空（共10分，每题1分） 1、操作系统的两个基本特征是并发和（ ）。 2、作业A、B、C在某时刻同时到达，预计运行时间分别为2、4、6分钟，按时间片轮转（时间片=1分钟，按照A、B、C顺序轮转），则作业的平均周转时间为（ ）分钟。 3、某系统中有m个并发进程，都需要同类资源n个，试问该系统不会发生死锁的最少资源数是（ ）。 4、在一个单处理机操作系统中，PCB表的规模是n行，则任一时刻，最多可能有（ ）个进程处于就绪态。
5、采用段式存储管理的存储系统中，若地址用16位表示，其中6位表示段号，
则允许段的最大长度是（ ）。 6、当前磁盘读写位于磁道号20，此时有多个磁盘请求，按照到达的顺序分别处于第10、22、20、2、40、6、38磁道。寻道时，移动一个磁道需6?s，按照先来先服务算法，所需寻道时间为（ ）?s。 7、在请求页式存储管理管理中，Belady现象是指采用FIFO页面淘汰算法时，当分配的页面数增加，（ ）的次数有时反而减少。 8、假定磁盘块的大小为1KB，对于1.2MB的软盘，该磁盘对应的位视图需占用（ ）字节的存储空间。 9、对于两个并发进程，设互斥信号量为mutex，若有一个进程进入临界区，另一个进程等待进入，则mutex为（ ）。 10、SPOOLING技术，也称假脱机技术，实质是将（ ）设备转化为共享
设备的技术。
得 分
三、简答题（共15分，每题3分） 1、同学甲在他的程序a.c中使用了如下语句：open(“a.txt”, “w+”); 同学乙在Unix操作系统提示符下进行如下操作：$ ln a.c \\d1\\b.c；同学丙在Windows XP操作系统中通过双击文件a.exe的图标执行该文件。请问甲、乙、丙三位同学分别使用了操作系统提供的哪种接口，并分别简述相应的接口。
共4页 第1页 学 院 班 级 学 号 姓 名
…2、作业调度算法从用户角度应考虑公平性。请分析响应比高者优先调度算法对于…长作业和短作业的公平性（说明是否公平，并说明理由）。
… … …
○… 3、三个用户user1~user3，对文件F1~F5及打印机、绘图仪的访问权限如图所示（注：…[ ]中表示允许的访问），试填写表中所示的访问矩阵。 …
… …user2 User3 User1 密…F2[RW] F3[R] …F1[R] F4[RWE] 打印机[W] F6[RWE] F5[RW] 绘图仪[W] … …
…○ F1 F2 F3 F4 F5 F6 打印机 绘图仪 …user1 …user2 …user3 …
…4、假设操作系统可以根据空闲块的情况动态调整文件的物理存储结构，现在，有封一个文件需要5个数据块，磁盘的空闲块如下列条件时，仅从便于访问文件的…角度，应分别采用什么存储结构？为什么？ …(1) n（n>5）个连续空闲块 (2) 5个不连续的空闲块 …(3) n（n>5）个不连续的空闲块。 … … ○ … … …
…线5、某操作系统采用动态分区方式管理内存，内存空间为640K，高端40K用来存…放操作系统。在时刻t，内存布局如图所示（▓表示占用，□表示空闲）。现有
…一进程欲申请39K内存空间，请分别标记出采用最佳匹配法和最坏匹配法为之……分配的区域，并从内存空间利用的角度对这两种分配法进行评价。
… …OS …0 60K 110K 150K 250K 300K 340K 385K 430K 600K 640K ……
……… 得 分
四、解析题（共40分，每题5分）
1、考虑一个共有150个存储单元的系统（假设未采用虚拟存储和其它内存扩充技术），时刻t内存的分配情况如下（单位为存储单元的个数）：
进程 最大需求 已分配 P1 70 45 P2 60 40 P3 60 15
使用银行家算法，确定是否可以同意下面的请求并说明理由（如果同意请求，请写出相应的安全序列及其生成过程）。
（1）在时刻t进程P4到达，最多需要60个存储单元，最初需要25个单元； （2）在时刻t进程P4到达，最多需要60个存储单元，最初需要35个单元。。
2、在一个请求分页存储管理系统中，一个进程的页面走向为1、2、3、4、2、1、
5、6、2、1、2、3、7、6、3、2、1、2、3、6，分配给该进程的物理块数为4，试计算采用下述页面淘汰算法时的缺页率（假设开始执行时主存中没有页面）。 （1）先进先出淘汰算法； （2）最近最久未使用淘汰算法；（3）最佳淘汰算法。
共4页 第2页
学 院 班 级 ……………○…………3、某文件系统采用直接索引和间接索引的混合索引结构，其索引数组如图所示，
共有6个索引项，其中前4个索引项（编号0-3）是直接索引项，直接指出磁盘块的地址，第5、6个索引项（编号分别为4、5）都是一级间接索引。某文件的索引结构已在图中给出。假设每个磁盘块大小为512字节，每个磁盘块号占4个字节，试回答：
（1）某进程分别要读取文件中字节偏移为1200、3000、69000处的数据，应该
如何找到它们所在的磁盘块及块内位移量？（请分别写出所找到的磁盘块及块内位移量，并写出计算过程。） （2）以这样的结构组织的文件最多可为多少字节？
4、有四道作业，它们的提交时间和运行时间如下表：
作业号 1 2 3 4 提交时间（时） 8：00 8：50 9：00 9：50 运行时间（小时） 2.0 0.5 0.2 0.3 优先级（1最高） 3 1 2 4 如果系统采用单道程序设计技术，对下面每种调度算法，分别计算作业的平均周转时间。
学 号 姓 名
… 密……………0 ○1 …2 …3 …4 …5 …封……………○……… … 线 … … …… … … … … … …
…… 294块 587 0 35 1 165 2 索引数组 421 3 356 333 4 78 321 5 765 125 6 99 … 526 294 433 433块 778 0 646 1 66 2 427 3
429 4 391 5 888 6 … 200
（1）最高优先级优先； （2）FIFO； （3）短作业优先。
5、建设银行东北大学营业部共有3个服务窗口，为避免顾客无目的的排队等待，在门口设置一个取号码机，取号码机对顾客互斥使用，得到号码的顾客才能被窗口
呼叫，如果此时未被呼叫，则顾客需要等待（设取到号码等待服务的顾客数不限），窗口空闲时，呼叫顾客并为之服务。试用P、V原语和信号量描述顾客进程和服务窗口进程。
共4页 第3页
学 院 ……………○6、某系统采用成组链接法管理磁盘的空闲空间，目前磁盘的状态如图所示。 （1）该磁盘目前还有多少个空闲盘块？
（2）现为某个文件分配3个盘块，画出分配后空闲块的链接情况
（3）在（2）的基础上，系统要删除一文件，并回收它所占的4个磁盘块，分别
为700、711、703，723，画出分配后空闲块的链接情况
7、某虚拟存储器的用户空间共有32个页，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号分别为5、10、4、7。试回答： （1）写出逻辑地址和物理地址的格式；
（2）虚拟地址0A5CH对应的物理地址是多少？
（3）画图表示该虚拟地址映射到物理地址的变换过程。 班 级 学 号 姓 名
… …………密…………… ○ … … … … … 封 … … … … … ○ … … … … 线 … … … … … … … … … …
…… 空闲磁盘块栈 2 300 299 300 50 350 349 . . . 302 301 350 50 400 401 . . . 352 351 400 50 0 449 . . . 402 401
8、缓冲池中包括空闲缓冲区、输入缓冲区、输出缓冲区三种队列，有CPU读入、
CPU写出、设备输入和设备输出四种操作，如图所示。其中输入缓冲区用于存放设备向CPU的输入数据，输出缓冲区用于存放CPU向设备的输出数据，空闲缓冲区用于存放输入或输出数据。
缓冲池 输入缓冲区队列 输入 读入 设备 空缓冲区队列 CPU 输出 写出 输出缓冲区队列
假设三种队列分别是互斥使用的，试结合 P、V操作描述“设备输入”这一操作
使用缓冲池的过程。
共4页 第4页