Memory Management

---

---

Segmentation

Segmentation is a memory management technique that divides a program’s logical memory into variable-sized blocks called segments. Unlike paging, where the division is based on a fixed size, segmentation divides the memory based on the programmer’s view of the program.

Think of a program not as one long list of instructions, but as a collection of logical units or modules. 🏗️

For example, a program has:

• A main() function
• Other functions (e.g., calculate_interest(), print_statement())
• Global variables
• A stack (for local variables and function calls)
• A heap (for dynamic memory)

Each of these logical units can be a segment. So, main() could be one segment, calculate_interest() another, and the global variables a third. The size of each segment is not fixed; it’s determined by the size of the logical unit it holds.

---

How Segmentation Works: Address Translation

Since segments are of variable sizes and are placed in different parts of the physical memory (RAM), the OS needs a way to translate the logical address used by the CPU into a physical address in RAM.

A Logical Address in segmentation has two parts:

1. Segment Number (s): The number that identifies the segment.
2. Offset (d): The location of the data or instruction within that segment.

This translation is handled using a Segment Table.

The Segment Table 🧠

The Segment Table is a data structure used by the OS for each process. It stores information about each segment. The two most important fields in the segment table are:

• Base: The starting physical address where the segment is stored in RAM.
• Limit: The size or length of the segment.

The Translation Process

Here’s the step-by-step process:

1. The CPU generates a Logical Address, which includes a Segment Number (s) and an Offset (d).
2. The OS uses the Segment Number (s) to look up the corresponding entry in the process’s Segment Table.
3. From the table, it retrieves the Base and Limit for that segment.
4. Protection Check: The OS first checks if the Offset (d) is less than the Limit. If d >= Limit, it means the program is trying to access memory outside its segment, which is an error (a “segmentation fault”).
5. If the offset is valid, the OS calculates the Physical Address by adding the base address to the offset.
   • Physical Address = Base Address + Offset
6. This physical address is then used to access the data in RAM.

---

A Simple Example

Let’s assume a program has a segment table like this:

Segment #	Base	Limit
0 (main)	2000	800
1 (function)	3200	400
2 (stack)	5000	1000

Export to Sheets

Now, the CPU wants to access an instruction at Logical Address = (Segment 1, Offset 150).

1. Look in the Segment Table: The OS looks at the entry for Segment #1.
   • Base = 3200
   • Limit = 400
2. Perform the Check: Is the offset (150) less than the limit (400)? Yes, 150 < 400. The access is valid.
3. Calculate the Physical Address:
   • Physical Address = Base + Offset
   • Physical Address = 3200 + 150 = 3350

So, the instruction is located at physical address 3350 in RAM.

---

Segmentation vs. Paging

This is a very common exam topic. Here are the key differences:

Feature	Segmentation	Paging
Block Size	Variable-sized blocks called segments.	Fixed-sized blocks called pages.
Division	Program is divided based on logical units (functions, modules).	Program is divided blindly into fixed chunks.
Programmer View	Visible to the programmer (they can think in terms of segments).	Invisible to the programmer.
Fragmentation	Suffers from External Fragmentation (unused memory holes between segments).	Suffers from Internal Fragmentation (wasted space in the last page).
Address	Logical address has a segment number and offset.	Logical address has a page number and offset.
Data Structures	Uses a Segment Table.	Uses a Page Table.

---

Advantages and Disadvantages of Segmentation

Advantages 👍	Disadvantages 👎
No Internal Fragmentation: Since segments are exactly the size of the logical unit, no space is wasted inside a block.	External Fragmentation: As segments are loaded and removed from memory, it creates variable-sized empty holes, leading to wasted space.
Better Protection & Sharing: It’s easier to implement protection (e.g., make a code segment read-only) or share a segment (e.g., a library function) among multiple processes.	Complex Memory Management: Allocating variable-sized blocks of memory is more difficult and slower than allocating fixed-size frames.
Logical Structure: Aligns with how programmers view their code, making it more intuitive.	Costly: The hardware and OS support for segmentation can be more complex.

---

---

Virtual Memory

Virtual Memory is a memory management technique that gives a program the illusion that it has a very large, continuous block of main memory (RAM), when in reality, its physical memory may be fragmented and much smaller. It achieves this by temporarily storing parts of the program on the hard disk and loading them into RAM only when needed.

Think of it like using a small desk to work on a massive project. You can’t fit all your documents on the desk at once. So, you keep most of them in a nearby filing cabinet (the hard disk). You only bring the specific documents you’re currently working on onto your desk (the RAM). When you need a new document, you swap it with one you’re done with. This gives you the illusion of having a huge workspace. 📚

---

How Virtual Memory Works

Virtual memory is most commonly implemented using Demand Paging.

