Synchronization Tools Flashcards
Why do processes and threads cooperate with each other? (3 things)
- information sharing
- computation speed up
- Modularity
Data can be shared with _____ ______ or _______ ________
shared memory, message passing
In shared memory, process A ____ shared memory, process B _____ this memory to their own _____ space and then is treated as ______ memory
creates, attaches, address, regular
In shared memory, ________ is needed to coordinate conflicting accesses
synchronization
POSIX APIs to shared memory synchronization include ______, _____ and ____
shm_open, shm_at, mmap
In message passing, process A sends message to B via _______
kernel
In message passing, processes can ____ for the message to be delivered
wait
The pros of shared memory is ______ and _______
speed, convenience
The cons of shared memory is having to ______ conflicts
manage
The pros of message passing is that there is no ______ and it is easy to _____ messages
conflict, exchange
The cons of message passing include high _______, ______ involvement, and the usage of several ______
overhead, kernel, syscalls
In the producer consumer problem, 2 _______ share a _______
threads, buffer
In the producer consumer problem, the producer places ______ into the buffer and must wait if it is ____
items, full
In the producer consumer problem, the consumer _____ items from the buffer and must wait if it is _____
takes, empty
In the producer consumer problem, we can coordinate producer and consumer by keeping a ______ on the # of items in the buffer
counter
In the producer consumer problem, how is count++ implemented?
register1 = count register1 = register1 + 1 count = register1
In the producer consumer problem, how is count– implemented?
register2 = count register2 = register2 -1 count = register2
In the producer consumer problem, consumers and producers run on the ____ core or _______ cores in parallel
same, different
In the producer consumer problem, the CPU scheduler can switch between producer and consumer at ___ time
any
In the producer consumer problem, when can the counter start at 6, call count++, call count–, and end up at 7?
When the CPU decides to swap the process to the consumer and finish the consumer process before the producer finishes
What is a race condition?
When multiple processes manipulate shared data concurrently and the result depends on the order of manipulation
A ______ _____ is code that manipulates shared data
critical section
To handle race conditions, make sure that when one _______ is executing the __, no other processes can
process, CS
What 3 requirements must be satisfied for a solution the CS problem?
- Mutual Exclusion
- Progress
- Bounded Waiting
Mutual Exclusion makes sure there is only ____ thread allows in the CS
one
Progress means that the thread should eventually _______
complete
Bounded Waiting means the process must wait for a _____ amount of time
finite
On _____________ systems, the CS problem can be solved by disabling _________ and ________
uniprocessor, interrupts, preemption
A problem on making a solution for the CS problem on a uniprocessor system is that users can make a ______ CS making the system _________
large, unresponsive
Solutions for the CS problem on multicore systems can use ______ only or be supported with _______
software, hardware
_______ solution is a software solution to the CS problem for only _____ processes
Peterson’s, two
Peterson’s solution assumes ____ and ______- are atomic
load, store
Peterson’s solution requires what 2 shared data items?
- integer named turn
- Boolean array named flag[2]
What does the turn value in peterson’s solution manage?
whose turn it is to enter CS
What does the flag value in peterson’s solution manage?
hether the process/thread is ready to enter CS
Describe Peterson’s solution in code
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = false;
remainder section
} while (true);Does Peterson’s algorithm satisfy the 3 requirements?
yes
Modern machines provide special _______ instructions that cannot be interrupted
atomic
What does atomic swap do?
update the memory word with new value and return the old value
What does Compare and swap do?
update one memory word if its original value matches a given value
Describe a simple spinlock using atomic_swap
while(atomic_swap(&lock, 1)) {
/* Do nothing */
}
critical section
lock = 0;
remainder sectionDescribe a simple spinlock using compare and swap
while(compare_and_swap(&lock, 0, 1)) {
/* Do nothing */
}
critical section
lock = 0;
remainder sectionBoth simple spinlocks using atomic_swap and compare_and_swamp can cause _______ _______
indefinite waiting
What are 2 software tools that are provided by libraries that can solve CS problems?
Mutex locks and semaphores
_____ locks have an atomic acquire and release
Mutex
Mutex/Spin locks can waste ____ _______, but prevents context switches
CPU cycles
_______ _____ are widely used on multiprocessor systems
mutex locks
A ________ is an integer variable accessed through two atomic operations: wait and signal
semaphore S
What do semaphores do?
They control access to a finite number of instances of some resource
In semaphores, wait ______ access to resources and signal _______ access
gains, releases
In semaphores, S is initialized to the _____ of resource instances available
number
In semaphores, S == 0 implies all _____ are being used
resources
A binary semaphore is similar to a _____
mutex
A _______ semaphore can be any integer value
counting
What are the 3 use cases of semaphores?
- Ensuring mutual exclusion
- Synchronizing steps in different processes
- Controlling access to finite resources
A busy-waiting semaphore keeps _________ in the wait call and may waste ____ __________, but improves _______ time
spinning, CPU, cycles, response
A non-busy-waiting semaphore ______ up the CPU when while waiting
frees
A non-busy-waiting semaphore has an additional _____ ______ in its struct
wait list
A non-busy-waiting semaphore has 2 internal operations: _____ and ________
block, wakeup
A non-busy-waiting semaphore’s block operation _______ the process that invokes it, placing it in the ________ queue
suspends, waiting
A non-busy-waiting semaphore’s wakeup operation _______ the execution of a ______ process, placing it in the _______ queue
resumes, blocked, ready
In semaphores, _____ and ______ operations must become ______ _________
wait, signal, CS
A non-busy-waiting semaphore does not completely remove busy waiting. why?
The busy waiting just got shifted from application-level CS entry to semaphore’s wait and signal commands, which are very short
Why would we want to move busy waiting to the semaphore level rather than the user’s CS?
User application may run for a long time, busy waiting can be costly
How can we use semaphores so that process 2 runs after process 1?
Semaphore synch (0); Process 1 - Statement S1 - signal (synch) Process 2 - wait(synch) - Statement S2
When can a dead lock occur using semaphores?
if P0 acquires S while P1 holds Q, P0 and P1 will wait for each other indefinitely
