《操作系统第3次作业》由会员分享，可在线阅读，更多相关《操作系统第3次作业（5页珍藏版）》请在金锄头文库上搜索。
1、操作系统第3次作业n 1. A CPU scheduling algorithm determines an order for the execution of its scheduled processes. Given n processes to be scheduled on one processor, how many possible different schedules are there? Give a formula in terms of n. 答：共有n！=n*(n-1)*(n-2)*1种不同调度方法。 n 2. Define the difference betw
2、een preemptive and nonpreemptive scheduling. State why strict nonpreemptive scheduling is unlikely to be used in a computer center. 答：非抢占式调度：一旦CPU被分配给一个进程，那么该进程会一直使用CPU直到进程终止或切换到等待状态时主动释放CPU。 可抢占式调度：当一个进程在CPU上运行时，该程序的CPU使用权可以被另一个新进程剥夺，被抢占的程序的状态被保存在PCB中，并进入就绪队列，等待下一次运行。 如果一个系统采用的是非可抢占式调度，并采用优先级调度，那么优
3、先级比较低的进程可能永远都在等待被执行，造成饥饿。这种情况就需要采用老化技术来防止饥饿。因此一个计算机中心最好不要采用严格的非抢占式调度。 n 3. Consider the following set of processes, with the length of the CPU-burst time given in milliseconds: n The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0. n a. Draw four Gantt charts ill
4、ustrating the execution of these processes using FCFS, SJF, a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling. n b. What is the turnaround time of each process for each of the scheduling algorithms in part a? n c. What is the waiting time
5、 of each process for each of the scheduling algorithms in part a? n d. Which of the schedules in part a results in the minimal average waiting time (over all processes)? FCFS P1 答：a）0 P2 P3 P4 P5 19 10 11 13 14 非抢占式SJF P2 P4 P3 0 1 2 4 9 P5 P1 19 非抢占式优先级 P2 P5 0 1 6 P1 P3 P4 16 18 19 RR P1 P2 P3 P4
6、P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1 P1 P1 P1 P1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 b）周转时间： FCFS： P1=10；P2=11；P3=13；P4=14；P5=19； SJF： P1=19；P2=1； P3=4； P4=2； P5=9； 非抢占式优先级： P1=16；P2=1； P3=18； P4=19； P5=6； RR： P1=19；P2=2； P3=7； P4=4； P5=14； c）等待时间： FCFS： P1=0；P2=10；P3=11；P4=13；P5=14； SJF：
7、P1=9；P2=0； P3=2； P4=1； P5=4； 非抢占式优先级： P1=6；P2=0； P3=16； P4=18； P5=1； RR： P1=9；P2=1； P3=5； P4=3； P5=9； d）平均等待时间： FCFS： (0+10+11+13+14)/5=9.6 SJF： (9+0+2+1+4)/5=3.2 非抢占式优先级： (6+0+16+18+1)/4=10.25 RR： (9+1+5+3+9)/4=6.75 所以，SJF算法的平均等待时间最少。 n 4. Suppose that the following processes arrive for execution a
8、t the times indicated. Each process will run the listed amount of time. In answering the questions, use nonpreemptive scheduling and base all decisions on the information you have at the time the decision must be made. n a. What is the average turnaround time for these processes with the FCFS schedu
9、ling algorithm? n b. What is the average turnaround time for these processes with the SJF scheduling algorithm? n c. The SJF algorithm is supposed to improve performance, but notice that we chose to run process P1 at time 0 because we did not know that two shorter processes would arrive soon. Comput
10、e what the average turnaround time will be if the CPU is left idle for the first 1 unit and then SJF scheduling is used. Remember that processes P1 and P2 are waiting during this idle time, so their waiting time may increase. This algorithm could be known as future-knowledge scheduling. 答：a)执行顺序为：P1，P2，P3；平均周转时间为：(8+(12-0.4)+(13-1)/3=10.53 b)执行顺序为:P1，P3，P2；平均周转时间为：(8+(9-1)+(13-0.4)/3=9.53 c)执行顺序为P3，P2，P1；平均周转时间为：(14+(6-0.4)+(2-1)/3=6.87
