答案仅为参考
1.Which of the following scheduling alogrithms could result in starvation and why?
(1)First-come,first-served
(2)Shortest job first
(3)Round robin
(4)Priority【来自课后习题】
答：最短工作优先调度和优先级调度算法会引起饥饿。

优先级调度算法会使某个低优先级进程无穷等待CPU，此时，可能发生两种情况，要么进程最终能进行，要么系统最终崩溃并失去所有未完成低优先级进程。

解决方式——老化，老化是一种技术，以逐渐增加在系统中等待很长时间的进程的优先级。

（最短工作优先调度会使工作长度最大的进入无限等待CPU）
2.Can a resource allocation graph (资源分配图) have cycle without deadlock（死锁）? If so,state why and draw a sample graph（画一个死锁点的图）; if no,state why not?
答：有死锁，死锁部分为P2-R4-P5-R3。

3.What is the cause of thrashing(颠簸)? How dose the system detect（检测）thrashing? Once it detects thrashing,what can the system do to eliminate（消除）this problem?【来自课后习题】
答：分配的页数少于进程所需的最小页数时发生颠簸，并迫使它不断地页错误。

该系统可通过对比多道程序的程度来估计CPU利用率的程度，以此来检测颠簸。

降低多道程序的程度可以消除颠簸。

4.某Demand Paging system,拥有逻辑空间64页，每页2KB，拥有物理空间1MB。

(1)写出逻辑地址的格式。

解：11位页内地址，5位页号
(2)若不考虑访问权限等，进程的页表最多有多少项？每项至少有多少位？
解：因为有32个逻辑页面，所以页表有32项。

因为有1M/2K= 2的9次方物理块，所以每个页表项至少有9位
(3)如果物理空间减少一半，页表结构应相应作怎样的改变？
解：32项，每项至少需要8位
5.设有n个进程共享一互斥段对如下两种情况 1) 每次只允许一个进程进入互斥段; 2) 最多
允许M个进程(M<N)同时进入互斥段;采用信号量是否相同?信号量值的变化范围如何？
二、
三、操作系统为文件分配磁盘块（block）的时候一般有三种方式；contiguous（连续分配），linked （链式分配），and indexed（索引分配）。

1.简述三种分及其配方式目录结构、优缺点；
2.Consider a file currently consisting of 100 blocks. Assume that the file control block (and
the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level) allocation strategies, if, for one block, the following conditions hold. In the contiguous-allocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end.
Assume that the block information to be added is stored in memory.
a. The block is added at the beginning.
b. The block is added in the middle.
c. The block is added at the en
d.
d. The block is removed from the beginning.
e. The block is removed from the middle.
f. The block is removed from the end.
a. 201 1 1
b. 101 52 1
c. 1 3 1
d. 198 1 0
e. 98 52 0
f. 0 100 0
四、。