Answers for Sample Questions of OS Chapter 9

### **What is memory management?**

Memory management is a core activity of an operating system. It determines what data and processes reside in memory and when. It involves tracking which parts of memory are in use and by whom, allocating and freeing memory space on demand, and deciding which processes (or parts thereof) and data should be moved into or out of memory. Memory management also includes the process of binding logical address spaces to separate physical address spaces. In multiprogramming systems, where multiple programs must reside in memory simultaneously to improve CPU utilization and system responsiveness, memory management becomes essential.

---

### **When does the address binding happen?**

Address binding — the mapping of symbolic or logical addresses to physical addresses — can occur at different stages of program execution:

1. **At compile time**: If the location of the process in memory is known at compile time, logical addresses can be bound directly to physical addresses. In this case, logical and physical addresses are the same.
2. **At load time**: If the memory location is not known at compile time but is determined when the program is loaded into memory, binding occurs at load time. Again, the logical and physical addresses become identical.
3. **At execution time**: If the process can be relocated from one memory segment to another during execution, binding must be delayed until runtime. This requires special hardware support. Most modern operating systems use this method. In such cases, logical and physical addresses differ. The provided material focuses mainly on execution-time binding.

---

### **What is a physical memory address?**

A physical address is the actual address recognized by the memory unit. It is the address that is loaded into the memory address register. Physical addresses are used by the memory hardware and their range depends on the size of the physical memory available.

---

### **What is a logical memory address?**

A logical address is the address generated by the CPU. It is often referred to as a virtual address, especially in execution-time binding schemes. It represents the address space used by the CPU for addressing instructions and data in memory. The size of the logical address space depends on the number of bits in the CPU.

---

### **Under what circumstances are these two addresses the same? When are they different?**

Logical and physical addresses are the same in **compile-time** and **load-time** binding schemes. They are different in **execution-time** binding, where special hardware (such as the MMU) is used to dynamically translate logical addresses into physical ones.

---

### **What are the memory allocation methods? What are their advantages and disadvantages?**

The material discusses the following memory allocation methods:

1. **Contiguous Memory Allocation**: Each process is allocated a contiguous block of memory. Memory can be divided into fixed- or variable-sized partitions to accommodate processes.
   - *Disadvantage*: Leads to **external fragmentation**, where free memory exists but is too fragmented to be used effectively.

2. **Paging**: A memory management scheme that allows the physical address space of a process to be non-contiguous. Physical memory is divided into fixed-size blocks called **frames**, and logical memory is divided into equal-sized blocks called **pages**. Process pages can be loaded into any available frames.
   - *Advantages*:
     - Eliminates external fragmentation and the need for compaction.
     - Allows the logical address space to be independent of the physical address space.
   - *Disadvantages*:
     - Introduces **internal fragmentation**, where some space may be wasted at the end of each page (on average half a page per process).
     - Page tables themselves introduce overhead; larger page sizes reduce this overhead.

---

### **How is a logical address mapped to a physical address?**

Mapping of logical (virtual) addresses to physical addresses at runtime is performed by a hardware component called the **Memory Management Unit (MMU)**.

- In a simple MMU setup, a **relocation register** is used. Each address generated by the CPU is dynamically adjusted by adding the base value stored in the relocation register.

- In a **paging system**, the logical address is divided into:

- **Page number (p)**: Used as an index into the **page table**.
  - **Offset (d)**: Specifies the exact byte within the page/frame.

The page table contains the **frame number** corresponding to each page. During address translation:

1. Extract the page number `p`.
  2. Use it to index into the page table and retrieve the corresponding frame number `f`.
  3. Combine the frame number `f` with the offset `d` to form the physical address `<f, d>`.

---

### **How can we reduce the time needed to look up physical addresses?**

Since storing the page table in main memory can slow down memory access (requiring two memory accesses per data access), a **Translation Look-aside Buffer (TLB)** is used to speed things up.

- The TLB is a fast hardware cache that stores recently used page table entries.
- When the CPU generates a logical address, the MMU first checks the TLB:
  - If a matching entry is found (**TLB hit**), the physical frame number is retrieved immediately, avoiding a trip to the main memory page table.
  - If no match is found (**TLB miss**), the page table in memory must be consulted.

This significantly reduces average memory access time.

---

### **What techniques are used to handle large page tables?**

In modern systems with large virtual address spaces (e.g., 32-bit or 64-bit architectures), single-level page tables can become very large and consume excessive memory. Several techniques are used to manage this:

1. **Hierarchical Paging (Multi-level Page Tables)**: The page table itself is paged. For example, in a **two-level paging** scheme, the logical page number is split into two parts: one to index the outer page table, and another to index the inner page table.
   - *Advantages*: Saves memory by allowing only necessary portions of the page table to be resident.
   - *Disadvantages*: Increases the number of memory accesses required for address translation (e.g., three accesses for a two-level page table).

2. **Hashed Page Tables**: Uses a hash function on the virtual page number to locate the appropriate page table entry. Useful for sparse address spaces.

3. **Inverted Page Tables**: Instead of maintaining a page table per process, a single global inverted page table is used, with one entry per physical frame. Each entry stores the virtual page number and the process ID (PID) that owns it.
   - *Advantage*: Reduces memory usage, as the size of the table depends on physical memory size, not virtual address space size.
   - *Disadvantage*: Lookup requires searching the table for a match of PID and virtual page number, which can be computationally expensive without optimization (e.g., hashing).