Midterm Flashcards
What are the key roles of an operating system?
1) Hide Hardware complexity (eg Abstraction)
Ex: OS hides the various storage devices in the system (hard drives, USB drives, etc) and provides a higher level abstractions known as a file.
2) Manage underlying hardware resources (eg Arbitration)
Ex: OS decides how many and which resources an application is allowed to use: OS allocates a certain amount of memory to an application, schedule it to run on the CPU, and controls access to various I/O devices.
3) Provide Isolation and Protection
With multiple applications running concurrently, the OS must make sure that no one application interferes with the execution of another application.
Ex: OS makes sure that memory allocated to one app is accessed by another app
Can you make distinction between OS abstractions, mechanisms, policies?
Abstractions - Entities that represent other entities in a more simplified approach. Typically enables portability.
- Ex: Files are an abstraction of physical hardware. We interact with the File and have the OS handle the complexities of reading and manipulating the physical storage.
- Additional Examples: sockets (network communications, memory page (memory management)
Policies - Rules on how a system is maintained and resources are utilized.
-Ex: Using least recently used (LRU) policy to manage memory swapping to disk. Memory that was least recently accessed will be swapped to disk.
Mechanisms - Tools used to implement Policies.
-Ex: Using a queue data structure that tracks the least recently used memory blocks as a means of implementing the LRU policy
What does the principle of separation of mechanism and policy mean?
Goal of this design principle is to use several flexible mechanisms that can support a range of policies. In different settings, applying different policies make sense.
Ex: For memory management some useful policies we could want include ‘least recently used’, ‘least frequently used’, or completely random. To support this, the OS will want to have mechanisms to track the frequency and time when the memory location was last accessed. This allows the OS to support all three policies.
What does the principle optimize for the common case mean?
Goal of this principle is to make sure that the most common use case for execution performs the best. Once the common use case is identified, pick a specific policy that makes sense and that can be supported given the underlying mechanisms and abstractions of the OS in use.
What happens during a user-kernel mode crossing?
Initially, a bit in the CPU is either set (privileged) or not set (unprivileged) to control access to the hardware. The hardware causes a trap if an application from unprivileged user mode tries to perform some instruction or access at the privileged kernel mode. The OS then determines what caused the trap and if it should grant access or terminate the action.
User-kernel mode crossing is also called a context switch: It takes CPU cycles to perform because it requires a lot more instructions and will most likely cause a switch in data locality, moving data from fast cache to slower memory. If the desired data is in cache, it is considered to be hot. If the data is in memory, the cache is considered to be cold.
What are some of the reasons why user-kernel mode crossing happens?
Any time an application needs access to underlying hardware.
For example: read from a file, write from a file
Occurs in response to a kernel trap or via a system call.
What is a kernel trap? Why does it happen? What are the steps that take place during a kernel trap?
Occurs when an unprivileged app attempts to perform a privileged operation. The hardware sends a signal to the OS which takes control at a specific location. The OS then has a chance to check what cause the trap and verify if it should grant access or if it should terminate the process.
What is a system call? How does it happen? What are the steps that take place during a system call?
So that apps can leverage the OS’s privileged access to hardware and avoid traps, the OS exposes a system call interface for the app to use if they want the OS to perform certain operations on their behalf.
-Ex: open() call to perform access to a file, send() to perform access to a socket
During a system call:
- The app makes the system call
- OS does a context switch from the app process to the kernel, making sure it holds onto the arguments passed within that system call
- The trap bit in the CPU gets adjusted so that the operation isn’t in privileged kernel mode
- The kernel executes the system call
- Once completed, the trap bit in the CPU is adjusted back
- OS does a context switch back to the app process and passes back the results
Contrast the design decisions and performance tradeoffs among monolithic, modular and microkernel-based OS designs.
Monolithic OS: Includes all services required by the app and the hardware. Ex: File system for sequential I/O and a file system for random I/O.
Pros:
-Everything is included
-Compile-time optimizations: Abstraction and all the services are packaged at the same time.
Cons:
-Lacks customization, portability, and manageability: Too much state, too much code that is hard to maintain, debug, and upgrade
-Requires a large memory footprint which impacts performance
Moduler OS: Includes basic services, APIs, and everything can be added as a module via an interface. Most common OS design today (eg linux). Pros: -Easier to maintain and upgrade -Smaller code base -> only include modules that are needed for the use case -Less resource intensive/better performance -> more memory for the app Cons: -Relying on an interface creates indirection which can impact performance but it’s not typically very significant. -Maintenance can be an issue -> Modules come from different code bases and could be a source of bugs.
Microkernel-based OS: Small, requiring only the basic OS primitives and generally customized (eg embedded devices). All other typical OS components run outside of the microkernel. Relies heavily on interprocess interactions.
Pros:
-Very small -> lower overhead and better performance
-Easier to verify -> test that the code behaves exactly as it should
Cons:
-Portability -> typically very customized to underlying hardware
-Software complexity -> many one-off versions for different hardware makes it hard to find common software components
-Frequent inter-process interactions is costly -> need for frequent user/kernel crossings is expensive
Process vs. thread, describe the distinctions. What happens on a process vs. thread context switch
Process: Instance of an executing program. An app that has been loaded in memory and is executing.
-A single threaded process is represented by it’s address space.
The address space will contain all the physical to virtual memory mapping for it’s code, data, and files.
-The process is also represented by it’s execution context (eg register values, stack pointer, program pointer).
-The OS represents all this information in a Process Control Block (PCB)
Threads:
-Part of the same virtual address space (and share all the code, data, files).
-Will potentially execute different instructions, access different portions of the address space, operate on different portions of the input, all within the same process.
-Each thread will need a different execution context (eg program counter, stack pointer, stack, and thread specific registers).
-The OS representation of a multi-threaded process will be a more complex process control block (PCB) structure.
will contain all the info shared among the threads (eg virtual address mappings, code, data, etc)
separate info about each thread’s execution context.
Process vs Thread context switch:
-Because threads share an address space, you don’t incur the indirect cost of recreating physical to virtual address space mappings. As a result, it’s not as costly to context switch between threads vs context switching between Processes which will likely require pulling in data from memory and having a cold cache.
Describe the states in a lifetime of a process?
When a process is created, it enters the “new” state. In this state, the OS will determine if it’s ok to admit the process, and if it is, allocate/initialize a PCB and some initial resources.
Assuming there are minimum available resources, the process is admitted and is in the “ready” state since it’s ready to start executing. Still not executed by the CPU. Process is waiting until the scheduler moves it into a “running” state.
When the scheduler gives the CPU a “ready” process, it is now in a “running” state. Once in a “running” state, a few things can happen:
- The process is interrupted and moved back into a “ready” state due to a need to execute a context switch.
- The process is moved into a “waiting” state because it initiated a long operation and is waiting on an event to occur (eg input from a keyboard). Once this event occurs, the process moves into the “ready” state.
- When a “running” process finishes all the operations of a program, or when it encounters an error, it will exit. It will return an exit code (success or failure) and the process will terminate.
Describe the lifetime of a thread?
A parent thread can create a child thread using a “fork” call with two paramaters, a procedure argument that reflects the procedure the new thread will execute and then the arguments for the procedure. When the new childe thread is created, a new thread data structure is created, it’s program counter will point to the first instruction on the procedure and the arguments will be provided on the thread stack.
If the parent thread terminates before the child thread, the child thread will terminate early. To prevent this, the parent thread would make a “join” call with the thread ID of the child thread and will be blocked until the child thread completes. Once the child thread completes, any resources that were allocated for its execution will be freed, the result of the computation is returned to the parent thread, and the child thread terminates.
If a child thread isn’t joined back with the parent thread and the resources of that child thread haven’t been freed, it’s called a zombie thread.
To avoid problems associated with multiple threads accessing shared data, mutual exclusion is applied so that when a thread is accessing shared data, the other threads are “blocked” until the thread has completed it’s operation. For more complicated use cases, conditional variables are used as a mechanism to support thread blocking until a specific event occurs. Once the event occurs, threads are awaken to execute their operation.
Describe all the steps which take place for a process to transition form a waiting (blocked) state to a running (executing on the CPU) state.
Typically, a process is in a waiting (blocked) state because it’s executing a long operation such as executing an I/O operation. The process is in an I/O waiting queue until the hardware completes the I/O operation and then responds. The scheduled then moves the waiting process back into a running state or it might be actually scheduled on the CPU depending on the current load on the system.
What are the pros-and-cons of message-based vs. shared-memory-based IPC.
Message-based IPC: OS establishes a communication channel (eg read/write or message to a shared buffer).
- Pros: OS manages the communication channel -> same OS-level APIs/system calls (eg send/rec data)
- Cons: Overhead -> Transferring info requires going from process 1 to channel to process 2.
Shared memory-based IPC: OS creates a shared memory channel and then maps it to the address space of each process. Both processes can ready/write from this memory and the OS is out of the way.
- Pros: No overhead -> OS is out of the way
- Cons: Need to re-implement code -> User manages all synchronization. Error prone. Don’t use OS APIs/calls.
What are benefits of multithreading? When is it useful to add more threads, when does adding threads lead to pure overhead? What are the possible sources of overhead associated with multithreading?
Multi-Core Benefits: First area of benefit is with parallelization. Assuming that each core has it’s own thread running the exact same code but with different inputs from an input matrix, each thread would execute it’s work in the same amount of time resulting in a speed up. Speed up efficiencies can also be found if each thread executes different portions of a program. Another area of benefit is with specialization. By specializing a thread, it is executing the same type of work and using the same data in cache creating a hot cache. Such result would lead to performance gains.
Single CPU: For a single CPU, multithreading allows the CPU to switch to a new thread while one thread is idle. Context switching for threads aren’t as costly as processes because the address space is shared by the threads so the time to switch is shorter. Overall, this leads to a performance benefit.
Useful to add threads when there are fewer thread than core or if you your threads are executing operations that cause it to idle often. Otherwise, adding threads is an overhead, especially if they aren’t efficiently used.
Multithreading overhead can come from not freeing up resources once a thread completes (eg zombie threads) and when managing thread synchronization.
Describe the boss-worker multithreading pattern. If you need to improve a performance metric like throughput or response time, what could you do in a boss-worker model? What are the limiting factors in improving performance with this pattern?
The boss-worker multithreading pattern involves a boss thread provides work to a number of worker threads, typically via a queue or buffer. The top limiting factor is that the boss thread gets involved on step 1 for each task despite how many worker threads are available.
To improve performance, you want to ensure the boss thread is efficient:
- Instead of having the boss thread directly track and communicate with a specific thread, you would want to minimize this overhead by simply having the boss thread communicate the work to a queue that the workers would access.
- Instead of having the boss wait to add more to the queue when it’s full, make sure there is a pool of worker threads ready and available to process the work.
- Lastly, you could specialize the worker threads to gain data locality performance benefits. While this would require the boss thread to do a little more work to track the worker thread pools, it would be offset from the performance gains.
Describe the pipelined multithreading pattern. If you need to improve a performance metric like throughput or response time, what could you do in a pipelined model? What are the limiting factors in improving performance with this pattern?
The pipeline multithreading pattern is where a task is executed in a sequence of stages where each stage represents a subtask and each stage includes different threads. There can be multiple tasks concurrently in the system at different pipeline stages.
Throughput is dependent on the longest stages. To address longer stages, you would ensure you had a pool of threads prepared in advance (similar to the thread pool technique used with the boss-worker pattern) and that you would have more threads made available to the longer stages vs the shorter stages. The challenge with this approach is that any changes to the input rate or available resources could dictate a need to rebalance.
What’s a simple way to prevent deadlocks? Why?
Two threads can deadlock if they are trying to acquire each other’s mutexes. To prevent this from happening, the simple solutions is to maintain lock order. For example. each thread will first focus on acquiring mutex A and once completed, then would move on to mutex B, etc. This prevents the situation where the threads own different mutexes and then try to acquire each other’s mutex.
What are mutexes?
A mutex is a synchronization construct that enforces the principle of mutual exclusion. It acts like a lock when used to access a shared resource for multiple threads. When a thread locks a Mutex, it has exclusive access to the shared resource. When another thread attempts to access a locked resource, it is considered to be “blocked” and will be suspended unless the Mutex owner releases the lock.
What are condition variables?
A condition variable allows a thread to block until some defined event happens. Is always associated with a particular mutex, and with the data protected by that mutex. When the event happens, the blocked threads are signaled and awoken so that they can acquire the mutex and access the shared resource.
What are spurious wake-ups, how do you avoid them, and can you always avoid them?
Spuriuos wake ups are when we wake up threads from an existing queue and then move them to another queue. An example is when a conditional variable sends a broadcast() call to wake up threads, only to move them to a mutex queue because the mutex hasn’t been unlocked yet. Sometimes, spurious wake ups can be avoided by waking up threads (eg broadcast()) after releasing the mutex. However, if the mutex can’t be released before waking up the threads (eg still need access to the shared resource), then the spurious wake up can’t be avoided.
Do you understand the need for using a while() look for the predicate check in the critical section entry code examples in the lessons?
The while loop helps address the situation where there are multiple threads who are attempting to access the shared resources and acquire the mutex. It helps to confirm that the condition is still true when a thread acquires the mutex.
Can you quickly write the steps/code for entering/exiting a critical section for problems such as reader/writer (reader priority)?
//reader code lock(&m); waitingReads++; while(status == -1) wait(&cond_reader, &m); status++; waitingReads--; unlock(&m);
//reader does work
lock(&m); status--; if(status == 0) signal(&cond_writer, &m); unlock(&m);
//writer code lock(&m); while(status != 0) wait(&cond_reader, &m); status = -1; unlock(&m);
//writer does work
lock(&m); status = 0; if(waitingReads > 0) broadcast(&cond_reader) else signal(&cond_writer) unlock(&m);
What’s a simple way to prevent deadlocks? Why?
Two threads can deadlock if they are trying to acquire each other’s mutexes. To prevent this from happening, the simple solutions is to maintain lock order. For example. each thread will first focus on acquiring mutex A and once completed, then would move on to mutex B, etc. This prevents the situation where the threads own different mutexes and then try to acquire each other’s mutex.
