운영체제: 프로세스(Process)와 스케줄링 알고리즘

운영체제는 컴퓨터 시스템의 핵심 부분 중 하나로, 프로세스 관리는 그 중요한 역할 중 하나입니다. 프로세스 관리를 이해하는 것은 운영체제와 컴퓨터 공학에 대한 기본적인 지식을 쌓는 데 중요합니다. 이 글에서는 프로세스 관리의 기본 개념과 중요성, 그리고 주요 프로세스 스케줄링 알고리즘에 대해 알아보겠습니다.

1 프로세스란 무엇인가?

1.1 프로세스의 정의

프로세스란 간단히 말해 실행 중인 프로그램입니다. 프로세스는 운영체제에 의해 관리되며, 각각 독립적인 메모리 공간을 할당받아 실행됩니다. 이로써 여러 프로세스가 동시에 실행될 수 있으며, 서로 간섭하지 않고 독립적으로 실행됩니다.

 

프로세스는 실행 중인 프로그램뿐만 아니라 프로세스 제어 블록(Process Control Block, PCB)과 같은 정보를 포함하고 있습니다. PCB에는 프로세스의 상태, 레지스터값, 프로세스 식별자 등의 정보가 저장되어 있어 운영체제가 프로세스를 관리할 때 필요한 정보를 담고 있습니다.

1.2 프로세스의 특징

프로세스의 주요 특징은 다음과 같습니다.

1. 독립성: 각각의 프로세스는 독립적인 메모리 공간을 가지므로 하나의 프로세스가 다른 프로세스에 영향을 주지 않습니다. 하나의 프로세스가 충돌하더라도 다른 프로세스에 영향을 미치지 않고 계속 실행될 수 있습니다.
2. 병렬 실행: 여러 프로세스가 동시에 실행될 수 있으므로 다중 코어(CPU) 시스템에서 병렬 처리를 지원합니다. 이를 통해 시스템의 성능을 향상시킬 수 있습니다.
3. 상호 협력: 프로세스 간에는 통신과 협력이 필요할 때가 있습니다. 운영체제는 이러한 프로세스 간 통신을 지원하며, 이를 통해 프로세스는 데이터를 교환하고 작업을 협력적으로 수행할 수 있습니다.

1.3 프로세스의 상태와 상태 전이

프로세스는 다양한 상태를 가질 수 있으며, 이러한 상태는 상태 전이에 따라 변경됩니다. 주요 프로세스 상태는 다음과 같습니다.

1. 준비 상태 (Ready State): 프로세스가 실행을 기다리는 상태를 준비 상태라고 합니다. 이 상태에 있는 프로세스는 CPU를 할당받을 준비가 되어 있지만 아직 실행되지 않았습니다.
2. 실행 상태 (Running State): 프로세스가 CPU를 할당받아 실행 중인 상태를 실행 상태라고 합니다. 이 상태에 있는 프로세스는 명령을 실행하고 있습니다.
3. 대기 상태 (Blocked State): 프로세스가 어떤 이벤트를 기다리는 상태를 대기 상태라고 합니다. 이벤트가 발생하면 대기 상태의 프로세스는 준비 상태로 전환됩니다.
4. 종료 상태 (Terminated State): 프로세스가 실행을 마치고 종료되거나, 오류로 인해 종료된 상태를 종료 상태라고 합니다.

프로세스는 이러한 상태들 사이를 상태 전이하며 실행됩니다. 이러한 상태 전이는 운영체제의 스케줄러에 의해 관리되며, 시스템의 효율성과 성능에 큰 영향을 미칩니다. 프로세스는 컴퓨터 시스템에서 실행되는 핵심 단위이며, 운영체제의 핵심 역할 중 하나입니다. 프로세스를 효과적으로 관리함으로써 시스템의 안정성과 성능을 향상시킬 수 있습니다.

 

이이서 프로세스 스케줄링 알고리즘에 대해 자세히 알아보겠습니다.

2 프로세스 스케줄링 알고리즘 개요

2.1 프로세스 스케줄링의 필요성

