Lecture Overview

One piece missing from our mental model of how the computer works is the operating system kernel. The kernel provides several basic features. The following is a highly simplified explanation but provides a good basic mental model of what happens.

Scheduling

• The circuits inside the CPU have a fetch-decode-execute cycle and to the CPU it just continuously fetches, decodes, and executes instructions.
• Memory is a large collection of cells, each cell contains a piece of data. Some cells contain instructions.
• There is a very important instruction called a jump instruction. The jump instruction tells the CPU to change where the next instruction is fetched from. Usually the instructions are fetched one by one from consecutive cells in memory. The jump instruction gives the CPU a new memory address which causes the CPU to instead start fetching from the given address. This has the effect of causing the CPU to "jump" somewhere else in memory.
• Consider the situation when you have multiple processes running, say for simplicity firefox and powershell. The instructions for firefox are in some part of memory and the instructions for powershell are in a different part. Only one process can be running at a single time (whichever process owns the memory where the CPU is currently fetch-decode-executing).
  • To simulate multiple processes running at the same time, we need to make the CPU jump back and forth between the two processes. This is the job of the kernel. This usually happens on the order of once every 1/1000 second. The CPU will fetch-decode-execute from firefox for a while, jump to powershell to execute for a while, jump back to firefox, and so on. If there are more than two processes, they will all get a chance to run a little bit before jumping to the next process. Since this happens every 1/1000 second, to us users it seems like multiple processes run at the same time when in reality only one process is running at any instant in time.
  • The operating system kernel is in charge of this jumping between processes and this called scheduling.
    • Older operating systems (and still some embedded real-time operating systems) used what is called cooperative scheduling. In this model, the processes have to contain periodic jumps into the operating system kernel. The operating system kernel then has code to determine which process to run next (based on time since last execution, priorities, etc.) and after deciding which process to run next it would jump into that process.
    • All modern general purpose operating systems (Windows, MacOS X, Linux, Android, etc.) use what is called preemptive scheduling. The CPU has a periodic timer tick. This is a timer inside the circuits of the CPU that counts down while the CPU is fetch-decode-executing from a process like firefox. Once the timer reaches zero, the CPU automatically jumps into the operating system kernel. The kernel will then decide which process to run next, reset the timer (usually for 1/1000 of a second), and jump to the process it decided to run. The kernel will bend over backwards to make the process think that no interruption occurred. (This is because the timer could hit zero at any moment so between any two firefox instructions the CPU fetch-decode-execute cycle could jump away.)

Syscalls

The kernel also provides many standardized routines to processes called system calls or syscalls for short. Programs can take advantage of these routines by using an instruction to jump into the kernel. There are many different syscalls available:

• Files and filesystems. A process can make a syscall to read or write data to a file.
• Input/Output to devices like printers, keyboard, sound card, networking, etc. For example, to write sound to the sound card, instead of sending the data directly on the system bus the process makes a syscall (i.e. a jump) into the kernel. The code within the kernel then takes care of sending the sound data to the sound card. This facilitates device independence. Different sound cards might need different instructions to access but the process syscalls into the kernel the in the same way no matter what kind of sound card is available. The kernel has what is called a device driver which knows about the specifics of the card and what kind of instructions are needed to send it data. This isolation lets programs like firefox be written which work on all kinds of hardware, since the specific details are in the kernel device drivers.
• Process creation and process kill. That is, to start a new process an existing process will make a syscall (jump into the kernel). The code inside the kernel will then take care of finding an unused portion of memory, loading this memory with the code of the process, and marking that the process is now available for scheduling.
• Many others, some of which we will cover later this semester.

The kernel can enforce security by limiting which syscalls a process can execute. For example, if only some processes are allowed to play sound, when some program syscalls into the kernel, the kernel can check if the process has permission before actually sending the sound data out to the sound card. Similarly, when a process syscalls into the kernel to access a file the permissions can be checked.

Memory Management

I've already hinted at it above, but the final major task the kernel is to be in charge of managing memory. The kernel keeps track of which process is using which piece of memory. A process can make a syscall into the operating system kernel asking for more memory and the kernel will find some unused memory and let the process know it can use it. The kernel is also in charge of protection to not allow one process to use another processes memory. This serves two purposes. First, it provides security so that the data like your bank password in one process cannot be accessed by another process. Second, this protects against bugs in one program taking out many other processes. If a process contains a bug (ok, more like when a process hits a bug since all programs have bugs) it might start writing to random locations in memory. If it writes into memory owned by a different process this will cause that process to malfunction. By protecting a process to only access its own memory, a bug in a single program just limits itself to that program.

The kernel enforces this protection via a complex mechanism called Virtual Memory which is outside the scope of this simple model I presented.

Exercises

No homework, but you could easily imagine several exam questions from the above material. For example, in 3-5 sentences explain what is a syscall.

It is not required for the course, but if you are interested, this book provides a nice introduction to operating systems. Not quite a textbook (the definitive textbook is this textbook), but Linux Kernel Development gives a good overview of an operating system. Despite its name, Linux Kernel Development is a good overview of all modern operating systems, not just Linux. It happens to use Linux as an example, but focuses on concepts.