7. 프로세스 동기화(1)

1. 동기화(Synchronization)란

협력하여 실행되는 프로세스들은 실행 순서와 자원의 일관성을 보장해야 하기에 반드시 동기화 되어야 한다.

즉, 프로세스 동기화란 프로세스들 사이의 수행 시기를 맞추는 것을 의미한다.

• 실행 순서 제어: 프로세스를 올바른 순서대로 실행하기
• 상호 배제: 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기

+) 스레드도 동기화 대상이다. 

1) 실행 순서 제어를 위한 동기화

동시에 실행되는 프로세스를 올바른 순서대로 실행하는 것

2) 상호 배제를 위한 동기화

상호배제는 공유 불가능한 자원의 동시 사용을 피하기 위한 것. e.g. 생산자-소비자 문제 

 

2. 배경

생산자-소비자 문제에서 생산자와 소비자 프로세스는 공유메모리를 이용하여 공통된 변수와 버퍼를 공유한다. 

각각의 프로세스를 독립적으로 수행하면 올바르게 동작하지만, 공유 변수의 값이 결과에 영향을 주기에 병행으로 수행되면 실행되는 순서에 따라 올바르게 동작하지 않을 수 있다.

또한 파이썬과 같은 고급 프로그래밍 언어의 한 문장은 컴파일러에 의해 여러 개의 기계 명령어로 번역되기에 우리가 봤을때는 한 문장이여도 컴퓨터내부적으로는 여러 줄을 의미할 수 있다. 따라서, 인트럽트는 한 기계 명령어의 명령어 주기가 끝난 시점에 처리된다.

변수 counter에 대해 기계적으로 뜯어보자. register1, register2는 CPU 내부 레지스터를 의미한다.

• 생산자가 counter ++

register1 = counter;
register1 = register1 + 1;
counter = register1;

• 소비자가 counter - -

register2 = counter;
register2 = register - 1;
counter = register2;

초기 counter의 값이 5라고 하자.

이때 병행 수행의 결과로 다양한 상황이 생길 수 있다. 예를들어

T0 : 생산자 register1 = counter;          {register1 = 5, counter = 5 }
T1 : 생산자 register1 = register1 + 1;    {register1 = 6, counter = 5 }
T2 : 소비자 register2 = counter;          {register2 = 5, counter = 5 }
T3 : 소비자 register2 = register2 - 1;    {register2 = 4, counter = 5 }
T4 : 생산자 counter = register1;          {counter = 6 }
T5 : 소비자 counter = register2;          {counter = 4 }

이처럼 병행으로 수행되는 여러 프로세스가 공통된 데이터를 조작할 때 결과가 접근 순서에 의해 결정되면 경합 상태, 경쟁 조건(race condition)이 존재한다고 한다.

race condition이 발생하면 생산자 소비자 문제처럼 데이터의 일관성이 깨지는 문제가 발생한다.

여러 프로세스가 병행으로 수행되어 발생하는 문제를 해결하는 것을 프로세스 동기화라 한다.

 

3. 임계 구역 문제

공유 자원: 전역 변수, 파일, 입출력장치, 보조기억장치 . 등두 . 개이상의 프로세스를 동시에 실행하면 문제가 발생하는 자원

임계 구역(critical section): 프로세스의 "코드"의 일부분으로서, 다른 프로세스와 공동으로 사용하는 변수, 테이블, 파일 등을 변경하는 부분

임계 구역의 실행은 상호배타적(mutually exclusive)으로 실행되어야 한다. 이 말은 한 프로세스가 임계 구역 실행시에 다른 프로세스는 임계 구역에 진입할 수 없어야 함을 말한다.

한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역 밖에서 기다려야 하며, 임계구역에 들어간 프로세스가 나와야 밖에 있던 프로세스가 들어갈 수 있다.

이에 따라 각 프로세스는 임계구역 진입 전에 허가가 필요하다.

이때 이 허가를 요청하는 코드를 진입 구역 (entry section)이라 하고,

허가를 받아 임계구역을 실행한 후에는 다른 프로세스들이 진입할 수 있도록 해야하며, 이 코드를 출구 구역 (exit section) 이라 한다.

진입 구역, 임계 구역, 출구 구역을 제외한 코드를 잔류 구역(remainder section)이라 한다.

init
진입조건( Entiry code )
    Critical Section
출구( Exit code )
Remainder section

임계 구역 문제를 해결하는 메커니즘은 3가지 요건이 모두 충족되어야 한다.

