5. CPU 스케쥴링

0. CPU 기본

• CPU의 기계어 명령에는 크게 CPU 내에서 수행되는 명령, 메모리 접근을 필요로 하는 명령, 입출력을 동반하는 명령으로 나눌 수 있다.
  • CPU 내에서 수행되는 명령의 예로는 레지스터에 있는 두 값을 더해 레지스터에 저장하는 Add 명령이 있다.
  • 메모리 접근을 필요로 하는 명령으로는 Load 명령과 Store 명령이 있다. Load 명령은 메모리에 있는 데이터를 CPU로 읽어들이는 명령이고, Store 명령은 CPU에서 계산된 결과값을 메모리에 저장하는 명령이다.
  • CPU 내에서 일어나는 명령이나 메모리를 접근하는 명령은 소요 시간이 비교적 짧고, 일반명령에 해당한다.
  • 입출력을 동반하는 명령은 오랜 시간이 소요되고, 특권명령이다.
• 프로그램의 수행은 크게 두 단계로 나뉜다.
  • CPU 버스트(burst) : 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 단계
  • I/O 버스트(burst) : I/O 요청이 발생해 커널에 의해 입출력 작업을 수행하는 비교적 느린 단계
  • 즉, CPU 버스트는 I/O를 한 번 수행한 후 다음 번 I/O를 수행하기까지 직접 CPU를 가지고 명령을 수행하는 작업을 말하고, I/O 버스트는 I/O 작업이 요청된 후 완료되어 다시 CPU 버스트로 돌아가기까지 일어나는 작업을 말한다.
• 각 프로그램마다 CPU 버스트와 I/O 버스트의 비율에 따라 두 가지로 나눌 수 있다.
  • I/O 바운드 프로세스 : I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스. 주로 사용자로부터 인터랙션(interaction)을 계속 받아가며 프로그램을 수행하는 대화형 프로그램(interactive program)이 해당된다.
  • CPU 바운드 프로세스 : I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스. 프로세스 수행의 상당 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램이 해당된다.
  • I/O 바운드 프로세스는 짧은 CPU 버스트를 많이 가지고 있고, CPU 바운드 프로세스는 소수의 긴 CPU 버스트를 가지고 있다.
• 이와 같은 패턴으로 CPU를 사용하는 여러 프로그램이 동일한 시스템 내부에서 함께 실행되기 때문에 CPU 스케쥴링이 필요하다.
• 보통 대부분의 경우 짧은 CPU 버스트를 가지고, 극히 일부분만 긴 CPU 버스트를 가진다. 특히 CPU 버스트가 짧은 프로세스는 주로 대화형 작업으로 사용자와 인터렉션을 하며 프로그램을 수행시키기에 CPU의 빠른 서비스를 필요로 한다.
• 그러므로 CPU 스케쥴링 시 I/O 바운드 프로세스의 우선순위를 높여주는 것이 바람직하다. 이를 통해 I/O 장치의 효율성도 높일 수 있다.

1. CPU 스케쥴러

• CPU 스케쥴러 : 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드
• CPU 스케쥴러가 필요한 경우는 다음과 같다.
  • 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우
  • 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
  • I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우
  • CPU에서 실행 상태에 있는 프로세스가 종료되는 경우
• CPU 스케쥴링 방식에는 비선점형과 선점형 방식이 있다.
  • 비선점형(nonpreemptive) : CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
  • 선점형(preemptive) : 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케쥴링 방법. CPU를 빼앗는 방법으로는 할당시간을 부여한 후 타이머 인터럽트를 발생시키는 방법이 대표적이다.

2. 디스패처

• 디스패처(dispatcher) : CPU 스케쥴러가 CPU를 할당하기로 결정한 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드
• 디스패처는 현재 수행 중인 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.
• 디스패치 지연시간(dispatch latency) : 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간. 대부분은 문맥교환 오버헤드에 해당된다.

3. 스케쥴링의 성능 평가

