Contiguous Memory Allocation
The operating
system is allocated space first, usually at either low or high memory
locations, and then the remaining available memory is allocated to processes as
needed. Contiguous Memory Allocation is one of the approaches where each
process is loaded into a single contiguous section of memory.
Memory Mapping
and Protection
The
relocation-register scheme provides protection against user programs accessing
areas that they should not, allows programs to be relocated to different memory
starting addresses as needed, and allows the memory space devoted to the OS to
grow or shrink dynamically as needs change.
Memory
Allocation
One method of
allocating contiguous memory is to divide all available memory into equal sized
partitions, and to assign each process to its own partition. The degree of
multi programming is bound by the number of partitions.
An alternative
approach is variable-partition scheme, the operating system keeps a table
indicating which parts of memory are available and which are occupied. The approach
is to keep a list of unused ( free ) memory blocks
( holes ), and to find a hole of a suitable size whenever a process
needs to be loaded into memory. There are many different strategies for finding
the "best" allocation of memory to processes:
- First fit -
Search the list of holes until one is found that is big enough to satisfy
the request, and assign a portion of that hole to that process. Whatever
fraction of the hole not needed by the request is left on the free list as
a smaller hole. Subsequent requests may start looking either from the
beginning of the list or from the point at which this search ended.
- Best fit -
Allocate the smallest hole that is big enough to satisfy
the request. This saves large holes for other process requests that may
need them later, but the resulting unused portions of holes may be too
small to be of any use, and will therefore be wasted. Keeping the free
list sorted can speed up the process of finding the right hole.
- Worst fit - Allocate
the largest hole available, thereby increasing the likelihood that the
remaining portion will be usable for satisfying future requests.
Simulations have
shown that both first fit and best fit are better than worst fit in terms of
decreasing time and storage utilization. First and best fits are about equal in
terms of storage utilization, but first fit is faster.
Fragmentation
All the memory
allocation strategies suffer from external fragmentation,
though first and best fits experience the problems more so than worst fit.
External fragmentation means that the available memory is broken up into lots
of little pieces, none of which is big enough to satisfy the next memory
requirement, although the sum total could.
Internal
fragmentation also
occurs, with all memory allocation strategies. This is caused by the fact that
memory is allocated in blocks of a fixed size, whereas the actual memory needed
will rarely be that exact size.
If the programs in
memory are relocatable, ( using execution-time address binding ),
then the solution to external fragmentation problem is compaction,
i.e. moving all processes down to one end of physical memory. This only
involves updating the relocation register for each process, as all internal
work is done using logical addresses.
Another possible
solution to the external fragmentation problem is to permit the logical address
space of the process to be non contiguous. Two techniques achieve this solution
are Paging and Segmentation.
No comments:
Post a Comment