여러 프로세스가 동시에 실행되는 다중 프로세스 환경에서는 어떤 프로세스가 CPU를 사용할지 결정해야 합니다. 이를 위해 프로세스 스케줄링 알고리즘이 필요하며, 이 알고리즘은 다음과 같은 목표를 달성합니다.

• 공평성(Fairness): 모든 프로세스가 CPU 시간을 공평하게 나눠받아야 합니다.
• 효율성(Efficiency): CPU를 최대한 활용하여 시스템 성능을 향상시켜야 합니다.
• 응답 시간(Response Time): 사용자와 상호작용하는 프로세스는 빠른 응답 시간을 가져야 합니다.
• 우선순위(Priority): 일부 프로세스는 다른 프로세스보다 높은 우선순위를 가질 수 있어야 합니다.

2.2 주요 프로세스 스케줄링 알고리즘

프로세스 스케줄링 알고리즘은 다양하며, 다음은 몇 가지 주요한 알고리즘입니다.

1. FCFS(First-Come, First-Served) 스케줄링: 가장 간단한 스케줄링 알고리즘으로, 먼저 도착한 프로세스가 CPU를 할당받습니다. 공평하지만 평균 응답 시간이 길 수 있습니다.
2. SJF(Shortest Job First) 스케줄링: 실행 시간이 가장 짧은 프로세스에 CPU를 할당하는 알고리즘으로, 최소 응답 시간을 보장합니다. 하지만 실행 시간을 미리 예측해야 합니다.
3. Round Robin 스케줄링: 시간 할당량(Time Quantum)을 사용하여 각 프로세스에 일정 시간 동안 CPU를 할당하는 방식입니다. 공평하고 응답 시간이 예측할 수 있지만 오버헤드가 있을 수 있습니다.
4. 우선순위 기반 스케줄링: 프로세스에 우선순위를 부여하고, 우선순위가 높은 프로세스에 CPU를 할당하는 알고리즘입니다. 우선순위 결정이 중요하며, 높은 우선순위 프로세스가 계속 실행될 수 있어 기아(Starvation) 문제가 발생할 수 있습니다.

프로세스 스케줄링 알고리즘은 시스템의 성능에 직접적인 영향을 미칩니다. 적절한 알고리즘을 선택하고 조절함으로써 시스템의 응답성, 처리량, 및 효율성을 최적화할 수 있습니다. 프로세스 스케줄링 알고리즘은 다중 프로세스 환경에서 CPU를 효율적으로 관리하는 데 중요한 역할을 합니다.

 

이어서 위에 소개한 각 알고리즘을 더 자세히 설명하겠습니다.

3 FCFS 스케줄링 알고리즘

FCFS(First-Come, First-Served) 스케줄링 알고리즘은 가장 간단한 프로세스 스케줄링 방법의 하나입니다. 이 알고리즘은 먼저 도착한 프로세스가 CPU를 할당받는 방식으로 동작합니다. FCFS 스케줄링은 큐(Queue) 자료구조를 사용하여 프로세스를 관리합니다. 도착한 순서대로 큐에 프로세스를 추가하고, CPU가 사용 가능한 경우 큐에서 가장 앞에 있는 프로세스를 선택하여 실행합니다. 실행이 끝나면 해당 프로세스는 큐에서 제거됩니다

도착 시간(Arrival Time)과 대기 시간(Waiting Time)

FCFS 스케줄링에서는 도착한 순서대로 실행하기 때문에, 각 프로세스의 도착 시간에 따라 실행 순서가 결정됩니다. 이에 따라 프로세스의 대기 시간이 크게 영향을 받을 수 있습니다. 대기 시간은 해당 프로세스가 CPU를 기다리는 시간을 의미하며, 첫 번째 프로세스는 대기 시간이 0이지만, 이후의 프로세스는 이전 프로세스의 실행 시간에 영향을 받아 대기 시간이 길어질 수 있습니다.

평균 대기 시간(Average Waiting Time)

FCFS 스케줄링의 주요 단점 중 하나는 평균 대기 시간이 길다는 것입니다. 도착 시간이 빠른 프로세스가 뒤에 도착한 프로세스들을 기다려야 하므로, 평균 대기 시간이 증가할 수 있습니다.

