🖥 프로세스

이 글은 유튜브 HPC Lab. KOREATECH 채널의 운영체제 강의를 수강하며 정리한 글입니다. 글에 포함된 내용 및 사진의 저작권은 HPC Lab. KOREATECH 채널에게 있으며 요청에 의해 언제든지 내려갈 수 있습니다.

다중 프로그래밍 시스템에서는 여러 개의 프로세스들이 존재하며 각 프로세스들은 서로 독립적으로 동작한다. 하지만 독립된 프로세스들이 _동일한 데이터를 동시에 참조_(쓰기 작업이 있을 시)하고 있다면 문제가 발생할 수 있다. 이런 문제를 해결하기 위해서는 동일한 데이터를 동시에 참고하고 있는 프로세스들간의 대화가 있어야 하며 이 과정을 프로세스 동기화라고 한다.

이 장을 학습하기 전 주요 단어에 대해 알고가자.

• 공유 데이터(Shared data) : 여러 프로세스들이 공유하는 데이터
• 임계 영역(Critical section) : 공유 데이터를 접근하는 코드 영역(code segment)
• 상호배재(Mutual exclusion) : 둘 이상의 프로세스가 동시에 _critical section에 진입_하는 것을 막는 것

임계 영역

임계 영역은 여러 프로세스가 공유 데이터를 접근하는 영역을 뜻한다. 위 그림처럼 두 프로세스가 공유하는 sdata에 각각 1씩 더한다면 메모리에는 최종적으로 2가 저장될거라 생각할 수 있다. 하지만 우리 프로그램을 개발하고 최종적으로 얻는 기계어 명령은 _원자성(Atomicity)_와 _Indivisible(분리불가능)_이란 특성으로 한 기계어가 실행 도중엔 인터럽트를 받지 않는 특징을 가진다. 따라서 두 프로세스에서 동시에 작업이 이뤄진 경우 각 명령어가 수행되며 sdata에 데이터를 읽어오는 명령행을 수행하는 시점에 따라서 메모리에 저장되는 결과는 달라질 수 있다.

상호배재

임계 영역에서 두 프로세스가 동시에 공유 메모리를 사용하면 생길 수 있는 문제를 알아봤다. 임계 영역에서 발생하는 문제의 핵심은 두 프로세스가 동시에 같은 메모리를 사용하기 때문이다. 따라 임계 영역의 진입을 제어한다면 병렬성을 유지하면서 안전한 프로그램을 작성할 수 있을것이다.

상호배재를 구현하기 위해선 다음과 같은 기본 연산과 요구 조건이 필요하다.

• enterCS primitive
  • 임계 영역 진입 전 검사
  • 다른 프로세스가 임계 영역 안에 있는지 검사
• exitCS primitive
  • 임계 영역을 벗어날 때의 후처리 과정
  • 임계 영역을 벗어남을 시스템이 알림

다음은 상호배재가 지켜야할 요구조건이다.

• 상호배재(Mutual exclusion)
  • 임계영역에 프로세스가 있으면, 다른 프로세스의 진입을 금지.
• 진행(Progress)
  • 임계영역에 있는 프로세스 외에는, 다른 프로세스가 임계영역에 진입하는 것을 방해하면 안됨
• 한정대기(Bounded waiting)
  • 프로세스의 임계영역 _진입은 유한시간 내에 허용_되어야 함

멀티 프로그래밍에선 실행 동작이 예측하기 어렵고, 디버깅과 재연이 어려워 배우는 단계에서 상호배재 알고리즘을 당장 만드는 것은 굉장히 어렵고 많은 경험이 필요하다. 따라서 선구자들이 경험과 기술을 담아 만든 알고리즘을 알아보자.

S/W적 해결

Dekker's Algorithm

Dekker's algorithm은 Two process ME을 보장하는 최초의 알고리즘이다.

2개의 프로세스의 상호배재를 해결하기 위해 Dekkers' algorithm에선 flag, turn이라는 2개의 상태 변수를 사용한다. flag은 경우 프로세스가 임계 영역에 진입함을 의미하며, turn은 차례를 의미한다.

