We talked about various concepts and topics related to OS and
system-level programming:
Assembly
C
Memory / Memory Management
CPU / Process management
System calls
Context switching
We talked very little about compilers – we might do more toward the
very end of this semester
Remember at the beginning: OS
OS is just a program running on the computer
What is (the purpose of) an OS?
Resource manager - allocate memory, CPU, other resources
Controls the execution of other programs
Protection - conflict resolution, security
Stability, fairness, responsiveness, throughput
We mentioned: Linux, Windows, Mac OS, Android, …
POSIX systems
Basically an effort to standardize Unix interfaces
macOS, Linux, *BSD are all compliant
Windows is compliant through, e.g., WSL
Using a computer without an OS would be hard
As programmers, we would have to know the details of hardware and
firmware of any computer our software should run on
OS and the Architecture/HW
We touched on this - a modern OS sets up the HW to work for it
The OS depends on hardware interrupts to stay in control (clock,
I/O)
OS relies on HW support for memory management (MMU)
Peripherals controlled via device drivers
But… how is an OS structured? How does it start?
Brief History of OSs (on PCs)
1955 and earlier: Very early mainframes have no operating
system
1956: GM-NAA I/O used for research by General Motors – first real
OS
1960s: IBM delivers System/360 OS
Details recounted in Mythical Man Month Book
Mainframes were king
OS mainly oriented toward batch processing initially
Later move to multitasking and time-sharing
Buroughs MCP was the first operating system to include virtual
memory management, also first OS written in a high-level language
Mid-60s - collaborative development on Multics (MIT, Bell Labs, GE)
- a project which failed, but was the direct precursor to Unix and
contained many of its innovations already
1970-80s: Digital Equipment Corporation (DEC) and Data General (DG)
lead the minicomputer market
Data General’s initial design detailed in The Soul of a New
Machine
There is no reason anyone would want a computer in their home. –Ken
Olsen, Founder and CEO of DEC
Operating systems include RT-11, RSTS, RSX-11
At AT&T Bell Labs, development on Unix started (still in the
late 1960s) as a smaller-scale experiment with some of Multics’
goals
Unix originally written on PDP-7, later implemented on PDP-11
Unix V1-V3 written in PDP assembly, V4 was the first one written in
assembly
1981: IBM releases a Personal Computer (PC) to compete with Apple
Basic Input/Output System (BIOS) for low-level control
Three high-level OSes, including MS-DOS
Developers were asked to write software for DOS or BIOS, not
bare-metal hardware
1982: Compaq and others release IBM-compatible PCs
Different hardware implementations (except 808x CPU)
Reverse engineered and reimplemented BIOS
Relied on customized version of MS-DOS
1985: IBM clones dominated computer sales
Used the same underlying CPUs and hardware chips
Close to 100% BIOS compatibility
MS-DOS was ubiquitous
Thus, IBM PC hardware became the de-facto standard
1986: Compaq introduces 80386-based PC
1990’s: Industry is dominated by “WinTel” (Microsoft and Intel)
Intel x86 CPU architectures (Pentium 1, 2, and 3)
Windows 3.1, NT, 95 software compatibility
Windows <95 were basically extenders for DOS - Windows ran on top
of the underlying DOS operating system
How to Build an OS?
We need some tools: C, assembler, knowledge of hardware and some
concepts
Ready to build our kernel
Wait, what is a kernel?
Kernel is the core program of an operating system
It is always resident in memory and facilitates communication with
the hardware
How do we structure the kernel?
Kernel architectures
For protection and maintaining exclusive control, a computer may run
in a privileged (kernel) mode and an unprivileged (user) mode
Certain operations are only available in kernel mode
In general, we want to run as much code as possible in user
mode
Problem: switching is expensive, user-mode software eventually needs
to ask the kernel for services, which need to be delivered partially
from kernel mode
How much of the OS (kernel) runs in which mode guides how the kernel
is structure architecturally
There are three common kernel architecture types:
Monolithic Kernels
Traditionally: live as a single binary - single code base
Important: Code runs in privileged mode (kernel-space)
Old approach: new device drivers need to be compiled into the kernel
binary and the OS needs to be reloaded
Modern approach: Drivers can be dynamically loaded into the running
kernel - modules
most BSDs (FreeBSD, OpenBSD, NetBSD), Solaris, Linux, DOS, old
Windows (9x, M)
isolation, robustness - a bug in a driver may potentially damage the
operating system - BSOD (aka the Blue Screen Of Death)
Kernel Space User space
+-------------------------------+ +------------------+
| Mem Man | | |
| Scheduler | | |
| File Sys System API <-------> User programs |
| Device drivers | | |
| Program loader | | |
| . . . | | |
+-------------------------------+ +------------------+
Microkernels
The kernel that runs in privileged mode is small - only
essentials
Device drivers run in (unprivileged) user space - they act as
servers - userspace programs with some privileged access to the
kernel
Mach, QNX, L4, MINIX, GNU HURD
Advantages:
usually smaller code bases
modularity, configurability
easier to add things
a driver bug does not bring down the OS
Disadvantages:
performance - many more context switches for message passing between
drivers
Kernel space User space
+---------------------+ +----------------------------------+
| Mem Man | | +-> File System <--> Disk Driver |
| Scheduling | | | |
| Interproces Comms <-------+-> Program 1 |
| | | | |
+---------------------+ | +-> Program 2 |
+----------------------------------+
Hybrids (?)
Really a monolithic kernel, somewhat structured like a
microkernel
Or a bigger microkernel
Most code still runs in kernel space - because performance
Often dismissed as a PR stunt for a monokernel
Windows NT series (modern Windows, including 10), OS/2, XNU
Some hybrid OSes are microkernels that have more things running in
kernel space than usual
That’s all nice, but where do we start?
Shall we just pile code on?
We need some code to start things up!
Some sort of “Hello, World, I’m an OS”
When we write “normal” software, we get an executable that is loaded
by the OS and run
Or we have the interpreter that is loaded by the OS and the
interpreter loads our Python/JS/Perl/… program
Question: who loads the OS?
How does an operating system start?
Booting up and Bootloaders
Note: this is the traditional view. Nowadays, the boot process is
under the direction of UEFI
Press the power button
Motherboard powers up and starts executing the BIOS (Basic
Input/Output System)
BIOS lives in a chip on the motherboard
Gets copied to RAM at address 0xFF
a jmp 0xFF instruction is written to RAM at 0xFFFF0
where the CPU starts executing
BIOS: loads user settings from a volatile memory on the MB (backed
by a small battery)
BIOS: some basic checks on the hardware and initialization
CPU, memory, kbd, mouse, graphics, HDD
interrupt handlers
run BIOSes on additional hardware (expansion cards)
then test everything (POST)
Initialize the bootstrap sequence
Scan all bootable devices (HDDs, CD/DVD-ROM, USB, floppy,
network, …)
If it finds a bootable master boot record (MBR) it stops,
loads the code from MBR and jumps to it
What is the MBR?
a 512B area at the very beginning of a storage device (disk, CD,
flash drive, …)
Contains some information about the structure of the storage
(partition table - up to 4 entries)
446B is executable code - can we fit an OS there?
Bootloader
In a modern setting, the MBR code is code that loads code that
(loads code that) loads the OS - a bootloader
There’s a small bootloader in the MBR and each partition might have
a boot loader
For Linux and free OSes, the standard bootloader is GRUB
nowadays
GRUB can load kernels directly, or it can jump to partition
bootloaders (e.g., to load Windows)
Let’s look at a small example OS: xv6
xv6
A small educational OS developed at MIT
Based on the Version 6 of UNIX, which was a popular version of UNIX
to study (mainly because of the legendary “Lions
Book”
Modern reimplementation
There are two versions: one for x86 and one for MIPS
We will be using the x86 version, which is no longer developed, but
still available and easily compilable
The whole source code can be printed on ~100 pages (use
make print to generate the PDF)