3.2.3 Explain the following scheduling algorithms

a)First In First Out(FIFO)

The simplest scheduling discipline

—Processes are dispatched according to their arrival time on the ready queue

—Process that has the CPU will run until complete

—Non preemptive scheduling algo.

b. Round-Robin Scheduling

• processes are given equal time slices called quanta (or quantums)
• takes turns of one quantum each
• if a process finishes early, before its quantum expires,
• the next process starts immediately and gets a full quantum
• in some implementations, the next process may get only the rest of the quantum
• assume a new process arrives and goes into the 
• queue before the process is removed from the processor

c. shortest job first

• another name is Shortest Process Next algorithm
• a better name may be shortest next-CPU-burst first
• assumes we know the length of the next CPU burst of all ready processes
• the length of a cpu burst is the length of time a process would 
• continue executing if given the processor and not preempted
• SJF estimates the length of the next burst based on the
•  lengths of recent cpu bursts
• starts with a default expected burst length for a new process
• suppose that time intervals are numbered 1 for first cpu burst, 2 for second cpu burst, etc.
• default length is e(1), the expected length of time for the first cpu burst
• unlike other scheduling algorithms, this algorithm assumes that information about a process's burst length is stored between the times when it is ready.
• in keeping with the need for efficiency, only a small amount of info is stored and only a simple calculation is performed
• we can weight the previous expectation (representing all previous bursts) and the most recent burst with any two weights that add up to 1, e.g., say 0.5 and 0.5, or 0.9 for previous expectations and 0.1 for actual time for most recent cpu burst

d. shortest remaining time

·         very short processes get very good service

·     a process may mislead the scheduler if it previously ran quickly but now may be cpu intensive (this algorithm fails very badly for such a case)

·         the penalty ratios are small;

·         this algorithm works extremely well in most cases

this algorithm provably gives the highest throughput (number of processes completed) of all scheduling algorithms if the estimates are exactly correct.

e. priority

·         processor is allocated to the ready process with the highest

priority (we will assume that the highest priority is 0, as in UNIX and LINUX)

·         if all arrive at time 0 and are to run to completion, the C, D have 

the highest priority, etc.

·         if there is a tie, choose the processes in alphabetical order
·         impractical and unrealistic in practice

f. multilevel queue

·         priorities are implicit in the position of the queue that the ready process

 is currently waiting in

·         when process is running on the processor, the OS 

must remember which queue it came from

·         after a process has executed for one time quantum, 

it is moved down one queue

·         process is placed at the back of the queue
·         a ready process is initially (implicitly) given a 
high priority, then, as it uses time while still remaining ready,

·         this is close to what is used for the traditional UNIX scheduler

 its priority is lowered

By:
NUR FARRAHANA BT MOHD ROSLAN
NUR HIDAYAH BT AZIRID                       

ZATTY ILYANI BT ABDULLAH