[운영체제] 6. CPU 스케줄링

반효경 교수님의 "운영체제와 정보기술의 원리" 책을 학습하고 정리한 글입니다.

 

0. CPU 스케줄링 개요

CPU는 여러 프로그램이 동시에 수행되는 시분할 환경에서 매우 효율적으로 관리되어야 하는 자원이다.

 

📌 프로그램 카운터 (PC, Program Counter)

현재 CPU에서 수행할 코드의 메모리 주소 값을 가진 레지스터

 

✍🏻 CPU가 실행하는 기계어 명령의 종류

• CPU 내 수행 명령
  • Add : CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령
  • CPU 내에서만 수행되어 명령의 수행 속도가 매우 빠르다
• 메모리 접근 명령
  • Load : 메모리에 있는 데이터를 CPU로 읽어들이는 명령
  • Store : CPU에서 계산된 결괏값을 메모리에 저장하는 명령
  • CPU 내 수행 명령보다는 시간이 오래 소요되지만, 비교적 짧은 시간에 수행

⇒  상기 두 명령은 사용자 프로그램이 직접 실행할 수 있는 일반 명령

• 입출력 동반 명령 : 키보드 입력, 처리 결과를 화면으로 출력
  • CPU나 메모리 접근 명령에 비해 대단히 오랜 시간이 소요

⇒ 모든 입출력 명령은 특권명령으로 규정해 사용자 프로그램이 직접 수행할 수 없고, 운영체제를 통해 서비스를 대행하도록 하고 있다.

 

🧐 사용자 프로그램 실행 과정

프로그램의 실행은 서로 다른 두 단계의 조합으로 이루어진다.

1. CPU Burst : 직접 빠른 CPU 내 수행 명령 실행 작업
2. I/O Burst : I/O 요청이 발생해 커널에 의해 느린 입출력 명령 실행 작업

 

✍🏻 버스트 비율에 따른 프로세스 분류

• CPU 바운드 프로세스 (CPU bound process)
  I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스
  • 프로세스 수행의 상당 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램
• I/O 바운드 프로세스 (I/O bound process)
  I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
  • 주로 사용자로부터 인터렉션(interrection)을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램(interactive program)

 

CPU 스케줄링은 이와 같이 CPU 사용 패턴이 상이한 여러 프로그램이 동일한 시스템 내부에서 함께 실행되어 필요하다. 프로세스의 CPU 버스트가 모두 균일한 경우는 CPU 스케줄링을 하는 것이 큰 의미가 없지만, 시분할 시스템에서는 CPU 버스트가 균일하지 않은 다양한 프로그램이 공존하여 효율적인 CPU 스케줄링 기법이 반드시 필요하다.

 

컴퓨터 시스템 프로세스의 대부분은 짧은 CPU 버스트를 가지는데, CPU를 한 번에 오래 사용하기 보다는 잠깐 사용하고 I/O 작업을 수행하는 프로세스들이 많다는 것이다. 즉, 사용자에게 입력을 받아 CPU 연산을 수행하고, 그 결과를 다시 출력하는 작업을 수행한다. 이러한 프로세스는 CPU의 빠른 서비스를 필요로 하기 때문에 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용하는 스케줄링 기법이 필요하다. 바꾸어 말하면 CPU 스케줄링 시 I/O 바운드 프로세스의 우선순위를 높여주는 것이 바람직하다.

 

1. CPU 스케줄러

준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드

 

✍🏻 CPU 스케쥴링이 필요한 경우

① 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄(blocked) 상태로 바뀌는 경우

② 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우

③ I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우

④ CPU에서 실행 상태에 있는 프로세스가 종료되는 경우

 

✍🏻 CPU 스케쥴러 방식

• 비선점형 방식 (nonpreemptive) : ① ④
  CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
• 선점형 방식 (preemptive) : ② ③
  CPU를 빼앗는 방법은 할당시간(time quantum)을 부여한 후 타이머 인터럽트를 발생시키는 방법이 대표적이다.

 

