Problem Set 1

Assigned: Jan. 22
Due: Jan. 29

Submitting homework:

Homework is due at class time. You may either submit it in hard copy in class or by email to the course grader, Jack Fan: s.jack.fan@earthlink.net

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. To make it clearer how this works and what kind of answer you're supposed to give, there is one example worked out here; the assignment is to work through a similar example in the same way.

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.

Example, with solution

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

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

The processes enter the system according to the following schedule:
A enters at time 0.
B enters at time 40.
C enters at time 50.
D enters at time 250.
E enters at time 310.

Solution to Example

Time RAM Active process Ready queue Event at end
0 OS: 0-10. empty A enters.
0-10 OS: 0-10; A: 10-30. A empty A blocks until 70.
10-40 OS: 0-10; A: 10-30. Idle empty B enters
40-50 OS: 0-10; A: 10-30; B: 30-70; B empty C enters.
50-70 OS: 0-10; A: 10-30; B: 30-70; C: 70-90. B C A unblocks
70-90 OS: 0-10; A: 10-30; B: 30-70; C: 70-90. B C,A B preempted for C.
90-140 OS: 0-10; A: 10-30; B: 30-70; C: 70-90. C A,B C preempted for A.
140-190 OS: 0-10; A: 10-30; B: 30-70; C: 70-90. A B,C A preempted for B.
190-210 OS: 0-10; A: 10-30; B: 30-70; C: 70-90. B C,A B blocks until 260
210-220 OS: 0-10; A: 10-30; B: 30-70; C: 70-90. C A C blocks until 280
220-230 OS: 0-10; A: 10-30; B: 30-70; C: 70-90. A empty A terminates
230-250 OS: 0-10; Free: 10-30; B: 30-70; C: 70-90. Idle empty D enters
250-260 OS: 0-10; D: 10-20; Free: 20-30; B: 30-70; C: 70-90. D empty B unblocks
260-270 OS: 0-10; D: 10-20; Free: 20-30; B: 30-70; C: 70-90. D B D blocks until 320
270-280 OS: 0-10; D: 10-20; Free: 20-30; B: 30-70; C: 70-90. B empty C unblocks
280-290 OS: 0-10; D: 10-20; Free: 20-30; B: 30-70; C: 70-90. B C B terminates
290-310 OS: 0-10; D: 10-20; Free: 20-70; C: 70-90. C empty E enters
310-320 OS: 0-10; D: 10-20; E: 20-40; Free: 40-70; C: 70-90. C E D unblocks
320-330 OS: 0-10; D: 10-20; E: 20-40; Free: 40-70; C: 70-90. C E,D C terminates
330-380 OS: 0-10; D: 10-20; E: 20-40. E D E is preempted for D
380-390 OS: 0-10; D: 10-20; E: 20-40. D E D terminates.
390-420 OS: 0-10; Free: 10-20; E: 20-40. E empty E terminates.

Assignment

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.

Note:

We assume that the clock time for a block is independent of anything else that is happening. In reality, as we shall see later in the course, this assumption can be correct or it can be wildly inaccurate, depending on the type of events involved in the blocks.

If two events happen simultaneously --e.g. one process unblocks at the same time that another enters -- you can deal with them in either order.

In working through this kind of long listing, it's easy to make trivial mistakes or typos. Don't worry about these. The point is to get the general idea right.