Concurrent Programming Concepts Review

Posted on Edited on In , ,

Background

As a Chinese old saying goes: Review the old and know the new (温故而知新). I learnt a lot from the OS class, recently, despite that I have taken this class 5 years ago during my undergraduate study. The latest topic discussed on the class is concurrency and deadlock, I think it is a good time for me to review some concepts of concurrent programming.

Mutual Exclusion / Synchornization Methods

Mutual Exclusion VS Synchornization

  1. Mutual Exclusion: There is a critical section (process can write shared data here) that allows only one process to enter. To ensure there is no other process enter this area, some measures should be applied here which called mutual exclusion.

  2. Synchornization: A process can only execute when others finish their work. So we should take some actions to guarantee this, which are synchornization methods.

Busy Waiting

Disabling Interrupts

The crucial problem for busy waiting is how to ensure the critical region can not be entered by two different processes at a time. As we known, preemption happens with interrupts. If we disable interrupts temporarily when there is a process enter the critical section, this problem can be solved. But only on single processor system.

On multi-processor system this does not work, because interrupts can only be disabled on one of the processors. Processses running on other processor can still enter the critical section simultaneously.

Lock Variable

It is a very simple solution to this problem. Check if the lock variable is 0, continuously. If it becomes 0, set it to 1, and enter the critical region. When it finishes, reset the lock variable to 0, so that other waiting process can enter the critical section.

But this can not work as expected, because you can’t perform the set lock operation atomically. There are changces for other processes modify the lock variable at the same time. The solution is not work either.

TSL (Test and Set Lock)

This is a hardware supported primitive. Using lock variable needs set and read lock variable atomically, which means no other operation can interrupt the lock setting procedure. Most of CPUs implement the TSL instruction to support this function. TSL means test and set lock. CPU will first lock the memory bus to prohibit other CPUs from accessing memory, then copy the lock value into register and store a non-zero value to lock variable. So this guarantees the operation is indivisable.

XCHG (Exchange)

It is an alternative atomic instruction for TSL. Just like its name, XCHG will exchange the value in a resgister with value in memory (lock variable).

Semaphore

Busy waiting with TSL and XCHG can solve the problem, but they are not efficient enough. Busy waiting consumes a lot of CPU resources to check whether the lock varaible is available.

Semaphore is not like busy waiting, it does not run the checking procedure continuously. Instead, semaphore mechanism uses sleep and wakeup to make it work.

semaphore is a variable indicating how many processes can perform action. value of semaphore could be 0 or greater than 0. When a process want to perform action, it should decrease the semaphore by 1. When it finishes its work, it becomes ready and increases the semaphore by 1. When the semaphore is 0, which means nobody can perform action at this time, the process will be put into sleep by scheduler. Util the semaphore becomes greater than 0, scheduler will randomly wakes up that number of sleeping processes doing its job.

The decrement and increament operations are named P, V (Proberen (try) and Verhogen (raise, make higher) in Dutch, because its inventor, Dijkstra, is from Netherlands) operations. It is essential for ensuring these operations are atomic. So usually implementations apply TSL and XCHG for these operations to promise atomicity.

eg: Producer and Consumer Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define N 100 // N slots in the buffer
item buff[N]; // buffer slots
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void Producer() {
    while(True) {
        item ele = produceEle(); // produce element
        P(empty); // decrease number of empty semaphore
        P(mutex);
        insertElem(ele, buff); // insert element into buffer slot.
        V(mutex);
        V(full); // increase number of full semaphore
    }
}

void Consumer() {
    while(True) {
        P(full); // decrease number of full semaphore
        P(mutex);
        item ele = removeEle(buff); // remove element from buffer
        V(mutex);
        V(empty); // increase number of empty semaphore
        consumeEle(); // consume the element
    }
}

Mutex

As we see in the code sniplet before, when the value of semaphore are only 0 or 1, it is called a binary-semaphore, or a mutex which could be used for mutual exclusion and synchornization.

Futex

Every lock and unlock operation will first trap into kernel by sycalls to check if the lock variable is owned by others. But, in reality, most of time the lock variable does not belongs to anyone.It is usually free for processes to enter the critical section, but the test lock procedure still cost a lot by doing a syscall. To make this more efficient, futex were created.

Futex stands for “Fast Userspace muTexes”, which, basically, does the lock test procedure in user space. Only when the lock is not free, it performs a syscall. That’s why futex improves performance a lot.

Condition Variables

Condition Variables is a synchornization mechanism. Synchornization needs more than just mutual exclusion; also need a way to wait for another thread to do something (e.g., wait for a character to be added to the buffer). So, it provides a way to make process wait util the specific condition is fullfilled.

Which Lock Should I Use

Which Lock should I use, busy waiting or semaphores? There are two simple principles:

  1. If lock hold time is short or task is uninterruptable, busy waiting and lock variables are OK (Linux kernel always use it).

  2. Else use semaphores.

Deadlock VS Starvation

These two concepts are usually confusing. Basically, Deadlock happens when processes are waiting on events or resources that will never come. It can be on only one process or system wide. And in this case, no process can go further.

Under Starvation, some process can move forward, but there does have some process(es) can not be excuted. Because, there is no resource available for them to access, due to scheduling reason.

For an instance, if the process scheduler always process short execution time process first (SRTF), the long run time process may have no changce to be executed, if there always comes short time tasks. Then, a starvation happened.

How Does Deadlock Happen

When a process A need a resource to move forward, but that resource is held by process B. At the meantime, process B is also waiting for the resource held by A.

If the resource is like memory, which can be preempted, deadlock will not happen. But, if it is a non-preemptable resource, like a Blu-ray recorder, deadlock will happen.

There are 4 essential conditions for deadlock:

  1. Each resource is either currently assigned to exactly one process or is available.
  2. Processes currently holding resources that were granted earlier can request new resources.
  3. Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them.
  4. There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain.

Deadlock Detection

Basically, the algorithm to detect deadlock is to detect cycles in the resource allocation graph.

For Each node N in the graph do:

  1. Initialize L to empty list and designate all arcs as unmarked
  2. Add the current node to end of L. If the node appears in L twice then we have a cycle and the algorithm terminates
  3. From the given node pick any unmarked outgoing arc. If none is available go to 5.
  4. Pick an outgoing arc at random and mark it. Then follow it to the new current node and go to 2.
  5. If the node is the initial node then no cycles and the algorithm terminates. Otherwise, we are in dead end. Remove that node and go back to the previous one. Go to 2.

Deadlock Prevention

If one of the 4 essential conditions can’t be reached, deadlock is impossible structurally.

References

  1. https://web.stanford.edu/~ouster/cgi-bin/cs140-spring14/lecture.php?topic=locks
  2. Modern Operating Systems 4th Edition–Andrew Tanenbaum.pdf Section 2.3 and 6