[OS] 동기화 도구

경쟁 상태(Race Condition)

공유 데이터에 동시 액세스하면 데이터 불일치를 초래할 수 있다.

x=2? 3? 1?

경쟁 상태

• 여러 프로세스가 동시에 공유 데이터에 액세스하고 조작하는 상황.
• 경쟁 상태를 방지하려면 동시 프로세스를 동기화해야 한다.
• 유니프로세서 환경에서는 CPU 스케줄러에 의해서도 경쟁 상태가 발생할 수 있다.

 

---

크리티컬 섹션 문제

크리티컬 섹션

• 공유 데이터에 액세스하는 코드 세그먼트

크리티컬 섹션 문제

• 한 프로세스가 크리티컬 섹션에서 실행 중일 때 다른 프로세스가 크리티컬 섹션에서 실행되지 않도록 한다.

프로세스가 협력하는 데 사용할 수 있는 프로토콜을 설계해야 한다.

일반적인 프로세스 Pi의 일반적인 구조

do {
	entry section
	critical section
	exit section
	remainder section
} while (TRUE);

• 섹션 진입(entry section)
      중요 섹션에 들어갈 수 있는 권한을 요청하는 코드 세그먼트
• 섹션 종료(exit section)
      중요 섹션의 종료를 알리는 코드 세그먼트

 

---

해결 요건

상호 배제(Mutual Exclusion)

• 프로세스 Pi가 크리티컬 섹션에서 실행 중인 경우
• 그러면 다른 어떤 프로세스도 크리티컬 섹션에서 실행될 수 없다.

실행

• 크리티컬 섹션에서 실행 중인 프로세스가 없는 경우
• 크리티컬 섹션에 들어가고자 하는 프로세스가 존재하며,
• 다음에 크리티컬 섹션에 진입할 프로세스의 선택을 무기한 연기할 수 없다.

대기 제한

• 기아(starvation)를 방지하기 위해 시간 제한이 존재한다.

 

---

크리티컬 섹션 처리

커널이 선점형/비선점형인지에 따라 두 가지 접근 방식

• 선점형 :  커널 모드에서 실행할 때 프로세스의 선점을 허용
• 비선점형 : 커널 모드를 종료하거나 차단하거나 자발적으로 CPU를 양보할 때까지 실행
• 기본적으로 커널 모드에서 경쟁 상태(race conditions)가 없다.

 

---

Peterson의 해결 방안

두 프로세스 동기화를 위한 해결 방안

두 프로세스는 두 변수를 공유

• int turn;
      크리티컬 섹션에 들어갈 차례
• boolean flag[2];
      프로세스가 크리티컬 섹션에 진입할 준비가 되었는지 여부
      프로세스 Pi가 준비되면 flag[i] = true

프로세스 Pi에 대한 알고리즘

while (true) {
		┌	flag[i] = TRUE;
entry section	│	turn = j;
		└	while (flag[j] && turn == j);

			critical section
    
exit section	-	flag[i] = FALSE;

			remainder section
}

flag[j]는 "j가 들어가고 싶다"를 의미
'turn == j'는 "이것은 j의 차례입니다"를 의미
→ 작동하지 않음

프로세스 Pj에 대한 알고리즘

while (true) {
		┌	flag[j] = TRUE;
entry section	│	turn = i;
		└	while (flag[i] && turn == i);

			critical section
    
exit section	-	flag[j] = FALSE;

			remainder section
}

 

---

동기화 하드웨어

간단한 도구 - 잠금(lock)

do {
	acquire lock
	critical section
	release lock
	remainder section
} while (TRUE);

최신 기계는 특별한 원자 하드웨어 명령을 제공

• 원자(Atomic) = 인터럽트 불가능(non-interruptable)
• 메모리 워드를 테스트하고 값을 설정
• 두 메모리 워드의 내용을 교환(swap)

 

---

동기화 하드웨어

TestAndSet 명령

