ADVANCED OPERATING SYSTEM ( AOS ) | First Come First Serve ( FCFS ) | Shortest Job First ( SJF ) | Banker’s Algorithm | Round Robin ( RR ) | Priority Scheduling | Selfish Round Robin( SRR )

ADVANCED OPERATING SYSTEM ( AOS ) | First Come First Serve ( FCFS ) | Shortest Job First ( SJF ) | Banker’s  Algorithm | Round Robin ( RR )  | Priority Scheduling | Selfish Round Robin( SRR )

1. First Come First Serve ( FCFS )

    1.1. First Come First Serve ( Preemptive )

    1.2. First Come First Serve ( Non-Preemptive )

2. Shortest Job First ( SJF )

    2.1. Shortest Remaining Job First (Preemptive)

    2.2. Shortest Job First (Non-Preemptive)

3. Banker’s  Algorithm.

    3.1. Banker’s  Algorithm.

4. Round Robin ( RR ) 

    4.1. Round Robin ( RR ) with Quantum q = 2, q=3, q=20 | Round             Robin ( Preemptive )

5. Priority Scheduling 

    5.1. Priority Scheduling ( Preemptive )

    5.2. Priority Scheduling ( Non-Preemptive )

6. Selfish Round Robin( SRR )

    6.1. Selfish Round Robin( SRR )

1.1. First Come First Serve ( Preemptive )

In FCFS(Preemptive) we use process (P) once time means arrival time once time use.

OR  in preemptive, all cycles use as per the arrive at more prominent upsides of appearance time. Such as

 

Rules of FCFS(Preemptive)

1) In FCFS(Preemptive) Arrival Time ( A.T ) small choose digit.

2) In FCFS(Preemptive) if Arrival Time ( A.T )  and Burst Time ( B.T ) values are equivalent then we further apply First Come First Serve.

3) If the Arrival Time ( A.T ) of FCFS(Preemptive) values are the same then compare Burst Time ( B.T ) values,  which are small values of  Burst Time ( B.T ) then you choose further processes.

In both Structures, we apply the question such: as s

Scenario Number   .1.

FCFS(Preemptive) Process id	FCFS(Preemptive) Arrival Time( A.T )	FCFS(Preemptive) Burst Time ( B.T )
P1	2	6
P2	1	7
P3	4	3
P4	3	6
P5	2	8
P6	5	1
P7	3	2
P8	2	3

 

So we apply  rule number  1 for further processes 

 

FCFS(Preemptive) Total Arrival Time ( TAT )				FCFS(Preemptive) Average Waiting Time ( AWT )
FCFS(Preemptive) TAT ( End – A.T )				FCFS(Preemptive) AWT ( TAT – B.T )
P1	17 -2	15		P1	15 - 6	9
P2	11 -1	10		P2	10 – 7	3
P3	36 – 4	32		P3	32 – 3	29
P4	31 – 3	28		P4	28 – 6	22
P5	25 – 2	23		P5	23 – 8	15
P6	37 – 5	32		P6	32 – 1	31
P7	33 – 3	30		P7	30 – 2	28
P8	5 - 2	3		P8	3 - 3	0
TAT		173		WT		137
ATAT		173 / 8		AWT		137 / 8
		= 21.625				= 17.125

 

Scenario Number    .2.

FCFS(Preemptive) Process id	FCFS(Preemptive) Arrival Time( A.T )	FCFS(Preemptive) Burst Time ( B.T )
P1	2	1
P2	3	1
P3	2	1
P4	4	2

So we use  rule number  2 as applies, 

FCFS(Preemptive) Total Arrival Time ( TAT )					FCFS(Preemptive) Average Waiting Time ( AWT )
FCFS(Preemptive) TAT ( End – A.T )					FCFS(Preemptive) AWT ( TAT – B.T )
P1	4 -3	1				P1	1 - 1	0
P2	2 -2	0				P2	0 - 1	-1
P3	3 - 2	1				P3	1 - 1	0
P4	6 - 4	2				P4	2 - 2	0
TAT		4				WT		-1
ATAT		4 / 4				AWT		-1 / 4
		= 1						= - 0.25

 

Scenario Number    .3.

FCFS(Preemptive) Process id	FCFS(Preemptive) Arrival Time( A.T )	FCFS(Preemptive) Burst Time ( B.T )
P5	2	4
P3	5	3
P6	3	2
P1	2	6
P2	4	5
P8	3	2
P7	6	1
P4	5	3

 

Here is the above diagram yellow box represents from 0 to 1 and from 1 to 2 with no arrival time, so both boxes are empty.

FCFS(Preemptive) Total Arrival Time ( TAT )					FCFS(Preemptive) Average Waiting Time ( AWT )
FCFS(Preemptive) TAT ( End – A.T )					FCFS(Preemptive) AWT ( TAT – B.T )
P1	12 -2	10				P1	10 - 6	4
P2	21 -4	17				P2	17 - 5	12
P3	24 - 5	19				P3	19 - 3	16
P4	27 - 5	22				P4	22 - 3	19
P5	6 - 2	4				P5	4 - 4	0
P6	14 - 3	11				P6	11 - 2	9
P7	28 - 6	22				P7	22 - 1	21
P8	16 - 3	13				P8	13 - 2	11
TAT		118				WT		92
ATAT		118 / 8				AWT		92 / 8
		= 14.75						= 11.5

 

Query No .1.

FCFS(Preemptive) Process id	FCFS(Preemptive) Arrival Time( A.T )	FCFS(Preemptive) Burst Time ( B.T )
P1	4	2
P2	5	6
P1	1	1
P2	3	2
P5	2	4
P3	1	7
P7	2	2
P6	3	1

 

Query No .2.

