[4] Address Space & Address Translation

Back in the day, early machines didn't really offer much in terms of user-friendly features. Basically, the physical memory of the machine looked something like this:

The OS was a set of routines (like a library) that stayed in memory (starting at physical address 0 in this example). There would be one running program (a process) that used the rest of the memory (starting at physical address 64k in this example). There weren't many expectations from the OS, and users didn't expect much. Life was simple for OS developers back then, wasn't it?

Multiprogramming and Time Sharing

After a while, since machines were costly, people started sharing them more efficiently. This led to the era of multiprogramming, where multiple processes were ready to run at the same time, and the OS would switch between them.

Soon, people wanted more from machines, leading to time sharing. as many users needed quick responses from their tasks.

One way to implement time sharing is to run one process for a short time, giving it full access to all memory. Then, stop it, save its state to a disk (including all of its memory), load another process's state, run it for a while, and repeat. This creates a basic form of sharing the machine.

Unfortunately, this approach has a big problem: it is too slow, especially as memory grows. Saving and restoring register-level state (like the PC and general-purpose registers) is fast, but saving all of the memory to disk is very slow. So, it's better to keep processes in memory while switching between them, which lets the OS handle time sharing more efficiently.

In the diagram, there are three processes (A, B, and C), each using a small part of the 512KB physical memory. With a single CPU, the OS runs one process (let's say A), while the others (B and C) wait in the ready queue.

As time sharing became more popular, new demands were placed on the operating system. Allowing multiple programs to be in memory at the same time made protection important. You don't want a process to read or, worse, write into another process's memory.

The Address Space

In an operating system, one of the main jobs is to manage how programs use memory. To do this, the OS provides a simple view of the physical memory called the address space. The address space makes each running program think it has its own private and continuous memory block, even though this isn't actually the case.

The address space of a process includes all the memory required by a running program. It consists of three key segments: the code (which contains the program’s instructions), the stack (used for managing function calls, local variables, and passing parameters), and the heap (which handles dynamically-allocated memory, such as memory allocated with malloc() in C or new in C++ and Java).

To better understand, imagine a small address space of just 16KB. The code resides at the top of this space, occupying the first 1KB, and is static, meaning it won’t change during execution. Below that, the heap begins, growing downward as the program requests more memory. At the bottom of the address space is the stack, which grows upward as the program makes function calls. This opposite growth of the stack and heap allows for dynamic adjustment of memory during runtime.

However, this address space layout is only an abstraction provided by the OS. The actual physical memory where the program is loaded could be completely different. For instance, in a system with multiple running processes, each process may believe its memory starts at virtual address 0, but the OS maps this virtual memory to different physical memory locations for each process. This concept is known as memory virtualization.

For example, if process A requests to access virtual address 0, the OS—working with hardware support—maps that request to a different physical address, such as 320KB, where process A is actually loaded in memory. This technique allows the OS to manage multiple processes efficiently and securely, ensuring that each program operates within its own isolated memory space without interfering with others.

Thus, for the OS to virtualize memory, it needs to do so effectively. The OS will not only virtualize memory but will do it efficiently. To ensure this, we need some goals to guide us.

1. Transparency:

   • The goal is to make virtualization invisible to running programs.

   • A program should behave as though it has exclusive access to physical memory, unaware that the memory it’s using is virtualized.

   • The OS and hardware manage the sharing of physical memory across multiple processes.

   • This creates the illusion that each process has its own dedicated memory, simplifying the programmer’s job.

2. Efficiency:

   • Virtual memory must be efficient.

   • The OS needs to ensure that virtualizing memory does not significantly slow down program execution or consume excessive memory.

   • Time efficiency focuses on minimal performance impact, often achieved through hardware mechanisms like Translation Lookaside Buffers (TLBs).

   • Space efficiency ensures that the structures supporting virtualization don’t waste too much of the system’s memory.

3. Protection:

   • Virtual memory must maintain protection.

   • Each process must be protected from the memory access of other processes and unauthorized access to the OS.

   • By isolating each process within its own address space, the OS ensures no process can interfere with another’s memory.

   • This isolation is crucial for preventing faulty or malicious processes from causing harm, maintaining system stability and security.

EVERY ADDRESS YOU SEE IS VIRTUAL

Have you ever written a C program that prints a pointer? The value you see is a virtual address. Wonder where your program's code is located? You can print that too, and it's also a virtual address. Any address you see as a user-level programmer is virtual. Only the OS knows the real physical location. So remember: if you print an address in a program, it's virtual.

Here’s a simple program that prints the locations of the main() function (where the code is), a heap-allocated value from malloc(), and an integer on the stack:

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
    printf("location of code  : %p\n", (void *) main);
    printf("location of heap  : %p\n", (void *) malloc(1));
    int x = 3;
    printf("location of stack : %p\n", (void *) &x);
    return x;
}

When we run the above code , we get the following output:

location of code  : 0x1095afe50
location of heap  : 0x1096008c0
location of stack : 0x7fff691aea64

From this, you can see the code is first in the address space, followed by the heap, and the stack is at the far end. All these addresses are virtual and are translated by the OS and hardware to their actual physical locations.

To better understand how memory is managed and how to use malloc() and free() in C, read the following article.

Address Translation

Address translation is a hardware technique that converts virtual addresses used by programs into physical addresses in memory. Whenever a program accesses memory—whether fetching instructions, loading, or storing data—the hardware performs this translation to locate the data. The operating system plays a crucial role in managing memory, configuring the hardware, and ensuring that translations are accurate. This process creates this beautiful illusion that allows programs to operate as if they have their own private memory, even though multiple programs share the same physical memory as the CPU switches between them.

