CONTIGUOUS MEMORY ALLOCATION

What does Contiguous Memory Allocation mean?

• Contiguous memory allocation is a classical memory allocation model that assigns a process consecutive memory blocks (that is, memory blocks having consecutive addresses).
• Contiguous memory allocation is one of the oldest memory allocation schemes. 
• When a process needs to execute, memory is requested by the process.
• The size of the process is compared with the amount of contiguous main memory available to execute the process.
• If sufficient contiguous memory is found, the process is allocated memory to start its execution. 
• Otherwise, it is added to a queue of waiting processes until sufficient free contiguous memory is available.
• One disadvantage of contiguous memory allocation is that the degree of multi-programming is reduced due to processes waiting for free memory.

MEMORY PROTECTION

• The contiguous memory allocation scheme can be implemented in operating systems with the help of two registers, known as the base and limit registers.
•  When a process is executing in main memory, its base register contains the starting address of the memory location where the process is executing, while the amount of bytes consumed by the process is stored in the limit register.
•  A process does not directly refer to the actual address for a corresponding memory location.
•  Instead, it uses a relative address with respect to its base register.
•  All addresses referred by a program are considered as virtual addresses. 
• The CPU generates the logical or virtual address, which is converted into an actual address with the help of the memory management unit (MMU).
•  The base address register is used for address translation by the MMU. Thus, a physical address is calculated as follows:
• Physical Address = Base register address + Logical address/Virtual address
• The address of any memory location referenced by a process is checked to ensure that it does not refer to an address of a neighboring process.
•  This processing security is handled by the underlying operating system.

MEMORY ALLOCATION

The main memory must accommodate both the operating system and the various user processes.

 We therefore need to allocate different parts of the main memory in the most efficient way possible.

The memory is usually divided into two partitions: one for the resident operating system, and one for the user processes.

 We may place the operating system in either low memeory or high memory. 

Main memory usually has two partitions

• Low Memory -- Operating system resides in this memory.

• High Memory -- User processes then held in high memory.

• With this approach each process is contained in a single contiguous section of memory.

Operating system uses the following memory allocation mechanism.

Single-partition allocation

In this type of allocation, relocation-register scheme is used to protect user processes from each other, and from changing operating-system code and data.

 Relocation register contains value of smallest physical address whereas limit register contains range of logical addresses.

 Each logical address must be less than the limit register.

Multiple-partition allocation

In this type of allocation, main memory is divided into a number of fixed-sized partitions where each partition should contain only one process.

 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.

One of the simplest methods for memory allocation is to divide memory into several fixed-sized partitions.

 Each partition may contain exactly one process.

 In this multiple-partition method, 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.

 Finally, when a process arrives and needs memory, a memory section large enough for this process is provided.

The difficulty with contiguous allocation is finding space for a new file. 

If the file to be created is n blocks long, then the OS must search for n free contiguous blocks.

 First-fit, best-fit, and worst-fit strategies  are the most common strategies used to select a free hole from the set of available holes. 

Simulations have shown that both first-fit and best-fit are better than worst-fit in terms of both time storage utilization. 

Neither first-fit nor best-fit is clearly best in terms of storage utilization, but first-fit is generally faster.

STRATEGIES USED TO SELECT A FREE BLOCK FROM THE SET OF AVAILABLE BLOCKS ARE

FIRST FIT: There may be many holes in the memory, so the operating system, to reduce the amount of time it spends analyzing the available spaces, begins at the start of primary memory and allocates memory from the first hole it encounters large enough to satisfy the request. Using the same example as above, first fit will allocate 12KB of the 14KB block to the process.

BEST FIT: The allocator places a process in the smallest block of unallocated memory in which it will fit. For example, suppose a process requests 12KB of memory and the memory manager currently has a list of unallocated blocks of 6KB, 14KB, 19KB, 11KB, and 13KB blocks. The best-fit strategy will allocate 12KB of the 13KB block to the process.

WORST FIT: The memory manager places a process in the largest block of unallocated memory available. The idea is that this placement will create the largest hold after the allocations, thus increasing the possibility that compared to best fit; another process can use the remaining space. Using the same example as above, worst fit will allocate 12KB of the 19KB block to the process, leaving a 7KB block for future use.

The Best fit and First fit strategies both leave a tiny segment of memory unallocated just beyond the new process. Since the amount of memory is small, it is not likely that any new processes can be loaded here. This condition of splitting primary memory into segments as the memory is allocated and deallocated is known as fragmentation. The Worst fit strategy attempts to reduce the problem of fragmentation by allocating the largest fragments to new processes. 

FRAGMENTATION

As processes are loaded and removed from memory, the free memory space is broken into little pieces. It happens after sometimes that processes cannot be allocated to memory blocks considering their small size and memory blocks remains unused. This problem is known as Fragmentation.

Fragmentation is of two types

External fragmentation-Total memory space is enough to satisfy a request or to reside a process in it, but it is not contiguous so it can not be used.

Internal fragmentation-Memory block assigned to process is bigger.

 Some portion of memory is left unused as it can not be used by another process.

External fragmentation can be reduced by compaction or shuffle memory contents to place all free memory together in one large block.

 To make compaction feasible, relocation should be dynamic.