[OS] 프로세스 동기화 (1)

위영민(Victor)·2021년 5월 17일

들어가기전에

데이터 접근방식

데이터에 대한 접근만 존재한다면, 크게 문제는 없음
But, 실제 프로그램에서는 기존의 데이터를 통한 연산작업이 훨씬 많음

Process Synchronization(프로세스 동기화)

왜 프로세스 동기화가 필요한가요 ?

결국, 공유하는 하나의 자원에 대해서, 여러 프로세스가 동시에 접근할 때 시간적인 차이로 생길 수 있는 데이터의 불일치문제가 존재할 수 있음

이러한 문제를 해결하고자 하는 것이 프로세스 동기화(Process Synchroniztion)이다.

Race Condition(경쟁조건)

정의

여러 프로세스들이 동시에 공유데이터에 접근하는 상황
데이터의 최종연산 결과가, 마지막에 그 데이터 연산을 한 프로세스에 의해 달라지는 현상

공유 메모리를 사용하는 프로세스들
커널 내부 데이터를 접근하는 루틴들 간에 경쟁조건 가능성이 존재함

일반적으로, 프로세스는 자기 주소영역에 데이터만 접근하므로, 동기화 문제가 발생하지 X
But, 본인이 수행할 수 없는 명령에 경우, OS에게 System call을 통해, 커널의 코드가 그 프로세스를 대신해서 명령을 수행함

커널의 코드가 실행 된다는 것 == 커널의 데이터의 접근한다는 것
그러한 경우, 경쟁조건이 발생한다면 ?

언제 OS에서 경쟁조건을 발생시키는가요 ?

1. Kernel 수행 중 인터럽트 발생 시 (CPU 1개)

문제점

Kernel 명령 수행중, Interrupt가 발생해서, Interrupt 처리루틴이 실행됌
결론적으로, count-- 는 적용되지 않고, count++ 만 적용됌

해결법

Kernel이 중요한 작업을 하는 동안, 다른 요청이 발생해도, 작업중인 동안에는 인터럽트 처리를 하지 못하도록 설정

2. Process가 System call을 하며, Kernel Mode로 수행 중 Context Switch가 일어나는 경우

이상적인 방식

문제 상황

(1) 프로세스 A가 실행 중이다가 system call
(2) 커널 모드에서 count++ 수행하다가, 할당시간 만료로 CPU를 뺏김
(3) 프로세스 B가 커널 모드에서 count++ 수행 중, 시간 만료로 CPU 뺏김
(4) 프로세스 A가 CPU를 되돌려 받아, 아까 작업하던 count++ 진행

문제점

결과적으로 프로세스B의 count++는 반영되지 않음!
- 문맥이 프로세스A의 것을 저장하고 있기 때문임

해결법

커널 모드에서 작업을 수행 주잉면, CPU를 Preemt 당하지 않도록 함
반드시, 커널모드 -> 사용자모드로 돌아갈 때만, Preemt 당한다.

3. Multiprocessor에서 Shared Memory 내에 Kernel data에 접근하는 경우

문제점

어떤 CPU가 마지막으로 count를 store했느냐에 따라 결과가 달라짐
multiprocessor의 경우, interrupt enable / disable로 해결되지 않음.

해결법

방법1. 한 번에 하나의 CPU만이 커널에 들어갈 수 있도록 하고, 하나의 커널을 lock으로 막고, 커널을 빠져나올 때 unlock. (커널 전체를 lock하기 때문에 비효율적)
방법2. 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock

Critical Region(임계구역)

정의

N개의 프로세스가 공유데이터를 동시에 사용하길 원하는 경우
각 프로세스의 Code Segment에는 공유데이터를 접근하는 코드인 Critical Section이 존재함

해결할 사항

하나의 프로세스가 Critical Section에 있을 때, 다른 모든 프로세스는 Critical Section에 들어갈 수 없어야 함

Initial attempts to solve problem

두개의 프로세스가 있다고 가정 P0, P1
프로세스들의 일반적인 구조

do {
    entry  section		// 공유 데이터에 대한 lock을 건다.
    critical section	// 공유 데이터에 접근하기 위해 critical section에 들어옴
    exit section		// critical section을 나왔으므로, unlock을 한다. (다른 프로세스를 위해)
    remainder section
} while(1);

프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다. (synchronization variable)

임계구역 문제를 해결하기 위한 충족조건

Critical-section을 해결하기 위해서 만족해야 하는 조건은

(1). Mutual Exculsion(상호배제)

= 프로세스 P가 Critical Section에 들어가 있다면(코드를 수행중이라면), 다른 프로세스들은 Critical Section에 들어갈 수 없음