FCFS 스케줄링의 장단점

FCFS 스케줄링은 간단하고 구현하기 쉽다는 장점이 있지만, 다음과 같은 단점도 가지고 있습니다.

• 기아(Starvation): FCFS 스케줄링은 무한 봉쇄 문제가 발생할 수 있습니다. 실행 시간이 긴 프로세스가 먼저 도착하면, 이후에 도착한 프로세스들은 오랜 시간 동안 CPU를 기다려야 할 수 있습니다.
• 평균 대기 시간 증가: FCFS 스케줄링은 평균 대기 시간을 증가시킬 수 있습니다. 특히, 실행 시간이 짧은 프로세스가 먼저 도착하고 실행되는 경우에도 뒤에 도착한 프로세스들이 대기해야 합니다.

4 SJF(Shortest Job First) 스케줄링 알고리즘

SJF(Shortest Job First) 스케줄링 알고리즘은 프로세스 스케줄링에서 가장 짧은 실행 시간을 가진 프로세스에 CPU를 할당하는 방식으로 동작하는 중요한 스케줄링 알고리즘 중 하나입니다. 이 알고리즘은 CPU를 가장 효율적으로 활용하는 데 도움이 됩니다.

도착 시간과 실행 시간

SJF 스케줄링에서는 각 프로세스의 도착 시간과 실행 시간을 알아야 합니다. 도착 시간은 프로세스가 시스템에 도착하는 시점을 나타내며, 실행 시간은 해당 프로세스가 CPU를 사용하는 시간을 의미합니다.

선점형(SJF Preemptive)과 비선점형(SJF Non-Preemptive)

SJF 스케줄링은 선점형과 비선점형 두 가지 방식으로 구현될 수 있습니다. 선점형 SJF에서는 이미 실행 중인 프로세스가 실행 시간이 더 짧은 새로운 프로세스에게 CPU를 양보할 수 있습니다. 반면, 비선점형 SJF에서는 한 번 CPU를 할당받은 프로세스는 실행을 마칠 때까지 CPU를 반환하지 않습니다.

SJF 스케줄링의 장단점

SJF 스케줄링은 다음과 같은 장단점을 가지고 있습니다.

• 최소 평균 대기 시간: SJF 스케줄링은 평균 대기 시간을 최소화하는 데 효과적입니다. 실행 시간이 짧은 프로세스가 먼저 실행되므로 대부분의 프로세스가 기다리는 시간이 짧아집니다.
• 실행 시간 예측 필요: SJF 스케줄링은 실행 시간을 예측해야 하므로, 실행 시간을 정확하게 예측하는 것이 중요합니다. 예측이 부정확하면 평균 대기 시간이 오히려 증가할 수 있습니다.
• 기아(Starvation): 선점형 SJF에서는 실행 시간이 긴 프로세스가 기아 상태에 빠질 수 있습니다. 실행 시간이 짧은 프로세스가 계속 CPU를 선점하기 때문에, 실행 시간이 긴 프로세스는 CPU를 할당받지 못할 수 있습니다.

SJF 스케줄링 알고리즘은 실행 시간이 짧은 프로세스를 우선적으로 실행하여 평균 대기 시간을 최소화하는 데 효과적입니다. 하지만 실행 시간 예측이 필요하며, 선점형 SJF에서 기아 문제가 발생할 수 있습니다.

5 Round Robin 스케줄링 알고리즘

Round Robin 스케줄링 알고리즘은 프로세스 스케줄링에서 가장 널리 사용되는 알고리즘 중 하나로, 시분할 시스템(Time Sharing System)에서 주로 활용됩니다. 이 알고리즘은 각 프로세스에 시간 할당량(Time Quantum)을 부여하고, 해당 시간 동안 CPU를 사용하도록 합니다. Round Robin 스케줄링은 시간 할당량을 사용하여 프로세스를 관리합니다. 모든 프로세스는 큐(Queue)에 들어가며, 큐의 맨 앞에 있는 프로세스에게 시간 할당량을 부여하고 CPU를 실행하도록 합니다. 시간 할당량이 만료되면 해당 프로세스는 큐의 뒤로 이동하고, 다음 프로세스가 실행됩니다. 이 과정이 반복되며, 모든 프로세스가 CPU를 공정하게 사용합니다.

