3. Process Scheduling

10/10/22

Process Scheduling

The OS manages and schedules processes

• New -> ready: when to admit processes to the system
• Ready -> running: decide which process to run next
• Running -> ready: when to interrupt process The scheduler decided which process to run next. There's no one size fits all. The type of operating system determines which algorithms are appropriate

Time Horizon

Long term: admits new processes and controls the degree of multi programming. Good mix of CPU and IO bound processes. Usually absent in popular modern Medium term: controls swapping. Looks to see how busy the system currently is. Short term: which process to run next. Manages the ready queue, runs frequently (must be fast). Called following clock interrupts or blocking system calls.

Classification by approach

• Non-preemptive: Processes are interrupted voluntarily
• Preemptive: Processes are interrupted forcefully or voluntarily. Requires context switches which generate. Prevents processes from monopolising the CPU. Most popular OS are preemptive.

Performance assessment

• User Oriented Criteria
  • Response time: time between creating the job and its first execution
  • Turnaround time: time between creating the job and finishing it
  • Predictability: variance in processing times
• System oriented criteria:
  • Throughput: number of jobs processed per hour
  • Fairness: Equally distributed processing.

Scheduling Algorithms

1. First Come First Served/First in First out
   • Concept: Non-preemptive algorithm that operates as a strict queuing mechanism.
   • Advantages: Positional fairness an easy to implement
   • Disadvantages: Favours long processes over short ones. Could compromise resource utilisation.
2. Shortest Job First
   • Concept: A non-preemptive algorithm that starts processes in order of ascending processing time
   • Advantages: Always result in the optimal turnaround time
   • Disadvantages: Starvation might occur. Fairness and predictability are compromised. Processing times have to be known beforehand
3. Round Robin
   • Concept: A preemptive version of FCFS. Processes run in the order they were added but they only get a max amount of time at once. Forces context switches at periodic intervals
   • Advantages: Improved response time. Effective for general purpose interactive/time sharing systems
   • Disadvantages: Increased context switching and overhead. Favours CPU bound processes over IO. Can reduce to FCFS.
   • Length of time slice must be considered. Good low response time is achieved with a small time slice. High throughput is achieved with a large time slice. If time slice is only used partially, next process starts immediately
4. Priority Queue
   • Concept: A preemptive algorithm that schedules processes by priority. Round robin is used within the same priority levels. Saved by the process control block
   • Advantages: Can priorities IO bound jobs
   • Disadvantages: Low priority may suffer from starvation

Algorithm	Concept	Advantage	Disadvantage
First Come First Served/First in First out	Non-preemptive algorithm that operates as a strict queuing mechanism.	Positional fairness an easy to implement	Favours long processes over short ones. Could compromise resource utilisation.
Shortest Job First	A non-preemptive algorithm that starts processes in order of ascending processing time	Always result in the optimal turnaround time	Starvation might occur. Fairness and predictability are compromised. Processing times have to be known beforehand
Round Robin	A preemptive version of FCFS. Processes run in the order they were added but they only get a max amount of time at once. Forces context switches at periodic intervals	Improved response time. Effective for general purpose interactive/time sharing systems	Increased context switching and overhead. Favours CPU bound processes over IO. Can reduce to FCFS.
Priority Queue	A preemptive algorithm that schedules processes by priority. Round robin is used within the same priority levels. Saved by the process control block	Can priorities IO bound jobs	Low priority may suffer from starvation

Multi-level feedback queues

Different algorithms can be used for the individual queues. Feedback queues allow priorities to change dynamically, jobs can move between queues. Move priorities to increase fairness