Lesson 4b Flashcards
Parallel Systems
What is a mutex
Mutual exclusion lock. Only one thread can access
What is a semaphore
A shared lock multiple threads can access data “Multiple readers”
Barrier Synchronization?
You have a location that other threads will wait for until all of them reach the location “Host wait until everyone is at the restaurant”
Atomic Instructions
Load-and-store, read-and-inc, etc…
What is all that is needed from the instruction set for barrier sync?
atomic read and write
what is rmw instruction?
Read-Modify-Write. Needed to set a value that is also being checked. If(i == 0) i = 1; this needs to happen atomically.
Different types of RMW
Test-and-set, Fetch-and-inc, fetch-and-0
Scalability issue with barrier sync
latency, waiting time, contention
What is spin lock on test and set?
if locked){while(locked){…} locked = 1; /* testAndSet in the while condition */
what is spin on read?
waiters spin on cached copy of L. Doesn’t create contention on network. /Checking local cache/ while(L == locked){ if (test-and-set(L) == locked) go back
How do we avoid contention when a lock is released
spin lock with delay
Can all processors have the same delay value?
No, this will cause the same contention that working from a regular spin lock would cause
What happens with delay that has exponential backoff
On each lock in the while loop the length of the delay is doubled. While(TestAndSet(L) == locked){ delay(d); d = d * 2; }
What is an important problem with spin lock?
Fairness, spin lock doesn’t guarantee that the original requester will get the lock first
what is the ticket lock similar to in daily life?
A ticket system at the deli. If you get ticket 16 you have to wait from stay ticket 5 until 16. Anyone that comes after you will need to wait to order.
What is the structure of the ticket lock?
struct lock { int next_ticket; int now_serving; };
What is the ticket algo
int myticket = fetchAndInc(l->next_ticket) loop {pause(my_ticket - l->now_serving); if (now_serving == my_ticket) return;
release_lock(L)
l->now_serving++; /* why is this happening after the lock? */
What causes network contention for ticket locks?
updating the “now_serving” global var. That causes caches to need updating
Key points of array based queuing lock?
Each processor gets the next available slot in the array. But the slots are not statically assigned to a Process.
What is the size of the queue array in a queuing lock?
It is the size of the number of processors
What are the two states in the queuing array?
has-lock and must-wait
What is the name of the variable that keeps track of the queue location?
queueLast
What problem does the queue lock solve
It is fair and it is not noisy. CPU cache will not need to be invalidated
what are the downsides of queue lock?
Space, if you have 1000 CPUs then you are eating into memory space
