Queue locks,( Array based locks, CLH, MCS Queue locks, composite locks)

Question 1

Why are queue locks good?

Answer 1

Cache-coherence traffic is reduced since each thread spins on a different location.
increase CS utilization
fair

Question 2

variables in Alock class

Answer 2

class ALock implements Lock {
boolean[] flags={true,false,…,false};
AtomicInteger tail
= new AtomicInteger(0);
ThreadLocal<Integer> mySlot;</Integer>

Question 3

Lock code for Alock

Answer 3

public lock() {
mySlot = tail.getAndIncrement();
while (!flags[mySlot]) {};
}

Question 4

unlock for Alock

Answer 4

public unlock() {
flags[mySlot] = false;
flags[(mySlot+1)] = true;
}

Question 5

What is good/bad about Alock

Answer 5

scalable,simple

not space efficient
1bit per thread

Question 6

What keeps track of the queue in CLH?

Answer 6

Linked List

Question 7

What are the 2 states of the CLH and what do they mean

Answer 7

true: has/want to acquire lock
false: finished + has released it

Question 8

What does each node have in a CLH

Answer 8

a track of its predecessors status

Question 9

Variables in CLH

Answer 9

class CLHLock implements Lock {
AtomicReference<Qnode> tail;
ThreadLocal<Qnode> myNode
= new Qnode();
}}</Qnode></Qnode>

Question 10

lock CLH

Answer 10

public void lock() {
myNode.locked = true;
Qnode pred
= tail.getAndSet(myNode);
while (pred.locked) {}
}

Question 11

unlock CLH

Answer 11

public void unlock() {
myNode.locked.set(false);
myNode = pred;
}

Question 12

Whats good about CLH

Answer 12

Lock release affects predecessor only
small, constant-sized space

Question 13

MCS Lock idea

Answer 13

FIFO
Spin on local memory only
small, constant-size overhead

Question 14

Difference between CLH and MCS

Answer 14

in CLH = implicit MCS = explicit
each node in the queue has a next field

Question 15

how does the Node look for MCS

Answer 15

class Qnode {
boolean locked = false;
qnode next = null;
}

Question 16

What variables does MCS lock have?

Answer 16

only tail (atomic reference)

Question 17

lock MCS

Answer 17

public void lock() {
Qnode qnode = new Qnode();
Qnode pred = tail.getAndSet(qnode);
if (pred != null) {
qnode.locked = true;
pred.next = qnode;
while (qnode.locked) {}
}}

Question 18

unlock MCS

Answer 18

public void unlock() {
if (qnode.next == null) {
if (tail.CAS(qnode, null)
return;
while (qnode.next == null) {}
}
qnode.next.locked = false;
}

Question 19

What 2 types of locks do composite locks use?

Answer 19

Backoff + Queue

Question 20

Idea of Composite locks

Answer 20

Keep small number of waiting threads in a queue and have the rest use exponential backoff

Question 21

how will the Composite lock work?

Answer 21

keep fixed sized array of lock nodes
Each thread that tries to acquire the lock selects array node at random.
if in use back off and try again
If node is acquired enqueue in TOLock style queue
wait till its your turn to enter CS

Question 22

node states in Composite lock and what do they mean

Answer 22

FREE = available
WAITING = linked into the queue and either in/waiting CS
RELEASED = owner leaves the CS
ABORTED = quit

Question 23

how does a thread try to acquire a lock in a CLock?

Answer 23

Acquire node in waiting array
enqueue node in queue
waits until node reaches head of the queue

Question 24

What does tail point to in CLock?

Answer 24

either null or last value entered into queue

Question 25

what are the 2 variables in the CLock?

Answer 25

tail (AtomicReference<Qnode>)
Qnode[] waiting</Qnode>

Question 26

how does the states look in CLock

Answer 26

enum State {FREE, WAITING, RELEASED,
ABORTED}

Question 27

How does the node class look(for the composite lock)?

Answer 27

class Qnode {
AtomicReference<State> state;
Qnode pred;
public Qnode() {
state = new
AtomicReference<State>
(State.FREE);
}</State></State>

Question 28

How does the tryLock look in CLock?

Answer 28

public boolean tryLock() {
Qnode node = acquireNode();
Qnode pred = spliceNode(node);
waitForPredecessor(pred, node);
}

Question 29

To aquire a node at random how does the function look in CLock

Answer 29

private Qnode acquireNode() {
Qnode node = waiting[random.nextInt()];
while (true) {
if (state.compareAndSet(FREE, WAITING))
return node;
currTail = tail;
if (state == ABORTED || state ==
RELEASED) {
if (node == currTail) {
Qnode myPred = null;
if (state == ABORTED)
myPred = node.pred;
if (tail.compareAndSet(
currTail, myPred)
node.state.set(WAITING);
return node;
}
}

Question 30

how is the node spliced into the queue in CLock?

Answer 30

private Qnode spliceNode(Qnode node) {
Qnode currTail;
do {
currTail = tail;
if (timeout()) {
node.state.set(FREE);
throw new TimeoutException();
}
} while (!tail.compareAndSet(currTail,
node);
return currTail;
}

Question 31

how does a node wait for its predecessor in CLock?

Answer 31

private void waitforPredecessor {
if (pred == null)
return;
State predState = pred.state.get();
while (predState != RELEASED) {
if (predState == ABORTED) {
Qnode temp = pred;
pred = pred.pred;
temp.state.set(FREE);
}
if (timeout()) {
node.pred = pred;
node.state.set(ABORTED);
} throw new TimeoutException();
predState = pred.state.get();
}
pred.state.set(FREE);
return;
}

Question 32

unlock for CLock

Answer 32

public void unlock() {
myNode.state.set(RELEASED);
}