이 글은 운영체제 공룡책을 읽고 정리한 내용입니다.

프로세스란?

운영체제는 응용프로그램이 동작할 수 있도록 자원을 관리하고 환경을 제공해줍니다. 즉 CPU활동을 관리한다고 볼 수 있는데 이러한 CPU활동을 무엇이라 부를까요?
응용프로그램들을 모두 메인메모리에 올릴 수 없으므로 하드디스크에 대부분의 실행프로그램들이 저장됩니다. 이후에 프로그램을 실행할 때 하드디스크에서 해당 프로그램을 불러와 메인메모리에 올려 동작할 수 있도록 준비시키고, 운영체제는 이를 실행시킵니다. 이러한 작업 (메인메모리에 올라와서 동작할 준비가 되어있거나, 혹은 동작하고 있는 상태) 들을 프로세스라고 부릅니다.

프로세스에는 5가지 상태가 있습니다.

• new : 프로세스가 생성중인 상태
• running : 명령어들이 실행되고 있는 상태
• waiting : 프로세스가 어떤 이벤트가 일어나기를 기다리는 상태
• ready : 프로세스가 처리기에 할당되기를 기다리는 상태
• terminated : 프로세스의 실행이 종료된 상태

CPU의 한 코어에서는 하나의 프로세스만이 실행 (running) 될 수 있지만 다수의 프로세스가 준비완료(ready)나 대기상태(waiting)로 있을 수 는 있습니다. 즉 8코어CPU를 가지고 8개의 프로세스를 실제로 동시에 실행할 수 있으며 1개의 코어로는 프로세스 스케줄링을 통해 여러개의 준비된 프로세스들을 번갈아가며 실행하며 다중 프로세스를 실행하는것과 같은 효과를 낼 수 있습니다.

프로세스 스케줄링

프로세스가 시스템에 들어가면 준비 큐에 들어가서 CPU 코어에서 실행되기를 기다립니다. 프로세스에 CPU코어가 할당되면 일시적인 할당시간동안 동작하게 되는데 종료되지 않고 인터럽트 되거나 특정이벤트가 발생되는 것을 기다려야 하는 경우가 있습니다. 해당 프로세스들은 대기 큐에 들어가서 이벤트를 기다리게 됩니다.
위 그림에서 보이는것처럼 프로세스들은 준비큐에서 기다리다가 CPU 코어를 할당받아 잠시동안 동작하고 다시 준비큐로 들어오는 과정을 종료될때까지 반복하게 되는데 그 중간과정에서 인터럽트나 입출력등의 이벤트가 필요한 경우 대기 큐에서 해당 이벤트를 대기하다가 다시 준비큐로 들어오며 다중 프로세스가 CPU 단일코어에서 동작하게 되는 모습입니다.

CPU 스케줄링

준비큐에 있는 프로세스에 CPU 코어를 할당하는 CPU 스케줄러가 존재합니다. 당연히 어떤 프로세스를 CPU에 올릴것인지에 대한 프로세스 스케줄링이 필요한 것처럼 멀티코어 CPU의 경우 해당 프로세스를 어떤 CPU코어에 할당할 것인지에 대한 CPU 스케줄링 또한 필요한 것입니다.
추가로 가용 메모리 공간을 확보해야 하는경우 스와핑이라는 기법을 사용할 수 있는데 메모리에서 프로세스를 제거하여 다중 프로그래밍 정도를 감소시키는 방법입니다. 메모리에서 디스크로 프로세스를 옮기면서 상태를 저장하여 이후에 다시 복원할 수 있는데 임시방편으로 가용메모리를 확보하는 경우 사용됩니다.

안드로이드에서의 프로세스

모바일 환경은 자원이 제한되어있습니다. 따라서 모바일 운영체제는 제한된 시스템 자원을 회수하기위해 기존 프로세스를 강제로 종료해야할 수 있습니다. 이를 위해 Android에서는 프로세스의 중요도 계층으 식별하여 중요하지 않은 프로세스부터 강제로 종료하여 중요한 프로세스를 위한 자원을 확보하게 됩니다.

