[Operating System] 프로세스와 동시성 제어

 

 

 

멀티쓰레드와 멀티프로세싱 환경에서는 여러 요소들이 동시에 실행되고, 운영체제는 동시성 관련 문제를 해결해 줘야 한다.

 

Race Condition - 두 요소가 동시에 공유 데이터를 조작할 때 실행 순서에 따라 결과가 달라지는 현상을 말한다.

Mutual Exclusion - 한 순간에 하나의 요소만 공유 자원에 접근할 수 있도록 보장해 Race Condition을 방지한다.

Critical Section - 여러 요소가 동시에 접근하면 안 되는 공유 자원에 접근하는 코드 블록 자체를 의미한다.

Starvation - 프로세스가 자원을 기다리지만 다른 프로세스가 자원을 반환하지 않아 무한히 기다리는 상황을 말한다.

Deadlock - 여러 프로세스가 서로 자원을 점유해 상대방이 작업을 마칠 때 까지 기다리며 무한히 기다리는 상황을 말한다.

 

CPU가 한 개인 경우에서도 Race Condition이 발생할 수 있다. (컨텍스트 스위칭. CPU 는 쓰레드를 실행!!!!)

 

 

N개의 Producer와 한개의 Consumer가 협업해서 작업을 처리한다고 해 보자.

Producer는 정보를 생산하는 역할을 수행하고 Consumer는 정보를 처리하는 역할을 수행한다.

 

Producer가 Consumer는 모두 독립적인 프로그램이고, 정보를 전달할 때는 IPC를 활용한다.

(Shared Memory 내부에 Buffer 존재)

 

 

 

in은 버퍼에 넣을 때 사용되고, out은 버퍼에서 정보를 꺼내갈 때 사용되는 인덱스로 사용된다.

 

 

 

 

이미 0과 1 인덱스에 들어가 있던 작업을 Consumer가 처리해 해당 인덱스는 비어 있다.

 

버퍼가 가득 찼으면 Producer는 대기해야 하고, 버퍼가 비어있으면 Consumer는 대기해야 한다.

이 부분을 간단하게 구현한다면 Busy Waiting을 사용해서 구현한다.

 

item v;
while (1) {
    while (counter == BUFFER_SIZE); (busy wait)
    b[in] = v;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

item w;
while (1) {
    while (counter == 0);  (busy wait)

    w = b[out];
    out = (out + 1) % BUFFER_SIZE;

    counter--;

    // consume item w 
}

 

 

무한 루프를 돌면서 기다리는 구조로, 계속 CPU를 사용해야 해서 비효율적이고 counter가 공유 메모리이기에 Race Condition이 발생할 수 있다. 

 

실제로는 Producer가 계속해서 CPU를 점유하고 있지는 않으니.. while 구문을 계속해서 실행하고 있지는 않는다.

Consumer가 counter를 조작하더라도 ready 상태에 있는 Producer는 그 변화를 실시간으로 확인하지 못해 자신에게 CPU가 할당될 때 까지 기다려야 한다. 

 

counter++ 연산은 한 문장이지만, 어셈블리어로 변환된 후 실행할 때는 3개의 명령어로 나눠서 실행된다. 

load register, counter -> increment register -> store register, counter

 

즉, 연산 자체가 원자적이지 않아 여러 요소에서 한 번에 접근 시 Race Condition이 발생할 수 있다. 

 

Interrupt는 CPU가 특정 작업을 수행하고 있을 때, 컴퓨터 하드웨어 등에서 발생한 이벤트가 CPU의 흐름을 가로채고 다른 작업을 먼저 처리하도록 요청하는 신호를 의미한다.

 

 

 

PIC는 하드웨어 장치의 신호를 인식하고 CPU에게 전달한다.

CPU는 명령어를 수행한 후 신호가 있는지 확인해 인터럽트가 들어왔는지 확인한다.

 

인터럽트 신호가 도착한 경우 커널은 현재 작업을 중단시키고 커널에 구현된 인터럽트 처리 함수를 실행한 후 원래 실행하던 프로그램을 이어서 실행시킨다.

 

인터럽트는 프로세스 스위칭에도 사용된다.

 

운영체제마다 다르지만, Clock은 일정 주기마다 인터럽트를 발생시킨다. (리눅스는 1ms마다 한 번의 인터럽트 발생)

CPU는 인터럽트마다 커널 모드로 변환해 커널 내부에서 인터럽트를 처리하는데, 이 때 인터럽트가 몇 번 걸렸는지 카운트해준다.

 

카운트 값이 100이라면 Time Slice가 주어진 후 인터럽트가 100번 걸렸음을 의미하니 할당된 Time Slice가 만료되었는지를 확인할 수 있다.

 

 

---

 

 

Producer의 Critical Section과 Consumer의 Critical Section이 서로 Mutual Exclusion 하게 실행되지 않아서 Race Condition이 발생한다.

 

 

 

 

명령어 집합의 크기가 큰 경우.. 사용자 입력, 중요한 패킷 등 빠르게 처리해야 할 인터럽트를 제대로 처리할 수 없다는 문제가 있어 자주 사용하지는 않지만...

 

원자적으로 실행해야 하는 명령어 집합을 다룰 때는 잠시 인터럽트를 무시하고, 해당 명령어 집합을 모두 처리한 후 인터럽트를 처리하는 방식으로 구현하면 Critical Section을 원자적으로 수행할 수 있어 Race Condition을 방지할 수 있다.

 

다른 방법으로는, 공유 메모리에 한 번에 하나의 Producer만 접근할 수 있도록 하는 방법이 있다.

Critical-Section Problem을 해결하기 위해서는 아래 세 가지 요구사항을 모두 만족해야 한다

 

1. Mutual Exclusion - 한 순간에 하나의 프로세스만 Critical Section에 들어갈 수 있어야 한다.

2. Progress - Critical Section에 들어가려는 프로세스가 없을 때, 다른 프로세스는 Critical Section에 진입할 수 있다.

3. Bounded Waiting - 특정 프로세스가 Critical Section에 진입하려 할 때, 무한히 기다리지 않는다. 

 

쓰레드끼리 서로 눈치만 보다가 아무도 못 들어가거나... 특정 쓰레드가 계속 새치기당해 무한히 기다려야 하는 경우가 있으니.. 세 가지 요구사항을 모두 만족시켜야 한다.

 

 

 

 

 

소스코드 수준에서 위와 같이 구현한다면 Mutual Exclusion은 만족하지만, Progress는 만족하지 않는다.

 

Process P1이 먼저 실행될 경우 아무 제약조건이 없기에 Critical Section에 바로 접근할 수 있어야 하지만 해당 while 구문의 조건에 걸려 들어갈 수 없다.

 

 

 

이런 문제를 해결하기 위해 Peterson Algorithm 이 도입됐다.

세 가지 요구사항을 모두 만족하지만, 두 개의 프로세스에 대해서만 제대로 작동하고.. Busy Waiting이 발생해 CPU를 낭비할 수 있다.

 

 

 

두 개 이상의 프로세스에서 제대로 동작하는 알고리즘으로 Bakery Algorithm 이 있다.

프로세스가 들어오면 우선 번호표를 뽑고.. 번호 순서대로 Critical Section에 접근하는 방식이다.

 

간단하게 구현할 수 있지만.. 실제 하드웨어 수준에서는 사용되지 않는다.