Non-Contiguous Memory Allocation in Operating System

Memory is nothing but a storage space where various data are stored. We can store data in temporary and permanent memory as per our future requirements for data. We can also keep our data safe by storing them in memory. Allocation of memory simply means providing an individual space for individual data or files. For example, if F is a file, the system will allot a certain address at which this F-named file will be stored in the system's memory.

Memory Management Strategies

1) Non-Contiguous Memory Allocation

1. Paging
2. Multilevel Paging
3. Inverted Paging
4. Segmented Paging
5. Segmentation

2) Contiguous Memory Allocation

a. Fixed Partition

b.Variable/Dynamic Partition

Non-contiguous memory allocation

Non-contiguous memory allocation is one of the most important strategies for memory management in operating systems. As the name suggests, it stores the data in a discontinuous pattern. In this method, the allocation of memory is not contiguous, which means the allocation of memory for any file or track happens randomly. The memory is not branched into fixed parts and, the allocation of memory depends on the size of the file and the available space in the memory.

The file is stored wherever there is an unoccupied or empty space inside the memory. The wastage of memory becomes very less due to the random allocation of memory.

Let us see an example: if a process contains 3 blocks named Yi, Yii, and Yiii, the system will allocate/ provide a  non-contiguous or random address to the entire block of that process in the RAM. It is not mandatory to allocate Yi next to Yii and Yii next to Yiii if neighbor memory addresses are not available in the system. It takes slightly more time to access different blocks of a process due to the random allocation of the blocks. It uses a pointer to store the address, and it also requires an index.

Advantages of Non-Contiguous Memory Allocation:

There are certain advantages of using the non-contiguous strategy of memory allocation:

1. It can help to reduce external fragmentation, as blocks of memory can be allocated and freed in any order rather than only being able to be freed in the reverse order in which they were allocated, as is the case with contiguous memory allocation.
2. It allows for more flexible memory management, as blocks of memory can be allocated and freed independently of one another.
3. It can be more systematic in terms of memory usage, as it allows the operating system to allocate memory more efficiently by using all available blocks of memory rather than leaving gaps between allocated blocks.
4. It allows the operating system to allocate memory more dynamically. It can allocate free blocks of memory as needed rather than pre-allocating a large block of contiguous memory.
5. It can be used to improve the execution of the operating system by reducing the time required to allocate and free memory, as blocks of memory can be allocated and freed more quickly than with contiguous memory allocation.

Disadvantages of Non-Contiguous Memory Allocation

There are a few disadvantages of using non-contiguous memory allocation in Operating system:

1. It is more difficult to implement and manage than contiguous memory allocation, as the blocks of memory are scattered throughout the address space.
2. It can lead to internal fragmentation, where there are many small blocks of free memory scattered throughout the address space that cannot be used to satisfy a request for a larger block of memory.
3. It can lead to external fragmentation, where there are large blocks of free memory available, but they are not contiguous, so they cannot be used to satisfy a request for a larger block of memory.
4. It can result in reduced performance, as the operating system must search for a suitable block of memory to satisfy a request, which can take longer than contiguous memory allocation.
5. It can make it more difficult to share memory between processes, as the blocks of memory are not contiguous.
6. It can make it more difficult to access data stored in non-contiguous blocks of memory, as the processor may need to perform multiple memory accesses to retrieve the data.

Working of Non-Contiguous Memory Allocation

In non-contiguous memory allocation, blocks of memory are scattered throughout the address space rather than being contiguous. When a memory request is made, the operating system searches for a suitable block of memory to satisfy the request.

To manage non-contiguous memory allocation, the operating system typically maintains a data structure called a "free list" or "free pool" that keeps track of all the available blocks of free memory. When a memory request is made, the operating system searches the free list for a suitable block of memory. If a suitable block is found, it is allocated to the requesting process and removed from the free list. If no suitable block is found, the operating system may need to perform additional memory management tasks, such as swapping blocks of memory to and from disk or requesting more memory from the system.

Once a block of memory has been allocated to a process, it can be used by the process to store data or program code. When the process no longer needs the memory, it can be returned to the free list by the operating system to be reused for future memory requests.

Types of Non-Contiguous Memory Allocation:

The non-contiguous memory allocation method is further classified into five different categories, which are mentioned below:-

1. Paging

Paging is a technique used in non-contiguous memory allocation to improve the performance of the operating system. It works by dividing the virtual address space of a process into smaller units called "pages" and mapping each page to a physical page of memory.

In a paging system, the operating system maintains a data structure called a "page table" that maps each page to a physical page of memory. When a process accesses a virtual address, the operating system translates the virtual address to a physical address using the page table. This allows the operating system to quickly translate virtual addresses to physical addresses, but it requires a separate entry in the page table for each page of memory. This can be inefficient if the process has a large number of pages, as it requires a large page table and may result in a lot of cache misses when accessing the page table.

