Focus questions: What is an OS and what does it do? How should we evaluate OSs and what are some of the trade-offs their designers face? What is the history of OSs and what new functionality will we see in future OSs?
1.1 Fact: Operating Systems solve problems that may be faced in many different situations. As such, the techniques, design patterns, and methods of dealing with these problems, and the complexity of the operating system itself, may be found useful in any large software application.
What is an operating system? The layer of software that manages a computer's resources for its users and their applications.
What roles does an operating system play? Referee, Illusionist, and glue.
What responsibility does the OS have as a referee? To provide fault tolerance, prevent user-mode applications from interfering with OS functionality. To facilitate communication between applications. To allocate finite system resources effectively.
What responsibilities does the OS have as illusionist? To provide an ideal virtual environment for applications to run, allowing applications to be created with certain assumptions as to the memory available, or the continuity of an application's execution.
What responsibilities does the OS have as glue? The OS provides useful abstractions and interfaces that allow programs to communicate with one another and also to operate within the operating system in a way that makes the application seem at home in the environment (dialog boxes, windows, etc).
The illusionist, or virtualization, aspect of operating systems serve to mask the hardware of a computer and offer a consistent interface to these resources, and also present a simplified view of these resources to applications.
What are some examples of common services that may be provided by OSs? GUI, file operations, network communication
What makes up the bulk of the code of an operating system? Offering common services to applications.
What makes up the bulk of the complexity of an operating system? Resource sharing and masking hardware limits.
What are some examples of types of programs that face some of the same challenges of operating systems? Web browsers, cloud computing, media players (Flash, Silverlight, Java),
Do: Consider how web browsers and cloud computing have parallels to the challenges faced by operating systems.
#1.2 Evaluation Criteria (p20) Creation of an operating system is all about _____. trade-offs
What are the different goals of an operating system, those typically involved in trade-offs? Reliability, Adoption, Portability, Performance, Security (RAPPS)
Reliability: that a system does what it is designed to do.
Why do techniques used for common software, such as testing, not work as well with operating systems? Because OSs operate in a hostile environment, and malicious code takes advantage of vulnerabilities that would follow rarer, and thus less test-covered sections.
Availability: the time that a system is in a useable state. Related to reliability.
If a system goes down often but always saves the users work and is not subject to bugs, it is... reliable but not available.
What two things impact availability? Give a brief definition of each. Mean time to failure (frequency of failures) and mean time to repair (how long it takes to bring the system back to a working state) (MTTF, MTTR)
1.2.2 - Security ______ is the property that a computer's operation cannot be altered by a malicious attacker. Security
_____ is the property that a computer's data can only be accessed by authorized users. Privacy
Nothing is ever 100% secure, but there's still some responsibility placed on the OS to ensure that something innocuous doesn't allow an attacker to take over the system. Bugs can, in many cases, be the root of a vulnerability within a computer program, so strong fault isolation can help keep a computer secure.
One difficulty in ensuring security is that, in many cases, there are situations where you would want a program to execute a potentially risky operation. Programs may need access to protected files and resources.
______ is how the OS ensures that only permitted actions are allowed. Enforcement
The ______ ______ defines what is permitted, who is allowed to access what data and who can perform what operations. security policy
What two areas in an OS will attackers seek to target vulnerabilities? Enforcement mechanisms and security policies
#1.2.3 Portability Fact: The operating system needs to provide a consistent interface to applications, so they can run correctly regardless of the specific hardware of a computer.
Fact: The operating system itself should not require change much to accomodate different hardware.
Because operating systems are such large applications, and last for such a long time, it is necessary to write with future possible capabilities and applications in mind.
Fact: Abstract machine interface: interface provided by operating system to applications. Contains the API, which are the OS functions that applications can consume. The memory access model and legally executable instructions are also in the AMI. This includes code to control dual-mode execution.
The AMI provides a consistent interface that allows both software and hardware to change with very little negative impact of that change to the other side.
This abstraction of the computer is powerful, and operating systems use a similar concept internally with the Hardware Abstraction Layer. This isn't as fully-featured as the AMI, only providing a hardware-agnostic platform for the operating system itself.
1.2.4 Performance Performance can be measured in a few different ways. Two of those are Efficiency: Related to the abstraction offered to applications, how much slower or resource-intensive is a process compared to if that same process were executed on the hardware? Overhead is used to refer to the amount of efficiency loss.
The operating system is also responsible for allocating the system resources between different processes to allow everything to execute fairly and with a minimal disruption to the user experience. Response time (delay): The time it takes from an action (like moving the mouse) to the realization of that on the computer (the cursor moving). Throughput: The amount of work that can get done over a period of time (measured over several actions)
Decreasing response time doesn't necessarily help with throughput.
Predictability refers to the likelihood that a computer's actions will be consistent over time. An application loading quickly most of the time but occassionally taking a long time to load is unpredictable. An application that always loads a little slowly is predictable.
1.2.5 Adoption What two things, related to adoptability, can influence the success of an operating system? The presence of applications and compatible hardware.
An operating system may make it easy to work with existing hardware or make it easyier to make applications compatible with different versions of the operating system.
Network effect: an effect having to do with the number of people using a system.
Whether the API for an OS is open or proprietary can influence how likely it is to succeed.
Each of the sections introduced above are important in operating system development. Many times making an OS that satisfies one of them well means that it will be lacking in some other area. The practice of creating and maintaining an operating system is exactly making good decisions about these trade-offs.
#1.3 - A brief history of operating systems Since the start of computers there has been a large increase in many areas related to computer power/speed/etc, but operating systems still face the same challenges as they did at the beginning. Allocation of resources, fault isolation, communication services, and so on.
From the very first computers, OSs were a way to provide an easier time of programming and reducing programmer errors. From single-user systems to batch-systems to multi-user systems, then from business machines to user machines that were concerned with interactive use rather than batch jobs as their predecessors focused on, as the requirements of operating systems grew, so did the complexity of the operating systems themselves.
There are several examples of modern operating systems in everyday use
- Desktop, laptop, netbook
- Smartphone
- Virtual machine
- web server/web cluster
- embedded devices
(p35 - end of Ch 1)
#Chapter 2: The Kernel Abstraction (p41)
_______ is the isolation of potentially misbehaving applications and users so that they do not corrupt other applications or the OS itself. Protection
Protection has implications for a number of the areas mentioned in the first chapter: How does protections impact reliability of a system? If the system goes down, the operating system will be blamed even if the cause was a separate application. Protection lessens the impact of a bad application.
How does protection impact the security of a system? It helps to prevent a malicious application from accessing resources of other applications or trading out the files of the OS itself.
How does protection impact the privacy of a system? It prevents applications from reading arbitrary data on the system, which would allow any malicious application to access everything that a user may want protected.
How does protection impact the efficiency of a system? Protection prevents a single application from scooping up all the system resources.
What part of the OS is responsible for implementing protection? The kernel
What is the lowest level of software running on a system? The kernel
Fact: The kernel runs directly on the CPU with unlimited rights. How can restricted applications run on the CPU, but with dangerous operations disabled? Combination of hardware and OS.
Overarching theme: Small amounts of carefully designed hardware can help make it much easier for the OS to provide what user's want. Focus questions: What is a process and how does it differ from a program? How does the OS implement processes? What hardware is needed for efficient restricted execution? How do we switch safely across the boundary between processes and user-level and the kernel? What steps are needed to start running an OS kernel, up to the point where it can create a process?
A _____ is the abstraction for protection provided by the OS kernel: the execution of an application program with restricted rights. process
2.1 The process concept (p45) The process is a running instance of a program on the computer. When the program is executed, the computer allocates all the typical thing that a process needs, heap, stack, static data, instructions (code).
Separate processes for the same program still need separate heap, stack, and static data even though they can share the same instructions in memory (as a memory-saving measure).
Process control block: data structure used to hold information about a particular process, memory location, executable location on disk, user running as, privileges, etc.
A process may contain one or more threads, but what we now call a thread was, some time in the past, called a process. As the need for multiprocessor programs increased, these "lightweight" processes became more prevalent. Now a process executes a program and consists of one or more threads running inside a protection boundary.
Each thread in a program has its own program counter and stack but uses the same code and data as other threads.
2.2 Dual-mode operation The CPU has all the same capabilities regardless of the program running on it at a specific point in time, what is it that prevents an application from running and simply taking control of the computer when given the chance?
Naively we could run a checker so every time we run a program it will get run by the checker and if an instruction is allowed it will run the instruction. There are some operations that we can safely say wouldn't need to be run by the checker (addition of values in registers, for instance), and could run without being checked. This same concept is how dual-mode is implemented, except instead of the OS being the protector, it is the CPU. Applications run in user mode and the OS in kernel mode, this is mediated by a bit that can be set to allow these protections to be implemented or not, respectively.
The minimal requirements for this setup are:
- Privileged instructions - special instructions not allowed in user mode
- Memory protection - memory accessed outside a processes own memory region are prohibited when executing in user mode
- Timer interrupts - the kernel must have a way to periodically regain control from the current process.
The hardware must also have a safe way to transition from one of these states to the other.
2.2.1 Privileged instructions The principle of least privilege: security and reliability are enhanced if each part of the system has exactly the privileges it needs to do its job, and no more.
Many parts of the operating system run as user-level applications on top of the OS, this helps to prevent issues from crashing the entire system and improves the ability of developers to debug the software (as debugging a kernel-level application requires a lower-level debugger than what is available for user-level applications).
Applications should not be allowed to change their privilege level. Applications should not be allowed to change the set of memory locations it can access.
Privileged instructions are those available in kernel mode, but not in user-mode.
What happens when a process running in user-mode attempts to execute a privileged instruction? A processor exception is generated (not a language exception that can be handled by the application, but an exception that gets passed to an exception handler in the OS kernel).
Memory needs to be protected from being overwritten as well as being read (to provide security and privacy both).
One method of ensuring that a process doesn't access memory outside it's region is the setting of the base memory address and the total memory available to an application (base and bounds). These are registers in the processor that can only be set by privileged instructions. This is a very basic scheme.
Because user mode applications can only copy and move memory around in their own applications, anything having to do with input and output is done by the kernel copying the data to/from the relevant locations in memory. (on pg 53)
(26 pages in 100 minutes)
(p96) end of Ch 2
Chapter 3 - The Programming Interface (p101) (n pages)
(p131) end of Ch 3
Chapter 4 - Concurrency and Threads (p137) (39 pages)
What are threads? An abstraction that allow programmers to write sequential code that will run concurrently.
Questions to consider: What are threads and what do they do? What building blocks are needed so that we can construct threads? Given these building blocks, how can we implement threads?
What is the difference between multi-threaded and single-threaded programming? A ST program executes code sequentially, a MT program executes individual threads sequentially but multiple threads may be running concurrrently.
How can threads be used to enhance program structure? Threads can express tasks that should be executed at the same time, when it is easier to visualize in the context of threads. Like a program that updates the UI, fetches additional data, listens for user input, etc.
What two ways can threads be used to enhance performance? On multi-core machines, harder jobs can be run in parallel on multiple cores. Threads can also be useful in cases where high-latency IO is being used, so parts of the application aren't waiting on further input.
What are threads and what do they contain? Threads are a single execution sequence that represents a separately schedulable task.
What does it mean to say that threads are separately schedulable? The OS can run, suspend, or resume a thread at any time.
What does it mean to say that a thread is a single execution sequence? the sequence of instructions being executed by the thread is separate from other threads.
What illusion do threads help to support? That the system has an infinite number of processors.
How does the system allow the execution of more threads than processors? Using a scheduler, which can switch, run, suspend, and resume threads.
How does a thread view the running of its own code? Intermittent (as it is normally) or continuous? Continuous.
Can we make any assumptions about the speed that a thread is executing? Yes, but it is best not to, as the scheduler can make any decisions about when a thread should execute.
What is the model of threading called where a thread can be interrupted at any time? pre-emptive threading.
What is the name of the model of threading where the thread has to specifically relinquish control of the processor? Is it used often? Cooperative multithreading. It is not used often.
When coordinating between different threads is it better to use their expected execution times or explicit synchronization? Explicit synchronization. There are no guarantees about the speed with which a thread will executed, as it is impacted by a number of factors outside of its control.
#4.2 Simple API and example Thread functions: create(thread, func, arg) - create a thread, save it to thread, make it run func with given arg yield() - thread that calls this gives up processor to let other threads run, it can be called anytime after that join(thread) - waits for the specified thread to finish then return value passed to exit by the thread, may be called only once for each thread exit(ret) - finish the current thread and store ret in current threads data structure, also returns to join if specified.
#4.3 Thread internals Questions: What state is needed to represent a thread? What is the thread's lifecycle? How does the lifecycle help the OS to provide the virtual processor abstraction?
What data structure holds a thread's state? Thread Control Block
What two types of information are held in a thread control block? The state of the computation being performed by the thread and meta-data about the thread needed for its management.
How many TCBs are there for each thread? One!
Threads may have shared information, but there are some things that are thread-specific.
What information is specific to each thread? Stack, Processor registers (including special purpose registers like the SP and instruction pointer), and Errno (or something like it)
Why does each thread need its own stack? Because each thread is going to have its own values for local variables and it's own call stack.
Threads may have thread-specific heap locations, even though the heap is shared between threads, but this is per OS
What is one piece of information that can be found in the per-thread metadata The thread ID
What information is shared between threads? Code, statically-allocated global variables, dynamically-allocated heap variables.
What is the difference between dynamic and static allocation? Dynamic allocation is something allocated on the heap, (e.g. using malloc) where statically allocated are on the stack. [source]
How does the operating system support the distinction between Thread-Specific variables and shareable variables? It typically doesn't. One thread may access the data of another thread, like if a pointer was passed from one thread to another but it pointed to data that was on the stack for the originating thread.
How do you keep issues of oversharing (between threads) from occurring? By knowing which variables are designed to be shared across threads (global variables, objects on the heap) versus the ones designed to be private (local/automatic variables).
#4.3.2 Thread life cycle What are the five states in which a thread may find itself through its lifetime? Init, Ready, Running, Waiting, Finished
Where are the processor registers stored for threads that are not in the Running state? In the TCB
What are the two situations that can bring a thread from Running to Ready? The thread is pre-empted by the scheduler or the thread yields, voluntarily
To a thread, what does the transition between Running and Ready look like? It doesn't look like anything, to the thread, execution is seamless.
How is a thread transitioned from Ready to Running? The values for the processor registers are copied from the TCB in memory to the registers of the processor itself.
In what state is a thread put when it is created, and what happens after that? Threads are initially put in the Init state, then the per-thread data structure is allocated and initialized, then it is put in the Ready state.
What state is a thread in if it is ready to run but is not currently running? Ready
When a thread is in Running state, where is its processor register information stored? In the processor.
If there are k processors, or cores, then how many running threads are there at a given time? k
If there is nothing to run on a processor, then what is run? What does it do? The idle thread. In older computers it had a tight loop, but in modern computers it puts the processor into a low power state until a hardware interrupt occurs.
Where are the TCBs stored for the threads that are running, ready, and waiting kept? In running, ready, and on Synchronization Variable's Waiting lists.
Where are the TCBs stored for Finished tasks? In the finished list before being deleted (after the return value from the thread is read and no other uses for the information exist).
What is the difference between a thread in the waiting state and a thread in the ready state? A thread in the ready state is ok to be moved to Running, but a waiting thread is not ok to run until some other thread moves it from waiting to ready.
How is a thread in waiting kept track of, and how is it brought out of waiting? The TCB information for the thread is stored on the waiting list of a synchronization variable associated with the event that it is waiting on.
What is one way to understand the various stages that threads go through? By considering the locations of the TCB and the processor registers associated with the thread.
#4.4 Implementation Details
How threads are implemented, first in the OS itself (all kernel), then, how multithreading is made available to user applications. Questions: How are threads implemented?
Purpose: to make the previous thread information more concrete.
#4.4.1 Creating a Thread How is the stack size to allocate for a thread determined? It may either be a static number, in which case it would be an error for a thread to use more than the given number, or it is given an initial value which may then be resized dynamically.
#4.4.2 Deleting a Thread What two actions are required to delete a thread? Remove it from the Ready list so it will never run again, and free the per-thread state that was allocated to it.
Why does a thread move to the finished state as opposed to exiting itself and freeing its own resources? Because execution can be interrupted at any time, and if it were to get interrupted after it had already removed itself from the Ready List, then it would never execute again and we would get a memory leak, or if it were to get interrupted after freeing its own memory, the context-switch code would be writing to freed memory. By moving to the finished state, another thread can come in and safely remove the information without the above issues.
the sthread library makes it easy to do this since the delete method switched to finished properly.
#4.4.3 Thread context switch What is a thread context switch? A mechanism to switch which threads are running and which are ready.
What does a thread context switch do? Copies the currently running threads registers from the processor to the TCB and then copies the other thread's registers from the TCB to the processor.
The big picture of thread context switching is the same as in a mode switch. The hardware saves the state of some registers of the current process, starts running a handler, then the handler saves the state of the rest of the registers. At this point instead of resuming (like the mode switch would), the handler invokes the scheduler which copies the state information to the thread's TCB then chooses another thread to run.
There are some other differences that are addressed in the questions What triggers a context switch? How does context switch work?
One thing we don't discuss is the policy that the scheduler uses to choose the next running thread
This is an important principle that will be in various places in the book p159 What does it mean to separate mechanism from policy in Operating System design? Mechanism is generally how something is done (how to switch between threads), whereas policy governs how a decision is made (which thread to run next).
for now we assume the scheduler is using a FIFO queue
What are the two categories of action that can trigger a kernel thread context switch? The thread itself may call a function (like yield, join, exit) that triggers a context switch, or an interrupt or exception may invoke an interrupt handler (timer interrupt, other hardware events like keyboard, mouse events, or network events)
How do many thread libraries ensure that no thread monopolizes the processor? By switching threads when a timer interrupt occurs.
How does a kernel thread context switch work? Running thread's registers are copied to the TCB, and a ready thread's registers are copied to the processor.
What makes it easier to switch between kernel-level threads compared to user-level threads? No mode switch needed.
What difference is there when saving the state of a thread when the switch was triggered by a library function as opposed to the hardware interrupt? What does the library need to do to ensure compatibility? The library procedure has to save the state, as the hardware is not involved as it is in the hardware interrupt. The library procedure needs to save the state in the same way as the interrupt handler code would, so they can be restored without worrying about whether they were saved by the library or the hardware/handler.
How does a thread switching library function, like yield, ensure that the function isn't called in an endless loop? By pushing an instruction pointer that leads to the end of the called method prior to saving the registers to the stack, so when the control is returned to this thread it will execute from the end of the method instead of calling it once again.
note, ch 2 mode switch also kept track of the stack pointer before starting handler
What is one difference between a mode switch and a kernel thread being interrupted by a kernel handler, specifically relating to the stack pointer? The stack pointer is saved in a mode switch but not in a kernel thread switch because the kernel handler runs in the current stack.
#4.4.4 Multi-threaded processes Questions: How do single-threaded processes mesh with the mechanisms for implementing a multi-threaded OS? What additions are needed to support multi-threaded processes?
What is the minimum number of threads needed to implement a kernel? None! It is possible to have a purely event-driven kernel that only runs in response to interrupts, exceptions, or traps.
Where is the information for a process stored? PCB (Process Control Block)
What is the difference between a PCB and a TCB? The PCB contains additional informatio nabout the process's address space, to allow proper virtual memory mapping.
How many threads does a PCB represent? How are the thread(s) related to the TCBs in terms of which the scheduler can choose? One. The scheduler can choose a PCB just the same as it can a TCB.
At a high level, what is the difference between switching kernel threads and process (user-level) threads? The mode switch and the virtual memory mapping switch.
When does the hardware save the stack pointer, when switching from user to kernel mode or when staying in kernel mode? When switching from user to kernel mode.
Where does the difference between switching from user to kernel mode or staying in kernel mode, have to be taken into account, with regards to the hardware saving the stack pointer? The iret instruction to resume a suspended thread.
Why is it easier for a software-triggered thread switch to take place from a kernel thread vs a user-thread? The kernel thread just uses a procedure call, but the user-level thread needs a system call (since the PCBs are in the kernels memory) to save its state.
How can a process create multiple threads? Using system calls.
How is each process thread represented in the kernel? As a separate PCB.
Where is the stack for a process thread allocated? The process's memory.
What state do a process's threads share? Code, heap, and globals.
How is process multi-threading useful? Program structure, exploiting multiple processors, and coping with high latency I/O devices.
What happens to a process thread when a system call is blocking? The calling thread goes from Running to Waiting while the system call is incomplete.
How can threads be used to interleave I/O and processing? When reading and processing multiple files, one file could be read while the other is processed (since the read operation would block).
Is it possible to implement threads without kernel support (i.e. just at the user-level)? Yes, by implementing the same data structures used to hold the threads, TCBs, lists, etc.
In a user-level thread library, is it possible to implement interrupts and exceptions? Yes, by setting up signal handlers for the process when an event occurs.
What are the benefits to user-level thread libraries? Is this something to really consider today? To reduce dependence on OS-code, enhance portability. Not really.
How do user-level thread libraries match up when considering program structure, parallel processing, and high-latency I/O? They are good with program structure, since you can use threads as you would normally if they were kernel-level, but the kernel only sees a single thread, so for parallel processing there is no benefit, and for synchronous high-latency I/O there is no benefit because if one thread blocks on a system call waiting for I/O then the OS will not see the other threads available for scheduling, only the main process thread which will be blocked.
What is a benefit to a hybrid user-level and OS thread implementation for a thread package? Reduce overhead by avoiding mode switches.
User-level thread libraries can register as a scheduler in the same way signal handlers can be registered.
#4.5 Asynchronous I/O and event-driven programming How does Asynchronous/event-driven programming function? Calls are made asynchronously and when a result is received it may be made available via a callback or some other means.
What are the various ways an asynchronous call can return? Callback to code in the process, calling a signal handler, storing the result in kernel memory until the process makes another call to receive it, or by placing it into the process's memory.
Is there a benefit to using async over threads? At this point they are pretty similar, performance-wise, and it may be better to go with whatever works best for ease of understanding and maintenance of the code.
In web servers, what event-driven programming pattern allows many concurrent tasks to be in progress at once? A thread spins in a loop and on each iteration it gets and processes the next I/O event.
In the event-driven programming pattern with a looping thread, what is the data structure that keeps track of a task's current state and next step? continuation
When comparing based on I/O, multiprocessors, and logically concurrent tasks, how do threads and events compare to each other? Both are ok in I/O, threads win at multiprocessors but you can also use both, and in the last case there are places where each could be appropriate.
What is data parallel programming/SIMD (single instruction multiple data)? Define the computation once and the runtime system determines how to distribute it over the various resources available.
What is distributed and parallel processing? Programs designed to run across distributed systems.
(p177) end of Ch 4
Chapter 5 - Synchronizing Access to Shared Objects (p179) (57 pgs) When threads share information is when multithreaded programming becomes difficult. How to overcome these challenges?
How do we build on the simple tools given to create more useful abstractions for handling synchronization? Shared objects Locks Condition variables How do the implementations of the above differ for user and kernel-level applications?
In the context of multi-threaded programming, what are independent threads? Threads that operate on completely separate subsets of state.
What makes independent threads easier than cooperating threads? The operations of cooperating threads may interleave, creating states that we cannot reason about.
In the context of multi-threaded programming, what are cooperating threads? Threads that can read and write shared state.
What does it mean to think sequentially when reasoning about a program? Considering the state of a program as instructions are executed in order.
What are the three reasons that thinking sequentially does not work when considering cooperating threads?
- The state, which can influence order of execution, depends on the specific interleaving of thread access to shared state. We cannot reason about ALL the possible interleavings of threads.
- Program execution can be non-deterministic. Outputs changing for the same inputs based on things like scheduler decisions of processor times.
- Computers and architectures reorder instructions.
(p181) (p245) end of Ch 5