System Programming - Lecture 1, v3 - Kernel, Structure, Process Scheduler

Summary

The lecture introduces the kernel’s role and major subsystems, then explains Linux task scheduling in greater detail. Its central distinction is that the kernel is a core component of an operating system, not the whole operating system. The lecture also emphasizes that Linux schedules tasks internally, while “process” and “thread” are abstractions built around them.

Operating systems, the kernel, and system calls

• An operating system can be understood broadly as the software needed to manage and use computer hardware. The kernel is essential, but an operating system may also include drivers, a bootloader, and tools such as a console.
• Applications such as browsers, video players, and compilers are not essential operating-system components: the system can run without them.
• The kernel connects user-space programs with hardware and other kernel services. User-space programs typically access those services through system calls.
• System calls are a specific API provided by a particular kernel. Linux, Windows, and macOS have different sets. Ordinary library functions, such as printf, are not themselves system calls, even if they eventually invoke one.

Interrupts and deferred work

• Hardware devices use interrupts to notify the CPU and kernel that an event needs attention—for example, a keyboard press or an incoming network packet.
• Interrupt handlers should do only the work that must happen immediately. Lengthy processing can delay other interrupts and system work.
• The lecture describes a two-stage approach:
  • Top half: Handle the interrupt quickly, often by acknowledging it or copying data into memory.
  • Bottom half: Do the more substantial processing later, outside the immediate interrupt context.
• This is presented as a general design pattern as well as a kernel technique: perform quick preliminary work, then defer heavier work to another context or worker thread.

How the kernel starts

The lecture presents startup as a chain in which each stage starts the next:

1. When powered on, the CPU begins executing firmware from a predefined location.
2. The firmware, called BIOS in the lecture, locates and starts a bootloader.
3. The bootloader locates and loads the kernel.
4. The kernel takes control and starts the operating system’s work.

The bootloader is useful because firmware is constrained in size and complexity, while the bootloader can be a larger program stored on disk. The lecture notes that modern firmware can be updated, despite the historical name “read-only memory.”

Linux kernel components introduced

The lecture surveys the kernel areas that will be covered in the course:

• Process and task management, including threading and scheduling.
• Hardware support and drivers, which let the kernel communicate with devices. Shared hardware standards allow one driver interface to support devices from multiple manufacturers.
• Time management, including clocks, timers, and scheduling-related timing.
• File-system support, which provides common operations across different file systems.
• Interprocess communication (IPC), including message queues, pipes, sockets, shared memory, mutexes, and semaphores.
• Networking, including network-device support, packet handling, routing, filtering, and protocols such as TCP, IP, and UDP. The lecture briefly contrasts the conceptual OSI model with the widely implemented TCP/IP model.
• User and access management, including credentials and permissions.
• Data structures and virtualization, among other kernel areas.

Processes, threads, and Linux tasks

• A process is described as a unit of program execution with resources such as memory and file descriptors; it can contain multiple threads.
• In Linux, the kernel represents execution units using a task structure. The lecture’s key practical point is that when discussing Linux scheduling, it is often clearest to think in terms of tasks.
• A Linux task has state and scheduling information, among other data. The kernel also tracks items such as identifiers, credentials, memory information, exit state, and file descriptors.
• A file descriptor returned to a user-space program is an integer index into that task’s file-descriptor table.
• Linux tasks can share resources. In the lecture’s model, a thread corresponds to a task, while a process is a grouping of tasks and their shared resources.

Task states and waiting

A task may be running, ready to run, or waiting for an event. For example, a thread blocked on a socket read has no data to process and is not ready to use the CPU.

Waiting is useful because the task does not need to waste CPU time repeatedly checking whether an event has occurred. Good use of blocking and wake-up mechanisms can improve performance; unnecessary or “spurious” wake-ups add work.

Timekeeping

The lecture distinguishes several time-related concepts:

• Monotonic time measures intervals and continues to advance; it is useful for timers and periodic work.
• Wall-clock time represents real-world calendar time and is useful when an action depends on a date or time of day.
• Hardware clocks and oscillators provide timing signals. The kernel uses these signals to update its timekeeping and timers.
• The lecture discusses the kernel’s configurable tick frequency, described as HZ. More frequent ticks can provide finer-grained updates, but each interrupt has overhead.
• A real-time clock (RTC) keeps time while the computer is powered off, using a battery.
• Busy-waiting for very short intervals is mentioned, but discouraged for ordinary application work because it consumes CPU time.
• A pulse-per-second (PPS) signal can help synchronize clocks very precisely. The lecture connects accurate time synchronization to distributed systems, where timestamps can help reason about the order of events.

Kernel file-system interfaces and data structures

• File systems differ internally, but commonly support operations such as opening, creating, reading, writing, and positioning within files.
• The kernel can use a shared interface—described as similar to a C++ virtual-function table—so common kernel code can work with different file systems through their function pointers.
• The lecture also explains intrusive data structures, using linked lists as the example:
  • A naïve approach duplicates list code for each object type.
  • A generic wrapper-based approach can require extra allocations or pointer indirection.
  • An intrusive approach embeds one or more link fields directly in an object. Separate links let the same object belong to multiple lists at once.
  • The kernel’s container_of technique recovers the address of an enclosing structure from the address of one of its members, using the member’s known offset.
• The same general approach can be used for other structures, such as trees and hash tables.

Multitasking and scheduling

The lecture distinguishes two approaches:

• Cooperative multitasking: Tasks voluntarily yield control. This can work well in small or controlled environments, but a task that fails to yield can monopolize a CPU.
• Preemptive multitasking: An external scheduler interrupts tasks and decides which task runs next. The lecture presents this as the approach used by modern general-purpose operating systems, including Linux.

Tasks are also described as broadly I/O-bound or CPU-bound:

• I/O-bound tasks spend much of their time waiting and usually benefit from quick service when they become ready.
• CPU-bound tasks have sustained computation to perform and benefit from longer uninterrupted runs.

The scheduler must balance responsiveness against the cost of switching tasks. A context switch requires saving and restoring execution state, so switching infinitely often—as an idealized mathematical model might assume—is not practical.

Linux scheduling and fairness

• The lecture discusses several Linux scheduling approaches and highlights the Completely Fair Scheduler (CFS) as the general-purpose scheduler it focuses on.
• Its fairness model is described in terms of shares or proportions of CPU time, rather than assigning every task a rigid time slice that must be used whether needed or not.
• In the lecture’s example, a chess program and a video converter have equal shares. The chess program often sleeps while waiting for user input, so the video converter can use the otherwise idle CPU time. When the chess program wakes, it can run promptly.
• The nice value influences a task’s relative share: a lower nice value means a less “nice” task and a higher scheduling weight, while a higher value means the task yields more relative CPU time to others.
• Real-time priority is presented separately from nice values; higher-priority real-time tasks can take precedence over lower-priority tasks.
• In the lecture’s account of CFS, runnable tasks are organized by virtual runtime in a red-black tree. The scheduler selects the task with the smallest virtual runtime; runtime and weights affect where tasks are ordered. Waiting tasks are removed from the runnable scheduling structure until they can run again.

Homework and next lecture

• The voluntary homework is to implement a coroutine messaging system using a provided task description, template, and coroutine library.
• The lecture describes a base version and two optional bonus parts, and suggests a three-week timeframe. It also says the task may be manageable in one or two evenings, depending on the student.
• The next lecture is planned to cover processes in more detail, including their memory, resources, interruption, communication with the kernel, and system calls.

Speakers and sources featured

• Speaker: One unnamed lecturer or narrator; no guest speakers are identified.
• Sources and examples mentioned: Linux kernel structures and scheduler code; Linux kernel mailing lists; the OSI and TCP/IP networking models; Go and C++20 coroutines; Google Spanner’s TrueTime; and the Accord distributed-transaction protocol.