Problem Set 4

Assigned: Feb. 24
Due: Mar. 3

Problem 1

Suppose that there is 256M of RAM, and that the system uses variable length partitions for memory management. Suppose that jobs enter and terminate according to the following schedule:
A of size 70M enters at time 0.
B of size 30M enters at time 10.
C of size 40M enters at time 20
A terminates at time 30.
D of size 20M enters at time 40.
E of size 100M enters at time 50.
C terminates at time 60.
F of size 30M enters at time 70.
E terminates at time 80.
G of size 20M enters at time 90.
H of size 80M enters at time 100.
H terminates at time 110.
Show how jobs are placed under each of the following memory allocation schemes: First-fit, best-fit, circular first-fit.

First-fit

Time      Memory
0-10      A: 0-70.  Free: 70-256. 
10-20     A: 0-70.  B: 70-100.  Free: 100-256.
20-30     A: 0-70.  B: 70-100.  C: 100-140.  Free: 140-256.
30-40     Free: 0-70.  B: 70-100.  C: 100-140.  Free: 140-256.
40-50     D: 0-20.  Free: 20-70.  B: 70-100.  C: 100-140.  Free: 140-256.
50-60     D: 0-20.  Free: 20-70.  B: 70-100.  C: 100-140.  E: 140-240.  Free: 240-256.
60-70     D: 0-20.  Free: 20-70.  B: 70-100.  Free: 100-140.  E: 140-246.  Free: 240-256.
70-80     D: 0-20.  F: 20-50. Free: 50-70.  B: 70-100.  Free: 100-140.  E: 140-246.  Free: 240-256.
80-90     D: 0-20.  F: 20-50. Free: 50-70.  B: 70-100.  Free: 100-256.
90-100    D: 0-20.  F: 20-50. G: 50-70.  B: 70-100.  Free: 100-256.
100-110   D: 0-20.  F: 20-50. G: 50-70.  B: 70-100.  H: 100-180. Free: 180-256
110       D: 0-20.  F: 20-50. G: 50-70.  B: 70-100.  Free: 100-256.

Best-fit Same as first fit up to time 70.

Time      Memory
70-80     D: 0-20.  Free: 20-70.  B: 70-100.  F: 100-130. Free: 130-140.   E: 140-246.  Free: 240-256.
80-90     D: 0-20.  Free: 20-70.  B: 70-100.  F: 100-130. Free: 130-256.
90-100    D: 0-20.  G: 20-40. Free: 40-70. B: 70-100.  F: 100-130. Free: 130-256.
100-110   D: 0-20.  G: 20-40. Free: 40-70. B: 70-100.  F: 100-130. H: 130-210.  Free: 210-256.
110       D: 0-20.  G: 20-40. Free: 40-70. B: 70-100.  F: 100-130. Free: 130-256.

Circular first fit Same as first-fit up to time 40

Time
40-50     Free: 0-70.  B: 70-100.  C: 100-140.  D: 140-160. Free: 160-256.
At time 50, E enters of size 100. There is no room for it. The problem doesn't specify what was to be done in this case (This was a mistake on my part.) What would actually be done, probably, is that E would have to wait until room opened up, but there's no way to incorporate that into the context of this problem. We'll assume, (pretty much unrealistically) that memory compaction is performed.
Time      Memory
50-60     B: 0-30.  C: 30-70.  D: 70-90.  E: 90-190.  Free: 190-256.
60-70     B: 0-30.  Free: 30-70.  D: 70-90.  E: 90-190.  Free: 190-256.
70-80     B: 0-30.  Free: 30-70.  D: 70-90.  E: 90-190.  F: 190-220. Free: 220-256.
70-80     B: 0-30.  Free: 30-70.  D: 70-90.  E: 90-190.  F: 190-220. Free: 220-256.
80-90     B: 0-30.  Free: 30-70.  D: 70-90.  Free: 90-190.  F: 190-220. Free: 220-256.
90-100    B: 0-30.  Free: 30-70.  D: 70-90.  Free: 90-190.  F: 190-220. G: 220-340  Free: 240-256.
100-110   B: 0-30.  Free: 30-70.  D: 70-90.  H: 90-170.  Free: 170-190.  F: 190-220. G: 220-340  Free: 240-256.
110       B: 0-30.  Free: 30-70.  D: 70-90.  Free: 90-190.  F: 190-220. G: 220-340  Free: 240-256.

Problem 2

In problem 1, suppose that the system is using first-fit and uses a free list to keep track of free memory. Show the state of the free list:

Problem 3

Suppose a paging system has a page size of 1 KByte. The current state of the page table PT is as follows:
PT[0] = 4
PT[1] = -1
PT[2] = 0
PT[3] = 5
PT[4] = 2
...
The value -1 means that the page is not in memory.

For each of the following virtual addresses, state whether the corresponding page is in memory. If it is, then give the corresponding physical address: Virtual addresses 50, 1100, 2200, 3300, 4400. (Keep in mind that 1 KByte = 1024 bytes.)

Answer:
Virtual address 50 = page 0 offset 50 = frame 4 offset 50 = physical address 4146
Virtual address 1100 = page 1 offset 76 = page fault.
Virtual address 2200 = page 2 offset 152 = frame 0 offset 152 = physical address 152
Virtual address 3300 = page 3 offset 228 = frame 5 offset 228 = physical address 5348.
Virtual address 4400 = page 4 offset 304 = frame 2 offset 304 = physical address 2352