Chapter 13: Early Systems

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 Early Systems.
• Work through the source examples for Early Systems without depending on raw chunk order.
• Use Early Systems as selective reference when learner modules point back to Ostep.

Prerequisites

• Earlier prerequisite concepts leading into Chapter 13: Early Systems.

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 13: Early Systems". 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 13: Chapter 13: Early Systems
• Raw source file: 055-13-1-early-systems.md
• Raw source file: 056-13-3-the-address-space.md

Merged source

Early Systems

13.1 Early Systems

13 The Abstraction: Address Spaces

In the early days, building computer systems was easy. Why, you ask?

Because users didn't expect much. It is those darned users with their expectations of "ease of use", "high performance", "reliability", etc., that really have led to all these headaches. Next time you meet one of those computer users, thank them for all the problems they have caused.

From the perspective of memory, early machines didn't provide much of an abstraction to users. Basically, the physical memory of the machine looked something like what you see in Figure 13.1.

The OS was a set of routines (a library, really) that sat in memory (starting at physical address 0 in this example), and there would be one running program (a process) that currently sat in physical memory (starting at physical address 64k in this example) and used the rest of memory.

There were few illusions here, and the user didn't expect much from the

OS. Life was sure easy for OS developers in those days, wasn't it?

0KB

Operating System

(code, data, etc.)

64KB

Current Program

(code, data, etc.)

max

Figure 13.1:Operating Systems: The Early Days 1

(code, data, etc.)

64KB

(free)

128KB

Process C

(code, data, etc.)

192KB

Process B

(code, data, etc.)

256KB

(free)

320KB

Process A

(code, data, etc.)

384KB

(free)

448KB

(free)

512KB

Figure 13.2:Three Processes: Sharing Memory

13.2 Multiprogramming and Time Sharing

After a time, because machines were expensive, people began to share machines more effectively. Thus the era ofmultiprogrammingwas born

[DV66], in which multiple processes were ready to run at a given time, and the OS would switch between them, for example when one decided to perform an I/O. Doing so increased the effective utilization of the

CPU. Such increases inefficiency were particularly important in those days where each machine cost hundreds of thousands or even millions of dollars (and you thought your Mac was expensive!).

Soon enough, however, people began demanding more of machines, and the era oftime sharingwas born [S59, L60, M62, M83]. Specifically, many realized the limitations of batch computing, particularly on programmers themselves [CV65], who were tired of long (and hence ineffective) program-debug cycles. The notion ofinteractivitybecame important, as many users might be concurrently using a machine, each waiting

for (or hoping for) a timely response from their currently-executing tasks.

One way to implement time sharing would be to run one process for a short while, giving it full access to all memory (Figure 13.1, page 1), then stop it, save all of its state to some kind of disk (including all of physical memory), load some other process's state, run it for a while, and thus implement some kind of crude sharing of the machine [M+63].

Unfortunately, this approach has a big problem: it is way too slow, particularly as memory grows. While saving and restoring register-level state (the PC, general-purpose registers, etc.) is relatively fast, saving the entire contents of memory to disk is brutally non-performant. Thus, what we'd rather do is leave processes in memory while switching between them, allowing the OS to implement time sharing efficiently (Figure 13.2).

Program Code where instructions live 1KB the heap segment:

Heap contains malloc'd data dynamic data structures 2KB

(it grows downward)
(free)
(it grows upward)

the stack segment:

15KB contains local variables arguments to routines,

Stack return values, etc.

16KB

Figure 13.3:An Example Address Space

In the diagram, there are three processes (A, B, and C) and each of them have a small part of the 512KB physical memory carved out for them. Assuming a single CPU, the OS chooses to run one of the processes (say A), while the others (B and C) sit in the ready queue waiting to run.

As time sharing became more popular, you can probably guess that new demands were placed on the operating system. In particular, allowing multiple programs to reside concurrently in memory makesprotectionan important issue; you don't want a process to be able to read, or worse, write some other process's memory.

---

The Address Space

13.3 The Address Space

However, we have to keep those pesky users in mind, and doing so requires the OS to create aneasy to useabstraction of physical memory.

We call this abstraction theaddress space, and it is the running program's view of memory in the system. Understanding this fundamental OS abstraction of memory is key to understanding how memory is virtualized.

The address space of a process contains all of the memory state of the running program. For example, thecodeof the program (the instructions) have to live in memory somewhere, and thus they are in the address space. The program, while it is running, uses astackto keep track of where it is in the function call chain as well as to allocate local variables and pass parameters and return values to and from routines. Finally, the heapis used for dynamically-allocated, user-managed memory, such as that you might receive from a call tomalloc()in C ornewin an objectoriented language such as C++ or Java. Of course, there are other things in there too (e.g., statically-initialized variables), but for now let us just assume those three components: code, stack, and heap.

