Bpq,utq,ulfq (topic 9)

Question 1

what does bounded mean

Answer 1

fixed capacity

Question 2

what does total mean?

Answer 2

a method is total if calls do not wait for conditions to become try

Question 3

what does partial mean?

Answer 3

A method may wait for conditions to hold (suspending)

Question 4

What does synchronous mean?

Answer 4

a method is synchronous if it waits for another method to overlap its call interval(A method call that adds an item to the pool is blocked until that item is removed by another method call)

Question 5

Blocking vs Non-Blocking

Answer 5

Blocking: caller waits until state changes
Non-Blocking: Method throws exception

Question 6

Does the enq and deq operate on the same sides of the queue?

Answer 6

no. so enq + deq should be able to proceed concurrently without interference. only concurrent calls will interfere

Question 7

Properties of a queue(what is it and what does it consist of):

Answer 7

queue = linked list
queue has head and tail fields that refer to 1st and last nodes in list
queue contains a sentinel node (place-holder)

Question 8

What are the 2 locks used(BQ)?

Answer 8

-deqlock (lock the front of the queue to ensure that there is not 1+ dequeuer at a time
-enqlock (lock end of queue to ensure that there is not more than one enqueuer at a time)

Question 9

perks of 2 locks

Answer 9

enqueuers and dequeuers can operate independently

Question 10

can enq calls continue while list is full and deq calls when list is empty?

Answer 10

No

Question 11

What does the conditions do in the BPQ

Answer 11

notFullCondition = notify enqueuers when list is not full anymore
notEMptyCondition = notify dequeuers when list is not empty anymore

Question 12

How do we keep track of the number of available slots in the BQ?

Answer 12

use a size field that is an AtomicInteger

Question 13

code for the BoundedQueue class

Answer 13

public class BoundedQueue<T> {
ReentrantLock enqLock, deqLock;
Condition notEmptyCondition, notFullCondition;
AtomicInteger size;
Node head;
Node tail;
int capacity;
enqLock = new ReentrantLock();
notFullCondition = enqLock.newCondition();
deqLock = new ReentrantLock();
notEmptyCondition = deqLock.newCondition();
}</T>

Question 14

enq code for bounded queue

Answer 14

public void enq(T x) {
boolean mustWakeDequeuers = false;
enqLock.lock();
try {
while (size.get() == capacity)
notFullCondition.await();
Node e = new Node(x);
tail.next = e;
tail = tail.next;
if (size.getAndIncrement() == 0)
mustWakeDequeuers = true;
} finally {
enqLock.unlock();
}
if (mustWakeDequeuers)
notEmptyCondition.signalAll();
}
}
}

Question 15

deq code for bounded queue

Answer 15

public T deq() {
T result;
boolean mustWakeEnqueuers = false;
deqLock.lock();
try {
while (size.get() == 0)
notEmptyCondition.await();
result = head.next.value;
head = head.next;
if (size.getAndDecrement() == capacity)
mustWakeEnqueuers = true;
} finally {
deqLock.unlock();
}
if (mustWakeEnqueuers) {
notFullCondition.signalAll();
}
return result;
}}

Question 16

Bad thing about deq + enq methods in BPQ

Answer 16

share atomic counter which is accessed on every method call

Question 17

Solution with 2 counters in BPQ

Answer 17

enq: checks enqSideSize and proceeds as long as less than capacity
deq: checks deqSideSize and proceeds as long as greater than zero

Question 18

UTQ enq:

Answer 18

public void enq(T x) {
enqLock.lock();
try {
Node e = new Node(x);
tail.next = e;
tail = tail.next;
} finally {
enqLock.unlock();
}
}

Question 19

UTQ deq

Answer 19

public T deq() throws EmptyException {
T result;
deqLock.lock();
try {
if (head.next == null)
throw new EmptyException();
result = head.next.value;
head = head.next;
} finally {
deqLock.unlock();
}
return result;
}

Question 20

ULFQ idea:

Answer 20

extension of unbounded queue.
prevents method calls from starving by having quicker threads help slower threads

Question 21

ULFQ structure:

Answer 21

linked list. each nodes next = atomicReference (for lockfree operations)

Question 22

LFQ node class

Answer 22

public class Node {
public T value;
public AtomicReference<Node> next;</Node>

public Node(T value) {
value = value;
next = new AtomicReference<Node>(null);
}
}</Node>

Question 23

What are the 2 enqueue steps of the LFQ?

Answer 23

Logical enqueue - appends node to linked list
Physical enqueue - tail field to point to new node

Question 24

are there 2 enqueue steps of the LFQ atomic?

Answer 24

no

Question 25

What should you do if you find tail pointing to the wrong value in LFQ?

Answer 25

If tail node has non-null next field CAS the queues tail field to tail.next

Question 26

ULFQ enq:

Answer 26

public void enq(T value) {
Node node = new Node(value);
while (true) {
Node last = tail.get();
Node next = tail.next.get();
if (last == tail.get()) {
if (next == null) {
if (last.next.compareAndSet(next, node)) {
tail.compareAndSet(last, node);
return;
} else
tail.compareAndSet(last, last.next);
}
}
}
}

Question 27

ULFQ deq:

Answer 27

public T deq() throws EmptyException {
while (true) {
Node first = head.get();
Node last = tail.get();
Node next = first.next.get();
if (first == head.get()) {
if (first == last) {
if (next == null) {
throw new EmptyException();
}
tail.compareAndSet(last, next);
} else {
T value = next.value;
if (head.compareAndSet(first, next))
return value;
}
}}}