复习

1 Suppose that the following processes arrive for execution at the times indicated. Each process will run the listed amount of time. In answering the questions, use nonpreempive scheduling and base all decisions on the information you have at the time the decision must be made. process  arrival time burst time P1          0.0          8 P2          0.4          4 P3          1.0          1 a. What is the average turnaround time for these processes with the FCFS scheduling algorithm b. What is the average turnaround time for these processes with the SJF scheduling algorithm c. Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit and them SJF scheduling is used. 2 What advantage is there in having different time-quantum sizes on different levels of a multilevel queueing system 3 Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes: FCFS RR Multilevel feedback queues 4 Consider the following set of processes, with the length of the CPU-burst time given in milliseconds: process            burst time       priority       arrive P1                    10                  3             0 P2                     1                   1             1 P3                     2                   3             2 P4                     1                   4             3 P5                     5                   2             4 The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0. a. Draw four Gantt charts illustrating the execution of these processes using FCFS, preemptive SJF, a preemptive priority (smaller priority implies higher priority), and RR (quantum=2) scheduling b. What is the turnaround time of each process for each of the scheduling algorithms in part a c. What is the waiting time of each process for each of the scheduling algorithms in part a d. Which of the schedules in part a results in the minimal average waiting time (over all processes) 答案： 1.    a:  FCFS: average turnaround time is: (8+(12-0.4)+(13-1))/3=10.53 B:     SJF: average turnaround time is: (8+(9-1)+(13-0.4))/3=9.53 C:  average turnaround time is: 6.87s 2.首先对于那些需要经常调用cpu来响应的进程，一般都是交互程序或者是实时系统，这些进程可以在较短的时间片下获得更好的响应执行。而对于那些很少调用cpu来响应的进程，我们可以将时间片变大，这样就减少了上下文切换的时间了，可以充分利用cpu资源。 3.FCFS:对于都是短进程和其他算法相似，但是如果存在长进程，则会加长短进程的等待时间。 RR:对于短进程更加有利，因为每个进程拥有相同的cpu时间，短进程会更快完成。 Multilevel feedback:结合了RR和FCFS的两种优点。总体上比较合理。 4. a. FCFS P1 P2 P3 P4 P5           0        10          11          13          14          19 preemptive SJF P2 P4 P3 P5 P1           0          1            2          4            9        19 preemptive priority P2 P5 P1 P3 P4           0            1            6            16          18        19 RR P1 P2 P3 P4 P5 P1 P5 P1 P5 P1                     0  2      3      5      6      8    10    12    14    15  19 B:            p1  p2  p3  p4  p5 FCFS:    10  11  13  14  19 SJF:    19  1    4    2    9 PP:      16  1    18  19  6 RR:      19  3    5    6    15 C:            p1  p2  p3  p4  p5 FCFS:    0  10  11  13  14 SJF:    9    0    2    1    4 PP:      6    0    16  18  1 RR:      9    2    3    5  8 D: FCFS:(0+10+11+13+14)/5=9.6 SJF:(9+0+2+1+4)/5=3.2 Priority:(6+0+16+18+1)/5=8.2 RR:(9+2+3+5+10)/5=5.8 SJF is the minimal average waiting time. 1 The Sleeping-Barber Problem: -A barbershop consists of a waiting room with n chairs and the barber room containing the barber chair. -If there are no customers to be served, the barber goes to sleep. -If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. -If the barber is busy but chairs are available, then the customer sits in one of the free chairs. -If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers. 2  The Cigarette-Smokers Problem. -Consider a system with three smoker processes and one agent process. -Each smoker continuously rolls a cigarette and then smokes it. But to roll and smoke a cigarette, the smoker needs three ingredients: tobacco, paper, and matches. One of the smoker processes has paper, another has tobacco, and the third has matches. -The agent has an infinite supply of all three materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient then makes and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats. Write a program to synchronize the agent and the smokers. 1 Consider the traffic deadlock depicted in the figure - a. Show that the four necessary conditions for deadlock in deed hold in this example. - b. State a simple rule that will avoid deadlocks in this system. 2 Consider the following snapshot of a system: Allocation       Max         Available A B C D         A B C D         A B C D P0        0 0 1 2            0 0 1 2           1 5 2 0 P1        1 0 0 0            1 7 5 0 P2        1 3 5 4            2 3 5 6 P3        0 6 3 2            0 6 5 2 P4        0 0 1 4            0 6 5 6 Answer the following questions using the banker’s algorithm a. What is the content of the matrix Need? b. Is the system in a safe state? c. If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately? 答案： 1.a.互斥，每个路口只允许一辆车经过。 占有并等待，挡在路口的车占有这个路口的通过位置，并等待前进。 非抢占，每辆车不能抢占其他车的位置。 循环等待，每辆车都等待前一辆的前进，形成一个循环。 b.车辆不得在十字路口处停留，如果你不能完全进入下一条街道，就在路口内的街道进行等待。. 2.a. Need= Max-Allocation P0=0012-0012=0000 P1=1750-1000=0750 P2=2356-1354=1002 P3=0652-0632=0020 P4=0656-0014=0642 |-0  0  0  0-| | 0  7  5  0 | | 1  0  0  2 | | 0  0  2  0 | |_0  6  4  2_| b.系统处于安全状态，因为Available矩阵等于（1 5 2 0），进程P0和P3都可以运行，当进程P3运行完时，会释放自己的资源，而允许其他的进程运行。 c.可以被满足，之后，Available矩阵等于（1 1 0 0 ），当以次序P0，P2，P3，P1，P4运行时候，可以完成运行。 1 Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in order), how would each of the First-fit, Best-fit, and Worst-fit algorithms place processes of 212K, 417K, 112K, and 426K (in order)? Which algorithm makes the most efficient use of memory? 2 Consider a logical address space of eight pages of 1024 words each, mapped onto a physical memory of 32 frames. a. How many bits are there in the logical address? b. How many bits are there in the physical address? 3 Consider the following segment table: Segment  Base  Length 0  219  600 1  2300  14 2  90  100 3  1327  580 4  1952  96 What are the physical addresses for the following logical addresses? a.0,430 b.1,10 c.2,500 d.3,400 e.4,112 答案： 1.a. First fit 212K置于500K中 417K置于600k中 112K置于200K中 426K则必须等到直到有一块足够的孔 b. Best fit 212K置于300K中 417K置于500K中 112K置于200K中 426K置于600K中 c. Worst fit 212K置于600K  417K置于500K  112K置于400K  426K需要等到Best fit内存利用率最高 2. a.400ms,200ms进入页表，200ms进入内存中的字会员限时特惠最后一天，文档免下载券特权立即送 b.有效进入时间为0.75*200ms+0.25*400ms即250ms 3. a. 430<600, 219+430 = 649 b. 10<14, 2300+10 = 2310 c. 500>100, 不存在 d. 400<580, 1327+400 = 1727 e. 112>96, 不存在 1 Consider the following page reference string: 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6. How many page faults would occur for the following replacement algorithms, assuming one, two, three, four, five, six, or seven frames? Remember all frames are initially empty, So your first unique pages will all cost one fault each. a  LRU replacement b  FIFO replacement c  Optimal replacement 答案： Number of frames            LRU      FIFO    Optimal 1                    20      20      20 2                    18      18      15 3                    15      16      11 4                    10      14      8 5                    8        10      7 6                    7        10      7 7                    7        7        7