1. FCFS Scheduling PDF

Preview

Summary

An example questions on the First Come First Serve - Non-Preemptive - Scheduling questions....

Description

[email protected] (FCFS) First Come First Serve ~ Non-Preemptive ~ CPU Scheduling Algorithm Let Pi be = Process i where ( i = 0, 1, 2, 3, …) AT be = Arrival Time BT be = Burst Time CT be = Completion Time TAT be = Turnaround Time WT be = Waiting Time Starting Time is always zero to find P P0 P1 P2 P3

AT 0 1 2 3

Draw Gantt Chart. Calculate

CT , TAT , WT .

CT . BT 5 3 8 6

CT ? ? ? ?

TAT ? ? ? ?

WT ? ? ? ?

Drawing Gantt Chart: Step 0: Start with an empty Gantt Chart. t=0 12 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 2021 22 P0

P1 P2

P3

When t=0 , P0 arrives and is the only process available. Since this algorithm is non-preemptive, this process will not be paused and will entirely execute. t=0 12 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 2021 22

Step 1:

P0 P1

P2 P3

0

[email protected]

When t=5 , P0 completes and three processes ( P1 , P2 , P3 ) already arrived and are available. Since this algorithm is FCFS, P1 will execute first by following the order of the process. Also, since this is non-preemptive algorithm, this process will not be paused and will entirely execute. t=0 12 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 2021 22

Step 2:

P0

0

P1

1

P2 P3

When t=8 , P1 completes and two processes ( P2 , P3 ) are available. Between P2 and P3 , P2 will go first under FCFS algorithm. P2 will execute entirely without being paused. t=0 12 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 2021 22

Step 3:

P0

0

P1

1

P2

2

P3

When t=16 , P2 completes and only one process ( P3 ) is available. will execute entirely without being paused. t=0 12 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 2021 22

Step 4:

P0

0

P1

1

P2

2

P3

3

Calculating

CT ,

TAT ,

WT :

Let Completion Time ( CT )

for each millisecond

P3

[email protected] be = for each millisecond for each millisecond

Turnaround Time ( TAT ) be = Waiting Time ( WT ) be = For P0 : t=0 .

Burst Time ( BT ) is 5 milliseconds ( ms ) and Arrival Time ( AT ) is at

t=0 12 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 2021 22 P0

0

CT TAT WT

5 5

Completion Time ( = Finishing Time – Starting Time CT ) = Completion Time – Arrival Time Turnaround Time ( = Turnaround Time – Burst Time TAT ) Waiting Time ( WT ) For P1 : t=1 .

⇒ ⇒ ⇒

CT =5−0 =5 TAT =5−0=5 WT =5 −5=0

Burst Time ( BT ) is 3 milliseconds ( ms ) and Arrival Time ( AT ) is at

t=0 12 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 2021 22 P1

1

CT TAT WT

8 7 4

Completion Time ( = Finishing Time – Starting Time CT ) = Completion Time – Arrival Time Turnaround Time ( = Turnaround Time – Burst Time TAT ) Waiting Time ( WT ) For P2 : t=2 .

CT =8−0 =8 TAT =8−1=7 WT =7−3=4

Burst Time ( BT ) is 8 milliseconds ( ms ) and Arrival Time ( AT ) is at

t=0 12 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 2021 22 P2

CT

⇒ ⇒ ⇒

2 16

[email protected] TAT WT

14 6

Completion Time ( = Finishing Time – Starting Time CT ) = Completion Time – Arrival Time Turnaround Time ( = Turnaround Time – Burst Time TAT ) Waiting Time ( WT )

For P3 : t =3 .

⇒ ⇒ ⇒

CT =16 −0=16 TAT =16−2=14 WT =14 −8=6

Burst Time ( BT ) is 6 milliseconds ( ms ) and Arrival Time ( AT ) is at

t=0 12 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 2021 22 P3

3

CT TAT WT

22 19 13

Completion Time ( = Finishing Time – Starting Time CT ) = Completion Time – Arrival Time Turnaround Time ( = Turnaround Time – Burst Time TAT ) Waiting Time ( WT )

P P0 P1 P2 P3

AT 0 1 2 3

BT 5 3 8 6

CT 5 8 16 22

Made By: [email protected] [email protected]

⇒ ⇒ ⇒

CT =22−0=22 TAT =22−3=19 WT =19 −6=13

TAT 5 7 14 19

WT 0 4 6 13...