ALGORITHM

   CPU Scheduling algorithms:

We'll discuss major scheduling algorithms here which are following  

1. First Come First Serve (FCFS) Scheduling

2. Shortest-Job-First (SJF) Scheduling

3. Priority Scheduling

4. Round Robin (RR) Scheduling

5. Multilevel Queue Scheduling

First Come First Serve (FCFS)

• Jobs are executed on first come, first serve basis.
• Easy t o understand and implement.
• Poor in performance as average wait time is high.

Wait time of each process is following

Process	Wait Time : Service Time - Arrival Time
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	8 - 2 = 6
P3	16 - 3 = 13

Average Wait Time: (0+4+6+13) / 4 = 5.55

Shortest Job First (SJF)

• Best approach to minimize waiting time.
• Impossible to implement
• Processer should know in advance how much time process will take.
• Wait time of each process is following

  Process	Wait Time : Service Time - Arrival Time
  P0	3 - 0 = 3
  P1	0 - 0 = 0
  P2	16 - 2 = 14
  P3	8 - 3 = 5

  Average Wait Time: (3+0+14+5) / 4 = 5.50

Priority Based Scheduling

• Each process is assigned a priority. Process with highest priority is to be executed first and so on.
• Processes with same priority are executed on first come first serve basis.
• Priority can be decided based on memory requirements, time requirements or any other resource requirement.
• ·        Wait time of each process is following

  Process	Wait Time : Service Time - Arrival Time
  P0	0 - 0 = 0
  P1	3 - 1 = 2
  P2	8 - 2 = 6
  P3	16 - 3 = 13

·        Average Wait Time: (0+2+6+13) / 4 = 5.25

Round Robin Scheduling

• Each process is provided a fix time to execute called quantum.
• Once a process is executed for given time period. Process is preempted and other process executes for given time period.

Context switching is used to save states of preempted processes

Wait time of each process is following

Process	Wait Time : Service Time - Arrival Time
P0	(0-0) + (12-3) = 9
P1	(3-1) = 2
P2	(6-2) + (14-9) + (20-17) = 12

P3	(9-3) + (17-12) = 11

Average Wait Time: (9+2+12+11) / 4 = 8.5

Multi Queue Scheduling

• Multiple queues are maintained for processes.
• Each queue can have its own scheduling algorithms.
• Priorities are assigned to each queue.

TOPIC: - CPU SCHEDULING                            ALGORITHM              SUBMITTED BY-DEEPIKA                       ROLL NO.-2309            CLASS: - B.sc 2ND YEAR