[OS] 06. CPU 스케줄링

CPU : 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙처리장치

 CPU는 프로그램이 시작되어 메모리에 올라가면 프로그램 카운터가 가리키는 주소의 기계어 명령을 하나씩 수행한다. 기계어 명령은 크게 3가지로 나뉜다.

 

①CPU 내에서 수행되는 명령

• CPU 내에서만 수행되므로 명령의 수행속도가 매우 빠르다.
• CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저장하는 Add 명령이 이에 해당.
• 사용자 프로그램이 직접 수행할 수 있는 일반명령에 해당한다.

②메모리 접근을 필요로 하는 명령

• CPU 내에서 수행되는 명령보다는 시간이 오래 소요되지만 비교적 짧은 시간에 수행할 수 있는 명령에 해당된다.
• 메모리에 있는 데이터를 CPU로 읽어들이는 Load명령, CPU에서 계산된 결괏값을 메모리에 저장하는 Store 명령이 이에 해당.
• 사용자 프로그램이 직접 수행할 수 있는 일반명령에 해당한다.

③입출력을 동반하는 명령

• 키보드로부터 입력을 받는다든지 컴퓨터에서 처리된 결과를 화면에 출력한다든지 하는 명령이 이에 해당.
• 입출력을 수반하는 명령은 CPU나 메모리 접근 명령에 비해 대단히 오랜 시간이 소요된다.
• 특권명령으로 규정되어 사용자 프로그램이 직접 수행할 수 없고 운영체제를 통해 명령이 수행된다.

 

 사용자 프로그램은 CPU 작업과 I/O 작업의 반복으로 구성된다. 프로그램의 수행은 다음과 같은 두 단계의 조합으로 이루어진다.

 

① CPU 버스트(burst)

• 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계
• I/O를 한 번 수행한 후 다음 번 I/O를 수행하기까지 직접 CPU를 가지고 명령을 수행하는 작업

② I/O 버스트(burst)

• I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
• I/O 작업이 요청된 후 완료되어 다시 CPU 버스트로 돌아가기까지 일어나는 일련의 작업

CPU 버스트와 I/O 버스트의 모습

 

 어떤 프로세스는 I/O 버스트가 빈번해 CPU 버스트가 매우 짧게 나타나는 반면, 또 다른 프로세스는 I/O를 거의 하지 않아 CPU 버스트가 매우 길게 나타난다. 이와 같은 기준으로 프로세스를 다음과 같이 나눌 수 있다.

 

① I/O 바운드 프로세스

• I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스를 말한다.
• 주로 사용자로부터 인터랙션(interaction)을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램(interactive program)이 해당된다.
• 짧은 CPU 버스트를 많이 가지고 있다.

② CPU 바운드 프로세스

• I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스를 말한다.
• 상당 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램이 해당된다.
• 소수의 긴 CPU 버스트로 구성된다.

 이와 같이 CPU 버스트가 균일하지 않은 다양한 프로그램들이 공존하므로 효율적인 CPU 스케줄링 기법이 반드시 필요하다. 대부분의 프로세스는 짧은 CPU 버스트를 가지며, 극히 일부분만 긴 CPU 버스트를 가진다. 사용자와의 인터랙션을 통해 수행되는 대화형 프로그램의 경우 사용자에게 입력을 받아 CPU 연산을 수행하고 그 결과를 다시 출력하는 작업을 수행한다. 이러한 작업은 CPU의 빠른 서비스를 필요로 한다. 이는 사용자에 대한 빠른 응답이 중요하기 때문이다. 

 따라서 CPU 스케줄링을 할 때 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있도록 하는 스케줄링이 필요하다. 즉, I/O 바운드 프로세스의 우선순위를 높여주는 것이 좋다. 이를 통해 사용자에게 빠른 응답을 제공할 수 있을 뿐만 아니라 I/O 장치의 효율성 역시 높일 수 있다. 

 

1. CPU 스케줄러

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

 

 프로세스가 CPU를 할당 받고 명령을 수행하다가 타이머 인터럽트가 발생하면 CPU 스케줄러가 호출된다. 그러면 CPU 스케줄러는 준비 큐에서 CPU를 기다리는 프로세스 중 하나를 선택해 CPU를 할당하게 된다. 이 밖에도 CPU 스케줄링이 필요한 대표적인 경우는 다음과 같다.

1. 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄(blocked) 상태로 바뀌는 경우 -> 비선점형 방식
2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우 -> 선점형 방식
3. I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우 -> 선점형 방식
   • 단, I/O 작업이 완료된 프로세스가 인터럽트 당한 프로세스보다 우선순위가 높아, 인터럽트 처리 후 이전에 수행되던 프로세스가 아닌 I/O 작업이 완료된 프로세스로 CPU가 할당되는 경우에 해당
4. CPU에서 실행 상태에 있는 프로세스가 종료되는 경우 -> 비선점형 방식

 

