操作系统课件：04_scheduling

1、1SchedulingIntroduction to Scheduling Bursts of CPU usage alternate with periods of I/O wait a CPU-bound process an I/O bound process2When to Schedule1. At process creation2. At process termination3. At blocking system calls4. At I/O interrupt (eg. Clock interrupt)Non-preemptive scheduling algorithm

2、s: let a process run until it blocks or until voluntarily releases the CPU.Preemptive scheduling algorithms3Goals of SchedulingThroughput!=Turnaround time4Scheduling in Batch Systems (1)(a) First-come-first-served (FCFS)(b) Shortest-job-first (SJF) - provably optimal if all jobs are known in advance

3、(c) Shortest-remaining-time-next (SRTN)5Scheduling in Interactive Systems (1) Round Robin Scheduling(a) list of runnable processes(b) list of runnable processes after B uses up its quantumLength of quantum: too short = waste of CPU time too long = poor response6Scheduling in Interactive Systems (2)A

4、 scheduling algorithm with four priority classesStatic and dynamic priority allocations, e.g. 1/f.7Scheduling in Interactive Systems (3) Multiple queues (higher priority with less quanta) Shortest process next(how to estimate process running time) Guaranteed scheduling (ratio=actual CPU time/CPU tim

5、e entitled) Lottery scheduling - biased randomness, passing tickets Fair share scheduling8Scheduling in Real-Time SystemsSchedulable real-time system Given m periodic events event i occurs within period Pi and requires Ci seconds Then the load can only be handled if11miiiCP9Policy versus Mechanism S

6、eparate what is allowed to be done with how it is done a process knows which of its children threads are important and need priority Scheduling algorithm parameterized mechanism in the kernel Parameters filled in by user processes policy set by user process10Thread Scheduling (1)Possible scheduling

7、of user-level threads 50-msec process quantum, threads run 5 msec/CPU burstApplication-specific thread schedulers11Thread Scheduling (2)Possible scheduling of kernel-level threads 50-msec process quantum threads run 5 msec/CPU burstProblem 37 Five Jobs Scheduling Round robin Priority scheduling FCFS

8、 Shortest job first Mean process turnaround time? 12JobABCDERunning time106248Priority35214UNIX Scheduler Real-time FIFO Not preemptable Real-time round robin Preemptable with time quanta Timesharing1314UNIX SchedulerThe UNIX scheduler is based on a multilevel queue structure15Scheduling in Windows (1)Ma