• Demand Paging: This is the core idea. Instead of loading the entire program into RAM when it starts, the OS loads only the first page. Other pages are only loaded from the hard disk into RAM on demand, i.e., when the CPU tries to access them.
• Page Table with Valid-Invalid Bit: To manage this, the page table is modified to include a valid-invalid bit for each entry.
  • Valid (1): This means the corresponding page is in RAM, and the entry points to the correct frame.
  • Invalid (0): This means the page is currently on the hard disk, not in RAM.

---

The Page Fault

A page fault is a trap or an exception raised by the hardware when a running program tries to access a memory page that is marked as “invalid” in the page table. This is not an error; it’s the mechanism that makes virtual memory work.

Here’s what happens when a page fault occurs:

1. The CPU tries to access an address on a page, but the page table entry for it is marked as invalid.
2. A trap is generated, and control is given to the Operating System.
3. The OS checks an internal table to find the location of the required page on the hard disk.
4. It finds a free frame in RAM. If there are no free frames, it uses a page replacement algorithm (like LRU or FIFO) to select a “victim” page to swap out.
5. The OS loads the required page from the hard disk into the free (or newly freed) frame in RAM.
6. It updates the page table, setting the valid-invalid bit to valid and updating the frame number.
7. Finally, it returns control to the program, which can now access the memory location as if the page had always been in RAM.

---

Advantages and Disadvantages of Virtual Memory

Advantages 👍	Disadvantages 👎
Larger Programs: Allows you to run programs that are much larger than your physical RAM.	Performance Overhead: The process of handling page faults (swapping pages between RAM and disk) is time-consuming and can slow down the system if it happens too frequently.
Increased Multiprogramming: More processes can be kept in memory simultaneously, as each process only needs a few of its pages to be in RAM. This increases CPU utilization.	Thrashing: If a process doesn’t have enough frames, it can get into a state of continuous page faulting, where it spends more time swapping pages than executing. This is called thrashing.
Efficient Memory Use: Only the necessary parts of a program are in memory at any given time, leading to less wasted space.	Disk Space Usage: It requires a significant amount of hard disk space to store the parts of programs that aren’t in RAM.
Faster Process Creation: Processes can start running faster as the entire program doesn’t need to be loaded first.

---

---

Memory Allocation

Memory allocation is how an operating system manages its main memory (RAM) by assigning sections of it to running programs and processes. The goal is to use the limited memory space as efficiently as possible.

Think of the RAM as a parking lot 🅿️ and processes as cars of different sizes. The parking lot attendant (the OS) has to decide which car goes into which spot to fit as many cars as possible.

There are two main ways the OS allocates memory.

---

1. Contiguous Memory Allocation

This is the simplest method. Here, each process is contained in a single, continuous section of memory. It’s like parking a long bus—it needs one long, unbroken parking space.

To keep track of memory, the OS divides it into partitions. When a process arrives, the OS looks for a free partition (or “hole”) that is large enough to hold it. There are three common strategies for choosing a hole:

• First-Fit: The OS scans the memory from the beginning and chooses the first hole that is large enough. This is fast.
• Best-Fit: The OS searches the entire list of holes and chooses the smallest hole that is large enough. This tries to reserve larger holes for larger processes but can leave tiny, unusable holes.
• Worst-Fit: The OS searches the entire list and chooses the largest hole. The idea is that the leftover space will be large enough to be useful.

The Problem with Contiguous Allocation: Fragmentation

The major drawback of this method is fragmentation, which is wasted memory space. There are two types:

• External Fragmentation: This happens when there is enough total free memory to satisfy a request, but the available spaces are not continuous. You have many small, scattered empty spots, but none are big enough for the incoming process. It’s like having 10 empty single-bike spots when you need to park a car.
• Internal Fragmentation: This occurs when a memory block allocated to a process is larger than what the process actually needs. The unused space inside the allocated block is wasted. For example, if a process needs 29KB but is allocated a 32KB block, 3KB is wasted due to internal fragmentation.

---

2. Non-Contiguous Memory Allocation

This is a more advanced and modern approach that solves the problem of external fragmentation. Here, a process is allowed to occupy different parts of physical memory that are not next to each other. The OS keeps track of all the scattered pieces.

It’s like tearing out the pages of a book and placing them in various empty slots in a binder. As long as you have an index to tell you the order, it doesn’t matter that they aren’t continuous.

The two most important techniques for non-contiguous allocation are:

• Paging: The memory is broken into fixed-size blocks called frames, and a process is broken into fixed-size blocks called pages. Any page can be placed in any free frame. This method completely eliminates external fragmentation but can have minor internal fragmentation.
• Segmentation: The memory is divided into variable-sized blocks based on the logical structure of a program (e.g., code, stack, heap). Each of these logical units, or segments, can be placed anywhere in memory. This method can suffer from external fragmentation.