시간 할당량(Time Quantum)

시간 할당량은 각 프로세스가 CPU를 사용할 수 있는 최대 시간을 나타냅니다. 일반적으로 짧은 시간(예: 10ms)으로 설정되며, 시분할 시스템에서는 사용자 경험을 향상시키는 데 도움이 됩니다.

선점형(Preemptive) 스케줄링

Round Robin 스케줄링은 선점형 스케줄링 알고리즘으로, 현재 실행 중인 프로세스의 시간 할당량이 만료되면 CPU를 선점하여 다음 프로세스에게 양도합니다. 이러한 선점형 동작으로 모든 프로세스가 CPU를 공평하게 사용할 수 있습니다.

Round Robin 스케줄링의 장단점

Round Robin 스케줄링은 다음과 같은 장단점을 가지고 있습니다.

• 공평한 CPU 할당: Round Robin 스케줄링은 모든 프로세스에게 공평하게 CPU를 할당합니다. 각 프로세스는 시간 할당량 동안 CPU를 사용하며, 시간이 만료되면 다음 프로세스에게 양도됩니다.
• 응답 시간 예측 가능: Round Robin 스케줄링은 응답 시간을 예측하기 쉽습니다. 각 프로세스는 시간 할당량을 가지고 있으므로, 다음에 실행될 프로세스가 언제 실행될지 예측할 수 있습니다.
• 오버헤드: 시간 할당량이 너무 작으면 문맥 교환(context switch) 오버헤드가 증가할 수 있습니다. 따라서 시간 할당량을 적절히 설정하는 것이 중요합니다.

Round Robin 스케줄링 알고리즘은 다중 프로세스 환경에서 CPU를 효율적으로 할당하는 데 많이 사용됩니다. 시간 할당량을 조절함으로써 응답 시간과 처리량을 조절할 수 있습니다. 하지만 시간 할당량 설정이 중요하며, 너무 작으면 오버헤드가 발생할 수 있습니다.

6 우선순위 기반 스케줄링 알고리즘

우선순위 기반 스케줄링 알고리즘은 각 프로세스에 우선순위를 부여하고, 우선순위가 높은 프로세스에게 CPU를 할당하는 방식으로 동작합니다. 이 알고리즘은 다양한 응용 분야에서 사용되며, 각 프로세스의 중요도나 긴급도에 따라 CPU를 할당할 수 있습니다.

 

우선순위 기반 스케줄링은 각 프로세스에 우선순위 값을 할당합니다. 일반적으로 낮은 우선순위 값이 높은 우선순위를 나타냅니다. CPU가 사용 가능한 경우, 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당합니다. 만약 두 개 이상의 프로세스가 동일한 우선순위를 가진 경우, 라운드 로빈 스케줄링과 유사하게 시간을 분할하여 CPU를 할당할 수 있습니다.

정적 우선순위 vs. 동적 우선순위

우선순위 기반 스케줄링은 정적 우선순위와 동적 우선순위 두 가지 방식으로 구현될 수 있습니다. 정적 우선순위에서는 프로세스가 생성될 때 고정된 우선순위를 부여받지만, 동적 우선순위에서는 실행 중인 프로세스의 상태나 동작에 따라 우선순위가 변동될 수 있습니다.

우선순위 기반 스케줄링의 장단점

우선순위 기반 스케줄링은 다음과 같은 장단점을 가지고 있습니다.

• 다양한 우선순위 지원: 우선순위 기반 스케줄링은 다양한 우선순위를 지원하여 다양한 응용 분야에서 사용될 수 있습니다. 중요한 작업이나 긴급한 작업을 우선적으로 처리할 수 있습니다.
• 기아 문제: 우선순위가 낮은 프로세스가 기아 상태에 빠질 수 있습니다. 항상 우선순위가 높은 프로세스에게 CPU를 할당하면 우선순위가 낮은 프로세스가 실행 기회를 얻지 못할 수 있습니다.
• 우선순위 역전 문제: 우선순위 기반 스케줄링에서는 우선순위가 높은 프로세스가 우선권을 가지지만, 우선순위가 낮은 프로세스가 높은 우선순위 프로세스의 자원을 사용해야 할 때 우선순위 역전 문제가 발생할 수 있습니다.

