운영체제 스터디 6주차 - 동기화

Background

프로세스들이 concurrent하게 데이터에 접근하여 수정을 할 경우 데이터 정합성(Data Inconsistency - 어떤 데이터들의 값이 서로 일치함)가 깨질 수도 있다. 서로 협력하는 프로세스의 요청들을 순서대로 처리해주는 것을 보장해줘야지 데이터의 정합성을 보장하는 것이 가능.

 

데이터의 무결성(Integrity of Data)도 고려해줘야 하는데 아래와 같은 환경이기 때문

1) 동시(Concurrent) 처리를 하는 경우: Instruction stream 중간의 어느 포인트에서 인터럽트가 발생해 컨텍스트 스위칭이 발생할지 모르고, 멀티 코어 프로그래밍을 하는 경우 컨텍스트 스위칭되었다고 하더라도 다른 코어에서 해당 프로세스를 할당하여 처리할 수도 있음

2) 병렬(Parallel) 처리를 하는 경우: 두 개 이상의 instruction stream이 동시에 다른 프로세싱 코어에서 처리되면서 데이터를 다룸

 

어떤 버퍼에 1씩 더하는 프로듀서와 해당 버퍼에서 1씩 빼가는 컨슈머가 있다고 했을 때, 이 프로듀서와 컨슈머를 concurrent하게 실행시키면 결과 값이 매번 다르게 나오는 상황 발생. 같은 물리적 공간을 가진 레지스터를 이용하지만, 그 레지스터를 이용할 때 컨텍스트 스위칭되는 시점에 따라 조금씩 값이 달라지는 것(값을 빼기전에 스위칭되어버리고 거기에 +1 해버리고 이런 상황)

 

이렇게 여러 개의 프로세스(혹은 스레드)가 같은 혹은 공유하고 있는 데이터를 동시적으로 접근하여 조작하는 상황을 경쟁 상황(Race Condition)이라고 함. 이럴 경우 처리되는 순서에 따라 결과 값이 달라지는 현상이 발생함. 어떤 데이터의 조작을 한 번에 한 번씩만 가능하도록 보장한다면 즉 프로세스(혹은 스레드) 동기화를 통해 이 상황을 해결할 수 있음.

 

 

The Critical Section Problem

임계영역(critical section)이란 데이터에 접근하고 업데이트하는 코드 영역을 말함. 그렇다면 이 임계영역을 처리하고 있는 동안에는 하나의 프로세스만 이 처리를 할 수 있도록 보장하게 해야 함. 그렇게 한다면 공유된 데이터에 대해서 프로세스 동기화가 자동으로 실현될 수 있음. 코드를 critical-section 기준으로 나눠서 생각해볼 수 있음

• entry-section: critical-section에 진입한다는 것을 알려주는 영역
• critical-section: 데이터의 접근과 조작이 이루어지는 영역
• exit-section: critical-section이 끝났다는 것을 알려주는 영역
• remainder-section: 그 외 영역

 

 

Critical Section 문제를 해결하기 위에 아래 세 가지 요구 사항이 존재

• Mutual Exclusion: 하나의 프로세스가 임계영역을 점유하고 있으면 다른 프로세스는 접근할 수 없음
• Progress: 데드락을 피하기 위한 요소로, 너무 엄격하면 안 된다는 뜻 같음
• Bounded Waiting: 특정 프로세스가 계속해서 임계영역 접근 권한 획득에서 밀리는 기아 현상을 피하기 위한 방법

→ 세 가지를 다 달성하기는 어려움. 따라서 Mutual Exclusion은 필수이지만, Progress와 Bounded Waiting은 경우에 따라 하나만 지켜지는 경우도 있는 것 같음.

 

싱글 코어 환경에서는 그냥 임계영역 처리 때 인터럽트가 안 발생하게 하는 방법도 있을 수 있음. 하지만 멀티 프로세서 환경에서는 현실적으로 사용할 수 없음(효율이 너무 떨어져서 멀티 프로세싱이나 멀티 스레딩을 쓰는 장점이 사라짐) 

 

보통은 선점형과 비선점형 방법이 있음.

• 비선점형 커널: 커널 모드 프로세스가 자발적으로 점유를 포기할 때까지 기다리게 하는 것 → 하지만 효율성이 떨어짐
• 선점형 커널: 커널 모드 프로세스의 점유를 강제로 뺐는 것. 디자인하기 어렵지만 더 효율적으로 데이터 처리가 가능해서 보통 이거 씀

 

Peterson's Solution

임계 영역 문제를 해결하기 위한 소프트웨어 솔루션에는 Dekker 알고리즘, Eisenberg and McGuire의 알고리즘 등 여러 가지가 있음. 그 중에서 Peterson 알고리즘에 대해서 알아보겠음. Peterson 알고리즘은 flag와 turn을 이용해서 어떤 프로세스의 차례일 때는 그 프로세스만 critical section에 들어가서 작업하고 플래그를 넘기는 방식으로 진행.

 

 

 

C로는 아래와 같이 간단하게 구현 가능. 전역변수인 turn과 flag를 사용하면서 작업을 수행하는데 producer에서는  turn이 1, flag[0] = true 로 바꾸고, consumer에서는 turn을 0, flag[1]을 true로 바꾸고 각자의 critical section에 들어가게 된다.

