Q.The operating system in computer or mobile allocates memory to different applications for their execution. How does an operating system keep track of the free memory that can be allocated among programs/applications to be executed?

This is a plain theory question asking for the mechanism by which an operating system tracks free memory for allocation.

---

The operating system maintains data structures that record which portions of memory are currently in use and which are available for allocation. Two fundamental approaches are used:

1. Bitmap (Bit Vector)

Memory is divided into fixed-size allocation units (blocks or frames), and a bitmap maintains one bit per unit: $0$ indicates free, $1$ indicates occupied (or vice versa). When a process requests memory, the OS scans the bitmap for a contiguous sequence of $0$s large enough to satisfy the request. This method is simple and space-efficient for the bookkeeping structure itself, but searching for a free block of a given size requires scanning the bitmap, which can be slow for large memory.

2. Linked List (Free List)

The OS maintains a linked list of free memory blocks, where each node records the starting address and size of a free region. When memory is allocated, a suitable block is removed (or split if larger than needed); when memory is freed, the block is returned to the list and merged with adjacent free blocks if possible (coalescing) to reduce fragmentation. Variants include:

• First Fit: allocate the first block large enough.
• Best Fit: allocate the smallest block that fits (minimizes wasted space but may leave tiny unusable fragments).
• Worst Fit: allocate the largest available block. …

Why Memory Tracking Matters

When multiple programs run concurrently, each needs its own chunk of RAM. The operating system acts as a memory manager: it must know at every instant which portions of physical memory are occupied and which are available. Without this bookkeeping, two programs might be assigned overlapping addresses, corrupting each other's data.

The core challenge is dynamic allocation. Programs request memory at unpredictable times and release it when done. The OS must respond quickly to allocation requests, minimize wasted space (fragmentation), and reclaim freed blocks for reuse.

---

Common Data Structures for Free-Memory Tracking

1. Free List (Linked List of Free Blocks)

The OS maintains a linked list where each node represents a contiguous block of free memory. Each node stores:

• The starting address of the block.
• The size of the block.
• A pointer to the next free block.

When a program requests $n$ bytes, the OS scans the list using one of several strategies:

• First Fit: allocate the first block large enough.
• Best Fit: allocate the smallest block that fits (minimizes leftover space).
• Worst Fit: allocate the largest block (leaves larger fragments).

When memory is freed, the OS adds the block back to the list and coalesces adjacent free blocks to reduce fragmentation.

---

2. Bitmap (Bit Vector)

Memory is divided into fixed-size units (e.g., 4 KB pages). A bitmap uses one bit per unit:

• 0 = free
• 1 = allocated (or vice versa)

To allocate $k$ contiguous units, the OS scans the bitmap for $k$ consecutive zeros. Deallocation simply flips the corresponding bits back to zero.

Trade-off: Bitmaps are space-efficient for large memories but scanning for contiguous runs can be slow.

---

3. Buddy System

Memory is divided into blocks whose sizes are powers of two (e.g., 1 KB, 2 KB, 4 KB, …). Each size class has its own free list.

• Allocation: If a request for $n$ bytes arrives, the OS finds the smallest power-of-two block $\geq n$. If none exists, it splits a larger block recursively.
• Deallocation: When a block is freed, the OS checks if its "buddy" (the adjacent block from the same split) is also free. If so, they are merged back into a larger block.

This reduces external fragmentation and makes coalescing efficient, but can waste space due to internal fragmentation (a 65 KB request gets a 128 KB block).

---

4. Memory Allocation Table (MAT) / Partition Table

For systems using fixed partitioning, the OS maintains a table with one entry per partition:

• Partition size
• Status (free / allocated)
• Process ID (if allocated)

This is simple but inflexible; modern OSes rarely use pure fixed partitioning.

---

5. Page Tables (for Virtual Memory)

In systems with paging, physical memory is divided into fixed-size frames and logical memory into pages. The OS keeps:

• A page table per process (maps virtual pages to physical frames).
• A free frame list or bitmap tracking which frames are unallocated.

When a process requests memory, the OS allocates free frames and updates the page table. The Memory Management Unit (MMU) translates virtual addresses to physical addresses on the fly.

---

Handling Fragmentation

• External fragmentation: Free memory exists but is scattered in small, non-contiguous blocks. Solved by compaction (moving allocated blocks together) or using paging.
• Internal fragmentation: Allocated blocks are larger than requested (e.g., allocating a 4 KB page for a 100-byte request). Minimized by choosing appropriate block sizes or using segmentation.

---

Example: Free List in Action

Suppose physical memory is 16 KB, initially all free. The free list starts with one node: …