CONTIGUOUS MEMORY ALLOCATION

CONTIGUOUS MEMORY ALLOCATION

Download here 

Contiguous Memory Allocation

·         Memory is divided into 2 partitions:

1.      OS

2.      User Process

·         OS can be placed either in low memory or high memory. It is based on location of Interrupt vector which is in general in low memory.

·         Memory Allocation refers to the way of allocating memory to multiple processes which are input queue and waiting to be brought into memory.

·         In Contiguous memory allocation, each process is contained in a single contiguous section of memory.

Memory mapping and protection

·         Relocation Register & Limit Register are used for memory mapping and protection.

·         Relocation Register – Smallest Physical address (Base or starting address)

·         Limit Register – range of logical addresses ( offset)

·         MMU maps logical address dynamically by adding value in relocation register and resultant address is sent to memory.

·         Protection – Every address produced by CPU is checked with Relocation & Limit Register (OS & data can be protected by being modified by user process)

·         Dynamic change in OS size can be obtained by using relocation register

o   For example, if os has code & device driver buffer space and the device driver is not in use then that space can be used for other purpose by reducing the size of OS (transient OS code).

Memory Allocation

·         Multiple partition Method:

o   Fixed Size partitions:

§  Each Partition has exactly one process.

§  Degree of multi-programming – bound to - No. of partitions

§  When a partition is free, a process is selected from the input queue and is loaded into free partition.

§  When the process terminates, the partition becomes available for another process.

·         Called as MFT in IBM OS/360 OS.

·         This restricts both the number of simultaneous processes and the maximum size of each process, and is no longer used.

o   Variable Size Partitions

·         Keeps a table of unused (free) memory blocks (holes), and to find a hole of a suitable size whenever a process needs to be loaded into memory.

·         Initially – all memory is available – large block of available memory – hole.

·         Later – memory contains a set of holes of variable sizes.

·         Cpu scheduling algo. – input queue – allocate when free required size hole is available – if not wait.

·         Large hole can be splitted into 2 parts – allocate one and add other to hole set.

·         Merge 2 holes when new hole is adjacent to old hole.

·          There are many different strategies for finding the "best" allocation of memory to processes, including the three most commonly discussed:

1.      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.

2.      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.

3.      Worst fit - Allocate the largest hole available, thereby increasing the likelihood that the remaining portion will be usable for satisfying future requests.

·         Simulations show that either first or best fit are better than worst fit in terms of both time and storage utilization. First and best fits are about equal in terms of storage utilization, but first fit is faster.

8.3.3. Fragmentation

• External Fragmentation exists when there is enough total memory space to satisfy a request but the available spaces are not contiguous.
• Worst case – block of free memory between every 2 processes and if these small pieces are one block instead then we might be able to run several more processes.
• Both best-fit and first-fit suffer with external fragmentation.
• 50-percent Rule:
• Statistical analysis of first-fit says for any kind of optimization out of given N allocated blocks another 0.5N blocks will be lost for fragmentation.
• Internal fragmentation – unused memory that is internal to a partition.
• When memory is partitioned into fixed-size blocks and allocate memory in units based on block size then memory allocated to a process may be slightly larger than the requested memory.
• COMPACTION - Solution for External Fragmentation
• Shuffle the memory contents so as to place all free memory together in one large block.
• Possible only when binding is during execution time (dynamic)
• Another solution (paging and segmentation) is to allow processes to use non-contiguous blocks of physical memory, with a separate relocation register for each block.