[운영체제] 3. CPU 스케줄링 - 스케줄러, 선점형 스케줄링, 비선점형 스케줄링, 멀티 레벨 큐 스케줄링

2. 프로세스와 스레드는 아래 링크에서 확인 가능합니다.

 

[운영체제] 2. 프로세스와 스레드 : PCB, TCB, 프로세스의 상태 전이, IPC

 

 

저번 포스트를 통해서 프로세스의 정의와 상태, 스레드, 멀티스레드 프로그래밍, 멀티프로세스 프로그래밍에 대해 알아보았다면 이번 포스트에서는 CPU 스케줄링에 대해 알아보자. 

 

 

📎 CPU 스케줄링의 목적

먼저 CPU 스케줄링이 왜 필요할까 ?

CPU 스케줄링의 등장 배경 

CPU가 유휴상태 (CPU가 잠시 사용되지 않는 상태, 즉 쉬는중)가 될때마다, 운영체제는 준비 큐 (프로세스 중 준비 상태)에 있는 프로세스 중 하나를 골라 실행해야 한다. 이때, 당연히 CPU의 유휴 상태는 곧 시스템의 자원 낭비이므로, 운영체제는 CPU의 유휴 시간을 최소화 하기 위해 노력하고, 따라서 프로세스를 실행하는 효율적 전략을 세워야할 것이다. 이때 이러한 전략이 CPU 스케줄링 알고리즘이다. 

 

예를 들어, 우리가 매일 사용하는 웹 서버를 생각해보자. 

 

웹 서버는 동시에 수많은 요청을 처리해야하는데, 일부 요청은 DB 쿼리 수행같은 I/O 즉, 입출력 작업을 필요로하고, 다른 요청은 또 연산을 필요로하는, 즉 CPU 작업을 필요로 한다고 해보자. 알다시피, 입출력 요청은 CPU bound 작업보다 더 많은 시간을 필요로 한다. 이때, 효율적 스케줄링 없이 I/O 작업 결과를 대기한다고 하면, CPU는 유휴 시간이 길어진다. 따라서 다양한 기준에 따른 알고리즘을 선택하여 유휴 시간을 최대로 줄이는, 최적의 상태를 유지하려 노력하기 위해 CPU 스케줄링이 등장했다. 

 

 

---

 

📎  프로세스를 관리하는 큐 

CPU 스케줄링에 대해 본격적으로 알아보기 전에, 프로세스 관리를 위해 사용되는 큐에 대해 알아보자. 

 

 

• 작업 큐(Job Queue)
  • 시스템에 제출된 모든 프로세스가 저장되는 큐
  • 디스크와 같은 보조 기억 장치에 존재하며, 프로세스의 생성 순서대로 저장된다
  • 장기 스케줄러에 의해 관리된다
• 준비 큐(Ready Queue)
  • 메모리에 적재되어 CPU 할당을 기다리는 프로세스들이 저장되는 큐
  • 단기 스케줄러에 의해 관리되며, 다양한 스케줄링 알고리즘에 따라 프로세스의 순서가 결정된다
• 대기 큐(Wait Queue)
  • I/O 작업이나 특정 이벤트 발생을 기다리는 프로세스들이 저장되는 큐
  • 각 I/O 장치마다 대기 큐가 존재하며, 이벤트 발생 시 프로세스는 준비 큐로 이동한다

 

 

---

 

 

📎  스케줄러의 종류

스케줄러는 프로세스 관리의 시간적 범위와 실행 빈도에 따라 장기, 중기, 단기로 나눌 수 있다. 실행빈도는 장기 -> 단기 순으로 높다. 

 

 

장기 스케줄러  - 작업을 어떤 순서로 가져와 메모리에 적재할 것인가

장기 스케줄러는 디스크에 있는 작업들을 메모리로 어떤 순서로 가져올지 결정한다. 작업 큐에서 준비 큐로 프로세스를 이동시키는 역할을 한다고 보면된다. 

• 디스크 - 메모리 사이의 스케줄링을 담당
• 프로세스 상태 변화 : 생성 -> 준비
• 현대의 시분할 시스템에서는 거의 사용되지않고, 배치 처리 시스템 등에 한정적 사용

 

중기 스케줄러 - 메모리에 적재된 프로세스 수를 어떻게 관리할 것인가

중기 스케줄러는 메모리에 적재된 프로세스의 수를 조절하여 시스템 성능을 최적화한다. 스왑핑(Swapping) 기법을 사용하여 메모리에서 디스크로 프로세스를 이동(swap out)시키거나 다시 메모리로 가져오는 역할을 한다.

• 프로세스 상태 변화 : 준비 -> 중단(suspended)

 