CPU 스케줄링 방식에는 두 가지 방식이 있다.

 

① 비선점형(Nonpreemptive) 방식

- CPU를 획득한 프로세스가 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법

 

② 선점형(preemptive) 방식

- 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법

 

2. 디스패처

CPU 스케줄러에 의해 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드

 

 디스패처는 현재 수행 중이던 프로세스의 문맥(context)을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다. 

 

 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 디스패치 지연시간(dispatch latency)이라고 하며, 이 시간의 대부분은 문맥교환 오버헤드에 해당된다.

 

3. 스케줄링의 성능 평가

 스케줄링 기법의 성능 평각에 있어서 크게 다음과 같이 나누어볼 수 있다.

 

시스템 관점의 지표

① CPU 이용률(CPU utilization)

• 전체 시간 중에서 CPU가 일을 한 시간의 비율 
• CPU가 idle 상태에 머무르는 시간을 최대한 줄이는 것이 스케줄링의 중요한 목표가 된다.

② 처리량(throughput)

• 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지를 나타낸다(CPU 버스트를 완료한 프로세스의 개수)
• 즉, CPU의 서비스를 원하는 프로세스 중 몇 개가 원하는 만큼의 CPU를 사용하고 이번 CPU 버스트를 끝내어 준비 큐를 떠났는지 측정한 것 

 

사용자 관점의 지표

① 소요시간(turnaround time)

• 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간
  (준비 큐에서 기다린 시간 + 실제로 CPU를 사용한 시간)
• 프로그램이 시작해 종료하는 데까지 걸리는 시간이 아님!!!

② 대기시간(waiting time)

• CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
• 시분할 시스템에서는 한 번의 CPU 버스트 중에도 준비 큐에서 기다린 시간이 여러 번 발생할 수 있다. 
• 이번 CPU 버스트가 끝나기까지 준비 큐에서 기다린 시간의 합을 뜻한다.

③ 응답시간(response time)

• 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간
• 대화형 시스템에 적합한 성능 척도로서 사용자 입장에서 가장 중요한 성능 척도라 할 수 있다.

 

4. 스케줄링 알고리즘

1) 선입선출(First-Come First-Served: FCFS) 스케줄링

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

 FCFS의 경우 CPU 버스트가 긴 프로세스가 먼저 도착할 경우 비효율적인 결과를 초래할 가능성이 있다. CPU 버스트가 짧은 프로세스들이 CPU 버스트가 긴 프로세스의 작업을 기다리느라 평균 대기시간이 길어지게 되며 이로 인해 I/O 장치들의 이용률까지도 동반 하락하게 된다.

 

 이처럼 FCFS 스케줄링은 CPU 버스트가 긴 프로세스가 먼저 도착할 경우 평균 대기시간이 길어지는 반면, CPU 버스트가 짧은 프로세스가 먼저 도착하게 되면 평균 대기시간은 짧아지게 된다. CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상을 콘보이 현상(Convoy effect)라고 한다.

 

2) 최단작업 우선(Shortest-Job First: SJF) 스케줄링

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

 

 최단작업 우선 스케줄링은 평균 대기시간을 가장 짧게 하는 최적 알고리즘으로 알려져 있다. SJF 알고리즘은 비선점형 방식과 선점형 방식 두 가지로 구현될 수 있다.

 

※ 비선점형 방식

• 일단 CPU를 획득하면 그 프로세스가 자진 반납하기 전까지는 CPU를 빼앗지 않는 방식

 

※ 선점형 방식

• CPU 버스트가 더 짧은 프로세스가 도착할 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여하는 방식 
• 이러한 방식을 SRTF(Shortest Remaining Time First)라고 부른다.

 

 SJF 스케줄링 기법은 프로세스의 CPU 버스트 시간을 미리 알 수 없기 때문에 현실적으로 구현이 어렵다. 또한 준비 큐에서 CPU 할당을 기다리고 있는 A 프로세스보다 CPU 버스트가 짧은 프로세스가 계속 도착할 경우 A 프로세스는 영원히 CPU를 할당받지 못하는 문제가 발생할 수 있다(이를 기아 현상이라고 한다).

 

3) 우선순위(Priority) 스케줄링

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

 

 우선순위 스케줄링도 현재 CPU에서 수행 중인 프로세스보다 우선순위가 높은 프로세스가 도착했을 때 CPU를 이양할 것인지 아닌지에 따라 선점형 방식과 비선점형 방식으로 구현할 수 있다.

 

 우선순위 스케줄링의 문제점 중 하나는 기아 현상이 발생할 수 있다는 점이다. 우선순위가 높은 프로세스가 계속해서 도착하면 상대적으로 우선순위가 낮은 프로세스는 CPU를 할당받지 못하게 된다. 이를 해결하기 위해 노화(aging) 기법을 사용할 수 있다. 이는 기다리는 시간이 길어지면 해당 프로세스의 우선순위를 조금씩 높여, 언젠가는 CPU를 할당받을 수 있게 해주는 방법이다.

 