• 상호 배제(mutual exclusive = mutex): 한 프로세스가 임계구역에서 실행하고 있으면 어떤 프로세스도 임계 구역에 진입할 수 없어야 한다. 
• 진행(progress): 임계 구역을 실행하고 있는 프로세스가 없을 때, 몇 개의 프로세스가 임계 구역에 진입하고자 하면 이들의 진입 순서는 이들에 의해서만 결정되어야 한다. 또한 이 결정이 무한정 연기되어서는 안된다. 
• 한계 대기(bounded waiting): 한 프로세스가 자신의 임계 구역에 진입하고자 요청을 한 후부터 이 요청이 허용될 때까지 다른 프로세스가 그들의 임계 구역에 진입할 수 있는 회수가 제한되어야 한다.

특히 상호 배제는 정말 중요하다.

 

두개의 프로세스가 있다고 가정하자 P0. P1

아래는 프로세스들의 일반적인 구조

do {
    entry section //lock
    critical section
    exit section //unlock
    remainder section
} while (1);

 

4. 임계 구역 문제 해결 알고리즘

 

Algorithm 1

Synchronization variable

int turn; //turn = 누구차례인가
initially turn = 0; // Pi can enter its critical section if(turn == i)

 

 

Process P0

do {
    while (turn != 0);	   //0이 아니면 1번 차례 -> 기다림
    critical section
    turn = 1;           //이제 1번차례로 변경해줘
    remainder section
} while (1);

Process P1

do {
    while (turn != 1);
    critical section
    turn = 0;
    remainder section
} while (1);

이 알고리즘의 문제점은 mutual exclusion 만족 / progress 만족 x

 

Algorithm 2

Synchronization variable

boolean flag[2];             // 2개의 flag를 가진다 (본인이 cs에 들어감을 말한다)
initially flag[모두] =false;

Process Pi

do {
    flag[i] = true;        //Pretend I am in
while (flag[j]);           //안에 누군가 있나? 있으면 기다린다
    critical section
    flag[i] = false;       //Pretend I am out
    remainder section
}while (1);

 

이또한 mutual exclusion은 만족 / progress 만족 x 

프로세스 A가 임계 구역에 들어가기 위해 flag를 true로 바꾼 시점에 context switching이 발생하여 프로세스 B에게 CPU가 넘어가면, 프로세스 B도 flag를 true로 바꿨는데 다시 context switch가 발생하여 프로세스 A가 CPU를 잡는다면 어느 누구도 임계구역에 들어갈 수 없게 된다.

 

Algorithm 3 (Peterson's Algorithm)

Combined synchronization variables of algorithms 1 and 2  -> flag, turn 모두 사용

do {
    flag[i] = true; // 내가 임계 구역에 들어갈게
    turn = j;	// 상대방 turn으로 변경
    while (flag[i] && turn == j); //2가지를 모두 만족하는지 확인
    critical section
    flag[i] = false;
    remainder section
}while (1);

상대방이 임계 구역에 들어가 있지 않고, 들어갈 준비도 하지 않으면 내가 들어가겠다는 내용

임계 구역 해결 위한 3가지를 모두 만족하지만, Busy Waiting(=Spin lock)이 발생한다. 이는 CPU와 메모리를 쓰면서 기다리는 것을 의미한다.

즉, 임계 구역에 들어가기 위해 상대방이 CPU를 가지고 flag 변수를 false로 바꿔야 하는데, 내가 CPU를 잡고 있는 상황임에도 상대방은 의미없이 while문을 계속 돌며 CPU 할당 시간을 낭비하는 것이다.

 

5. 하드웨어적 방법

 

임계구역 문제가 발생하는 이유는 데이터를 읽고 쓰는 동작이 하나의 명령어가 아니기 때문이다.

따라서 이 명령어들을 하나로 만드는 작업을 하면 된다. 명령어 하나만으로  atomic하게 데이터를 읽고 쓰는 것을 하면 해결 가능하다.

 

Test & Set

Synchronization variable

booleanlock = false;

Process Pi

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

매개변수를 읽고, 그 변수를 1로 바꿔주는 역할을 한다.

lock이 0이라면, while문을 탈출하고 lock이 1이 된다. lock이 1이라면, while문을 돌고 lock은 그대로 1이된다.

 

reference

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

운영체제

https://www.aladin.co.kr/shop/wproduct.aspx?isbn=K932838038?utm_source=search_ad&utm_medium=google&utm_campaign=bestbook&gad_source=1&gclid=CjwKCAjw9IayBhBJEiwAVuc3fp1JhpHBLi2oiRQsxeoBd0Di-mOgUB2T_-0BMVw749rwhT8XHIO1jRoCiqMQAvD_BwE