FCFS(Preemptive) Process id	FCFS(Preemptive) Arrival Time( A.T )	FCFS(Preemptive) Burst Time ( B.T )
P1	6	2
P2	9	8
P3	1	1
P2	0	2
P4	5	6
P5	0	12
P7	4	7
P6	2	1

Query No .3.

FCFS(Preemptive) Process id	FCFS(Preemptive) Arrival Time( A.T )	FCFS(Preemptive) Burst Time ( B.T )
P1	10	1
P2	12	1
P3	11	2
P4	0	2
P5	5	6
P6	0	7
P7	3	4
P8	2	1

Query No .4.

FCFS(Preemptive) Process id	FCFS(Preemptive) Arrival Time( A.T )	FCFS(Preemptive) Burst Time ( B.T )
P1	9	10
P5	7	13
P2	5	21
P3	4	20
P5	3	6
P6	2	3
P4	5	2
P7	3	10

Query No .5.

FCFS(Preemptive) Process id	FCFS(Preemptive) Arrival Time( A.T )	FCFS(Preemptive) Burst Time ( B.T )
P5	2	11
P6	8	12
P4	1	0
P3	0	2
P1	7	1
P2	0	3
P4	1	3
P7	3	1

 

Query No .6.

FCFS(Preemptive) Process id	FCFS(Preemptive) Arrival Time( A.T )	FCFS(Preemptive) Burst Time ( B.T )
P1	8	30
P2	9	40
P3	10	50
P4	0	2
P5	3	3
P6	4	4
P7	1	8
P8	5	1

 

Query No .7.

FCFS(Preemptive) Process id	FCFS(Preemptive) Arrival Time( A.T )	FCFS(Preemptive) Burst Time ( B.T )
P0	3	1
P1	9	60
P2	7	10
P4	0	1
P3	1	3
P2	4	2
P5	1	0
P6	5	2

 

 

1.2. First Come First Serve ( Non-Preemptive )

In First Come First Serve Non-Preemptive we use processes (P) completely time, which means burst time is completely used. OR in Non-Preemptive burst time completely use.

Rules of FCFS( Non-Preemptive )

1)  In First Come First Serve Non-Preemptive Arrival Time ( A.T ) small choose.

2) In First Come First Serve Non-Preemptive if Arrival Time ( A.T ) is equal then we apply First Come First Serve.

3) If Burst Time (B.T) is only given then we use First Come First Serve.

Question No   1.

FCFS(NP) Process id	FCFS(NP) Burst Time ( B.T )
P1	10
P2	4
P3	3
P4	5

Here we set aside the Average Waiting Time ( AWT ) for First Come First Serve Non-Preemptive so you see beneath:

FCFS(NP) Average Waiting Time ( AWT )
AWT ( B.T )
P1	10
P2	14
P3	17
P4	22
WT	63
AWT	63 / 4
	= 15.75

 

Question No   2.

FCFS(NP)  Process id ( P.id )	FCFS(NP)  Burst Time ( B.T )
P3	3
P2	4
P4	5
P1	10

 Here we set aside the Average Waiting Time ( AWT ) for First Come First Serve Non-Preemptive so you see beneath:

FCFS(NP) Average Waiting Time ( AWT )
AWT ( B.T )
P1	22
P2	7
P3	3
P4	12
WT	44
AWT	44 / 4
	= 11

 

Question No .3.

FCFS(NP) Process id	FCFS(NP) ArrivalTime(A.T)	FCFS(NP) Burst Time( B.T )
P1	2	4
P2	3	2
P3	0	8
P4	4	6

Here we apply rule number 1 Arrival Time ( A.T ) small choose.

Here we measure Total Arrival Time ( TAT ) & Average Waiting Time ( AWT )  for FCFS( Non-Preemptive ) so you see below:

FCFS(NP) Total Arrival Time ( TAT)				FCFS(NP) Average Waiting Time ( AWT )
FCFS(NP) TAT ( End – A.T )				FCFS(NP) AWT ( TAT – B.T )
P1	12 -2	10		P1	10 – 4	6
P2	14 -3	11		P2	11 – 2	9
P3	8 – 0	8		P3	8 – 8	0
P4	20 - 4	16		P4	16 - 6	10
TAT		45		WT		25
ATAT		45 / 4		AWT		25 / 4
		= 11.25				= 6.25

 

Question No .4.

FCFS(NP) Process id	FCFS(NP) ArrivalTime(A.T)	FCFS(NP) Burst Time( B.T )
P1	2	4
P2	3	2
P3	1	3
P4	4	5
P5	0	2
P6	2	1
P7	1	0
P8	0	0

Here we apply rule number 1 Arrival Time ( A.T ) small choose.

Here we measure Total Arrival Time ( TAT ) & Average Waiting Time ( AWT )  for FCFS( Non-Preemptive ) so you see below:

FCFS(NP) Total Arrival Time ( TAT)				FCFS(NP) Average Waiting Time ( AWT )
FCFS(NP) TAT ( End – A.T )				FCFS(NP) AWT ( TAT – B.T )
P1	9 -2	7		P1	7 – 4	3
P2	12 -3	9		P2	9 – 2	7
P3	5 – 1	4		P3	4 – 3	1
P4	17 - 4	13		P4	13 - 5	8
P5	2 -0	2		P5	2 -2	0
P6	10 -2	8		P6	8 -1	7
P7	5 – 1	4		P7	4 – 0	4
P8	2 - 0	2		P8	2 - 0	2
TAT		49		WT		32
ATAT		49 / 8		AWT		32 / 8
		= 6.125				= 4

 

 

Example No .1.

FCFS(NP) Process id	FCFS(NP) ArrivalTime(A.T)	FCFS(NP) Burst Time( B.T )
P1	3	4
P2	2	2
P3	0	8
P4	1	3

 

 

