Operating Systems and System Software PDF

1 Operating Systems and System So ware Betriebssysteme und Systemso ware Prof. Redha Gouicem Operating Systems and System So ware ...

1 Operating Systems and System So ware Betriebssysteme und Systemso ware Prof. Redha Gouicem Operating Systems and System So ware  2 Table of Contents Course Information Chapter 1: Introduction to Operating Systems Chapter 2: Program Execution Chapter 3: Memory Management Chapter 4: File Management Chapter 5: Input-Output Devices and Interrupts Chapter 6: Concurrency, Inter-Process Communication and Synchronization Chapter 7: User-Kernel Interactions And User Space Components Chapter 8: Virtualization Operating Systems and System So ware  4 Course Information Operating Systems and System So ware  5 Team Course offered by the LuFg Betriebssysteme/Operating Systems Office: UMIC building, 2nd floor Website: https://os.rwth-aachen.de Lecturer Teaching assistants Prof. Redha Gouicem Jérôme Coquisart, M.Sc. and Christian van Sloun, M.Sc. (COMSYS) Operating systems Binary translation Scheduling Cross architecture emulators Memory management Memory models Unikernels Correctness … … Contact emails Course related: [email protected] Virtualization General: [email protected] Hypervisors Thesis: [email protected] Deployment models … Operating Systems and System So ware  6 Organization Lectures: 2x week, 1.5 hours each Exercises: 1x week Present solutions to the previous week’s assignments Tutorials: 1x week, 24 groups (EN, DE or both) Solve and discuss assignments in small groups Week Topic 1 Introduction to operating systems 2 Processes and threads 3 Memory management 4 File management 5 I/O devices and interrupts 6 Concurrency and Synchronization 7 User space OS (System calls, shared libraries) 8 Virtualization and containers Operating Systems and System So ware  7 Week Planning Day Time Where Rooms Lectures Monday 10:30 – 12:00 1385 C.A.R.L. 101 Friday 16:30 – 18:00 1515 Hörsaalgebäude TEMP 2.0 001, 002 Exercise Tuesday 16:30 – 18:00 1385 C.A.R.L. 003 Tutorials Monday 08:30 – 10:00 1420 Audimax 301, 303, 304 Tuesday 08:30 – 10:00 1385 C.A.R.L. 207, 208, 209, 211, 212, 215 2356 Informatik E2 052, 054, 055 10:30 – 12:00 2356 Informatik E2 052, 055 1420 Audimax 301, 304 Friday 12:30 – 14:00 1420 Audimax 301, 304 2356 Informatik E2 052, 055 14:30 – 16:00 1132 HKW 504 1385 C.A.R.L. 204, 206 1420 Audimax 303 2356 Informatik E2 055 Tutorial registration on RWTHonline Operating Systems and System So ware  8 Course Evaluation Weekly assignments Automatically graded assignments on Moodle, mostly programming Individual submission, but you are allowed to help each other in small groups (without copying solutions) 20% of the final grade + 10% bonus points for the exam Planning: For a given topic T , e.g., memory management: The tutorials covering T will happen on Friday, Monday and Tuesday A er the last tutorial, the graded assignment will be released (Tuesday around 12:00) You have a week to complete the graded assignment, until the following Global Exercise (Tuesday 16:00) The assignment solution will be provided and discussed in the Global Exercise just a er the deadline (Tuesday 16:30) Written exam Mostly concept questions and exercises. You won’t have to write code from scratch. At most, we may give you some code to read and explain/fix, or have you write a couple of lines. 80% of the final grade You need to get a passing grade (half of the total points) in both to pass the course! Operating Systems and System So ware  9 Course Links Moodle Everything is made available in the BuS (Lecture) Moodle room Lecture recordings are made available as soon as possible Tutorial sheets Weekly graded assignments Slides Lecture slides are available at this address These slides are synchronized with the lecture, i.e., pages will change at the same time as the live presentation. Operating Systems and System So ware  10 Course Evaluation Please give us feedback on things that you disliked or feel could be improved, but also on the things that you liked! This is very important for us, especially since this course has been heavily refactored. We need your opinion to improve the course for future years! You have until 23.06.2024 23:59:00 to fill in the evaluation forms. Below, you can find two forms: one for the lecture where you can give us feedback about everything except tutorials, and one for the tutorials. Lecture evaluation Tutorial evaluation Link Link Operating Systems and System So ware  11 References Books Modern Operating Systems, Fi h Edition Andrew S. Tanenbaum, Herbert Bos (2023) The Design and Implementation of the FreeBSD Operating System, Second Edition Marshall K. McKusick, George V. Neville-Neil, Robert N.M. Watson (2015) The C Programming Language, Second Edition Brian W. Kernighan, Dennis M. Ritchie (1988) Linux Kernel Development, Third Edition Robert Love (2010) Operating Systems and System So ware  13 Chapter 1: Introduction to Operating Systems Operating Systems and System So ware  14 This Week’s Program In this first week, we’ll start slow, first defining what an operating system is, its general architecture, and how it is used by applications. 1. Overview of Operating Systems Definitions and general concepts, history 2. Protection Domains and Processor Privilege Levels So ware and hardware isolation mechanisms between the OS and user applications 3. Operating System Architectures Main OS architectures and designs, their pros and cons Operating Systems and System So ware  15 Overview of Operating Systems Operating Systems and System So ware  16 What Is an Operating System? Computer systems are complex machines with a large number of components: Internal chips: processor(s), memory Storage devices: hard drives (HDD), solid state drives (SSD), etc. PCI devices: network cards, graphics cards, etc. Peripherals: keyboard, mouse, display, etc. Application programmers cannot be expected to know how to program all these devices. And even if they do, they would rewrite the exact same code for every application, e.g., the code to read inputs from the keyboard. Resources can be shared by multiple programs. Expecting programs to collaborate and not mess with each other is not possible, e.g., two programs try to print at the same time, but the printer can only print one coherent job at a time. The operating system is the so ware layer that lies between applications and hardware. It provides applications a simpler interface with hardware and manages resources. Operating Systems and System So ware  17 What Is an Operating System? (2) The operating system is the glue between hardware and user applications. It can be split into two parts: User interface programs: libraries, shell, graphical interfaces (GUI), etc. They offer a high level of abstractions, and are usually used by user applications to manipulate the underlying system. Kernel: executes critical operations with a high level of privilege (supervisor mode) and directly interacts with hardware. User interface programs go through the kernel to manipulate the state of the underlying hardware. User Web Text... Media applications browser editor player Libraries Utilities Shell Operating system Kernel Hardware HDD SSD... Keyboard In this course, we will mostly focus on the kernel part of the operating system. Operating Systems and System So ware  18 What Is the Operating System’s Job? The operating system has two main jobs: 1. From the applications’ perspective: provide easy abstractions to use the hardware 2. From the hardware’s perspective: manage the resources for controlled and safe use Abstraction layer Resource manager Hardware is complex and provides messy interfaces. Devices may have Hardware resources are shared by multiple programs and need to be their own design and interfaces, even when they have the same goal, properly managed to allow safe use, e.g., hard drives may respond to different types of commands for the e.g., if two programs try to use the same hard drive, we need to make same functional task. sure they are not unsafely modifying the same data. The operating system must provide a simple and The operating system must provide a safe and clean interface to access hardware resources. controlled allocation of resources to programs. Operating Systems and System So ware  19 Main Operating System Services Most operating systems are expected to provide the following features to user applications: 1. Program management execution environment, synchronization, scheduling, etc. 2. Memory management memory allocation, isolation 3. File management file system, standardized API, cache, etc. 4. Network management network topology, protocols, APIs, etc. 5. Human interface IO peripherals, display, etc. Operating Systems and System So ware  20 A Brief History of Computers and Operating Systems First mechanical computers Charles Babbage’s Analytical engine (1837) Turing complete. Programs on punch cards. Never fully built, a simplified version was built by his son later. First program written by Ada Lovelace (computing Bernoulli numbers). Calculating machine of Babbage’s Analytical Engine. Source: Wikimedia Charles Babbage, 1860. Source: Wikimedia Ada Lovelace, 1843. Source: Wikimedia Percy Ludgate’s Analytical engine (1909) Turing complete. Programs on punch cards. Never built, designed independently from Babbage’s engine. Operating Systems and System So ware  21 A Brief History of Computers and Operating Systems (2) First generation: Electro-mechanical computers (1940 – 1955) Heavy developments during World War II to help development of weapons (physical simulations) and compute rocket trajectories. Zuse Z3 (1941, Germany): First Turing complete electro-mechanical Theoretical work on computation theory and computer architectures, computer (programs on punched 35 mm film) with Alan Turing and John von Neumann Colossus Mark 1 (1943, UK): First programmable fully electronic First compiler by Grace Hopper (1952) for the UNIVAC I computer computer (programmed with cables and switches) ENIAC (1946, USA): First Turing complete fully electronic computer (programmed with cables and switches) Manchester Baby (1948, UK): Turing complete, fully electronic, programs entered in memory via keyboard Alan Turing, 1936. John von Neumann, 1940s. Grace Hopper, 1984. Source: Wikimedia Source: Wikimedia Source: Wikimedia No real operating systems, operators reserved the machines, programmed them or manually inserted the punch cards, and waited for the results. Zuse Z3 (replica). Source: Wikimedia Manchester Baby (replica). Source: Wikimedia Operating Systems and System So ware  22 A Brief History of Computers and Operating Systems (3) Second generation: Transistor computers (1955 – 1965) With transistors, computer become reliable enough for commercial use Mainframes are bought by corporations, government agencies and universities, e.g., weather forecast, engineering simulation, accounting, etc. First real of operating systems with GM-NAA I/O (1956), IBSYS (1960), working in batch mode to schedule and pipeline jobs NASA computer room with two IBM 7090s, 1962. Source: Wikimedia Source: Modern Operating Systems, A. S. Tanenbaum, H. Bos, page 9. Time sharing systems with CTSS (1961) and BBN Time-Sharing System (1962) PDP-1 computer. Source: Wikimedia First minicomputers for individual users: PDP-1 (1961), LINC (1962) Operating Systems and System So ware  23 A Brief History of Computers and Operating Systems (4) Third generation: Integrated circuits (1965 – 1980) Minicomputers and mainframes are becoming more commonplace IBM releases its OS/360 (1966) that features multiprogramming MIT, Bell and General Electric develop Multics (1969) that pioneered a lot of common OS concepts e.g., hierarchical file systems, protection domains, dynamic linking, processes Bell (Ken Thompson, Dennis Ritchie, et al.) develop UNIX (1969-71) influenced by Multics, with novel concepts e.g., “everything is a file” philosophy, inter-process communication (pipes), unified file systems This later on led to the creation of the POSIX standard UNIX will influence the design of many operating systems: 1969 1969 Unnamed PDP-7 operating system Open source 1971 to 1973 Unix 1971 to 1973 Berkeley’s BSD (1978) 1974 to 1975 Version 1 to 4 Unix Version 5 to 6 PWB/Unix Mixed/shared source Closed source 1974 to 1975 1978 1978 BSD AT&T’s System V (1983) 1979 1.0 to 2.0 Unix Version 7 Unix/32V 1979 1980 1980 BSD Vrije University’s MINIX (1987) 1981 1982 3.0 to 4.1 Xenix 1.0 to 2.3 Xenix System III 1981 1982 BSD 4.2 3.0 1983 SunOS 1983 1 to 1.1 System V Linux (1991) 1984 1985 Unix-like systems Unix Version 8 SCO Xenix SCO Xenix R1 to R2 1984 1985 AIX V/286 System V 1986 BSD 4.3 1.0 R3 HP-UX 1986 SunOS SCO Xenix 1.0 to 1.2 Unix 1.2 to 3.0 1987 9 and 10 V/386 1987 (last versions HP-UX 1988 BSD 4.3 System V 2.0 to 3.0 1988 from Tahoe R4 1989 Bell Labs) SCO Xenix 1989 BSD Net/1 V/386 BSD 4.3 1990 Reno 1990 1991 BSD Net/2 1991 Linux 0.0.1 SunOS To 0.9 Minix 4 386BSD 1.x NexTSTEP 1992 OpenSTEP 1992 1.0 to 4.2 NetBSD BSD 0.8 to 1.0 1993 SCO UNIX UnixWare HP-UX 1993 4.4-Lite 3.2.4 1.x to 2.x 6 to 11.10 & 1994 FreeBSD Lite Release 2 (System V R4.2) 1994 1.0 to 2.2x 1995 NetBSD OpenBSD 1995 1.1 to 1.2 OpenServer 1.0 to 2.2 5.0 to 5.04 1996 Solaris 1996 2.1 to 9 1997 1997 NetBSD 1.3 FreeBSD AIX 1998 1998 3.0 to 3.2 3.0 to 7.3 1999 Mac OS X 1999 Minix Linux Server FreeBSD 2000 2.x 2.0 to 6.x OpenServer 2000 3.3 to 4.x 5.0.5 to 5.0.7 2001 to 2002 2001 to 2002 2003 UnixWare 2003 7.x 2004 OpenBSD 2004 (System V R5) Mac OS X, 2.3 to 7.2 2005 to 2007 NetBSD 2005 to 2007 OS X, 1.4 to 9.x HP-UX macOS Solaris 11i v1 to 11i v3 2008 to 2009 10.x to 13.x FreeBSD 10 2008 to 2009 Minix 5.0 to 13.x DragonFly BSD OpenServer 2010 Operating Systems and System So ware 3.1.0 to 3.4.0 (Darwin 1.2.1 to 22) 1.0 to 6.4 6.x OpenSolaris 2010 & derivatives 2011 to 2018 Solaris (Illumos, etc.) 2011 to 2018  24 A Brief History of Computers and Operating Systems (5) Third generation: Personal computers (1980 – today) Large scale integration enabled to build chips with thousands of transistors/mm 2 (hundreds of millions today) Thus, microcomputers for personal use became powerful and affordable 1974: Intel releases the 8080, the first 8-bit general purpose CPU and the first disk-based OS: CP/M 1980: IBM designs the IBM PC and tasks Bill Gates (Microso ) to find them a suitable OS He purchases DOS (Disk Operating System) from a Seattle-based company and licenses it to IBM for the PC 1981: IBM releases the PC with MS-DOS as its operating system 1984: Apple releases the Macintosh with MacOS featuring a graphical user interface (GUI) the first GUI was developed at Xerox, but they did not realize its potential, unlike Steve Jobs… Fast forward to today: Microso develops Windows ▪ on top of MS-DOS: Windows 1.0 to 3.1, Windows 95, 98, ME ▪ with the Windows NT family: NT, 2000, XP, Vista, 7, 8, 10, 11 Apple continues to develop macOS: ▪ Mac OS versions 1 to 9 (2001) ▪ Mac OS X (and now macOS) with a new hybrid kernel (2001 – today) ▪ iOS, iPadOS, watchOS Linux is everywhere on the server market and embedded devices, e.g., Android Operating Systems and System So ware  25 A Quick Review of Computing Hardware Operating Systems and System So ware  26 Overview A computer system is a set of chips, devices and communication hardware. It comprises: Computing hardware that executes programs Central Processing Unit (CPU) Memory to store volatile information with fast access Random Access Memory (RAM), caches Various device controllers to communicate with hardware devices using different specifications Disk, video, USB, network, etc. A communication layer that enables all these components to communicate commands and data Bus Operating Systems and System So ware  27 Central Processing Unit The Central Processing Unit, or CPU/processor, is the brain of the computer. Its job is to load an instruction from memory, decode and execute it, and then move on to the next instruction and repeat. Each CPU understands one “language”, its instruction set, e.g., x86, ARMv7, which makes them not interoperable. A CPU contains the following components: Execution units that execute instructions ▪ Decoder reads an instruction and forwards to the proper execution unit Arithmetic/ Floating Point ▪ Arithmetic/Logical Unit (ALU) performs integer and binary operations Logical Unit Unit ▪ Floating-Point Unit (FPU) performs floating-point operations ▪ Memory Unit (MU) performs memory accesses Memory Unit Decoder Registers that store data ▪ State information, e.g., instruction pointer, stack pointer, return address ▪ Program values in general-purpose registers Registers Multiple levels of caches to avoid performing redundant and costly memory accesses L1 cache L1 cache data instructions L2 cache Operating Systems and System So ware  28 Memory and Devices The CPU is the “brain” of the computer and acts “by itself” (following the running program instructions). The other components act as they are instructed by the CPU. Memory is a passive device that stores data. The CPU and devices read from and write to it. Other devices perform operations as instructed by the CPU. e.g., display something on the monitor, send this through the network, etc. Communication between components happens through the bus, the communication layer that links them. Operating Systems and System So ware  29 Protection Domains and Processor Privilege Levels Operating Systems and System So ware  30 The Need for Isolation Some operations are critical and could break the system if done improperly: Modify the state of a device e.g., modify the state of the microphone LED to make it look muted when it is not e.g., make a USB drive read-only/writable Access restricted memory areas e.g., modify a variable from another program e.g., read private data – passwords – from other programs We cannot trust all application so ware to not do these critical operations! User applications can be written by anyone: Programmers lacking skills/experience/knowledge Malicious programmers that want to attack a system The operating system needs to isolate these operations to make the system safe and secure! Operating Systems and System So ware  31 Protection Domains In order to provide the necessary isolation, operating systems provide different protection domains or modes. These domains give different capabilities to the code executing on the machine. Usually, two protection domains are provided: Supervisor mode User mode They have different privilege levels, allowing or restricting a set of operations. Info Protection domains are so ware-defined by the operating system. The OS relies on hardware features to be enforce them. (We will discuss these features later on.) Operating Systems and System So ware  32 Supervisor Domain Supervisor domain (also referred to as S mode) has the highest privilege level. This means that all operations are allowed. Programs running in this domain can: Use all the instruction set defined by the CPU architecture Directly interact with hardware devices Access any memory area This domain is used by the kernel that contains the low level components of the operating system. Operating Systems and System So ware  33 User Domain User domain (also referred to as U mode) has the lowest privilege level. This means that some operations are restricted in this domain. Programs running in this domain cannot: Use privileged instructions that modify the system state, e.g., directly manipulate a hardware device Access some memory areas, e.g., access the memory of another program This domain is used by all the applications outside of the kernel: high level operating system services and user applications. Operating Systems and System So ware  34 Relationship Between Protection Domains User mode is usually a subset of supervisor mode. All the operations that can be performed in user mode can also be performed in supervisor mode. Protection domains are usually enforced with features provided by the hardware. Operating Systems and System So ware  35 Processor Privilege Levels In practice, protection domains are backed by hardware processor privilege levels, also called CPU modes or CPU states. For example, x86 provides four levels, also called protection rings. ARMv7 provides three privilege levels, while ARMv8 provides four. Ring 3 PL0 Ring 2 PL1 Ring 1 Ring 0 PL2 Privilege Privilege x86 protection rings ARMv7 privilege levels Careful with the numbers! There is no standard order in the value of the levels! For x86, ring 0 is the most privilege, while PL0 is the least privileged on ARMv7! Operating Systems and System So ware  36 Matching Protection Domains to Privilege Levels Most operating systems use two protection domains (user and supervisor), e.g., Linux, Windows, macOS. Thus, they only need two processor privilege levels, as specified by the Instruction Set Architecture: Ring 3 PL0 Ring 2 PL1 Ring 1 Ring 0 PL2 Kernel Kernel Applications Applications Protection domains and protection rings on x86 platforms Protection domains and privilege levels on ARMv7 platforms Virtualized context In virtualized environments, the hypervisor needs specific instructions. On x86, they are in a new ring -1 level, while ARMv7 uses its PL2 level. Operating Systems and System So ware  37 Switching Between Modes When applications running in user mode need to use a privileged feature, they have to switch to supervisor mode. e.g., writing to a file on disk, allocating memory, etc. This switching is performed through system calls, which are function calls from user to supervisor mode. They provide a controlled interface between user space applications and privileged operating system services. This ensures that user applications can perform privileged operations in a secure way, only through kernel code. Examples: read() and write() for file manipulation, listen(), send() and receive() for networking In addition to calling the function, a system call also checks that: The program is allowed to perform this request e.g., the program is not trying to manipulate a resource it is not allowed to access The arguments passed by the program are valid e.g., the program is not trying to get privileged information with a forged pointer Operating Systems and System So ware  38 Protection Domains and Operating System Architecture Let’s go back to our operating system architecture and add the protection domains. User applications and high level operating system services run in user mode. The kernel runs in supervisor mode. User Web Text... Media applications browser editor player User mode Libraries Utilities Shell Operating system Kernel Supervisor mode Hardware HDD SSD... Keyboard What components of the operating system are in the kernel? Operating Systems and System So ware  39 Operating System Architectures Operating Systems and System So ware  40 Supervisor or User Mode? That Is the Question When designing an operating system, one main question has to be answered: Which component will run in supervisor mode (and which in user mode)? In other words: Which components of the operating system are part of the kernel? Some components have to be in the kernel because they need privileged instructions. Other components can reside anywhere. Their position will have an impact on safety, performance and API. There are four main architectures: Monolithic kernels Microkernels Hybrid kernels Unikernels Let’s have a look at these different architectures! Operating Systems and System So ware  41 Monolithic Kernels A monolithic kernel provides, in kernel space, a large amount of core features, e.g., process and memory management, synchronization, file systems, etc., as well as device drivers. Applications user mode Libraries Characteristics Defines a high level interface through system calls System calls Good performance when kernel components communicate (regular function calls in kernel space) IPC, file systems Limited safety: if one kernel component crashes, the whole system crashes supervisor mode Examples Scheduler, virtual memory Unix family: BSD, Solaris Device drivers, interrupt handlers Unix-like: Linux DOS: MS-DOS Critical embedded systems: Cisco IOS Hardware Source: Wikimedia Modularity Monolithic kernels can be modular and allow dynamic loading of code, e.g., drivers. These are sometimes called modular monolithic kernels. Operating Systems and System So ware  42 Microkernels A microkernel contains only the minimal set of features needed in kernel space: address- space management, basic scheduling and basic inter-process communication. Applications All other services are pushed in user space as servers: file systems, device drivers, high level interfaces, etc. Libraries Characteristics user mode Small memory footprint, making it a good choice for embedded systems Application Device UNIX File Enhanced safety: when a user space server crashes, it does not crash the whole system IPC driver server server Adaptability: servers can be replaced/updated easily, without rebooting Limited performance: IPCs are costly and numerous in such an architecture Examples supervisor Basic IPC, virtual memory, scheduling mode Minix L4 family: seL4, OKL4, sepOS Hardware Mach Source: Wikimedia Zircon Operating Systems and System So ware  43 Hybrid Kernels The hybrid kernel architecture sits between monolithic kernels and microkernels. It is a monolithic kernel where some components have been moved out of kernel space as Applications servers running in user space. While the structure is similar microkernels, i.e., using user servers, hybrid kernels do not Libraries user provide the same safety guarantees as most components still run in the kernel. mode Controversial architecture UNIX File server server This architecture’s existence is controversial, as some just define it as a stripped down monolithic kernel. Application Device Examples IPC driver supervisor mode Windows NT Basic IPC, virtual memory, scheduling XNU (Mach + BSD) Hardware Source: Wikimedia Operating Systems and System So ware  44 Unikernels A unikernel, or library operating system, embeds all the so ware in supervisor mode. The kernel as well as all user applications run in the same privileged mode. Applications It is used to build single application operating systems, embedding only the necessary set of applications in a minimal image. Libraries Characteristics System calls supervisor High peformance: system calls become regular function calls and no copies between mode user and kernel spaces IPC, file systems Security: attack surface is minimized, easier to harden Usability: hard to build unikernels due to lack of features supported Scheduler Device drivers, interrupt handlers Examples Unikra Hardware clickOS IncludeOS Operating Systems and System So ware  45 Comparison Between Kernel Architectures Monolithic kernel Microkernel Hybrid kernel Unikernel Applications Applications Applications user Applications mode Libraries user Libraries Libraries Libraries mode user mode System calls System calls UNIX File supervisor server server Application Device UNIX File mode IPC, file systems IPC driver server server IPC, file systems supervisor Application Device mode Scheduler, virtual memory supervisor IPC driver Scheduler mode supervisor Device drivers, interrupt handlers Basic IPC, virtual memory, scheduling Basic IPC, virtual memory, scheduling Device drivers, interrupt handlers mode Hardware Hardware Hardware Hardware The choice of architecture has various impacts on performance, safety and interfaces: Switching modes is costly: minimizing mode switches improves performance Supervisor mode is not safe: minimizing code in supervisor mode improves safety and reliability High level interfaces for programmers are in different locations depending on the architecture i.e., in the kernel for monolithic, but in libraries or servers for microkernels Operating Systems and System So ware  46 Recap Operating Systems and System So ware  47 Recap 1. Definition The operating system is the so ware layer that lies between applications and hardware. It provides applications simple abstractions to interact with hardware and manages resources. It usually offers the following services: program management, memory management, storage management, networking and human interface. 2. Protection domains Supervisor mode for critical operations in the kernel, user mode for the non-critical OS services and user applications. Hardware enforces these with processor privilege levels. System calls allow user mode applications to use supervisor mode services. 3. Kernel architectures Monolithic, microkernel, hybrid, unikernel. Next week, we will start diving into program management in the OS with processes and threads! Operating Systems and System So ware  49 Chapter 2: Program Execution Operating Systems and System So ware  50 This Week’s Program We will explore how programs are managed and executed by the operating system: 1. Processes Abstraction of a program, process control block, states 2. Threads Abstraction of a unit of execution, user vs. kernel threads, multi-threading 3. Scheduling General concepts, batch, interactive, real time Operating Systems and System So ware  51 Processes Operating Systems and System So ware  52 One System, Multiple Programs Your system runs a large number of applications at the same time: E-mail client Web browser(s) Music player Development environment … In such a multiprogramming system, there will be more programs than CPUs available to run them. The job of the OS is to switch between programs very quickly, every tens or hundreds milliseconds, to give the illusion of parallelism. The OS needs to keep track of each running program to manage them properly! Operating Systems and System So ware  53 The Process Model A process is the abstraction that represents an instance of a running program. Processes contain the set of information required for the program to execute properly: Code (the binary representation of the program’s instructions) Memory (variables, stack, heap, etc.) Registers (instruction pointer, stack pointer, etc.) Resources in use (open files, sockets, etc.) They are independent entities that the OS manipulates, choosing which one to run and when. Process switch CPU A B C A B C A Time Caution Program ≠ process! The program is the ‘recipe’ (the code) and the process is an execution of the program. Operating Systems and System So ware  54 Process Creation A new process can be created for various reasons: A user creates it by starting a new program e.g., by clicking on the icon or starting it from the command line Another process creates it using a process creation system call e.g., your web browser starts your PDF reader a er downloading a file When the system starts an initial process is created to initialize the system, launch other programs like the desktop environment, etc. Depending on their purpose, processes can be classified as: Foreground processes that interact with the user e.g., video player, calculator, etc. Background processes that run by themselves with no user interaction required e.g., weather service, notification service, network configuration, etc. Note Background processes that always stay in the background are also called daemons or services. Operating Systems and System So ware  55 Process Hierarchy Most systems keep an association between a process and the process that created it, its parent. In UNIX-based systems, all processes are linked in this way, creating a process tree. The root of the tree is init, the first process created when the system boots. init thermald bluetoothd sshd cupsd GNOME The init process also adopts orphaned processes. NetworkManager thunderbird firefox vscode gnome-terminal e.g., if gnome-terminal terminates without terminating its child processes (ssh and emacs), they become children of init firefox-tab1 firefox-tab2 firefox-tab3 vscode-win1 vscode-win2 ssh emacs Windows does not keep a full process tree. Parent processes are given a handle on their children. The handle can be passed on to another process. Operating Systems and System So ware  56 Process States A er its creation, a process can go into three different states: Ready (also called runnable) The process can be executed and is waiting for the scheduler to allocate a CPU for it Running The process is currently being executed on the CPU Running Blocked The process cannot run because it is waiting for an event to complete 2 4 3 State transitions: Ready Blocked 1. Process creation ( ∅ → ready) 1 5 2. Scheduler picks the process to run on the CPU (ready → running) 3. Scheduler picks another process to run on the CPU (running → ready) 4. Process cannot continue to run, waiting for an event (running → blocked) e.g., keyboard input, network packet, etc. 5. Blocking event is complete, the process is ready to run again (blocked → ready) Operating Systems and System So ware  57 Process Model and Scheduling Processes have different behaviors depending on the program they execute. A command line interpreter (CLI) repeatedly: ▪ Waits for a user to type in commands (running → blocked) ▪ Wakes up and executes them when available (blocked → ready ↔ running) A video player repeatedly: ▪ Reads data from disk and waits for it to be available in memory (running → blocked) ▪ Copies the frames into graphical memory (blocked → ready ↔ running) A program that computes digits of π never waits and only uses the CPU (ready ↔ running) P0 P1 P2 Pn The scheduler is the component of the OS that manages the allocation of CPU resources to processes, depending on their state. Scheduler CPU Operating Systems and System So ware  58 Process Implementation For each process, the OS maintains a process control block (PCB) to describe it. Runtime Memory Files Process ID (PID) Address space Current working directory (CWD) Segments Parent Process ID (PPID) Page table User ID (UID) Memory mappings Registers Group ID (GID) Instruction pointer Stack pointer File descriptors General purpose Page table pointer (CR3) Signals Scheduler metadata Used CPU time Time of next alarm Operating Systems and System So ware  59 Process Memory Layout A process’ memory, or address space, is split into several sections. 0xFFFFFFFF Kernel memory is shared between all processes, accessible only in supervisor mode In 32 bit Linux, 1 GB for the kernel, 3 GB for user space. Kernel In 64 bit Linux, 128 TB for the kernel, 128 TB for user space reserved for the kernel, cannot be accessed by user space Text is where the program binary is loaded in memory It contains the actual binary instructions that will be executed by the CPU. 0xC0000000 Stack Data contains the static initialized variables from the binary environment, local variables Initialized global variables and static local variables, constant strings e.g., a global int count = 0; or a local static int idx = 0; BSS (block starting symbol) contains static uninitialized variables e.g., a global static int i; Heap dynamically allocated memory Heap contains dynamically allocated memory, grows towards higher addresses e.g., malloc(), brk/sbrk, mmap() BSS uninitialized data Stack contains local variables, environment variable, calling context (stack frame) Grows towards address 0x00000000 Data initialized static variables Text program code 0x00000000 Operating Systems and System So ware  60 Process Registers Registers are the part of the process state that are physically on the CPU Instruction Pointer (IP), or Program Counter (PC) Contains the address of the next instruction to execute if not jumping x86-64: RIP arm64: PC Stack Pointer (SP) Contains the address of the top of the stack x86-64: RSP arm64: SP General Purpose (GP) Contains values or addresses used by instructions x86-64: RAX, RBX, …, R15 arm64: X0–X30 Page Table Pointer Contains the address of the memory mapping x86-64: CR3 arm64: TTBR We’ll come back to how memory mappings and page tables work in a future lecture. Operating Systems and System So ware  61 Context Switch When the OS changes the currently running process, it performs a context switch. The OS needs to exchange the PCB of the current process with the PCB of the next process. Context switching between the running process A and the ready process B happens in several steps: 1. Change the state of the currently running process A to ready 2. Save the CPU registers into A’s PCB 3. Copy the registers from B’s PCB into the CPU registers 4. Change the state of B from ready to running Process A 2 3 Process B CPU Registers Registers Registers Operating Systems and System So ware  62 Process Isolation Another property of processes is that they are isolated from each other. They act independently, as if they were running alone on the machine. They do not share memory, open files, etc. Tip We will see how this is enforced later when discussing memory and file management. Multiprocessing They can communicate and collaborate if explicitly stated in the program. We will discuss that in a future lecture. Operating Systems and System So ware  63 POSIX API: Processes Let’s quickly see the POSIX API to manage processes in C. pid_t fork(void); Create a new process by duplicating the calling process, i.e., its PCB and memory. Upon success, returns the PID of the child in the parent, 0 in the child. Returns -1 upon error. int exec[lvpe](const char *path, const char *arg,...); This family of functions replaces the current program with the one passed as a parameter. Returns -1 upon error. Upon success, it doesn’t return, but the new program starts. pid_t wait(int *status); Wait for any child process to terminate or have a change of state due to a signal. Returns the PID of the child on success, -1 on failure. Operating Systems and System So ware  64 POSIX API: Processes – Example fork.c ❱ gcc -o fork fork.c 1 #include ❱./fork 2 #include Parent PID: 469002 3 #include Fork success, my child has PID 469003 4 #include I am the child! 5 I waited 3 seconds 6 int main(int argc, char **argv) Child has terminated, wait over 7 { 8 pid_t pid; 9 10 printf("Parent PID: %d\n", getpid()); 11 12 pid = fork(); 13 switch (pid) { 14 case -1: 15 printf("[%d] Fork failed...\n", getpid()); 16 return EXIT_FAILURE; 17 case 0: 18 printf("[%d] I am the child!\n", getpid()); 19 sleep(3); 20 printf("[%d] I waited 3 seconds\n", getpid()); 21 break; 22 default: 23 printf("[%d] Fork success, my child is PID %d\n", getpid(), pid 24 wait(NULL); 25 printf("[%d] Child has terminated, wait is over\n", getpid()); 26 } 27 28 return EXIT_SUCCESS; 29 } Operating Systems and System So ware  65 Processes: a Heavyweight Mechanism Applications may benefit from executing multiple tasks at the same time, e.g., your development environment needs to wait for keyboard input, syntax check, render the UI, run extensions, etc. Using one process per task is not always a good idea! Creating a process means copying an existing one → It is a costly operation! Processes don’t share memory → Good for isolation. → Communication must be explicitly set up! Is there a more lightweight mechanism to execute parallel programs! Operating Systems and System So ware  66 Threads A thread is the entity that executes instructions. It has a program counter, registers and a stack. A process contains one or more threads, and threads in the same process share their memory. Threads are sometimes called lightweight processes. Tip Another definition of a process is a set of threads sharing an address space. But we will discuss that in future lectures when discussing memory management. Operating Systems and System So ware  67 Process Model and Thread Model Let’s go back to our process model, and add threads in the mix. Processes group resources together, e.g., memory, open files, signals, etc., while threads execute code. Examples: Web server Text editor Operating Systems and System So ware  68 Threads: Shared vs. Private Data Threads in the same process share some resources, while others are thread-private. Per-process resources Per-thread resources Address space Program counter Global variables Registers Open files Stack Child processes State Pending alarms Signals and signal handlers Accounting metadata Operating Systems and System So ware  69 Threading Implementation Threads are usually implemented as a thread table in the process control block. Runtime Memory Files Process ID (PID) Address space Current working directory (CWD) Segments Parent Process ID (PPID) Page table User ID (UID) Memory mappings Registers Group ID (GID) Instruction Page table pointer pointer (CR3) Stack pointer File descriptors Thread General table[ purpose ] Page table Thread ID pointer (CR3) Registers SignalsInstruction pointer Stack pointer Scheduler General metadata purpose Used CPU time Signals Time of next alarm Scheduler metadata Used CPU time Time of next alarm Operating Systems and System So ware  70 POSIX API: Threads Let’s have a quick look at the main functions of the POSIX API to manipulate threads: int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*function)(void *), void *arg); Create a new thread that will execute function(arg). void pthread_exit(void *retval); Terminate the calling thread. int pthread_join(pthread_t thread, void **retval) Wait for thread to terminate. N