Homework #5 solution

Homework #5 Solution

Assignment: Problems 9.2, 9.5, 9.8, 9.16, 10.2, and 10.11

Problem 9.2

Explain the difference between internal and external fragmentation.

Internal fragmentation is the difference between the (fixed) size of a memory hole and the data within in that memory. For example, if a 1,024 byte block of memory holds 800 bytes of data, then the 224 bytes difference is considered lost to internal fragmentation.

External fragmentation occurs when the sum of memory fragments is large enough to satisfy a request, but the holes are non-contiguous and the request cannot be satisfied. This can occur when memory is dynamically allocated and freed.

Problem 9.5

Given memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each algorithm place processes of size 212 KB, 417 KB, 112 KB, and 426 KB (in order)?

a) First-fit

The first-fit algorithm selects the first free partition that is large enough to accommodate the request.

First-fit would allocate in the following manner:

212 KB => 500 KB partition, leaves a 288 KB partition
417 KB => KB partition, leaves a 183 KB partition
112 KB => 288 KB partition, leaves a 176 KB partition
426 KB would not be able to allocate, no partition large enough!

b) Best-fit

The best-fit algorithm selects the partition whose size is closest in size (and large enough) to the requested size.

Best-fit would allocate in the following manner:

212 KB => 300 KB, leaving a 88 KB partition
417 KB => 500 KB, leaving a 83 KB partition
112 KB => 200 KB, leaving a 88 KB partition
426 KB => 600 KB, leaving a 174 KB partition

c) Worst-fit

The worst-fit algorithm effectively selects the largest partition for each request.

Worst-fit would allocate in the following manner:

212 KB => 600 KB, leaving a 388 KB partition
417 KB => 500 KB, leaving a 83 KB partition
112 KB => 388 KB, leaving a 276 KB partition
426 KB would not be allowed to allocate as no partition is large enough!

d) Which algorithm makes the most efficient use of memory?

The best-fit algorithm performed the best of the three algorithms, as it was the only algorithm to meet all the memory requests.

Problem 9.8

Consider a logical-address space of eight pages of 1,024 words each, mapped onto a physical memory of 32 frames.

a) How many bits are in the logical address?

The logical address is split into two parts: the page address and then the offset.

The page address must be able to reference 8 (or 2³) distinct pages. This requires 3 address bits.

The offset must be able to reference 1,024 (or 2¹⁰) distinct words on each page. This requires 10 address bits.

Therefore, 13 bits are required for the logical address.

b) How many bits are in the physical address?

The physical address is also split into two parts: the frame address and then the offset.

The number of frames is 32 (or 2⁵), so that will require 5 bits.

The size of the frame is the same as the size of the page, therefore this will require 10 bits, as described above.

Therefore, 15 bits are required for the physical address.

Problem 9.16

Considering the segment table on page 315, what are the physical addresses for the following logical addresses?

a) 0430

The first bit of the address is the segment, in this case, segment 0. Segment 0 is based at physical location 219.

The remainder of the address is the offset, or 430.

The physical address is 219 + 430 = 649.

b) 110

The segment is 1. Segment 1's base is at physical location 2300. The offset is 10.

The physical address is 2300 + 10 = 2310.

c) 2500

The segment is 2, based at physical location 90. The offset is 500.

The physical address is 90 + 500 = 590.

Please note that this address is illegal because the limit on segment 2 is only 100, less than the offset of 500.

d) 3400

The segment is 3, based at 1327. The offset is 400.

The physical address is 1327 + 400 = 1727.

e) 4112

The segment is 4, based at 1952. The offset is 112.

The physical address is 1952 + 112 = 2064.

This address is also illegal because segment 4's limit is only 96, smaller than the 112 offset.

Problem 10.2

Assume a reference string for a process with m frames, initially empty. The page reference string has length p, and n distinct page numbers occur in it.

a) What is the lower bound on the number of page faults?

The lower bound is n.

If n distinct pages are referenced, then each page must cause a page fault when it is initially loaded into memory.

b) What is the upper bound on the number of page faults?

The upper bound is p.

If m (the number of frames) is 1, for example, then each page reference could cause a page fault. This is the upper bound.

Problem 10.11

Consider the reference string:

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6

Simulate the operation of each page replacement algorithm assuming 5 frames.

a) LRU replacement

Here's the simulation using LRU... the page table is listed at each page reference list each (page #, frame #) pair. Also, an "*" at the end of the line indicates that a page fault occurs at this step.

Ref 1: (1,0) *

Ref 2: (1,0) (2,1) *

Ref 3: (1,0) (2,1) (3,2) *

