Skip to main content

Chapter 16: Segmentation Generalized Base Bounds

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives​

  • Explain the main ideas and vocabulary in Segmentation Generalized Base Bounds.
  • Work through the source examples for Segmentation Generalized Base Bounds without depending on raw chunk order.
  • Use Segmentation Generalized Base Bounds as selective reference when learner modules point back to Ostep.

Prerequisites​

  • Earlier prerequisite concepts leading into Chapter 16: Segmentation Generalized Base Bounds.

Module targets​

  • module-02-memory-management-virtual-memory

AI companion modes​

  • Explain simply
  • Socratic tutor
  • Quiz me
  • Challenge my understanding
  • Diagnose my confusion
  • Generate extra practice
  • Revision mode
  • Connect forward / backward

Source-of-truth note​

This unit is anchored to Ostep and the source chapter "Chapter 16: Segmentation Generalized Base Bounds". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment​

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance​

  • Primary source: Ostep
  • Source chapter 16: Chapter 16: Segmentation Generalized Base Bounds
  • Raw source file: 070-16-1-segmentation-generalized-base-bounds.md
  • Raw source file: 072-16-4-support-for-sharing.md
  • Raw source file: 073-16-6-os-support.md

Merged source​

Segmentation Generalized Base Bounds​

16.1 Segmentation: Generalized Base/Bounds

dress generated by the process is in or out of bounds. If in bounds, compute the translation.

  1. Run with these flags: -s 0 -n 10. What value do you have set

-l(the bounds register) to in order to ensure that all the generated virtual addresses are within bounds?

  1. Run with these flags: -s 1 -n 10 -l 100. What is the maxi-

mum value that bounds can be set to, such that the address space still fits into physical memory in its entirety?

  1. Run some of the same problems above, but with larger address

spaces (-a) and physical memories (-p).

  1. What fraction of randomly-generated virtual addresses are valid,

as a function of the value of the bounds register? Make a graph from running with different random seeds, with limit values ranging from 0 up to the maximum size of the address space.

16

Segmentation

So far we have been putting the entire address space of each process in memory. With the base and bounds registers, the OS can easily relocate processes to different parts of physical memory. However, you might have noticed something interesting about these address spaces of ours:

there is a big chunk of "free" space right in the middle, between the stack and the heap.

As you can imagine from Figure 16.1, although the space between the stack and heap is not being used by the process, it is still taking up physical memory when we relocate the entire address space somewhere in physical memory; thus, the simple approach of using a base and bounds register pair to virtualize memory is wasteful. It also makes it quite hard to run a program when the entire address space doesn't fit into memory; thus, base and bounds is not as flexible as we would like. And thus:

THECRUX: HOWTOSUPPORTA LARGEADDRESSSPACE

How do we support a large address space with (potentially) a lot of free space between the stack and the heap? Note that in our examples, with tiny (pretend) address spaces, the waste doesn't seem too bad. Imagine, however, a 32-bit address space (4 GB in size); a typical program will only use megabytes of memory, but still would demand that the entire address space be resident in memory.

To solve this problem, an idea was born, and it is called segmentation. It is quite an old idea, going at least as far back as the very early 1960's [H61, G62]. The idea is simple: instead of having just one base and bounds pair in our MMU, why not have a base and bounds pair per logical segmentof the address space? A segment is just a contiguous portion of the address space of a particular length, and in our canonical 1 1KB Program Code 2KB 3KB 4KB 5KB Heap 6KB

(free)

14KB 15KB

Stack 16KB

Figure 16.1:An Address Space (Again) address space, we have three logically-different segments: code, stack, and heap. What segmentation allows the OS to do is to place each one of those segments in different parts of physical memory, and thus avoid filling physical memory with unused virtual address space.

Let's look at an example. Assume we want to place the address space from Figure 16.1 into physical memory. With a base and bounds pair per segment, we can place each segmentindependentlyin physical memory. For example, see Figure 16.2 (page 3); there you see a 64KB physical memory with those three segments in it (and 16KB reserved for the OS).

Operating System 16KB

(not in use)

Stack

(not in use)

32KB Code

Heap 48KB

(not in use)

64KB

Figure 16.2:Placing Segments In Physical Memory

As you can see in the diagram, only used memory is allocated space in physical memory, and thus large address spaces with large amounts of unused address space (which we sometimes callsparse address spaces) can be accommodated.

The hardware structure in our MMU required to support segmentation is just what you'd expect: in this case, a set of three base and bounds register pairs. Figure 16.3 below shows the register values for the example above; each bounds register holds the size of a segment.

Segment Base Size

Code 32K 2K

Heap 34K 2K

Stack 28K 2K

Figure 16.3:Segment Register Values

You can see from the figure that the code segment is placed at physical address 32KB and has a size of 2KB and the heap segment is placed at 34KB and also has a size of 2KB.

Let's do an example translation, using the address space in Figure 16.1.

Assume a reference is made to virtual address 100 (which is in the code segment). When the reference takes place (say, on an instruction fetch), the hardware will add the base value to theoffsetinto this segment (100 in this case) to arrive at the desired physical address: 100 + 32KB, or 32868.

It will then check that the address is within bounds (100 is less than 2KB), find that it is, and issue the reference to physical memory address 32868.

Support For Sharing​

16.4 Support for Sharing

