CS/OS

[OS]임계 구역 문제와 해결 방안(1) - 하드웨어 지원

frog-in-well 2022. 7. 27. 17:52

1. 임계 구역 문제

프로세스 동기화는 임계 구역 문제로부터 시작한다. 각 프로세스는 임계 구역이라고 부르는 코드 부분을 포함하고 있다. 임계 구역은 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있는 코드 영역이다. 즉 임계 구역은 경쟁 상태가 발생할 수 있는 곳이다.

임계 구역 문제 해결을 위한 조건

  1. 상호 배제(mutual exclusion) : 프로세스가 자신의 임계 구역에서 실행된다면, 다른 프로세스들은 자신의 임계 구역에서 실행될 수 없다.
  2. 진행(progress) : 다른 프로세스가 임계 구역에서 실행 중이지 않다면 프로세스는 임계 구역에서 실행될 수 있다.
  3. 한정된 대기(bounded waiting) : 프로세스가 자기의 임계 구역에 진입하려는 요청을 한 뒤부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계 구역에 진입하도록 허용되는 횟수에 한계가 있다.

2. 임계 구역 문제 해결 방안

2.0 Peterson’s Solution

Peterson Solution은 임계 구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스가 있는 경우로 한정해서 생각한다. 두 프로세스가 두 개의 데이터 항목을 공유하여 문제를 해결한다. (공유 메모리를 통한 해결)

  • int turn, boolean flag[2]
  • 변수 turn은 임계 구역으로 진입할 순번을 표시한다. 만약 turn == i 라면 Process i가 임계 구역에서 실행될 수 있다.
  • flag 배열에는 프로세스가 임계 구역으로 진입할 준비가 되었다는 것을 표시한다. 만약 flag[i] == True 라면 Process i 가 임계 구역으로 진입할 준비가 된다.

 

while Ture:
	flag[i] = True
	turn = j
	
	while (flag[j] and turn==j) :
		#j가 flag 내릴 때까지 숨참음
		continue
	
	#critical section start
	#...
	#critical section end
	flag[i] = False
  1. 임계 구역으로 진입하기 위해 Process i는 flag[i]를 참으로 만들고, turn을 j로 설정한다.
  2. 만약 Process j 도 깃발을 들었다면, Process j가 임계 구역에서 실행되기를 기다린다. 이후 Process j가 깃발을 내리면 Process i가 임계 구역에 들어간다.
  3. 임계 구역에서의 실행이 끝나면 Process i도 깃발을 내린다.

이 해결책은 임계 구역 문제 해결을 위한 조건 3가지를 모두 만족한다.

 

3. 하드웨어 지원을 통한 동기화

Peterson’ Solution은 고전적인 소프트웨어 기반의 해결책이었다. 이러한 방식은 현대의 컴퓨터 아키텍처에서 작동하지 않을 수 있다. 임계 구역 문제를 해결하기 위한 실질적인 하드웨어 명령어를 살펴보자.

1. 메모리 장벽 (Memory Barriers)

컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항을 알려준다. 이러한 명령어를 메모리 장벽이라고 한다.

x = 100 
memory_barrier()
flag = True

위와 같은 경우에 x에 대한 메모리의 저장이 완료되고 다른 프로세서에 보이도록 한 뒤 flag=True 로 연산이 수행되도록 한다.

2. 하드웨어 명령어, test_and_set() & compare_and_swap()

1. test_and_set()

하드웨어 명령어는 데이터의 접근 → 연산 → 연산 결과 저장의 과정을 한 번에 수행할 수 있는 하드웨어적인 지원을 해주는 것이다. 한 번에 수행하는 것을 atomically(원자적으로)하게 수행한다고 표현한다. 다시 말해, 원자적으로 수행한다는 것은 인터럽트 되지 않고 수행된다는 것이다.

 

def test_and_set(lock):
	tmp = lock

	lock = True

	return tmp
  • test_and_set(lock) 명령어는 lock의 값을 읽고(복사 후 반환) , lock을 True로 설정하는 일을 한 번에(원자적으로) 수행한다.

 

while test_and_set(lock) :
	#wait
	continue

#critical section

#lock 해제
lock = False
  • 만약 lock이 True 였다면, test_and_set은 lock을 True로 설정하고, True를 반환할 것이므로 반복문에서 돌게 된다.
  • 만약 lock이 False였다면, test_and_set은 lock을 True로 설정하지만, False를 반환하므로 반복문에서 빠져나와 critical section을 수행한다. 수행이 끝나면 다시 lock을 False로 설정한다.

2. compare_and_swap()

CAS 명령어도 마찬가지로 원자적으로 특정한 연산을 수행해준다. test_and_set 과는 다르게 3개의 매개 변수를 사용한다. 결과적으로 본다면 test_and_set과 동일하게 작동하게 된다.

 

def compare_and_swap(value, expected, new_value):
	tmp = value

	if value == expected :
		value = new_value

	return tmp
  • test_and_set과 마찬가지로 value 값을 읽고(복사 후 반환), value가 expected와 같다면, value의 값을 new_value로 설정하는 일을 한 번에 수행한다.

 

while compare_and_swap(lock, False, True) : 
	#wait
	continue

#ciritical section

#lock 해제
lock = False
  • 만약 lock이 True 였다면, compare_and_swap은 lock을 True를 반환하여 반복문에서 돌게 된다.
  • 만약 lock이 False 였다면, compare_and_swap은 expected 값인 False와 같기 때문에 lock을 True로 설정하지만, False를 반환하기 때문에 반복문에서 빠져나와 critical section을 수행한다. 수행이 끝나면 다시 lock을 False로 설정한다.

 

+)CAS에서는 1,0을 사용하여 lock의 값을 할당한다고 공룡책에는 설명되어 있지만 쉽게 이해하기 위해 True, False로 바꾸어 설명했다.

3. 원자적 변수 (Atomic Variables)

원자적 변수는 CAS를 다시 원자적인 연산으로 구현하여 사용하는 도구다.

다음 글에서는 소프트웨어 도구를 통해 임계 구역 문제를 해결하는 방법인 뮤텍스, 세마포, 모니터에 대하여 설명하겠다.