우선순위 기반 스케줄링 알고리즘은 프로세스의 중요도나 긴급도를 고려하여 CPU를 할당하는 데 사용됩니다. 다양한 우선순위를 지원하므로 다양한 응용 분야에서 활용할 수 있지만, 기아 문제와 우선순위 역전 문제에 주의해야 합니다.

7 멀티레벨 큐 스케줄링 알고리즘

멀티레벨 큐 스케줄링 알고리즘은 여러 개의 우선순위 큐를 사용하여 프로세스를 관리하는 방식으로 동작합니다. 각 큐는 서로 다른 우선순위를 가지고 있으며, 우선순위가 높은 큐에 있는 프로세스가 먼저 실행됩니다. 이 알고리즘은 다양한 프로세스 그룹 또는 작업 부하에 대한 다양한 우선순위를 지원하기 위해 사용됩니다.

 

멀티레벨 큐 스케줄링은 여러 개의 큐를 사용하여 프로세스를 관리합니다. 각 큐는 서로 다른 우선순위를 가지고 있으며, 우선순위가 높은 큐에 있는 프로세스가 먼저 CPU를 할당받습니다. 이 알고리즘은 다음과 같이 동작합니다.

큐의 우선순위

멀티레벨 큐에서는 여러 개의 큐가 존재하며, 각 큐에는 서로 다른 우선순위의 프로세스가 들어갑니다. 일반적으로 우선순위가 높은 큐에는 더 짧은 시간 할당량이 부여됩니다.

프로세스의 큐 이동

프로세스는 큐 간에 이동할 수 있습니다. 예를 들어, 우선순위가 낮은 큐에서 실행 중인 프로세스가 우선순위가 높은 큐로 이동할 수 있습니다. 이동은 다양한 조건에 따라 결정될 수 있으며, 일반적으로는 일정한 규칙 또는 우선순위를 기준으로 이루어집니다.

멀티레벨 큐 스케줄링의 장단점

멀티레벨 큐 스케줄링은 다음과 같은 장단점을 가지고 있습니다.

• 다양한 우선순위 지원: 멀티레벨 큐 스케줄링은 다양한 우선순위를 지원하여 다양한 응용 분야에서 사용될 수 있습니다. 각 큐는 다른 우선순위의 작업을 처리하므로 중요한 작업과 긴급한 작업을 분리하여 관리할 수 있습니다.
• 우선순위 역전 방지: 멀티레벨 큐 스케줄링은 우선순위 역전 문제를 방지할 수 있습니다. 높은 우선순위의 큐에서 실행 중인 프로세스가 낮은 우선순위의 큐로 이동하지 않는 한, 우선순위 역전이 발생하지 않습니다.
• 구현 복잡성: 멀티레벨 큐 스케줄링은 구현이 복잡할 수 있습니다. 큐 간의 이동과 우선순위 설정 등을 관리해야 하므로 구현 및 관리가 어려울 수 있습니다.

멀티레벨 큐 스케줄링 알고리즘은 다양한 우선순위와 작업 부하를 지원하여 다양한 응용 분야에서 사용됩니다. 우선순위 역전 문제를 방지할 수 있지만, 구현이 복잡할 수 있으므로 상황에 맞게 적절히 선택해야 합니다.

마치며

프로세스 관리는 운영체제의 핵심 기능 중 하나로, 컴퓨터 시스템의 성능과 안정성에 중요한 영향을 미칩니다. 이 글에서 다룬 내용을 통해 프로세스 관리의 핵심 개념과 주요 알고리즘을 이해했을 것입니다. 운영체제와 컴퓨터 공학에 대한 더 깊은 공부를 위한 좋은 시작점이었기를 바랍니다.