Here we summarize Total Arrival Time ( TAT ) & Average Waiting Time ( AWT )  for FCFS( Non-Preemptive ) so you see in below:

FCFS(NP) Total Arrival Time ( TAT)				FCFS(NP) Average Waiting Time ( AWT )
FCFS(NP) TAT ( End – A.T )				FCFS(NP) AWT ( TAT – B.T )
P1	17 -3	14		P1	14 – 4	10
P2	13 -2	11		P2	11 – 2	9
P3	8 – 0	8		P3	8 – 8	0
P4	11 - 1	10		P4	10 - 3	7
TAT				WT		26
ATAT		43 / 4		AWT		26 / 4
		= 10.75				= 6.5

Example No .2.

FCFS(NP) Process id	FCFS(NP) ArrivalTime(A.T)	FCFS(NP) Burst Time( B.T )
P1	0	3
P2	2	2
P2	2	1
P3	3	3

 

Here we measure Total Arrival Time ( TAT ) & Average Waiting Time ( AWT )  for FCFS( Non-Preemptive ) so you see in below:

FCFS(NP) Total Arrival Time ( TAT)				FCFS(NP) Average Waiting Time (AWT )
FCFS(NP) TAT ( End – A.T )				FCFS(NP) AWT ( TAT – B.T )
P1	3 -0	0		P1	0 – 3	-3
P2	5 -2	3		P2	3 – 2	1
P2	6 – 2	4		P2	4 – 1	3
P3	9 - 3	6		P3	6 - 3	3
TAT		13		WT		4
ATAT		13 / 4		AWT		4 / 4
		= 3.25				= 1

 

Example No .3.

FCFS(NP) Process id	FCFS(NP) ArrivalTime(A.T)	FCFS(NP) Burst Time( B.T )
P0	4	9
P1	2	2
P2	2	6
P1	0	1

Here we find Total Arrival Time ( TAT ) & Average Waiting Time ( AWT )  for FCFS( Non-Preemptive ) so you see below:

FCFS(NP) Total Arrival Time ( TAT)				FCFS(NP) Average Waiting Time ( AWT )
FCFS(NP) TAT ( End – A.T )				FCFS(NP) AWT ( TAT – B.T )
P0	18 -4	14		P0	14 – 9	5
P1	1 -2	-1		P1	-1 – 2	-3
P1	3 – 2	1		P1	1 – 6	-5
P2	9 - 0	9		P2	9 - 1	8
TAT		23		WT		5
ATAT		23 / 4		AWT		5 / 4
		= 5.75				= 1.25

Example No .4.

FCFS(NP) Process id	FCFS(NP) ArrivalTime(A.T)	FCFS(NP) Burst Time( B.T )
P0	3	0
P0	1	2
P1	2	4
P1	0	1

Here we count Total Arrival Time ( TAT ) & Average Waiting Time ( AWT )  for FCFS( Non-Preemptive ) so you see below:

FCFS(NP) Total Arrival Time ( TAT)				FCFS(NP) Average Waiting Time ( AWT )
FCFS(NP) TAT ( End – A.T )				FCFS(NP) AWT ( TAT – B.T )
P0	3 -3	0		P0	0 – 0	0
P0	7 -1	6		P0	6 – 2	4
P1	1 – 2	-1		P1	-1 – 4	-5
P1	7 - 0	7		P1	7 - 1	6
TAT				WT		5
ATAT		12 / 4		AWT		5 / 4
		= 3				= 1.25

 

2.1. Shortest Remaining Job First (Preemptive)

In SRJF (Preemptive) we utilize a more modest Burst Time(B.T) as per Arrival Time(A.T), and that implies a more modest burst time utilized contrasted with Arrival Time(A.T). In SRJF (Preemptive) when cycles arrive at more prominent upsides of Arrival Time(A.T). Later or over the more noteworthy upsides of Arrival Time(A.T) then a couple of cycles are Non-Preemptive.

Rules of  SRJF ( Preemptive )

1) Small Burst Time ( B.T ) select for SRJF ( Preemptive ) according to Arrival Time(A.T).

2)  In SRJF ( Preemptive ) in the event that Arrival Time ( A.T ) values are equivalent, we see or pick little upsides of Burst Time ( B.T )

3) In SRJF ( Preemptive ) assuming Arrival Time ( A.T ) and Burst Time ( B.T ) values are equivalent then we apply First Come First Serve.

These situations we apply to the inquiry, for example, :

Question No   .1.

SRJF  Process id	SRJF Arrival Time( A.T )	SRJF Burst Time ( B.T )
P1	0	2
P2	0	1
P3	0	1
P4	0	4

So here we calculate the Total Arrival Opportunity ( TAT ) and Average Waiting Time ( AWT ) of SRJF ( Preemptive ) so under:

SRJF  Total Arrival Time ( TAT )				SRJF Average Waiting Time ( AWT )
SRJF TAT ( End – A.T )				SRJF  AWT ( TAT – B.T )
P1	4 - 0	4		P1	4 – 2	2
P2	1 – 0	1		P2	1 – 1	0
P3	2 – 0	2		P3	2 – 1	1
P4	8 – 0	8		P4	8 – 4	4
TAT		15		WT		7
ATAT		15 / 4		AWT		7 / 4
		= 3.75				= 1.75

 

Question No   .2.

SRJF  Process id	SRJF Arrival Time( A.T )	SRJF Burst Time ( B.T )
P1	2	6
P2	0	5
P3	1	8
P4	2	3

So here we calculate Total Arrival Opportunity ( TAT ) and Average Waiting Time ( AWT ) of SRJF ( Preemptive ) so under:

