Solution Set 1

This assignment asks you to trace through the execution of the sample OS described in lecture 2, with variable-length partitions, first-fit memory allocation, and a round-robin scheduler.

Assume that the computer has 128M of RAM and that it runs a round-robin scheduler with a 50 msec quantum. You may assume that the time required by the operating system itself, in dealing with interrupts or in carrying out context switches, is negligible.

Suppose that there are five processes, with the following characteristics:

The OS requires 10 MBytes and is always resident, starting at address 0.

Trace the system in the same way with the same processes entering the system under the following schedule:
D enters at time 0.
A enters at time 10.
B enters at time 50.
C enters at time 120.
E enters at time 250.

Solution

Time RAM Active process Ready queue Event at end
0. OS: 0-10. empty D enters.
0-10. OS: 0-10; D: 10-20. D empty A enters
10-20. OS: 0-10; D: 10-20. A: 20-40. D A D blocks until 70.
20-30. OS: 0-10; D: 10-20. A: 20-40. A empty A block until 90.
30-50. OS: 0-10; D: 10-20. A: 20-40. Idle empty B enters.
50-70. OS: 0-10; D: 10-20. A: 20-40. B: 40-80. B empty D unblocks.
70-90. OS: 0-10. D: 10-20. A: 20-40. B: 40-80. B D A unblocks.
90-100. OS: 0-10. D: 10-20. A: 20-40. B: 40-80. B D,A B preempted for D.
100-110. OS: 0-10. D: 10-20. A: 20-40. B: 40-80. D A,B D terminates.
110-120. OS: 0-10. Free: 10-20. A: 20-40. B: 40-80. A B C enters
120-160. OS: 0-10. Free: 10-20. A: 20-40. B: 40-80. C: 80-100. A B,C A preempted for B.
160-180. OS: 0-10. Free: 10-20. A: 20-40. B: 40-80. C: 80-100. B C,A B blocks until 230.
180-230. OS: 0-10. Free: 10-20. A: 20-40. B: 40-80. C: 80-100. C A C preempted for A; B unblocks
230-240. OS: 0-10. Free: 10-20. A: 20-40. B: 40-80. C: 80-100. A B,C A terminates.
240-250. OS: 0-10. Free: 10-40. B: 40-80. C: 80-100. B C E enters.
250-260. OS: 0-10. E: 10-30. Free: 30-40. B: 40-80. C: 80-100. B C,E B terminates.
260-270. OS: 0-10. E: 10-30. Free: 30-80. C: 80-100. C E C blocks until 330.
270-320. OS: 0-10. E: 10-30. Free: 30-80. C: 80-100. E empty New quantum for E.
320-330. OS: 0-10. E: 10-30. Free: 30-80. C: 80-100. E empty C unblocks
330-350. OS: 0-10. E: 10-30. Free: 30-80. C: 80-100. E C E terminates.
350-390. OS: 0-10. Free: 10-80. C: 80-100. C empty C terminates.
Note: Since there are two simultaneous events at time 230, you could have decided that C would go onto the ready queue before B, so that the ready queue would be C,B. That would give a different solution for the remainder of the problem.