Think OS by Allen B. Downey

Think OS: A Brief Introduction to Operating Systems

• In a statically-typed language, you can tell by looking at the program what type each variable refers to. In a dynamically-typed language, you don't always know the type of a variable until the program is running.
• In general, "static" refers to things that happen at compile time, and "dynamic" refers to things that happen at run time.
• The location of a variable is called its "address".
• During parsing, the compiler reads the source code and builds an internal representation of the program, called an "abstract syntax tree".
• The compiler reads the internal representation of the program and generates machine code or byte code.
• It is usually a good idea to turn off optimization while you are developing new code. Once the program is working and passing appropriate tests, you can turn on optimization and confirm that the tests still pass.
• An abstraction is a simplified representation of something complicated.
• A large part of software engineering is designing abstractions that allow users and other programmers to use powerful and complicated systems without having to know about the details of their implementation.
• An important kind of abstraction is virtualization, which is the process of creating a desirable illusion.
• One of the most important principles of engineering is isolation: when you are designing a system with multiple components, it is usually a good idea to isolate them from each other so that a change in one component doesn't have undesired effects on other components.
• One of the most important goals of an operating system is to isolate each running program from the others so that programmers don't have to think about every possible interaction.
• A process is a software object that represents a running program.
• Most operating systems have the ability to interrupt a running process at almost any time, save its hardware state, and then resume the process later.
• Most operating systems create the illusion that each process has its own chunk of memory, isolated from all other processes.
• "daemon" is used in the sense of a helpful spirit, with no connotation of evil.
• A bit is a binary digit; it is also a unit of information. [...] In general, if you have b bits, you can indicate one of 2^b values.
• In general, if the probability of the outcome is 1 in N, then the outcome contains log2N bits of information.
• Intuitively, unexpected new carries a lot of information; conversely, if there is something you were already confident of, confirming it contributes only a small amount of information.
• While a process is running, most of its data is held in "main memory", which is usually some kind of random access memory (RAM).
• Each byte in main memory is specified by an integer "physical address". The set of valid physical addresses is called the physical "address space".
• When a program reads and writes values in memory, it generates virtual addresses. The hardware, with help from the operating system, translates to physical addresses before accessing main memory. This translation is done on a per-process basis, so even if two processes generate the same virtual address, they would map to different locations in physical memory.
• Virtual memory is one important way the operating system isolates processes from each other.
• The data of a running process is organized into 4 segments:
• The text segment contains the program text; that is, the machine language instructions that make up the program.
• The static segment contains variables that are allocated by the compiler, including global variables and local variables that are declared static.
• The stack segment contains the run-time stack, which is made up of stack frames. Each stack frame contains the parameters and local variables of a function.
• The heap segment contains chunks of memory allocated at run time, usually by calling the C library function malloc.
• Local variables on the stack are sometimes called "automatic", because they are allocated automatically when a function is called, and freed automatically when the function returns.
• In C there is another kind of local variable, called "static", which is allocated in the static segment. It is initialized when the program starts and keeps its value from one function call to the next.
• Most processors provide a memory management unit (MMU) that sits between the CPU and main memory. The MMU performs fast translation between VAs and PAs.
• If a process doesn't use a virtual page, we don't need an entry in the page table for it.
• Searching an associative table can be slow in software, but in hardware we can search the entire table in parallel, so associative arrays are often used to represent page tables in the MMU.
• The fundamental idea is that page tables are sparse, so we have to choose a good implementation for sparse arrays.
• A "file system" is a mapping from each file's name to its contents.
• A "file" is a sequence of bytes.
• The gap in performance between main memory and persistent storage is one of the major challenges of computer system design.
• Sometimes the operating system can predict that a process will read a block and start loading it before it is requested.
• If a process has used a block recently, it is likely to use it again soon. If the operating system keeps a copy of the block in memory, it can handle future requests at memory speed.
• Performance techniques: block transfers, prefetching, buffering, caching.
• A UNIX inode contains information about the file including: the user ID of the file owner, permission flags indicating who is allowed to read/write/execute it, and timestamps that indicate when it was last modified and accessed.
• The file abstraction is really a "stream of bytes" abstraction, which turns out to be useful for many things, not just file systems.
• Floating-point numbers are represented using the binary version of scientific notation.
• Most computers use the IEEE standard for floating-point arithmetic.
• There are two common uses of C unions. One is to access the binary representation of data. Another is to store heterogeneous data.
• Memory management is one of the most challenging parts of designing large software systems, which is why most modern languages provide higher-level memory management features like garbage collection.
• Memory errors can be difficult to find because the symptoms are unpredictable.
• Safe memory management requires design and discipline.
• Often there is a trade off between safe memory management and performance.
• If you allocate a chunk of memory and never free it, that's a "memory leak".
• Because memory management is so difficult, most large programs, like web browsers, leak memory.
• When malloc allocates a chunk, it adds space at the beginning and end to store information about the chunk, including its size and the state (allocated or free).
• Fragmentation wastes space; it also slows the program down by making memory caches less effective.
• One of the fundamental problems of computer architecture is the "memory bottleneck".
• A "cache" is a small, fast memory on the same chip as the CPU.
• The tendency of a program to use the same data more than once is called "temporal locality". The tendency to use data in nearby locations is called "spatial locality".
• Caches are fast because they are small and close to the CPU, which minimizes delays due to capacitance and signal propagation. If you make a cache big, it will be slower.
• Most cache policies are based on the principle that history repeats itself; if we have information about the recent past, we can use it to predict the immediate future.
• In an operating system, the kernel is the lowest level of software, surrounded by several other layers, including an interface called a "shell".
• At its most basic, the kernel's job is to handle interrupts. An "interrupt" is an event that stops the normal instruction cycle and causes the flow of execution to jump to a special section of code called an "interrupt handler".
• A hardware interrupt is caused when a device sends a signal to the CPU.
• A software interrupt is caused by a running program.
• When a program needs to access a hardware device, it makes a "system call", which is similar to a function call, except that instead of jumping to the beginning of the function, it executes a special instruction that triggers an interrupt, causing the flow of execution to jump to the kernel. The kernel reads the parameters of the system call, performs the requested operation, and then resumes the interrupted process.
• In general, the kernel doesn't know which registers a process will use, so it has to save all of them.
• In a multi-tasking system, each process is allowed to run for a short period of time called a "time slice" or "quantum".
• When a process is created, the operating system allocates a data structure that contains information about the process, called a "process control block" or PCB.
• Most schedulers use some form of priority-based scheduling, where each process has a priority that can be adjusted up or down over time. When the scheduler runs, it chooses the runnable process with the highest priority.
• Simple scheduling policies are usually good enough.
• Scheduling tasks to meet deadlines is called "real-time scheduling".
• When you create a process, the operating system creates a new address space, which includes the text segment, static segment, and heap; it also creates a new "thread of execution", which includes the program counter and other hardware state, and the run-time stack.
• A "mutex" is an object that guarantees a "mutual exclusion" for a block of code; that is, only one thread can execute the block at a time.
• Many simple synchronization problems can be solved using mutexes.
• A condition variable is a data structure associated with a condition; it allows threads to block until the condition becomes true.
• There are some synchronization problems that can be solved simply with semaphores, yielding solutions that are more demonstrably correct.
• One nice thing about using wrapper functions is that you can encapsulate the error checking code, which makes the code that uses these functions more readable.
• Any problem that can be solved with semaphores can also be solved with condition variables and mutexes.