Question

Problem 8

1. Given five memory partitions of 100 KB, 200 KB, 600 KB, 450 KB, and 400 KB (in order - shown in figure below), how would the first-fit, best-fit, and worst-fit algorithms place processes of 100 KB, 75 KB, 380 KB, 555 KB and 326 KB (in order)? If one process will not fit you can list their partition as NULL. Which algorithm makes the most efficient use of memory? To make this decision, calculate the total fragmentation (external and internal).

Partition	A	B	C	D	E
Size	100 KB	200 KB	600 KB	450 KB	400 KB

First-fit:

Partition	A	B	C	D	E
Process (list size)

Processes not scheduled in:

Internal Fragmentation:

External Fragmentation:

Best-fit:

Partition	A	B	C	D	E
Process (list size)

Processes not scheduled in:

Internal Fragmentation:

External Fragmentation:

Worst-fit:

Partition	A	B	C	D	E
Process (list size)

            Processes not scheduled in:

Internal Fragmentation:

External Fragmentation:

Answer 1

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:

100 KB => 100 KB partition, leaves a 0 KB partition
75 KB => 200 KB partition, leaves a 125 KB partition
380 KB => 600 KB partition, leaves a 220 KB partition
555 KB would not be able to allocate, no partition large enough!
326 KB => 400 KB partition, leaves a 74 KB partition

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:

100 KB => 100 KB, leaving a 0 KB partition
75 KB => 200 KB, leaving a 125 KB partition
380 KB => 400 KB, leaving a 20 KB partition
555 KB => 600 KB, leaving a 45 KB partition
326 KB => 450 KB partition, leaves a 124 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:

100 KB => 600 KB, leaving a 500 KB partition
75 KB => 450 KB, leaving a 375 KB partition
380 KB => 400 KB, leaving a 20 KB partition
555 KB would not be able to allocate, no partition large enough!
326 KB would not be able to allocate, no partition large enough!

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