What are they?
First-fit and Best-fit are memory allocation schemes that were typically used in dynamic and fixed partition memory allocation schemes to allocate memory.
To simplify what they are, consider the following list of jobs and the available resources.
The above figure shows a list of jobs and the resources to which these jobs could be allocated.
Here to allocate the jobs, we use either the first-fit memory allocation scheme or the best-fit memory allocation scheme.
Let us allocate the jobs first on the basis of first-fit memory allocation and then on the basis of best-fit memory allocation to understand how jobs are allocated and the pros and cons of the two schemes.
Allocating using First-fit memory allocation
Consider the same image.
Here we are using First-fit memory allocation. Therefore, jobs have to be allocated on the basis of the first partition meeting the requirements.
First consider Job 1. The memory size of Job 1 is 50K. When we search through the available partitions, we can see that the first partition could hold up to 70K. Therefore, Job 1 could be allocated to this partition. Since it is the the first partition meeting the requirements, the memory size of other partitions need not be compared.
Now consider Job 2. Job 2 cannot be allocated to partition 1 as Job 1 is already allocated to it. Then the next available partition could hold up to 40K and the size of Job 2 is 30K. Therefore, Job 2 is allocated to partition 2.
Next consider Job 3. Job 3 has to be allocated to either partitions 3 or 4 as partitions 1 and 2 have already been allocated. The size of Job 3 is 25K and partition 3 could hold up to 30K. Therefore, Job 3 could be allocated to partition 3.
Finally consider Job 4. The only remaining partition that Job 4 could be allocated is partition 4. However, the maximum memory that this partition can hold is 25K and the size of Job 4 is 30K. Therefore, the size of Job 4 > the partition to which it could have been allocated. Therefore, Job 4 has to wait until either of Job 1 or Job 2 or Job 3 runs to completion.
The final memory allocation graph could be summarized as follows:
The memory wastage due to the allocation on the basis of this scheme is as follows:
Allocating using Best-fit memory allocation
Here we are using Best-fit memory allocation. Therefore, jobs have to be allocated on the basis of the best partition (partition with the least memory wastage) meeting the requirements.
First consider Job 1. The memory size of Job 1 is 50K. When we search through the available partitions, we can see that the best partition that could hold 50K is the first partition as other partitions cannot hold that amount of memory. Therefore, Job 1 could be allocated to this partition.
Now consider Job 2. Job 2 cannot be allocated to partition 1 as Job 1 is already allocated to it. The second partition could hold up to 40K and the third partition could hold up to 30K. The size of Job 2 is 30K. Since we are considering a partition with the least wasted space or least memory wastage when allocated, Job 2 is allocated to partition 3. If allocated to partition 2 as done using first-fit, then there will be a 10K wastage. No wastage is incurred if allocated to partition 3. Therefore, partition 3 would be the ideal option for Job 2.
Next consider Job 3. Job 3 has to be allocated to either partitions 2 or 4 as partitions 1 and 3 have already been allocated. The size of Job 3 is 25K and partition 2 could hold up to 40K and partition 4 could hold up to 25K. Since we are considering a partition with the least wasted space or least memory wastage when allocated, Job 3 is allocated to partition 4. If allocated to partition 2 then there will be a 15K wastage. No wastage is incurred if allocated to partition 4. Therefore, partition 4 would be the ideal option for Job 3.Therefore, Job 3 could be allocated to partition 4.
Finally consider Job 4. The only remaining partition that Job 4 could be allocated is partition 2. Since the size of the partition is greater than the memory size of Job 4, Job 4 could be allocated to partition 2.
By this method and for this example, no jobs are waiting as opposed to first-fit memory allocation as described above. However, this might not be true for every example when using best-fit memory allocation (i.e. best-fit could also result in jobs to wait for allocation).
The final memory allocation graph could be summarized as follows:
The memory wastage due to the allocation on the basis of this scheme is as follows:
As you could see the memory was best allocated using best-fit memory allocation, resulting in only 30K internal fragmentation as opposed to 35K using first-fit scheme.
However, the entire list needs to be searched when using best-fit memory allocation before a job is allocated to partitions. This is a very cumbersome operation if there a re large no. of partitions in the system.
Therefore, best-fit memory allocation is relatively slow in allocating memory.
Advantages and disadvantages of the two schemes
Note: Although partitions were shown by graphical figures in the above explanation, actually the OS accesses these partitions in the form of tables (the job list refers to the memory list).
In fact for allocation two separate memory lists called the free list and the busy list are used. Free list shows the partitions that are free and if matched where jobs could be allocated. The busy list consist of the partitions where the jobs were allocated.
To enhance clarity of these two mechanisms and to get a rough idea of the actual memory allocation, the following two tables shoe how the memory is allocated in a tabulated manner. The list consist of both the busy list and the free list. At any time the two lists could be separated by identifying which partitions were allocated (shift to busy list) and which partitions are free (shift to free list).
Using first-fit memory allocation:
Using best-fit memory allocation:
First-fit and Best-fit are memory allocation schemes that were typically used in dynamic and fixed partition memory allocation schemes to allocate memory.
To simplify what they are, consider the following list of jobs and the available resources.
Here to allocate the jobs, we use either the first-fit memory allocation scheme or the best-fit memory allocation scheme.
- The first-fit memory allocation scheme allocates on the basis of the first partition fitting the requirements.
- The best-fit memory allocation scheme allocates on the basis of the best partition (one with the least memory wastage) fitting the requirements.
Let us allocate the jobs first on the basis of first-fit memory allocation and then on the basis of best-fit memory allocation to understand how jobs are allocated and the pros and cons of the two schemes.
Allocating using First-fit memory allocation
Consider the same image.
Here we are using First-fit memory allocation. Therefore, jobs have to be allocated on the basis of the first partition meeting the requirements.
First consider Job 1. The memory size of Job 1 is 50K. When we search through the available partitions, we can see that the first partition could hold up to 70K. Therefore, Job 1 could be allocated to this partition. Since it is the the first partition meeting the requirements, the memory size of other partitions need not be compared.
Now consider Job 2. Job 2 cannot be allocated to partition 1 as Job 1 is already allocated to it. Then the next available partition could hold up to 40K and the size of Job 2 is 30K. Therefore, Job 2 is allocated to partition 2.
Next consider Job 3. Job 3 has to be allocated to either partitions 3 or 4 as partitions 1 and 2 have already been allocated. The size of Job 3 is 25K and partition 3 could hold up to 30K. Therefore, Job 3 could be allocated to partition 3.
Finally consider Job 4. The only remaining partition that Job 4 could be allocated is partition 4. However, the maximum memory that this partition can hold is 25K and the size of Job 4 is 30K. Therefore, the size of Job 4 > the partition to which it could have been allocated. Therefore, Job 4 has to wait until either of Job 1 or Job 2 or Job 3 runs to completion.
The final memory allocation graph could be summarized as follows:
The memory wastage due to the allocation on the basis of this scheme is as follows:
Allocating using Best-fit memory allocation
Here we are using Best-fit memory allocation. Therefore, jobs have to be allocated on the basis of the best partition (partition with the least memory wastage) meeting the requirements.
First consider Job 1. The memory size of Job 1 is 50K. When we search through the available partitions, we can see that the best partition that could hold 50K is the first partition as other partitions cannot hold that amount of memory. Therefore, Job 1 could be allocated to this partition.
Now consider Job 2. Job 2 cannot be allocated to partition 1 as Job 1 is already allocated to it. The second partition could hold up to 40K and the third partition could hold up to 30K. The size of Job 2 is 30K. Since we are considering a partition with the least wasted space or least memory wastage when allocated, Job 2 is allocated to partition 3. If allocated to partition 2 as done using first-fit, then there will be a 10K wastage. No wastage is incurred if allocated to partition 3. Therefore, partition 3 would be the ideal option for Job 2.
Next consider Job 3. Job 3 has to be allocated to either partitions 2 or 4 as partitions 1 and 3 have already been allocated. The size of Job 3 is 25K and partition 2 could hold up to 40K and partition 4 could hold up to 25K. Since we are considering a partition with the least wasted space or least memory wastage when allocated, Job 3 is allocated to partition 4. If allocated to partition 2 then there will be a 15K wastage. No wastage is incurred if allocated to partition 4. Therefore, partition 4 would be the ideal option for Job 3.Therefore, Job 3 could be allocated to partition 4.
Finally consider Job 4. The only remaining partition that Job 4 could be allocated is partition 2. Since the size of the partition is greater than the memory size of Job 4, Job 4 could be allocated to partition 2.
By this method and for this example, no jobs are waiting as opposed to first-fit memory allocation as described above. However, this might not be true for every example when using best-fit memory allocation (i.e. best-fit could also result in jobs to wait for allocation).
The final memory allocation graph could be summarized as follows:
The memory wastage due to the allocation on the basis of this scheme is as follows:
As you could see the memory was best allocated using best-fit memory allocation, resulting in only 30K internal fragmentation as opposed to 35K using first-fit scheme.
However, the entire list needs to be searched when using best-fit memory allocation before a job is allocated to partitions. This is a very cumbersome operation if there a re large no. of partitions in the system.
Therefore, best-fit memory allocation is relatively slow in allocating memory.
Advantages and disadvantages of the two schemes
Note: Although partitions were shown by graphical figures in the above explanation, actually the OS accesses these partitions in the form of tables (the job list refers to the memory list).
In fact for allocation two separate memory lists called the free list and the busy list are used. Free list shows the partitions that are free and if matched where jobs could be allocated. The busy list consist of the partitions where the jobs were allocated.
To enhance clarity of these two mechanisms and to get a rough idea of the actual memory allocation, the following two tables shoe how the memory is allocated in a tabulated manner. The list consist of both the busy list and the free list. At any time the two lists could be separated by identifying which partitions were allocated (shift to busy list) and which partitions are free (shift to free list).
Using first-fit memory allocation:
Using best-fit memory allocation:
Comments
Post a Comment