프로세스 동기화

경·2022년 7월 9일

운영체제

1. 프로세스(Process)

프로그램
- 어떤 작업을 하기 위해 실행할 수 있는 파일 또는 프로그램
프로세스
- 프로그램이 메모리에 적재되어 CPU자원을 할당받아 실행 중인 상태
- 운영체제로 부터 자원을 할당받는 작업 단위
스레드
- 할당받은 자원을 이용하는 실행의 단위
멀티 태스킹
- OS를 통해 CPU의 자원을 프로세스 또는 스레드 간에 나누는 행위
Context Switching(문맥 교환)
- 하나의 프로세스가 CPU를 사용중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 이전의 프로세스를 보관하고 새로운 프로세스를 적재하는 작업, 스케줄러에 의해 발생한다.

프로세스의 상태

new: 프로세스가 생성되는 상태
ready: 프로세스가 CPU에 할당되어, 처리되기를 기다리는 상태
running: 프로세스가 CPU에 할당되어, 명령어들이 실행되는 상태
waiting(Blocked): 이벤트 발생으로 프로세스가 기다리는 상태
terminated: 프로세스가 종료되는 상태

프로세스 동기화(Synchronization)

동기화 오류
두 개 이상의 프로세스가 공유 데이터(shared data)에 동시접근하게 되면 data inconsistency(데이터 모순성)이 발생할 수 있다.
Race Conditions: 경쟁 상태
두 개 이상의 프로세스가 공통 자원을 병행적으로 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이뤄졌는 지에 따라 결과가 같지 않고 달라지는 상황을 말한다.
Critical-Section: 임계구역
두 개 이상의 프로세스/스레드가 동시에 접근해서는 안 되는 공유자원에 접근하는 코드를 의미한다.
문제 해결을 위한 조건

Mutual Exclusion: 상호 배제
: 공유데이터에 접근중인 프로세스가 있을때 다른 프로세스는 공유데이터에 접근할 수 없다.
Progress: 진행
: 공유데이터에 접근중이지 않을때 접근하고자 한다면 공유데이터에 접근할 수 있어야한다.
Bounded Waiting: 한정 대기
: 공유데이터에 접근 요청을 한 후 부터 요청이 허용될 때 까지의 시간의 제한이 있어야한다.

문제 해결

1. Mutex: 뮤텍스

동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘

임계구역을 가진 프로세스들의 실행시간이 서로 겹치지 않고 단독으로 실행 되도록 하는 기술
한 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제 기법

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

프로세스가 임계구역에 들어갈때 lock을 확인한다.
lock이 0이라면 프로세스는 lock을 1로 바꾸고 실행한다.
종료되면 lock을 0으로 변경한다.
lock이 1이라면 프로세스는 lock이 0으로 바뀔때까지 기다린다.

2. Semaphore

멀티 프로그래밍 환경에서 공유된 자원에 대한 접근을 제한하는 방법

공유자원의 접근할 수 있는 프로세스의 최대 허용치가 존재
공유 자원에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근할 수 있다.
두가지 타입이 존재한다.
- Counting semaphore
  : 자원이 여러개여서 0이상의 정수값으로 사용하는 경우, 주로 resource counting에 사용한다.
- Binary semaphore(=Mutex)
  : 자원이 하나인 경우, 0또는 1만을 가지고 한다.

P(S):
	while(s<=0);
    S--;
V(S):
    S++;

P를 사용해 남는 자원이 있을 경우 해당 자원을 받아 실행하고,
실행이 완료되면 V를 사용해 자원을 반납한다.
남는 자원을 확인하는 과정에서 busy-wait(spin lock)이 발생한다.

typedef struct
{
	int value;			//semaphore
    struct process *L;	//Process wait queue
} semaphore;

P(S):
	S.vlaue--;
    if(S.value<0){
    	add this process to S.L;
        block();
    }
V(S):
	S.value++;
    if(S.value<=0){
    	remove a process P from S.L;
        wakeup(P);
    }

busy-wait을 막기 위해 Block/Wawkeup 방식을 사용한다.
P에서 사용할 수 없는 자원이 없을 경우 해당 프로세스를 L에 연결한 뒤 block 된다.
다른 자원이 프로세스를 끝내고 자원을 반납할때 기다리는 프로세스가 있을 경우 그 프로세스를 꺼내 실행한다.

Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 이벤트를 무한이 기다리는 현상
P0 => P(S); P(Q); ... V(S); V(Q);
P1 => P(Q); P(S); ... V(Q); V(S);
Starvation : 서로 다른 프로세스가 필요한 자원을 가지고 있어 큐에서 빠져나갈 수 없는 현상

Semaphore의 문제점

코딩하기가 어렵다.

정확성의 입증이 어렵다.

자발적 협력이 필요하다.

한번의 실수가 모든 시스템에 치명적 영향을 미친다.

ex)
V(mutex); critical section; P(Mutex); => Mutual exclusion이 깨짐
P(mutex); critical sectionl P(mutex); => Deadlock

3. Monitor: 모니터

Semaphoer의 단점을 해결
ADT(Abstract Data Type)의 안전한 High Level Synchronization Construct
프로그래머가 정의한 함수에 Mutual exclusion을 제공한다.
모니터 내에서는 하나의 프로세스만 실행할 수 있다.
Condition variale(조건변수)가 있어서 코드 실행 중 충족이 되지 않아 오래 걸릴 경우 조건에 따라 조건변수를 사용해 잠들게 할 수 있다.

동기화 관련 여러 문제들

1. The Bounded-Buffer Problem

Producer 프로세스와 Consumer 프로세스가 존재하며 하나 이상이 존재할 수 있다.
생산자는 데이터를 반들어 버퍼에 삽입하고, 소비자는 버퍼에서 데이터를 꺼내는 역할을 한다.
발생할 수 있는 문제
- 생산자 두개가 동시에 도착해 비어있는 버퍼에 데이터를 넣을 경우
- 소비자 두개가 동시에 도착해 데이터를 빼는 경우
- 버퍼가 유한하기때문에 생기는 문제로 생산자가 모든 데이터가 채워진 후에 다시 도착해 데이터를 넣고자 할 경우 또는 채워진 데이터가 없는데 소비자가 데이터를 원할 경우

2. Readers-Writers Problem

데이터를 읽기만 하는 Reader 프로세스와 데이터를 읽고 수정하는 Writer 프로세스가 존재한다.
Reader가 도착하면 lock없이 데이터를 읽을 수 있어야하며, Writer가 도착하면 오로지 Writer만 데이터에 접근할 수 있어야한다.
Reader가 한번에 많이 들어올 경우 Writer 이 계속 접근하지 못할 수 있다.

3. Dining-Philosophers Problem

교착상태의 대표적인 예제
- 상호배타 : 젓가락은 한번에 한 철학자만 사용할 수 있다.
- 보유 및 대기 : 집어든 젓가락은 계속 들은 채로 사용중인 반대쪽 젓가락을 기다린다.
- 비선점 : 이미 누군가 집어든 젓가락을 뺏을 수 없다.
- 환형대기 : 모든 철학자들이 자신의 오른쪽에 앉은 철하자가 젓가락 놓기를 기다린다.