Memory Management Schemes – Non-Contiguous Memory Allocation

In the previous article, we’ve discussed about contiguous memory allocation and in this article, we’re going to learn about non-contiguous memory allocation.

Main Difference Between Contiguous Memory Allocation And Non-Contiguous Memory Allocation

Contiguous memory allocation	Non-contiguous memory allocation
In this method the main memory divided into same or different size of partitions and a program is divided into parts (if needed) and allocated to contiguous memory partitions.	In this method program is allocated to memory partitions in a non-contiguous manner. These partitions reside in several locations. Paging is an non-contiguous memory allocating technique.

How “Paging” (Non-Contiguous Memory Allocation) Provides Solution For The Problem – External Fragmentation?

Contiguous memory allocation technique causes external fragmentation.

Ex – consider a memory with 2KB, 4KB, 8KB, 15KB partitions.

These partitions are filled with P1=2KB, P2=2KB, P3=6KB, P4=10KB programs respectively.

Suppose after this process allocation P5 = 6KB needs to be loaded into the memory.

Although it has 9KB free space in the whole memory we there is no contiguous 6KB free slot.

Because of that, the program cannot be loaded into the memory and the free spaces inside other memory slots are wasted.

This problem caused by external defragmentation and the only solution for overcome from this problem is paging.

Paging is a non-contiguous memory allocation technique.

In this method the main memory is divided into small size partitions and one program is loaded into one or many partitions without a consecutive manner i.e. in a non-contiguous manner.

So, every partition can be used to store programs without fragmentation.

It uses page table to map the correct memory partition that holds the programs.

What Is Meant By A ‘Page’ And ‘Frame’ In Relation To Logical Address And Physical Address Of A Process?

In the paging mechanism the logical memory space is divided into same size partitions and they are called blocks or page.

Each page has its own address and it is called logical address.

Logical address contains 2 parts.

The first part is page number and the second part is page offset.

Logical memory is the memory that is created while executing the program.

The physical memory is also divided into same size partitions and have the same capacity as logical address partition.

This partition is called frame and each frame has its unique address which is called physical address.

The physical address also consists of 2 parts.

First part is frame number and the second part is frame offset.

The real data of the program is stored in the physical memory.

The Page Table

The page table is in the MMU and this is the table that maps each logical memory page to the correct physical memory frame.

Each process has its own page table.

Page table base register point to the page table and page-table length register show the length of the register.

Mapping Of ‘Page’ And ‘Frame’ In Address Translation

In mapping, the first logical address shows the “page 0” so it checks the 0th index of the frame table and get the corresponding frame number and locate that frame number in the physical memory.

It contains the real data that is needed to use in page 0 logical address.

When we consider the “page 2” it checks the 2nd index of page table and get the corresponding frame number for 2nd .

As the above picture, the number is 3.

So after that it is mapped to the 3rd frame of the physical memory.

Finally, the 3rd frame in the physical memory will contain the data that should be mapped to page 2.

Should The Size Of The “Page” And The Size Of The Corresponding ‘Frame’ Be Similar Or Different?

The size of a page and size of a frame should be same.

If not, there will an external fragmentation in the frames.

Because one page cannot fulfill the whole page and the rest of the space will be wasted.

Therefore the size should be the same.

What Is The Main Advantage Of Having TLB (Translation Look Aside Buffer) In Paging? What is the hit ratio of TLB?

In the paging mechanism, for each logical memory address that is generated from the CPU needs to find the correct physical memory address from the paging table.

But paging table is inside the main memory.

So the CPU has to access the main memory twice to get correct data in a logical address.

So there will be a huge drawback in the speed when using the paging mechanism.

TLB (translation look aside buffer) is a hardware component that stores a limited number of recent page table entries.

So, when the CPU looks for a page number, first it checks the TLB.

If the page number is found inside the TLB we say it is a “TLB hit”.

But if the page number is not found inside the TLB we say “TLB miss”.

If we miss the TLB the processor checks it again inside the main memory and copy that specific entry to the TLB.

So the next time when processor asks TLB can directly give the physical address without going to the main memory. This will reduce the drawback.

Page Number (p) & Page Offset (d)

Page Number: Page number is the index for the page table to find out the base address of each page in the main memory.

Page offset: Page offset shows the exact location of the word inside the frame. From the above figure, the location is n.

Frame Number (f) & Frame Offset (d)

Frame Number: This is the real base address in the physical memory frame. This is taken from the page table by referring the page number of the logical address.

Frame Offset: it shows the exact location of the word inside the frame. It is the same as Page Offset.

Question

Explain following figure with the knowledge you have gained so far.

Answer

When a process is being executed the CPU creates logical memory address and they are mapped to the real memory of the process in the Physical memory.

As the above diagram shows logical memory is consist with p (page number) and d (page offset).

First, The CPU checks the page number inside the TLB if the correct page number exists inside the TLB (“TLB hit” scenario).

Frame number of that is copied and make the physical address by combining it with the d (page offset).

But if the page number does not exist inside the TLB (“TLB miss” scenario) CPU checks it inside the page table that is in the main memory.

It uses p (page number) as the index for the page table and find the correct frame number inside that index.

After that it combines the d (page offset) with the frame number and makes the physical address of the corresponding logical address.

In a “TLB miss” scenario the used index and frame number copies to the TLB from the main memory for future references.

Conclusion

In this article, we covered the following topics under the Non-Contiguous Memory Allocation,

• Main Difference Between Contiguous Memory Allocation And Non-Contiguous Memory Allocation
• How “Paging” (Non-Contiguous Memory Allocation) Provides Solution For The Problem – External Fragmentation?
• What Is Meant By A ‘Page’ And ‘Frame’ In Relation To Logical Address And Physical Address Of A Process?
• The Page Table
• Mapping Of ‘Page’ And ‘Frame’ In Address Translation
• Should The Size Of The “Page” And The Size Of The Corresponding ‘Frame’ Be Similar Or Different?
• What Is The Main Advantage Of Having TLB (Translation Look Aside Buffer) In Paging? What is the hit ratio of TLB?
• Page Number (p) & Page Offset (d)
• Frame Number (f) & Frame Offset (d)

If you found this article helpful, let us know by adding a comment below and have a wonderful day! 😊