Memory Management

                       Memory Management

Memory management is the functionality of an operating system which handles or manages primary memory and moves processes back and forth between main memory and disk during execution. Memory management keeps track of each and every memory location, regardless of either it is allocated to some process or it is free. It checks how much memory is to be allocated to processes. It decides which process will get memory at what time. It tracks whenever some memory gets freed or unallocated and correspondingly it updates the status.

This tutorial will teach you basic concepts related to Memory Management.

Process Address Space

The process address space is the set of logical addresses that a process references in its code. For example, when 32-bit addressing is in use, addresses can range from 0 to 0x7fffffff; that is, 2^31 possible numbers, for a total theoretical size of 2 gigabytes.

The operating system takes care of mapping the logical addresses to physical addresses at the time of memory allocation to the program. There are three types of addresses used in a program before and after memory is allocated −

S.N.	Memory Addresses & Description
1	Symbolic addresses The addresses used in a source code. The variable names, constants, and instruction labels are the basic elements of the symbolic address space.
2	Relative addresses At the time of compilation, a compiler converts symbolic addresses into relative addresses.
3	Physical addresses The loader generates these addresses at the time when a program is loaded into main memory.

Virtual and physical addresses are the same in compile-time and load-time address-binding schemes. Virtual and physical addresses differ in execution-time address-binding scheme.

The set of all logical addresses generated by a program is referred to as a logical address space. The set of all physical addresses corresponding to these logical addresses is referred to as a physical address space.

The runtime mapping from virtual to physical address is done by the memory management unit (MMU) which is a hardware device. MMU uses following mechanism to convert virtual address to physical address.

• The value in the base register is added to every address generated by a user process, which is treated as offset at the time it is sent to memory. For example, if the base register value is 10000, then an attempt by the user to use address location 100 will be dynamically reallocated to location 10100.
• The user program deals with virtual addresses; it never sees the real physical addresses.

logical Address

 A logical address also referred to as a virtual address, is an address of something generated by the central processing unit (CPU) while a program is running.  Usually, the operating system or some other programs uses base addresses as a measure to find addresses. In this case the base address refers to the starting address of a memory block. In regard to the written program, the CPU generates an address; the very address is added with the base address so that it forms the physical address. In this case, the address generated by the CPU is referred to as Logical address.

The logical address is mapped to its correlating physical address by the memory management unit. Logical address usually ranges from zero to maximum. Load-time and compile-time address binding methods are used to create identical logical address and physical address.

Logical Address System

Physical Address

Physical address is a location that exists in the memory; it allows accessing a particular storage cell in the main memory.  It is used by both hardware and software for accessing data. Software however, does not use physical addresses directly instead, it accesses memory using a virtual address. A hardware component referred to as the Memory Management Unit (MMU) is responsible for translating a virtual address to a physical address.

The physical address is not directly accessible or viewed by the user program hence a logical address needs to be mapped to it to make it accessible with the aid of pointers which reveal location but not the code.

• 

The Difference

1. Logical address is the address that is generated by the central processing unit (CPU) in perspective of a program. Logical address can also be referred to as a virtual address. Physical address on the other hand is a location that exists in the memory; it allows accessing a particular storage cell in the main memory.
2. Logical address space is the set of all logical addresses generated by CPU for a program whereas physical address space is the set of all physical address mapped to corresponding logical addresses.
3. The physical address is an accessible physical location existing within the memory whereas the logical address exist virtually and does not have a specific location to exist physically in memory unit hence it is also known as virtual address.
4. The logical address is generated by the central processing unit (CPU) whereas physical address is computed by Memory Management Unit (MMU). MMU is a hardware device that maps virtual to physical address.
5. Physical and logical addresses are same in compile-time and load-time addressing-binding schemes. The two only differ in the execution-time address-binding scheme.
6. The physical address helps to identify a location in the main memory whereas the logical address helps to obtain the physical address.
7. The logical address is flexible hence will keep changing with the system but the physical address of that object always remains constant. This explains why the logical address gets formatted when the system is rebooted while no change happens to the physical address.
8. The user can use the logical address to access the physical address whereas the user can indirectly access physical address but not directly.

Contiguous memory allocation

In contiguous memory allocation, all the available memory space remain together in one place. It means freely available memory partitions are not scattered here and there across the whole memory space.