Total Arrival Time ( TAT ) SRJF				Average Waiting Time ( AWT ) SRJF
TAT ( End – A.T ) SRJF				AWT ( TAT – B.T ) SRJF
P1	14 – 2	12		P1	12 – 6	6
P2	5 – 0	5		P2	5 – 5	0
P3	22 – 1	21		P3	21 – 8	13
P4	8 – 2	6		P4	6 – 3	3
TAT		44		WT		22
ATAT		44 / 4		AWT		22 / 4
		= 11				= 5.5

 

Question No   .3.

SRJF  Process id	SRJF Arrival Time( A.T )	SRJF Burst Time ( B.T )
P1	2	3
P2	3	2
P3	1	4
P4	0	4
P5	4	2
P6	2	1
P7	3	5
P8	1	2
P9	0	6
P10	4	5

So here we calculate the Total Arrival Opportunity ( TAT ) and Average Waiting Time ( AWT ) of SRJF ( Preemptive ) so under:

SRJF  Total Arrival Time( TAT )				SRJF Average Waiting Time ( AWT )				SRJF Response Time (RT)
TAT ( End – A.T )				AWT ( TAT – B.T )				RT ( Start – A.T)
P1	14 – 2	12		P1	12 – 3	9		P1	11 – 0	11
P2	6 – 3	3		P2	3 – 2	1		P2	4 – 1	3
P3	18 – 1	17		P3	17 – 4	13		P3	14 – 2	12
P4	11 – 0	11		P4	11 – 4	7		P4	8 – 3	5
P5	8 – 4	4		P5	4 – 2	2		P5	6 – 1	5
P6	4 – 2	2		P6	2 – 1	1		P6	3 – 0	3
P7	23 – 3	20		P7	20 – 5	15		P7	18 – 2	16
P8	3 – 1	2		P8	2 – 2	0		P8	2 – 3	-1
P9	34 – 0	34		P9	34 – 6	28		P9	28 – 4	24
P10	28 – 4	24		P10	24 – 5	19		P10	23 – 2	21
TAT		129		WT		95		RT		99
ATAT		129/10		AWT		95/10		ART		99/10
		= 12.9				=9.5				= 9.9

 

Example No   .1.

SRJF  Process id	SRJF Arrival Time( A.T )	SRJF Burst Time ( B.T )
P1	12	0
P2	10	1
P3	0	2
P4	4	6

 

Example No   .2.

SRJF  Process id	SRJF Arrival Time( A.T )	SRJF Burst Time ( B.T )
P0	4	0
P2	0	12
P2	7	3
P1	6	10

 

Example No   .3.

SRJF  Process id	SRJF Arrival Time( A.T )	SRJF Burst Time ( B.T )
P1	4	3
P0	2	5
P0	0	1
P2	1	0

 

Example No   .4.

SRJF  Process id	SRJF Arrival Time( A.T )	SRJF Burst Time ( B.T )
P1	8	9
P0	0	6
P2	2	1
P1	4	7

 

Example No   .5.

SRJF  Process id	SRJF Arrival Time( A.T )	SRJF Burst Time ( B.T )
P1	7	1
P0	2	0
P2	3	3
P3	9	2

 

Example No   .6.

SRJF  Process id	SRJF Arrival Time( A.T )	SRJF Burst Time ( B.T )
P2	2	3
P3	4	6
P1	7	1
P0	0	6

 

 

2.2. Shortest Job First (Non-Preemptive)

In SJF (Non-Preemptive) we make use of a extra modest Arrival Time(A.T) when time for a startup implies a greater modest arrival time once time used.

Rules for SJF( N-P )

1) Small Arrival Time ( A.T ) for SJF Non Preemptive choose once time for a startup.

2) After Arrival Time ( A.T ) is chosen then Burst Time ( B.T ) small values choose, if Burst Time ( B.T )  of  SJF (Non-Preemptive) are equal then we apply First Come First Serve for further processes.

In the two Scenarios, we apply the inquiry such:

Question Number   .1.

SJF( NP ) Processes id	SJF( NP ) Arrival Times( A.T )	SJF( NP ) Burst Time ( B.T )
Pa	1	10
Pb	2	3
Pc	3	8
Pd	4	9
Pe	5	6
Pf	3	3
Pg	2	2
Ph	3	1

Here we find the Total Arrival Time ( TAT ) & Average Waiting Time ( AWT ) of Non-Preemptive so below:

SJF( NP ) Total Arrival Time ( TAT )				SJF( NP )Average Waiting Time(AWT )
SJF( NP ) TAT ( End – A.T )				SJF( NP ) AWT ( TAT – B.T )
Pa	10 -1	9		Pa	9 – 10	-1
Pb	16 -2	14		Pb	14 – 3	11
Pc	33 – 3	30		Pc	30 – 8	22
Pd	42 - 4	38		Pd	38 – 9	29
Pe	25 -5	20		Pe	20 -6	14
Pf	19 -3	16		Pf	16 -3	13
Pg	13 – 2	11		Pg	11 – 2	9
Ph	11 - 3	8		Ph	8 - 1	7
TAT		146		WT		104
ATAT		146 / 8		AWT		104 / 8
		= 18.25				= 13

 

Question Number   .2.

SJF( N-P ) Process id ( P.id )	SJF( N-P ) Arrival Time(A.T )	SJF( N-P ) Burst Time ( B.T )
P11	5	10
P21	0	3
P31	1	7
P41	2	9
P51	6	6
P61	2	3
P71	3	2
P81	5	1

 Here we put away the Total Arrival Opportunity ( TAT ) of SJF(N-P) and the Average Waiting Time ( AWT ) of SJF(N-P) so underneath:

