Best fit memory allocation is the smallest partition fitting the requirements which makes the best use of memory space. The illustration above shows the method of best fit memory allocation. In best fit, each job should find the smallest memory block into which the job will fit.
The first column is the memory divided into five blocks using fixed partition.
On the second column:
Job 1 has 100k memory size, so it has to be allocated in a block that is not too small, and not too large than the memory size. Block 1 has 50k, so it is impossible to fit. Block 2 has 200k, though the memory size of Job 1 could fit, still it is too large. Block 3 has 70k, smaller than the memory size of Job 1. Block 4 has 115k, it is perfect for the memory size Job 1, but then, Job 1 must take a look at the remaining block just to be sure that the Block 4 is the best fit. Lastly, Block 5 has 15k, also smaller than the memory size of Job 1. With these, it is assumed that Block 4 with 115k memory size is the best fit for Job 1 which has 100k memory size.
Job 2 has 5k memory size. With the sizes of the memory in each block, it can be seen that Job 2 could fit in any block except for Block 4 since Job 1 is allocated in this block. But then, the sizes of the memory of Block 1, 2, and 3 are too large for Job 2. And so, it is assumed that Block 5 with 15k memory size is the best fit for Job 2 which has 5k memory size.
Job 3 has 35k memory size. The remaining blocks that have to be allocated are blocks 1, 2 and 3. These blocks have big enough memory size but then Block 2 and Block 3 are too large for Job 3. With these, Job 3 which has 35k memory size is allocated at Block 1 with 50k memory size.
Job 4 has 15k memory size. Now, the remaining blocks are Block 2, and Block 3. And in these two blocks, Block 3 has smaller memory size, which means Block 3 with 70k memory size is the best fit for Job 4 which has 15k memory size.
Job 5 has 23 k memory size, and the only block which has to be allocated is Block 2. So Job 5 with 23k memory size is allocated at Block 2 which has 200k memory size.
On the third column:
Job 3 with 35k memory size has 2 turnarounds, which means it would still remain in Block 1. Job 5 with 23k memory size still has to remain in Block 2 since it has 2 turnarounds.
Job 4 has ended and it was replace by Job 7 with 25k memory size. Job 2 also ended and was replaced by Job 6 with 6k memory size.
On the fourth column:
Job 3 already ended, and so Block 1 is free and ready to be allocated by other jobs. Job 5 also ended and it was replaced by Job 9 with 88k memory size. Job 7 has also ended and was replaced by Job 8 with the memory of 100k. Job 6 also ends and Block 5 is also free and ready to be allocated. Job 8 was allocated at Block 3 since Block 2 is too large and the other blocks are too small. Same goes for Job 9, it was allocated at Block 2 since it would be the best fit for Job 9.
On the fifth column:
Job 1 was finished on its third turnaround, and it was replaced by Job 10 with 100k memory size. Block 1 and Block 5 remained free and ready to be allocated. While Job 8, and Job 9 remained in their blocks since it is their second turnaround.
On the sixth column:
Job 8 ended, so Block 3 is free. Job 9 still remained since it has to finish its last turnaround. Job 10 also remained. And the remaining blocks are free.
On the seventh column:
Job 9 ended, and Block 2 is free. But still, Job 10 has to remain to finish its last turnaround.
On the eighth column:
Job 10 finished its turnaround and all the blocks are free and ready to be allocated again.
First fit allocation method is the first partition fitting the requirements and faster in making allocations. The illustration above displays the method of first fit memory allocation. In first fit, the jobs should allocate the first free block in which their memory will fit even if it means leading to memory waste.
The first column is the memory divided into five blocks using fixed partition.
On the second column:
Job 1 has 100k memory size. Since Block 1 has smaller memory size and Block 2 has enough memory, then Job 1 was allocated at Block 2. Next is Job 2 with 10k memory size. And because Block 1 has enough memory for Job 2, Job 2 was allocated at Block 1. Job 3 has 35k memory size. Block 1 and Block 2 has already been allocated with Job 1 and Job 2, therefore, Job 3 was allocated in Block 3 since it can hold the memory size of Job 3. Job 4 with 15k memory size has been allocated in Block 4 which has 115k memory size. Since the remaining block for the first turnaround has a memory of 15k, Job 5 could not fit on the said block. And so, Job 5 is on the waiting queue, and Job 6 was allocated in Block 5 since it only has 9k memory size.
On the third column:
Job 5 replaced Job 2 in Block 1. Job 1 and Job 3 remained while Job 7 replaced Job 4 on Block 4. Job 6 finished its turnaround, and Block 5 is free.
On the fourth column:
Job 5 still remained in Block 1 as well as Job 1 in Block 2. Job 3 already ended, and was immediately replaced with Job 8 with 55k memory size. Job 7 also ends and was replaced with Job 9 in Block 4. Still, Block 5 remained free.
On the fifth column:
Job 5 finished the job and so, Block 1 is free. Job 1 was finished on its third turnaround, and it was replaced by Job 10 with 100k memory size. Block 5 remained free while Job 8 and Job 9 remained in their blocks since it is their second turnaround.
On the sixth column:
Job 8 ended, so Block 3 is free. Job 9 still remained since it has to finish its last turnaround. Job 10 also remained. And the remaining blocks are free.
On the seventh column:
Job 9 ended, and Block 4 is free. But still, Job 10 has to remain to finish its last turnaround.
On the eighth column:
Job 10 finished its turnaround and all the blocks are free and ready to be allocated again.
The first column is the memory divided into five blocks using fixed partition.
On the second column:
Job 1 has 100k memory size. Since Block 1 has smaller memory size and Block 2 has enough memory, then Job 1 was allocated at Block 2. Next is Job 2 with 10k memory size. Since the Block with biggest memory had been allocated, Job 2 proceeded to the next Block that is smaller than Block 2 and larger than other blocks, which is Block 4. Job 3 came next with 35k memory size. Aside from Block 2 and Block 4, Block 3 also has a large memory; therefore, Job 3 allocated Block 3. The free blocks are Block 1 and Block 5, since Job 4 would not fit in Block 5, Job 4 allocated Block 1. Since the remaining block for the first turnaround has a memory of 15k, Job 5 could not fit on the said block. And so, Job 5 is on the waiting queue, and Job 6 was allocated in Block 5 since it only has 9k memory size.
On the third column:
Job 5 replaced Job 2 in Block 4. Job 1 and Job 3 remained while Job 7 replaced Job 4 on Block 1. Job 6 finished its turnaround, and Block 5 is free.
On the fourth column:
Job 5 still remained in Block 4 as well as Job 1 in Block 2. Job 3 already ended, and was immediately replaced with Job 8 with 55k memory size. Job 7 also ends, so Block 1 is free. Still, Block 5 remained free.
On the fifth column:
Job 1 was finished on its third turnaround, and it was replaced by Job 9 with 88k memory size. Job 8 remained in its block and Job 5 in Block 4 was replaced by Job10. Block 1 and Block 5 remained free.
On the sixth column:
Job 8 ended, so Block 3 is free. Job 9 still remained. Job 10 also remained. And the remaining blocks are free.
On the seventh column:
. Job 9 and Job 10 still remained since it has to finish its last turnaround. While the remaining blocks are free.
On the eighth column:
Job 9 and Job 10 finished its turnaround and all the blocks are free and ready to be allocated again.
0 comments:
Post a Comment