• foreground process : 사용자가 현재 상호작용하고 있는 응용 프로그램을 나타내며 화면에 나타나 있는 현재 프로세스
• visible process : 전경에서 직접 볼 수 없지만 전경 프로세스가 참조하는 활동을 수행하는 프로세스
• service process : 백그라운드 프로세스와 유사하지만 사용자가 인지할 수 있는 활동을 수행하는 프로세스 (음악 스트리밍)
• background process : 활동을 수행하고 있지만 사용자가 인식하지 못하는 프로세스 (백그라운드 게임 데이터 다운로드)
• empty process : 응용 프로그램과 관련된 활성 구성요소가 없는 프로세스

프로세스간 통신

서로 영향을 주고받는 협력적인 프로세스들이 있다면 통신을 통해 데이터를 주고받을 수 있어야 합니다. 따라서 프로세스간 통신 (interprocess communication, IPC)은 공유메모리나 메시지전달 두가지 방식으로 구현됩니다.

(a) : 공유메모리 방식으로 두 프로세스가 함께 접근가능한 공유메모리 영역을 할당하여 데이터를 읽고 쓸 수 있도록 합니다. 메모리 영역을 쓰거나 참조만 하기 때문에 운영체제의 개입이 없습니다.
(b) : 메시지 전달 방식으로 운영체제가 제공해주는 통신수단인 메시지큐를 사용하여 통신하는 방식입니다. 이 방식은 프로세스의 통신간에 운영체제가 개입하게 됩니다.

공유메모리 방식

생산자-소비자 문제의 경우 하나의 프로세스는 정보를 생산만 하고, 하나의 프로세스는 생산된 정보를 소비하기만 하는 구조입니다. 이런 경우 공유메모리를 통해 구현할 수 있는데, 하나의 프로세스는 공유메모리에 쓰기만 하고 하나의 프로세스는 공유메모리를 읽기만 하면 되기 때문입니다.
만약 공유메모리가 유한버퍼여서 꽉 찼다면 어떻게 될까요?
메모리가 꽉 찼다면 생산자 프로세스는 메모리에 자리가 날 때 까지 wait 해야할 것이고, 만약 메모리가 비어있다면 소비자 프로세스가 메모리에 데이터가 들어올 때 까지 wait 해야할 것입니다.
이러한 공유메모리 방식은 단점이 존재합니다. 공유메모리에 접근하고 조작하는 코드가 응용프로그램을 개발하는 과정에서 작성되어야 하는데, 만약 공유메모리에 접근해야하는 프로세스가 너무 많거나 추후 추가되거나 하면 그 과정이 복잡해지고 불편해질 수 있습니다. 따라서 운영체제에서 프로세스간 통신수단을 제공해주어 동일한 주소공간을 공유하지 않고도 프로세스들이 통신을 하고 동기화될 수 있는 방법이 아래에서 설명할 메시지 전달 방식입니다.

메시지 전달 방식

메시지 전달방식은 두 가지 연산을 필수적으로 제공합니다.

• send
• receive

보내고 받기. 되게 간단명료합니다. 두 프로세스간 통신을 원하면 그들 사이에 통신연결이 되어있어야 하며 서로 메시지를 보내고 받아야 합니다. 통신을 원하는 프로세스끼리 서로 가리킬 방법이 있어야 하는데 송수신자의 이름을 명시하여 send(P, message), receive(Q, message) 형식으로 P나 Q 프로세스로부터 메시지를 송수신하도록 구현할 수 있습니다. 이를 직접 통신이라 부르는데, 굳이 직접 통신하지 않아도 간접적으로 통신하는 방법 또한 존재합니다. 간접통신에서 메시지들은 메일박스 또는 포트 라고 부르는 곳으로 전송되는데 A라는 포트가 있다고 하면 send(A, message), receive(A, message)와 같이 특정 포트에 데이터를 송수신하도록 구현합니다.

CPU 스케줄링

위에서 설명했듯이 CPU는 매우 바쁜 상태를 유지하며 시스템의 모든 처리코어가 다중프로세스를 처리하도록 합니다. 프로세스 실행은 I/O 버스트와 CPU버스트를 왔다갔다 하면서 실행되는데 CPU 버스트의 실행시간 분포는 CPU 스케줄링을 하는데 중요하게 작용합니다.

선점 및 비선점 스케줄링

CPU 스케줄링 결정은 네 가지 상황에서 발생합니다.