SJF( N-P ) Total Arrival Time ( TAT )				SJF( N-P ) Average Waiting Time ( AWT )
SJF( N-P ) TAT ( End – A.T )				SJF( N-P ) AWT ( TAT – B.T )
P11	41 -5	36		P11	36 – 10	26
P21	3 -0	3		P21	3 – 3	0
P31	22 – 1	21		P31	21 – 7	14
P41	31 – 2	29		P41	29 – 9	20
P51	15 -6	9		P51	9 -6	3
P61	9 -2	7		P61	7 -3	4
P71	6 – 3	3		P71	3 – 2	1
P81	4 - 5	-1		P81	-1 - 1	-2
TAT		107		WT		66
ATAT		107 / 8		AWT		66 / 8
		= 13.375				= 8.25

 

Question Number   .3.

SJF( N-Pr ) Process id ( P.id )	SJF( N-Pr ) Arrival Time( A.T )	SJF( N-Pr ) Burst Time ( B.T )
P10	6	10
P20	7	4
P30	0	7
P40	4	9
P50	6	5
P60	2	6
P70	1	2
P80	3	1

Here we set aside the Total Arrival Opportunity ( TAT ) of SJF(N-P) and the Average Waiting Time ( AWT ) of SJF(N-P) so beneath:

SJF( N-Pr ) Total Arrival Time ( TAT )				SJF( N-Pr ) Average Waiting Time ( AWT )
SJF( N-Pr ) TAT ( End – A.T )				SJF( N-Pr ) AWT ( TAT – B.T )
P10	44 -6	38		P10	38 – 10	28
P20	14 -7	7		P20	7 – 4	3
P30	7 – 0	7		P30	7 – 7	0
P40	34 – 4	30		P40	30 – 9	21
P50	19 -6	13		P50	13 -5	8
P60	25 -2	23		P60	23 -6	17
P70	10 – 1	9		P70	9 – 2	7
P80	8 - 3	5		P80	5 – 1	4
TAT		132		WT		88
ATAT		132 / 8		AWT		88 / 8
		= 16.5				= 11

 

Question Number   .4.

SJF( N-P ) Processes id ( P.id )	SJF( N-P) Arrival Time( A.T )	SJF( N-P ) Burst Time ( B.T )
P101	4	10
P201	5	0
P301	6	2
P401	2	5
P501	0	6
P601	3	7
P701	3	4
P801	3	1

 

Here we find Total Arrival Time ( TAT ) of SJF(NP) & Average Waiting Time ( AWT ) of SJF(NP) so below:

SJF( N-P ) Total Arrival Time ( TAT )				SJF( N-P ) Average Waiting Time ( AWT )
TAT ( End – A.T )				AWT ( TAT – B.T )
P101	35 -4	31		P101	31 – 10	21
P201	6 -5	1		P201	1 – 0	1
P301	9 – 6	3		P301	3 – 2	1
P401	18 – 2	16		P401	16 – 5	11
P501	6 -0	6		P501	6 -6	0
P601	25 -3	22		P601	22 -7	15
P701	13 – 3	10		P701	10 – 4	6
P801	7 - 3	4		P801	4 - 1	3
TAT		93		WT		58
ATAT		93 / 8		AWT		58 / 8
		= 11.625				= 7.25

 

Example Number   .1.

Process id ( P.id )	Arrival Time( A.T )	Burst Time ( B.T )
P1	0	10
P2	8	3
P3	3	0
P4	4	0
P5	1	1
P6	3	4
P7	6	9
P8	3	1

 

Example Number   .2.

Process id ( P.id )	Arrival Time( A.T )	Burst Time ( B.T )
P1	0	5
P0	4	1
P0	3	0
P2	9	6
P1	4	1
P3	3	0
P4	2	2
P5	3	1

 

Example Number   .3.

Process id ( P.id )	Arrival Time( A.T )	Burst Time ( B.T )
P0	5	6
P2	0	4
P1	3	8
P3	0	3
P4	1	1
P5	0	0
P6	2	2
P7	0	8

 

 

Example Number   .4.

Process id ( P.id )	Arrival Time( A.T )	Burst Time ( B.T )
P0	3	2
P2	4	7
P3	2	6
P2	8	4
P4	1	1
P5	0	0
P6	2	2
P7	0	0

 

Friends, whatever data I will share with you at the end of this course, read carefully and understand it. Dears if you understand this thing well then you will be easy on quizzes and in exams and you will get good marks and you will give me prayers. Friends it depends on you how you think and practice for this book. Shame on you if you don't practice on this topic

Good Luck

3.1. Banker’s  Algorithm.

Q1. Consider the following snapshot of a system:

	ALLOCATION				MAX				AVAILABLE
	A	B	C	D	A	B	C	D	A	B	C	D
P0	0	0	1	2	0	0	1	2	2+R6	2+R5	2+R4	2+R3
P1	1	0	0	0	1	7	5	0
P2	1	3	5	4	2	3	5	6
P3	0	6	3	2	0	6	5	2
P4	0	0	1	4	0	6	5	6

 

Where

R3= 3^rd Digit of your Registration number, R4= 4^th Digit of your Registration number

R5= 5^th Digit of your Registration number, R6= 6^th Digit of your Registration number

Example: MCS 181001

1	8	1	0	0	1
R1	R2	R3	R4	R5	R6

 

Apply the Banker’s algorithm to provide a safe sequence of execution, if it is possible.  Show all intermediate steps.

Sol:

My Roll Number for Banker's  Algorithm that is MCS 181046

1	8	1	0	4	6
R1	R2	R3	R4	R5	R6

 

Now we find A, B, C, and D values  which are given in the above data table, as you see in the below table.

A	B	C	D
2 + R6	2 + R5	2 + R4	2 + R3
2 + 6	2 + 4	2 + 0	2 + 1
8	6	2	3

 

