The main memory must accommodate both the operating system and various user processes. The operating system is placed in either low memory or high memory. It is common to place the operating system in low memory. Consider the below figure.
There are so many methods available for memory allocation. We are going to discuss these methods in detail.
- Single Partition Allocation
- Multiple Partitions Memory Management
- Compaction
- Paging
- Segmentation
- Segmentation with Paging
1. Single Partition Allocation
In this memory allocation method, the operating system resides in the low memory, and the remaining memory is treated as a single partition. This single partition is available for user space and only one job can be loaded in this user space. The below figure depicts the single partition allocation.
The short-term scheduler (CPU scheduler) selects a job from the ready queue for execution. Then the dispatcher loads that job into the main memory and connects the CPU to that job. The main memory consists of only one process at a time because the user space is treated as a single partition.
Advantages
- The main advantage of this scheme is its simplicity. It does not require great expertise to understand.
Disadvantages
- The memory is not utilized fully.
- A lot of memory will waste in this scheme.
- Poor utilization of processors (waiting for I/O)
- The user’s job is limited to the size of the available main memory.
- Poor utilization of memory.
2. Multiple Partition Memory Management
This method can be implemented in 3 ways. These are
- Fixed Equal Multiple Partitions Memory Management.
- Fixed Variable Multiple Partitions Memory Management.
- Dynamic Multiple Partitions Memory Management.
A. Fixed Equal Multiple Partitions Memory Management
In this memory management scheme, the operating system occupies the low memory, and the rest of the main memory is available for user space. The user space is divided into fixed partitions. The partition sizes are depending on the operating system.
For example, the total size of the main memory is 6 MB, and 1 MB is occupied by the operating system. The remaining 5 MB is partitioned into 5 equal fixed partitions (5X1 MB), J1, J2, J3, J4, and J5 are the 5 jobs to be loaded into main memory, these sizes are:
| Job | Size |
|---|---|
| J1 | 450 KB |
| J2 | 1000 KB |
| J3 | 1024 KB |
| J4 | 1500 KB |
| J5 | 500 KB |
Internal and External Fragmentation:
Job 1 is loaded into partition 1. The maximum size of partition 1 is 1024 KB. The size of J1 is 450 KB. So, 1024 – 450 = 574 KB of space wasted, this wasted memory is said to be Internal fragmentation. But there is not enough to load Job 4. Because the size of Job 4 is greater than all partitions, the entire partition (that is partition 5) was wasted. This wasted memory is said to be External fragmentation.
Therefore, the total internal fragmentation is:
= (1024 - 450) + (1024 - 1000) + (1024 - 500)
= 574 + 24 + 524
= 1122 KB
The external fragmentation for this scheme is = 1024 KBAdvantages
- This scheme supports multi-programming.
- The processor and I/O devices are efficiently utilized.
- It requires no special costly hardware.
- Simple and easy to implement.
Disadvantages
- This scheme suffers from internal as well as external fragmentation.
- The single free area may not be large enough for a partition.
- It does require more memory than a single partition method.
- A job’s partition size is limited to the size of physical memory.
B. Fixed Variable Partitions Memory Management
In this scheme, the user space of the main memory is divided into a number of partitions, but the partition sizes are different in length. The operating system keeps a table indicating which partitions of memory are available and which are occupied. When a process arrives and needs memory, we search for a partition large enough for this process. If we find one then we allocate the partition to that process.
Partitions P1, P2, P5, and P6 are totally free, there are no processes in these partitions. This wasted memory is said to be external fragmentation.
The total external fragmentation is (400 + 350 + 625) = 1375.
The total internal fragmentation is (700-600) + (525-450) + (900-825) = 250.
First Fit: Allocate the partition that is big enough. Searching can start either from low memory or high memory, we can stop searching as soon as we find a free partition that is large enough.
Best Fit: Allocate the smallest partition that is big enough (or) select a partition, which has the least internal fragmentation.
Worst-Fit: Search the entire partitions and select a partition that is the largest of all. Or select a partition that had the maximum internal fragmentation.
Advantages
- This scheme supports multiprogramming.
- Efficient processor utilization and memory utilization are possible.
- Simple and easy to implement.
Disadvantages
- This scheme is suffering from internal and external fragmentation.
- Possible for large external fragmentation.
C. Dynamic Partitions Memory Management
To eliminate some of the problems with fixed partitions, an approach known as Dynamic partitioning was developed. In this method, partitions are created dynamically so that each process is loaded into a partition of exactly the same size as that process. In this scheme, the entire user space is treated as a Big hole. The boundaries of partitions are dynamically changed, and the boundaries are depended on the size of the processes.
Advantages
- In this scheme, partitions are changed dynamically. So that scheme doesn’t suffer from internal fragmentation.
- Efficient memory and processor utilization.
Disadvantages
- This scheme suffers from external fragmentation.
3. Compaction
Compaction is a technique of collecting all the free spaces together in one block, this block or partition can be allotted to some other jobs. For example, consider the figure, it is the memory allocation figure.
The total internal fragmentation in this scheme is (100 + 75 + 75 = 250). The total external fragmentation is 400 + 350 + 625 = 1375 KB. Collect the internal and external fragmentation together in one block (250 + 1375 = 1625 KB). This type of mechanism is said to be Compaction. After applying this scheme, the compacted memory is 1625 KB.
4. Paging
Paging is an efficient memory management scheme because it is a non-contiguous memory allocation method. The previous (Single partition, Multiple partitions) methods support the continuous memory allocation, the entire process loaded in the same partition. But in the paging the process is divided into small parts, these are loaded elsewhere in the main memory.
The basic idea of paging is the physical memory (main memory) is divided into fixed-sized blocks called Frames. The logical address space (user job) is divided into fixed-sized blocks called Pages. But the page size and frame size should be equal. The size of the frame or a page is depending on the operating system Generally the page size is 4KB
In this scheme, the operating system maintains a data structure, that is page table and it is used for mapping purposes. The page table specifies some useful information like it tells which frames are allocated, which frames are available, how many total frames are there, and so on. The general page table consists of two fields, one is page number and another one is frame number. Each operating system has its own methods for storing page tables, most allocate a page table for each process.
Advantages
- It supports the time-sharing system.
- It does not affect fragmentation.
- It supports virtual memory.
- Sharing of common code is possible.
Disadvantages
- This scheme may suffer Page breaks. For example, the logical addressee space is 17KB, and the page size is 4 KB. So, this job requires 5 frames. But the fifth frame consists of only 1 KB. So, the remaining 3 KB is wasted, it is said to be page breaks.
- If the number of pages is high, it is difficult to maintain page tables.
5. Segmentation
A segment can be defined as a logical grouping of instructions such as a subroutine, array, or data area. Every program (job) is a collection of these segments. Segmentation is the technique for managing these segments. For example, consider the figure.
Each segment has a name and length. The address of the segment specifies both the segment name and offset within the segment. The operating system searches the entire main memory for free space to load segments. This mapping is done by segment table. The segment table is a table where each entry of the segment table has a segment Base and a segment Limit.
The segment Base contains the starting physical address where the segment resides in the main memory. The segment limit specifies the length of the segment. The Limit specifies the size of the segment. The Base specifies starting address of the segment. For example, segment 0 loaded in main memory from 1500KB to 2500KB, so 1500KB is the base and 2500-1500 = 1000KB is the limit.
Advantages of Segmentation
- Eliminate fragmentation: By moving a segment around, fragmented memory space can be combined into a single free area.
- Segmentation supports virtual memory.
- Allow dynamically growing segments.
- Facilitate shared segments.
- Dynamic linking and loading of the segments
6. Segmentation with paging
Both paging and segmentation have their advantages and disadvantages. It is better possible to combine these two schemes to improve on each. The combined scheme was Page the segments. Each segment in this scheme is divided into pages, and each segment maintains a page table. So, the logical address is divided into 3 parts. First is the segment number (S), the second is the page number(P), and another is displacement (or) offset(D). For a better understanding consider the below figure.
The logical address space is divided into 3 segments numbered 0 to 2. Each segment maintains a page table, and the mapping between the page and frame is done by the page table. For example, frame number 8 shows the address (1, 3), 1 stands for the segment number, and 3 stands for the page number. The main advantage of this scheme is to avoid fragmentation, and it supports the user view of memory.
Protection
The word protection means security from unauthorized references from the main memory. To provide protection the operating system follows different types of mechanisms. In a paging memory management scheme, the operating system provides protection bits that are associated with each frame. Generally, these bits are kept in the page table. Sometimes these bits are said to be valid/not valid bits.
