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 문제는 여전히 남아있다.