• 한 프로세스가 실행상태에서 대기상태로 전환될 때
• 프로세스가 실행상태에서 준비 완료 상태로 전환될 때
• 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때
• 프로세스가 종료될 때

항상 1번과 4번의 경우에서만 스케줄링을 하게된다면, 프로세스가 알아서 종료되거나 대기상태로 돌아올때 까지 기다리기만 하면 됩니다. 이를 비선점 스케줄링이라 합니다. 2번과 3번의 경우도 발생한다면, 강제로 프로세스를 교체시키거나 가만히 놔두는 선택지가 존재합니다. 이러한 방식을 선점 스케줄링이라 합니다. 대부분의 운영체제는 효율을 위해 선점스케줄링방식으로 동작하지만 경쟁조건을 일으킬 수 있는 문제점이 있습니다.

디스패처

CPU 스케줄링을 할 때 CPU에서 동작하는 프로세스를 교체하는 행위를 context switching이라 합니다. 이러한 context switching 기능을 제공해주는 모듈을 디스패처라 부릅니다.

스케줄링 알고리즘

CPU 스케줄링 알고리즘을 비교하기 위해 여러가지 다양한 기준이 있습니다.

• CPU이용률
• 처리량
• 총 처리시간
• 대기 시간
• 응답 시간

보통 CPU이용률과 처리량을 극대화하고 총 처리시간, 대기 시ㅏㄴ, 응답 시간을 최소화하도록 동작합니다.

선입선처리 스케줄링 (FCFS)

이 알고리즘은 선입선출 큐로 관리하게 되는데 프로세스가 준비 큐에 진입하면 프로세스 제어블록 (PCB)을 큐의 끝에 연결합니다. 들어온 순서대로 프로세스가 진행되기 때문에 CPU 버스트 시간의 차이가 클 수록 평균 대기시간의 편차가 커질 수 있습니다.

Gantt 차트를 그려보면 위와 같은데 같은 프로세스가 순서만 반대로 들어온 경우입니다. 위의 케이스에서는 대기시간이 0 + 24 + 27 초로 긴 편이고 아래의 경우에는 대기시간이 0 + 3 + 6초로 매우 짧은 편입니다.
또한 이러한 방식은 도착순서대로 프로세스가 실행되고 끝날 때 까지 내려놓지 않기 때문에 비선점형 스케줄링으로 볼 수 있습니다.

위의 케이스에서 볼 수 있듯이 CPU 버스트가 짧은 프로세스를 먼저 실행하면 더 대기시간을 짧게 가져갈 수 있는데 들어온 순서대로 함에 따라 긴 프로세스가 나머지 짧은 프로세스를 방해하는 현상을 convoy effect라고 합니다.

최단작업 우선 스케줄링 (SJF)

프로세스의 CPU 버스트가 짧은 순서로 스케줄링을 진행하고, CPU버스트가 모두 같다면 FCFS를 적요하는 스케줄링 방법입니다.

이렇게 하면 보통 평균대기시간이 짧아진, 위와같이 최적화된 스케줄링이 가능합니다.
이러한 방식은 비선점형 스케줄링으로 구현할 수 도 있지만, 현재 진행중인 프로세스의 남은 CPU 버스트보다 더 짧은 프로세스가 들어오게 된다면 교체해버리는 선점형 스케줄링 방식으로도 구현가능합니다.
그러나 CPU 버스트의 정확한 길이를 알 방법이 없기 때문에 이전의 버스트들의 길이를 지수평균한 값으로 근사시켜 다음 버스트의 길이를 예측하는 식으로 우선순위를 정하게 됩니다.

라운드 로빈 스케줄링 (RR)

10~100ms정도의 작은 단위시간을 할당해서 해당 단위시간동안만 프로세스가 동작하도록 하는 스케줄링 방법입니다.

• 단위시간보다 긴 프로세스면 중간에 interrupt가 걸립니다.
• 단위시간보다 짧은 프로세스면 자연적으로 종료됩니다.

