프로세스 동기화 문제에 관하여

프로세스 동기화 문제란

프로세스 동기화 문제란 공유 데이터의 동시 접근이 발생하는 경우에는 데이터의 불일치 문제를 발생시킬 수 있는 것을 말합니다.

 

일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요하게 됩니다.

 

동기화 문제의 예시를 들어 보겠습니다.

1. 특정 공유데이터 x = 1 가 있다고 가정합니다.

2. 해당 공유데이터는 프로세스 A, B가 공유합니다.

2; 먼저 한 프로세스 A가 해당 공유데이터를 읽어들이면 x = 1 을 읽어오게 됩니다.

3. 그리고 그 상태에서 interrupt가 발생하여 CPU를 다른 프로세스 B가 점유하게 되었습니다.

4. 그리고 프로세스 B가 공유 데이터에 x += 1 명령을 수행해서 x = 2 가 되었습니다.

5. 그리고 다시 프로세스 A가 CPU를 점유하게 됩니다.

6. 프로세스 A는 이미 X를 읽어오는 인스트럭션을 실행하였기 때문에 여전히 X = 1 입니다.

7. 따라서 이후의 작업을 수행할 때, x 가 갱신된 사실을 모르고 작업을 수행하므로 원치 않은 결과가 나오게 됩니다.

 

이러한 결과를 통해 발생하는 문제를 Race condition이라고 합니다.

 

여러 프로세스들이 동시에 공유 데이터를 접근하는 상황에서는 데이터의 최종 연산 결과가

 

마지막에 그 데이터를 다룬 프로세스에 따라 달라지는 것을 말합니다.

 

Critical-Section Proble

공유 데이터를 접근하는 코드를 critical section 이라고 합니다.

 

여러 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 상황에서,

 

하나의 프로세스가 Critical-Section 에 있을 때에는 다른 프로세스가 Critical-Section에 들어가지 못하도록 제어해야 합니다.

 

 

Critical Section의 규칙

 

Critical-Section에 대한 접근을 잘 제어하기 위해서는 다음과 같은 규칙들이 존재합니다.

1. Mutual Exclusion (상호 배제)
   • 배타적으로 접근해야 한다는 것을 말합니다.
2. Progress (진행)
   • 아무도 크리티컬 섹션에 있지 않은 상태에서는 크리티컬 섹션에 들어가고자 하는 프로세스가 있으면 들어가게 해줘야 한다는 것을 말합니다.
   • 동시 접근을 통해 에러가 발생해서 둘다 접근하지 못하게 되는 경우를 잘 처리해야 한다는 것을 의미합니다.
3. Bounded Waitin (유한 대기)
   
   • 프로세스가 Critical Section에 들어가려고 요청한 이후부터 요청이 허용될 때까지, 다른 프로세스들이 크리티컬 섹션에 들어가는 횟수에는 한계가 있어야 함을 말합니다.
   • 특정 요소들이 돌아가면서 크리티컬 섹션을 돌아가면서 독차지해서, 다른 프로세스가 Starvation 발생하는 경우를 방지해야 함을 의미합니다.

 

동기화 알고리즘

피터슨의 알고리즘

do
{
	flag[i] = true;
    	turn = j;
    	while (flag[j] && turn == j);
    	critical section
    	flag[i] = false;
    	remainder section
} while(1);

턴과 플래그를 사용하여 동기화를 제어하는 알고리즘입니다.

 

우선 자신의 플래그를 true로 설정하고 턴을 상대방 으로 설정합니다.

 

상대방이 플래그를 true로 설정하고, 상대방 턴일 경우에는 대기합니다.

 

그게 아니라면 크리티컬 섹션에 접근을 수행합니다.

 

해당 알고리즘은 중간에 CPU를 빼앗기게 되어도 Critical Section의 세 규칙을 만족할 수 있습니다.

 

하지만 해당 알고리즘도 문제점은 존재합니다.

 

만약에 프로세스가 CPU를 점유하게 되었는데, 크리티컬 섹션은 다른 프로세스가 차지하고 있다면, 프로세스는 자신의 CPU 할당 시간만큼

 

의미없게 대기만 하면서 CPU 시간을 낭비하게 될 수 있습니다.

 

 

동기화 하드웨어

do
{
	while(Test_and_Set(lock));
    	critical section
    	lock = false;
        remainder section
}

이러한 동기화 문제를 하드웨어 적으로 하나만 주어지면 해당 문제를 쉽게 해결할 수 있습니다.

 

읽기와 쓰기를 하나의 instruction으로 동시에 처리할 수 없다는 것이 동기화 문제의 핵심인데,

 

하나의 instruction으로 이를 해결할 수 있다면 이 문제를 해결할 수 있을 것입니다.

 

해당 예시에서 Test_and_Set은 읽기와 쓰기를 하나의 instruction으로 처리한다고 가정합니다.

 

그러면 lock을 통해 lock이 false이면 크리티컬 섹션에 들어가고, 아니면 대기합니다. 

 

 

 

출처

KOWS 운영체제 - 반효경 교수님 - Process Synchronization 1, 2

http://www.kocw.net/home/search/kemView.do?kemId=1046323