Synchronization

CS2112

 2019/11/12 

Monitor

idea: object state guarded by its mutex

monitor is just a class, whose all public methods “synchronize,” which means you can’t access state without holding mutex

Principal: let short methods hold the mutex in case it doesn’t affect performance

1 2	T1: add(elem) T2: size(); contains(elem);

when elem is added, it may not be seen in size. So add should be written as synchronized add (T elem) {}

Locks & Deadlock

Lock is achieved by a mutex
deadlocks happen when all threads end up being blocked by a mutex

e.g.

class a{
    synchronized f(){ b.g();}
}
class b{
    synchronized g() { a.f() }
}

1 2	T1: a.f() ---> b.g() T2: b.g() ---> a.f()

Say we first go into T1, we acquire a; Then before going into b.g() in T1, we acquire b.g() in T2. Then we get into a deadlock cause we can’t get b.g() in a.f() nor vice versa.

That’s because we wrote a lock acquisition order in cycle

Solution:

no cycle
write an order in which to acquire mutex

e.g. a<b: can’t acquire a after b (which makes b.g() illegal)

And then write a spec /** Requires: lock level < a */
acquire mutex in the same order (T1: A,B; T2: A,B instead of T2: B,A)

Barriers

in scientific computation, there are many computations embarrassingly parallel

span N threads and wait until they are all done
updates before barrier will be seen by all threads after the barrier

1
2
3

b = new CyclicBarrier(N); // N is the number of threads(without R/W sharing)
// after each thread finishes executing, it will wait(), until all threads are done
// (the barrier blocks everything until N await() are called)

Blocking Abstractions

How to build your own threads-blocking abstractions?

e.g.

/** computes two threads seperately and then add them together*/
class WorkerPair extends Runnable
{
    int done=0; // # threads done (0~2)
    Object result;
    
    WorkerPair(){
        new Thread(this).start();
        new Thread(this).start();
    }
    
    public void run(){
    	realDoWork(); //TODO implement this
    	synchronized(this){ // Why not put a synchronized around run()? because then only one thread will really realDoWork();
    		done++;
    		result = something;
    	}
    }
    
    Object getResult(){
    	while(done<2){...}
    	return result;
    }
    
}

Condition Variables

allow you to block things until some condition is true
a condition variable is always associated with a mutex
every Java object has its own condition variable, which ties to its own mutex

A notifyAll() is sent whenever any of the conditions may become true; threads awakened by notifyAll() then test to see if their particular condition has become true; otherwise, they go back to sleep.

/** Effect: blocks thread and releases mutex, wait for some condition to become true
(note: why should wait() release mutex? Becuase when the program enters this waiting thread, this thread first acquires mutex, so when it begins to wait, it has to release it so other threads can do their work and finally wake it up after done)
	Requires: mutex is held*/
void wait();

/** Effect: return all wait() method (Unblocks/Wake up all threads that are waiting)
	Requires: mutex held*/
void notifyAll();

To block until condition is true:

public void run(){
    realDoWork();
    synchronized(this){ 
    	done++;
    	result = something;
        notifyAll();
    }
}

synchronized Object getResult(){
    while(done<2) wait();
    return result;
}