(2). Progress(진행)

= 아무도 Critical Section에 있지 않은 상태에서, Critical Section에 들어가고자 하는 프로세스가 있다면, Critical Section에 들어가게 해줘야 함

(3). Bounded Wating(유한대기)

= 프로세스가 Critical Section에 들어가려고, 요청한 후부터 그 요청이 허용될 때까지, 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 함
(Ex. 3개의 프로세스가 있는데, 2개 프로세스들끼리만 왔다갔다 사용하고, 나머지 하나 프로세스는 Critical Section에 들어가지 못하는 상황)

Algorithms

Algorithm 1

int turn;
intitalize turn = 0;		// P(i)는 critical section에 if(turn == i)면 들어감

do {
    while(turn != 0);		// 내 차례가 아니면, 대기
    critical section
    turn = 1				// 이제 상대방(P1) 차례
    remainder section
} while(1);

do {
    while(turn != 1);		// 내 차례가 아니면, 대기
    critical section
    turn = 0				// 이제 상대방(P0) 차례
    remainder section
} while(1);

이 알고리즘의 문제점

충족조건 1(Mutual exculsion)은 만족시킴
그러나, 충족조건 2(Progress)를 만족시키지 X
- 극단적인 예로, P0는 Critical Section을 많이 접근해야하고, P1은 Critical Section에 1번만 들어가면 되는 상황이라하자.
- P0 -> P1이 되고, P1이 본인 작업후 처음 Critical Section을 P0에 넘겨준 이후로는 turn 변수의 변화가 일어나지 못할 것이고, P0는 영원히 대기중일 것임

즉, 과잉양보 현상이 발생한다.

과잉양보
: 반드시 한 번씩 교대로 들어가야만 함 (swap-turn). 그가 turn 값을 내 값으로 바꿔 줘야만 내가 들어갈 수 있음. 특정 프로세스가 더 빈번히 critical section에 들어가야 한다면, 문제가 발생

Algorithm 2

Shared Data

boolean flag[2];
initialize flag[all] = false	// 아직, 모든 프로세스는 critical section에 진입할 의사가 X

P(i) 가 CS에 들어가고 싶을 때 (flag[i] == true)

do {
    flag[i] = true;		// 나 들어가려고 한다.
    while(flag[j]);		// 다른 사람 있으면 기다릴게
    critical section	// critical section 들어와서 수행
    flag[i] = false;	// 나 다 끝났어. 깃발 내린다.
    remainder section
} while(1);

이 알고리즘의 문제점

충족조건 1(Mutual exclusion)은 만족함
그러나, 충족조건 2(Progress)는 만족시키지 X
- 한 프로세스가 깃발(flag)를 들고 CPU를 뺏긴 뒤, 다른 프로세스가 깃발을 들 경우, 둘 다 2행(while문)까지 수행 후, 서로 끊임없이 양보(과잉양보)

Algorithm 3 (Peterson`s Algorithm)

Algorithm 1,2를 통합하고, 순서를 잘 고려한 알고리즘

do{
    flag[i] = true;					// 나 들어가고 싶다.
    turn = j;						// 상대방 차례로 세팅
    while(flag[j] && turn == j);	// 상대방이 깃발(flag)도 들고, 들어갈 차례면 난 기다릴게
    critical section
    flag[i] = false;				// 나 끝났어. 깃발 내린다.
    remainder section
} while(1);

이 알고리즘 분석

critical section 충족조건 3가지 조건을 모두 충족함
그러나, Busy Waiting(=spin lock) 발생
(상대가 turn을 바꿔주지 않는 이상, 계속 CPU와 메모리를 쓰면서 wait. 비효율적)

Synchronization Hardware

앞선 방식들은 SW적인 처리방식의 가장 큰 특징인, 하나의 Instruction으로 처리 할 수 없어서 생긴 문제들이다.

이게 하나의 instruction으로 해결되면 간단히 lock걸고 해제할 수 있음 !

즉, 하드웨어적으로 하나의 (Test & modify를 atomic하게 수행할 수 있도록 지원하는) instruction만 주어지면 critical section문제는 쉽게 해결된다!

Test_and_set(a) 이라는 고유(Atomic)한 instruction이 제공됨

a라는 데이터를 읽어와서 값을 1로 바꿔준다. (즉, 읽고 쓰기를 동시에!)

Mutual Exclusion with Test & Set

Sychronization variable

boolean lock = false;

P(i)에 대해서

do {
    while(Test_and_Set(lock));	// lock 걸렸는지 체크하고, 아무도 없으면 내가 들어가기 전에 lock을 건다.( lock = false -> true )
    critical section
    lock = false;
    remainder section
} while(1);