Notes: Segmentation | Operating System - Computer Science Engineering (CSE) PDF Download

Non-Contiguous Allocation in Operating System

Paging and Segmentation are the two ways which allow a process’s physical address space to be non-contiguous. It has advantage of reducing memory wastage but it increases the overheads due to address translation. It slows the execution of the memory because time is consumed in address translation.
In non-contiguous allocation, Operating system needs to maintain the table which is called Page Table for each process which contains the base address of the each block which is acquired by the process in memory space. In non-contiguous memory allocation, different parts of a process is allocated different places in Main Memory. Spanning is allowed which is not possible in other techniques like Dynamic or Static Contiguous memory allocation. That’s why paging is needed to ensure effective memory allocation. Paging is done to remove External Fragmentation. 

Working 

Here a process can be spanned across different spaces in main memory in non-consecutive manner. Suppose process P of size 4KB. Consider main memory have two empty slots each of size 2KB. Hence total free space is, 2*2= 4 KB. In contiguous memory allocation, process P cannot be accommodated as spanning is not allowed.
In contiguous allocation, space in memory should be allocated to whole process. If not, then that space remains unallocated. But in Non-Contiguous allocation, process can be divided into different parts and hence filling the space in main memory. In this example, process P can be divided into two parts of equal size – 2KB. Hence one part of process P can be allocated to first 2KB space of main memory and other part of process P can be allocated to second 2KB space of main memory. Below diagram will explain in better way: 

But, in what manner we divide a process to allocate them into main memory is very important to understand. Process is divided after analysing the number of empty spaces and their size in main memory. Then only we divide our process. It is very time consuming process. Their number as well as their sizes changing every time due to execution of already present processes in main memory.
In order to avoid this time consuming process, we divide our process in secondary memory in advance before reaching the main memory for its execution. Every process is divided into various parts of equal size called Pages. We also divide our main memory into different parts of equal size called Frames. It is important to understand that:
Size of page in process
= Size of frame in memory
Although their numbers can be different. Below diagram will make you understand in better way: consider empty main memory having size of each frame is 2 KB, and two processes P1 and P2 are 2 KB each. 

Resolvent main memory, 

In conclusion we can say that, Paging allows memory address space of a process to be non-contiguous. Paging is more flexible as only pages of a process are moved. It allows more processes to reside in main memory than Contiguous memory allocation.

Segmentation in Operating System

A process is divided into Segments. The chunks that a program is divided into which are not necessarily all of the same sizes are called segments. Segmentation gives user’s view of the process which paging does not give. Here the user’s view is mapped to physical memory.

There are types of segmentation:

1. Virtual memory segmentation:
   Each process is divided into a number of segments, not all of which are resident at any one point in time.
2. Simple segmentation: 
   Each process is divided into a number of segments, all of which are loaded into memory at run time, though not necessarily contiguously.

There is no simple relationship between logical addresses and physical addresses in segmentation. A table stores the information about all such segments and is called Segment Table.

Segment Table: It maps two-dimensional Logical address into one-dimensional Physical address. It’s each table entry has:

• Base Address: It contains the starting physical address where the segments reside in memory.
• Limit: It specifies the length of the segment.

Translation of Two dimensional Logical Address to one dimensional Physical Address.

Address generated by the CPU is divided into:

• Segment number (s): Number of bits required to represent the segment.
• Segment offset (d): Number of bits required to represent the size of the segment.

Advantages of Segmentation:

• No Internal fragmentation.
• Segment Table consumes less space in comparison to Page table in paging.

Disadvantage of Segmentation: 

• As processes are loaded and removed from the memory, the free memory space is broken into little pieces, causing External fragmentation.