9. Process Synchronization 1

KOCW 반효경 교수님 운영체제 강의 정리
이 글은 공부한 것을 복습 및 기록하기 위한 게시물입니다.
잘못된 정보가 기입되어 있을 수 있으니 주의해주시기 바랍니다.
강의 링크 : http://www.kocw.net/home/cview.do?lid=aa53d6aa576466ee, http://www.kocw.net/home/cview.do?lid=5cf910642999f4a5

1. 데이터의 접근 - Race Condition

데이터를 Meomory에서 가져와 CPU에서 연산한 후 데이터의 결과를 Memory에 저장하게 된다.
이떠 CPU가 1개일 경우에는 문제가 발생하지만 Memory는 1개인 상황에서 CPU가 여러개일 경우 문제가 발생하게 된다.
이 문제를 Race Condition이라 한다.

Race Condition(경쟁 조건)은 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과 값에 영향을 줄 수 있는 상태를 뜻한다.

Race Condition은 멀티프로세서 뿐만 아니라 공유 메모리를 사용하는 프로세스들 간에서도 자주 발생한다.
또한 CPU가 1개이더라도 커널에서는 시스템 콜이 여러개가 오게될시 Race Condition이 발생하게 된다.

2. OS에서의 Race Condition

OS에서의 Race Condition이 발생하는 경우는 크게 3가지다.

• Kernel 수행 중 Interrupt 발생 시
• Process가 System call을 하여 Kernel mode로 수행 중인데 context switch가 일어나는 경우
• Multiprocessor에서 Shared Memory 내의 kernel data

2-1. Kernel 수행 중 Interruppt 발생 시

위 예시에서 Kernel에서 Count 변수 값을 증가시키고 Interrupt handler가 Count 변수를 감소시켜 Count값이 변화가 없어 보이지만 실제로는 Interrupt handler의 결과 값이 반영되지 않게 된다.
왜냐하면 Kernel에서 이미 Interrupt handler가 들어오기 전에 Count 변수 값을 저장해놨다가 변수 값을 증가시키고 저장하기 때문이다.

그래서 해당 문제에 대한 해결 방법으로는 Kernel에서 특정 작업을 진행중일 때는 Interrpt를 disalbe 시킨 후 작업이 완료되면 Interrupt를 enalbe시켜주는 방법이 있다.

결국에는 처리 순서를 정해주면 해결되는 문제이다.
그러나 무작정 Interrupt를 막게 되면 CPU가 비효율적으로 돌아가는 일이 초래될 수 있다.

2-2. Process가 System call을 하여 Kernel mode로 수행 중인데 context switch가 일어나는 경우

이번 예제 또한 2-1과 마찬가지로 '프로세스A'가 Count 변수를 이미 Load 했기 때문에 '프로세스B'에서 작업한 Count++은 반영되지 않고 '프로세스A'에서의 Count++ 작업만 저장이 된다.

이러한 문제의 해결방법으로는 프로세스가 커널 모드에 있을 때 CPU 할당 시간이 끝나도 CPU를 박탈당하지 않게 하는 것이다.
이 방법을 사용할 시 CPU 할당시간이 제대로 지켜지지 않게될 수 있지만 RTOS가 아닌 시분할 동작이기 때문에 큰 문제가 발생하지는 않는다.

2-3. Multiprocessor에서 Shared Memory 내의 kernel data

이전 예제(2-1, 2-2)들은 CPU가 1개일 때 프로세스 혹은 커널이 뭔가를 작업하던 중 CPU 소유권이 넘어갔기 때문에 발생하는 문제이지만 이번 예제는 근본적으로 작업 주체인 CPU가 여럿일 경우에 발생하는 문제이다.

이번 문제의 해결방법은 2가지가 있다.

• 첫번째, 커널 전체를 lock을 해준 후 작업이 완료되어 커널을 빠져나올 때 unlock을 해주는 것이다. 즉, 한번에 하나의 CPU만 커널에 들어갈 수 있게 하는 것이다.
• 두번째, 커널 내부에 있는 각 공유데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법이 있다.

당연히 1번 방법은 커널 전체를 lock하는 것으로 매우 비효율적이다.

3. 프로세스 동기화(Process Synchronization)문제

