Algorithm Explained PDF

Preview

Summary

Tutorial Letter 102/1/Operating Systems and ArchitectureSemesters 1School of ComputingThis tutorial letter contains important informationabout your module.Bar codeCOSPart IContents1) Introduction ...........................................................................................................

Description

Tutorial Letter 102/1/2014 Operating Systems and Architecture

COS3721 Semesters 1 School of Computing This tutorial letter contains important information about your module.

Bar code

Page 1 of 22

Part I Contents 1)

Introduction ........................................................................................................................................2

2)

Turnaround Time and Waiting Time..................................................................................................2

3)

Exercises ...........................................................................................................................................

1) Introduction

The purpose of this tutorial letter is to:  Present two formulae to calculate the Turnaround Time and the Waiting Time respectively of a set of processes.  Show the construction of Gantt charts for a number of scheduling algorithms.  Show how the two formulae are used to calculate the turnaround times and waiting times of a set of processes.  Show how various quantum settings determine the resulting scheduling algorithm. Next we give mathematical formulae for the turnaround time and the waiting time. 2)

Turnaround Time and Waiting Time

Turnaround Time The turnaround time of a job is defined as the interval from the time of submission to the time of completion of the job. Therefore:

Turnaround time = Time of completion - Time of submission

For non-pre-emptive algorithms, there is a single waiting block and then a single processing block. For pre-emptive algorithms there is a succession of waiting times interspersed with processing times. The turnaround time is the sum of these two times. We assume the I/O-time to be included in the term ∑ waiting time. Page 2 of 22

Waiting Time The waiting time is defined as the sum of all the times that a process waits in the system. Therefore, it is the sum of the times that the CPU is not allocated to the process. From the definition of turnaround time we observe that: ∑ waiting time = Turnaround time − ∑ CPU burst time

The quantity ∑ CPU burst time is equal to the total length of the process. Next we present a number of examples for calculating Gantt charts and thereafter calculate the respective turnaround times and the waiting times. 3)

Exercises

Exercise 3.1 Consider the following set of processes, CPU burst times in milliseconds and priorities shown below. Suppose we have to execute these processes with one processor:

Process

Burst time

Priorit y

P1

10

3

P2

1

1

P3

2

3

P4

1

4

P5

5

2

Assume that the processes arrive in the order P1, P2, P3, P4, P5, and that they are all ready to execute at time 0. (a) Draw four Gantt charts, each illustrating the execution of these processes using the scheduling algorithms First-Come-First-Served, Shortest-Job-First without preemption, a non-pre-emptive priority scheduling algorithm and Round-Robin (quantum = 1). Assume that a smaller priority number indicates a higher priority. (b) Calculate the turnaround time and the waiting time for each process under each of the above scheduling algorithms. Page 3 of 22

(c) Calculate which scheduling algorithm results in the minimal average waiting time (over all processes). Solution 3.1 (a) The Gantt charts are given below. FCFS P1

P2

0 SJF without pre-emption P2

P4

10

P3

P3

P4

11

P5

13

P5

14

19

P1

0 1 2 4 9 19 Note that processes P2 and P4 both have a CPU burst time of 1 ms, but we pick P2 before P4 since P2 has a smaller process number than P4. Non-pre-emptive Priority P2 P5 P1 P3 P4 0 1 6 16 18 19 Note that once again we have a tie — processes P1 and P3 both have a priority of 3, but we pick P1 before P3, due to its smaller process number. Round-Robin (quantum = 1) P1 0

P2 1

P5 11

P3 2

P1 12

P4 3

P5 13

P5 4

P1 14

P1 5

P1 15

P3 6

P1 16

P5 7

P1 17

P1 8

P5 9

P1 10

11

P1 18

19

(b) We draw 4 tables, where a table shows the turnaround time and waiting time for all the processes under one specific scheduling algorithm only. Remember: Turnaround time = Time completed − Arrival time. ∑ Waiting time = Turnaround time − ∑ CPU burst

Page 4 of 22

The tables are shown below. FCFS Process

Turnaround time

Waiting Time

P1

(10 - 0) = 10

(10 - 10) = 0

P2

(11 - 0) = 11

(11 - 1) = 10

P3

(13 - 0) = 13

(13 - 2) = 11

P4

(14 - 0) = 14

(14 - 1) = 13

P5

(19 - 0) = 19

(19 - 5) = 14

SJF without pre-emption Process

Turnaround time

Waiting Time

P1

(19 - 0) = 19

(19 - 10) = 9

P2

(1 - 0) = 1

(1 - 1) = 0

P3

(4 - 0) = 4

(4 - 2) = 2

P4

(2 - 0) = 2

(2 - 1) = 1

P5

(9 - 0) = 9

(9 - 5) = 4

Non-pre-emptive Priority Process

Turnaround time

Waiting Time

P1

(16 - 0) = 16

(16 - 10) = 6

P2

(1 - 0) = 1

(1 - 1) = 0

P3

(18 - 0) = 18

(18 - 2) = 16

P4

(19 - 0) = 19

(19 - 1) =18

P5

(6 - 0) = 6

