Lecture 6: Segmentation & paged segmentation

3. Segmentation

3.1 Concept and motivation

Segmentation is a memory-management technique in which a program is divided into logical units of variable size, called segments. Each segment corresponds to a meaningful part of the program rather than an arbitrary fixed-size block. For example, a program may naturally be viewed as a collection of segments such as:

• main program
• functions or procedures
• global data
• stack
• heap
• symbol table
• arrays or large data structures

The main motivation for segmentation is that programmers think in terms of logical modules, not in terms of pages of equal size. A procedure is one logical unit, a stack is another, and a data area is another. Segmentation therefore reflects the programmer’s natural view of memory more closely than paging.

3.2 User view vs physical view

Suppose a program contains a code module of 40 KB, a data area of 12 KB, a stack of 8 KB, and a symbol table of 6 KB. In segmentation, these can exist as four separate segments. Their sizes are not equal, and they need not be adjacent in physical memory.

3.3 Logical address format

In segmentation, a logical address is not a single number. It is a pair:

Here:

• Segment number (s) identifies which segment is being referenced.
• Offset (d) tells the location of the required byte or word within that segment.

This is very natural. For example, an instruction may refer to “byte 120 inside the stack segment” or “word 80 inside the code segment.”

3.4 Segment table

Since segments are variable in size and may be stored anywhere in physical memory, the operating system keeps a segment table. Each entry in the segment table usually contains:

• Base – starting physical address of the segment
• Limit – length of the segment

Some systems also store protection bits, valid bits, sharing information, and status bits.

Segment No.	Meaning	Base	Limit
0	Code	4000	1200
1	Data	9000	700
2	Stack	12500	500
3	Symbols	16000	300

3.5 Address translation in segmentation

When the CPU generates a logical address <s, d>, the MMU performs the following steps:

1. Use s to index the segment table.
2. Obtain the base and limit of that segment.
3. Check whether d < limit.
4. If valid, compute physical address as base + d.
5. If invalid, generate a trap to the operating system.

3.6 Protection and sharing in segmentation

Segmentation is especially good for protection and sharing because each segment is a meaningful logical unit. For example:

• The code segment can be marked read-only and executable.
• The data segment can be marked read-write.
• The stack segment can grow and can have separate access rules.
• Shared library code can be mapped as a segment shared by multiple processes.

So segmentation is not just about address translation. It also supports cleaner program organization and finer control.

3.7 Fragmentation in segmentation

Because segments are variable-sized, segmentation suffers from external fragmentation. Free memory may exist, but it may be scattered in small holes. Therefore:

• allocation becomes more difficult over time,
• compaction may be needed,
• memory management becomes more complex than a pure fixed-size scheme.

3.8 Worked example

4. Paged Segmentation

4.1 Why combine paging and segmentation?

Paging and segmentation each solve a different problem:

• Segmentation matches the logical structure of a program.
• Paging removes the need for contiguous physical allocation and reduces external fragmentation.

So the natural next step is to combine them. That gives us paged segmentation.

4.2 Address format

In paged segmentation, a logical address typically has three parts:

Here:

• Segment number selects the logical module.
• Page number selects the page within that segment.
• Offset selects the location within that page.

4.3 Translation steps

1. Use the segment number to locate the segment-table entry.
2. The segment-table entry tells where the page table of that segment is stored.
3. Use the page number to index that page table.
4. Obtain the frame number.
5. Combine frame number and offset to obtain the physical address.

4.4 Why paged segmentation is useful

Paged segmentation gives the best of both worlds:

• Logical organization from segmentation
• Efficient noncontiguous physical allocation from paging
• Better protection and sharing possibilities
• Less external fragmentation than pure segmentation

4.5 Cost of the scheme

The main drawback is complexity. There are now multiple levels of translation:

• segment lookup,
• page-table lookup,
• frame mapping.

More tables mean more storage overhead and more translation work, unless hardware support such as TLB-style caching is used.

5. Virtual Memory Concepts

5.1 What virtual memory really means

Virtual memory is a memory-management technique that allows a process to execute even when the entire process is not physically present in main memory. Only the currently needed parts of the process must be in RAM. The remaining parts can stay on secondary storage, usually disk.

In simple language, virtual memory creates the illusion that the process has access to a large, continuous memory space, even though physical memory is limited and only a portion of that space is resident in RAM at any time.

5.2 Why virtual memory is important