So we have  the values of A = 8 , B = 6 , C = 2 , D = 3

	ALLOCATION				MAX				Need(Max-Allocation)				AVAILABLE
	A	B	C	D	A	B	C	D	A	B	C	D	A	B	C	D
P0	0	0	1	2	0	0	1	2	0	0	0	0	8	6	2	3
P1	1	0	0	0	1	7	5	0	0	7	5	0	8	6	3	5
P2	1	3	5	4	2	3	5	6	1	0	0	2	9	9	8	9
P3	0	6	3	2	0	6	5	2	0	0	2	0	9	15	11	11
P4	0	0	1	4	0	6	5	6	0	6	4	2	9	15	12	15
													10	15	12	15

 

P0 à Need ≤ Available

          0 0 0 0 ≤ 8 6 2 3  True

Extra steps you ignore :

Here we only for understanding this scenario below the table:

P0	Need ≤ Available		True / False
	0	8	T
	0	6	T
	0	2	T
	0	3	T
Overall Condition	True

 

Here all values are true then the overall condition is true, if any value is false then the complete condition is false.

When all values are true then

Available = Available +  Allocation

               = 8 6 2 3  + 0 0 1 2

               = 8 6 3 5

 

Available	Available +  Allocation		Result
	8	0	8
	6	0	6
	2	1	3
	3	2	5

 

Here no need for an extra explanation for the exam or quiz this is just for the demo.

P1 à Need ≤ Available

          0 7 5 0 ≤ 8 6 3 5  False

Here which Processor condition is false then again calculate or check after completing other processes.

Extra steps you ignore :

Here we only for understanding this scenario below the table:

P1	Need ≤ Available		True / False
	0	8	T
	7	6	F
	5	3	F
	0	5	T
Overall Condition	False

 

If all values are not true then the overall condition is false. Here no need for an extra explanation for exams or quizzes this is just for the demo.

When all values are true then

Available = Available +  Allocation

Else no need for this formula when the condition is false.

P2 à Need ≤ Available

          1 0 0 2 ≤ 8 6 3 5  True

Extra steps you ignore :

Here we only for understanding this scenario below the table such:

P2	Need ≤ Available		True / False
	1	8	T
	0	6	T
	0	3	T
	2	5	T
Overall Condition	True

 

Here all values are true then overall condition is true, if any value is false then complete condition is false.

When all values is true then

Available = Available +  Allocation

               = 8 6 3 5  + 1 3 5 4

               = 9 9 8 9

Available	Available +  Allocation		Result
	8	1	9
	6	3	9
	3	5	8
	5	4	9

 

Here no need for an extra explanation for the exam or quiz this is just for the demo.

P3 à Need ≤ Available

          0 0 2 0 ≤ 9 9 8 9  True

Extra steps you ignore :

Here we only for understanding this scenario below the table:

P3	Need ≤ Available		True / False
	0	9	T
	0	9	T
	2	8	T
	0	9	T
Overall Condition	True

 

Here all values are true then the overall condition is true, if any value is false then the complete condition is false.

When all values are true then

Available = Available +  Allocation

               = 9 9 8 9  + 0 6 3 2

               = 9 15 11 11

Available	Available +  Allocation		Result
	9	0	9
	9	6	15
	8	3	11
	9	2	11

 

Here no need for an extra explanation for the exam or quiz this is just for the demo.

P4 à Need ≤ Available

          0 6 4 2 ≤ 9 15 11 11  True

Extra steps you ignore :

Here we only for understanding this scenario below the table such:

P4	Need ≤ Available		True / False
	0	9	T
	6	15	T
	4	11	T
	2	11	T
Overall Condition	True

 

Here all values are true then overall condition is true, if any value is false then complete condition is false.

When all values is true then

Available = Available +  Allocation

               = 9 15 11 11  + 0 0 1 4

               = 9 15 12 15

Available	Available +  Allocation		Result
	9	0	9
	15	0	15
	11	1	12
	11	4	15

 

Here no need for an extra explanation for the exam or quiz this is just for the demo.

P1 à Need ≤ Available

          0 7 5 0 ≤ 9 15 12 15  True

Extra steps you ignore :

Here we only for understanding this scenario below the table such:

P1	Need ≤ Available		True / False
	0	9	T
	7	15	T
	5	12	T
	0	15	T
Overall Condition	True

 

Here all values are true then overall condition is true, if any value is false then complete condition is false.

When all values is true then

Available = Available +  Allocation

               = 9 15 12 15  + 1 0 0 0

               = 10 15 12 15

Available	Available +  Allocation		Result
	9	1	10
	15	0	15
	12	0	12
	15	0	15

 

Here no need for an extra explanation for the exam or quiz this is just for the demo.

 

Yes, a system is in a safe state. Because

Need ≤ Available

0 6 4 2 ≤ 10 15 12 15

So the system is in a safe state.

Safe sequence: < P0 , P2 , P3, P4 , P1 >

P0 à P2 àP3 à P4 à P1

Now find the Instance of R?

 According to the given Allocation values, we easily find the Instance of R

	ALLOCATION
	A	B	C	D
P0	0	0	1	2
P1	1	0	0	0
P2	1	3	5	4
P3	0	6	3	2
P4	0	0	1	4

 

So Instance of R is :

Instance of R
An instance of R1 (A)	8	1	1			10
An instance of R2 (B)	6	3	6			15
An instance of R3 (C)	2	1	5	3	1	12
An instance of R4 (D)	3	2	4	2	4	15

 

4.1. Round Robin ( RR ) with Quantum q = 2, q=3, q=20 | Round Robin ( Preemptive )

