Best-fit, First-fit, and Worst-fit

The following jobs will be loaded into memory using fixed partition following a certain memory allocation method: a. best-fit, b. first-fit, c. worst-fit.

a. Job1 (100k)             f. Job6 (6k)

turnaround: 3              turnaround: 1

b. Job2 (10k)               g. Job7 (25k)

turnaround: 1              turnaround: 1

c. Job3 (35k)               h. Job8 (55k)

turnaround: 2              turnaround: 2

d. Job4 (15k)               i. Job9 (88k)

turnaround: 1              turnaround: 3

e. Job5 (23k)               j. Job10 (100k)

turnaround: 2              turnaround: 3

 Above is the given memory blocks and sizes.

 Legend: IF = Internal Fragmentation

a.)    Best-fit

• Makes the best use of memory space; results in least wasted space; internal fragmentation reduced, but not eliminated; its goal is to find the smallest memory block into which the job will fit.

• We say that best-fit is which the jobs fit to the smallest internal fragmentation of the block. Job 1 was best-fitted in memory block 4 that has a size of 115k where it is the smallest fragmentation of 15k among the other blocks. Job 2 best-fitted in memory block 5 with only 5k internal fragmentation. Since block 4 and block 5 is busy, Job 3 only find its best-fit with block 1, block 2 and block 3. Job 3 fitted in block 1 which it has 15k of internal fragmentation. Same as the other jobs Job 4 was fitted on block 3 which it had 55k internal fragmentation and Job 5 in block 2 which it had 177k internal fragmentation. On the second round, Job 2 and Job 4 ends where Job 6 searched which will it be fitted then replaced Job 2 which it had 9k internal fragmentation and Job 7 replacing Job 4 with 45k internal fragmentation. In the third round, four jobs end Job 3, Job 5, Job 6 and Job 7, and Job 8 and Job 9 arrives. When Job 8 searching where it is fitted, block 1 and block 5 cannot accommodate Job 8 because of its lack of memory for Job 8 and also it cannot accommodate block 4 because it is busy since Job 1 has three turnaround. Job 8 accommodated block 3 not blocks 2 because block 3 is lesser internal fragmentation than block 2. Job 9 has no choice to be fitted on block 2 because other blocks is busy and cannot accommodate Job 9. In the fourth round, the round of Job 1 end while Job 8 which have two turnaround and Job 9 which have three turnaround remain and Job 10 arrives. Job 10 only fitted on block 4 which it replacing the Job 1 which it had only 15k internal fragmentation.

b.)    First-fit

• Leads to fast allocation of memory space; first partition fitting the requirements; faster in making allocation.

• First-fit is first come first serve that it will arrive in block where it first be fitted no matter its internal fragmentation. Job 1 was first-fit in block 2 with a size of memory of 200k. Then, Job 2 with 10k was first-fit to block 1 with 50k. Since block 1 and block 2 is busy Job 3 proceed to block 3 which it’s first-fitted as well as Job 4 to block 4. Job 5 has no available memory block in the first round so Job 5 was in the waiting queue then Job 6 can accommodate block 5, Job 6 entered. In the second round, Job 2, Job 4 and Job 6 ends while Job 1 which has three turnaround and Job 3 which has two turnaround remain and Job 5 and Job 7 arrives. Job 5 with 23k first-fit to block 1 where it replaces Job 2. Job 7 was also first-fitted to block 4 with size of 115k. In the third round, Job 3 and Job 7 ends and Job 8 which have 55k and Job 9 which have 88k arrives. Since block 1 and block 2 is busy, Job 8 proceeds to block 3 which it fitted. As well as Job 8, Job 9 proceeds to block 4 where it fitted. In the fourth round, Job 1 and Job 5 end and Job 10 arrives. Job 10 was first-fitted to block 2 replacing Job 1’s places in the last round.

c.)    Worst-fit

• Allocates largest free available block to new job; opposite of best-fit; good way to explore theory of memory allocation but not best choice for an actual system.

• We say that worst-fit is opposite to best-fit where jobs fitted on biggest internal fragmentation among the blocks. In the first round, when Job 1 was searching the whole blocks, it got the biggest internal fragmentation in block 2 of 100k. As well as Job 1, Job 2 searches the biggest internal fragmentation in block 4 of 105k. Since block 2 and block 4 is busy Job 3 only searched in block 1, block 3, and block 5 where Job 3 entered in block which have 35k internal fragmentation. Job 4 gets the biggest internal fragmentation in block 1 of 35k. Since Job 5 cannot accommodate block 5, Job 5 is in the waiting queue so Job 6 entered block 5 since block 5 accommodate Job 6 with 9k internal fragmentation. In the second round, Job 2, Job 4 and Job 6 ends and Job 1 with three turnaround and Job 3 with two turnaround remain and Job 5 in the waiting queue can now entered block 4 because block 4 can accommodate Job 5. Job 7 arrives and replaces Job 4 which has 25k internal fragmentation. In the third round, Job 3 and Job 7 ends and Job 8 arrives. Job 8 (since block 2 and block 4 is busy) searched the blocks 1, 3 and 5 where the biggest internal fragmentation is on block 3 with 15k. In the fourth round, Job 1 and Job 5 finished their turnarounds, Job 9 and Job 10 arrives. Job 9 searched the biggest internal fragmentation in block 2 with a memory size of 200k, where Job 9 has 112k internal fragmentation in block 2. Job 8 still remains because it had two turnaround. Job 10 entered in block 4 with a memory size of 115k with 15k internal fragmentation of block 10.