Recent Post

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.


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
  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



–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


No comments