In Round Robin ( RR ) we have some scenario-based questions that are

1) Quantum q = 2.

2) Quantum q = 3.

3) Quantum q = 20 with Priority base (High and Low).

4) Round Robin ( Preemptive ) with Quantum q = 1.

Rules of  Round Robin ( RR )

1)  As indicated by Arrival Time ( A.T ) we pick processes for Round Robin.

So we solve step by step first one is

1) Quantum q = 2.

Process id for RR	Arrival Time( A.T ) of RR	Burst Time ( B.T ) of RR
R1	0	4
R2	2	3
R3	5	1
R4	4	2
R5	3	6

Here we carve out Total Arrival Opportunity ( TAT ) and Average Waiting Time ( AWT ) for Round Robin so under you notice:

Total Arrival Time ( TAT ) of RR				Average Waiting Time ( AWT ) of RR
TAT ( End – A.T ) for RR				AWT ( TAT – B.T )  for RR
R1	8 -0	8		R1	8 – 4	4
R2	11 -2	9		R2	9 – 3	6
R3	9 – 5	5		R3	5 – 1	4
R4	12 – 4	8		R4	8 – 2	6
R5	16 – 3	13		R5	13 – 6	7
TAT		43		WT		27
ATAT		43 / 5		AWT		27 / 5
		= 8.6				= 5.4

 So we solve step by step second one is

2) Quantum q = 3.

Process id for RR	Arrival Time( A.T ) of RR	Burst Time ( B.T ) of RR
R11	5	5
R21	4	6
R31	3	7
R41	1	9
R51	2	2
R61	6	3

Here we carve out Total Arrival Time ( TAT ) and Average Waiting Time ( AWT ) for Round Robin so under your notice:

Total Arrival Time ( TAT ) of RR				Average Waiting Time ( AWT ) of RR
TAT ( End – A.T ) for RR				AWT ( TAT – B.T ) for RR
R11	31 -5	26		R11	26 – 5	21
R21	27 -4	23		R21	23 – 6	17
R31	32 – 3	29		R31	29 – 7	22
R41	29 – 1	28		R41	28 – 9	19
R51	6 – 2	4		R51	4 – 2	2
R61	21 – 6	15		R61	15 – 3	12
TAT		125		WT		93
ATAT		125 / 6		AWT		93 / 6
		= 20.83				= 15.5

 

So we solve step by step third one is

3) Quantum q = 20 with Priority base (High and Low).

Process id for RR	Arrival Time( A.T )	Burst Time ( B.T )	Priority base (RR)
R10	0	60	1 ( H )
R20	10	20	1
R30	20	10	2 ( L )

  

Here we find out Total Arrival Time ( TAT ) and Average Waiting Time ( AWT ) for Round Robin so you see below:

Total Arrival Time ( TAT ) of RR				Average Waiting Time ( AWT ) of RR
TAT ( End – A.T ) for RR				AWT ( TAT – B.T ) for RR
R10	90 -0	90		R10	90 – 60	30
R20	40 -10	30		R20	30 – 20	10
R30	50 – 20	30		R30	30 – 10	20
TAT		150		WT		60
ATAT		150 / 3		AWT		60 / 3
		= 50				= 20

So we solve step by step fourth one is

4) Round Robin ( Preemptive ) with Quantum q = 1

Process id for RR	Arrival Time( A.T ) of RR	Burst Time ( B.T ) of RR
R1	0	2
R2	1	1
R3	2	6
R4	3	3
R5	1	4
R6	0	5
R7	2	3
R8	3	6
R9	4	2
R10	2	1

 

Here we find out Total Arrival Time ( TAT ) and Average Waiting Time ( AWT ) for Round Robin for further steps:

Total Arrival Time ( TAT ) of RR				Average Waiting Time ( AWT ) of RR				Response Time (RT) of RR
TAT ( End – A.T ) for RR				AWT ( TAT – B.T ) for RR				RT ( Start – A.T) for RR
R1	5 – 0	5		R1	5 – 2	3		R1	0 – 0	0
R2	3 – 1	2		R2	2 – 1	1		R2	2 – 1	1
R3	32 – 2	30		R3	30 – 6	24		R3	5 – 2	3
R4	24 – 3	21		R4	21 – 3	18		R4	9 – 3	6
R5	26 – 1	25		R5	25 – 4	21		R5	3 – 1	2
R6	28 – 0	28		R6	28 – 5	23		R6	1 – 0	1
R7	22 – 2	20		R7	20 – 3	17		R7	6 – 2	4
R8	33 – 3	30		R8	30 – 6	24		R8	10 – 3	7
R9	19 – 4	15		R9	15 – 2	13		R9	11 – 4	7
R10	8 – 2	6		R10	6 – 1	5		R10	7 – 2	5
TAT		182		WT		149		RT		36
ATAT		182/10		AWT		149/10		ART		36/10
		= 18.2				=14.9				=3.6

 

Note: Friend’s one point to keep in mind is fully practice about this topic and well think how to ask questions in exams or quizzes. Exam point of view put any digit of the registration number in Round robin for the solution, so best of luck. 

5.1. Priority Scheduling ( Preemptive )

Rules of Priority Scheduling-Preemptive

1) In this scenario According to Arrival Time ( A.T ), we comparison of Priority.

2) If Arrival Time ( A.T ) is same or equal then we apply First Come First Serve for this process.

Question Num .1.

Process id ( P.id )	Arrival Time( A.T )	Burst Time ( B.T )	Priority
P1	0	10	3
P2	2	1	1( H )
P3	1	2	4
P4	3	1	5( L )
P5	4	5	2

 

