Best-fit
Memory management
Memory Allocation or Contiguous memory allocation
Main memory usually has two partitions:
Low Memory — Operating system resides in this memory.
High Memory — User processes then held in high memory.
Operating system uses the following memory allocation mechanism
a) SINGLE-PARTITION ALLOCATION
If the operating system is residing in low memory, and the user processes are executing in high memory. And operating system code and data are protected from changes by the user processes. We also need protect the user processes from one another. We can provide this 2 protection by using a relocation registers.
The relocation register contains the value of the smallest physical address; the limit register contains the range of logical addresses (for example, relocation = 100,040 and limit =74,600).
With relocation and limit registers, each logical address must be less than the limit register;
The MMU (Memory Management Unit) maps the logical address dynamically by adding the value in the relocation register. This mapped address is sent to memory.
The relocation-register scheme provides an effective way to allow the operating-system size to change dynamically.
Fig : HARDWARE SUPPORT FOR RELOCATION AND LIMIT REGISTERS
b) MULTIPLE-PARTITION ALLOCATION
One of the simplest schemes for memory allocation is to divide memory into a number of fixed-sized partitions. Each partition may contain exactly one process.
Thus the degree of multiprogramming is bound of partitions. When a partition is free, a process is selected from the input queue and is loaded into the free partition. When the process terminates, the partition becomes available for another process.
The operating system keeps a table indicating which parts of memory are available and which are occupied.
Initially, all memory is available for user processes, and is considered as one large block, of available memory, a hole.
When a process arrives and needs memory, operating system forms a hole large enough for this process.
When a process arrives and needs memory, we search this set for a hole that is large enough for this process. If the hole is to large, it is split into two: One part is allocated to the arriving process; the other is returned to the set of holes. When a process terminates, it releases its block of memory, which is then placed back in the set of holes. If the new hole is adjacent to other holes, we merge these adjacent holes to form one larger hole.
This procedure is a particular instance of the general dynamic storage-allocation problem, which is how to satisfy a request of size n from a list of free holes. There are many solutions to this problem.
The set of holes is searched to determine which hole is best to allocate, first-fit, best-fit, and worst-fit are the most common strategies used to select a free hole from the set of available holes.
First-fit:
Allocate the first hole that is big enough. Searching can start either at the beginning of the set of holes or where the previous first-fit search ended. We can stop searching as soon as we find a free hole that is large enough.
Best-fit:
Allocate the smallest hole that is big enough. We must search the entire list, unless the list is kept ordered by size. This strategy produces the smallest leftover hole.
Worst-fit:
Allocate the largest hole. Again, we must search the entire list unless it is sorted by size. This strategy produces the largest leftover hole which may be more useful than the smaller leftover hole from a best-t approach.
Posted By-: Vissicomp Technology Pvt. Ltd.
Website -: http://www.vissicomp.com
Visicomp Codder 