이때 suspended 는 우리가 알고있는 프로세스의 상태 5단계 - block과 같이 프로세스의 실행이 중단된 상태라는 공통점이 있지만 원인에 대한 차이가 있으니, 아래와 같이 참고하여 알아두자. 

 

Suspended 상태 (중단 상태)

• 발생 원인:
  • 주로 중기 스케줄러에 의해 발생
  • 메모리 부족(너무 많은 프로세스가 메모리에 적재되어 프로세스당 가지고 있는 메모리가 극히 적어지면) 과 같은 외부적인 이유로 인해 프로세스가 디스크로 스왑 아웃(swap out)되어 실행이 중단된다
• 복귀 과정:
  • 스스로 Ready 상태로 돌아갈 수 없다
  • 중기 스케줄러에 의해 다시 메모리로 스왑 인(swap in)되어야 Ready 상태로 돌아갈 수 있다

Blocked 상태 (대기 상태)

• 발생 원인:
  • 프로세스가 I/O 작업 완료와 같은 특정 이벤트가 발생하기를 기다리는 동안 발생
  • 프로세스 스스로 I/O 작업을 요청하고 기다리는 상태
• 복귀 과정:
  • I/O 작업이 완료되면 스스로 Ready 상태로 돌아갈 수 있다
  • 외부적인 스케줄러의 개입이 필요하지 않다

 

단기 스케줄러 - CPU를 어떤 프로세스에 할당할 것인가

단기 스케줄러는 준비 큐에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정한다. 시분할 시스템에서 주로 사용되며, 실행 빈도는 매우 높다. 프로세스의 상태를 Ready, Running, Waiting 사이에서 변경한다.

• 시분할 시스템에서 주료 사용
• 메모리 - CPU 사이의 스케줄링 담당 
• 프로세스 상태 변화 : 준비 -> 실행 -> 대기 -> 준비

 

 

따라서 결국 시스템의 프로세스 관리와 CPU 할당을 간략히 표현하면 다음과 같다. 

 

1. 새로운 프로세스가 작업 큐에 저장된다
2. 장기 스케줄러는 작업 큐에서 프로세스를 선택하여 메모리에 적재하고, 준비 큐로 이동시킨다
3. 단기 스케줄러는 준비 큐에서 CPU를 할당할 프로세스를 선택한다 
4. 디스패처는 선택된 프로세스에 CPU를 할당하고, 문맥 교환을 수행한다
5. 프로세스는 CPU를 사용하여 작업을 수행하다가 I/O 작업이나 이벤트 대기가 필요한 경우 대기 큐로 이동한다
6. I/O 작업이나 이벤트가 완료되면 프로세스는 다시 준비 큐로 이동하여 CPU 할당을 기다린다

 

여기의 3번 과정에서 단기 스케줄러는 선택한 CPU 스케줄링 알고리즘에 따라 CPU를 할당할 프로세스를 선택하게 된다. 

 

 

---

 

 

 

📎  스케줄링의 종류 

스케줄링 알고리즘은 CPU를 프로세스에 할당하는 방식에 따라 선점, 비선점 스케줄링으로 구분할 수 있다. 

 

선점 스케줄링

기준

• 실행 중인 프로세스가 완료되기 전에 다른 프로세스가 CPU를 강제로 점유할 수 있다
• 우선순위가 높거나 긴급한 처리를 위해 사용된다

장점

• 응답 시간이 중요한 시스템에 적합해, 우선순위가 중요한 프로세스를 신속하게 처리할 수 있다
• 반응성이 좋다

단점 

• 문맥 교환으로 인한 오버헤드가 발생할 수 있다
• 우선순위 관리가 까다로워질 수 있다 

사례

• 시분할 시스템, 실시간 시스템 (빠르고, 반응성 중요한)
• 라운드 로빈, SRTF 스케줄링 

 

비선점 스케줄링

기준

• 실행 중인 프로세스가 완료되기 전까지 다른 프로세스가 CPU를 점유할 수 없다
• 프로세스가 CPU를 스스로 반환할 때까지 기다려야 한다

장점

• 문맥 교환으로 인한 오버헤드가 적고, 우선순위 관리가 간편하다 

단점 

• 응답 시간, 반응성이 느려질 수 있다
• 짧은 시간을 요구하는 작업을 수행하는 프로세스가 긴 작업 종료 시 까지 대기해야 할 수 있다

사례

• 일괄 처리 시스템 (응답 시간보다는 처리량 자체가 중요한)
• FCFS, SJF 스케줄링 

 

 

 

 

---

 

 

 

📎  기아 상태와 해결 방법

