REN

During my studying and research in operating systems, few textbooks give a rather detailed description on how an operating system is booted. In this article, I'll talk about how an operating system is booted based on x86 machine and Linux.

How an OS is booted

The operating system is often called the first program for every applications runs above the OS. Then the question comes: How the OS is loaded into main memory and make the kernel work? Actually, before the OS is running, there's a small program called bootloader whose role is to load the rest bulk of OS into main memory.

When the power is on, computer memory is usually uninitialized. Hence, there is nothing to run for the mechanism of Von Neumann architecture. Early computers would have hardware that would enable the operator to press a button to load a sequence of bytes from punched cards, punched paper tape, or a tape drive. Switches on the computer’s front panel would define the source of the data and the target memory address. In some cases, the boot loader software would be hard wired as non-volatile memory (in early computers, this would be a grid of wires with cuts in the appropirate places where a 0-bit was needed).

In early minicomputer and microcomputer systems, a computer operator would use the switches on the computer’s front panel to toggle in the code to load in a bigger program, programming each memory location and then starting the program. This program might do something basic such as read successive bytes into memory from a paper tape attached to a teletype.

In later systems, read-only memory would contain a small bootloader that would have basic intelligence to read, say, the first sector (512 bytes) of a disk.

Since this initial program had to be as small as possible, it would have minimal capabilities. What often happened is that the boot loader would load another boot loader, called a second stage loader, which was more sophisticated. This second stage loader would have error checking, among possibly other features, such as giving the user a choice of operating systems to boot, the ability to load diagnostic software, or enabling diagnostic modes in the operating system. This multi-stage boot loader, having a boot loader load a bigger boot loader, is called chain loading.

The boot loader will often perform some core initialization of the system hardware and will then load the operating system. Once the operating system is loaded, the boot loader transfers control to it and is no longer needed. The operating system will initialize itself, configure the system hardware (e.g., set up memory management, set timers, set interrupts), and load device drivers, if needed.

x86 Architecture Booting

IA-32, also known as x86, is the leader in desktop processor architecture. I using x86 architecture to illustrate OS booting for the following reason: we're using x86 everyday no matter common PC users or application programmers, thus most computer science and programming learners are under x86 environment; Although some other architectures such as ARM, SPARC, PowerPC are having a considerable market sharing, installing OSes on those machines are not common and familiar for most people even professionals.

Booting with BIOS

An IA–32-based PC is expected to have a BIOS (Basic Input/Output System, which comprises the bootloader firmware) in non-volatile memory (ROM in the past and NOR flash memory these days). The BIOS is a descendent of the BIOS found on early CP/M systems in that it contains low-level functions for accessing some basic system devices, such as performing disk I/O, reading from the keyboard, and accessing the video display. It also contains code to load a stage 1 boot loader.

When the CPU is reset at startup, the computer starts execution at memory location 0xffff0 (the IA–32 architecture uses a segment:offset form of addressing; the code segment is set to 0xf000 and the instruction pointer is set to fff0).

The processor starts up in real mode, which gives it access to only a 20-bit memory address space and provides it with direct access to I/O, interrupts, and memory (32-bit addressing and virtual memory comes into play when the processor is switched to protected mode). The location at 0xffff0 is actually at the end of the BIOS ROM and contains a jump instruction to a region of the BIOS that contains start-up code.

Upon start-up, the BIOS goes through the following sequence:

Power-on self-test (POST)
Detect the video card’s (chip’s) BIOS and execute its code to initialize the video hardware
Detect any other device BIOSes and invoke their initialize functions
Display the BIOS start-up screen
Perform a brief memory test (identify how much memory is in the system)
Set memory and drive parameters
Configure Plug & Play devices (traditionally PCI bus devices)
Assign resources (DMA channels & IRQs)
Identify the boot device

Stage 1: MBR (Master Boot Record)

In legacy mode, at the very first sector of a bootable disk, there's a Master Boot Record whose size is 512 bytes containing the code of stage 1 bootloader, disk partition table and boot signiture. The picture below shows the layout of a typical 512 byte boot record:

The code area, as I just illustrated, read block 0 of the booting disk into memory location: 0x0000:0x7c00 and jumps there, and set initializations for switching to protected mode. The disk partition table takes 64 bytes, and there's only 4 primary disk partition for a disk. (In UEFI mode, this constraint will be broken). The boot signiture is 0xAA55. The reason that we use 0xAA55 is when represented in binary, it was 1010101001010101, which was two different rectangular wave form. As we just said, this signiture is an identifier for a bootable disk. And rectangular wave form is easy to be identified in digit circuit level.