FCFS처럼 선입선출큐로 구현을 하는데 어차피 단위시간동안만 동작하게 되므로 CPU 버스트와 무관하게 균일한 평균대기시간을 가지게 됩니다. 단위시간이 너무 짧다면 context switching이 너무 빈번하게 일어나므로 CPU버스트에 손해를 봅니다. (dispatch latency가 증가한다는 것과 같은 말입니다.) 따라서 너무 길지도 너무 짧지도 않은 적당한 단위시간을 정하는 것이 중요합니다.
이 방식은 자명하게도 선점 스케줄링입니다.

우선순위 스케줄링

SJF나 FCFS 방식의 스케줄링은 각각 나름대로의 우선순위를 정해서 우선순위에 의해 CPU를 배정하는 방식이었습니다. 이러한 방식을 통틀어 우선순위 스케줄링이라 부르는데 (반대로 라운드 로빈은 우선순위 스케줄링이 아닙니다.) 이들에는 특별한 문제점이 있습니다.

무한 봉쇄 (indefinite blocking) 혹은 기아 상태 (starvation)이라 부르는데 실행준비는 되어 있으나 우선순위가 낮은 프로세스들이 계속해서 우선순위가 밀려 CPU를 얻지 못하고 무한히 대기하는 상태를 의미합니다.

이러한 문제를 해결하기 위한 방법으로 노화 (aging)가 있습니다. 시스템에서 대기하는 프로세스들이 탈출할 수 있도록 우선순위를 점점 증가시키는 것입니다.

다단계 큐 스케줄링 (MLQ)

우선 순위에 따라 준비 큐를 여러개 두는 방식입니다. 하나의 준비 큐에 우선순위 순서대로 들어가는 것이 아니라, 우선순위에 따라 각각 다른 준비 큐로 들어가 우선 순위가 높은 순서대로 준비 큐를 비우는 방식입니다.

안드로이드 OS와 같은 경우 각각의 프로세스 역할에 따라 자명하게 구분된 우선순위가 존재하는데, 이러한 프로세스들을 우선순위가 높은 (real-time과 같은 프로세스)것부터 먼저 전부 실행시키는 것입니다.

다단계 피드백 큐 스케줄링 (MLFQ)

MLQ 방식에서는 우선순위가 낮은 프로세스들이 실행되지 못할 가능성이 있습니다. 따라서 aging과 같이 기아문제를 해결할 수단이 필요합니다.

낮은 우선순위에서 너무 오래 대기하는 프로세스는 높은 우선순위의 준비 큐로 이동할 수 있고, 우선순위가 높은 프로세스가 CPU 버스트를 너무 오래 사용하면 낮은 우선순위 큐로 이동하게 됩니다.
가장 일반적인 스케줄링 알고리즘이며 특정 시스템에 부합하도록 설계가능하지만, 가장 복잡한 알고리즘이기도 합니다.

다중 처리기 스케줄링

• 다중 코어 CPU
• 다중 스레드 코어
• NUMA 시스템
• 이기종 다중 처리

와 같은 환경에서는 여러 스레드가 병렬로 실행되면서 부하 공유가 가능해지며 아래 그림과 같이 두 가지의 전략이 가능합니다.

(a) 옵션을 선택하면 공유 준비 큐에 경쟁조건이 생길 수 있으므로 서로 다른 프로세서가 동일한 스레드를 스케줄하지 않도록 보장해야 합니다.
(b) 옵션을 선택하면 경쟁조건과 같은 성능문제를 겪지 않지만 코어마다 부하가 편차가 생길 수 있으므로 비효율적이게 될 수 도 있습니다. 따라서 이를 해결하기 위해 균형 알고리즘을 사용하여 부하를 균등하게 분산시킬 수 있습니다.
보통 SMP를 지원하는 운영체제에서는 (b) 옵션의 형태로 스케줄링 하게 됩니다.

부하 균등화

위에서 (b)의 방식을 사용할 때 부하를 균등하게 하는 알고리즘에 대해 언급했었습니다.
하나의 처리기에만 큰 부하가 걸리게 되면 나머지 처리기들이 쉬게 되므로 부하 균등화는 SMP 시스템의 모든 처리기들에 부하를 균등하게 배분합니다.
특정 태스크가 주기적으로 각 처리기의 부하를 검사하고 부하가 높은 처리기에서 쉬고 있는 처리기로 push migration 시키거나, 쉬고있는 처리기가 바쁜 처리기로부터 pull migration 하는 방식으로 일어납니다.