두 프로세스는 1행에서 임계 영역의 진입하기 전 flag에 자신이 진입함을 알리고 만약 상대방 프로세스가 임계영역을 사용하고 있다면 while을 수행하며 대기한다. 만약 두 프로세스가 동시에 임계영역에 진입하려고 시도한다면 두 프로세스 중 어떤 프로세스가 우선시 해야할지 정해야 한다. 이 문제를 해결하기 위해서 turn 변수를 사용한다. 만약 두 프로세스가 대기중이면 자기 차례(turn)이 아니면 내 flag를 내려 상대방이 임계영역에 진입할 수 있도록 한다. 상대방은 임계영역의 작업을 모두 수행한 후 내 flag를 내리고 상대방에게 차례(turn)을 넘긴다.

N-Process 상호배재

이제 N개의 프로세스의 상호배재에 대해 알아보자, N개의 상호배재 알고리즘은 다익스트라, 크누스, 램포트, 핸슨등이 있는데 이 강의에선 다익스트라만 소개한다.

다익스트라 알고리즘도 앞의 Dekker's algorithm과 같이 flag, turn 상태 변수를 사용한다. 하지만 상태에 대해 더 작은 단위로 잘라 문제를 해결하는 상태는 다음과 같이 구분한다.

• IDLE : 프로세스가 임계 지역 진입을 시도하고 있지 않을 때
• WANT-IN : 프로세스의 임계 지역 진입 시도 1단계일 때
• IN-CS : 프로세스의 임계 지역 진입 시도 2단계 및 임계 지역 내에 있을 때

다익스트라 알고리즘에선 임계 영역 진입하기 전 2단계를 거친다. 먼저 첫단계에서는 내가 임계 영역에 진입하기를 원한다는 상태(want-in)을 설정하고 내 차례(turn == i)가 올 때까지 while을 돌며 대기한다. 대기하면서 현재 임계 영역에 진입한 프로세스의 차례 상태를 검사하며(if (flag[turn] == idle)) 만약 현재 차례의 프로세스가 임계 영역을 빠져나와 IDLE 상태로 변경되면 자신의 아이디를 차례에 대입한다(turn = i) 하지만 이때 여러 프로세스가 경쟁 상태로 turn에 자신의 아이디를 대입하기 때문에 2단계에 여러 프로세스가 진입하게 될 수 있다.

2단계에서는 내가 임계 영역에 진입했다고 알리고 (flag[i] = in-CS), 현재 나를 제외한 다른 프로세스도 2단계에 접속 했는지 검사한다. 이때 j가 프로세스의 개수만큼 검사를 했지만 나를 제외한 모든 프로세스가 in-CS가 아니면 임계 영역에 진입하게 된다.

이처럼 다익스트라는 운이 나쁘다면 임계영역에 아무것도 없지만 1단계와 2단계를 여러번 수행할 수 있다.

SW 해결의 문제점

• 속도가 느림
  • 다익스트라 알고리즘에서 볼 수 있듯이 상황에 따라서 무의미한 진입시도가 반복될 수 있음
• 구현이 복잡함
  • 여러 프로세스가 동일한 상태를 동기화하기 위한 작업이 중요하기 때문에 구현이 복잡하다.
• ME primitive 실행 중 preemption 될 수 있음
  • 공유 데이터 수정 중은 interrupt를 억제 함으로서 해결 가능
    • Overhead 발생
• Busy waiting
  • 소프트웨어적으로 "대기" 상태를 구현하기 위해서 의미없는 무한반복(while True {})을 수행하는데 이 작업은 결국 시스템 자원을 소모하는 일(work)이기 때문에 효율적이지 못하다.

H/W 해결

TestAndSet 명령어

이전 S/W적 해결 방법이 복잡했던 이유는 상태 변수의 상태를 병렬적으로 수행되는 프로세스간 상태 변수의 동기화 처리가 추가되었기 때문이다.

boolean TestAndSet(boolean *target) {
    boolean temp = *target;
    *target = true;
    return temp;
}