그런데 우선순위가 계속 밀리고 밀려 무한히 실행이 안되는 프로세스가 있으면 어떡할까 ? 

 

우선순위가 낮은 프로세스가 계속 CPU를 할당 받지 못하고 준비 큐에서 무한히 대기하는 상태를 기아 상태 라고 하며 따라서 우선순위 스케줄링 기법에서 발생한다. 먹을게 (자원)이 없어서 무한히 배고픈 상태라고 쉽게 생각하면 되며, 이러한 기아 상태는 에이징 기법으로 해결할 수 있다.

 

에이징 기법은, 오랫동안 대기한 프로세스의 우선순위를 점차 높여 자원 할당 기회를 제공하는 기법이다. 오래 대기할 수록, 그에 비례해 우선순위를 높여주면서 모든 프로세스에게 공정한 기회를 줘 해결한다. 

 

 

 

📎 CPU 스케줄링 알고리즘 - 선점형

앞서 말했듯이 선점형 알고리즘은 CPU가 프로세스를 실행 중일때, 다른 프로세스가 강제로 CPU를 점유할 수 있는 스케줄링 방식이다. 

 

선점형 우선순위 

• 실행 중인 프로세스보다 우선순위가 높은 프로세스가 도착하면, 실행 중인 프로세스는 중단되고 새로운 프로세스가 CPU를 할당받는다
• 응답 시간이 중요한 실시간 시스템 등에 적합하다

 

 

라운드 로빈 

정의

• 각 프로세스에 동일한 시간 할당량(time quantum)을 부여하고, 할당량이 끝나면 다음 프로세스로 CPU를 넘기는 방식
• 모든 프로세스가 공평하게 CPU를 할당받으며, 시분할 시스템에 적합하다

특징

• 공정성을 보장하며, 응답 시간이 중요한 시스템에 적합하다
• 점유 시간이 시간 할당량보다 크면, 타이머에 의해 종료되어 인터럽트가 발생한다. 그러면 준비 큐에 있던 다음 프로세스가 CPU를 점유하게 되며, 아직 작업이 남은 실행중이던 프로세스는 준비 큐에 삽입된다. (FIFO니까 꼬리에 들어감)
• 시간 할당량(time quantum)의 크기에 따라 성능이 달라진다
  • 시간 할당량이 너무 크면 선입 선처리(FCFS)와 유사해진다
  • 시간 할당량이 너무 작으면 문맥 교환 오버헤드가 증가한다 (자주 프로세스가 바뀐다는거니까)

장점

• 모든 프로세스에 공평한 기회를 제공
• 응답 시간이 비교적 빠르다

단점

• 시간 할당량 설정에 따라 성능이 크게 달라진다
• 문맥 교환 오버헤드가 발생 가능

사용 예시

• 시분할 시스템, 실시간 시스템 등

 

SRTF (Shortest Remaining Time First) 

정의

• 현재 실행 중인 프로세스의 남은 실행 시간과 새로 도착한 프로세스의 실행 시간을 비교하여, 남은 실행 시간이 더 짧은 프로세스에 CPU를 할당하는 방식
• 최단 작업 우선 스케줄링(SJF)의 선점형 버전이다

특징

• 평균 대기 시간을 최소화한다
• 새로운 프로세스가 도착할 때마다 스케줄링을 다시 수행한다 (남은 시간 계산해야하니까)

장점

• 평균 대기 시간이 가장 짧다
• 시스템 처리량을 향상시킨다

단점

• 남은 실행 시간을 예측하기 어렵고, 매번 계산해야한다
• 문맥 교환 오버헤드가 발생할 수 있다
• 긴 작업의 경우 기아현상이 일어날 수 있다

사용 예시

• 실시간 시스템, 배치 시스템

 

 

📎 CPU 스케줄링 알고리즘 - 비선점형

 

비선점형 우선순위 

• 실행 중인 프로세스는 완료될 때까지 CPU를 점유한다
• 새로운 프로세스가 도착하더라도 실행 중인 프로세스가 완료될 때까지 기다려야 한다
• 일괄 처리 시스템 등에 적합하다 

 

SJF (Shortest Job First)

정의

• CPU 점유 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 방식
• 평균 대기 시간을 최소화하는 데 목적을 둔다

특징

• 비선점형이므로, CPU를 점유한 프로세스는 작업이 완료될 때까지 CPU를 놓지 않는다
• CPU 점유 시간을 미리 알고 있어야 스케줄링이 가능해, 과거의 점유시간을 통해 미래값을 예측하는 방식으로 구현한다
• CPU 점유 시간을 예측하기 어려운 대화형 시스템에는 적합하지 않다

장점

• 평균 대기 시간을 최소화하고, 이에 따라 전체 작업의 처리 시간을 단축시킬 수 있다

