Unit 12

• CPU scheduling

  CPU scheduler chooses which tasks process to run first from the ready queue. This is done to ensure the CPU is not idle
• Aims of scheduling

  ...

  • Fairness, ensures that all processes get a fair share of the CPU
  • Efficiency, maximise CPU utilization
  • Response time, minimise and maintain a consistent response time
  • Turnaround time, minimise time between submission and job completion
  • Throughput, maximise number of jobs completed in a time frame
• Pre-emptive scheduling

  Allows running processes to be temporarily suspended, the processes will release the CPU when receiving a command

  
  

  Types of pre-emptive scheduling:

  • Round robin
  • Multilevel queue
  • Multilevel feedback queue
• Non-pre-emptive scheduling

  Processes release CPU upon task completion, it releases CPU voluntarily

  Types of non-pre-emptive scheduling:

  • First in first out/first come first serve
  • Shortest job first
  • Priority
• Round robin

  ...

  • Long avg wait time
  • Process switch requires times
  • If time quantum is too short, it reduces CPU efficiency
  • If time quantum is too long, it causes poor response time to requests
• Multilevel queue

  ...

  • Classifies processes into different groups
  • Ready queue separated into several separate queues
  • A process is permanently assigned to a queue based on priority, size, and process type
  • Has priority over low level queues
• Multilevel feedback queue


  ...

  • Processes can move between queues
  • If a process uses too much CPU time, it will be moved to a lower priority
  • If a process lacks CPU time, it will be moved to a higher priority
• FIFO


  ...

  • Simplest CPU scheduling algorithm
  • The process that requests the CPU first is allocated to CPU first
  • Avg wait time is quite long
• SJF


  ...

  • Scheduling is done by examining the length of the next CPU burst of a process
  • If CPU is free, the process with the smallest next CPU burst is assigned
  • If 2 processes have same CPU burst, it will implement FIFO|
  • Short avg wait time
• Priority


  ...

  • Priority is associated with each process
  • CPU is allocated the job with the highest priority
  • Equal priority processes are scheduled with FIFO
  • A problem of this algorithm is starvation