#6 동기화(Synchronization) 3 - HW Solution

1. Test And Set(TAS) 명령어

boolean TestAndSet(boolean *target) {
    boolean tmp = *target;
    *target = true;
    return tmp;
}

• Test, Set 연산을 한번에 원자적으로 수행하는 기계 명령어
  => 실행중 인터럽트를 받지않는것이 보장됨
  
  

 

2. TAS 를 사용한 상호배제

while True:
    while TAS(lock):
        pass
 
 	''' 임계 영역 '''
 
	lock = False

• lock 을 획득하는 과정을 기계적으로 보장
• 위 방식만으로는 3개 이상의 프로세스에 대해서는 Bounded Wait 규칙에 위배될 수 있음

 

 

3. TAS를 사용한 n개의 프로세스의 상호배제

while True:
    waiting[i] = True
    key = True
    # 자신이 대기상태이고 lock이 걸려있는 상태일 경우 대기
    # 지속적으로 lock의 상태를 확인하여 lock이 해제된 경우 
    # key는 False가 되고 lock은 다시 True가 되어 다른 프로세스의 진입을 막고 작업시작
    while waiting[i] & key:
        key = TAS(lock)
        
    # lock을 획득했기 때문에 대기상태 해제
    waiting[i] = False
    
    ''' 임계 영역 '''
    
    # 자신을 제외한 다른 대기중인 프로세스들이 있는지 확인
    j = (i + 1) % n
    while j != i and not waiting[j]:
        j = (j + 1) % n
        
    # 대기중인 프로세스가 없을 경우 lock을 해제
    if j == i:
        lock = False
        
    # 대기중인 프로세스를 찾았을 경우 굳이 lock을 해제하지 않고 
    # 해당 프로세스의 대기상태를 해제(waiting[j] = False)하여 진입시켜준다.
    # 이렇게 하는것으로 대기중인 모든 프로세스들은 순서대로 수행되기에 
    # n개의프로세스의 상호배제에서도 bounded waiting 규칙을 만족시킬 수 있다.
    else:
        waiting[j] = False

• 임계구역에의 진입 조건을 lock의 획득만이 아니라 waiting 상태의 해제로도 가능하도록 한 방식
  
  
• 임계구역에 진입한 프로세스는 작업이 완료되면 굳이 lock을 해제하지 않고 대기중인 다른 프로세스중
  가장 먼저 찾아낸 프로세스의 대기상태를 해제시키는 것으로 진입을 허가한다. 
  
  
• 이렇게 하면 대기중이었던 프로세스들은 다른 프로세스들과의 경쟁없이 자신의 순서가 오면 자연스레
  임계구역에 진입하게 되기 때문에 bounded waiting 문제가 해결된다. 
  
  
• TAS의 존재덕분에 SW Solution들에 비해 구현은 훨씬 간단해졌지만 busy waiting 문제는 여전히 남아있다.