단점

• CPU 점유 시간을 미리 알아야 한다
• CPU 점유 시간이 긴 프로세스는 CPU를 할당받지 못할 수 있다

 

FCFS (First-Come, First-Served)

정의

• 준비 큐(Ready Queue)에 도착한 순서대로 CPU를 할당하는 방식
• 가장 간단한 스케줄링 알고리즘 (FIFO인 큐로 구현 가능하니까)

특징

• 비선점형이므로, CPU를 점유한 프로세스는 작업이 완료될 때까지 CPU를 놓지 않는다

장점

• 구현이 간단하고 공정하다
• 프로세스의 도착 순서대로 처리하므로 예측 가능하다

단점

• 평균 대기 시간이 길어질 수 있다
• CPU burst time이 긴 프로세스가 먼저 도착하면 다른 프로세스의 대기 시간이 길어진다

사용 예시

• 단순한 시스템이나 배치 처리 시스템

 

 

 

 

---

 

 

 

 

 

 

📎 멀티 레벨 큐와 멀티 레벨 피드백 큐 스케줄링

앞서 선점 / 비선점 방식의 스케줄링은 단일 큐를 사용하며, 각각 장단에 따라 쓰이기 좋은 시스템이 다르다는 공통점이 있다. 이 경우, 다양한 프로세스의 특성을 전부 반영할 수 없고 따라서 유연성이 부족하다는 단점이 있다. 또 우선순위 스케줄링 방식은 앞서 말했듯이 기아 상태의 발생 가능성이 있다. 

 

따라서 이를 보완하기 위해 준비 큐를 단일로 두지 않고 여러 개의 큐로 나누는 알고리즘이 등장했고, 다음과 같다. 

 

멀티 레벨 큐 스케줄링 (Multi-level Queue Scheduling)

 

 

 

정의

• 준비 큐를 여러 레벨의 큐로 나누어 프로세스를 관리한다
• 각 큐는 서로 다른 우선순위를 가지며, 일반적으로 높은 우선순위를 가진 큐일수록 CPU를 더 자주 할당받습니다.
  • 우선순위 높은 상위 큐 : 실시간, 대화형 작업
  • 우선순위 낮은 하위 큐 : 계산 위주의 작업
• 프로세스는 생성될 때 특정 큐에 할당되며, 큐 사이를 이동할 수 없다

특징

• 각 큐는 서로 다른 스케줄링 알고리즘을 사용할 수 있다
• 시스템 프로세스, 대화형 프로세스, 배치 프로세스 등 프로세스의 특성에 따라 다른 큐에 할당하여 효율적인 스케줄링 가능

장점

• 프로세스 특성에 맞는 스케줄링으로 효율성을 높일 수 있다

단점

• 큐 사이의 이동이 불가능하여 유연성이 떨어지고, 기아 상태 발생 가능성이 있다
  • 이를 해결하기 위해서 또 준비 큐를 스케줄링한다 : CPU 시간을 적절히 분배하여 스케줄링

 

멀티 레벨 피드백 큐 스케줄링 (Multi-level Feedback Queue Scheduling)

 

 

정의

• 멀티 레벨 큐 스케줄링과 유사하지만, 프로세스가 큐 사이를 이동할 수 있다는 점에서 차이가 있다
• 프로세스의 CPU 사용 시간에 따라 동적으로 우선순위를 변경하여 큐를 이동시킨다

특징

• CPU를 많이 사용하는 프로세스는 우선순위가 낮은 큐로 이동하고, I/O 작업을 많이 하는 프로세스는 우선순위가 높은 큐에 머무르게 한다
• 일반적으로 라운드로빈 알고리즘을 사용해, 각 큐에 시간할당량을 부여한다. 따라서 CPU 점유 시간이 짧으면 라운드로빈으로 빠르게 처리하고, 길면 할당 시간이 더 길게 된 하위 큐 (우선순위 낮은) 으로 보낸다. 해당 큐에서도 실행이 안되면, 최하위 큐로 보내 FCFS 로 처리한다.
• 프로세스의 과거 행동을 기반으로 우선순위를 동적으로 조정한다

장점

• 다양한 작업 부하에 유연하게 대응할 수 있고, I/O 중심 작업에 유리하다
• 기아 상태를 방지하고 시스템 반응성을 향상시킨다

단점

• 구현이 복잡하고 오버헤드가 발생할 수 있다
• 어떻게 큐를 이동시킬지 알고리즘을 잘 설정해야 한다

사용 예시

• 대부분의 현대 운영체제 (Windows, Linux 등) 에 쓰인다

 

 

참고자료 

Operating Systems: CPU Scheduling