Operating Systems #2 — Operating System Overview

The last post was about the machine. This one is about the software that sits on top of it.

Multiprogramming and multitasking

Multiprogramming exists to keep the CPU from waiting needlessly. A single application can't keep the CPU busy all the time, so the idea is to spend the waiting time running another application and raise utilization.

For that, every program has to be in memory — which is effectively impossible. Hence virtual memory: a running program doesn't need to be resident in full, only the part that has to run right now. Each program takes less space, so more of them fit. When that still isn't enough, a resident program is pushed out to disk and a new one brought in (swapping). It has to write to disk, so it's slow.

Once you have multiprogramming, multitasking becomes possible. Even with no I/O, when a program's time is up the CPU is taken away and handed to another. Several programs share the CPU's time — time sharing. Response time has to be small enough for the user to perceive them as running simultaneously.

To summarize:

• Multiprogramming — using multiple processes so the CPU never rests, raising utilization.
• Multitasking — making multiple processes appear to run at the same time.

OS operation

What the OS does falls into three groups.

Handling hardware interrupts. Interrupts from I/O devices get handled. Later the timer device also sends interrupts, with no I/O involved. Spinning in an infinite loop for a device like a keyboard — where you have no idea when input arrives — is inefficient, so the device raises an interrupt when input comes and the CPU handles it then.

Software errors and requests. Something urgent, unrelated to I/O, can require interrupting the running software. Division by zero, say. The CPU is fast enough that the ripple effect of an error spreads very quickly, so it has to be handled fast. This is an exception or trap, and it's handled much like an interrupt.

An exception is an error condition; a trap arises from a request (to get handling done). I came away understanding interrupt in the broad sense as covering hardware interrupts, exceptions, and traps.

Dual mode. An application doesn't only run code the user wrote. Take printf apart and at the end there's an instruction asking the OS to do the output. Printing to screen means touching the display device, and hardware access is controlled by the OS for security. The way to ask the OS is a system call.

System call code is OS code, not application code the user wrote, and its privileges differ. OS code is trusted, so it may touch hardware directly; user code has weaker privilege. But the CPU just fetches instructions from memory and runs them — it can't tell OS code from user code. So the mode bit in PSW is used. While a user application runs, it's user mode; calling a system call switches to kernel mode before the call executes.

The flow:

user process running
  → system call invoked
  → trap, mode bit = kernel mode
  → system call executes
  → on return, mode bit = user mode, result returned
  → back in the user process

Every system call is a user → kernel mode transition.

The OS's components

Process management

A process is a program in execution — more precisely, the OS's materialization of a running program under the name "process." A program needs a CPU, memory, I/O, files, and the data defined inside the program. The OS provides a data structure that bundles all of it together, and that structure is the process. Think of a cafeteria tray with its sections.

When the user double-clicks something, the OS builds the process structure, fills it in, and loads it into memory, then registers it for CPU scheduling. When scheduling grants it the CPU the program runs, and when it's done the process terminates — that is, the structure is deleted.

A single-threaded process has one PC; a multithreaded one has a PC per thread.

For process management the OS creates and deletes processes, suspends running ones, does process synchronization, provides interprocess communication, and handles deadlock.

Memory management

All data and instructions must be in memory. With several processes resident, the OS tracks which process is where and which regions are free. Concretely: managing the memory layout, deciding what to swap in and out, allocating memory for a new process, and dynamic allocation during execution (malloc and friends).

Storage and the file system

Disk space is complicated enough that direct user access would be too hard, so the OS makes it simple: "applications only need to know about files — you don't need to know what a hard disk looks like." You write to a file and the OS stores it for you. That's why we have no idea where on disk our data lands.

File-system management covers how files are maintained, how they're stored (hence the directory concept), and what operations to expose to the user — creating and deleting files and directories, changing file data, storing files on secondary storage, backing them up.

Beneath that sits mass storage management. The OS has to know the free space, the used space, and which file lives where. Disk scheduling belongs here too: reordering I/O requests to minimize movement of the disk head.

Caching and consistency

