CS 3120 Operating Systems, Summer 2003

Assignment 2, due:  Monday, June 2, 1:35 pm.

 

This assignment is to be typed with the exception of any diagrams, which can be neatly drawn.

 

  1. [10 points] For the following set of processes, draw a Gant diagram representing the allocation of the CPU and calculate the average response time and average wait time using FCFS, SJF, SRT, and Round Robin (q = 3, q=7).  Show all calculations.

 

Process

Arrival Time

Total Burst Time

P1

0

12

P2

1

1

P3

2

5

P4

4

2

P5

5

7

P6

6

3

 

 

Answer:

 

FCFS:

 

0-1

1-2

2-3

3-4

4-5

5-6

6-7

7-8

8-9

9-10

P1

10-11

11-12

12-13

13-14

14-15

15-16

16-17

17-18

18-19

19-20

P1

P2

P3

P4

20-21

21-22

22-23

23-24

24-25

25-26

26-27

27-28

28-29

29-30

P5

P6

 

 

Process

Arrival

Finish

Response

(finish-arrival)

Burst time

Wait Time

(response-CPU time)

P1

0

12

12 - 0 = 12

12

12 - 12 = 0

P2

1

13

13 - 1 = 12

1

12 - 1 = 11

P3

2

18

18 - 2 = 16

5

16 - 5 = 11

P4

4

20

20 - 4 = 16

2

16 - 2 = 14

P5

5

27

27 - 5 = 22

7

22 - 7 = 15

P6

6

30

30 - 6 = 24

3

24 - 3 = 21

Average:

 

(12 + 12 + 16 + 16 + 22 +24)/6 =102/6 = 17

 

(0 + 11 + 11 + 14 + 15 +21)/6 = 72/6 = 12

 

 

SJF:

 

0-1

1-2

2-3

3-4

4-5

5-6

6-7

7-8

8-9

9-10

P1

10-11

11-12

12-13

13-14

14-15

15-16

16-17

17-18

18-19

19-20

P1

P2

P4

P6

P3

20-21

21-22

22-23

23-24

24-25

25-26

26-27

27-28

28-29

29-30

P3

P5

 

Process

Arrival

Finish

Response

(finish-arrival)

Burst time

Wait Time

(response-CPU time)

P1

0

12

12 - 0 = 12

12

12 - 12 = 0

P2

1

13

13 - 1 = 12

1

12 - 1 = 11

P3

2

23

23 - 2 = 21

5

21 - 5 = 16

P4

4

15

15 - 4 = 9

2

9 - 2 = 7

P5

5

30

30 - 5 = 25

7

25 - 7 = 18

P6

6

18

18 - 6 = 12

3

12 - 3 = 9

Average:

 

(12 + 12 + 21 + 9 + 25 + 12)/6 =  91/6 = 15.17

 

(0 + 11 + 16 + 7 + 18 + 9)/6 = 10.17

 

SRT:

 

0-1

1-2

2-3

3-4

4-5

5-6

6-7

7-8

8-9

9-10

P1

P2

P3

P4

P3

P6

10-11

11-12

12-13

13-14

14-15

15-16

16-17

17-18

18-19

19-20

P6

P5

P1

20-21

21-22

22-23

23-24

24-25

25-26

26-27

27-28

28-29

29-30

P1

 

 

Process

Arrival

Finish

Response

(finish-arrival)

Burst time

Wait Time

(response-CPU time)

P1

0

30

30 - 0 = 30

12 (1+11)

30 - 12 = 18

P2

1

2

2 - 1 = 1

1

1 - 1 = 0

P3

2

9

9 - 2 = 7

5 (2+3)

7 - 5 = 2

P4

4

6

6 - 4 = 2

2

2 - 2 = 0

P5

5

19

19 - 5 = 14

7

14 - 7 = 7

P6

6

12

12 - 6 = 6

3

6 - 3 = 3

Average:

 

(30 + 1 + 7 + 2 + 14 + 6)/6 = 60/6 = 10

 

(18 + 0 + 2 + 0 + 7 + 3)/6 = 30/3 = 5

 

Round Robin (q=3):

0-1

1-2

2-3

3-4

4-5

5-6

6-7

7-8

8-9

9-10

P1

P2

P3

P1

10-11

11-12

12-13

13-14

14-15

15-16

16-17

17-18

18-19

19-20

P4

P5

P6

P3

20-21

21-22

22-23

23-24

24-25

25-26

26-27

27-28

28-29

29-30

P1

P5

P1

P5

 

 

 

Process

Arrival

Finish

Response

