Objectives:
Topic 10 Processor Scheduling
• Understand the purpose of long term scheduling, medium term scheduling and short term scheduling.
• Understand the following scheduling policies: First-Come- First-Serve, Round-Robin, Shortest Process Next, Shortest
Copyright By PowCoder代写 加微信 powcoder
Remaining Time, Highest Response Ratio Next, and Feedback.
• Understand the basic scheduling policy of the traditional UNIX systems.
• Stallings: Chapter 9.
Aim of Scheduling
• Assign processes to be executed by the processor(s)
• Response time
• Throughput
• Processor efficiency
Long-Term Scheduling
• Determines which programs are admitted to the system for processing
• Controls the degree of multiprogramming
• More processes, smaller percentage of time each process is executed
Medium-Term Scheduling • Part of the swapping function
• Based on the need to manage the degree of multiprogramming
Short-Term Scheduling
• Known as the dispatcher
• Executes most frequently
• Invoked when an event occurs – Clock interrupts
– I/O interrupts
– Operating system calls
Short-Term Scheduling Criteria • User-oriented
– Response Time
• Elapsed time between the submission of a request until there is
• System-oriented
– Effective and efficient utilization of the processor
• Performance-related – Quantitative
– Measurable such as response time and throughput
Priorities
• Scheduler will always choose a process of higher priority over one of lower priority
• Have multiple ready queues to represent each level of priority
• Lower-priority may suffer starvation
– Allow a process to change its priority based on its age or execution history
Decision Mode • Nonpreemptive
– Once a process is in the running state, it will continue until it terminates or blocks itself for I/O
• Preemptive
– Currently running process may be interrupted and
moved to the Ready state by the operating system
– Allows for better service since any one process cannot monopolize the processor for very long
Process Scheduling Example
First-Come-First-Served (FCFS)
• Each process joins the Ready queue
• When the current process ceases to execute, the oldest process in the Ready queue is selected
First-Come-First-Served (FCFS)
• A short process may have to wait a very long time before it can execute
• Favors CPU-bound processes
– I/O processes have to wait until CPU-bound process completes
Round-Robin
• Uses preemption based on a clock
• An amount of time is determined that allows each process to use the processor for that length of time
Round-Robin
• Clock interrupt is generated at periodic intervals
• When an interrupt occurs, the currently running process is placed in the ready queue
– Next ready job is selected
• Known as time slicing
Virtual Round-
• Processes in the Auxiliary Queue get preference over those in the Ready Queue
Shortest Process Next
• Nonpreemptive policy
• Process with shortest expected processing time is selected
• Short process jumps ahead of longer processes
• Must estimate the processing time
• Possibility of starvation for longer processes
Shortest Remaining Time
• Preemptive version of shortest process next policy
• Must estimate processing time
Highest Response Ratio Next (HRRN)
• Choose next process with the greatest ratio
time spent waiting + expected service time —————————————————– expected service time
Multilevel Feedback
• Penalize jobs that have been running longer
• Don’t know remaining time process needs to execute
Traditional UNIX Scheduling
• Multilevel feedback using round robin within each of the priority queues
• If a running process does not block or complete within 1 second, it is preempted
• Priorities are recomputed once per second
• Base priority divides all processes into fixed bands of priority levels
• Decreasing order of priority – Swapper
– Block I/O device control
– File manipulation
– Character I/O device control – User processes
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com