Fragmentation | Segmentation | Paging

1.  Logical versus Physical Address Space

An address generated by the CPU is commonly referred to as a logical address,
whereas an address seen by the memory unit-that is, the one loaded into the memory address register of the memory-is commonly referred to as a physical address. 

The compile-time and load-time address-binding methods generate identical logical and physical addresses. However, the execution-time address binding scheme results in differing logical and physical addresses. The set of all logical addresses space gen erated by a program is a logical the set of all physical
addresses corresponding to these logical addresses is a physical address space
Thus, in_ the execution-time address-binding scheme, the logical and physical
address spaces differ.

The run-time mapping from virtual to physical addresses is done by a
hardware device called the memory management unit (MMU). it does this by adding together thelogical address and the contents of the base register. The base register is now called a  relocation register. The user program never sees the real physical addresses.

2. Beladys Anomalies

In Operating System, process data is loaded in fixed sized chunks and each chunk is referred to as a page. The processor loads these pages in the fixed sized chunks of memory called frames. Typically the size of each page is always equal to the frame size.

A page fault occurs when a page is not found in the memory, and needs to be loaded from the disk. If a page fault occurs and all memory frames have been already allocated, then replacement of a page in memory is required on the request of a new page. This is referred to as demand-paging. The choice of which page to replace is specified by a page replacement algorithms. The commonly used page replacement algorithms are FIFO, LRU, optimal page replacement algorithms etc.

Generally, on increasing the number of frames to a process’ virtual memory, its execution becomes faster as less number of page faults occur. Sometimes the reverse happens, i.e. more number of page faults occur when more frames are allocated to a process. This most unexpected result is termed as Belady’s Anomaly.

Bélády’s anomaly is the name given to the phenomenon where increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern.

3. Fragmentation

Fragmentation occurs in a dynamic memory allocation system when most of the free blocks are too small to satisfy any request. It is generally termed as inability to use the available memory.

In such situation processes are loaded and removed from the memory. As a result of this, free holes exists to satisfy a request but is non contiguous i.e. the memory is fragmented into large no. Of small holes. This phenomenon is known as External Fragmentation.

Also, at times the physical memory is broken into fixed size blocks and memory is allocated in unit of block sizes. The memory allocated to a space may be slightly larger than the requested memory. The difference between allocated and required memory is known as Internal fragmentation i.e. the memory that is internal to a partition but is of no use.

One solution to the problem of external fragmentation is compaction.
The goal is to shuffle the memory contents so as to place all free n memory together
in one large block. Compaction is not always possible, however. If relocation
is static and is done at assembly or load time, compaction cannot be done;
compaction is possible only if relocation is dynamic and is done at execution time. When compaction is possible, we must determine its cost. The
simplest compaction algorithm is to move all processes toward one end of
memory; all holes move in the other direction, producing one large hole of
available memory. This scheme can be expensive.

Another possible solution to the external-fragmentation problem is to
permit the logical address space of the processes to be noncontiguous, thus
allowing a process to be allocated physical memory wherever such memory
is available.Two complementary techniques achieve this solution: paging and segmentation (. These techniques can also be combined.

Paging

A solution to fragmentation problem is Paging. Paging is a memory management mechanism that allows the physical address space of a process to be non-contagious. Here physical memory is divided into blocks of equal size called Pages. The pages belonging to a certain process are loaded into available memory frames.

 

Segmentation

Segmentation is another memory management scheme that supports the user-view of memory. Segmentation allows breaking of the virtual address space of a single process into segments that may be placed in non-contiguous areas of physical memory.

Segmentation with Paging

Both paging and segmentation have their advantages and disadvantages, it is better to combine these two schemes to improve on each. The combined scheme is known as 'Page the Elements'. Each segment in this scheme is divided into pages and each segment is maintained in a page table. So the logical address is divided into following 3 parts :

• Segment numbers(S)
• Page number (P)
• The displacement or offset number (D)