OS 6. 동기화 도구(Synchronization Tools)

서론

 협력적 프로세스(collaborative process)는 시스템 내에서 실행 중인 다른 프로세스의 실행에 영향을 주거나 영향을 받는 프로세스이다. 협력적 프로세스는 노리 주소 공간(코드 및 데이터)을 직접 공유하거나 공유 메모리 또는 메시지 전달을 통해서만 데이터를 공유할 수 있다. 그러나 공유 데이터를 동시에 접근하면 데이터의 일관성을 망칠 수 있다. 이 논리 주소 공간을 공유하는 협력적 프로세스의 질서 있는 실행을 보장하여, 이를 통해 데이터의 일관성을 유지하는 다양한 도구들을 소개한다.

---

임계구역 문제

 프로세스 동기화에 관한 논의는 임계구역 문제로 부터 시작된다.

경쟁 상황(Race Condition)

 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라 한다. 경쟁 조건을 방지하려면 동시 프로세스(concurrent processes)를 동기화(synchronized) 해야 한다. 유니프로세서(uniprocessor) 환경에서는 CPU 스케줄러에 의해서도 경쟁 조건이 발생할 수 있다.

임계 구역 문제(Critical Section Problem)

 각 프로세스는 임계구역(Critical Section)이라 부르는 코드 부분을 포함하고 있고, 그 안에서도 적어도 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다. 이 시스템의 중요한 특징은 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다. 즉 동시에 두 프로세스는 그들의 임계구역 안에서 실행할 수 없다.

 임계구역 문제는 프로세스들이 데이터를 협력적으로 공유하기 위하여 자신들의 활동을 동기화할 때 사용할 수 있는 프로토콜을 설계하는 것이다. 각 프로세스는 자신의 임계구역으로 집입하려면 진입 허가를 요청해야 한다. 이러한 요청을 구현하는 코드 부분을 진입 구역(entry section)이라 부르고 임계구역 뒤에는 퇴출 구역(exit section)이 따라올 수 있다. 코드의 나머지 부분들은 나머지 구역(remainder section)이라 부른다.

해결안(Requisites for solution)

임계구역 문제에 대한 해결안은 다음의 세 가지 요구 조건을 충족해야 한다.

• 상호 배제(Mutual Exclusion): 프로세스 Pi가 임계구역에서 실행 중인 경우 다른 프로세스를 실행할 수 없다.
• 진행(Progress): 임계구역에서 실행 중인 프로세스가 없고 임계구역에 들어가고자 하는 일부 프로세스가 존재하다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 누가 그 임계구역으로 진입할 수 있는 지를 결정하는 데 참여할 수 있으며, 이 선택을 무기한 연기할 수 없다.
• 한정된 대기(Bounded Waiting): 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다. 또한, 기아(starvation)를 방지하려면 시간제한이 있어야 한다.

Critical-Section Handling

 커널이 선점형(preemptive)인지 비선점형(non-preemptive)인지에 따라 두 가지 접근 방식이 존재한다. 선점형 방식(Preemptive)은 프로세스가 커널 모드에서 실행할 때 프로세스의 선점을 허용한다. 비선점형(non-preemptive)은 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널 모드를 종료하거나 차단하거나 자발적으로 CPU를 양보할 때까지 실행한다. 본질적으로 비선점형 커널은 한순간에 커널 안에서 실행 중인 프로세스는 하나밖에 없으므로 커널 자료구조에 대한 경쟁 조건이 없다.

---

Peterson의 해결법(Peterson’s Solution)

 Peterson의 해결법은 상호 배제 문제(Mutal Exclustion Problem)를 해결하는 고전적인 알고리즘이다. 상호 배제 문제란 둘 이상의 프로세스가 공유 자원에 접근하려고 할 때, 자원에 대한 동시 접근으로 인해 발생할 수 있는 문제이다.  Peterson의 해결법은 이 문제를 해결하기 위해 두 개의 프로세스가 공유 자원에 대한 접근을 제어한다.

  Peterson의 해결법은 다음과 같은 두  개의 변수를 사용한다.

• flag: 각 프로세스의 동작을 제어하는 이진 변수
• turn: 다음에 실행할 프로세스를 지정하는 변수

이 알고리즘은 두 개의 프로세스 P0, P1이 있다고 가정하자.

초기화 : flag[0] = flag[1] = false
P0 : flag[0] = true; turn = 1; while(flag[1] == true && turn == 1); // critical section flag[0] = false;
P1 : flag[1] = true; turn = 0; while(flag[0] == true && turn == 0); // critical section flag[1] = false;