In the example in Figure 13.3 (page 3), we have a tiny address space (only 16KB)1. The program code lives at the top of the address space (starting at 0 in this example, and is packed into the first 1K of the address space). Code is static (and thus easy to place in memory), so we can place it at the top of the address space and know that it won't need any more space as the program runs.

Next, we have the two regions of the address space that may grow (and shrink) while the program runs. Those are the heap (at the top) and the stack (at the bottom). We place them like this because each wishes to be able to grow, and by putting them at opposite ends of the address space, we can allow such growth: they just have to grow in opposite directions. The heap thus starts just after the code (at 1KB) and grows downward (say when a user requests more memory viamalloc()); the stack starts at 16KB and grows upward (say when a user makes a proce-

dure call). However, this placement of stack and heap is just a convention;

you could arrange the address space in a different way if you'd like (as we'll see later, when multiple threadsco-exist in an address space, no nice way to divide the address space like this works anymore, alas).

Of course, when we describe the address space, what we are describing is theabstractionthat the OS is providing to the running program.

The program really isn't in memory at physical addresses 0 through 16KB; rather it is loaded at some arbitrary physical address(es). Examine processes A, B, and C in Figure 13.2; there you can see how each process is loaded into memory at a different address. And hence the problem:

THECRUX: HOWTOVIRTUALIZEMEMORY

How can the OS build this abstraction of a private, potentially large address space for multiple running processes (all sharing memory) on top of a single, physical memory?

When the OS does this, we say the OS isvirtualizing memory, because the running program thinks it is loaded into memory at a particular address (say 0) and has a potentially very large address space (say 32-bits or 64-bits); the reality is quite different.

When, for example, process A in Figure 13.2 tries to perform a load at address 0 (which we will call avirtual address), somehow the OS, in tandem with some hardware support, will have to make sure the load doesn't actually go to physical address 0 but rather to physical address 320KB (where A is loaded into memory). This is the key to virtualization of memory, which underlies every modern computer system in the world.

1We will often use small examples like this because (a) it is a pain to represent a 32-bit address space and (b) the math is harder. We like simple math.

TIP: THEPRINCIPLE OFISOLATION

Isolation is a key principle in building reliable systems. If two entities are properly isolated from one another, this implies that one can fail without affecting the other. Operating systems strive to isolate processes from each other and in this way prevent one from harming the other. By using memory isolation, the OS further ensures that running programs cannot affect the operation of the underlying OS. Some modern OS's take isolation even further, by walling off pieces of the OS from other pieces of the OS. Suchmicrokernels[BH70, R+89, S+03] thus may provide greater reliability than typical monolithic kernel designs.

13.4 Goals

Thus we arrive at the job of the OS in this set of notes: to virtualize memory. The OS will not only virtualize memory, though; it will do so with style. To make sure the OS does so, we need some goals to guide us.

We have seen these goals before (think of the Introduction), and we'll see them again, but they are certainly worth repeating.

One major goal of a virtual memory (VM) system istransparency2.

The OS should implement virtual memory in a way that is invisible to the running program. Thus, the program shouldn't be aware of the fact that memory is virtualized; rather, the program behaves as if it has its own private physical memory. Behind the scenes, the OS (and hardware) does all the work to multiplex memory among many different jobs, and hence implements the illusion.

Another goal of VM isefficiency. The OS should strive to make the virtualization asefficientas possible, both in terms of time (i.e., not making programs run much more slowly) and space (i.e., not using too much memory for structures needed to support virtualization). In implementing time-efficient virtualization, the OS will have to rely on hardware support, including hardware features such as TLBs (which we will learn about in due course).

Finally, a third VM goal isprotection. The OS should make sure to protect processes from one another as well as the OS itself from processes. When one process performs a load, a store, or an instruction fetch, it should not be able to access or affect in any way the memory contents of any other process or the OS itself (that is, anythingoutsideits address space). Protection thus enables us to deliver the property of isolation among processes; each process should be running in its own isolated cocoon, safe from the ravages of other faulty or even malicious processes.

2This usage of transparency is sometimes confusing; some students think that "being transparent" means keeping everything out in the open, i.e., what government should be like.

Here, it means the opposite: that the illusion provided by the OS should not be visible to applications. Thus, in common usage, a transparent system is one that is hard to notice, not one that responds to requests as stipulated by the Freedom of Information Act.