(finish-arrival)

Burst time

Wait Time

(response-CPU time)

P1

0

29

29 - 0 = 29

12

29 - 12 = 17

P2

1

4

4 - 1 = 3

1

3 - 1 = 2

P3

2

20

20 - 2 = 18

5

18 - 5 = 13

P4

4

12

12 - 4 = 8

2

8 - 2 = 6

P5

5

30

30 - 5 = 25

7

25 - 7 = 18

P6

6

18

18 - 6 = 12

3

12 - 3 = 9

Average:

 

(29 + 3 + 18 + 8 + 25 + 12)/6 = 95/6 = 15.83

 

(17 + 2 + 13 + 6 + 18 + 9)/6 = 65/6= 10.83

 

 

Round Robin (q=7):

 

0-1

1-2

2-3

3-4

4-5

5-6

6-7

7-8

8-9

9-10

P1

P2

P3

10-11

11-12

12-13

13-14

14-15

15-16

16-17

17-18

18-19

19-20

P3

P4

P5

20-21

21-22

22-23

23-24

24-25

25-26

26-27

27-28

28-29

29-30

P5

P6

P1

 

 

Process

Arrival

Finish

Response

(finish-arrival)

Burst time

Wait Time

(response-CPU time)

P1

0

30

30 - 0 = 30

12

30 - 12 = 18

P2

1

8

8 - 1 = 7

1

7 - 1 = 6

P3

2

13

13 - 2 = 11

5

11 - 5 = 6

P4

4

15

15 - 4 = 11

2

11 - 2 = 9

P5

5

22

22 - 5 = 17

7

17 - 7 = 10

P6

6

25

25 - 6 = 19

3

29 - 3 = 16

Average:

 

(30 + 7 + 11 + 11 + 17 + 19)/6 = 95/6 = 15.83

 

(18 + 6 + 6 + 9 + 10 + 16)/6 = 65/6 = 10.83

 

 

 

  1. [3 points] Given a full context switch time of 1 quantum, an average IO bound process burst time of 7, an average CPU bound process burst time of 100, and a mix of 70% IO bound processes and 30% CPU bound processes, what quantum length would you select for Round Robin scheduling if:
    1. You were trying to maximize CPU utilization
    2. Minimimize waiting times
    3. Minimize response time. 

 

Discuss your reasoning behind each answer.

 

a.       We want to keep the CPU full of processes doing their work.  Time spent on context switching is "time wasted" in terms of the CPU doing process work. To maximize CPU utilization we therefore would need to minimize the time spent doing context switches.  With the round robin algorithm, processes have access to the CPU until their time quantum expires or they complete their burst.  So to minimize context switches we would want to have most processes complete their burst time without interruption (essentially FCFS).  As our average CPU bound process has a burst time of 100, we'd want to set the quantum length for round robin scheduled to be greater than 100.  If we knew what the standard deviation was in our average burst length, we might be able to use that information to come up with a more accurate quantum length that would allow most processes to finish up without interruption. 

 

b.      We've defined waiting times as the response time minus time spent in the CPU doing work. As the burst time of a process is not within our control and is constant for each process, we can simplify our goal to minimize response times (as question C asks).  In the case of interactive processes (IO bound) response time is the elapsed time between when a process arrives in the ready queue and when it blocks to do its IO (the IO will output the response to the user).  As such, it can be calculated the same as turnaround for batch processes - time finished minus time arrived.

 

To reduce the response time, we need to make sure that those 70% of processes that are IO bound aren't held up behind the 30% that are CPU bound.  So we want to have a fairly small time quantum.  However, we also have to worry about the time it takes to do a context switch.  The text says "in general, the average turnaround time can be improved if most processes finish their next CPU burst in a single time quantum... If context-switch time is added in, the average turnaround time increases for a smaller time quantum, since more context switches will be required" (p. 165) At the extreme of a RR (q=1), we'd be having 1 quantum of overhead for each quantum of CPU time spent doing process work. 

 

We've got 70% of our processes averaging 7 quanta and 30% averaging 100 quanta.  So we would definitely want the time quantum to be larger than 7 to allow the IO bound processes to finish without interruption. If we knew the variance of burst times, we might want to raise that number accordingly.  Expected CPU burst time is about 35 (0.7 x 7 + 0.3 x 100), so using that as a justification would work.  The book gives a general guideline of a quantum length that would allow 80% of processes to complete without interruption.  Without having more detail about the variance in IO and CPU bound processes, it's hard to get more precise. If you made some assumptions, you could further the argument.

 

 

