Semaphores/Producer-Comsumer

Question 1

Semaphore

Answer 1

A way of stopping threads from colliding in critical regions.

Question 2

Operations in Semaphores

Answer 2

There are two operations:
- wait()
- signal()
A thread must call wait() before entering a critical region, obtaining the lock it if it free or waiting if it is not (in this case, it is called being blocked).
A thread must call signal() when leaving the critical region, unlocking the semaphore.

Question 3

Producer-Consumer Problem

Answer 3

• Producer and Consumer are split into separate threads with different roles.
• Both require access to a shared resource.
• There can be multiple consumers or producers.

Question 4

Buffer Example

Answer 4

Lets say we had a class called Buffer:

class Buffer {
private int store;

public void insert(int item) {
    store = item;
}

public void remove() {
    return store;
}

}
We can then declare in another method a class called Producer that extends Thread, which when instantiated, creates a Producer Thread which has a private buffer attribute (private Buffer buff;). We can then call public void run() {} and inside it, use buff.insert(1); to insert an item. There can be anther class called Consumer, but instead of running .insert, we can run .remove instead. Finally we can create a main class which executes this:

public class ProdCon {
public static void main(String[] args) {
Buffer b = new Buffer();
Producer p = new Producer(b);
Consumer c = new Consumer(b);
p.start();
c.start();
}
}

Question 5

Buffer Correction Attempt 1

Answer 5

However, we know that this does not protect us from race conditions, so instead we can try to add volatile and boolean statements:
class Buffer {
private int store;
private volatile boolean empty = true;
public void insert(int item) {
while(!empty);
store = item;
empty = false;
}

public void remove() {
    while(empty);
    empty = true;
    return store;
}

}

Question 6

Volatile

Answer 6

This essentially allows us to use the last value it was declared as, since it allows the value to be shown and shared between other threads.

Question 7

Spinlock

Answer 7

Using
while (!empty);
empty = false;

and

while(empty);
empty = true;

is the concept of spinlock. Since the status variable is shared between threads, threads can recognise if a thread has removed the item, allowing the next thread to insert its item.

Question 8

Yielding / Buffer Correction Attempt 2

Answer 8

There is another alternative, which is yielding:
class Buffer {
private int store;
private volatile boolean empty = true;
public void insert(int item) {
while(!empty) {
Thread.yield();
}
store = item;
empty = false;
}

public void remove() {
    while(empty) {
            Thread.yield();
    }
    empty = true;
    return store;
}

}
What this does is give up control of the CPU, allowing the CPU to do other stuff instead of waiting. It still needs to be in a spinlock, however, since this request can be ignored.

Question 9

Synchronization / Buffer Correction Attempt 3

Answer 9

class Buffer {
private int store;
private volatile boolean empty = true;
public synchronized void insert(int item) {
while(!empty) {
Thread.yield();
}
store = item;
empty = false;
}

public synchronized void remove() {
    while(empty) {
            Thread.yield();
    }
    empty = true;
    return store;
}

}
The keyword synchronization declares that the thread has entered a critical region, getting exclusive control of the lock if it is free, blocking other threads if it is not. And when it leaves, it relinquishes access to the lock, and other threads then can access it.

Question 10

Synchronization with wait() and notify()

Answer 10

public synchronized void insert(int item) {
while(!empty) {
wait();
}
store = item;
empty = false;
notify();
}
The wait() calls suspend current thread and moves it to the wait set.
Notify() calls a random thread in the wait set and places it in the entry set.
We can also call notifyAll() to allow all threads in the wait set to compete for the chance to resume, with the winner calling synchronized first.

Question 11

Semaphore Class / Final Buffer Correction

Answer 11

class Buffer {
private int store;
private Semaphore sem = new Semaphore(1);
public synchronized void insert(int item) {
sem.acquire();
store = item;
sem.release();
}

public synchronized void remove() {
    sem.acquire();
    int item = store;
    sem.release();
    return item;
}

}
When the aquire() method is called, if the counter is 0, the thread will block, if it is greater, the counter is decreased and the thread can continue.
When the release() method is called, the counter is increased and the first thread in the wait queue is permitted to continue.
Testing and setting the counter must be atomic operations to prevent race conditions.