This is my notes from Chapter 15 - Mechanism: Address Translation from the book Operating Systems: Three Easy Pieces.

The chapter starts off by recapping LDE (Limited Direct Execution), a way to execute programs directly on the CPU and check the program’s execution in a timely fashion through timer interrupts or when the program invokes a system call. Then the book discusses the importance of memory virtualization:

1. To avoid the processes accessing each other's memory.
2. To prevent the processes from accessing the OS’s memory itself.

This chapter is all about a simple strategy for memory virtualization: Hardware-based Address Translation or simply, Address Translation. Just like how LDE works with support from hardware (timer interrupts, system calls, etc) this strategy works with support from hardware. Every program assumes that its address space starts from 0 (which is virtual) but the actual physical address space of the program may not necessarily be 0. This virtual address will be translated to the actual physical address during the program execution with support from hardware.

The chapter lays a few assumptions for a simplistic explanation of the strategy:

1. The physical address where the program executes is contiguous.
   • This assumption avoids the need to discuss segmentation, etc.
2. The size of the address space is not too large than the size of physical memory.
3. The address space of every program is exactly the same size.
   • This makes it easy to deal with allocation as we can assume the physical memory as fixed-sized chunks.

How does Address Translation Work?

Each address in the program gets converted to the physical address when each instruction is executed. Let’s say the OS allocates address space from 32KB to 64KB. The program assumes its address space starts at 0. So for every instruction, the address gets incremented by 32KB (which is where the program is actually running). This ensures that the data the program reads/writes is from the actual physical address. This translation is done with the help of hardware.

The book explains this with an example:

void func() {
	int x = 3000;
	x = x + 3;
}

The x86 assembly for the above C code looks like this:

128: movl 0x0 (%ebx), %eax ; load 0+ebx into eax
132: addl $0x3, %eax       ; add 3 to eax register
135: movl %eax, 0x0 (%ebx) ; store eax back to ebx (variable x)

The program’s address space may look like this:

Address Space Stack