c.       Due to the relationship between waiting times and response times, the answer to this part is the same as the answer in b.  Your solution should indicate why these 2 parts are essentially the same.

 

 

 

  1. [1 point] When a process forks a child, the parent and child processes gain access to the CPU in an undetermined order.  This can lead to a race condition.  Was this a problem with Assignment 1?  Why or why not?

 

Answer:

            No.  The only data the child needed from the parent was passed to the child in the argument vector as part of the execvp call. The child process will have a copy of this data. The parent then waited for the child to finish before continuing with its work (which should include not freeing the memory for the argument vector until after the child has terminated). In future assignments, when we deal with inter-process communication and shared data, race conditions will become pertinent.  In the limited scope of this assignment, it shouldn't have been a problem.

 

  1. [6 points] Examine Peterson's algorithm with the following modifications.  Determine if the algorithm is still correct or not.  If it's correct, prove it correct for mutual exclusion, bounded waiting, and progress.  If it's incorrect, demonstrate with a specific interleaving, what goes wrong:
    1. turn = j is changed to turn = i (I want in, you have to wait for me) for both processes

 

Answer:  incorrect.  No mutual exclusion if executed in the following order. (Assuming flag[1]=flag[0]= false, and turn = 0 for intitialization.)

1.      P0 signals sets flag[0] to true 

2.      P0 sets turn to 0.

3.      P0 tests entry to the critical section (flag[1]==false)

4.      P0 accesses the CS.  It then gets interrupted. 

5.      P1 sets flag[1] to true

6.      P1 sets turn to 1. 

7.      P1 test entry to the critical section (flag[0]==true & turn==0 (false!)),

8.      P1 can access CS.

 

Process P0:                                                           Process P1;
repeat                                                                   repeat
     1. flag[0] := true;                                                       5. flag[1] := true;
            // I wants in                                                            // I wants in                                          
      2. turn := 0;                                                                6. turn := 1;
            // You have to wait for me                                     // You have to wait for me
      3. while (flag[1] & turn == 1);                                  7. while(flag[0] & turn == 0);
                4. CS                                                                        8.  CS
      flag[0] := false;                                                       flag[1] := false;
            // 0 is done                                                                // 1 is done        
                 RS                                                                          RS
forever                                                                   forever

 

 

    1. the lines flag[i]= true and turn = j are reversed in both processes (it's your turn, I want in)

 

Answer:  incorrect  - no mutual exclusion If executed in the following order:

1.      P1 sets turn to 0

2.      P0 sets turn to 1

3.      P0 sets flag[0] to true

4.      P0 starts to test entry flag[1]== false

5.      P0 gains access to CS

6.      P1 sets flag[1] to true

7.      P1 tests entry flag[0] (true) && turn ==0 (false)

8.      P1 gains access to CS

 

Process P0:                                                           Process P1;
repeat                                                                   repeat
    2. turn := 1;                                                               1. turn := 0;
            // it’s your turn                                                        // it’s your turn                                          
     3.flag[0] := true;                                                       6. flag[1] := true;  
            // but I want in                                                           // but I want in
      4.while (flag[1] && turn == 1);                                7. while(flag[0] && turn == 0);
         5.       CS                                                                     8.     CS
      flag[0] := false;                                                       flag[1] := false;
            // 0 is done                                                                // 1 is done         
                 RS                                                                          RS
forever                                                                   forever

 

 

 

    1. flag[i]= true and turn = j are reversed in Pi (it's your turn, I want in), but the other process, Pj, is left with the order flag[j]=true and turn = i (I want in, it's your turn)

 

Answer:  incorrect.  No mutual exclusion if interleaved as follows:

1.      P1 sets flag[1] to true

2.      P0 sets turn to 1

3.      P1 sets turn to 0

4.      P1 tests entry (flag[0]==false)

5.      P1 gains entry

6.      P0 sets flag[0] to true

7.      P0 tests entry (flag[1]== true, turn ==1 (false!))

8.      P0 gains entry to CS

 

 

Process P0:                                                           Process P1;
repeat                                                                   repeat
     2. turn := 1;                                                              1. flag[1] := true;
            // it’s your turn                                                       // I want in                                           
      6. flag[0] := true;                                                       3. turn := 0;
            // I want in                                                             // it’s your turn
      7. while (flag[1] && turn == 1);                                4. while(flag[0] && turn == 0);
           8.     CS                                                                       5.   CS
      flag[0] := false;                                                       flag[1] := false;
            // 0 is done                                                                // 1 is done        
                 RS                                                                          RS
forever                                                                   forever