Data travels disk → memory → cache → register on its way to the CPU. The problem is that many programs are running at once. A datum might be in cache or in memory, and every program must operate on its latest value. The OS has to guarantee that.

More cores makes it harder (cache coherency). In a distributed system it's worse still: the same work split across machines means the same data on each, and the values can diverge. Protocols have to be written with that in mind.

I/O management

I/O devices vary by type and by manufacturer. The OS's job is to make sure users don't have to distinguish between all those characteristics. A user only distinguishes block device from character device. Disk, SSD, USB stick, CD-ROM — you just say you want to write to a block device.

And the OS provides software that compensates for how slow I/O devices are: buffering, caching, and spooling. Printers are slow, so when printing a document the data is written to a spool area; the application moves on and the OS feeds the printer at the printer's pace.

Protection and security

Security here means defence against attack. Protection is the mechanism that stops someone without authority from reaching a resource outside their authority.

Every user gets a userID and that ID carries privileges. A file you created is fully yours by default, and you can configure what privileges others get on it. When a user logs in, programs they run inherit their privileges — the same application has different power depending on whether an ordinary user or root launched it.

There are groupIDs as well as userIDs, so users can be bundled and given group-level access. And there's privilege escalation, for when a program temporarily needs authority it doesn't have. Print spooling is the example: the spool is OS territory, so the user can't write there freely, and the program is lent the privilege for the duration of the print job.

Operating system services and system calls

The OS does its work on request from the user — that is, it provides services that the user can ask for. Creating a process is offered as the fork system call.

The services include: user interface, program execution, I/O operations, file-system services, communication (data exchange between processes and over the network), error detection and handling, resource allocation, accounting (tracking how much of the system a user consumes), and protection and security.

System calls are primitive

System calls are very simple. printf internally calls the write() system call. Calling write() directly to print something would mean composing several calls, because write() is so primitive. That's complicated, so a high-level API like printf makes it easy.

There's a second reason for APIs. System calls come from the OS, so the same job has different names and conventions on different systems. Using system calls directly means rewriting the program per OS; using an API means one source tree. (You still compile separately per OS.) UNIX-family systems share one API, POSIX.

APIs come in two kinds. One is provided by the programming language, like C's printf — very portable. The other is a standard API for an OS family: less portable, but common across that family.

How a system call is implemented

We write write(), but inside the OS each system call has a number. You need the location of the OS code for that number in order to jump there, so a table is kept whose index is the system call number. The entry at that index holds the memory address of the system call; PC is set to that address and control jumps there.

Calling printf invokes write() inside it, and write() takes you into kernel mode. When write() returns, its value goes to printf, and printf's return value goes to the application.

The file-copy example

Think about a command like cp. Counting the system calls makes the point. Read the source filename from the keyboard (I/O, so a system call), echo what the user typed to screen (write), do the same for the output filename, open the input file (open), create the output file (create), loop reading and writing (read and write, repeatedly), close the files and print a completion message (close, write), then terminate the process (also a system call).

System calls are grouped into process control, file management, device management, information maintenance (getting things like a process id), communication, and protection.

Virtual machines

Suppose you modified your own OS's source, compiled, ran it, and it broke. Now you have to reinstall the unmodified OS. That takes a while.

A virtual machine bundles the hardware and the OS on top of it and makes the bundle look like hardware. There really is an OS installed, but it's presented as bare hardware — and you can install another operating system on top of that.

Without a VM, a kernel sits on the hardware and processes run on the kernel, asking it to do work through the system call interface. With a VM, a hypervisor sits on the kernel and hands virtual machines to the processes above it. A VM looks like hardware, so a kernel can be installed on it, and applications can run against that kernel's system call interface.

One machine can host several operating systems, so you can test all the environments an application needs on a single computer. Cloud computing uses this to let many users share one machine while each gets the OS they need — an efficient use of the resource.

The JVM comes from a similar idea. Compilation translates to machine code, so once compiled a program only runs where that machine code is understood. Instead, ship the program itself and translate it on the user's machine in real time. The JVM loads and translates the classes it receives, so any machine with a JVM can run it.