Total Arrival Time ( TAT )				Average Waiting Time ( AWT )
TAT ( End – A.T )				AWT ( TAT – B.T )
P1	14 -2	12		P1	12 – 9	3
P2	5 -1	4		P2	4 – 4	0
P3	19 – 0	19		P3	19 – 6	13
P4	21 – 4	17		P4	17 – 2	15
P5	28 - 3	25		P5	25 - 7	18
TAT		77		WT		49
ATAT		77 / 5		AWT		49 / 5
		= 15.4				= 9.8

 

Question Num .2.

 

Process id ( P.id )	Arrival Time( A.T )	Burst Time ( B.T )	Priority
P0	3	4	5( H )
P1	2	6	2
P2	4	2	1( L)
P3	0	1	3
P4	1	3	4

 

 

Total Arrival Time ( TAT )				Average Waiting Time ( AWT )
TAT ( End – A.T )				AWT ( TAT – B.T )
P0	7 -3	4		P0	4 – 4	0
P1	14 -2	12		P1	12 – 6	6
P2	16 – 4	12		P2	12 – 2	10
P3	1 – 0	1		P3	1 – 1	0
P4	8 - 1	7		P4	7 - 3	4
TAT		36		WT		20
ATAT		36 / 5		AWT		20 / 5
		= 7.2				= 4

 

5.2. Priority Scheduling ( Non-Preemptive )

Rules of Priority Scheduling-Non-Preemptive

1) Any processor has a small Arrival Time ( A.T ) that we use as First Come First Serve for the processes.

Process id ( P.id )	Arrival Time( A.T )	Burst Time ( B.T )	Priority
P1	5	2	7( L )
P2	6	4	6
P3	3	6	5
P4	2	3	4
P5	1	5	3( H)

 

PS Total Arrival Time ( TAT )				PS Average Waiting Time ( AWT )
PS TAT ( End – A.T )				PS AWT ( TAT – B.T )
P1	17 -5	12		P0	12 – 2	10
P2	21 -6	15		P1	15 – 4	11
P3	15 – 3	12		P2	12 – 6	6
P4	9 – 2	7		P3	7 – 3	4
P5	6 - 1	5		P4	5 - 5	0
TAT		51		WT		31
ATAT		51 / 5		AWT		31 / 5
		= 10.2				= 6.2

 

6.1. Selfish Round Robin( SRR )

Show the schedule using Selfish RR and also provide the memory map. Assume that there are only 3-page frames available in the main memory. Use the LFU page replacement algorithm and calculate the Page Fault count. Use q=1, accepted=1 and new=2.

 

Process ID	Burst Time	Arrival Time
P1	7	C1
P2	2	C2
P3	4	C3
P4	7	C4
P5	4	C5
P6	3	C6

 

Where

C1= 1^st Digit of your Roll number, C2= 2^nd Digit of your Roll number

C3= 3^rd Digit of your Roll number, C4= 4^th Digit of your Roll number

C5= 5^th Digit of your Roll number, C6= 6^th Digit of your Roll number

Example: MCS 181001

1	8	1	0	0	1
C1	C2	C3	C4	C5	C6

 Sol:

My Roll Number for Selfish Round robin is MCS 181046

1	8	1	0	4	6
C1	C2	C3	C4	C5	C6

 So currently Arrival Time values may be modified these above values are positioned in the above table that is given inside the inquiry, as an instance, you discover within the beneath the table.

Process ID	Burst Time	Arrival Time
P1	7	1
P2	2	8
P3	4	1
P4	7	0
P5	4	4
P6	3	6

 

Using Selfish RR, memory map, 3 page-frames, use LFU page replacement algorithm and calculate Page Fault count? Use q=1, accepted=1 and new=2.

n(2)	a(1)
P2, P6, P5, P3, P1, P4	P4
	P1

 

Here keep in mind not to enter the first processor P2 according to the table P4 has an arrival time is 0, so P4 is entered first and moves firstly in a(1). In the n(2) column you see from P4 to P2as back word sequence P4 is entered first and moved firstly in a(1) and at the end, P2 has entered fi and moved lastly in a(1).

Memory Management ( LFU )

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P4

P6

P5

P1

P1

P1

P1

P1

P1

P5

P1

P1

P1

P6

P5

P1

P1

P1

P1

P1

P1

P1

P1

P1

P1

P1

P1

P1

P3

P3

P3

P3

P3

P3

P3

P3

P3

P3

P3

P3

P3

P3

P2

P2

P6

P5

P5

P2

H

H

H

H

H

H

H

H

H

H

H

H

H

 

This is a complete solution in the below table.

 

This is a further explanation of the above table which you see below table.

P4

P4

P1

P3

P4

P1

P3

P4

P5

P1

P3

P4

P6

P5

P1

P3

P2

P4

P6

P5

P1

P2

P4

P6

P5

P1

P1

P4

P4

P1

P3

P4

P1

P3

P4

P5

P1

P3

P4

P6

P5

P1

P3

P2

P4

P6

P5

P1

P2

P4

P6

P5

P1

P1

P4

P4

P1

P3

P4

P1

P3

P4

P5

P1

P3

P4

P6

P5

P1

P3

P2

P4

P6

P5

P1

P2

P4

P6

P5

P1

P1

P4

P4

P1

P3

P4

P1

P3

P4

P5

P1

P3

P4

P6

P5

P1

P3

P2

P4

P6

P5

P1

P2

P4

P6

P5

P1

P1

P4

P4

P1

P3

P4

P1

P3

P4

P5

P1

P3

P4

P6

P5

P1

P3

P2

P4

P6

P5

P1

P2

P4

P6

P5

P1

P1

P4

P4

P1

P3

P4

P1

P3

P4

P5

P1

P3

P4

P6

P5

P1

P3

P2

P4

P6

P5

P1

P2

P4

P6

P5

P1

P1