이 문제를 해결하기 위해 하드웨어에선 새로운 명령어를 추가해 문제를 간단하게 만들었다. 위 코드에서 개별적인 행은 기계어가 한번에 처리된다. 따라서 개별 프로세스가 동시에 시도해도 ME가 보장되게 된다. (S/W 해결에선 위 코드에서 1행가 2행이 개별적으로 수행됐고, 1행과 2행 사이에 스케쥴러에 의해 작업이 중지되고 다른 프로세스가 임계영역 진입을 위한 작업을 하게 되면 ME가 보장되지 못했다.) 하지만 이런 방법은 3개 이상의 프로세스가 작업하게 된다면 Bounded waiting 조건이 위배될 수 있다.

N-Process 상호배재

H/W에서 N-Process에 대한 상호배재는 TAS 명령어를 통해 구현이 간단하다. 하지만 달라진 점은 N-Process에 대한 waiting 상태 배열을 사용하게 된다. 코드의 흐름은 먼저 내가 기다리고 있다고 알리고(waiting[i]=true), 누군가 진입을 했다고 예상한다(key=true) 그리고 while을 돌며 대기하게 되는데 이때 lock을 기준으로 임계 영역에 진입하게 된다. 임계영역에 접근하면 자신의 대기상태를 끄고(waiting[i]=false) 임계영역에 해당하는 작업을 수행한다. 임계영역에서 빠져나오면 내를 제외한 대기영역에서 다음에 해당하는 프로세스 id를 찾아는데 (while ((j!=i)&&!waiting[j]){...}), 만약 대기하는 프로세스가 없다면 다음에 시도하는 불특정 프로세스가 진입할 수 있도록 lock을 false로 둔다. 만약 대기하는 프로세스가 있다면 그 프로세스의 대기 상태를 false로 바꿔 사진에서 (3)에 해당하는 대기 상태를 빠져나오게 한다.

H/W 해결 장/단점

S/W에 비해 구현이 많이 간단해졌지만 아직 Busy waiting 문제를 해결하진 못했다.

OS supported SW solution

Spinlock

Spinlock(이하 스핀락)은 이전 S/W와 H/W가 해결하려던 방법을 합친 것이라 생각된다. 스핀락도 마찬가지로 임계영역에 누군가 들어갔는지 알기 위해 상태 변수를 이용한다. 하지만 이 상태 변수를 조작하는건 _초기화, P(), V() 연산_으로만 가능하도록 제한한다. P(), V()는 하드웨어에서 해결하려던 방법과 같이 운영체제가 이 연산은 한 Instruction cycle에 수행되도록 보장해준다. P() 연산은 자물쇠를 잠그고, V()는 자물쇠는 연다고 생각하면 임계 영역에 진입하기 전에 P()는 자물쇠를 잠그고 들어가게 되며 이 과정은 Indivisible(or atomic)하기 때문에 임계 영역에 유일한 프로세스가 진입할 수 있다. 작업을 끝낸 프로세스는 V()를 통해 자물쇠를 풀고 나오면 대기하던 프로세스가 다시 자물쇠를 잠그고 들어오는 형태로 동작하게 된다.

하지만 스핀락은 몇가지 단점이 존재한다. 첫번째로 멀티 프로세서 시스템에서만 사용이 가능하다. 왜냐하면 스핀락의 P(), V() 연산은 운영체제에 의해 실행 도중 CPU에서 쫓아내지 않는 Atomic한 연산을 보장한다. 따라서 다른 프로세스가 P() 연산에서 while을 돌며 대기를 하게 되면 다른 프로세스는 CPU를 점유하지 못해 둘 다 일을 할 수 없게 된다. 또, 앞서 언급한 것 처럼 스핀락의 P() 연산 내부에선 while을 통해 대기하는 Busy waiting 문제가 존재한다.

Semaphore

앞서 스핀락은 구현의 간단함과 운영체제 수준에서 보장하기 때문에 특정 하드웨어 명령어에 의존하지 않아도 되기 때문에 유용하지만 Busy waiting 문제를 해결하진 못했다. 이때 다익스트(Dijkstra)님이 1965년에 제안한 Semaphore(이하 세마포어)를 통해 이 문제를 해결했다. 앞서 스핀락와 비슷하게 음이 아닌 정수형 변수 S가 존재하며, 초기화, P(), V()로만 접근 가능하다는 점은 동일하다. 차이점이라면 _세마포어는 임의의 변수 S 하나에 Ready queue 하나가 할당_된다.

