Describe various space allocation strategies with their merits/demerits.

Introduction

Space allocation strategies in operating systems are the methods used by the operating system to allocate memory space to the processes in the main memory. The main goal of these strategies is to efficiently use the available memory space and minimize the time taken to allocate and deallocate memory to the processes. There are several strategies used for space allocation, including Contiguous Allocation, Non-Contiguous Allocation, Paging, and Segmentation.

Contiguous Allocation

Contiguous Allocation is a memory allocation strategy where each process is allocated in a single contiguous block of memory. The operating system maintains a base register and a limit register for each process. The base register holds the smallest physical address while the limit register specifies the size of the range.

Formula: If the base register value is B and the limit register value is L, then the process can access memory from location B to B+L.

Merits: This method is simple to implement and efficient in terms of speed as the entire process is located in a single continuous memory block.

Demerits: It suffers from external fragmentation, where free memory is divided into small blocks scattered throughout the system. Also, the size of the process needs to be known in advance.

Example: MS-DOS uses contiguous allocation.

Non-Contiguous Allocation

Non-Contiguous Allocation allows a process to be allocated in several memory spaces. This strategy solves the problem of external fragmentation and allows dynamic memory allocation.

Merits: It solves the problem of external fragmentation and the size of the process doesn't need to be known in advance.

Demerits: It is more complex to implement and slower than contiguous allocation due to the overhead of managing multiple memory blocks.

Example: Modern operating systems like Windows, Linux, etc., use non-contiguous allocation.

Paging

Paging is a memory management scheme that allows physical address space of a process to be noncontiguous. The memory is divided into fixed-size blocks called pages.

Formula: The operating system maintains a page table for each process, which is used to translate logical addresses to physical addresses.

Merits: It solves the problem of external fragmentation and allows the physical address space of a process to be noncontiguous.

Demerits: There is an overhead of maintaining page tables. It also suffers from internal fragmentation as the last page may not be fully used.

Example: Most modern operating systems use paging.

Segmentation

Segmentation is a memory management scheme that divides the memory into variable-sized blocks known as segments. Each segment can be allocated to a process.

Formula: The operating system maintains a segment table for each process, which is used to translate logical addresses to physical addresses.

Merits: It allows memory to be allocated in a way that matches the logical structure of a program, making it easier to grow and shrink structures.

Demerits: It suffers from external fragmentation as memory is divided into variable-sized blocks.

Example: Intel x86 architecture uses segmentation.

Comparison Table

Strategy	Merits	Demerits	Example
Contiguous Allocation	Simple to implement, efficient in terms of speed	External fragmentation, size of the process needs to be known in advance	MS-DOS
Non-Contiguous Allocation	Solves the problem of external fragmentation, size of the process doesn't need to be known in advance	More complex to implement, slower than contiguous allocation	Windows, Linux
Paging	Solves the problem of external fragmentation, allows the physical address space of a process to be noncontiguous	Overhead of maintaining page tables, internal fragmentation	Most modern operating systems
Segmentation	Allows memory to be allocated in a way that matches the logical structure of a program	External fragmentation	Intel x86 architecture

Conclusion

In conclusion, the choice of space allocation strategy depends on the requirements of the system and the trade-offs between simplicity, speed, and efficient use of memory. While contiguous allocation is simple and fast, it suffers from external fragmentation. Non-contiguous allocation and paging solve the problem of external fragmentation but are more complex and slower. Segmentation allows memory to be allocated in a way that matches the logical structure of a program but suffers from external fragmentation.

Summary

Space allocation strategies in operating systems include contiguous allocation, non-contiguous allocation, paging, and segmentation. Contiguous allocation allocates each process in a single continuous block of memory, while non-contiguous allocation allows a process to be allocated in multiple memory spaces. Paging divides memory into fixed-size blocks called pages, and segmentation divides memory into variable-sized blocks known as segments. Each strategy has its merits and demerits, and the choice depends on the system's requirements and trade-offs between simplicity, speed, and efficient memory use.

Analogy

Space allocation strategies in operating systems are like different ways of organizing a library. Contiguous allocation is like placing each book on a single shelf, non-contiguous allocation is like placing a book on multiple shelves, paging is like dividing the library into fixed-size sections, and segmentation is like dividing the library into variable-sized sections based on the subject of the books.