Week 8 Flashcards
What is concurrency?
The ability of our machine to handle and execute multiple different tasks at seemingly same time.
At the process level, programmers can manage concurrency using __________
threading
Unless explicitly synchronized, processes/threads may:
Be run in _________
Be stopped and restarted at ________
Remain stopped for _____________
any order
any time
arbitrary lengths of time
Why is the operating system one of the most difficult concurrent programs to write?
It is multiplexing access to hardware resources and therefore sharing a great deal of state between multiple processes.
It frequently uses many threads to hide hardware delays while servicing devices and application requests.
Lots of shared states plus alot of threads.
What is a race condition?
A race condition is when the output of a process is unexpectedly dependent on timing or other events.
Processes contain ________ , multiple ____ can be executing concurrently within a single process.
threads
A process thread can be thought of as …
an abstraction of the CPU state
Both processes and threads are used for concurrency. What do they do?
Processes allow for concurrency to be managed at the OS level
Threads allow for concurrency to be managed at the process level.
Why use threaeds instead of separate processes?
When the program needs cheap communication.
Lowers the cost of a context switch
Gives the programmer additional control over concurrent execution.
Communication between threads tends to use ________ objects in memory
Communication between threads tends to use shared objects in memory.
Thread stacks and local variables are intended to be _________
Thread stacks and local variables
are intended to be private
What is the difference between concurrency and atomicity?
Concurrency: the illusion that multiple things are happening at once. (requires stopping or starting any thread at any time.
Atomicity: the illusion that a set of separate actions occurred all at once.
What is a critical section?
> A critical section contains a series of instructions that only one thread should be executing at any given time.
> This series of instructions should look atomic with respect to other
threads.
What are these critical section requirements?
Mutual Exclusion
Progress/Fairness
Performance
> Mutual Exclusion: this is the most basic property. Only one thread
should be executing in the critical section at one time.
> Progress/Fairness: all threads should eventually be able to proceed through the critical section.
> Performance: we want to keep critical sections as small as
possible without sacrificing correctness.
How do we enforce critical sections?
There are 2 possible approaches.
> Don’t stop: On uniprocessors a single thread can prevent other threads from executing in a critical section by simply not being descheduled.
> Don’t enter: More generally we need a way to force other threads—potentially running on other cores—not to enter the
critical section while one thread is inside. How do we do this? Locks!
What is a lock?
A lock is just another variable in your program.
A lock is either free/unlocked/available or held/acquired/locked by exactly one thread.
If a thread holds a lock then they are (presumably) in the critical section
What are the 3 things that we care about when evaluating locks?
- Correctness (i.e., Mutual Exclusion): this is the most basic property. Only one thread should be executing in the critical
section at one time. - Progress (i.e., fairness): all threads should eventually be able to proceed through the critical section.
- Performance: what is the overhead of the lock? How is it affected by multiple processors?
What is test and set?
Test-and-set: write a memory location and return its old value.
What is a spinlock?
Lock for the fact that it guards the critical section.
spin describing the process of acquiring it.
Spinlocks are rarely used on their own to solve synchronization problems, but are commonly used to build more useful
synchronization primitives.
Are spin lock…
correct?
fair?
performant?
Are spin locks correct? Yes, they provide mutual exclusion.
Are spin locks fair? No, they don’t employ any mechanism to ensure other threads get to execute.
Are spin locks performant? Sometimes…
SPIN LOCKS
When should we go to sleep?
When should we spin?
Sleep if the critical section is long.
Spin if the critical section is short.
What is a busy waiting.
Busy waiting: threads wait for the critical section by pounding on the door, executing the test-and-set repeatedly.
Bad on a multicore system. Worse on a single core system! Busy waiting prevents the thread in the critical section from making progress!
What is compare and swap.
It will test whether the stored value is equal to some test value. If so, update the the
stored value to some new value.
Compare-and-swap is more powerful than test-and-set, but in the simple case of spin locks the code and behavior is essentially the same.
These are often used for lock-free synchronization.
What is load-linked and store-conditional.
First, load a value from memory
using the load-link instruction.
> Second, store a value into that address using store-conditional, but only if the value at that address hasn’t been modified in the meantime.
- Again, we can use these instructions to implement a spin lock
