45.（7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。

（1）请说明在上述条件下如何进行磁盘块空闲状态管理。

（2）设某单面磁盘旋转速度为每分钟6000转。每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号大的方向移动（如下图所示），磁道号请求队列为50、90、30、120，对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这4个扇区点共需要多少时间？要求给出计算过程。 （3）如果将磁盘替换为随机访问的Flash半导体存储器（如U盘、SSD等），是否有比CSCAN更有效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。

46.（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框（Page Fame）。在时刻260之前该进程访问情况如下表所示（访问位即使用位）。

页号 0 1 2 3 页根号 7 4 2 9 装入时刻 130 230 200 160 访问位 1 1 1 1 当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题： （1）该逻辑地址对应的页号是多少？

（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。

（3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，示意图如下。）

二、答案

23-27：ACBAD 28-32：BBCCB 45. （1）可采用位示图法表示磁盘块的空闲状态，一个磁盘块在位示图中用一个二进制位表示，为0表示磁盘块空闲，为1表示磁盘块已分配。16384个磁盘块共占用16384bit=16384/8B =2048B=2KB，正好可放在系统提供的内存中。

（2）采用CSCAN调度算法，磁道的访问次序为120 30 50 90，如下图所示： 100 120

30 90 50

因此访问过程中移动的磁道总数为（120-100）+（120-30）+（90-30）=170，故总的寻道时间为170*1ms=170ms；

由于每转需要1/6000分钟=10ms，则平均旋转延迟时间为10ms/2 =5ms，总的旋转延迟时间为5ms*4=20ms；

由于每个磁道有100个扇区，则读取一个扇区需要10ms/100 = 0.1ms，总的读取扇区时间（传输时间）为0.1ms*4=0.4ms；

综上，磁盘访问总时间为170ms+20ms+0.4ms=190.4ms。

（3）采用FCFS（先来先服务）调度策略更高效。因为Flash半导体存储器的物理结构不需要考虑寻道时间和旋转延迟时间，可直接按I/O请求的先后顺序服务。 46.

（1）由于计算机的逻辑地址空间和物理地址空间均为64KB=216B，按字节编址，且页（块）的大小为1KB=210B，所以计算机的逻辑地址结构和物理地址结构均为： 页（页框）号 （6位） 页（块）内偏移量 （10位） 17CA H=(0001 0111 1100 1010)2，所以17CAH对应的页号是(000101)2=5。

（2）若采用先进先出（FIFO）置换算法，则置换装入时间最早的页，故0号页被置换，将5号页装入7号页框，所以17CA H对应的物理地址为（0001 1111 1100 1010）2=1FCA H。 （3）若采用时钟（CLOCK）置换算法，则从当前指针指示页框开始查找，若其中页的访问位为0，则置换该页，否则将访问位清零，并将指针指向下一个页框，继续查找。由于初始时内存中的4个页的访问位均为1，因此，前4次查找并未找到合适的页，但查找时已将对应页的访问位清零，第5次查找时，指针重新指向2号页框，其中存放的2号页的访问位为0，故置换该页，将5号页装入2号页框，所以17CA H对应的物理地址为（0000 1011 1100 1010）2=0BCA H。

2011年计算机专业考研真题——OS

一、试题

23. 下列选项中，满足短任务优先且不会发生饥饿的调度算法是（）。

A. 先来先服务 B. 高响应比优先 C. 时间片轮转 D. 非抢占式短任务优先 24 下列选项中，在用户态执行的是（）。

A. 命令解释程序 B. 缺页处理程序 C. 进程调度程序 D. 时钟中断处理程序

【解析】缺页处理与时钟中断都属于中断，会对系统造成影响，因此只能在核心态执行。进程调度属于系统的一部分，也只能在核心态执行。命令解释程序属于命令接口，是操作系统提供给用户使用的接口，可以再用户态执行。

25. 在支持多线程的系统中，进程P创建的若干个线程不能共享的是（）。

A. 进程P的代码段 B. 进程P中打开的文件 C. 进程P的全局变量 D. 进程P中某线程的栈指针 26. 用户程序发出磁盘I/O请求后，系统正确的处理流程是（）。

A. 用户程序→系统调用处理程序→中断处理程序→设备驱动程序 B. 用户程序→系统调用处理程序→设备驱动程序→中断处理程序 C. 用户程序→设备驱动程序→系统调用处理程序→中断处理程序 D. 用户程序→设备驱动程序→中断处理程序→系统调用处理程序 27. 某时刻进程的资源使用情况如下所示。 进程 P1 P2 P3 P4 已分配资源 R1 2 1 0 0 R2 0 2 1 0 R3 0 0 1 1 R1 0 1 1 2 尚需资源 R2 0 3 3 0 R3 1 2 1 0 0 2 1 可用资源 R1 R2 R3 此时的安全序列是（）。 A. P1, P2, P3, P4 B. P1, P3, P2, P4 C. P1, P4, P3, P2 D. 不存在 28. 在缺页处理过程中，操作系统执行的操作可能是（）。 Ⅰ. 修改页表 Ⅱ. 磁盘I/O Ⅲ. 分配页框

A. 仅Ⅰ、Ⅱ B. 仅Ⅱ C. 仅Ⅲ D. Ⅰ、Ⅱ和Ⅲ 29. 当系统发生抖动（thrashing）时，可以采取的有效措施是（）。 Ⅰ. 撤销部分进程

Ⅱ. 增加磁盘交换区的容量 Ⅲ. 提高用户进程的优先级 A. 仅Ⅰ B. 仅Ⅱ C. 仅Ⅲ D. Ⅰ、Ⅱ

30. 在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（）。

A. 编辑 B. 编译 C. 连接 D. 装载

31. 某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100μs，将

缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。在单缓冲区和双缓冲区结构下，读入并分析该文件的时间分别是（）。

A. 1500μs、1000μs B. 1550μs、1100μs C. 1550μs、1550μs D. 2000μs、2000μs

32. 有两个并发进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。

//加1操作 //减1操作 load R1,x //取x到寄存器R1中 load R2,x inc R1 dec R2 store x,R1 //将R1的内容存入x store x,R2 两个操作完成后，x的值是（）。

A. 可能为-1或3 B. 只能为1 C. 可能为0、1或2 D. 可能为-1、0、1或2 45. （8分）某银行提供1个服务窗口和10个顾客等待座位。顾客到达银行时，若有空座位，则到取号机领取一个号，等待叫号。取号机每次仅允许一个顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下： cobegin { process 顾客i { 从取号机获得一个号码； 等待叫号； 获得服务； } process 营业员 { while(true) { 叫号； 为顾客服务； } } } coend

请添加必要的信号量和P、V（或wait()、signal()）操作实现上述过程的互斥和同步。要求写出完整的过程，说明信号量的含义并赋初值。

46.（7分）某文件系统为一级根目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。

（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块，需要在FCB中设置哪些相关描述字段？

（2）为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。

二、答案