As support for segmentation grew, system designers soon realized that they could realize new types of efficiencies with a little more hardware support. Specifically, to save memory, sometimes it is useful to share certain memory segments between address spaces. In particular, code sharingis common and still in use in systems today.

To support sharing, we need a little extra support from the hardware, in the form ofprotection bits. Basic support adds a few bits per segment, indicating whether or not a program can read or write a segment, or perhaps execute code that lies within the segment. By setting a code segment to read-only, the same code can be shared across multiple processes, without worry of harming isolation; while each process still thinks that it is accessing its own private memory, the OS is secretly sharing memory which cannot be modified by the process, and thus the illusion is preserved.

An example of the additional information tracked by the hardware (and OS) is shown in Figure 16.5. As you can see, the code segment is set to read and execute, and thus the same physical segment in memory could be mapped into multiple virtual address spaces.

Segment Base Size Grows Positive? Protection

Code 32K 2K 1 Read-Execute

Heap 34K 2K 1 Read-Write

Stack 28K 2K 0 Read-Write

Figure 16.5:Segment Register Values (with Protection)

With protection bits, the hardware algorithm described earlier would also have to change. In addition to checking whether a virtual address is within bounds, the hardware also has to check whether a particular access is permissible. If a user process tries to write to a read-only segment, or execute from a non-executable segment, the hardware should raise an exception, and thus let the OS deal with the offending process.

16.5 Fine-grained vs. Coarse-grained Segmentation​

Most of our examples thus far have focused on systems with just a few segments (i.e., code, stack, heap); we can think of this segmentation ascoarse-grained, as it chops up the address space into relatively large, coarse chunks. However, some early systems (e.g., Multics [CV65,DD68]) were more flexible and allowed for address spaces to consist of a large number of smaller segments, referred to asfine-grainedsegmentation.

Supporting many segments requires even further hardware support, with asegment tableof some kind stored in memory. Such segment tables usually support the creation of a very large number of segments, and thus enable a system to use segments in more flexible ways than we have thus far discussed. For example, early machines like the Burroughs B5000 had support for thousands of segments, and expected a compiler to chop code and data into separate segments which the OS and hardware would then support [RK68]. The thinking at the time was that by having finegrained segments, the OS could better learn about which segments are in use and which are not and thus utilize main memory more effectively.

Os Support​

16.6 OS Support

You now should have a basic idea as to how segmentation works.

Pieces of the address space are relocated into physical memory as the system runs, and thus a huge savings of physical memory is achieved relative to our simpler approach with just a single base/bounds pair for the entire address space. Specifically, all the unused space between the stack and the heap need not be allocated in physical memory, allowing us to fit more address spaces into physical memory.

However, segmentation raises a number of new issues. We'll first describe the new OS issues that must be addressed. The first is an old one:

what should the OS do on a context switch? You should have a good guess by now: the segment registers must be saved and restored. Clearly, each process has its own virtual address space, and the OS must make sure to set up these registers correctly before letting the process run again.

The second, and more important, issue is managing free space in physical memory. When a new address space is created, the OS has to be able to find space in physical memory for its segments. Previously, we assumed that each address space was the same size, and thus physical memory could be thought of as a bunch of slots where processes would fit in. Now, we have a number of segments per process, and each segment might be a different size.

Not Compacted Compacted 8KB Operating System 8KB Operating System 16KB 16KB

(not in use)

24KB 24KB

Allocated Allocated 32KB 32KB

(not in use)

Allocated 40KB 40KB 48KB 48KB

(not in use)
(not in use)

56KB 56KB

Allocated 64KB 64KB

Figure 16.6:Non-compacted and Compacted Memory

The general problem that arises is that physical memory quickly becomes full of little holes of free space, making it difficult to allocate new segments, or to grow existing ones. We call this problemexternal fragmentation[R69]; see Figure 16.6 (left).

In the example, a process comes along and wishes to allocate a 20KB segment. In that example, there is 24KB free, but not in one contiguous segment (rather, in three non-contiguous chunks). Thus, the OS cannot satisfy the 20KB request.

One solution to this problem would be tocompactphysical memory by rearranging the existing segments. For example, the OS could stop whichever processes are running, copy their data to one contiguous region of memory, change their segment register values to point to the new physical locations, and thus have a large free extent of memory with which to work. By doing so, the OS enables the new allocation request to succeed. However, compaction is expensive, as copying segments is memory-intensive and generally uses a fair amount of processor time.

See Figure 16.6 (right) for a diagram of compacted physical memory.

A simpler approach is to use a free-list management algorithm that tries to keep large extents of memory available for allocation. There are literally hundreds of approaches that people have taken, including classic algorithms likebest-fit(which keeps a list of free spaces and returns the one closest in size that satisfies the desired allocation to the requester), worst-fit,first-fit, and more complex schemes likebuddy algorithm[K68].

An excellent survey by Wilson et al. is a good place to start if you want to learn more about such algorithms [W+95], or you can wait until we cover some of the basics ourselves in a later chapter. Unfortunately, though, no matter how smart the algorithm, external fragmentation will still exist;

thus, a good algorithm simply attempts to minimize it.

TIP: IF1000 SOLUTIONSEXIST, NOGREATONEDOES

The fact that so many different algorithms exist to try to minimize external fragmentation is indicative of a stronger underlying truth: there is no one "best" way to solve the problem. Thus, we settle for something reasonable and hope it is good enough. The only real solution (as we will see in forthcoming chapters) is to avoid the problem altogether, by never allocating memory in variable-sized chunks.