Operating Systems

1. UNIX's Evolution: From Bell Labs to Modern Systems

The first notable milestone was porting the UNIX system from the PDP-7 to the PDP-11.

Humble beginnings. UNIX started as an experiment at Bell Labs in 1970, initially running on a PDP-7. Its portability to the PDP-11 was a pivotal moment, hinting at its potential as a universal operating system. This early success was followed by a groundbreaking decision to rewrite UNIX in C, a high-level language, which was unheard of at the time for operating systems.

Key milestones:

• Initial development at Bell Labs on PDP-7
• Porting to PDP-11, demonstrating portability
• Rewriting in C, enabling wider adoption
• Release of Version 6 and Version 7, gaining popularity
• Development of BSD at Berkeley, driving innovation
• Commercialization with System III and System V

Legacy of innovation. The evolution of UNIX is a story of continuous innovation and adaptation. From its early days as a research project to its widespread use in commercial and academic settings, UNIX has consistently pushed the boundaries of operating system design. Its influence can be seen in many modern operating systems, including Linux and macOS.

2. Core Components of Traditional UNIX Systems

The operating system is often called the system kernel, or simply the kernel, to emphasize its isolation from the user and applications.

Kernel at the core. The heart of UNIX is the kernel, which manages the system's resources and provides a foundation for user applications. The kernel is isolated from users and applications, ensuring stability and security. It acts as an intermediary between the hardware and the software.

Key components:

• Kernel: Manages processes, memory, and I/O
• System call interface: Allows user programs to access kernel functions
• Shell: Provides a user interface for interacting with the system
• C compiler: Enables development of user applications

Process and file management. The kernel is divided into two main parts: process control and file management. Process control handles memory management, scheduling, and interprocess communication. The file system manages data exchange between memory and external devices, using device drivers and a disk cache.

3. Modern UNIX Systems: Modular and Extensible

There is a small core of facilities, written in a modular fashion, that provide functions and services needed by a number of OS processes.

Modular design. Modern UNIX systems, like SVR4, Solaris, and Linux, have adopted a modular architecture. This approach allows for greater flexibility, extensibility, and code reuse. The kernel is no longer a monolithic block of code but a collection of independent modules.

Key features:

• Modular kernel: Allows for dynamic loading and unloading of modules
• Virtual file system: Supports multiple file system types
• Preemptive kernel: Enables real-time processing
• Dynamically allocated data structures: Improves memory management

Benefits of modularity. The modular design of modern UNIX systems makes it easier to add new features, fix bugs, and adapt to different hardware platforms. This has been crucial for the continued relevance and widespread adoption of UNIX-based operating systems.

4. UNIX Process Management: States and Structures

UNIX uses two categories of processes: system processes and user processes.

Two process types. UNIX distinguishes between system processes, which run in kernel mode to perform administrative tasks, and user processes, which execute user programs. User processes can enter kernel mode through system calls, exceptions, or interrupts.

Process states:

• Running (user/kernel): Executing in user or kernel mode
• Ready to run: Waiting to be scheduled
• Asleep: Blocked, waiting for an event
• Preempted: Temporarily suspended by the kernel
• Zombie: Terminated but still in the process table

Process image. A process in UNIX is a complex set of data structures, including user-level context, register context, and system-level context. The system-level context includes the process table entry and the U area, which contain essential process control information.

5. Solaris' Multithreaded Approach: User and Kernel Threads

Solaris implements an unusual multilevel thread support designed to provide considerable flexibility in exploiting processor resources.

Multilevel threading. Solaris uses a unique multilevel thread model, including processes, user-level threads (ULTs), lightweight processes (LWPs), and kernel threads. This approach allows for flexible exploitation of processor resources.

Key components:

• Processes: Traditional UNIX processes
• User-level threads (ULTs): Managed by a threads library, invisible to the OS
• Lightweight processes (LWPs): Map ULTs to kernel threads
• Kernel threads: Scheduled and dispatched to run on processors

Flexibility and efficiency. The combination of user-level and kernel-level threads allows application programmers to exploit concurrency in a way that is most efficient and appropriate for a given application. This approach reduces overhead and allows for better resource utilization.

6. Linux's Process and Thread Model: Flexibility and Control

Thus, Linux makes no distinction between a thread and a process.

Unified model. Linux does not distinguish between threads and processes. A new process is created by copying the attributes of the current process, and resources can be shared, allowing for thread-like behavior.

Process states:

• Running: Executing or ready to execute
• Interruptible: Blocked, waiting for an event
• Uninterruptible: Blocked, waiting directly on hardware
• Stopped: Halted, can only resume by action from another process
• Zombie: Terminated but still in the process table