In the contiguous memory allocation, both the operating system and the user must reside in the main memory. The main memory is divided into two portions one portion is for the operating and other is for the user program.

In the contiguous memory allocation when any user process request for the memory a single section of the contiguous memory block is given to that process according to its need. We can achieve contiguous memory allocation by dividing memory into the fixed-sized partition.

A single process is allocated in that fixed sized single partition. But this will increase the degree of multiprogramming means more than one process in the main memory that bounds the number of fixed partition done in memory. Internal fragmentation increases because of the contiguous memory allocation.

→ Fixed sized partition

In the fixed sized partition the system divides memory into fixed size partition (may or may not be of the same size) here entire partition is allowed to a process and if there is some wastage inside the partition is allocated to a process and if there is some wastage inside the partition then it is called internal fragmentation.

Advantage: Management or book keeping is easy.

Disadvantage: Internal fragmentation

→ Variable size partition

In the variable size partition, the memory is treated as one unit and space allocated to a process is exactly the same as required and the leftover space can be reused again.

Advantage: There is no internal fragmentation.

Disadvantage: Management is very difficult as memory is becoming purely fragmented after some time.

Fixed and Variable partition

There are two Memory Management Techniques: Contiguous, and Non-Contiguous. In Contiguous Technique, executing process must be loaded entirely in main-memory. Contiguous Technique can be divided into:

1. Fixed (or static) partitioning
2. Variable (or dynamic) partitioning

1. Fixed Partitioning:
This is the oldest and simplest technique used to put more than one processes in the main memory. In this partitioning, number of partitions (non-overlapping) in RAM are fixed but size of each partition may or may not be same. As it is contiguous allocation, hence no spanning is allowed. Here partition are made before execution or during system configure.

As illustrated in above figure, first process is only consuming 1MB out of 4MB in the main memory.
Hence, Internal Fragmentation in first block is (4-1) = 3MB.
Sum of Internal Fragmentation in every block = (4-1)+(8-7)+(8-7)+(16-14)= 3+1+1+2 = 7MB.

Suppose process P5 of size 7MB comes. But this process cannot be accommodated inspite of available free space because of contiguous allocation (as spanning is not allowed). Hence, 7MB becomes part of External Fragmentation.

There are some advantages and disadvantages of fixed partitioning.

Advantages of Fixed Partitioning –

1. Easy to implement:
   Algorithms needed to implement Fixed Partitioning are easy to implement. It simply requires putting a process into certain partition without focussing on the emergence of Internal and External Fragmentation.
2. Little OS overhead:
   Processing of Fixed Partitioning require lesser excess and indirect computational power.

Disadvantages of Fixed Partitioning –

1. Internal Fragmentation:
   Main memory use is inefficient. Any program, no matter how small, occupies an entire partition. This can cause internal fragmentation.
2. External Fragmentation:
   The total unused space (as stated above) of various partitions cannot be used to load the processes even though there is space available but not in the contiguous form (as spanning is not allowed).
3. Limit process size:
   Process of size greater than size of partition in Main Memory cannot be accommodated. Partition size cannot be varied according to the size of incoming process’s size. Hence, process size of 32MB in above stated example is invalid.
4. Limitation on Degree of Multiprogramming:
   Partition in Main Memory are made before execution or during system configure. Main Memory is divided into fixed number of partition. Suppose if there are  partitions in RAM and  are the number of processes, then  condition must be fulfilled. Number of processes greater than number of partitions in RAM is invalid in Fixed Partitioning.

2. Variable Partitioning –
It is a part of Contiguous allocation technique. It is used to alleviate the problem faced by Fixed Partitioning. In contrast with fixed partitioning, partitions are not made before the execution or during system configure. Various features associated with variable Partitioning-

1. Initially RAM is empty and partitions are made during the run-time according to process’s need instead of partitioning during system configure.
2. The size of partition will be equal to incoming process.
3. The partition size varies according to the need of the process so that the internal fragmentation can be avoided to ensure efficient utilisation of RAM.
4. Number of partitions in RAM is not fixed and depends on the number of incoming process and Main Memory’s size.

There are some advantages and disadvantages of variable partitioning over fixed partitioning as given below.

Advantages of Variable Partitioning –

