Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Jun 21, 2024
Difficulty: Medium

Non-Contiguous Memory Allocation in OS

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Allocating space to computer programmes is referred to as memory allocation. Memory is a sizable collection of bytes. Contiguous and non-contiguous memory allocation are the two basic types of memory allocation. If we talk about non-contiguous memory allocation in OS, Depending on its needs, it enables a process to acquire several memory blocks in different parts of memory. Paging and segmentation are the techniques for making a process's physical address space non-contiguous. Non-contiguous memory allocation separates the operation into blocks (pages or segments), which are then assigned to various memory locations according to the amount of available memory.

non contiguous memory allocation in os

Memory management is the functionality of an Operating System that handles and manages primary memory and moves processes back and forth between main memory and disk during execution. 

Memory management keeps track of every single memory location, regardless of whether it is used by a process or not. It determines how much memory should be assigned to each process. It determines which processes will be given memory and when. It keeps track of when memory is freed or unallocated and updates the state accordingly.

Memory Allocation refers to the process of assigning sections of memory in a program (by the operating system), which is used to store variables, classes and instances of structures.

In this article, we’ll be discussing non-contiguous memory allocation in detail. 

Must Read, Internal and External Fragmentation.

What is Non-contiguous Memory Allocation?

Non-contiguous memory allocation is a memory allocation technique in which the different parts of a process are allocated to different places in the main memory.

In this type of memory allocation, a process can acquire several memory blocks at different locations in the memory according to its need. The available free space is distributed here and there, unlike contiguous memory allocation, where all the free space is allocated in one place.The execution of non-contiguous memory is slower than contiguous memory allocation.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Fundamental Approaches of Non-contiguous Memory Allocation

It includes segmentation and paging. There is no loss of memory in this allocation. The processes after swapping can be arranged in any location.

For example, a process having 3 segments, say, P1, P2, P3, will be allocated in contiguous memory blocks in the RAM like block 1 (-> P1), block 3 (-> P2), block 5 (-> P3).

Non-contiguous memory allocation

Paging

Paging is a storage method used in operating systems to recover processes from secondary storage into the main memory in the form of pages. The basic concept behind paging is to break each procedure into individual pages. The primary memory will be separated into frames as well.

One page of the process should be saved in one of the memory frames. The pages can be placed in various locations across the memory, but finding contiguous frames or holes is always the goal.

Process pages are only brought into the main memory when needed; otherwise, they are stored in secondary storage.

Frame sizes vary depending on the operating system. Each frame must have the same size. Because the pages in Paging are mapped to the frames, the page size must be the same as the frame size.

Paging

Example

One of the easiest techniques for paging is constructing the page table as a group of registers. The page table is retained in the main memory because the capacity of registers is restricted, while the size of the page table is generally huge.

This technique causes no external fragmentation since every frame that is free will be allocated to a process that requires it. Internal fragmentation, though, persists.

  • If a procedure necessitates ‘n’ pages, at least ‘n’ frames must be used.
  • The process's initial page is loaded into the first frame on the free-frame list, and the frame number is then entered into the page table.
Paging

 

The frame table is a Data Structure that stores information such as which frames are allocated or available and other information. Each physical page frame is represented by one entry in this table.

Free frames after allocation in paging

In the same manner that the operating system keeps a copy of the instruction counter and register contents for each process, it keeps a copy of the page table for each process. When the operating system manually maps a logical address to a physical address, this copy is also used to convert logical addresses to physical addresses.

When a process needs to be assigned to the CPU, the CPU dispatcher uses this copy to define the hardware page table.

Segmentation

Segmentation is a memory management method used in operating systems that divides memory into portions of varying sizes. Each component is referred to as a segment, and each segment can be assigned to a process.

A table called segment table stores information about each segment. One (or more) segments contain the segment table.

The segment table primarily comprises two pieces of information regarding the segment:

  1. Base: This is the segment's starting address.
  2. Limit: The segment's length is the limit. 
     

Why is Segmentation required?

We have been utilizing paging as our primary memory management approach up until now. Paging is more closely associated with the operating system than with the user. It splits all processes into pages, even though a process may contain certain related sections of functions that must be loaded on the same page.

The operating system is unconcerned about the user's perspective on the procedure. It may partition the same function into many pages, which may or may not be loaded into memory at the same time. The system's efficiency suffers as a result.

Segmentation, which separates the process into segments, is preferable. Each segment includes the same kind of functions. For example, the main function can be found in one segment and the library functions in the other.

Segmentation

Example:

The segmentation example is shown below, with five segments numbered from 0 to 4. As illustrated, these portions will be stored in physical memory. Each segment has its own entry in the segment table, which provides the segment's initial entry address in physical memory (referred to as the base) as well as the segment's length (denoted as limit).