• Programs can be larger than physical memory.
• Only required parts of a program need to be loaded.
• More processes can reside in the system at the same time.
• Memory utilization improves.
• CPU utilization improves because multiprogramming becomes easier.

5.3 Logical address space vs physical memory

A process may have a large logical address space containing code, stack, heap, data, libraries, and memory-mapped regions. But at one moment, it may actually use only a small subset of that space. Virtual memory takes advantage of this fact.

5.4 Characteristics of virtual memory

Characteristic	Meaning
Large logical space	Processes can have address spaces much larger than RAM.
Partial loading	Only needed pages or segments are kept in memory.
On-demand transfer	Missing parts are brought from backing store when referenced.
Illusion of continuity	The process experiences memory as one coherent address space.

5.5 Locality and why virtual memory works

Virtual memory works well because programs usually show locality of reference. At any given time, the CPU tends to use:

• a small region of code repeatedly,
• some nearby instructions,
• a limited working set of data.

That means the whole program does not need to be in memory all at once. If it did, virtual memory would be much less useful and much more painful.

5.6 Benefits of virtual memory

• Supports large programs and large address spaces
• Allows higher degree of multiprogramming
• Improves RAM utilization
• Supports modern abstractions such as memory-mapped files and shared libraries

5.7 Cost of virtual memory

The great advantage comes with a heavy warning label: if the system constantly moves pages between RAM and disk, performance can collapse. Disk access is enormously slower than memory access.

6. Demand Paging

6.1 Basic idea

Demand paging is the most common implementation approach for paged virtual memory. In this scheme, a page is brought into main memory only when it is actually referenced.

So instead of loading all pages of a process at startup, the system begins with only a subset in RAM. The remaining pages stay on backing store until needed.

6.2 Valid-invalid bit

To support demand paging, each page-table entry includes a valid-invalid bit:

• Valid means the page is in the process’s logical address space and currently available for use.
• Invalid means either the page is not part of the process’s legal address space or it is not currently in memory.

When a referenced page is marked invalid, the hardware generates a page-fault trap.

6.3 What is a page fault?

A page fault occurs when the CPU references a page that is part of the process’s logical address space but is not currently resident in main memory. This is not automatically an error. In demand paging, page faults are expected.

6.4 Steps in page-fault handling

1. The CPU generates a reference to a page.
2. The MMU checks the page table.
3. If the entry is invalid, a page-fault trap occurs.
4. The operating system checks whether the reference is legal.
5. If illegal, the process is terminated or trapped with an error.
6. If legal, the OS locates the missing page on backing store.
7. A free frame is allocated. If no free frame exists, a page-replacement algorithm is invoked.
8. The required page is read from disk into the selected frame.
9. The page-table entry is updated to mark the page valid.
10. The interrupted instruction is restarted.

6.5 Restarting the instruction

This step is important. After the page is brought into memory, the CPU must execute the instruction again as if nothing unusual happened. That is why page-fault handling is tightly integrated with hardware support and operating-system control.

6.6 Demand paging and performance

Demand paging saves memory, but page faults are expensive because disk I/O is involved. Therefore performance depends strongly on the page-fault rate.

Let:

• ma = memory access time
• p = page-fault rate
• page fault service time = time to handle a fault and load the page

Then the effective access time increases dramatically even when p is small, because disk access is so slow compared with RAM access.

6.7 Pure demand paging vs prepaging

In pure demand paging, no page is brought in until it is first referenced. Some systems, however, also use limited prepaging, where a few likely-needed pages are loaded in advance to reduce initial page faults.

The textbook excerpt on BSD notes that pages can be prepaged on startup and that pure demand paging can increase fault overhead. :contentReference[oaicite:3]{index=3}

6.8 Advantages of demand paging

• Less I/O at process startup
• Lower memory usage initially
• Programs larger than RAM can execute
• Better multiprogramming support

6.9 Disadvantages of demand paging

• Page faults are expensive
• Hardware and OS support are required
• Poor page-replacement choices can cause many faults
• If faults become excessive, the system may enter thrashing

6.10 Worked example

7. Final Comparison Snapshot

Topic	Main idea	Strength	Main weakness
Segmentation	Divide memory by logical program units	Natural organization, easy protection and sharing	External fragmentation
Paged Segmentation	Segment first, page later	Logical structure + better physical allocation	More complex translation
Virtual Memory	Logical memory larger than RAM	Runs larger programs, improves utilization	Depends heavily on page-fault behavior
Demand Paging	Load a page only when referenced	Efficient memory use	Fault handling is expensive