[5주차] 병행 제어 (1)

신은지·2021년 10월 10일

반효경 공룡 OS

목록 보기

5/8

Process Synchronization

Race Condition
: 하나의 공유 데이터에 동시에 접근할 때 생기는 문제
: 서로 다른 프로세스 간에는 주소 공간을 공유하지 않지만, OS가 개입하는 경우 문제가 발생한다.
(CPU가 여러개일때, 하나일때 모두 발생 가능)
: 시스템 콜 발생 시 OS는 하나니까 공유 데이터에 복수의 접근이 발생할 수 있다.
: 데이터 최종 연산 결과는 마지막에 해당 데이터를 다룬 프로세스에 따라 달라진다.

OS에서 Race Condition 발생 상황
(1) Kernel 수행 중 인터럽트 발생 시
: 인터럽트 처리 때문에 OS 내부의 공유 데이터에 접근하여 발생하는 경우
: 인터럽트를 disable해서 해결한다.

(2) Process가 시스템 콜을 하여 kernel mode로 수행 중인데 문맥 교환이 발생하는 경우

(3) Multiprocessor에서 공유 메모리 내의 kernel data
: 한번에 하나의 CPU만 커널에 들어가게 만들어 OS를 공유하지 않게 만든다는 취지.
: 오버헤드가 발생하므로, OS 전체가 아닌 공유 데이터 각각을 lock / unlock해서 구현한다.

공유 데이터의 동시 접근(concurrent process)은 데이터의 불일치 문제를 발생시킬 수 있다.
: 일관성 유지를 위해 협력 프로세스간의 실행 순서를 정해주는 메커니즘이 필요하다!
: Race condition을 막기 위해 동시 접근은 동기화되어야 한다.

Critical-Section

Critical-Section (=임계영역 = 공유변수 영역)
: 공유 자원이 서로 참조될 수 있는 코드 범위. 동기화를 통해 독점을 보장하는 과정 필요

: P1 작업 수행 중 OS가 다른 프로세스(P2)로 넘어갈 때, P1의 작업은 반영이 되지 않을 수 있다.
: 한 프로세스가 임계영역에 들어가있으면, 다른 프로세스는 임계영역에 들어가지 못하게 lock을 거는 작업이 필요하다.

Race Condition Solution

프로그램적 해결법의 충족 조건
(1) Mutual Exclusion (상호 배제)
: 프로세스 Pi가 임계영역 부분을 수행 중이면 다른 모든 프로세스는 그들의 임계영역에 들어가면 안된다.
(2) Progress (진행)
: 아무도 임계영역에 있지 않은 상태에서 임계영역에 들어가고자 하는 프로세스가 있으면 임계영역에 들어가게 해준다.
(3) Bounded Waiting (유한대기)
: 프로세스가 임계영역에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 플로세스들이 임계영역에 들어가는 횟수에 한계가 있어야 한다.

Algorithm 1

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

critical section에 들어가기 전 내 차례인지 체크 - 내 차례가 아니면 기다리고, 내 차례면 공유 코드를 수행한 후 끝나면 상대에게 넘겨주는 방식
동시에 들어가는 경우는 발생하지 않지만, 무조건 순서를 번갈아 수행해야 한다는 문제가 생긴다.
: 특정 프로세스가 더 임계영역에 자주 들어가야하는데, 다른 프로세스는 굳이 들어갈 필요가 없다면?

Algorithm 2

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

들어가고 싶다는 의중 표현 후, 상대의 상태 확인하고 들어갈 수 있다면 들어간다.
누구든 임계영역에 들어갔다가 나올 때 깃발을 내려서 표시한다.
다른 깃발이 들려있을 때, 끊임없이 서로 양보하는 상황이 발생할 수 있다.
: 서로 깃발만 들고있다가 CPU를 뺏기는 상황 = Progress 문제 발생 가능

Algorithm 3 (Peterson's Algorithm)

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

깃발을 든 경우에 한해서 임계영역에 들어가도록 턴을 정한다.
: 상대가 깃발을 들었는지, 그리고 이번이 상대의 턴인지를 체크해서 두 조건에 해당하는 경우에만 기다린다. 내가 임계영역을 나올 때는 깃발을 내려서 표시한다.
Busy Waiting 발생 (= spin lock)
: 동작은 하지만 비효율적! 계속 CPU와 memory를 쓰면서 기다리는 문제 발생
: 내가 while에 걸려서 임계영역 못 들어가는 상황이면, CPU를 들고서 while만 돌 수 있다.

Synchronization Hardware
동기화를 하드웨어단에서 지원해서 문제 해결하기
: 하드웨어적으로 CPU 접근을 쪼개지 않고 한번에 하도록 만들면 임계영역 접근 문제를 해결할 수 있다.

Semaphores (세마포어)

지금까지의 방식들을 추상화시킨 것. 일종의 추상 자료형
세마포어를 이용, race condition 문제를 추상 자료형으로 해결할 수 있다.

P 연산 : 자원을 획득하는 과정 = lock 과정
V 연산 : 자원을 반납하는 과정 = unlock 과정

(1) Busy-wait

: 변수값을 주고 처리
: busy waiting 문제 발생

(2) Block / Wakeup Implementation

: 세마포어를 일종의 구조체로 정의
: 큐를 이용, 실행 중 오래 걸리는 작업에 걸리면 잠들게 두고(대기), 나머지 작업은 세마포어를 쓸 수 있게 만든다.

: P연산 - 세마포어 자원이 음수라면 여분이 없는 상태 = 리스트에 프로세스를 동결시킨다.
: V연산 - 세마포어 자원이 반납되어 양수가 되면 여분 생김 = block된 프로세스를 wakeup 시킨다.

세마포어 구현법 비교
(1) 임계영역 길이가 긴 경우, Block/Wakeup이 적당
(2) 임계영역 길이가 매우 짧은 경우(경쟁이 치열하지 않은 경우), Block/Wakeup 오버헤드가 busy-wait 오버헤드보다 커질 수 있다! (굳이 재우고 깨울 필요 없다)
(3) 그래도 일반적으로 Block/Wakeup이 더 좋다