#include ‹stdio.h›
#include ‹pthread.h›
#define true 1
#define false 0

int sum = 0;
int turn; 
int flag[2];

int main()
{
	pthread_t tid1, tid2;
    pthread_create(&tid1, NULL, producer, NULL); 
    pthread_create(&tid2, NULL, consumer, NULL);
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    printf("sum = %d\n", sum);
}

 

void *producer(void *param)
{
	int k;
	for (k = 0; k ‹ 10000; k++) { 
    	/* entry section */
        flag[0] = true;
        turn = 1;
        
        while (flag[1] && turn == 1);
        
        /* critical section */
        sum++;
        
        /* exit section */
        flag[0] = false;
        
        /* remainder section */
        }
	pthread_exit(0);
}

 

void *consumer(void *param)
{
	int k;
	for (k = 0; k ‹ 10000; k++) { 
    	/* entry section */
        flag[1] = true;
        turn = 0;
     	
        while (flag[0] && turn == 0);
        
        /* critical section */
        sum--;
        
        /* exit section */
        flag[1] = false;
        
        /* remainder section */
        }
	pthread_exit(0);
}

 

 

Peterson 알고리즘은 동기화 처리를 보장해주지 않으므로 완벽하지 않음. 그럼에도 불구하고 배우는 이유는 CSP(Critical Section Problem)를 해결하기 위해 좋은 예시이고, 무엇보다 mutual exclusion, progress, bounded waiting을 구현한다는 것을 증명 가능하기 때문에 이론적으로는 완벽함.

 

flag 변수만 사용할 경우의 문제 flag의 역할: 각 프로세스가 임계 구역에 진입하려는 의도를 나타냅니다. 프로세스는 임계 구역에 진입하기 전에 해당 flag를 true로 설정합니다. 문제점: 만약 두 프로세스가 거의 동시에 임계 구역에 진입하려고 하면, 두 프로세스 모두 자신의 flag를 true로 설정할 것입니다. 이 경우, 두 프로세스 모두 임계 구역에 진입할 수 있게 되어, 상호 배제(mutual exclusion)가 보장되지 않습니다. 즉, flag만 사용하는 경우 상호 배제를 충분히 보장할 수 없습니다. turn 변수만 사용할 경우의 문제 turn의 역할: 어느 프로세스가 임계 구역에 진입할 차례인지를 나타냅니다. 한 프로세스가 임계 구역에 진입할 때, 다른 프로세스는 turn이 자신에게 돌아올 때까지 기다려야 합니다. 문제점: 만약 한 프로세스가 임계 구역에 진입하지 않는다면 (예를 들어, 장시간의 계산을 수행하거나, 네트워크 지연 등으로 인해), 다른 프로세스는 무한히 기다려야 할 수 있습니다. 이것은 "기아 상태(starvation)"로 알려져 있으며, 특정 프로세스가 임계 구역에 진입하는 것을 무한히 지연시킬 수 있습니다. flag와 turn을 함께 사용하는 이유 상호 배제 보장: flag는 프로세스가 임계 구역에 진입하려는 의도를 나타내고, turn은 어느 프로세스가 임계 구역에 진입할 차례인지를 결정합니다. 이 두 변수를 함께 사용함으로써, 한 프로세스가 임계 구역에 있을 때 다른 프로세스가 진입하지 못하게 하여 상호 배제를 보장합니다. 기아 상태 방지: turn 변수는 임계 구역 접근 순서를 공정하게 조절합니다. 어느 한 프로세스가 임계 구역에 있지 않을 때 다른 프로세스가 기다리는 것이 아니라, turn에 따라 차례가 돌아오면 진입할 수 있습니다. 이는 한 프로세스가 무한히 기다리는 상황을 방지합니다. 결과적으로, 피터슨 알고리즘은 이 두 변수를 사용하여 상호 배제를 보장하면서도 프로세스 간 공정한 임계 구역 접근을 보장합니다. 이는 두 프로세스가 공유 자원을 안전하게 사용할 수 있게 하며, 동시성 문제와 기아 상태를 효과적으로 해결합니다.

 

 

Hardware Support for Synchronization

기계어로 변환하고 처리하는 과정에서 순서가 계속 꼬이고 있는 사실을 발견할 수 있다. 그렇다면 아예 하드웨어 단에서의 솔루션은 없을까? 메모리 배리어를 만드는 것도 있을 수 있고, 하드웨어 인스트럭션 자체를 atomic하게 만드는 방법도 있을 수 있음. atomic한 operation이라고 하는 것은 중간에 인터럽트가 발생할 수 없는 오퍼레이션. test_and_set()과 compare_and_swap()이라는 특별한 아토믹한 인스트럭션을 만들어서 사용하는 것을 가정해보자.

 

 

 

위 두 인스트럭션을 사용하여 코드를 짠다면 아래와 같은 형태로 될 수 있다

 

소프트웨어단을 만지는 사람들은 Atomic variable이라는 미리 만들어진 것들을 사용해서 구현할 수 있음. 이 변수를 이용하면 중간에 인터럽트가 발생시키지 않고 mutual exclusion을 온전히 구현할 수 있다.