Skip to main content

Concurrent Programming

Thread​

x

//Main thread is T0
t1 = new Thread(s1); //CREATE
t1.start(); //START
s2();
t1.join(); //Join/Wait
s3().

DeadLock​

The two thread are going to join to each other. Therefore, they will wait forever and cause a deadlock.

//Main thread is T0
t1 = new Thread(s1); 
t2 = new Thread(s2);
t1.start(); 
t2.start();
s1 = t2.join();
s2 = t1.join();

Structured Locks​

Key in concurrent programming: When you using threads, you need to be careful about how they access shared resources. Avoid data races using proper synchronization, and use wait and notify when certain conditions occur.

Data Race​

INCR(A){
    A.count = A.count-1;
}

If two thread are proforming the same method, they could read and write at the same time, which causes the result unpredictable. This phenomenon is called Data Race.

Synchronized​

INCR(A){
    Synchronized(A){ //Acquires A
        A.count = A.count-1;
    } //Releases A
}

Synchronized is a method that ensures that only one thread can acquire the data at a time.

X = {Buffer, input, output}

INSERT(item){
    Synchronized(X){ WAIT IF X IS FULL
        Buffer[input] = item;
        input++;
    }
}

REMOVE(){
    Synchronized(X){ WAIT IF X IS EMPTY
        item = Buffer[output];
        output++;
        NOTIFY IF IT IS COMPLETED
        return item
    }
}

Unstructured Locks​

Consider the linked process N1 -> N2 -> N3 -> N4.

Try LOCK(L1);
    if (success){
        LOCK(L2)
        WORK(N1,N2)
        UNLOCK(L1)
        LOCK(L3)
        WORK(N2,N3)
        UNLOCK(L2)
        LOCK(L4)
        WORK(N3,N4)
        UNLOCK(L4)
    }

Liveness​

The term “liveness” refers to a progress guarantee. The three progress guarantees that correspond to the absence of the conditions listed above are deadlock freedom, livelock freedom, and starvation freedom.

Dead Lock​

The first is deadlock, in which all threads are blocked indefinitely, thereby preventing any forward progress.

Live Lock​

The second is livelock, in which all threads repeatedly perform an interaction that prevents forward progress, e.g., an infinite “loop” of repeating lock acquire/release patterns. ex. If T1 +1, T2 -1 the process will live forever.

Starvation​

The third is starvation, in which at least one thread is prevented from making any forward progress.

Dining Philosophers​

N philosophers sit in a round table, and there are N chopsticks besides them. The philosophers can think and pick up the chopstick on their left side, or pick up the chopstick on their right side. When they have a pair of chopsticks, they could start eating dinner.

You may encounter deadlock or livelock when solving the problem.

Critical Section​