Task structure. A process in Linux is represented by a task_struct data structure, which contains information about the process's state, scheduling, identifiers, interprocess communication, links, timers, file system, virtual memory, and processor-specific context.

7. UNIX Concurrency Mechanisms: Pipes, Messages, and More

One of the most significant contributions of UNIX to the development of operating systems is the pipe.

Interprocess communication. UNIX provides several mechanisms for interprocess communication and synchronization, including pipes, messages, shared memory, semaphores, and signals. These mechanisms allow processes to communicate and coordinate their actions.

Key mechanisms:

• Pipes: Circular buffers for producer-consumer communication
• Messages: Blocks of text with a type, sent to message queues
• Shared memory: Common block of virtual memory shared by multiple processes
• Semaphores: Generalization of wait and signal primitives for synchronization
• Signals: Software mechanisms to inform processes of asynchronous events

Synchronization and coordination. Pipes, messages, and shared memory facilitate data exchange, while semaphores and signals are used to trigger actions by other processes, ensuring proper synchronization and coordination.

8. Solaris Thread Synchronization: Mutexes, Semaphores, and Locks

Solaris implements these primitives within the kernel for kernel threads; they are also provided in the threads library for user-level threads.

Synchronization primitives. Solaris provides four thread synchronization primitives: mutex locks, semaphores, readers/writer locks, and condition variables. These primitives are implemented in both the kernel and the threads library.

Key primitives:

• Mutex locks: Prevent more than one thread from proceeding when the lock is acquired
• Semaphores: Classic counting semaphores for synchronization
• Readers/writer locks: Allow multiple readers or a single writer to access an object
• Condition variables: Used to wait until a particular condition is true

Atomic operations. All synchronization primitives require a hardware instruction that allows an object to be tested and set in one atomic operation, ensuring mutual exclusion and preventing race conditions.

9. UNIX and Solaris Memory Management: Paging and Allocation

For paged virtual memory, UNIX makes use of a number of data structures that, with minor adjustment, are machine independent.

Paging and virtual memory. UNIX uses paged virtual memory, allocating page frames in main memory to processes and disk block buffers. This scheme is effective for user processes and disk I/O.

Key data structures:

• Page table: One per process, with entries for each virtual page
• Disk block descriptor: Describes the disk copy of a virtual page
• Page frame data table: Describes each frame of real memory
• Swap-use table: One per swap device, with entries for each page on the device

Kernel memory allocation. For kernel memory, a modified buddy system is used, known as the lazy buddy system. This system defers coalescing blocks until it is likely needed, reducing overhead and improving performance.

10. Linux Memory Management: Three-Level Paging and Slab Allocation

Linux makes use of a three-level page table structure.

Three-level paging. Linux uses a three-level page table structure, including page directories, page middle directories, and page tables. This structure is designed to accommodate 64-bit architectures.

Key components:

• Page directory: Points to page middle directories
• Page middle directory: Points to page tables
• Page table: Refers to virtual pages of the process

Slab allocation. For kernel memory, Linux uses a slab allocation scheme within allocated pages. This scheme maintains linked lists of memory chunks of various sizes, allowing for efficient allocation and deallocation of small memory blocks.

11. Traditional UNIX Scheduling: Time-Sharing and Priorities

The scheduling algorithm is designed to provide good response time for interactive users while ensuring that low-priority background jobs do not starve.

Multilevel feedback. Traditional UNIX scheduling uses multilevel feedback with round robin within each priority queue. The system preempts processes every second.

Priority calculation:

• Priority is based on process type and execution history
• CPU utilization and a user-controllable "nice" factor are considered
• Base priorities divide processes into fixed bands

Priority bands:

• Swapper
• Block I/O device control
• File manipulation
• Character I/O device control
• User processes

12. Modern UNIX Scheduling: Real-Time and Preemption

The new algorithm is designed to give highest preference to real-time processes, next-highest preference to kernel-mode processes, and lowest preference to other user-mode processes.

Real-time support. Modern UNIX systems, like SVR4 and Linux, have added support for real-time processing. This includes preemptable static priority schedulers and preemption points.

SVR4 priority classes:

• Real-time: Highest priority, guaranteed to run before kernel or time-shared processes
• Kernel: Medium priority, runs before time-shared processes
• Time-shared: Lowest priority, for user applications

Linux scheduling classes:

• SCHED_FIFO: First-in-first-out real-time threads
• SCHED_RR: Round-robin real-time threads
• SCHED_OTHER: Other, non-real-time threads

Last updated: January 17, 2025