To explain the concept of address translation and process relocation simply, let’s break it down:

Let’s look at an example. A process has an address space of 16KB. It includes program code, a heap for dynamic memory, and a stack for local variables, like our variable x = 3000. The program will load x into a register, add 3 to it, and store the result back into memory. In this process’s address space, everything is organized from address 0 to 16KB.

However, in reality, the OS doesn’t place the process’s address space at physical address 0. Instead, the OS places the process at a different location in physical memory, say starting at 32KB, while keeping other memory areas, like 0–16KB, for itself. In next figure, this process is relocated into physical memory starting at 32KB.

The challenge is how to make this relocation transparent to the process so that it still thinks it’s operating from address 0. This is where address translation comes in, ensuring the program can continue executing as if its address space starts at 0, even though it’s placed elsewhere in physical memory.

Dynamic Relocation: Foundations of Virtual Memory

Dynamic relocation, also known as base and bounds, is a fundamental technique in computer memory management. Introduced in the late 1950s with the first time-sharing machines, it solved a critical problem: how to efficiently use physical memory while keeping processes isolated from each other.

The Core Concept

At its heart, dynamic relocation is about creating an illusion—a virtual memory space for each process. It translates the addresses a program "thinks" it's using (virtual addresses) into the actual locations in physical memory (physical addresses). This translation happens in real-time as the program runs, hence the term "dynamic".

Hardware Components

The magic of dynamic relocation relies on two special hardware registers in the CPU:

1. Base Register: Holds the starting physical address where the program is loaded.

2. Bounds Register (or Limit Register): Contains the size of the program's address space.

These registers are part of what we call the Memory Management Unit (MMU), a crucial component in modern CPUs.

How It Works

1. Program Compilation: Programs are compiled as if they'll be loaded at address 0.

2. Loading: The operating system decides where to load the program in physical memory.

3. Setting Up: The OS sets the base register to the chosen starting address and the bounds register to the program's size.

4. Address Translation: For every memory access, the CPU adds the content of the base register to the virtual address.

   Formula: Physical Address = Virtual Address + Base Register

Protection Mechanism

The bounds register plays a crucial role in memory protection:

• Before any address translation, the CPU checks if the virtual address is within the bounds.

• If a program tries to access memory outside its allocated space, the CPU raises an exception, typically resulting in the program's termination.

An Illustrative Example

Imagine a program with a 4 KB address space loaded at physical address 16 KB:

• Base Register = 16 KB

• Bounds Register = 4 KB

Address translations would work like this:

• Virtual Address 0 → Physical Address 16 KB

• Virtual Address 1 KB → Physical Address 17 KB

• Virtual Address 3000 → Physical Address 19384

• Virtual Address 4400 → Fault (out of bounds)

Hardware Support

Dynamic relocation requires specific hardware features to function effectively:

1. CPU Modes:

   • Two modes: Privileged (kernel) mode and User mode

   • A status bit indicates the current mode

   • Mode switches occur during system calls, exceptions, or interrupts

2. Address Translation and Bounds Checking:

   • Hardware circuitry to add the base value and check bounds

3. Privileged Instructions:

   • Special instructions to modify base and bounds registers

   • Only accessible in kernel mode

4. Exception Handling:

   • Generate exceptions for illegal memory access or privileged instruction attempts

   • Ability to set up exception handlers

Operating System Responsibilities

The OS must manage several aspects to implement dynamic relocation:

1. Process Creation:

   the OS must take action when a process is created

   • Find space in physical memory for the new process

   • Update a "free list" data structure to track available memory

   • Mark the allocated space as used

2. Process Termination:

   The OS must take action when a process ends (either gracefully or because it was forcefully killed for misbehaving).

   • Reclaim the process's memory

   • Add the freed memory back to the free list

   • Clean up associated data structures

3. Context Switching:

   • Save and restore base and bounds registers for each process

   • Update these values in the process control block (PCB)

4. Memory Management:

   • Ability to move a process's address space when it's not running

   • Update the saved base register value after moving

5. Exception Handling:

   • Install exception handlers at boot time

   • Handle illegal memory access attempts (usually by terminating the offending process)

Benefits and Implications

1. Flexibility: Programs can be loaded anywhere in physical memory.

2. Isolation: Each program is confined to its own memory space.

3. Simplicity: The translation mechanism is straightforward and fast.

4. Illusion of Exclusive Memory: Each program feels like it has the entire memory to itself, starting from address 0.

Limitations

Despite its usefulness, dynamic relocation has some drawbacks:

1. Internal Fragmentation: Fixed-size memory allocation can lead to wasted space within allocated blocks.

2. Inflexibility: The entire process must be loaded into contiguous physical memory.

Conclusion

Dynamic relocation provides a foundation for virtual memory systems, offering a balance of simplicity and effectiveness. It introduced key concepts like address translation and memory protection, paving the way for more advanced memory management techniques like segmentation and paging. While modern systems have evolved beyond this simple model, understanding dynamic relocation is crucial for grasping the fundamentals of memory virtualization in operating systems.

As we move forward in the field of operating systems, we build upon these foundational concepts, always striving for more efficient, flexible, and secure ways to manage our computer's resources. Dynamic relocation, although now replaced by more advanced methods, shows the cleverness of early computer scientists and is an important step in the development of memory management.