1. No Internal Fragmentation:
   In variable Partitioning, space in main memory is allocated strictly according to the need of process, hence there is no case of internal fragmentation. There will be no unused space left in the partition.
2. No restriction on Degree of Multiprogramming:
   More number of processes can be accommodated due to absence of internal fragmentation. A process can be loaded until the memory is not empty.
3. No Limitation on the size of the process:
   In Fixed partitioning, the process with the size greater than the size of the largest partition could not be loaded and process can not be divided as it is invalid in contiguous allocation technique. Here, In variable partitioning, the process size can’t be restricted since the partition size is decided according to the process size.

Disadvantages of Variable Partitioning –

1. Difficult Implementation:
   Implementing variable Partitioning is difficult as compared to Fixed Partitioning as it involves allocation of memory during run-time rather than during system configure.
2. External Fragmentation:
   There will be external fragmentation inspite of absence of internal fragmentation.
   For example, suppose in above example- process P1(2MB) and process P3(1MB) completed their execution. Hence two spaces are left i.e. 2MB and 1MB. Let’s suppose process P5 of size 3MB comes. The empty space in memory cannot be allocated as no spanning is allowed in contiguous allocation. The rule says that process must be contiguously present in main memory to get executed. Hence it results in External Fragmentation.
   
   Now P5 of size 3 MB cannot be accommodated in spite of required available space because in contiguous no spanning is allowed.

Internal and External fragmentation

Comparison Chart

BASIS FOR COMPARISON	INTERNAL FRAGMENTATION	EXTERNAL FRAGMENTATION
Basic	It occurs when fixed sized memory blocks are allocated to the processes.	It occurs when variable size memory space are allocated to the processes dynamically.
Occurrence	When the memory assigned to the process is slightly larger than the memory requested by the process this creates free space in the allocated block causing internal fragmentation.	When the process is removed from the memory, it creates the free space in the memory causing external fragmentation.
Solution	The memory must be partitioned into variable sized blocks and assign the best fit block to the process.	Compaction, paging and segmentation.

Definition of Internal Fragmentation

Internal fragmentation occurs when the memory is divided into fixed sized blocks. Whenever a process request for the memory, the fixed sized block is allocated to the process. In case the memory assigned to the process is somewhat larger than the memory requested, then the difference between assigned and requested memory is the Internal fragmentation.

This leftover space inside the fixed sized block can not be allocated to any process as it would not be sufficient to satisfy the request of memory by the process. Let us understand Internal fragmentation with the help of an example. The memory space is partitioned into the fixed-sized blocks of 18,464 bytes. Let us say a process request for 18,460 bytes and partitioned fixed-sized block of 18,464 bytes is allocated to the process. The result is 4 bytes of 18,464 bytes remained empty which is the internal fragmentation.

The overhead of keeping track of the internals hole created due to internal fragmentation is substantially more than the number of internal holes. The problem of internal fragmentation can be solved by partitioning the memory into the variable sized block and assign the best-sized block to a process requesting for the memory. Still, it will not totally eliminate the problem of internal fragmentation but will reduce it to some extent.

Definition of External Fragmentation

External fragmentation occurs when there is a sufficient amount of space in the memory to satisfy the memory request of a process. But the process’s memory request can not be satisfied as the memory available is in a non-contiguous manner. Either you apply first-fit or best-fit memory allocation strategy it will cause external fragmentation.

When a process is loaded and removed from the memory the free space creates the hole in the memory space, and there are many such holes in the memory space, this is called External fragmentation. Although the first fit and best fit can affect the amount of external fragmentation, it can not be totally eliminated. Compaction may be the solution for external fragmentation.

Paging

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. This scheme permits the physical address space of a process to be non – contiguous.

• Logical Address or Virtual Address (represented in bits): An address generated by the CPU
• Logical Address Space or Virtual Address Space( represented in words or bytes): The set of all logical addresses generated by a program
• Physical Address (represented in bits): An address actually available on memory unit
• Physical Address Space (represented in words or bytes): The set of all physical addresses corresponding to the logical addresses

Example:

• If Logical Address = 31 bit, then Logical Address Space = 2³¹ words = 2 G words (1 G = 2³⁰)
• If Logical Address Space = 128 M words = 2⁷ * 2²⁰ words, then Logical Address = log₂ 2²⁷ = 27 bits
• If Physical Address = 22 bit, then Physical Address Space = 2²² words = 4 M words (1 M = 2²⁰)
• If Physical Address Space = 16 M words = 2⁴ * 2²⁰ words, then Physical Address = log₂ 2²⁴ = 24 bits

