Address spaces using segments

This lecture is about virtual memory, focusing on address spaces. It is the first lecture out of series of lectures that uses xv6 as a case study.

Address spaces

Example hardware for address spaces: x86 segments

PC block diagram without virtual memory support:

The x86 starts out in real mode and translation is as follows:

The operating system can switch the x86 to protected mode, which allows the operating system to create address spaces. Translation in protected mode is as follows:

Next lecture covers paging; now we focus on segmentation.

Protected-mode segmentation works as follows:

Case study (xv6)

xv6 is a reimplementation of Unix 6th edition.

Newer Unixs have inherited many of the conceptual ideas even though they added paging, networking, graphics, improve performance, etc.

You will need to read most of the source code multiple times. Your goal is to explain every line to yourself.

Overview of address spaces in xv6

In today's lecture we see how xv6 creates the kernel address spaces, first user address spaces, and switches to it. To understand how this happens, we need to understand in detail the state on the stack too---this may be surprising, but a thread of control and address space are tightly bundled in xv6, in a concept called process. The kernel address space is the only address space with multiple threads of control. We will study context switching and process management in detail next weeks; creation of the first user process (init) will get you a first flavor.

xv6 uses only the segmentation hardware on xv6; it doesn't use paging. (In JOS you will use page-table hardware too, which we cover in next lecture.)

The x86 designers probably had in mind more interesting uses of segments. What might they have been?

In xv6, each each program has a user stack and a kernel stack; when the user program switches to the kernel, it switches to its kernel stack. The switch is arranged with the TSS, which is covered later.

Since an xv6 process's address space is essentially a single segment, a process's physical memory must be contiguous. So xv6 may run into fragmentation if process sizes are a significant fraction of physical memory.

xv6 kernel address space

Let's see how xv6 creates the kernel address space by tracing xv6 from when it boots, focusing on address space management:

creating the first process's address space

running the first process

Managing physical memory

To create an address space we must allocate physical memory, which will be freed when an address space is deleted (e.g., when a user program terminates). xv6 implements a first-fit memory allocator (see kalloc.c, sheet 22).

It maintains a list of ranges of free memory. The allocator finds the first range that is larger than the amount of requested memory. It splits that range in two: one range of the size requested and one of the remainder. It returns the first range. When memory is freed, kfree will merge ranges that are adjacent in memory.

Under what scenarios is a first-fit memory allocator undesirable?

Growing an address space

How can a user process grow its address space? growproc.

We could do a lot better if segments didn't have to contiguous in physical memory. How could we arrange that? Using page tables, which is our next topic. This is one place where page tables would be useful, but there are others too (e.g., in fork).