After a bit of an unexpected break, I have been able to get back to my operating systems study. So, let’s take a look at some of the key ideas in chapter 2 of the xv6 book!
Operating System Organization Link to heading
In the introduction to the chapter, the authors claim:
[A]n operating system must fulfill three requirements: multiplexing, isolation, and interaction.
Multiplexing refers to multiple programs being able to run on the computer, ideally without any one program hogging time or resources. Isolation means that the operating system must protect programs from one another. And, interaction means that the OS must allow programs to communicate with each other in a safe manner.
The rest of the chapter describes how operating system kernels are organized to meet these requirements, with xv6 as an example.
Multiplexing Link to heading
An operating system must support scheduling the execution of potentially many independent programs, allowing each program to have a fair share of system resources, such as processor time. This should be true even in the case where the number of programs executing is greater than the number of physical processors in the computer - a very common situation!
One could imagine a scenario where each program would run for a period of time and then yield to other programs. This arrangement is known as cooperative scheduling. Although it could work in some applications (for example, embedded systems), it is not a good idea to assume that all programs running on a computer will cooperate with one another in this way. It also makes programs more complex to write.
Instead, an operating system maintains some state for each program. The abstraction is called the process, which is the fundamental unit for both multiplexing and isolation. The OS runs a process for a while, then saves its state (like registers and the stack) before switching to another. Each process is not aware of this swapping: the kernel handles it for them.
Isolation Link to heading
In addition to the runtime state, like stack and register values, each process is given its own address space. Other processes cannot access this address space, so that they cannot view or change data in this process’s memory.
xv6, like other Unixes, provide processes with virtual addresses rather than physical addresses to reference memory. When a process requests the contents of some virtual address, vA, the kernel and the processor work together to map this to a physical address, pB.
By multiplexing processes and providing each with its own address space, Unix gives each process the illusion that it is the only one running on its own machine. This abstraction simplifies programs by hiding physical memory details from the process. For instance, virtual memory means that each process will believe its memory starts at address 0 and goes all the way up to the total memory on the system. Compilers, then, can use these virtual addresses to put static data and stack elements at the same virtual address in all executions of the process, while the OS and hardware actually do the translation to make this work.
Hardware Support for Isolation Link to heading
The OS and hardware work closely to provide isolation. Not only must processes be protected from one another, but even more importantly, the kernel must be protected from buggy or malicious programs as well. If a process were to attempt to write to a memory address owned by the kernel, the processor should detect that and return execution back to the kernel by way of a page fault. The kernel may then handle the access violation, typically by terminating the offending process. The implementation here relies on page tables, and since those are the subject of chapter 3, there will be more to come there in the next post of the series.
Additionally, though, instructions can be run in one of several modes. Because xv6 is designed to run on RISC-V processors, there are three modes to be aware of: machine mode, supervisor mode, and user mode. Other architectures have similar concepts, but with different names and details.
Machine mode is typically reserved for the process of booting a computer up; instructions in machine mode have full access to the system, which is required in the process of starting up the operating system. Supervisor mode is the common mode of operation for kernel tasks, such as system calls. Here, the kernel can read and write interrupts and make adjustments to the page table. User mode is where typical user applications run. Attempts to execute privileged instructions while in user mode will trigger the processor to return execution to the kernel, so that it can handle it.
Interaction Link to heading
The chapter does not spend much time on the third requirement, but does state that processes should not be completely isolated from one another. There are times where two or more processes need to collaborate. The OS provides communication mechanisms, such as pipes (discussed in chapter 1), to allow such interaction.
Exercise: Adding a System Call to xv6 Link to heading
The chapter ends with an exercise:
Add a system call to xv6 that returns the amount of free memory available.
I think this is an open-ended exercise, but I took it to mean to provide a system call that would allow implementing a minimal version of the free command available on many Unix systems. In other words, rather than returning the available memory within a process, it should return the amount of free memory on the entire system.
My implementation can be found in this pull request.
After reviewing the existing code for a bit, along with the description of the xv6 kernel layout in the chapter, I found that memory appears to be managed by the kmem struct. kmem contains a lock and a linked list of free pages. So, my hypothesis was, if I could keep track of the size of this list as memory was both allocated (i.e., the free list got smaller) and freed (i.e., the free list got larger), then the amount of free memory should be
(Number of free pages) × (Page size)
The exercise turned out to be a simple but satisfying way to better understand memory tracking in xv6.
Conclusion Link to heading
The chapter provides a nice overview of some of the key considerations for OS (and xv6) organization. I did not summarize it here, but probably half the chapter is very focused on xv6 organization, which was useful in doing the exercise. I anticipate the rest of the book will go deeper into the implementation of the three core requirements listed at the outset of the chapter: multiplexing, isolation, and interaction.
Chapter 3 dives into Page Tables and includes several exercises, making it more hands-on than the first two. It should be fun!