Section 1
Preview this deck
In general, spinlocks pass the _______ criterion for locking, but fail miserably in the areas of _______ and performance.
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
0
All-time users
0
Favorites
0
Last updated
6 years ago
Date created
Mar 1, 2020
Cards (67)
Section 1
(50 cards)
In general, spinlocks pass the _______ criterion for locking, but fail miserably in the areas of _______ and performance.
correctness, fairness
Dijkstra's name for the POSIX sem_wait() call was ______ (), and for sem_post() it was ______ (). Hint: these are very short names!
p, v
When compiling a multi-threaded program (using GCC or Clang), you have to add the -_______ command-line switch to ensure the correct library is linked, and other configuration changes are made.
pthread
A data structure is considered ______ - ______ when it performs correctly even when accessed (via its APIs) by multiple threads concurrently.
thread safe
A(n) ______ concurrent ______ scales up much better than a precise one, at the expense of some precision.
sloppy, counter
Having one big lock that is used any time any critical section is accessed is a _______-_______ locking strategy, which can lead to inefficiency.
coarse grained
Assuming a shared resource has been initialized in another thread (without ascertaining that) is an example of a(n) ______ violation. You should use a condition variable or ______ to ensure the correct sequencing of the two operations.
order, semaphore
_______ _______ keeps two (or more threads) from accessing shared data at the same time, avoiding race conditions.
mutual exclusion
The threading API analogous to fork() is called _______ _ _______().
pthread, create
A complete solution to the bounded buffer problem uses both ______ semaphores (as mutexes) and counting semaphores that signal other ______ when a buffer slot is filled or available.
binary, threads
Unlike a fork call, the function that creates a new thread takes a(n) _______ _______ as an argument. It uses the value passed for that parameter as the starting point of the code the thread is executing.
function pointer
To facilitate the writing of correctly-functioning concurrent programs, the _______ provides a few useful instructions we can use to build _______ primitives, which threads can then use to coordinate access to shared resources.
hardware, synchronization
Constantly polling a flag until its value changes is called _______-_______. It's effective but not efficient.
spin waiting
Once we have multiple _______ within a process, the order in which things happen is no longer entirely _______.
threads, deterministic
In multi-threaded programs, we often want some chunk of code to execute _______, without being preempted before completing.
atomically
Encapsulating synchronization within a data structure's methods or functions allows application programmers to assume the data structure is thread-______, and use it from multiple threads without having to worry about handling ______ conditions.
safe, race
Above all else, a locking mechanism must guarantee _______ _______. Otherwise, it might allow multiple threads to enter a critical section simultaneously.
mutual exclusion
A(n) ______ semaphore can be used to enforce mutual exclusion, replacing a lock. You just have to set its initial value to ______.
binary, 1
Using a separate lock for each separate shared resource is a _______-_______ locking strategy that can increase concurrency.
fine grained
The most basic way of accomplishing mutual exclusion when using the pthread library is to create a(n) lock, which is a variable of type _______ _ _______ _t
pthread, mutex
Instead of spin waiting, the function that acquires a lock can use the _______() system call to force a context switch if the flag it's waiting for has not yet changed.
yield
It is important to consider scaling to more than 1 or 2 threads when making a data structure ______ - safe. Otherwise, using it might undo all benefits of ______.
thread, concurrency
When no thread is in its corresponding _______ section, the lock is said to be _______.
critical, available
When a _______ is in the critical section guarded by a particular lock, that lock should be _______ by that thread.
thread, acquired
One way to break the ______-and-______ condition necessary for deadlock is to require threads to acquire all of the locks they're going to hold simultaneously in one fell swoop. This, sadly, is not practical in many settings.
hold, wait
In the context of locking, _______ means giving each thread contending for the lock a chance at acquiring it once it's free. On the other hand, if a thread never gets a chance to run, it's said to be suffering from _______.
fairness, starvation
One way to scale a concurrent counter up to many threads is to store a separate counter for each ______, which occasionally gets transferred to a single ______ counter.
thread, global
All threads in a process share both code and the _______ section of memory, but each thread has its own _______ (often called thread-local storage).
heap, stack
Every _______ section in a multi-threaded program needs to be "protected" by a(n) _______, which provides mutual exclusion.
critical, lock
Each thread in a process keeps separate _______ information, including the _______ register (which keeps track of where the program is fetching instructions from).
state, PC
The simplest type of POSIX lock is called a(n) _______ because it is used to provide _______ exclusion between threads.
mutex, mutual
A monitor is a programming language feature that automatically ______ a lock whenever a method for a particular object is called, and ______ it when the method exits.
acquires, releases
Without some intentional control, multi-threaded access to shared data will lead to a(n) _______ _______ where the results depend on the timing of the code's execution.
race condition
All of a thread's state information is saved in a(n) ______________, similar to the ______________ stored for each process.
thread control block, process control block
______ lists and ______ are data structures that are commonly accessed concurrently, so it makes sense for an OS or language library to provide them.
linked, queues
You can guarantee that a block of instructions will execute _______ by disabling _______ before starting its execution. This approach is very heavy-handed, however, and can cause other problems.
atomically, interrupts
When moving a thread from the _______ state to the blocked state due to an unavailable lock, the OS has to add the thread to a(n) _______ so it gets a fair chance to run when the lock becomes available.
running, queue
To use locks in a multi-threaded program, you first declare a(n) lock _______. For the simplest type of POSIX lock, it would be of type pthread_ _______ _t.
variable, mutex
The test-and-set instruction is often known as the ________ ________ instruction, since it swaps the contents of a register with the contents of a memory location in a single instruction.
atomic exchange
We can use Dijkstra's ______ to make one thread wait for another to signal the completion of some task. Thus, they can take the place of ______ variables
semaphores, condition
Code that accesses shared data in a multi-threaded program is known as a(n) _______ _______.
critical section
A correct solution to the ______ ______ problem relies on a thread-safe queue that holds the items produced and consumed by multiple threads concurrently.
bounded buffer
As an alternative to spin waiting, the function that acquires a lock can move the calling thread from the _______ state to the _______ state, where it doesn't take up any CPU time until the lock becomes available.
running, blocked
A semaphore is an object with a(n) ______ value that we can manipulate using a routine to ______ its value and another to attempt to decrement its value.
integer, increment
To avoid spin waiting, a thread can voluntarily move itself from the _______ state to the _______ state by calling yield().
running, ready
The threading API analogous to wait() is called _______ _ _______().
pthread, join
When compiling a multi-threaded program (using GCC or Clang), you have to add the -_______ command line switch to ensure the correct library is linked, and other configuration changes are made.
pthread
The basic abstraction introduced for concurrency is that of a(n) _______, which breaks the classic view of a single point of execution within a program.
thread
Because C lacks native support for generics, the thread creation function both accepts and returns a(n) _______ _______. This allows it to receive and pass back any type of value, at the expense of a cast in both directions.
void pointer
Using a pointer after checking that it's not null but without locking it is an example of a(n) ______ violation. You should precede the check with code that ______ a lock and doesn't release it till after you're done using the pointer.
atomicity, acquires
Section 2
(17 cards)