华东师范⼤学期末试卷（软院A卷）20012 －2013 学年第⼆学期课程名称：操作系统
学⽣姓名：_____________ 学号：__________________专业：软件⼯程年级/班级________________课程性质：专业必修⼀⼆三四总分阅卷⼈签名
1、判断题（请判断以下叙述的正误，⽤T和F表⽰，并对错误的叙述进⾏改正，说明理由。20分，每题2分）（ F ）1、分页或分段系统必须采⽤虚拟存储技术。
（ F ）2、以索引⽅式组织盘块（block）空间的⽂件中，索引表的每个表项描述⼀个⽂件盘块，含有相应盘块的逻辑盘块号和物理盘块号。
（ F ）3、最短寻道时间优先调度(SSTF)算法是每次选择离磁头当前位置最近的I/O请求，其寻道长度必然是最短的，但有可能出现饥饿现象。
（ F ）4. 微内核操作系统中，CPU调度、进程间通讯和虚存管理功能必须在微内核中实现。（ T ）5. 对于⿏标这样的低速字符设备，采⽤DMA⽅式进⾏数据交换是不合适的。（ F ）6. 在⽬录⽂件中，必须保存⽂件名和⽂件控制块信息。
（ F ）7. 在虚存管理时，采⽤先进先出（FIFO）页⾯替换策略，必然会发⽣Belady异常（即分配页框越多，缺页率反⽽越⾼）。
（ F ）8. 页表由各个进程⾃⼰管理，进程可在⽤户态对页表进⾏更新。
（ F ）9. 假脱机（spooling）⽅式常被⽤于处理字符设备（character device），如终端，的I/O操作。
（ F ）10. RAID技术有助于增强存储系统的可靠性（availability），降低存储系统的响应时间（response time），但是会降低访问的吞吐率（throughput）。2、单选题（30分，每题2分）
1、地址空间的容量只受___D___的限制。A.物理内存⼤⼩B.磁盘空间⼤⼩
C.内存和外存可使⽤总容量D.计算机地址位数
2、采⽤分段式存储管理的系统中，若地址⽤24位表⽰，其中8位表⽰段号，则允许每段的最⼤长度是__B____。A.224B.216C.28D.232
3、在分页系统中，⼀个进程的页表如下所⽰：
如果页⾯⼤⼩为4KB ，则逻辑地址0所对应的物理地址为 _A____。
A.8192B.4096C.2048D.1024
对于接下来的3个问题，假设某作业访问页⾯的顺序为 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2，分配给该作业三个内存块。４、采⽤FIFO 页⾯置换算法会产⽣ ___C_______ 次缺页中断。A. 7B. 8C. 9
D. 10 ５、采⽤LRU 页⾯置换算法会产⽣ ___C_______ 次缺页中断。A. 6B. 7C. 8
D. 9 ６、采⽤最优页⾯(OPT)置换算法会产⽣ __B________ 次缺页中断。A. 5B. 6C. 7D. 8
对于接下来的4个问题，假定某磁盘共有50个柱⾯（编号为0~49），如果在为访问12号柱⾯的请求者服务后，当前正在为访问14号柱⾯的请求者服务，同时有若⼲个请求者在等待服务，它们依次要访问的柱⾯号为：8、15、9、35、25、30、40和5（以上是按请求时间先后排序的），请选择最准确的答案。
７、如果采⽤先来先服务（FCFS ）调度算法，则满⾜所有这些请求过程中磁臂移过的总磁道数为 __B___。A. 50B. 105C. 120D. 130
８、如果采⽤最短寻道时间优先（SSTF ）调度算法，则满⾜所有这些请求过程中磁臂移过的总磁道数为 _A____。A. 46B. 47C. 48D. 49
3 3 6 2 1 1 Frame No. Page No. 74 0 2
９、如果采⽤电梯调度算法（SCAN），则满⾜所有这些请求过程中磁臂移过的总磁道数为_B____。A. 51B. 61
C. 79D. 44
1０、如果采⽤循环扫描（C-SCAN）调度算法，则满⾜所有这些请求过程中磁臂移过的总磁道数为__A___。A. 44B. 97C. 48D. 93
11. 以下哪⼀种程序（或程序⽚段）会⾃我复制、传播，进⽽威胁系统的安全？AA. 计算机病毒B. 特洛伊⽊马C. 逻辑炸弹
D. 操作系统⾃举（bootstrap）⽂件
12. 以下哪种存储设备通常只⽀持顺序访问？CA. 光盘B. 磁盘C. 磁带D. U盘
13. 当发⽣抖动（或称为颠簸，thrashing）时，以下哪种现象不会出现？BA. 处于等待（waiting）状态的进程数增多B. CPU利⽤率增⾼C. 磁盘I/O增多
D. 长程调度（long-term scheduling）允许更多的进程进⼊就绪（ready）状态14. 以下哪个功能不是由设备驱动程序提供的？CA. 提供标准的设备访问系统调⽤（如open(), read()等）B. 提供中断处理程序C. 提供DMA控制功能
D. 提供内核直接访问设备的接⼝
15. 以下哪种数据结构必须存放在持久存储介质上？CA. 进程控制块B. 页表C. ⽂件控制块D. 打开⽂件列表
3、简答题（25分，每题5分）
1、假定某请求分页系统中，内存有效访问时间（effective access time）为1微秒（1微秒=10-6秒），⼆级存储平均访问时间为10毫秒（1毫秒=10-3秒），试问如果希望虚拟存储系统的有效访问时间仅⽐内存增加不超过10%，则要求页⾯缺页率不⼤于多少？
答：设页⾯缺页率为f，则虚存的平均访问时间为：(1-f)*1+10000*f=1+9999f
如果希望虚存的平均访问时间相⽐内存增加不超过10%，则1+9999f<1*(1+10%) 也即1+9999f<1.1f<0.1/9999≈1/100000
2、假设某系统使⽤位图(bitmap)来管理空闲磁盘空间，⽽该位图在⼀次系统崩溃中损坏了，试问有没有办法恢复该位⽰图？如果可以，请简述重构该位⽰图的⽅法。并分析重构所需的代价。
答：先将位图所有位清零，然后从根⽬录开始，遍历搜索系统中的每个⽂件，对于找到的每个⽂件，获取分配给该⽂件的盘块信息，将位图中的相应位置为1，直⾄遍历结束，新的位图就重构好了。
3. 请简述在⼀个⽀持有向⽆环图⽬录结构的⽂件系统中，删除⼀个普通⽂件（⾮⽬录⽂件）时操作系统需要执⾏哪些操作。答：查看／更新引⽤计数，如果为零，更新⽬录⽂件，释放FCB，释放磁盘数据块
4. 请简述页⾯替换算法中的LRU替换与时钟算法（第⼆次机会），并详细⽐较两者各⾃的优缺点。答：要点：队列的维护代价
5. 请简述前向页表、反向页表、哈希页表（或称为散列页表）的数据结构，并分析其各⾃的优点。答：要点：空间代价，查找代价4、综合题（25分）
1（10‘）、假设⽂件系统的盘块⼤⼩为4KB, 某⽂件的物理存储⽅式采⽤链接⽅式，该⽂件⾸5个盘块的盘块号分别为20、54、80、95和100。假如要访问该⽂件的第15000字节单元，请回答以下问题：
（1）要访问的字节单元在哪个盘块上？其盘块号为多少？该字节单元是盘块内的第⼏字节？
（2）要访问该字节单元需要访问多少个盘块？试图⽰上述的访问过程。（假如该⽂件的FCB已载⼊内存）答：
该字节所在盘块的逻辑块号：B=15000/4096=3 （2分）所以该盘块的物理盘块号为：95 （2分）块内位移：S=15000 mod 4096=2712 （2分）该字节所在盘块为该⽂件的第四个盘块
所以，要依次访问前⾯三个盘块后才可以获取该第四个盘块的指针，⼀共要进⾏磁盘I/O操作的次数为: 3+1=4 （2分）图⽰上述的访问过程（略）（2分）
2（15’）. 假设有⽂件系统使⽤i-node如图所⽰。其中⼀个磁盘块⼤⼩为4KB，⼀个磁盘块指针⼤⼩为32位（4B），直接块（direct block）⼤⼩为2KB，其它索引块⼤⼩和⼀个磁盘块⼀样⼤⼩。假设有⼀个4MB⼤⼩的⽂件，其i-node已在内存中（direct block也在内存中），⽂件的其它部分都在磁盘上，不考虑缓存。请问：
a) 访问其第⼀个字节，第1K个字节，第1M个字节，第2M个字节，第3M个字节，和最后⼀个字节分别需要访问⼏个磁盘块（2'x5=10）？
b) 该⽂件系统最⼤能⽀持多⼤的⽂件(5')？
答：a) 1K: 1, 1M: 1, 2M: 1, 3M: 2, 最后：2 b) 2K/4*4K+4K/4*4K+4K/4*4K/4*4K
因篇幅问题不能全部显示，请点此查看更多更全内容