• 공유 데이터(Shared data)의 동시 접근(Concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다.
• 일관성(Consistency) 유지를 위해서는 협력 프로세스(cooperating process)간의 실행 순서(orderly execution)를 정해주는 매커니즘이 필요하다.

Race Condition을 막기 위해서는 Concurrent process는 동기화(Synchronize)되어야 한다.

4. Critical-Section Problem

Critical Section이란 공유 데이터를 접근하는 코드를 의미한다.
만약 위 사진과 같이 P1에서 Critical Section이 실행 중일 때 CPU가 P2로 넘어가게 되면 P2의 Critical Section은 실행하지 않고 기다리고 있어야 한다.

4-1. Initial Attempts to Solve Problem

위 사진은 S/W로 코드를 넣어 Critical Section을 해결하는 방법이다.
프로세스는 공유 데이터에 접근하는 코드(Critical Section)와 공유 데이터에 접근하지 않는 코드(remainder section)로 반복되어 구성될 것이다.
공유 데이터를 접근하는 코드(Critical Section)이전에 entry section을 통해 일종의 lock을 걸어줄 것이며 exit section을 통해 unlock을 시켜줄 것이다.

5. 프로그램적 해결법의 충족 조건

프로그램적 해결법의 충족 조건은 3가지가 있다.

• Mutual Exclusion - 배타적 접근
• Progress - 둘이 동시에 들어가는 것을 막고자 하다보니 Critical Section에 아무도 있지 않은 상태에서 들어가지 못하는 상황이 발생할 수 도 있다.
• Bounded Waition - Critical Section을 대기할 때 Starvation이 일어나지 않게 해야한다.만약 3개의 프로세스가 Critical Section을 사용하는데 2개의 프로세스만 서로 번갈아 가면서 사용하고 1개의 프로세스는 무한적으로 대기할 때 Bounded Waiting을 만족하지 못하는 상황이 발생하게 된다.
  
  

고급 언어의 문장들이 단일 Instruction이 아니기 떄문에 Critical Section 코드를 수행하는 도중에 CPU의 소유권을 빼앗겨서 발생하는 문제들이다.

5-1. Algorithm 1

turn 변수를 이용하여 프로세스의 순서를 정해준다.
turn이 자기 차례일 때는 Critical Section안으로 들어가고 나올 때 turn의 변수 값을 바꿔준다.
다른 프로세스는 turn이 자기 차례가 되지 않았을 때 While문이 돌아가고 있기 때문에 계속해서 대기를 하게 된다.

알고리즘 1은 충족 조건중 Mutual Exclusion은 만족하지만 Progress는 만족히자 못한다.
알고리즘 1은 무조건 한 프로세스가 Critical Section에 들어갔다 나와야 하는 교대형식의 코드이다.
프로세스들이 Critical Section에 들어가려는 빈도가 빈번하지 않을 수 있다.
만약 프로세스A는 Critical Section에 빈번하게 접근을 해야하는데 프로세스B는 그렇지 않다고 한다면 프로세스A는 Critical Section에 접근하지 못하는 상황이 발생하게 된다.

5-2. Algorithm 2

알고리즘 1의 문제를 보완하여 나온 것이 알고리즘 2이다.
flag 배열 변수를 사용한다.
자신의 flag 변수를 true로 만들어 주고 상대방의 flag 변수가 true이면 대기를 하게 되고 false이면 Critical Section에 접근하여 작업한 후 자신의 flag 변수를 false로 만들어 준다.

그러나 알고리즘 2 또한 문제가 있다.
프로세스A가 flag를 true로 바꾼 상태에서 프로세스B에게 CPU가 넘어가게 되면 프로세스B 또한 자신의 flag를 true로 바꾸게 된다. 이렇게 되면 두 프로세스 모두 Critical Section에 들어가지 못한 상태로 무한 대기를 하게 된다.
Progress를 만족하지 못한다.

5-3. Algorithm 3(Peterson's Algorithm)

알고리즘 3은 피터슨 알고리즘이다.
flag와 turn 변수를 둘다 사용하게 된다. 피터슨 알고리즘은 3가지 충족 조건을 모두 만족한다.


그러나 Busy Waiting(spin lock)문제가 발생할 수 있다.
프로세스A가 계속해서 Critical Section에 접근한 상태에서 프로세스B로 CPU가 할당이 된다면 프로세스B는 접근하지 못하고 계속해서 자신의 CPU 할당 시간 동안 무한대기를 하게 되어 효율적인 동작을 하지 못한다.

5-4. Synchronization Hardware

H/W적으로 Critical Section 문제는 쉽게 해결될 수 있따.
결국 Critical Section문제는 데이터를 메모리에서 읽는 것과 쓰는 것을 하나의 instruction으로 실행할 수 없기 때문에 발생하는 문제이다.

위 문제를 해결해줄 Instruction으로 Test_and_set(a)가 있다.
Test_and_set(a)은 a라는 값을 읽고 a를 1로 바꿔주는 것을 하나의 instruction으로 실행해주는 것이다.
Test_and_set(a)이 지원된다면 코드로 복잡하게 알고리즘을 구현할 필요가 없다.