(6 - 5) = 1 Page 5 of 22

Round Robin with q = 1 Process

Turnaround time

Waiting Time

P1

(19 - 0) = 19

(19 - 10) = 9

P2

(2 - 0) = 2

(2 - 1) = 1

P3

(7 - 0) = 7

(7 - 2) = 5

P4

(4 - 0) = 4

(4 - 1) = 3

P5

(14 - 0) = 14

(14 - 5) = 9

(c) The average waiting times are calculated below: Scheduling algorithm

Average waiting time

FCFS

(0 + 10 + 11 + 13 + 14) / 5 = 48/5 = 9.6

SJF

(9 + 0 + 2 + 1 + 4) / 5 = 16/5 = 3.2

Priority

(6 + 0 + 16 + 18 + 1) / 5 = 41/5 = 8.2

Round Robin

(9 + 1 + 5 + 3 + 9) / 5 = 27/5 = 5.4

Therefore, the shortest job first scheduling policy yields the minimal average waiting time of 3.2 ms. This is to be expected, since SJF is provably optimal (see SGG page 190). Note also that there is no need to use a calculator to do the final division - you can see the result simply by looking at the values in bold. Exercise 3.2 Use the following process arrival list to draw the Gantt charts and to calculate the turnaround time and waiting time of each job under each of the following scheduling policies Show all your calculations clearly: (a) SJF (without pre-emption) (b) SJF (with pre-emption) (c) RR (quantum = 5)

Page 6 of 22

Process

Arrival time

Length of CPU burst

a

0

3

b

2

6

c

3

10

d

7

1

e

8

5

f

15

2

g

25

7

Solution 3.2 (a) SJF (without pre-emption) A

b

0

d

3

9

e 10

f 15

c 17

g 27

34

The turnaround times and waiting times for SJF without pre-emption are given below: Process

Arrival time

CPU burst

Time of Completion

Turnaround time

Waiting time

a

0

3

3

(3 - 0) = 3

(3 - 3) = 0

b

2

6

9

(9 - 2) = 7

(7 - 6) = 1

c

3

10

27

(27 - 3) = 24

(24 - 10) = 14

d

7

1

10

(10 - 7) = 3

(3 - 1) = 2

e

8

5

15

(15 - 8) = 7

(7 - 5) = 2

f

15

2

17

(17 - 15) = 2

(2 - 2) = 0

g

25

7

34

(34 - 25) = 9

(9 - 7) = 2

(b) SJF (with pre-emption) A 0

b 3

d 7

b 8

e 10

f 15

c 17

g 27

34 Page 7 of 22

Note that process d is ready to run at time 7. Process b has not yet finished running but its remaining length (2 units) is longer that the total length of process d (1 unit). Process b is suspended and process d is selected due to pre-emption. The turnaround times and waiting times for the above SJF with pre-emption are: Process

Arrival time

CPU burst

Time of Completio n

Turnaround time

Waiting time

a

0

3

3

(3 - 0) = 3

(3 - 3) = 0

b

2

6

10

(10 - 2) = 8

(8 - 6) = 2

c

3

10

27

(27 - 3) = 24

(24 - 10) = 14

d

7

1

8

(8 - 7) = 1

(1 - 1) = 0

e

8

5

15

(15 - 8) = 7

(7 - 5) = 2

f

15

2

17

(17 - 15) = 2

(2 - 2) = 0

g

25

7

34

(34 - 25) = 9

(9 - 7) = 2

(c) RR (quantum = 5) A

b

c

d

e

b

0 3 8 13 14 19 20 The RR turnaround times and waiting times are:

c

f 25

g 27

34

Process

Arrival time

CPU burst

Time of Completion

Turnaround time

Waiting time

a

0

3

3

(3 - 0) = 3

(3 - 3) = 0

b

2

6

20

(20 - 2) = 18

(18 - 6) = 12

c

3

10

25

(25 - 3) = 22

(22 - 10) = 12

d

7

1

14

(14 - 7) = 7

(7 - 1) = 6

e

8

5

19

(19 - 8) = 11

(11 - 5) = 6

f

15

2

27

(27 - 15) = 12

(12 - 2) = 10

g

25

7

34

(34 - 25) = 9

(9 - 7) = 2 Page 8 of 22

Exercise 3.3 (An exercise on setting quantum values (q)) Consider the following pre-emptive priority scheduling algorithm based on dynamically changing priorities. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate α; when it is running its priority changes at a rate β. (α and β represent real numbers): Assume that a numerically larger value represents a higher priority. All processes are given a priority of 0 when they enter the ready queue. The parameters α and β can be set to give many different scheduling algorithms. If the number of jobs in the Do While (jobs in ready queue) S tart the job with the numerically highest priority; If (end of quantum or request for I/O) then S uspend the job currently running; Add α to the priority of each waiting job; Add β to the priority of the job that has just been running End_If Accept any new jobs into the ready queue with priority 0 End_Do