The mapping from virtual to physical address is done by the memory management unit (MMU) which is a hardware device and this mapping is known as paging technique.

• The Physical Address Space is conceptually divided into a number of fixed-size blocks, called frames.
• The Logical address Space is also splitted into fixed-size blocks, called pages.
• Page Size = Frame Size

Let us consider an example:

• Physical Address = 12 bits, then Physical Address Space = 4 K words
• Logical Address = 13 bits, then Logical Address Space = 8 K words
• Page size = frame size = 1 K words (assumption)

Address generated by CPU is divided into

• Page number(p): Number of bits required to represent the pages in Logical Address Space or Page number
• Page offset(d): Number of bits required to represent particular word in a page or page size of Logical Address Space or word number of a page or page offset.

Physical Address is divided into

• Frame number(f): Number of bits required to represent the frame of Physical Address Space or Frame number.
• Frame offset(d): Number of bits required to represent particular word in a frame or frame size of Physical Address Space or word number of a frame or frame offset.

The hardware implementation of page table can be done by using dedicated registers. But the usage of register for the page table is satisfactory only if page table is small. If page table contain large number of entries then we can use TLB(translation Look-aside buffer), a special, small, fast look up hardware cache.

Paged Allocation

Paged allocation in memory management divides computer physical memory (Random Access Memory – RAM) into fixed size of memory units called page frames (memory block size). Also divides virtual address space to size of the pages. The main advantage of using paged allocation is, an empty page frame can be used by any job however, need to keep track of number of pages and where the pages of individual job are located in memory. In other words memory can be used efficiently and each job runs on its own address space.

Example

From the above figure, the size of each page is 100 memory locations. The memory utilized by the process1 in the above given figure is 350 memory locations where it takes 4 pages to store 350 memory locations. That is, in memory block 0 or page 0 holds first 100 memory locations of data. In second page, memory locations of 100 to 199 are stored and so on.

Steps to determine exact location of the instruction or code line

• Find the page number and displacement.

• Determine memory block size which contains required page.

• Obtain the address of beginning of the first memory block.

• Add the displacement to starting address of memory blocks if the required page is in other than page 0.

When the system moves required pages from main memory to secondary memory it gives rise to demand paging, in other words, moving only the required page to physical memory.

Protection and Sharing

1. Protection – There is always a danger when we have multiple programs at the same time as one program may write to the address space of another program. So every process must be protected against unwanted interference when other process tries to write in a process whether accidental or incidental. Between relocation and protection requirement a trade-off occurs as the satisfaction of relocation requirement increases the difficulty of satisfying the protection requirement Prediction of the location of a program in main memory is not possible, that’s why it is impossible to check the absolute address at compile time to assure protection. Most of the programming language allows the dynamic calculation of address at run time. The memory protection requirement must be satisfied by the processor rather than the operating system because the operating system can hardly control a process when it occupies the processor. Thus it is possible to check the validity of memory references.
2. Sharing – A protection mechanism must have to allow several processes to access the same portion of main memory. Allowing each processes access to the same copy of the program rather than have their own separate copy has an advantage.
   
   For example, multiple processes may use the same system file and it is natural to load one copy of the file in main memory and let it shared by those processes. It is the task of Memory management to allow controlled access to the shared areas of memory without compromising the protection. Mechanisms are used to support relocation supported sharing capabilities.

Advantages and Disadvantages of Paging.

Advantages :

Allocating memory is easy and cheap

Any free page is ok, OS can take first one out of list it keeps

Eliminates external fragmentation

Data (page frames) can be scattered all over PM

Pages are mapped appropriately anyway

Allows demand paging and prepaging

More efficient swapping

No need for considerations about fragmentation

Just swap out page least likely to be used

Disadvantages :

Longer memory access times (page table lookup)

Can be improved using TLB

Guarded page tables

Inverted page tables

Memory requirements (one entry per VM page)

Improve using Multilevel page tables and variable page sizes (super-pages)

Guarded page tables

Page Table Length Register (PTLR) to limit virtual memory size

Internal fragments