Distributed Mutual Exclusion Algorithm

Lamport’s distributed mutual exclusion algorithm https://en.wikipedia.org/wiki/Lamport%27s_distributed_mutual_exclusion_algorithm

Ricart-Agrawala algorithm https://en.wikipedia.org/wiki/Ricart%E2%80%93Agrawala_algorithm

Suzuki-Kasami algorithm (Token-passing mutual exclusion algorithm)

Raymond’s Algorithm (Tree-based token algorithm)



HW3 (Due by 12/4 23:59) 프린트는 수업시간에 제출

1. thread-cpp11-sharedcounter vs thread-cpp11-mutex vs thread-cpp11-nomutex test report
-윈도우,리눅스에서 실행해서 테스트해본다.
-코드 분석 및 실행 결과 리포트 2~3장

2. multithread-java-synchronized vs multithread-java-notsynchronized test report
-윈도우,리눅스에서 실행해서 테스트해본다.
-코드 분석 및 실행 결과 리포트 2~3장

3. multithread-java-synchronized WOEID
-WOEIDLIST1.csv~WOEIDLIST3.csv 파일을 각각 다른 쓰레드에서 로딩해서 하나의 매니저에 데이타 추가(Insert)후 출력(Print) 및 검색(Query)
woeid (Woeid, WoeidImporter)

4. Insert & Query synchronized data via ThreadedTCP
-ThreadedTCP-java (TCP threaded blocking) 사용
-WOEIDLIST1.csv~WOEIDLIST4.csv 파일을 각각 다른 클라이언트에서 서버로 데이터를 하나씩 보내서 서버 매니저에 데이타 추가(Insert)후 검색(Query)
-java 버전 (Windows와 Linux)으로 작성
-서버는 Threaded TCP & synchronized data manager 사용
-4개의 클라이언트는 각각 다른 파일(WOEIDLIST1.csv~WOEIDLIST4.csv)을 로딩하여 하나씩 Woeid 데이터 입력 메시지(INSERT id,city,country,latitute,longitude)를 전송(send) 하여 서버에서 새로운 데이터 insert 후 회신받음(receive)
-또한 클라이언트는 Woeid 데이터 검색 메시지(QUERY Seoul)를 전송(send)하여 서버 매니저에서 검색한 결과 Woeid 데이터를 회신받음(receive)
-또한 클라이언트는 전체리스트출력 메시지(PRINT)를 전송(send)하여 서버 매니저에서 리스틀 전체 출력하고 회신 받음(receive)

Java Thread yield() vs join() vs sleep()


We can prevent a thread from execution by using any of the 3 methods of Thread class:

  • yield()
  • join()
  • sleep()

yield() method pauses the currently executing thread temporarily for giving a chance to the remaining waiting threads of the same priority to execute. If there is no waiting thread or all the waiting threads have a lower priority then the same thread will continue its execution. The yielded thread when it will get the chance for execution is decided by the thread scheduler whose behavior is vendor dependent (i.e., yield() can only make a heuristic attempt to suspend the execution of the current thread with no guarantee of when will it be scheduled back).

join() The current thread can invoke join() on any other thread which makes the current thread wait for the other thread to die before proceeding. If any executing thread t1 calls join() on t2 (i.e, t2.join()) immediately t1 will enter into waiting state until t2 completes its execution.

sleep() method can force the scheduler to suspend the execution of the current thread for a specified period of time as its parameter.

Java Thread Synchronization

Thread Synchronization


    • Mutex Semaphore (aka Mutex) controls only one thread at a time executing on the shared resource by lock & unlock.
    • Counting Semaphore (aka Semaphore – Java7) controls the number of threads executing on the shared resource by acquire & release.
    • Monitor controls only one thread at a time, and can execute in the monitor (shared object) by wait & notify/notifyAll.

Thread Mutex vs NoMutex

Thread with Mutex (cpp11)
– threadFunc에서 mutex를 사용하여 global variable 인 count 가 정상적으로 증가하면서 출력함

Thread without Mutex (cpp11)
– threadFunc에서 mutex를 사용하지 않고 global variable인 count 를 증가하면서 출력을 했으므로, 정상적인 순서대로 동작하지 않음

Thread with Mutex (cpp11)
–threadFunc에서 mutex를 사용하여 SharedCounter 가 정상적으로 증가하면서 출력함

Java Thread Synchronization
Monitor를 사용하여 SharedCounter 가 정상적으로 증가하면서 출력함

Java Thread No Synchronization
– Monitor를 사용하지 않고 SharedCounter 를 증가하면서 출력을 했으므로, 정상적인 순서대로 동작하지 않음

Lamport vs Vector Clock

4 processes (P1, P2, P3, P4) with events a,b,c,d,e,f,g,…


Lamport Clock Timestamps

For each process, p:
    initialize the timestamp, TS = 0;
    on each event, e:
        if e is receiving message m, 
            p.TS = max(m.TS, p.TS);
        e.TS = p.TS;
        if e is sending message m, 
            m.TS = p.TS;


Vector Clock Timestamps

For M processes:
    initialize the timestamp, p.VT = (0,0,..,0);
    on each event, e:
        if e is receiving message m, 
            for i=1 to M, 
                p.VT[i] = max(m.VT[I], p.VT[I]);
        e.VT = p.VT;
        if e is sending message m, 
            m.VT = p.VT;