CPU Scheduling

CPU Scheduling

1. Multiprocessing vs Multiprogramming

   • Multiprocessing
     • Management of multiple processes within a multiprocessor
       • 2 or more CPUs
   • Multiprogramming
     • Management of multiple processes within a uniprocessor system
       • 1 CPU
       • Utilises scheduling
         • Pre-emptive multitasking
           • Context switching
         • Schedulers
           • Long-term scheduler
             • Selects which process to be brought into the ready queue
             • Controls 'degree of multiprogramming' (num of processes in memory)
           • Short-term scheduler
             • Selects which process should be executed next and allocates CPU
             • Leads to dispatcher giving process control of CPU
               • Dispatch latency = time taken to stop one process and run another
           • Medium-term scheduler
             • Swaps processes in and out of memory balancing process mix
           • Scheduling Criteria
             • CPU utilization
             • Throughput
             • Turnaround time
             • Waiting time
             • Response time

2. Scheduling Algorithms

   • Goals
     • All Systems
       • Fairness
       • Balance - Keep busy
     • Batch Systems
       • Throughput
       • Turnaround time
       • CPU utilisation
     • Interactive Systems
       • Response time
       • Proportionality
     • Real-time systems
       • Meeting deadlines - Avoid data loss
       • Predictability
   • Types
     • First Come, First Served
       • Oldest process of ready queue selected
         • Favours CPU-bound processes
         • Short processes may have to wait a long time
     • Shortest Job First
       • Optimal - minimum average waiting time for set of processes
     • Priority Scheduling
       • Priority number associated with each process
         • Problem: Starvation
           • Lowest priority may never execute
     • Round Robin
       • Set time given
         • When set time is complete, process placed at back of ready queue
           • Good for short jobs, bad for long jobs
     • Mutltilevel Queue Scheduling
       • Ready queue formed into multiple queues with own algorithms
     • Multilevel Feedback Scheduling
       • Process can move between various queues
         • Configure algorithm to match a system's design
         • Complex