Lesson 4b

Question 1

What is a mutex

Answer 1

Mutual exclusion lock. Only one thread can access

Question 2

What is a semaphore

Answer 2

A shared lock multiple threads can access data “Multiple readers”

Question 3

Barrier Synchronization?

Answer 3

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”

Question 4

Atomic Instructions

Answer 4

Load-and-store, read-and-inc, etc…

Question 5

What is all that is needed from the instruction set for barrier sync?

Answer 5

atomic read and write

Question 6

what is rmw instruction?

Answer 6

Read-Modify-Write. Needed to set a value that is also being checked. If(i == 0) i = 1; this needs to happen atomically.

Question 7

Different types of RMW

Answer 7

Test-and-set, Fetch-and-inc, fetch-and-0

Question 8

Scalability issue with barrier sync

Answer 8

latency, waiting time, contention

Question 9

What is spin lock on test and set?

Answer 9

if locked){while(locked){…} locked = 1; /* testAndSet in the while condition */

Question 10

what is spin on read?

Answer 10

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

Question 11

How do we avoid contention when a lock is released

Answer 11

spin lock with delay

Question 12

Can all processors have the same delay value?

Answer 12

No, this will cause the same contention that working from a regular spin lock would cause

Question 13

What happens with delay that has exponential backoff

Answer 13

On each lock in the while loop the length of the delay is doubled. While(TestAndSet(L) == locked){ delay(d); d = d * 2; }

Question 14

What is an important problem with spin lock?

Answer 14

Fairness, spin lock doesn’t guarantee that the original requester will get the lock first

Question 15

what is the ticket lock similar to in daily life?

Answer 15

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.

Question 16

What is the structure of the ticket lock?

Answer 16

struct lock { int next_ticket; int now_serving; };

Question 17

What is the ticket algo

Answer 17

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? */

Question 18

What causes network contention for ticket locks?

Answer 18

updating the “now_serving” global var. That causes caches to need updating

Question 19

Key points of array based queuing lock?

Answer 19

Each processor gets the next available slot in the array. But the slots are not statically assigned to a Process.

Question 20

What is the size of the queue array in a queuing lock?

Answer 20

It is the size of the number of processors

Question 21

What are the two states in the queuing array?

Answer 21

has-lock and must-wait

Question 22

What is the name of the variable that keeps track of the queue location?

Answer 22

queueLast

Question 23

What problem does the queue lock solve

Answer 23

It is fair and it is not noisy. CPU cache will not need to be invalidated

Question 24

what are the downsides of queue lock?

Answer 24

Space, if you have 1000 CPUs then you are eating into memory space

Question 25

How would you solve the size problem of the queue lock?

Answer 25

use dynamic allocation (linked-list)

Question 26

What ins(opcode) is required for the linked based queueing lock

Answer 26

fetch-and-store. It is required for fixing the list atomically

Question 27

How can a race condition be avoided when unlocking a queue linked-list

Answer 27

compare-and-swap (L, me, nil) compare 1st and 2nd set 1st and 3rd.

Question 28

How would comp-and-swap be implemented

Answer 28

gcc has some builtin for these

Question 29

How do you add a new waiter to the linked queue

Answer 29

Set last requester next to the new waiter. Set current running next to new waiter, This breaks the connection from last to current

Question 30

What is the lock algo for the linked queue

Answer 30

• Join L atomically (fetch-and-store), - await predecessor to signal spin