Mutual Exclusion & Dekker's Algorithm

Requirement for Mutual Exclusion Primitive

• Mutual exclusion (상호배제) : 공유자원에 동시에 접근 못함

• Progress (진행) : 공유자원에 다른 프로세스가 접근하지 않은 상태면 바로 쓸 수 있어야 함

• Bounded waiting (한정대기) : 기다리다 보면 언젠가는 접근 할 수 있어야

Dekker's Alogirthm

Dekker's Algorithm이란 두 프로세스간 동시성 제어시 상호배제문제를 해결하는 알고리즘이다.

해당 알고리즘은 두개 'flag'와 하나의 'turn' 토큰을 이용하여 상호배제를 보장한다.

• flag: Ture 일떄 임계구역으로 들어가길 원하는 상태, False는 그 반대
• turn: 0과 1의 값을 가지며 현재 동시에 진행중인 프로세스간의 차례를 나타낸다.

import threading
import random
import time

class DekkersAlgorithm():
    #  flags to indicate if each prcoess is in queue to enter its critical section
    flag = [False, False]
    # to denote which prcoess will enter next
    turn = 0

    def process0(self):
        #process 0 wants to enter
        self.flag[0] = True
        while self.flag[1] == True:
            #if process1 is already running..
            if self.turn == 1:
                # gives access to other prcoess  wait for random amount of time
                self.flag[0] = False
                while self.turn == 1:
                    #process 0 is waiting for process 1 to complete
                    print("waiting")
                self.flag[0] = True
        #critical section
        print("process 1 running in critical section")

        # remainder section
        self.turn = 1
        self.flag[0] = False



    def process1(self):
        #process 1 wants to enter
        self.flag[1] = True
        while self.flag[0] == True:
            #if process0 is already running..
            if self.turn == 0:
                # gives access to other prcoess  wait for random amount of time
                self.flag[1] = False
                while self.turn == 0:
                    #process 1 is waiting for process 0 to complete
                    print("waiting")
                self.flag[1] = True
        #critical section
        print("process 2 running in critical section")

        # remainder section
        self.turn = 0
        self.flag[1] = False

    def main(self):
        while True:
            t1 = threading.Thread(target = self.process0)
            t1.start()
            t2 = threading.Thread(target = self.process1)
            t2.start()


if __name__ == "__main__":
    d = DekkersAlgorithm()
    d.main()

waiting
process 1 running in critical section
waiting
process 2 running in critical section
process 2 running in critical section
process 1 running in critical section
process 2 running in critical section
process 2 running in critical section
waiting

process 1 running in critical section
waiting
process 1 running in critical section
#KeyBoard Interrupt to Exit