第一题
假设一个系统有 5 个进程，它们的到达时间和服务时间如表所示，忽略 I/O 以及其他的开销时间，若分别按先来先服务 (FCFS)，抢占式的短进程优先 (SPF) 调度算法进行 CPU 调度，请给出各进程的完成时间、周转时间和平均周转时间。
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| A | 0 | 3 |
| B | 2 | 6 |
| C | 4 | 4 |
| D | 6 | 5 |
| E | 8 | 2 |
周转时间=作业完成时刻—作业到达时刻；
带权周转时间=周转时间/服务时间；
平均周转时间=作业周转总时间/作业个数；
平均带权周转时间=带权周转总时间/作业个数；
先来先服务（FCFS）：
服务顺序为 A - B - C - D - E
| 进程 | 到达时间 | 服务时间 | 完成时间 | 周转时间 |
|---|---|---|---|---|
| A | 0 | 3 | 3 | 3 |
| B | 2 | 6 | 9 | 7 |
| C | 4 | 4 | 13 | 9 |
| D | 6 | 5 | 18 | 12 |
| E | 8 | 2 | 20 | 12 |
平均周转时间：
抢占式进行优先：
IMPORTANT
需要注意的是，除了第一个到达的，其他的不看到达时间，而是去抢占，具体方法是比较到达时候正在运行的进程的剩余时间和自己的所需要的服务时间比较，小的再去进行。
运行顺序为：
A 完成之后，B 开始，B 运行一个时间之后，C 到达，比较 B 剩余的量和 C 的服务时间，C 小于 B，所以进行 C，此时 B 剩余 5，C 运行两个之后，D 到达，此时 C 剩余 2 两个，和 D 的服务时间比较，C 小于 D，所以 C 继续运行，运行结束之后 E 到达，此时时间为 8，这时候比较 E 和 B 和 D 之间剩余的时间，E 为 2，B 为 5，D 为 5，则运行 E，E 运行完成之后时间为 10，然后比较剩余的Ｂ和Ｄ，由于Ｂ是先到达的，所以开始执行Ｂ完成时间为 15，最后是 D，完成时间是 20
| 进程 | 到达时间 | 服务时间 | 完成时间 | 周转时间 |
|---|---|---|---|---|
| A | 0 | 3 | 3 | 3 |
| B | 2 | 6 | 15 | 13 |
| C | 4 | 4 | 8 | 4 |
| D | 6 | 5 | 20 | 14 |
| E | 8 | 2 | 10 | 2 |
| 平均周转时间： |
第二题
假设当前系统中有５个进程
| Allocation | A | B | C | D |
|---|---|---|---|---|
| P 0 | 0 | 0 | 1 | 2 |
| P 1 | 1 | 0 | 0 | 0 |
| P 2 | 1 | 1 | 5 | 4 |
| P 3 | 0 | 3 | 3 | 2 |
| P 4 | 0 | 0 | 1 | 1 |
| Need | A | B | C | D |
|---|---|---|---|---|
| P0 | 0 | 0 | 1 | 2 |
| P1 | 1 | 7 | 5 | 0 |
| P2 | 2 | 3 | 5 | 6 |
| P3 | 0 | 6 | 3 | 2 |
| P4 | 0 | 6 | 5 | 0 |
| 结果画成表的形式会更好： |
可以找到这样的一个序列，
| 进程 | 已分配资源 | 还需资源 | 可用资源 | 进程结束后总资源 | finish |
|---|---|---|---|---|---|
| P0 | 0 0 1 2 | 0 0 1 2 | 1 6 2 2 | 1 6 3 4 | TRUE |
| P3 | 0 3 3 2 | 0 6 3 2 | 1 6 3 4 | 1 9 6 6 | TRUE |
| P1 | 1 0 0 0 | 1 7 5 0 | 1 9 6 6 | 2 9 6 6 | TRUE |
| P2 | 1 1 5 4 | 2 3 5 6 | 2 9 6 6 | 3 10 11 10 | TRUE |
| P4 | 0 0 1 1 | 0 6 5 0 | 3 10 11 10 | 3 10 12 11 | TRUE |
第三题
在斜杠上标注上什么原因转换
第四题
在请求分页系统中，某进程的页面访问串为：2,3,4,7,2,4,6,2,5,4,3,7。设分配给该进程的存储物理帧（frame）数为m。当m=4时，计算FIFO和LRU两种页面替换算法的缺页次数。
注意看是求缺页次数还是缺页率。
FIFO（先进先出）
LRU（替换最久没有被访问）
第一个替换的是 3 是因为 2 被访问了 2 次。
OPT 最佳置换算法，（最久不会被访问）这个是往后看，置换的是最久不会被访问。
第五题
有一个咖啡厅的订单系统，订单缓冲区用来存取咖啡。服务员做完咖啡，放入订单缓冲区中，顾客从订单缓冲区中取咖啡。请用信号量机制实现以下服务员和顾客两个并发进程的同步过程。
消费者和生产者的问题
缓冲区要互斥的来使用，是互斥的信号量。
semaphore empty=1;//定义互斥信号量
int a=0;//是否放入咖啡(可用资源数量）
Process waiter(){
while(1){
P(empty); // 申请一个缓冲区
V(a); //放入咖啡
}
Process consume(){
while(1){
P(a); // 取走咖啡
V(empty); //释放一个缓冲区
}
这里首先需要理解 P 和 V 的意思，P 是申请，V 是释放。
医生诊完病，释放化验单，然后申请化验结果，然后再去诊病。
而化验哪里，首先是申请化验单，然后才能化验，最后才能释放化验结果。
王海平