• 단어의 내용을 원자적으로 테스트하고 수정

boolean TestAndSet (boolean *target)
{
	boolean rv = *target;
	*target = TRUE;
	return rv:
}

• 1. 원래 값을 반환
• 2. 값을 참으로 설정

공유 부울 변수 잠금(lock)이 false로 초기화

해결책

while (true) {
	while (TestAndSet(&lock )) ; /* do nothing */
	critical section
	lock = FALSE;
	remainder section
}

• 1. '잠금' 값을 반환
• 2. '잠금'을 참으로 설정

스왑 명령

• 두 단어의 값을 전환

void Swap (boolean *a, boolean *b)
{
	boolean temp = *a;
	*a = *b;
	*b = temp:
}

공유 부울 변수 잠금(lock)이 FALSE로 초기화

각 프로세스에는 로컬 부울 변수 키가 있다.

while (true) {
	key = TRUE;
	while (key == TRUE)
		swap (&lock, &key);
	critical section
	lock = FALSE;
	remainder section
}

• "key == true"는 "입력하고 싶다"를 의미
• "lock == true"는 "그가 입력했습니다"를 의미

 

---

세마포어

세마포어 S

• 정수 변수

S를 수정하는 두 가지 표준 작업

• wait(), signal()
      원래 이름은 P(), V()

P(S) {
	while (S <= 0) ; // noop
	S--;
}

V(S) {
	S++;
}

• 양수이면 감소하고 입력,
• 그렇지 않으면 양성이 될 때까지 기다린다.

세마포어의 사용

• 두 개의 프로세스 Pi & Pj, 두 개의 크리티컬 섹션 A & B
• S를 1로 초기화

바이너리 세마포어

• 정수 값의 범위는 0과 1 사이만 가능
• 상호 배제 제공

세마포어 계산

• 정수값은 무제한 도메인에 걸쳐 있을 수 있다.

 

---

세마포어 구현

Busy waiting(= spinlock)

• 어떤 프로세스가 크리티컬 섹션에 있는 동안 다른 프로세스는 계속 반복
• CPU 사이클을 낭비

P(S) {
	while (S <= 0) ; // noop
	S--;
}

• 양수가 될 때까지 기다린다.
• (Busy waiting)

Block and wakeup

• 각 세마포어에 대해 연결된 대기 큐가 있다.

Typedef struct {
	int value; // semaphore
	struct process *list; // waiting queue
} semaphore;

• 구조체 세마포어 S :
      value: 0   →   PCB   →   PCB   →   PCB
      list

두 가지 작업

• Block
      P(S) 자체를 호출한 프로세스를 일시 중단
      이 프로세스의 PCB를 세마포어 S의 대기 큐에 삽입
• Wakeup(P)
      세마포어 S에 대한 대기 큐에서 프로세스 P의 PCB를 제거
      P의 실행 재개

block과 wakeup으로 세마포어 구현

P(S){
	S.value--;
	if (S.value < 0) {
		add this process to waiting queue.
		block();
	}
}
V(S){
	S.value++;
	if (S.value <= 0) {
		remove a process P from the waiting queue.
		wakeup(P);
	}
}

어느 것이 더 좋습니까?

• Busy-waiting
      컨텍스트 전환이 필요하지 않다.
      크리티컬 섹션의 길이가 짧을 때 좋다.
• Block-wakeup
      컨텍스트 전환이 필요하다.
      크리티컬 섹션의 길이가 길 때 좋다.

 

---

요약

• 경쟁 상태
      여러 프로세스가 동시에 공유 데이터에 액세스하고 조작하는 상황
• 크리티컬 섹션
      공유 데이터에 액세스하는 코드 세그먼트
• 세마포어 S
      P() 및 V() 작업을 통해서만 액세스할 수 있는 정수 변수
• Busy-Waiting
      짧은 크리티컬 섹션에 좋다.
• block-wakeup
      긴 크리티컬 섹션에 좋다.