# A. Preliminaries These are lecture notes for PB152. Everything that you need to know to pass the subject (excluding the seminar, which is a separate subject – PB152cv) is contained in this document. The lectures cover the same material in a different format. │ Study Materials │ │ • «lecture notes» are the main study text │ ◦ these include the slides used in the lecture │ ◦ mostly self-contained with minimal dependencies │ ◦ English version already available in the IS │ • you can make your own notes during the lecture │ • the translated version will not be updated this year The lecture notes is the text you are reading right now. This is your main study resource; it is based on the lecture slides, but with additional details that would not fit into the slide format. These lecture notes should be self-contained in the sense that they only rely on knowledge you have from other courses, like PB150 Computer Systems (or PB151) or PB071 Principles of Low-Level programming. Likewise, being familiar with the topics covered in these lecture notes is sufficient to pass the exam. │ Seminars │ │ • a separate, optional course (code «PB152cv») │ • covers operating systems from a practical perspective │ • get your hands on the things we'll talk about here │ • offers additional practice with C programming The seminar is a good way to gain some practical experience with operating systems. It will mainly focus on interaction of programs with OS services, but will also cover user-level issues like virtualisation, OS installation and shell scripting. │ Books │ │ • there are a few good OS books │ • you are encouraged to get and read them │ │ • A. Tanenbaum: Modern Operating Systems │ • A. Silberschatz et al.: Operating System Concepts │ • L. Skočovský: Principy a problémy OS UNIX │ • W. Stallings: Operating Systems, Internals and Design │ • many others, feel free to explore The books mentioned here usually cover a lot more ground than it is possible to include in a single-semester course. The study of operating systems is, however, very important in many sub-fields of computer science, and also in most programming disciplines. Spending extra time on this topic will likely be well worth your time. │ Exam │ │ • written multiple-choice test │ • 3 types of questions │ a. 12 elementary │ b. 12 intermediate │ c. 6 advanced │ • maximum is 90 points, 45 to pass │ • grades: 81+ A, 72+ B, 63+ C, 54+ D, 45+ E Each question is graded +3/0/-1 for correct, absent and incorrect answer, respectively. It might be better to not answer if you don't know what the correct choice is. The exam will be offline and ‘closed book’ (no materials allowed). The first (elementary) part will present 4 direct answers to one of the review questions listed in these notes. In the second (intermediate) part, each question will present 4 statements (a short paragraph) about some aspect of operating systems. In both cases, the question will indicate how many of the statements are true and you will need to select all of those. In the advanced part, there will be no indication of how many true or false statements there are. These questions get an extra (fifth) choice ‘none of the above statements are correct’ which is of course mutually exclusive with all the others. The exam is in Czech by default, with each technical term also appearing in English (in brackets). However, you can opt to take the entire exam in English if you prefer. │ Topics │ │ 1. Anatomy of an OS │ 2. System Libraries and APIs │ 3. The Kernel │ 4. File Systems │ 5. Basic Resources and Multiplexing │ 6. Concurrency and Locking In the first half of the semester, we will deal with the basic components and abstractions used in general-purpose operating systems. The first lecture will simply give an overview of the entire OS and will attempt to give you an idea how the parts fit together. In the second lecture, we will cover the basic programming interfaces provided by the OS, provided mainly by system libraries. │ Topics (cont'd) │ │ 7. Device Drivers │ 8. Network Stack │ 9. Command Interpreters & User Interfaces │ 10. Users and Permissions │ 11. Virtualisation & Containers │ 12. Special-Purpose Operating Systems The second half of the semester will start with device drivers, which form an important part of operating systems in general, since they mediate communication between application software and hardware peripherals connected to the computer. In a similar fashion, the network stack allows programs to communicate with other computers (and software running on those other computers) that are attached to a computer network. │ Related Courses │ │ • PB150/PB151 Computer Systems │ • PB153 Operating Systems and their Interfaces │ • (PA150 Advanced OS Concepts) │ • (PV062 File Structures) │ • PB071 Principles of Low-level programming │ • PB173 Domain-specific Development in C/C++ There is a number of courses that overlap, provide prerequisite knowledge or extend what you will learn here. The list above is incomplete. The course PB153 is an alternative to this course. Most students are expected to take PB071 in parallel with this course. Even though knowledge of C isn't strictly required for the theory we cover, it will definitely be useful. A basic level of C programming, however, will be needed for the optional seminar (PB152cv). # B. Semester Overview This section gives a high-level overview of the topics that will be covered in individual lectures. Think of it as an extended table of contents, or as a collection of abstracts, one for each of the upcoming lectures. │ 2 System Libraries and APIs │ │ • «POSIX»: Portable Operating System Interface │ • UNIX: (almost) everything is a «file» │ • the least common denominator of programs: C │ • user view: objects, archives, shared libraries │ • «compiler», linker System libraries and their APIs provide the most direct access to operating system services. In the second lecture, we will explore how programs access those services and how the system libraries tie into the C programming language. We will also deal with basic artifacts that make up programs: object files, archive files, shared libraries and how those come about: how we go from a C source file all the way to an executable file through compilation and linking. Throughout this lecture, we will use POSIX as our go-to source of examples, since it is the operating system interface that is most widely implemented. Moreover, there is abundance of documentation and resources both online and offline. │ 3 The Kernel │ │ • «privileged» CPU mode │ • the boot process │ • boundary enforcement │ • kernel designs: micro, «mono», exo, … │ • «system calls» In the third lecture, we will focus on the kernel, arguably the most important (and often the most complicated) part of an operating system. We will start from the beginning, with the boot process: how the kernel is loaded into memory, initialises the hardware and starts the user-space components (that is, everything that is not the kernel) of the operating system. We will then talk about boundary enforcement: how the kernel polices user processes so they cannot interfere with each other, or with the underlying hardware devices. We will touch on how this enforcement makes it possible to allow multiple users to share a single computer without infringing on each other (or at least limiting any such infringement). Another topic of considerable interest will be how kernels are designed and what is and what isn't part of the kernel proper. We will explore some of the trade-offs involved in the various designs, especially with regards to security and correctness vs performance. Finally, we will look at the «system call» mechanism, which is how the user-space communicates with the kernel, and requests various low-level operating system services. │ 4 File Systems │ │ • why and how │ • abstraction over shared «block storage» │ • directory «hierarchy» │ • everything is a file revisited │ • i-nodes, directories, hard & soft links Next up are file systems, which are a very widely used abstraction on top of persistent block storage, which is what hardware storage devices provide. We will ask ourselves, first of all, why filesystems are important and why they are so pervasively implemented in operating systems, and then we will look at how they work on the inside. In particular, we will explore the traditional UNIX filesystem, which offers important insights about the architecture of the operating system as a whole, and about important aspects of the POSIX file semantics. │ 5 Basic Resources and Multiplexing │ │ • «virtual memory», processes │ • sharing CPUs & «scheduling» │ • processes vs threads │ • «interrupts», clocks One of the basic roles of the operating system is management of various resources, starting with the most basic: the CPU cores and the RAM. Since those resources are very important to every process or program, we will spend the entire lecture on them. In particular, we will look at the basic units of resource assignment: threads for the CPU and processes for memory. We will also look at the mechanisms used by the kernel to implement assignment and protection of those resources, namely the virtual memory subsystem and the scheduler. │ 6 Concurrency and Locking │ │ • inter-process «communication» │ • accessing «shared resources» │ • mutual exclusion │ • «deadlocks» and deadlock prevention Scheduling and slicing of CPU time is closely related to another important topic that pervades operating system design: concurrency. We will take a high-level, introductory look at this topic, since the details are often complicated, architecture-specific and require deep understanding of both hardware (SMP, cache hierarchies) and of kernels. │ 7 Device Drivers │ │ • user vs kernel drivers │ • interrupts &c. │ • GPU │ • PCI &c. │ • block storage │ • network devices, wifi │ • USB │ • bluetooth One of the fundamental roles of an operating system is to mediate access to hardware devices. Some of the code that provides hardware access deals mainly with the software interfaces and APIs – this is known as hardware abstraction. However, to make this abstraction work, there is often a large amount of device-specific (or at least device-class-specific) ‘glue’ – also known as device drivers. One of the important questions will be the interplay between processor-level protections and direct hardware access and what this means for drivers. We will see that for some (but not all) types of hardware, only privileged programs (either inside the kernel, or close to it) can reasonably mediate between hardware itself and between higher levels of the system (hardware abstraction layer, application software, etc.). │ 8 Network Stack │ │ • TCP/IP │ • name resolution │ • socket APIs │ • firewalls and packet filters │ • network file systems While there is a dedicated course about networking, we will spend one of our lectures talking about networks: in modern operating systems, networking is an integral part of the package and networking considerations often influence other parts of the system. We will look at the ubiquitous TCP/IP stack, how it integrates into an operating system and what are the APIs that applications can use to take advantage of network services. We will also touch on network-related functionality that is often deeply integrated into operating systems: packet filtering and network file systems. │ 9 Command Interpreters & User Interfaces │ │ • «interactive» systems │ • history: consoles and terminals │ • «text-based» terminals, RS-232 │ • bash and other Bourne-style shells, POSIX │ • «graphical»: X11, Wayland, OS X, Windows, Android, iOS The next lecture will focus on human-computer interaction, which is clearly a central aspect of the experience of using a computer and is therefore an important part of most general-purpose operating systems. Even computers that do not directly (physically) interact with humans usually present some form of an interface, usually mediated over the network. We will first look at ‘traditional’ text-based interfaces, which are still in common use among system and network engineers and computer programmers, but we will also look in some depth at the graphics stacks that power modern devices (up to and including smartphones). │ 10 Users and Permissions │ │ • «multi-user» systems │ • «isolation», ownership │ • file system «permissions» │ • capabilities There are two important use-cases for computers (and hence operating systems) in which higher-level access control and permission management is important: first, when a single computer is shared by multiple users (this is the more traditional case), but in more modern times, also whenever we execute untrusted or semi-trusted programs on our devices (think application permissions on smartphones, web pages that execute javascript on your laptop and so on). │ 11 Virtualisation & Containers │ │ • resource multiplexing redux │ • «isolation» redux │ • multiple kernels on a single system │ • type 1 and type 2 «hypervisors» │ • ‹virtio› A computer, along with its operating system, is a natural ‘unit’ of computation resources – it conveniently packages up the resources themselves, with a software stack and configuration. Unfortunately, computers – being physical devices – are somewhat inflexible and unwieldy: they have to be procured, placed in racks in air-conditioned rooms, attached to a power source, to each other and to the larger network. Their physical components are prone to wear and failure, and need to be replaced or repaired regularly. Virtualization makes it possible to detach the logical aspects of a computer – its installed software, data storage and configuration – from the physical box. This improves hardware utilization, decouples hardware maintenance from software aspects and makes everyone's life easier (most of the time, anyway). In this lecture, we will peek under the hood of modern hypervisor-based virtual machines and how they are implemented in the current generation of operating systems. │ 12 Special-Purpose Operating Systems │ │ • general-purpose vs special-purpose │ • «embedded» systems │ • «real-time» systems │ • high-assurance systems (seL4) Throughout most of the course, we will have talked about general-purpose operating systems: those that run on personal computers and servers. The last lecture will be dedicated to more specialised systems: those that run in washing machines, on satellites or on the Mars rovers. We will also briefly cover high-assurance systems, which focus on extremely high reliability and/or security.