스핀락과 세마포어의 차이점이라면 S가 없을 경우(=임계 영역에 누군가 있다면) 스핀락의 경우 Busy waiting을 하며 순서를 기다리지만 세마포어의 경우 S에 할당된 Ready queue에서 대기_한다. 대기하던 프로세스는 V() 연산(=임계 영역 탈출시 호출)은 _S의 Ready queue에서 대기하던 프로세스 하나를 깨우거나 없다면 다음 프로세스가 사용할 수 있도록 S를 1증가한다.

이렇게 세마포어는 Busy waiting을 해결하지만 V()를 보면 알 수 있듯이 어떤 프로세스가 wake-up할지는 스케쥴러에 달려있다. 따라서 운이 좋지 않다면 프로세스는 Starvation problem을 겪게 된다.

프로세스간 실행 순서

세마포어를 이용하면 _프로세스간의 실행 순서_를 맞출 수 있다. 예를 들어 프로세스A는 프로세스B가 실행된 후 수행되어야 한다고 가정하면, S를 0으로 초기화하고 프로세스A는 P()를 호출하여 대기하도록 한다. 그리고 먼저 실행되어야 할 프로세스B가 V()를 호출하면 대기하던 프로세스A가 깨어나 작업을 수행할 수 있게 된다.

생성자-소비자 문제

생성자-소비자 문제는 생성자는 소비자가 소비를 하는 동안 생성할 수 없고, 소비자는 생성자가 생성하는 동안 소비를 할 수 없도록 한다. 만약 이 과정이 깨진다면 소비자는 미완성된 결과를 소비하고, 생성자는 소비자가 생성하는 동안 새로운 값을 넣어 자료의 무결성을 해칠 수 있을 것이다.

Single-buffer

버퍼의 크기가 1인 상황에서 세마포어를 이용한 생성자-소비자 문제를 알아보자. 이 경우엔 간단하게 표현하면 생성자와 소비자는 상대방이 잠금을 풀어주기 전에는 임계 영역에 진입할 수 없도록 만든다. 따라서 임계 영역이 끝나면 자신의 자물쇠를 풀어주면 대기하던 상대방이 작업을 수행할 수 있게 된다.

N-Buffers

버퍼의 크기가 N보다 큰 경우 생성자와 소비자 뿐만 아니라 버퍼의 크기(빈 공간, 데이터가 든 공간)에 해당하는 세마포어가 필요하다. 소비자와 생성자를 뜻하는 세마포어는 데이터 생성과 소비를 임계 영역으로 사용하기 위해 사용되며 자신이 작업할 임계 영역에 진입하기 전 자신의 세마포어를 잠근다(생성자의 경우 P(mutexP), 소비자의 경우 P(mutexC)) 이후 생성자는 데이터를 넣기 전에 빈 공간을 확인하고(P(nrempty)) 데이터를 넣은 뒤 데이터가 든 공간을 증가(V(nrfull))한다.

소비자도 자신의 데이터 소비를 임계 영역으로써 자기 자신에 세마포어를 잠그고(P(mutexC)), 데이터가 든 공간을 확인한다(P(nrfull)). 데이터를 소모하면 빈 공간을 증가한다(V(nrempty))

따라서 소비자는 데이터가 든 공간을 임계 영역 진입을 위한 자물쇠(P(nrfull))로 사용하고, 생성자는 데이터를 넣을 빈 공간을 임계 영역 진입을 위한 자물쇠(P(nrempty))로 사용한다.

Reader-Writer problem

Reader-Writer 문제는 여러명의 Reader들은 동시에 데이터를 읽을 순 있지만, 데이터를 작성하는 Writer는 오직 한사람이며, Reader와 Writer는 동시에 데이터를 접근할 수 없는 문제이다.