4) 라운드 로빈(Round Robin) 스케줄링

 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 정해져있으며, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다.

 

 라운드 로빈에서 사용되는 CPU를 연속적으로 사용할 수 있는 최대시간을 할당시간(time quantum)이라고 부른다. 할당시간이 너무 길면 FCFS와 같아지고 너무 짧으면 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 커져 시스템의 성능을 저하시킬 수 있다.

 

 라운드 로빈방식을 사용하면 CPU를 많이 쓰는 프로세스는 대기시간이 그에 비례해서 길어지고, 반대로 CPU를 적게 쓰는 프로세스는 대기시간도 짧아지게 된다. 일반적으로 SJF 방식보다 평균 대기 시간은 길지만 응답시간은 더 짧다. 

 

 할당시간이 만료되어 CPU를 회수하는 방법으로는 타이머 인터럽트를 사용하게 된다. 만약 CPU 버스트 시간이 할당시간보다 짧으면 CPU를 다 사용한 후 스스로 반납하게 된다. 라운드 로빈 스케줄링의 기본적인 목적은 CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것이다.

 

 

5) 멀티레벨 큐(Multi-Level Queue)

준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법. 즉, 프로세스들이 CPU를 기다리기 위해 여러 줄로 서 있는 것을 말한다.

 

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

멀티레벨 큐의 모습

 일반적으로 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영된다.

 

※ 전위 큐

- 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용한다.

 

※ 후위 큐

- 응답시간이 큰 의미를 가지지 않기 때문에 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄이도록 한다.

 

 

 멀티레벨 큐에서는 큐 자체에 대한 스케줄링 역시 필요하다. 여러 개의 준비 큐에 대해서 어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링이 필요한데 고정 우선순위 방식(fixed priority scheduling)과 타임 슬라이스(time slice) 방식이 있다.

 

※ 고정 우선순위 방식

- 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어 있을 때에만 서비스한다.

- 전위 큐와 후위 큐를 사용할 경우, 전위 큐에게 우선적으로 CPU가 할당되고, 전위 큐가 비어 있는 경우에만 후위 큐에 CPU가 할당된다.

 

※ 타임 슬라이스 방식

- 큐에 대한 기아 현상을 해소할 수 있는 방식.

- 각 큐에 CPU 시간을 적절한 비율로 할당한다.

 

 

6) 멀티레벨 피드백 큐 (Multilevel Feedback Queue)

멀티레벨 큐와 같이 여러 큐가 존재한다는 것은 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.

 

 멀티레벨 피드백 큐에서는 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시키는 방식으로 우선순위 스케줄링에서 발생했던 기아 현상을 해결할 수 있다.

 

멀티레벨 피드백 큐의 모습

 멀티레벨 피드백 큐의 대표적인 방식은 위의 그림과 같다. 상위에 있는 큐일수록 우선순위가 높으며 프로세스가 준비 큐에 도착하면 우선순위가 가장 높은 큐에 줄을 선다. 위의 큐에서 작업을 완료하지 못한 프로세스는 두 번재 큐로 내려가고 거기에서도 작업을 완료하지 못하면 마지막 큐로 내려가게 된다.

 큐에 대한 스케줄링은 최상위 큐가 우선적으로 CPU를 할당받고, 상위 큐가 비었을 때에만 하위 큐에 CPU가 할당된다. 

 

 멀티레벨 피드백 큐는 작업시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하도록 하고, 작업시간이 긴 프로세스에 대해서는 문맥교환 없이 CPU 작업에만 열중할 수 있는 FCFS 방식을 채택할 수 있게 한다.

 

7) 다중처리기 스케줄링

 CPU가 여러 개인 시스템에서의 CPU 스케줄링.

 

 프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내어가도록 할 수 있다. 하지만 특정 CPU에서 수행되어야 하는 프로세스가 있을 수도 있다. 이런 상황에서는 한 줄이 아니라 각 CPU 별로 줄 세우기를 할 수도 있다.

 

 여러 줄로 줄 세우기를 하는 경우 일부 CPU에 작업이 편중되는 현상이 발생할 수 있다. 이를 방지하기 위해 각 CPU별 부하가 적절히 분산되도록 하는 부하균형(load balancing) 메커니즘이 필요하다. 

 

 다중처리기 스케줄링은 대칭형 다중처리(symmetric multi-programming)와 비대칭형 다중처리(asymmetric multiprogramming)로 나누어볼 수 있다. 전자는 각 CPU가 각자 알아서 스케줄링을 결정하는 방식이고, 후자는 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 거기에 따라 움직이는 방식을 말한다.

 

 

Reference

운영체제와 정보기술의 원리 - 교보문고