Saturday 18 June 2011

Scheduling algorithms

  • Earliest deadline first scheduling. When an event occurs (end of task, new task released, etc.) the queue will be searched for the process closest to its deadline.
  • Fair-share scheduling. Sharing cpu time between groups and users in groups. Another algorithm is called recursively to manage sharing of processes.
  • Least slack time scheduling or Least Laxity First. Assigns priority based on the slack time (difference between the deadline, ready and run time) of a process.
  • List scheduling. From an ordered list of processes with priorities, assign first to highest priority the available resources. Possible strategies: critical path, longest path, highest level first, longest processing time.
  • Multi level feedback queue.
  • Rate-monotonic scheduling. Optimal, preemptive, static-priority scheduling algorithm. Priority given in rate monotonic principle (first deadline is first processed).
  • Round-Robin scheduling. Simplest algorithm, assigns time slices to each process without priority.
  • Shortest job next (or first). Executes next the waiting process with the smallest execution time, is non-preemptive.
  • Shortest remaining time. A version of shortest job next scheduling that terminates the running process before to choose another task.