2. 디스패처 (Dispatcher)

새롭게 선택한 프로세스에 CPU를 할당하고 작업하도록 환경설정하는 운영체제의 코드

• 현재 수행 중인 프로세스의 문맥(Context)를 그 프로세스의 PCB에 저장
• 새롭게 선택한 프로세스의 문맥을 PCB로부터 복원한 후 CPU를 할당
• 시스템의 상태를 사용자 모드로 전환하여 사용자 프로그램에게 CPU 제어권을 넘김
• 사용자 프로그램은 복원된 문맥 중 프로그램 카운터로부터 현재 수행할 주소를 찾음

📌 디스패치 지연시간 (Dispatch latency)

디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간

 

3. 스케줄링의 성능 평가

• 시스템 관점 지표 : CPU 이용률과 처리량
• 사용자 관점 지표 : 소요시간, 대기시간, 응답시간 등 대기시간과 관련된 지표

CPU가 일을 하지 않고 휴면(idle) 상태에 머무르는 시간을 최대한 줄이는 것이 스케줄링의 중요한 목표다.

 

📌 용어 정리

• CPU 이용률 (CPU utilization) : 전체 시간 중 CPU가 일을 한 시간의 비율
• 처리량 (throughput) : 주어진 시간동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지를 나타낸 것
• 소요시간 (turnaround time) : 프로세스의 준비 큐 대기시간 + CPU 사용시간의 합
  ⇒ 프로그램이 시작해 종료하는 데까지 걸린 시간이 아니다.
• 대기시간 (waiting time) : CPU 버스트 기간 중 프로세스가 준비 큐에서 기다린 시간의 합
  ⇒ 한 번의 CPU 버스트 중에서도 준비 큐에서 기다린 시간이 여러 번 발생할 수 있다.
• 응답시간 (response time) : 프로세스가 준비 큐에 들어온 후 첫 번째 CPU 할당까지 기다린 시간

 

4. 스케줄링 알고리즘

4-1. 선입선출 스케줄링

📌 FCFS (First-Come First-Served)

프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식

• CPU를 먼저 요청한 프로세스에게 CPU를 먼저 할당하고, 자발적으로 CPU를 반납할 때까지 빼앗지 않는다.
• CPU 버스트가 긴 프로세스 하나가 CPU 버스트가 짧은 프로세스 여러 개보다 먼저 도착할 경우, CPU를 잠깐만 사용하면 준비 큐를 떠나 I/O 작업을 수행할 수 있는 다수의 프로세스들이 앞의 긴 작업 하나 때문에 계속 기다려야 하는 상황이 발생하는 비효율이 발생한다.
• 즉, 먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 달라진다.

 

📌 콘보이 현상 (Convoy effect)

CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상

• FCFS 스케줄링의 대표적인 단점

 

4-2. 최단작업 우선 스케줄링

📌 SJF (Shortest Job First)

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식

• CPU 버스트가 짧은 프로세스가 CPU를 먼저 사용하고 준비 큐를 빠져나가게 되면 프로세스들이 준비 큐에서 기다리는 전체적인 시간이 줄어들게 된다.
• 평균 대기시간을 가장 짧게 하는 최적 알고리즘(Optimal algorithm)으로 알려져 있다.

📌 SRTF (Shortest Remaining Time First)

현재 CPU에서 실행 중인 프로세스의 남은 CPU 버스트 시간보다 더 짧은 CPU 버스트를 가진 프로세스가 도착한 경우 CPU를 빼앗는 SJF의 선점형 구현 방식

• 비선점형 방식은 현재 CPU를 점유한 프로세스가 CPU 버스트를 모두 수행할 때까지 스케줄링을 하지 않는다.
• 선점형 방식은 CPU 버스트가 더 짧은 프로세스가 도착하면 이 프로세스에게 CPU를 할당한다.

 