ready queue is n, discuss fully the scheduling algorithms that result from each of the following settings of α and β: (a) β < 0 < α (b) α = β/( n + 1) and β =(1 - n) Solution 3.3 (a) β < 0 < α Since β < 0, the priority of the job that has just run is decreased, while the priorities of the waiting jobs are increased since α > 0. Hence we have here an ageing algorithm and depending on the values α and β it may result in some or other form of round robin (RR). (b) α = β/( n + 1) and β =(1 - n) First we calculate some values of α and β for n = 0, 1, 2, 3, ... Case 1: n = 0: Then α = 1 and β = 1. This yields FCFS since there is only one job in the system. Case 2: n = 1: Then α = 0 and β = 0. Once again this is FCFS (or maybe RR since priorities do not change). Page 9 of 22

Now we consider 3 additional cases: Case 3: n = 2: α = - 0.33 and β = -1 Case 4: n = 3: α = - 0.5 and β = -2 Case 5: n = 4: α = - 0.6 and β = -3 From the 3 cases above we see that β becomes negative by a larger value than α and this means that the priorities of the waiting jobs increase relative to the priority of the running job. So in general we have β ≤ α. Hence the running job will be pre-empted at some stage. This again leads to an ageing algorithm which may turn out to be an approximate form of Round-Robin scheduling. But, new jobs enter with priority 0 and if new jobs keep on entering the system, they each get one time slice. This leads to a Last Come First Served (LCFS) algorithm and may result in the starvation of the waiting jobs in the ready queue.

Page 10 of 22

Part II Contents 1) 2) 3) 4)

Introduction ......................................................................................................................................1 Formulae ..........................................................................................................................................1 The Banker’s Algorithm ...................................................................................................................12 Page Replacement ..........................................................................................................................20

1) Introduction

The purpose of this tutorial letter is to:  Present the formulae to calculate the content of the Need and Max matrices and the maximum resource vector.  Give an example of the application of the Banker’s algorithm for determining whether a given system is in a safe state or not.



Give examples of the FIFO, LRU and Optimal page replacement algorithms for a given page reference string.

Next we give mathematical formulae for the calculation of the Need, Max and maximum resource vectors. 2)

Formulae

The formulae are: (a) Need[i, j] := Max[i,j] – Allocation [i, j] (b) Max [i, j] := Need[i, j] + Allocation [i, j] (c) Max_resource_vector :=

in,jm

Allocation [i,j]  Available i,j

Next some information about the Banker’s algorithm.

Page 11 of 22

3)

The Banker’s Algorithm

Most deadlock avoidance algorithms examine the resource allocation state to ensure that a circular-wait condition will not arise. An example of a deadlock avoidance algorithm is the Banker's algorithm. Note that the Banker's algorithm actually consists of two algorithms namely the safety algorithm and the resource-request algorithm. The last part of the allocation algorithm states that 'If the resulting resource-allocation state is safe, ... process P i is allocated its resources'. This means that if a process requests resources, we have to execute the safety algorithm to determine if the resulting resource allocation state is safe. A safe state is one with an underlying safe sequence where all the resources that P i may request are either currently available or held by a process P j, where j < i. If the resources are not immediately available, Pi can wait until all processes P j, j < i, have completed. When P i finishes, Pi+1 may obtain its resources. An unsafe state may, but will not necessarily, lead to a deadlock. A deadlock is, therefore, avoided by refusing any request which could lead to an unsafe state. A process may, therefore, have to wait for a resource that is currently available because its allocation will lead to an unsafe state. This may lead to sub-optimal utilisation of resources. The following example illustrates the use of the Banker's algorithm. Example 3.1 A particular system uses the deadlock avoidance approach. At time t0, the state is:

Process

Allocation

Max

Available

P0

0014

0656

1650

P1

1224

2357

P2

0012

0012

P3

1000

1750

P4

0632

0652

Page 12 of 22

Suppose that requests are made in the following order ( t0 < t1 < t2): Time

Process

Request

t0

P2

110 0

t1

P1

013 0

t2

P3

052 0

Now we use the Banker's safety algorithm to first determine whether the system is currently in a safe state and thereafter whether each of these requests may be safely granted or not. In each case, if the request can be granted, then grant the request and bring the allocation up to date before considering the next request. We show all workings and give a safe sequence for all requests that can be granted.

Solution to Example 3.1 First we calculate the array Need using the formula in (a) above: Process

Allocation

Max

Need

Available

P0

001 4

065 6

064 2

165 0

P1

122 4

235 7

113 3

P2

001 2

001 2

000 0

P3

100 0

175 0

075 0

P4

063 2

065 2

002 0

We also add all the allocated resources to the available ones to obtain the maximum resource vector (note the notation – round brackets and commas between the numbers): maximum resource vector = (3,14,12,12) Because we are testing the current system for a safe state, we apply the Banker’s Safety Algorithm to the current allocation. 1.

Available := (1,6,5,0)

(= Work)

All the processes are still running, and therefore:

Page 13 of 22

Finish = (0,0,0,0,0)

(0 = false, 1 = true)

1. This is the initialisation called for in Step 1 of the Banker's Safety Algorithm. 2. We must now search the array Need from the top to find a process needing fewer resources than those available. Process P2 needs no additional resources, and so our search has been successful....