Ref 4: (1,0) (2,1) (3,2) (4,3) *

Ref 2: (1,0) (2,1) (3,2) (4,3)

Ref 1: (1,0) (2,1) (3,2) (4,3)

Ref 5: (1,0) (2,1) (3,2) (4,3) (5,4) *

Ref 6: (1,0) (2,1) (4,3) (5,4) (6,0) *

Ref 2: (1,0) (2,1) (4,3) (5,4) (6,0)

Ref 1: (1,0) (2,1) (4,3) (5,4) (6,0)

Ref 2: (1,0) (2,1) (4,3) (5,4) (6,0)

Ref 3: (1,0) (2,1) (3,3) (5,4) (6,0) *

Ref 7: (1,0) (2,1) (3,3) (6,0) (7,4) *

Ref 6: (1,0) (2,1) (3,3) (6,0) (7,4)

Ref 3: (1,0) (2,1) (3,3) (6,0) (7,4)

Ref 2: (1,0) (2,1) (3,3) (6,0) (7,4)

Ref 1: (1,0) (2,1) (3,3) (6,0) (7,4)

Ref 2: (1,0) (2,1) (3,3) (6,0) (7,4)

Ref 3: (1,0) (2,1) (3,3) (6,0) (7,4)

Ref 6: (1,0) (2,1) (3,3) (6,0) (7,4)

The total number of page faults using LRU is 8.

b) FIFO replacement

Here's the simulation using FIFO... same format as above:

Ref 1: (1,0) *

Ref 2: (1,0) (2,1) *

Ref 3: (1,0) (2,1) (3,2) *

Ref 4: (1,0) (2,1) (3,2) (4,3) *

Ref 2: (1,0) (2,1) (3,2) (4,3)

Ref 1: (1,0) (2,1) (3,2) (4,3)

Ref 5: (1,0) (2,1) (3,2) (4,3) (5,4) *

Ref 6: (2,1) (3,2) (4,3) (5,4) (6,0) *

Ref 2: (2,1) (3,2) (4,3) (5,4) (6,0)

Ref 1: (1,1) (3,2) (4,3) (5,4) (6,0) *

Ref 2: (1,1) (2,2) (4,3) (5,4) (6,0) *

Ref 3: (1,1) (2,2) (3,3) (5,4) (6,0) *

Ref 7: (1,1) (2,2) (3,3) (6,0) (7,4) *

Ref 6: (1,1) (2,2) (3,3) (6,0) (7,4)

Ref 3: (1,1) (2,2) (3,3) (6,0) (7,4)

Ref 2: (1,1) (2,2) (3,3) (6,0) (7,4)

Ref 1: (1,1) (2,2) (3,3) (6,0) (7,4)

Ref 2: (1,1) (2,2) (3,3) (6,0) (7,4)

Ref 3: (1,1) (2,2) (3,3) (6,0) (7,4)

Ref 6: (1,1) (2,2) (3,3) (6,0) (7,4)

The total number of page faults using FIFO is 10.

c) Optimal replacement

Here's the simulation using the optimal replacement algorithm... same format:

Ref 1: (1,0) *

Ref 2: (1,0) (2,1) *

Ref 3: (1,0) (2,1) (3,2) *

Ref 4: (1,0) (2,1) (3,2) (4,3) *

Ref 2: (1,0) (2,1) (3,2) (4,3)

Ref 1: (1,0) (2,1) (3,2) (4,3)

Ref 5: (1,0) (2,1) (3,2) (4,3) (5,4) *

Ref 6: (1,0) (2,1) (3,2) (5,4) (6,3) *

Ref 2: (1,0) (2,1) (3,2) (5,4) (6,3)

Ref 1: (1,0) (2,1) (3,2) (5,4) (6,3)

Ref 2: (1,0) (2,1) (3,2) (5,4) (6,3)

Ref 3: (1,0) (2,1) (3,2) (5,4) (6,3)

Ref 7: (1,0) (2,1) (3,2) (6,3) (7,4) *

Ref 6: (1,0) (2,1) (3,2) (6,3) (7,4)

Ref 3: (1,0) (2,1) (3,2) (6,3) (7,4)

Ref 2: (1,0) (2,1) (3,2) (6,3) (7,4)

Ref 1: (1,0) (2,1) (3,2) (6,3) (7,4)

Ref 2: (1,0) (2,1) (3,2) (6,3) (7,4)

Ref 3: (1,0) (2,1) (3,2) (6,3) (7,4)

Ref 6: (1,0) (2,1) (3,2) (6,3) (7,4)

The total number of page faults

using optimal replacement is 7.