SJF 스케줄링 기법의 구현의 어려운 부분은 CPU 버스트 시간을 미리 알 수 없다는 점이다. 그래서 예측을 통해 CPU 버스트 시간을 구한 후 예측치가 가장 짧은 프로세스에게 CPU를 할당하게 된다.

 

✍🏻 (n+1)번째 CPU 버스트의 예측 시간

• tn : n번째 실제 CPU 버스트 시간
• Tn : n번째 CPU 버스트의 예측 시간
• ⍺ : 0과 1 사이의 상수, 두 요소를 어느 정도씩 반영할지 조절하는 매개변수(parameter)

과거의 CPU 버스트 시간을 통해 미래의 CPU 버스트 시간을 예측하여 최근의 CPU 버스트 시간일수록 가중치를 높이는 방식이 된다.

 

SJF는 CPU 버스트가 짧은 프로세스에게만 CPU를 할당할 경우 CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야 하는 문제가 발생한다. CPU 버스트가 짧은 프로세스가 계속 도착할 경우 영원히 CPU를 할당받지 못하는 기아 현상(starvation)이 발생하게 된다.

 

4-3. 우선순위 스케줄링

📌 Priority Scheduling

준비 큐에 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 방식

• 우선순위 값(priority number)을 통해 표시하며 우선순위 값이 작을수록 높은 우선순위를 가지는 것으로 가정한다.
• 우선순위를 결정하는 방식은 CPU 버스트 시간 순서(SJF 알고리즘과 동일), 시스템 관련 중요 작업 순서 등이 존재한다.
• 우선순위 스케줄링도 비선점형 방식과 선점형 방식으로 각각 구현할 수 있다.
• 우선순위 스케줄링 방식에서도 기아 현상이 발생할 수 있다. 이런 문제를 해결하기 위해 노화(aging) 기법을 사용할 수 있다.

📌 노화 기법 (aging)

기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위를 가져 CPU를 할당하는 방법

 

4-4. 라운드 로빈 스케줄링

📌 Round Robin Scheduling

각 프로세스가 할당시간을 제한하여 CPU를 회수하고 준비 큐에 새로 대기를 시작하는 방법

• 시분할 시스템의 성질
• 할당시간이 너무 길면 평균 대기시간이 길어질 수 있다.
• 할당시간이 너무 짧으면 문맥교환의 오버헤드가 커진다.
• 일반적으로 할당시간을 수십 밀리초 정도의 규모로 설정하여 사람이 느리지 않다고 체감할 정도의 시간 규모로 CPU를 할당받을 수 있다.
• 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 (N-1) * Q시간 이내에 적어도 한 번의 CPU를 할당 받아 효과적이다.
  (최소 준비 큐의 프로세스 개수 N, 할당시간 Q)
• CPU 사용량에 비례해 소요시간이 증가하므로 공정한 스케줄링 방식이라고 할 수 있다.

 

📌 할당시간 (time quantum)

각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간

 

4-5. 멀티레벨 큐

📌 multi-level queue

준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법

• 일반적으로 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두게 된다.

 

📌 전위 큐 (foreground queue)

멀티레벨 큐에서 대화형 작업을 담기 위한 준비 큐

📌 후위 큐 (background queue)

멀티레벨 큐에서 계산 위주의 작업을 담기 위한 준비 큐

 

멀티레벨 큐에서는 여러 개의 준비 큐에 대한 스케줄링이 필요하다.

• 고정 우선순위 큐 (fixed priority scheduling)
  큐에 고정적인 우선순위를 부여해 해당 큐를 먼저 서비스하고, 우선순위가 높은 큐가 비어있을 때 낮은 큐를 서비스하는 방식
  • 큐에 대한 스케줄링으로 가장 쉬운 방법
• 타임 슬라이스 형식 (time slice)
  각 큐에 CPU 시간을 적절한 비율로 할당하는 방법 (ex. 전위 큐 80% / 후위 큐 20%)
  • 큐에 대한 기아 현상을 해소할 수 있는 방법

 