이 문제를 해결하기 위해선 Reader와 Writer 중 한쪽에게 우선권을 주도록한다. Reader가 우선 순위가 더 높은 경우 작업이 요청이 R-W-R 순서로 도착한 경우, 두 번째로 도착한 W는 마지막에 도착한 R이 우선 순위가 더 높기 때문에 R이 있는 동안엔 자신의 일을 할 수 없게 된다.

위 사진은 Reader가 우선시 될 경우이다. Writer는 오직 한명이기 때문에 간단하지만 Readers의 경우 조금 복잡하지만 작업 전/후 영역을 나눠 생각하면 비교적 쉽게 이해할 수 있다.

Reader는 먼저 읽기 작업인 프로세스가 없는 경우(nreaders==0) 데이터를 읽기 위해 Writer를 잠근다. 이때 Writer가 계속 쓰기 작업 중일 경우 Reader는 Ready queue에서 대기한다. Writer가 모든 쓰기 작업이 종료된 뒤 자신의 잠금을 풀면(V(wmutex)) 대기하던 Reader들이 읽기를 시작한다. 여기서 임계 영역에 진입하기 전 Reader의 수를 알기 위해 카운터를 한다(nreaders = readers + 1).

임계 영역이 끝난 후, Reader의 수를 1 줄이는데 이때 자신이 마지막 Reader였다면, Writer가 쓰기 작업을 할 수 있도록 Writer의 잠금을 풀어준다(V(wmutex))

Eventcount / Sequencer

세마포어는 앞서 문제가 되었던 다양한 문제와 Busy waiting까지 모든걸 해야했다. 하지만 세마포어는 대기하는 프로세스들 중 하나를 깨우는 과정에서 Starvation 현상이 발생하게 된다. Eventcount / Sequencer는 이런 문제를 해결하기 위해 제안된 방법이다. Sequencer는 정수형 변수로 세마포어의 S와 비슷하게 활용되며 ticket()이라는 특수한 연산으로만 접근이 가능하고 생성시 _0으로 초기화되고 감소하지 않는다._와 발생 사건들의 순서를 유지한다.

ticket(S)은 현재까지 ticket() 연산이 호출된 횟수를 반환하며 이 작은은 indivisible operation이다.

Eventcount는 정수형 변수이며, 생성시 0으로 초기화, 감소하지 않고 특정 사건의 발생 횟수를 기록한다. Eventcount는 read(E), advance(E), await(E, v)연산으로만 접근이 가능하다.

read(E)는 현재 Eventcount의 값을 반환한다. advance(E)는 E를 1증가하고, E에 해당하는 프로세스를 깨운다. await(E, v)는 현재 번호표(E)와 내 번호표(v)를 비교해 대기해야 한다면(if (E < v)), 해당 대기열에 프로세스를 전달해 내 차례가 되면 깨워돌라고 요청한다.

Eventcout / Sequencer의 동작 과정은 은행 창구와 매우 유사하다. 번호표를 뽑고(ticket(S)) 기다리다(await(E, v)) 아무도 없다면 볼 일을 보면 된다. 만약 내 차례가 아니면(E < v) 대기실에서 대기하고 있다 창구 직원이 부르면 내 차례가 돌아온다. 창구 직원은 번호표 순서에 맞게 부르기 때문에 영원히 안불리는 상황은 발생하지 않는다.(starvation 문제 해결)

이전 세마포어와 비슷하지만 세모퍼어의 P(S) 연산에 해당하는 작업에서 다음 순서를 보장받을 수 있는 ticket(S)이 추가된 것이 Eventcount / Sequencer이다.

생성자-소비자 문제

앞서 살펴본 생성자-소비자 문제를 Eventcount/Sequencer를 통해 해결해 볼 수 있다.

Language-level solution

앞서 ME를 해결하기 위해 다양한 영역에서의 솔루션을 얻고, 최종적으로 ME, Busy waiting, Starvation같은 문제를 해결했다. 하지만 앞서 내용을 접해봐서 알 수 있듯이 알고리즘과 사용 방법이 복잡한 면이 있다. Language-level solution은 이런 문제를 언어 차원에서 해결할 수 있는 솔루션이다.

Monitor