Section notes for CS162 Section #6, March 5, 2002 Barbara Hohlt - Administrivia - Each group submits a revised design doc the day after the code is due. - Each student submits a group evaluation form the day after the code is due. - Each student turns in a project oath form to their TA. - Important dates and times: Thursday - proj1-code is due Friday - proj1-final-design is due Sunday - Midterm review in 10 Evans, 3-5pm Next Wednesday - Midterm 10 Evans AND 100 Lewis --- 7:00 - 8:30 pm - An I/O bound process is one that that spends most of its time doing I/O than it spends doing computations. A CPU bound process, on the other hand, spends most of its time doing computations. - Multiprogramming, the objective is to have some process running at all times to maximize CPU utilization. Therefore, we are interested in CPU scheduling. -------------------------------------------------------------------------- CPU Scheduling -------------------------------------------------------------------------- - CPU Scheduling - assume a program execution model consisting of CPU/IO bursts. - want to maximize CPU and DISK utilization - goodness metrics: average response time, maximize throughput, and fairness - many scheduling policies - CPU Scheduling Algorithms - FIFO, non preemptive - RR, preemptive FIFO - SJF, non preemptive - SRTF, preemptive SJF - Lottery, preemptive - MLFB Queues - Lottery Scheduling (research) - http://www.research.compaq.com/SRC/personal/caw/papers/lottery-osdi94.ps - give every job some number of tickets - approximates SRTF - fair -------------------------------------------------------------------------- Multilevel Feedback Queue Scheduling -------------------------------------------------------------------------- - Multilevel Queue Scheduling - partitions the ready queue into several separate queues - used when processes are easily classified (ex: foreground and background) - Multilevel Feedback Queue Scheduling - allows a process to move between queues - Used by most UNIX systems with some variation in details - Multiple run queues for different priorities - BSD uses 32 run queues for 128 different priority levels; so queuenum = priority/4 - Each queue scheduled in round-robin fashion - Time slice increases expontentially at lower priorities - Job starts in highest priority queue - Job increases priority if blocks for I/O - Job decreases priority if timeslice expires - MLFB result approximates SRTF - CPU bound jobs drop in priority - Short running I/O bound jobs have highest priority - unfair, long jobs may starve - Scheduling Countermeasures - break up job into several small jobs - put lots of System.out.println() in job - Linux uses same basic idea as MLFB, but does not actually maintain queues - Rather, computes "goodness" value for each runnable process in the system at each scheduling decision point; process with highest "goodness" is the next to run goodness = priority + counter Priority indicates the priority of the process. Counter indicates length of time slice (in ticks) when it acquires the CPU. ----------------------------------------------------------------------------- CPU Scheduling Examples ----------------------------------------------------------------------------- Warmup example: FIFO - 10 Jobs, 5 mins CPU time each, no I/O, all start at time 0 What is the average flow time? Answer: 27.5 CPU minutes (5 + 10 + 15 + 20 + 25 + 30 + 35 + 40 + 45 + 50) / 10 = 27.5 Example 1: FIFO 3 Jobs (A,B,C), 1 second CPU time each, no I/O, all start at time 0 What is the average flow time? Answer: 2 seconds (1 + 2 + 3) / 3 = 2 Example 2: RR Answer Example 1 for Round Robin with timeslice = 0.1 sec. No context switch overhead. Answer: 2.9 seconds 1 A 1 B 1 C 2 B 2 C 2 A 3 C 3 A 3 B 4 A 4 B 4 C 5 B 5 C 5 A 6 C 6 A 6 B 7 A 7 B 7 C 8 B 8 C 8 A <== 9 C 9 A 9 B <== 10 A 10 B 10 C <== Example 3: SJF Answer Example 1 for SJF. Answer: 2 (1 + 2 + 3) / 3 = 2 Example 4: MLFB 4 MLFB queues with priorities 1, 2, 3, 4 and time slices 10, 20, 40, 80 ms respectively. Priority 1 is high and 4 is low. All newly ready-to-run jobs enter at priority 1. Suppose a process repeatedly does 12ms pf computing followed by 10 ms of I/O. Describe the path it takes through the scheduler queues. Ans: 1, 2, 1, 2, 1, 2, .... The process will spend the first 10 ms of each 12 ms period that it computes in the queue whose priority is 1. The remaining 2 ms it wil spend in the queue whose priority is 2. The subsequent I/O period of 10 ms is what causes the process to reenter the priority 1 level again. ----------------------------------------------------------------------------- Example 5: Extra ----------------------------------------------------------------------------- Given 4 processes, each that want to do the following: CPU burst of time T I/O burst of time 3T Can overlap I/O and CPU, but only one CPU at a time Each process does 3 of these bursts and exits. Start each process at the same time. How long does it take for all processes to finish under different scheduling policies? FIFO: 1: C I I I C I I I C I I I 2: - C I I I C I I I C I I I 3: - - C I I I C I I I C I I I 4: - - - C I I I C I I I C I I I Total time: (3 bursts * 4T each burst) + 3T = 15 T Average response time? Process 1 took 12 time steps Process 2 took 13 Process 2 took 14 Process 2 took 15 Average is 12+13+14+15 / 4 = 13.5 How often is the CPU being used? - For every time step except last 3 (12 T) / (15 T) = 80% utilization Note that RR and SRTCF perform the same, since all jobs enter at the same time and have the same amount of run time!