Paging can be particularly useful in non-contiguous memory allocation, as it allows the operating system to manage blocks of memory that are scattered throughout the address space in a more organized and efficient manner. It can also be used in concurrence with other memory management techniques, such as demand paging and multilevel paging, to improve the performance of the operating system.

2. Multilevel paging

Multilevel paging is a technique used in non-contiguous memory allocation to improve the performance of the operating system. It works by dividing the virtual address space of a process into smaller units called "pages" and "page tables".

In a traditional paging system, the virtual address space is divided into pages. The operating system maintains a page table that maps each page to a physical memory page. This allows the operating system to quickly transcribe a virtual memory or address to a physical address, but it requires a separate entry in the page table for each page of memory. This can be inefficient if the process has a large number of pages, as it requires a large page table and may result in a lot of cache misses when accessing the page table.

In a multilevel paging system, the virtual address space is divided into pages and page tables. The operating system maintains a page table for each page table, and each page table maps a set of pages to physical pages of memory. This allows the operating system to translate a virtual address to a physical address using multiple levels of page tables, rather than a single, large page table.

This can be more efficient if the process has a large number of pages, as it requires a smaller page table and may result in fewer cache misses when accessing the page table. Multilevel paging can be particularly useful in non-contiguous memory allocation, as it allows the operating system to locate blocks scattered throughout the address space quickly. It can also be used in concurrence with other memory management techniques, such as demand paging, to improve the production of the operating system.

3.  Inverted paging

Inverted paging is a technique used in non-contiguous memory allocation to improve the performance of the operating system. It works by maintaining a data structure called an "inverted page table" that maps virtual addresses to physical addresses.

In a traditional page table, the entries in the table are indexed by the virtual addresses of the pages and contain the corresponding physical addresses. This allows the operating system to translate a virtual address to a physical address quickly, but it requires a separate entry in the table for each page of memory. This can be inefficient if the process has a large number of pages, as it requires a large page table and may result in a lot of cache misses when accessing the page table.

In an inverted page table, the entries are indexed by the physical addresses of the pages and contain the corresponding virtual addresses. This allows the operating system to translate a physical address to a virtual address quickly, but it requires a separate entry in the table for each physical page of memory. This can be more efficient if the process has a large number of pages, as it requires a smaller page table and may result in fewer cache misses when accessing the page table.

Inverted paging can be particularly useful in non-contiguous memory allocation, as it allows the operating system to locate blocks scattered throughout the address space quickly. It can also be used in concurrence with other memory management techniques, such as demand paging, to improve the production of the operating system.

4. Segmentation

Segmentation is a technique used in non-contiguous memory allocation to improve the performance of the operating system. It works by dividing the virtual address space of a process into smaller units called "segments" and "pages".

In a traditional paging system, the virtual address space is divided into pages. The operating system maintains a page table that maps each page to a physical memory page. This allows the operating system to translate a virtual address to a physical address quickly, but it requires a separate entry in the page table for each page of memory. This can be inefficient if the process has a large number of pages, as it requires a large page table and may result in a lot of cache misses when accessing the page table.

In a segmentation system, the virtual address space is divided into segments. Each segment is a contiguous block of virtual addresses representing a logical grouping of related memory, such as code, data, or stack. The operating system maintains a data structure called a "segment table" that maps each segment to a physical memory block. This allows the operating system to translate a virtual address to a physical address using the segment table rather than a page table.

Segmentation can be particularly useful in non-contiguous memory allocation, as it allows the operating system to manage blocks of memory that are scattered throughout the address space in a more organized and efficient manner. It can also be used in concurrence with other memory management techniques, such as paging, to improve the performance of the operating system.

5. Segmented paging

Segmented paging is a technique used in non-contiguous memory allocation to improve the performance of the operating system. It works by dividing the virtual address space of a process into smaller units called "segments" and "pages".

In a traditional paging system, the virtual address space is divided into pages, and the operating system maintains a page table that maps each page to a physical page of memory. This allows the operating system to quickly transcribes a virtual memory or address to a physical address, but it requires a separate entry in the page table for each page of memory. This can be inefficient if the process has a large number of pages, as it requires a large page table and may result in a lot of cache misses when accessing the page table.

In a segmented paging system, the virtual address space is divided into segments and pages. Each segment is a contiguous block of virtual addresses representing a logical grouping of related memory, such as code, data, or stack. The operating system maintains a page table for each segment, and each page table maps a set of pages to physical pages of memory. This allows the operating system to translate a virtual address to a physical address using multiple levels of page tables, rather than a single, large page table.

Segmented paging can be particularly useful in non-contiguous memory allocation, as it allows the operating system to manage blocks of memory scattered throughout the address space more efficiently. It can also be used in concurrence with other memory management techniques, such as demand paging, to improve the production of the operating system.