Scheduling Algorithms

5.3 Scheduling Algorithms

5.3.1 First-Come First-Serve Scheduling, FCFS
FCFS is very simple - Just a FIFO queue, like customers waiting in line at the bank or the post office or at a copying machine.
Unfortunately, however, FCFS can yield some very long average wait times, particularly if the first process to get there takes a long time

5.3.2 Shortest-Job-First Scheduling, SJF
The idea behind the SJF algorithm is to pick the quickest fastest little job that needs to be done, get it out of the way first, and then pick the next smallest fastest job to do next


5.3.3 Priority Scheduling
Priority scheduling is a more general case of SJF, in which each job is assigned a priority and the job with the highest priority gets scheduled first.
Priority scheduling can suffer from a major problem known as indefinite blocking, or starvation, in which a low-priority task can wait forever because there are always some other jobs around that have higher priority.


5.3.4 Round Robin Scheduling
Round robin scheduling is similar to FCFS scheduling, except that CPU bursts are assigned with limits called time quantum.
When a process is given the CPU, a timer is set for whatever value has been set for a time quantum.


5.3.5 Multilevel Queue Scheduling
When processes can be readily categorized, then multiple separate queues can be established, each implementing whatever scheduling algorithm is most appropriate for that type of job, and/or with different parametric adjustments.


5.3.6 Multilevel Feedback-Queue Scheduling
Multilevel feedback queue scheduling is similar to the ordinary multilevel queue scheduling described above, except jobs may be moved from one queue to another for a variety of reasons:

If the characteristics of a job change between CPU-intensive and I/O intensive, then it may be appropriate to switch a job from one queue to another.
Aging can also be incorporated, so that a job that has waited for a long time can get bumped up into a higher priority queue for a while.

http://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_CPU_Scheduling.html

• Operating Systems Lecture Notes 

Lecture 6
CPU Scheduling

When do scheduling decisions take place? When does CPU choose which process to run? Are a variety of possibilities:
When process switches from running to ready - on completion of interrupt handler, for example.
Common example of interrupt handler - timer interrupt in interactive systems. If scheduler switches processes in this case, it has preempted the running process. Another common case interrupt handler is the IO completion handler

Big difference: Batch and Interactive systems.
In batch systems, typically want good throughput or turnaround time.
In interactive systems, both of these are still usually important (after all, want some computation to happen), but response time is usually a primary consideration.

What about interactive systems?
Cannot just let any process run on the CPU until it gives it up - must give response to users in a reasonable time.
So, use an algorithm called round-robin scheduling. Similar to FCFS but with preemption.
Have a time quantum or time slice.
Let the first process in the queue run until it expires its quantum (i.e. runs for as long as the time quantum), then run the next process in the queue

http://people.csail.mit.edu/rinard/osnotes/h6.html

• The CPU scheduler algorithm may have tremendous effects on the system performance

Interactive systems
Real-time systems

https://docs.google.com/viewer?a=v&q=cache:RZfa-x-ejVYJ:cs.gmu.edu/~astavrou/courses/CS_571_F09/CS571_Lecture4_Scheduling.pdf+&hl=en&pid=bl&srcid=ADGEESiX_7iA0OeeayJ8iJ6e57m5E05DmQhvTaFI_RQ7UAx8jX-FFVZXjz4qgIza_AZ4BZB-nOmN-CwLwF-Dk1aAiFiG9AV5GsYf4u_-hVjYuYSWmpZ0sBVk9XJRRVL1IHmNoLvPP2xJ&sig=AHIEtbQuS4_Mr9TKwjZpNXLwy72aXWQMYw

• Presented Scheduling Algorithms

For interactive systems
Round-Robin scheduling
Priority scheduling
Multiple queues
Guaranteed scheduling
Lottery scheduling
Fair-share scheduling

https://docs.google.com/viewer?a=v&q=cache:SJZ1uCD84pUJ:soc.eurecom.fr/OS/docs/CourseOS_III_Scheduling.pdf+&hl=en&pid=bl&srcid=ADGEESiVcJ_QcPa7_VZ7caCkPycPSiwDwfgc6ohu4vzp6xGrxcQMsmZhbC1AwB-FFH-MRKRnpnY-d8icc_HMXFPezCDDj7hemAhRdXSXrBqZ2aRsHa6lS3eVo4aEBgYVAsxLSKLuUJp8&sig=AHIEtbRVjdr3i0JZeu70Y0t3N-Fdf2WZLQ