Scheduling

Scheduling

1. Which process ready to execute commands get the CPU?

   • Decided by short term scheduler

2. Pre-requistes for successful scheduling

   • CPU - I/O - Burst cycle
     • I/O occurs after a fixed amount of time in >= 90% of cases
       • This time is appropriate for re-scheduling
   • Pre-emptive scheduling
     • Proceses can be forced to relinquish CPU

3. Scheduling Criteria

   • Maxmise
     • CPU utilisation
     • Throughput
       • Number of processes completed (in their time slot) within a given time
     • Turn around time
       • Time it takes for each process to be executed
   • Minimise
     • Waiting time
       • Amount of time spent in ready queue
     • Response time
       • Time between submissions of request and production of first response

4. Scheduling algorithms

   • First come, first served (FCFS)
     • Jobs put in a queue and served according to arrival time
       • Easy to implement
       • CPU-intensive processes can cause long waiting times
     • Combine with pre-emption = round robin
       • Don't run process to completion. Process given time slice - can finish before this else moved to back of ready queue.
         • Treats all proceses equally
   • Shortest job first
     • Select next job with shortest CPU burst time
       • Not implementable - can't decide a semantic property
         • Approximate burst times by extrapolating previous behaviour

5. Priority Scheduling

   • Assume priority associated with each each process and CPU allocated to process with highest priority
     • Equal-priority processes scheduled according to FCFS
     • Implement (with/without pre-emption) depending on situation
   • With pre-emption
     • Newly arrived process with higher priority may gain processor immediately if a process with lower priority is running.
     • Introduces extra context switch - lower priority processes take longer to complete
     • Good for ensuring quick response time for high priority process
       • E.G sensors
   • Without pre-emption
     • Newly arrived process always waits
   • Disadvantage
     • Starvation of lower priority processes possible
       • Solution: Increase priority of processes afar a while (ageing)

6. Multi-level queue scheduling

   • Applicable when processes can be partitioned into groups
     • Interactive / batch processes
   • Split ready queue into several separate queues, each which can have a separate scheduling algorithms.
   • Scheduling between queues usually implemented as pre-emptive priority scheduling
   • Other way of organising queues - according to length of CPU burst
     • Processes that haven't completed in current queue's 'time', then they fall down to next queue
       • E.G. number cruncher / editor
         • Number crunches runs when editor not in use

7. Multi-processor systems

   • More complex
   • Symmetric MP
     • All processors identical and can be scheduled independently
       • Have separate ready queues for each processor, or a shared ready queue
   • Processor Affinty
     • Do you want to keep process running on same CPU on resumption?
     • Processor affinity for CPU on which it is currently running on
       • Soft affinity
         • Current CPU only preferred when re-scheduled
       • Hard affinity
         • Process may be bound to specific CPU
         • Advantages
           • Cache remains valid
           • Avoid time consuming cache invalidations and recovery
   • Load balancing
     • Use all CPUs equally
       • Push migration
         • Periodically check load, push processes to ess loaded CPUs
       • Pull migration
         • CPU complains of too much work - idle CPUs pull processes from busy CPUs

8. Linux implentation

   • Several schedulers may co-exist, assign fixed percentage of CPU time to each scheduler
     • Important schedulers
       • Round robins scheduler with priorities
         • Maintain tree of processes ordered by runtime allocated so far
           • Pick next process as one with least runtime allocated so far
             • Insert new process in ready queue at appropriate place in tree
               • Priorities handled by giving weights to run times
       • Real time scheduler
         • Process needs to assigned explicitly
         • Real time events (FIFO)