Round Robin (RR)

Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds.  After this time has elapsed, the process is preempted and added to the end of the ready queue.

If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once.  No process waits more than (n-1)q time units.

•Performance

–q large Þ FIFO

–q small Þ q must be large with respect to context switch, otherwise overhead is too high

Example of RR with Time Quantum = 4

Process             Burst Time

  P1                          24

  P2                          3

  P3                          3

 

The Gantt chart is:  

 

•Typically, higher average turnaround than SJF, but better

 response

  Time Quantum and Context Switch Time

 

Multilevel Queue

Ready queue is partitioned into separate queues: 

–foreground (interactive)

–background (batch)   

Each queue has its own scheduling algorithm:

–foreground – RR

–background – FCFS

•Scheduling must be done between the queues:

–Fixed priority scheduling; (i.e., serve all from foreground then from background).  Possibility of starvation.

–Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., 80% to foreground in RR

–20% to background in FCFS

Multilevel Queue Scheduling

 

Multilevel Feedback Queue 

•A process can move between the various queues; aging can be implemented this way.

•Multilevel-feedback-queue scheduler defined by the following parameters:

–number of queues

–scheduling algorithms for each queue

–method used to determine when to upgrade a process

–method used to determine when to demote a process

–method used to determine which queue a process will enter when that process needs service

Example of Multilevel Feedback Queue

•Three queues:

–Q0 – RR with time quantum 8 milliseconds

–Q1 – RR time quantum 16 milliseconds

–Q2 – FCFS

•Scheduling

–A new job enters queue Q0 which is served FCFS. When it gains CPU, job receives 8 milliseconds.  If it does not finish in 8 milliseconds, job is moved to queue Q1.

–At Q1 job is again served FCFS and receives 16 additional milliseconds.  If it still does not complete, it is preempted and moved to queue Q2.

Thread Scheduling

•Distinction between user-level and kernel-level threads

•Many-to-one and many-to-many models, thread library schedules user-level threads to run on LWP

–Known as process-contention scope (PCS) since scheduling competition is within the process

•Kernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in system

  Multiple-Processor Scheduling

•CPU scheduling more complex when multiple CPUs are available

•Homogeneous processors within a multiprocessor

•Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing

•Symmetric multiprocessing (SMP) – each processor is self-scheduling, all processes in common ready queue, or each has its own private queue of ready processes

•Processor affinity – process has affinity for processor on which it is currently running

–soft affinity

–hard affinity