위 알고리즘에서, 먼저 flag[0], flag[1]이 초기화되고, P0이 critical section에 진입하려면 flag[0]을 true로 설정하고, turn을 1로 설정한다. 그리고 P1이 critical section에 들어가지 않는 동안 while문을 실행한다. P1도 마찬가지로 flag[1]을 true로 설정하고, turn을 0으로 설정한 후, P0이 critical section에 들어가지 않는 동안 while문을 실행한다.
 이 알고리즘은 상호 배제를 보장한다. 만약 P0이 critical section에 들어가고 있으면 flag[0]은 true이므로 P1은 while문에서 무한루프에 빠지게 된다. 마찬가지로 P1이 critical section에 들어가고 있으면 flag[1]은 true이므로 P0은 while문에서 무한루프에 빠지게 된다.

동기화 하드웨어(Synchronization Hardware)

 Peterson의 해결법을 구현할 간단한 도구 "lock", 최신 기계는 특별한 원자(Atomic) 하드웨어 명령을 제공합니다.(원자성 = 인터럽트 불가능) 메모리 워드와 설정 값을 테스트하거나 두 메모리 워드의 내용을 교환한다.

 TestAndSet 명령어는 해당 변수의 값을 원래 값으로 반환한 후, 해당 변수를 참으로 설정한다. 공유 부울 변수 lock이 FALSE로 초기화된다

 스왑(swap) 명령어는 두 변수의 값을 서로 바꾼다. 공유 부울 변수 lock이 FALSE로 초기화된다. 각 프로세스에는 로컬 부울 변수 키가 있다.

 여기서 TestAndSet 명령어와 스왑 명령어은 공유 변수를 원자적으로 변경하기 위해 사용된다. 각 프로세스는 로컬 변수를 사용하여 자신이 자원에 접근하는 것을 표시하고, TestAndSet 명령어를 사용하여 잠금을 획득하고자 시도한다. 그러나, 두 프로세스가 동시에 TestAndSet 명령어를 사용하여 잠금을 획득하려고 시도하는 경우 경쟁 상태가 발생할 수 있다. 이를 방지하기 위해 Peterson's Solution은 두 개의 프로세스가 번갈아 가며 자원에 접근하도록 보장한다.

---

세마포(Semaphore)

 세마포 S는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait() 및 signal()로만 접근할 수 있다. wait() 대신 P()로, signal() 대신 V()라고도 한다.

세마포의 사용

 두 개의 프로세스 Pi와 Pj와 두 개의 임계 영역 A와 B가 있다. S를 1로 초기화한다.

세마포는 0과 1 사이만 가능한 이진 세마포와 값의 제한이 없는 카운팅 세마포로 구분한다.

세마포 구현(Semaphore implementation)

 바쁜 대기(Busy waiting, spinlock)는 공유 자원에 접근하기 위해 기다리는 프로세스가 일정 시간 간격으로 재시도를 수행하는 방법이다. 세마포는 프로세스들 사이의 동기화를 위해 사용되는데, 이때 프로세스가 세마포를 기다리는 동안 세마포가 해제될 때까지 기다리는 것이 아니라, 일정 시간 간격으로 반복해서 세마포어가 해제될 때까지 계속 시도하는 방법이다.(CPU 사이클을 낭비)

 Block 및 wakeup

 프로세스가 실행을 시작하면 CPU 및 기타 시스템 리소스를 할당받아 실행된다. 하지만 이러한 프로세스가 다른 작업이나 이벤트를 기다리고 있을 수 있다. 예를 들어, 파일을 읽고 쓰거나 다른 프로세스에서 전송된 메시지를 수신하고 처리하는 경우가 있다. 이러한 상황에서는 해당 이벤트가 발생하기를 기다리며 프로세스가 블록(Block)된다. 블록 된 프로세스는 CPU나 시스템 리소스를 사용하지 않으며, 대기 상태에 있다. 이는 다른 프로세스가 리소스를 사용할 수 있게 하는 동시에 시스템 자원을 효율적으로 활용하는데 도움이 된다.
 웨이크업(Wakeup)은 블록 된 프로세스를 다시 실행 가능한 상태로 바꾸는 것을 말한다. 이벤트가 발생하거나 다른 프로세스의 작업이 완료될 때, 해당 이벤트를 기다리고 있는 블록 된 프로세스를 깨워서 다시 실행 가능한 상태로 만든다.

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

 두 개를 비교하자면 Busy-waiting은 문맥 교환이 필요하지 않고 임계 구역의 길이가 짧을 때 좋다. Block-wakeup은 문맥 교환이 필요하지만 임계 구역의 길이가 길면 좋다.

---

핵심

• 경쟁 조건은 여러 프로세스가 동시에 공유 데이터에 액세스 하고 조작하는 상황이다.
• 임계구역(Critical Section)은 공유 데이터에 액세스 하는 코드 구역(segment)이다.
• 세마포 S는 P() 및 V() 연산을 통해서만 액세스 할 수 있는 정수 변수이다.
• Busy-Waiting은 짧은 Critical Section에 좋고, Block-Wakeup은 긴 Critical Section에 좋다.