• 스케쥴링의 성능 평가의 지표는 크게 시스템 관점의 지표와 사용자 관점의 지표로 나눌 수 있다.
• 시스템 관점의 지표로는 CPU 이용률과 처리량이 있고, 사용자 관점의 지표로는 소요시간, 대기시간, 응답시간 등 기다린 시간과 관련된 지표들이 있다.
• CPU 이용률(CPU utilization) : 전체 시간 중 CPU가 일을 한 시간의 비율. CPU가 휴면(idle) 상태에 머무르는 시간을 최대한 줄이는 것이 스케쥴링의 중요한 목표가 된다.
• 처리량(thoroughput) : 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지를 나타낸다. 이를 개선하려면 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리하다.
• 소요 시간(turnaround time) : 준비 큐에서 기다린 시간 + 실제로 CPU를 사용한 시간. 이는 해당 CPU 버스트가 완료될 때까지 걸린 시간으로 프로그램이 시작해 종료하는 데까지 걸리는 시간이 아니다. 실제로는 프로그램이 시작해서 종료할 때까지 CPU 버스트가 여러 차례 있을 수 있다.
• 대기 시간(waiting time) : CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합. 시분할 시스템에서는 하나의 CPU 버스트가 끝날 때까지 준비 큐에서 기다린 시간이 여러 번 발생할 수 있다.
• 응답 시간(response time) : 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간. 타이머 인터럽트가 빈번히 발생할수록 각 프로세스가 처음 CPU를 얻기까지 걸리는 시간이 줄어들기 때문에 응답시간이 향상된다. 그래서 응답시간은 대화형 시스템에 적합한 성능 척도이다.

4. 스케쥴링 알고리즘

• 선입선출(First-Come First-Served) 스케쥴링 : 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
  • 먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 달라진다. CPU 버스트가 긴 프로세스가 먼저 도착할 경우 평균 대기시간이 길어진다.
  • 콘보이 현상(Convoy effect) : CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상. FCFS 스케쥴링의 대표적인 단점이다.
• 최단작업 우선(Shortest-job First) 스케쥴링 : CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
  • 평균 대기시간을 가장 짧게 하는 최적 알고리즘이다.
  • SJF 알고리즘은 비선점형 방식과 선점형 방식으로 구현될 수 있다. 특히 선점형 방식의 경우 CPU 버스트가 가장 짧은 프로세스에게 CPU를 할당했다 하더라도, CPU 버스트가 더 짧은 프로세스가 도착하면 그 프로세스에게 CPU를 부여한다. 이를 SRTF(Shortest Remaining Time First)라고도 부른다.
  • 일반적으로 중간중간에 새로운 프로세스가 도착하는 경우가 발생하므로 선점형 방식이 평균 대기시간을 가장 많이 줄일 수 있는 방식이다.
  • 하지만 현실적으로 프로세스의 CPU 버스트 시간을 미리 알 수 없다. 그래서 예측을 통해 CPU 버스트 시간을 구한 후 예측치가 가장 짧은 프로세스에게 CPU를 할당한다.
  • (n+1)번째 CPU 버스트의 예측시간 T(n+1) = at(n) + (1-a)T(n)으로 계산한다. t(n)은 실제 n번째 CPU 버스트 시간을, a는 0과 1 사이의 상수로 두 요소를 어느 정도씩 반영할지 조절하는 매개변수이다.
  • 이는 최근의 CPU 버스트 시간일수록 가중치를 높이는 방식이다.
  • 기아 현상(starvation) : CPU 버스트가 긴 프로세스가 준비 큐에서 무한정 기다리게 되는 현상으로 SJF 알고리즘의 심각한 문제점이다.
• 우선순위 스케쥴링(priority scheduling) : 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
  • 우선순위는 우선순위값(priority number)을 통해 표시하고 우선순위값이 작을수록 높은 우선순위를 가지는 것으로 가정한다.
  • CPU 버스트 시간을 우선순위값으로 정의하면 SJF 알고리즘과 동일하다.
  • 우선순위 스케쥴링도 기아 현상이 발생할 수 있으나 이를 해결하기 위해 노화 기법을 사용할 수 있다.
  • 노화(aging) 기법 : 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법