Stage 2: VBR (Volume Boot Record)

A Volume Boot Record (VBR) is the first sector of a partition (unlike MBR which is the first sector of a hard disk). A VBR (just like a MBR) also contains some code and data, but it's far less standard. Instead of a Partition Table it usually holds some file system information, like the BIOS Parameter Block (although it's not needed nowadays, many OS's have kept it for compatibility). The code is always OS specific, but in common all versions function the same: locate the kernel on the partition, load and execute it. A really good example of a VBR is the original DOS bootsector, which knew FAT and loaded IO.SYS and MSDOS.SYS from the root directory. On Windows NT-derived systems (e.g., Windows Server 2012, Windows 8), the IPL loads a program called NTLDR, which then loads the operating system.

A multi-stage bootloader - GRUB

There are many variations on booting other operating systems on an Intel PC. One popular boot loader on Linux systems is GRUB, or GRand Unified Bootloader. GRUB is also a multi-stage bootloader. The BIOS, of course, does what it always does: identifies a bootable device, loads the Master Boot Record, and transfers control to this newly-loaded code. When installing GRUB in a UNIX-like system, the MBR will contain codes called GRUB Stage 1 whose responsibility is locating GRUB Stage 2. The Stage 2 loader presents the user with a choice of operating systems to boot and allows the user to specify any additional boot parameters for those systems (e.g., force maximum memory, enable debugging). It then reads in the selected operating system kernel and transfers control to it.

A specific problem with using GRUB to boot Windows is that Windows is not Multiboot compliant. Multiboot is a Free Software Foundation specification on loading multiple operating systems using a single boot loader. What GRUB does in this case is fake a conventional Windows boot process. It boots a bootloader that would normally reside in the MBR (or run the Windows boot menu program). From that point onward, GRUB is out of the picture, Windows has no idea what happened, and the native Windows boot process takes over.

Booting with UEFI

As 64-bit architectures emerged to replace 32-bit architectures, the BIOS was starting to look quite dated. Intel set out to create a specification of a BIOS successor that had no restrictions on having to run the startup code in 16-bit mode with 20-bit addressing. This specification is called the Unified Extensible Firmware Interface, or UEFI. Although developed by Intel, it was managed since 2005 by the Unified EFI Forum. It is used by many newer 64-bit systems, including Macs, which also have legacy BIOS support for running Windows.

Some of the features that EFI supports are:

BIOS compatability preserved some components from the BIOS, including power management (Advanced Configuration & Power Interface, ACPI) and system management components (e.g., reading and setting date).
Support for larger disks The BIOS only supported four partitions per disk, with a capacity of up to 2.2 TB per partition. UEFI supports a maximum partition size of 9.4 ZB (9.4 × 1021 bytes).
No need to start up in 16-bit (real) mode The pre-boot execution environment gives you direct access to all of system memory.
Device drivers UEFI includes device drivers, including the ability to interpret architecture-independent EFI Byte Code (EBC). Operating systems use their own drivers, however, so — as with the BIOS — the drivers are generally used only for the boot process.
Boot manager This is a significant one. The old BIOS only had the smarts to load a single block, which necessitates multi-stage booting process. UEFI has its own command interpreter and complete boot manager. You no longer need a dedicated boot loader. As long as you place the bootable files into the UEFI boot partition, which is formatted as a FAT file system (the standard file system format in older Windows systems; one that just about every operating system knows how to handle).
Extensibility The firmware is extensible. Extensions to UEFI can be loaded into non-volatile memory.

With UEFI, there is no longer a need for the Master Boot Record to store a stage 1 boot loader; UEFI has the smarts to parse a file system and load a file on its own, even if that file does not occupy contiguous disk blocks. Instead, UEFI reads the GUID (Globally Unique IDentifier) Partition Table (GPT), which is located in blocks immediately after block 0 (which is where the MBR still sits for legacy reasons). The GPT describes the layout of the partition table on a disk. From this, the EFI boot loader identifies the EFI System Partition. This system partition contains boot loaders for all operating systems that are installed on other partitions on the device. For EFI-aware Windows systems, UEFI loads the Windows Boot Manager (bootmgfw.efi). For older 64-bit NT systems, EFI would load IA64ldr. For Linux, there are many options. Two common ones are to use an EFI-aware version of GRUB (the Grand Unified Bootloader) and load a file such as grub.efi or to have EFI load load elilo.efi, the EFI loader.

In general, even with UEFI, the dominant approach is to load an boot loader dedicated to a specific operating system rather than load that operating system directly. However, the need for a multi-stage boot process that requires loading multiple bootloaders is no longer necessary.