segment's initial entry address in physical memory

 

Segment 2 starts at position 4300 and is 400 bytes long. As a result, a reference to byte 53 of segment 2 is mapped to position 4300 (4300+53=4353) in this scenario. 3200(the base of segment 3)+852=4052 is mapped to a reference to segment 3, byte 85.

Because this segment is 1000 bytes long, a reference to byte 1222 of segment 0 would result in a trap to the OS.

Segmentation with paging

Pure segmentation is not widely used and is not supported by many operating systems. However, segmentation and paging can be coupled to maximize the benefits of both strategies.

The primary memory is separated into variable-size segments, which are further divided into fixed-size pages in Segmented Paging.

  1. Pages are more compact than segments.
  2. Every programme contains many page tables since each segment has its own page table.
  3. Segment Number (base address), Page Number, and Page Offset are used to indicate the logical address.
     

Number of Segments: It directs you to the correct Segment Number.

Number of Pages: It directs you to the specific page inside the section.

Page Offset: It is a value that is used to offset the position of the page within the frame.

 

The varied information regarding each page of the segment is contained in each Page table. Every segment's information is contained in the Segment Table. Every page table entry is mapped to one of the pages inside a segment, and each segment table entry links to a page table item.

 segment table entry links to a page table item

Must Read -  Difference between Contiguous and Non-Contiguous Allocation.

Advantages of Non-Contiguous Memory Allocation

  • Efficient Use of Memory: Non-contiguous memory allocation allows for efficient use of available memory space because it can allocate memory in smaller, variable-sized chunks.
     
  • Flexibility: It provides flexibility in managing memory, enabling the system to allocate and deallocate memory blocks as needed, reducing wastage.
     
  • Virtual Memory: Non-contiguous allocation supports virtual memory systems, allowing processes to use more memory than is physically available by swapping data in and out of secondary storage.

Disadvantages of Non-Contiguous Memory Allocation

  • Fragmentation: It can suffer from both external and internal fragmentation, leading to inefficient memory usage and performance degradation over time.
     
  • Complexity: Managing non-contiguous memory allocation is more complex compared to contiguous allocation, requiring additional overhead for tracking memory blocks and their allocation status.
     
  • Overhead: It may introduce additional overhead due to page tables or segment tables required to map logical addresses to physical addresses.
     
  • Slower Access: Accessing non-contiguous memory locations may be slower compared to contiguous memory, as it involves multiple memory lookups and translations.

Frequently Asked Questions

What is non-contiguous memory allocation?

Non-contiguous memory allocation separates the operation into blocks (pages or segments), which are then assigned to various memory locations according to the amount of available memory.

Is segmentation contiguous or non-contiguous?

An OS mechanism for allocating non-contiguous memory is segmentation. Segmentation, as opposed to paging, breaks the process down into modules rather than fixed-size pages.

What is the contiguous memory allocation? 

Contiguous memory allocation is a method of managing memory in which, whenever a user process requests memory, one of the sections of the contiguous memory block is given to that process in accordance with its needs.

What is the difference between contiguous and continuous memory?

Contiguous memory refers to a block of memory locations that are physically adjacent and sequentially ordered. Continuous memory implies an uninterrupted sequence or flow of memory addresses, ensuring data can be accessed without interruption.

What is spanning in contiguous memory allocation?

Spanning in contiguous memory allocation refers to allocating memory segments that are not necessarily adjacent to each other but are logically connected to accommodate larger data structures or programs. This technique helps optimize memory usage while ensuring data integrity and efficient access.

Conclusion

This blog discussed the non-contiguous memory allocation in an operating system. In this type of memory allocation, a process can acquire several memory blocks at different locations in the memory according to its need. The available free space is distributed here and there, unlike contiguous memory allocation, where all the free space is allocated in one place.

Recommended Readings:


Check out some of the amazing Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingBasics of C, Basics of Java, etc. along with someTop OS interview QuestionsContests and Interview Experiences only on Coding Ninjas Studio

Topics covered
1.
Introduction
2.
What is Non-contiguous Memory Allocation?
3.
Fundamental Approaches of Non-contiguous Memory Allocation
3.1.
Paging
3.1.1.
Example
3.2.
Segmentation
3.2.1.
Why is Segmentation required?
3.2.2.
Example:
3.3.
Segmentation with paging
4.
Advantages of Non-Contiguous Memory Allocation
5.
Disadvantages of Non-Contiguous Memory Allocation
6.
Frequently Asked Questions
6.1.
What is non-contiguous memory allocation?
6.2.
Is segmentation contiguous or non-contiguous?
6.3.
What is the contiguous memory allocation? 
6.4.
What is the difference between contiguous and continuous memory?
6.5.
What is spanning in contiguous memory allocation?
7.
Conclusion