• 라운드 로빈 스케쥴링(Round Robin Scheduling) : 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 특정 시간으로 제한하고 이 시간이 경과할 시 해당 프로세스로부터 CPU를 회수하고 준비 큐의 다른 프로세스에게 CPU를 할당하는 방식
  • 시분할 시스템의 성질을 가장 잘 활용한 스케쥴링 방식이다.
  • 할당시간(time quantum) : 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간
  • 할당시간이 너무 길면 FCFS와 같고, 할당시간이 너무 짧으면 문맥교환 오버헤드가 커진다. 따라서 일반적으로 할당시간을 수십 밀리초 정도의 규모로 설정한다.
  • 라운드 로빈 스케쥴링은 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적이다.
  • n개의 프로세스가 준비 큐에 있고 할당시간이 q면 모든 프로세스는 (n-1)q시간 내에 적어도 한 번은 CPU를 할당받는다.
  • 프로세스의 대기시간이 그 프로세스의 CPU 버스트 시간에 비례하게 된다. CPU 버스트 시간이 길수록 실행되다가 준비 큐로 되돌아가는 횟수가 증가하기 때문이다.
• 멀티레벨 큐(multi-level queue) : 준비 큐를 여러 개로 분할해 관리하는 스케쥴링 기법
  • 일반적으로 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케쥴링을 적용하기 위해 준비 큐를 별도로 둔다.
  • 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영된다.
  • 전위 큐에서는 응답 시간을 짧게 하기 위해 라운드 로빈 스케쥴링을 사용하고, 후위 큐에서는 응답 시간이 큰 의미를 가지지 않아 FCFS 스케쥴링 기법을 사용해 문맥교환 오버헤드를 줄인다.
  • 큐 자체에 대한 스케쥴링도 필요한데, 여기에는 고정 우선순위 방식과 타임 슬라이스 방식이 있다.
  • 고정 우선순위 방식 : 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하는 방식
  • 타임 슬라이스 방식 : 큐에 대한 기아 현상을 해소하기 위해 각 큐에 CPU 시간을 적절한 비율로 할당하는 방식
• 멀티레벨 피드백 큐(Multilevel Feedback Queue) : 멀티레벨 큐와 유사하나 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다.
  • 프로세스들의 다양한 성격을 반영해 구현할 수 있다. 예를 들어 우선순위가 낮은 큐에서 오래 기다린 경우 우선순위가 높은 큐로 승격시키는 방식을 사용할 수 있다.
  • 멀티레벨 피드백 큐를 정의하는 요소들로는 큐의 수, 각 큐의 스케쥴링 알고리즘, 프로세스를 상위 큐(하위 큐)로 승격(강등)시키는 기준, 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준 등이 있다.
• 다중처리기 스케쥴링(multi-processor scheduling) : CPU가 여러 개인 다중처리기 시스템에서의 스케쥴링을 말한다.
  • 한 CPU 당 하나의 큐를 대응시켜 여러 개의 큐를 만드는 경우 일부 CPU에만 작업이 편중될 수 있어 CPU별 부하가 적절히 분산되도록 하는 부하균형(load balancing) 매커니즘을 필요로 한다.
  • 다중처리기 스케쥴링의 방식은 각 CPU가 각자 알아서 스케쥴링을 결정하는 대칭형 다중처리와 하나의 CPU가 다른 모든 CPU의 스케쥴링 및 데이터 접근을 책임지는 비대칭형 다중처리로 나눌 수 있다.
• 실시간 스케쥴링(real-time scheduling) : 실시간 시스템에 적용되는 스케쥴링으로 각 작업마다 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야 한다.
  • 실시간 시스템에는 경성 실시간 시스템과 연성 실시간 시스템이 있다.
  • EDF(Earliest Deadline First) 스케쥴링 : 데드라인이 얼마 남지 않은 요청을 우선적으로 처리하는 방식
• 스레드 스케쥴링(Thread Scheduling)
  • Local Scheduling : user level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케쥴할지 결정한다.
  • Global Scheduling : kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 thread를 스케쥴할지 결정한다.

5. 스케쥴링 알고리즘의 평가

• 스케쥴링 알고리즘의 성능 평가 방법으로 큐잉모델, 시뮬레이션, 구현 및 실측 방식이 있다.
• 큐잉모델(queueing model) : 확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 받아 복잡한 수학적 계산을 통해 각종 성능지표인 CPU의 처리량, 프로세스의 평균 대기시간 등을 구하는 방법
• 구현 및 실측(implementation and measurement) : 동일한 프로그램을 원래 커널과 CPU 스케쥴러를 수정한 커널에 수행시켜보고 실행시간을 측정해 알고리즘 성능을 평가하는 방법
• 시뮬레이션(simulation) : 가상으로 CPU 스케쥴링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떤 결과가 나오는지 확인하는 방법

 

출처 : 운영체제와 정보기술의 원리