Assignments | Class Photo | Course Home | Schedule & Lecture Notes | Submit | Tutoring Hours

## Assignment 08

### Overview

Topic: Operating Systems
Related Reading: Ch. 10 of Dale/Lewis, as well as our leccture notes.
Due: 8pm Tuesday, 15 April 2008

### Internet Requirements

Other than for submission, you do not need an internet connection for completing the assignment.

### Practice Problems

• Exercises 69-71 of Ch. 10 (p. 351)

• All of the CPU scheduling examples given in the text involve the simpler case when all jobs "arrive" into the system at time 0. In this problem, we wish to examine the more general case which is when jobs arrive at differing times. One such example was given in the lecture notes.

Consider the following set of jobs:
Job Arrival Time Service Time
p1 0 120
p2 0 60
p3 50 180
p4 100 50
p5 250 300

1. Draw a Gantt chart (as shown on page 340 of the text) that shows the CPU usage with first-come, first-served CPU scheduling. Then calculate the average turnaround time for the resulting schedule.
2. Draw a Gantt chart that shows the CPU usage with shortest job next CPU scheduling. Then calculate the average turnaround time for the resulting schedule.
3. Draw a Gantt chart that shows the CPU usage with round robin CPU scheduling with a time slice of 30. Then calculate the average turnaround time for the resulting schedule.
• Using the page map table of Exercise 59-61 of Ch. 10 (p. 359) and a frame size of 1024, what is the physical address of the following logic addresses?

1. 85
2. 2359
3. 5000

### Problems to be Submitted (20 points)

1. (10 points)

All of the CPU scheduling examples given in the text involve the simpler case when all jobs "arrive" into the system at time 0. In this problem, we wish to examine the more general case which is when jobs arrive at differing times. One such example was given in the lecture notes.

Consider the following set of jobs:
Job Arrival Time Service Time
p1 0 150
p2 0 200
p3 100 10
p4 120 130
p5 140 50
p6 240 40

For each of the following Scheduling Policies, draw a Gantt chart (see, for example, page 340 of the text) that shows the CPU usage. Then calculate the average turnaround time for the resulting schedule.

1. (3 points)
First-Come, First Served

2. (3 points)
Shortest Job Next (please note that SJN is non-preemptive as described in the text)

3. (4 points)
Round Robin with time slice of 30.

Note: Though you are asked to give Gantt charts, it may be difficult to typeset the diagrams as in the book. You may choose to report the same information in whatever way you choose. For example, the Gannt chart shown on page 341 of the text might be represented more easily as:

```Job     From     To
----------------------
P2        0      75
P5       75     200
P1      200     340
P4      340     620
P3      620     940

Average turnaround time is 435
(because all arrival times were 0)
```
Feel free to also see the solutions given to the practice problems.

2. (3 points)

If, in a dynamic-partition memory management system, the current value of the base register is 58712 in decimal, and the current value of the bounds register is 1587, compute the physical addresses that correspond to the following logical addresses:

1. 377
2. 1422
3. 2535

3. (3 points)

In a paged memory-management system, the frame and page sizes are 2048 and the following page map table applies to the currently executing process,
 Page Frame 0 1 2 3 4 64 22 8 71 55

1. 6439
2. 9423
3. 11000

4. (4 points)

Assume that dynamic partitioning is used for memory management, with 500 blocks of memory, the first 100 of which are used by the operating system. Consider the following sequence of process events, encountered by the system.

```Process P1 arrives, requiring 200 blocks.
Process P2 arrives, requiring 100 blocks.
Process P1 terminates.
Process P3 arrives, requiring 70 blocks.
Process P4 arrives, requiring 60 blocks.
Process P5 arrives, requiring 80 blocks.
Process P6 arrives, requiring 20 blocks.
```
1. If the operating system uses "best fit" policy for memory management, describe the final memory configuration.

2. If the operating system uses "worst fit" policy for memory management, describe the final memory configuration.

Note: There will be an issue of how you wish to typeset your answer. Using the figure on page 349 as an example, we might suggest the following tabular form for describing such a partition set

Partitions
process size
OpSys 100 blocks
Process 1 -?- blocks
Empty 60 blocks
Process 2 -?- blocks
Process 3 -?- blocks
Empty 52 blocks
Empty 100 blocks

Note that we use '-?-' for the size of the partitions for existing process because they are not specified in that example. In your solution, you should identify the size of all partitions.

### Extra Credit (2 points)

1. (2 points)

Though not discussed in the text, the lecture notes describe a CPU scheduling policy known as Shortest Remaining Processing Time (SRPT), that is a preemptive version of the SJN policy.

Demonstrate your understanding of the SRPT policy by giving the Gantt chart and average turnaround time which results on the set of jobs used in Problem A of the submitted problems.

CSCI 140, Spring 2008