Part 2 Flashcards
Process vs. thread, describe the distinctions. What happens on a process vs. thread context switch?
In the toy shop example: a Process is like an order of toys and a thread is like a worker in a toy shop.
A process is an active entity that represents the state of a program while executing. A thread is an entity that performs a task directed by a process that can happen simultaneously with other simular threads.
During process context switch, the cpu switches processes which forces virtual memory address space to be remapped to the processes physical address space, which is costly. Since threads share an address space, this remapping is unnecessary. As such, thread context switching is faster overall.
if (t_idle) > 2 * (t_ctx_switch) -> context switch to hide idle time
Describe the states in a lifetime of a process?
1) New
2) Ready
3) Running
4) Terminated
5) Waiting
Describe the lifetime of a thread?
The thread is first created by the fork() method, and then executes, exec(), some function. A thread then closes/returns to the parent thread by using the function join()
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
The process is in a waiting state when some I/O or wait event is triggered. Once the I/O or wait event is completed, the process goes to a ready state. Upon some schedular dispatch event, the process then transitions to a running state.
What are the pros-and-cons of message-based vs. shared-memory-based IPC?
Message-Passing:
+ Managed by the operating system
- A lot of overhead involved
Shared Memory IPC:
+ Operating System is out of the way (not involved)
- Since OS is out of the way, we must re-implement code (More error prone)
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?
- Parallelization -> Speed Up Tasks
- Specialization -> Makes use of Hot Cache!
- Efficiency -> Lower memory requirements & cheaper IPC
It becomes useful to add more threads when there is a bottleneck in the system.
(?) Adding threads where they need to access a shared variable or resource creates more overhead within the implementation
Keeping track of Mutex and Condition Variables, using a single mutex for multiple resources, using signal when instead you should broadcast.
Describe the boss-worked 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?
In the boss-worker patern, a boss thread assigns jobs/tasks to other worker threads. The throughput is calculated by: 1 / boss_time_per_order.
To increase performance, one could create more worker threads on demand, but this can be inefficient. Another way is by having a pool of workers with a dynamic size. A variant of this creates specialized workers for certain tasks.
With this pattern based on the variant implemented, there is a lot of overhead keeping track of all the worker threads, keeping the thread queue synchronized, and determing the right amount of workers to maintain efficiency.
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?
In a pipelines pattern, the threads are assigned a subtask of one entire task.
To improve the pipeline pattern is by creating a thread pool in the stage that is the weakest link/slowest stage.
The limiting factors for development and performance optimization is that there are a lot of balancing and synchronization overhead.
What are mutexes and condition variables?
A Mutex is a way to allow only one thread access (to have exclusive acess) to a set of data, or variable, at a time.
Condition variables can be used to keep other threads waiting until that specific condition has been met and signaled/broadcast by another thread.
These two variables are usually used within the critical section of a thread’s task.
Can you quickly write the steps/code for entering/existing a critical section for problems such as reader/writer, reader/writer with selective priority (e.g., reader priority vs. writer priority)?
Swapping the read_phase w/ write_page and vice versa changes this to a writer priority function.
// ----- READER ------
Lock(counter_mutex) {
while(resource_counter == -1)
wait(counter_mutex, read_phase);
resource_counter++;
} // Unlock
// . . . do stuff . . .
Lock(counter_mutex) {
resource_counter--;
if (resource_counter == 0)
signal(write_phase);
} // Unlock
// ----- WRITER -----
Lock(counter_mutex) {
while(resource_counter != 0)
wait(counter_mutex, write_phase);
resource_counter = -1;
} // Unlock
// . . . do stuff . . .
Lock(counter_mutex) {
resource_counter = 0;
broadcast(read_phase);
signal(write_phase);
} // Unlock
What are spurious wake-ups, how do you avoid them, and can you always avoid them?
Spurious wake-ups are unnecessarily waking up a thread knowing that the thread cannot access the data it needs too, or that it cannot proceed with normal execution.
You can avoid them by reordering the operations of which you wake up a thread. By locking the mutex and signaling/broadcasting outside of the lock. However, this isn’t always the case and sometimes cannot be done without affecting the correctness of the code.
Why is using a while() loop for the predicate check in the critical section entry code so important?
We cannot guarantee access to a mutex once the condition is signaled - so we use a while() loop to assure we don’t change the data while its being accessed elsewhere. In addition, using a while loop can support multiple threads.
What’s a simple way to prevent deadlocks? Why?
A simple way of preventing deadlocks is to maintain a lock order, or lock chain. This prevents the deadlock cycle and will guarantee that the threads will always have access to a mutex at one point in the chain.
– Extra —
Deadlock prevention can be expensive to implement, sometimes a better method to avoid deadlocks is to detect when a deadlock occurs and to recover/rollback when necessary. Another met hod is the Ostrich Algorithm, doing nothing and if a deadlock occurs - just reboot.
Can you explain the relationship among kernel vs. user-level threads?
Think though a general mxn scenario (as described in the Solaris papers), and in the current Linux model. What happens during scheduling, synchronization and signaling in these cases?
In order for a user-level thread to execute, it must first be associated with a kernel-level thread. The OS scheduer, then schedules that kernel-level thread to a CPU.
There are three models as to how a user-level thread interacts with a kernel-level thread, and those models are: one-to-one, many-to-one, and many-to-many.
A user-level thread can be assigned to any amount of kernel-level threads. The complications arise when the kernel-level threads must synchroniize between each other - which can be done through adaptive mutexes - chosing when to spin or block other threads as to not waste cycles. Signals are called by either the CPU or Process running to keep each other in the loop as to what needs to occur.
Can you explain why some of the mechanisms described in the Solaris papers (for configuring the degree concurrency, for signaling, the use of LWP…) are not used or necessary in the current threads model in Linux?
Because the solaris model was many to many, special signals and system calls allowed the kernel and user level library to interact and coordinate with one another, fixing the visibility issues present.
However, the visibility of state and decisions between kernel and UL library are solved in a 1-1 model and as such special signals and system calls are not needed in current linux threading models.
