Memory Management

Quick link to: Overview of Operating System , Process Management , Memory Management , Storage Management

Table of Content
  1. Memory Management:
  2. Contiguous Memory Allocation: 
    1. Memory Allocation
    2. Memory Protection
  3. Swapping 
  4. Fragmentation
  5. Paging
  6. Basic method
  7. Hardware Support
  8. Protection
  9. Structure of the Page table
  10. Hierarchical Paging
  11. Hashed Page Tables
  12. Inverted Page Table
  13. Segmentation
  14. Basic Method
  15. Hardware
  16. Protection and Sharing
  17. Fragmentation
  18. Demand Paging: Basic Concepts.

Memory Management

The memory management can be done in two ways namely, contiguous and non-contiguous as shown in the figure.

Memory Management Techniques

Contiguous Memory Allocation

In contiguous memory allocation technique, memory is allocated continuously and no spanning is allowed. It means, if a process needs a 2MB space, then the process must be allocated to a partition which is 2MB or more in size. Basically there are two types in contiguous memory all0cation namely, fixed partition and dynamic partition.

Fixed partitioning (static partitioning)

In the fixed partitioning, the number of partitions are fixed and the size of each partition may or may not be same. As this is a contiguous technique, no spanning is allowed. Following is an example of fixed partitioning with 4 partitions. In the first case memory is divided in to different sizes such as 4MB, 8MB, and 16MB. In the second case all four partitions are divided equally ie., 8MB.

Example of fixed partitioning: Here, we will show 5 cases of fixed partitioning. Let us assume the memory is divided into four partitions of sizes 4MB, 8MB, 8MB, and 16MB and at the beginning of each case all memory spaces are free.

Case 1: Process P=4MB has arrived and it is allocated to the first partition.

Case 2: Process P=2MB has arrived and it is allocated to the first partition which is having maximum size of 4MB. So, in this case only 2MB is allocated and the remaining 2MB will be free but it cannot be allocated to any other process. This free space is called internal fragmentation.

Case 3: Process P=7MB has arrived and it is allocated to the second partition which is having maximum size of 8MB. Hence, 1MB will be left free creating an internal fragmentation.

Case 4: Process P=18MB has arrived. Memory cannot be allocated to the process as maximum size of a partition is 16MB and the process requires 18MB.

Case 5: The processes P2=7MB, P3=7MB, P4=14MB has arrived and they are allocated to the second, third, and fourth partition respectively. As the image shows, case 5 has created 3 internal fragmentation (1MB, 1MB, and 2MB) and also a free space of 4MB is available in the first partition. Now if a process P5=6MB has arrived, if we count then the total amount of memory available is 8MB (4MB in the internal fragmentation and 4MB free space in the first partition). But still we cannot allocate this available 8MB to process P5 as this memory is not contiguous. This is called as external fragmentation.

Dynamic Partitioning or Variable Partitioning

In dynamic partitioning, the memory is not divided in advance like fixed partitioning. Instead whenever a process arrives, exact amount of memory required by the process is allocated to the process.

Advantages of dynamic partitioning are:

  • As the exact amount of memory is allocated, there will be no internal fragmentation and also there is no limit on process size.
  • As the memory is not divided in advance, there is no limitation on number of process to be allocated in the memory.

Disadvantages of dynamic partitioning are:

  • There is a possibility of external fragmentation. One solution to avoid external fragmentation is to use compression. Compression is a technique in which all process are first copied to a memory location and then again they are copied to main memory to a continuous location removing all free space created between them. But compression technique is not desirable as it needs processes to halt their executing and then copying from one location to another and again back to memory takes a lot of time.
  • The allocation and freeing is very complex.

Example: Let us say five processes P1=2MB, P2=4MB, P3=8MB, P4=4MB, and P5=8MB arrives. As the process arrives, memory is allocated exactly the amount of memory is required as shown in the below image 1. Suppose after sometime the process P2 and P4 complete their task and free the space occupied as shown in image 2. Now if a new process P6=8MB arrives, no memory will be allocated to the process P6 because them 8MB memory available is not continuous. This is called a external fragmentation.

Memory Allocation

Memory can be allocated in four ways namely, first fit, next fit, best fit, and worst fit.

First fit: In the first fit, first free space which is big enough to accommodate will be allocated to the process. First fit is very simple and very fast but there is a possibility of creating an internal fragmentation.

Next fit: Next is similar to first fit but only difference being the search for the free space will start from the last allocated location. Next fit is little faster than first fit.

Best fit: Best fit uses linear search technique. First all available free space is searched, then the smallest memory which is big enough to accommodate the process is allocated to the process.

In best fit, little or less internal fragmentation happens. Having said that, in best fit, small or tiny internal fragmentations are created. As in the best fit entire memory is searched, this method becomes very slow.

Worst fit: Worst fit uses linear search technique. First all available free space is searched, then the biggest memory which is big enough to accommodate the process is allocated to the process.

In worst fit, big size internal fragmentation happens which can accommodate more processes. As in the worst fit entire memory is searched, this method becomes very slow.

Swapping

Table of Content

Any process which needs to be executed should be kept in main memory. However, if the process in the main memory is not getting executed for some reason such as waiting for an event to occur or waiting for an IO, then such process can be moved back to backing store (swap out) and any process in the backing store which is ready to be executed can be loaded into the main memory (swap in). This process of swapping-out and swapping-in of processes between main memory and backing store in order to reduce the CPU idle time is called as swapping.

The backing stores are usually a fast disk. These backing stores should be big enough to accommodate all the copies of memory images for all users. And also backing stores must provide direct access to the memory images.

A ready queue is maintained by the system. This ready queue consists of any process which is ready to run. Memory images of these process could be either in the backing store or in the main memory.

A dispatcher is called when CPU scheduler decides to execute a process. The main job of the dispatcher is to ensure the next process in the ready queue is in the main memory. Suppose the process is not in the memory then the dispatcher will look for a free space in the main memory to load the process in the available space. Suppose if the space is not available then the dispatcher swap-out a process which is currently in the memory and swap-in the desired process. And then reloads the registers and transfer the control to the selected process.