Question

Given six memory partitions of 100 MB, 170 MB, 40 MB, 205 MB, 300 MB, and 185 MB (in order), how would the first-fit, best-fit, and worst-fit algorithms place processes of size 200 MB, 15 MB, 185 MB, 75 MB, 175 MB, and 80 MB (in order)? Indicate which—if any—requests cannot be satisfied. Comment on how efficiently each of the algorithms manages memory.

Answer 1

Answer:

We have six memory partitions, let label them:

100MB (F1), 170MB (F2), 40MB (F3), 205MB (F4), 300MB (F5) and 185MB (F6).

We also have six processes, let label them:

200MB (P1), 15MB (P2), 185MB (P3), 75MB (P4), 175MB (P5) and 80MB (P6).

Using First-fit

1. P1 will be allocated to F4. Therefore, F4 will have a remaining space of 5MB from (205 - 200).
2. P2 will be allocated to F1. Therefore, F1 will have a remaining space of 85MB from (100 - 15).
3. P3 will be allocated F5. Therefore, F5 will have a remaining space of 115MB from (300 - 185).
4. P4 will be allocated to the remaining space of F1. Since F1 has a remaining space of 85MB, if P4 is assigned there, the remaining space of F1 will be 10MB from (85 - 75).
5. P5 will be allocated to F6. Therefore, F6 will have a remaining space of 10MB from (185 - 175).
6. P6 will be allocated to F2. Therefore, F2 will have a remaining space of 90MB from (170 - 80).

The remaining free space while using First-fit include: F1 having 10MB, F2 having 90MB, F3 having 40MB as it was not use at all, F4 having 5MB, F5 having 115MB and F6 having 10MB.

Using Best-fit

1. P1 will be allocated to F4. Therefore, F4 will have a remaining space of 5MB from (205 - 200).
2. P2 will be allocated to F3. Therefore, F3 will have a remaining space of 25MB from (40 - 15).
3. P3 will be allocated to F6. Therefore, F6 will have no remaining space as it is entirely occupied by P3.
4. P4 will be allocated to F1. Therefore, F1 will have a remaining space of of 25MB from (100 - 75).
5. P5 will be allocated to F5. Therefore, F5 will have a remaining space of 125MB from (300 - 175).
6. P6 will be allocated to the part of the remaining space of F5. Therefore, F5 will have a remaining space of 45MB from (125 - 80).

The remaining free space while using Best-fit include: F1 having 25MB, F2 having 170MB as it was not use at all, F3 having 25MB, F4 having 5MB, F5 having 45MB and F6 having no space remaining.

Using Worst-fit

1. P1 will be allocated to F5. Therefore, F5 will have a remaining space of 100MB from (300 - 200).
2. P2 will be allocated to F4. Therefore, F4 will have a remaining space of 190MB from (205 - 15).
3. P3 will be allocated to part of F4 remaining space. Therefore, F4 will have a remaining space of 5MB from (190 - 185).
4. P4 will be allocated to F6. Therefore, the remaining space of F6 will be 110MB from (185 - 75).
5. P5 will not be allocated to any of the available space because none can contain it.
6. P6 will be allocated to F2. Therefore, F2 will have a remaining space of 90MB from (170 - 80).

The remaining free space while using Worst-fit include: F1 having 100MB, F2 having 90MB, F3 having 40MB, F4 having 5MB, F5 having 100MB and F6 having 110MB.

Explanation:

First-fit allocate process to the very first available memory that can contain the process.

Best-fit allocate process to the memory that exactly contain the process while trying to minimize creation of smaller partition that might lead to wastage.

Worst-fit allocate process to the largest available memory.

From the answer given; best-fit perform well as all process are allocated to memory and it reduces wastage in the form of smaller partition. Worst-fit is indeed the worst as some process could not be assigned to any memory partition.