4-6. 멀티레벨 피드백 큐

📌 multi-level feedback queue

멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능한 방법

• 우선순위 스케줄링에서 기아 현상을 해결하기 위한 노화 기법을 멀티레벨 피드백 큐 방식으로 구현할 수 있다.

 

✍🏻 멀티레벨 피드백 큐를 정의하는 요소

• 큐의 수
• 각 큐의 스케줄링 알고리즘
• 프로세스를 상위 큐로 승격시키는 기준
• 프로세스를 하위 큐로 강등시키는 기준
• 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준

 

이러한 방식은 라운드 로빈 스케줄링을 발전시켜 프로세스 CPU 작업시간을 다단계로 분류함으로써 작업시간이 짧은 프로세스일수록 더욱 빠른 서비스를 가능하게 하고, 작업시간이 긴 프로세스에 대해서는 문맥교환 없이 CPU 작업에만 열중할 수 있는 방식을 채택할 수 있게 한다.

 

4-7. 다중처리기 스케줄링

📌 다중처리기 시스템 (multi-processor system)

CPU가 여러 개인 시스템

 

CPU가 하나인 시스템보다 더욱 복잡한 문제가 된다. 이떄는 프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내가도록 할 수 있다. 하지만 반드시 특정 CPU에서 수행되어야 하는 프로세스가 있을 경우 문제가 복잡해진다. 이런 상황에서는 각 CPU 별로 줄 세우기를 할 수도 있다. 한편 여러 줄로 줄 세우기를 하는 경우 일부 CPU에 작업이 편중되는 현상이 발생할 수 있다.

 

다중처리기 스케줄링에서는 이와 같은 현상 방지를 위해 각 CPU별 부하가 적절히 분산되도록 부하 균형(load balancing) 매커니즘을 필요로 한다.

 

✍🏻 다중처리기 스케쥴링의 방식

• 대칭형 다중처리 (symmetric multi-processing)
  각 CPU가 알아서 스케줄링을 결정하는 방식
• 비대칭형 다중처리 (asymmetric multi-processing)
  하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 거기에 따라 움직이는 방식

 

4-8. 실시간 스케줄링

실시간 시스템(Real-time system)에서는 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야 한다.

📌 경성 실시간 시스템 (hard real-time system)

미사일 발사, 원자로 제어 등 시간을 정확히 지켜야 하는 시스템

📌 연성 실시간 시스템 (soft real-time system)

데드라인이 존재하지만 지키지 않았다고 해서 위험한 상황이 발생하지 않는 시스템

• 멀티미디어 스트리밍 시스템 등

 

실시간 환경에서는 먼저 온 요청을 먼저 처리하기 보다는 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 널리 사용하게 된다.

 

5. 스케줄링 알고리즘 평가

✍🏻 스케줄링 알고리즘 성능 평가 방법

• 큐잉모델 (queueing model)
  • 주로 이론가들이 수행하는 방식
  • 확률분포를 통해 프로세스 도착률과 CPU 처리율을 입력 값으로 복잡한 수학적 계산을 통해 각종 성능지표(performance index)인 CPU 처리량, 프로세스 평균 대기시간 등을 구하는 방식
• 시뮬레이션 (simulation)
  • 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력 값으로 넣어 결과를 확인하는 방법
  • 입력 값은 가상으로 생성할 수도 있고, 실제 시스템 CPU 요청 내역(트레이스, Trace)을 추출해 사용할 수도 있다.
• 구현 및 실측 (implementation & measurement)
  • 이론가와 정반대인 구현가들이 수행할 수 있는 방식
  • 운영체제 커널의 소스 코드 중 CPU 스케줄링을 수행하는 코드를 수정해서 커널을 컴파일한 후 시스템에 설치하여 실제 실행시간을 측정하여 알고리즘 성능을 평가하는 방식

 

참고자료

• 책 - 운영체제와 정보기술의 원리 (반효경, 2020년 5월)