[OS] CPU 스케줄링

CPU 스케줄링

• CPU는 일반적으로 한 시스템 내에 하나씩 밖에 없으므로 여러 프로그램이 동시에 수행되는 시분할 환경에서 매우 효율적으로 관리되어야 하는 자원이다.

• CPU 버스트 (burst) : 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계이자 작업이다.
• I/O 버스트 (burst) : I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계이자 작업이다.
• CPU 바운드 프로세스(CPU bound process) : I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스를 말한다.

• I/O 바운드 프로세스(I/O bound process) : I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스를 말한다.

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

• CPU 바운드 프로세스에게 먼저 CPU를 할당한다면 그 프로세스가 CPU를 다 사용할 때까지 I/O 바운드 프로세스는 응답시간이 길어질 뿐만 아니라 해당 I/O 장치도 그 시간 동안 작업을 수행하지 않는 휴면 상태가 되기 때문에 비효율적이다. 따라서 CPU 스케줄링 시에 CPU 바운드 프로세스 보다는, I/O 바운드 프로세스에게 우선순위를 높여주는 것이 바람직하다.

1. CPU 스케줄러

• CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드이다. 프로세스가 CPU를 할당받고 기계어 명령을 수행하다가 타이머 인터럽트가 발생하면 CPU 스케줄러가 호출 된다. 그러면 CPU 스케줄러는 준비 큐에서 CPU를 기다리는 프로세스 중 하나를 선택해 CPU를 할당하게 된다.

• CPU 스케줄링 방식은 두가지가 있다.

  • 비선점형(nonpreemptive) 방식 : CPU를 휙득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법을 말한다.
  • 선점형 (preemptive) 방식 : 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법을 말한다. CPU를 빼앗는 방법으로는 할당시간(time quantum)을 부여한 후 타이머 인터럽트를 발생시키는 방법이 대표적이다.

2. 디스패처(dispatcher)

• CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지 결정하고나면 선택된 프로세스에게 실제로 CPU를 이양하는 작업이 필요하다. 이와 같이 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드를 디스패처라고 한다. 디스패처는 현재 수행중이던 프로세스의 문맥(context)를 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로 부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.

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

3. 스케줄링의 성능 평가

• 시스템 관점의 지표
  • CPU 이용률(CPU utilization) : 전체 시간 중에서 CPU가 일을 한 시간의 비율이다
  • 처리량(throughput) : 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇개를 끝마쳤는지(CPU 버스트를 완료한 프로세스의 개수)를 나타낸다.
• 사용자 관점의 지표
  • 소요시간(turnaround time) : 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간, 즉 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합을 뜻한다.
  • 대기시간(waiting time) : CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합을 뜻한다.
  • 응답시간(response time) : 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 얻기까지 기다린 시간을 뜻한다.

4. 스케줄링 알고리즘

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

• 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식을 말한다. 이 방식에서는 CPU를 먼저 요청한 프로세스에게 CPU를 먼저 할당하고, 그 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않는다.

• 단점 : CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 콘보이 현상(Convoy effect)이 발생한다.

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

• CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 이와 같은 할당 방식을 통해 CPU 버스트가 짧은 프로세스가 CPU를 먼저 사용하고 준비 큐를 빠져나가게 되면 프로세스들이 준비 큐에서 기다리는 전체적인 시간이 줄어들게 된다. 평균 대기시간을 가장 짧게 하는 스케줄링 방식이다.

• 현재 CPU 버스트 시간보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착할 경우 CPU를 빼앗게 된다.

• 일반적인 시분할 환경에서는 중간중간에 새로운 프로세스가 도착하는 경우가 발생하므로 선점형 방식이 평균 대기시간을 가장 많이 줄일 수 있는 방식이 된다.

• 단점 : CPU 버스트가 짧은 프로세스에게만 CPU를 할당할 경우 CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야 하는 기아 현상(starvation) 문제가 발생할 수 있다.

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

• 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식을 말한다. 이때 우선순위는 우선순위값(priority number)을 통해 표시한다.

• 단점 : 우선순위가 높은 프로세스가 계속 도착하는 상황에서 우선 순위가 낮은 프로세스는 CPU를 무한정 기다릴수 있는 기아 현상이 발생할 수 있다. 이를 해결하기 위해 기다리는 시간이 길어지면 우선순위를 높여가는 노화(aging) 기법을 사용할 수 있다.

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

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

• 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간을 할당 시간(time quantum)이라고 부른다.

• 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적이다. n개의 프로세스가 준비 큐에 있고 할당시간이 q라고 할때, 모든 프로세스는 (n - 1)q시간 이내에 적어도 한번은 CPU를 할당받을 수 있다. 그러므로 빠른 응답시간을 보장할 수 있다.

• 각 프로세스의 대기시간이 그 프로세스의 CPU 버스트 시간에 비례하므로 공정하고 합리적인 스케줄링이다.

• 라운드 로빈 스케줄링의 기본적인 목적은 CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 동시에, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것이다.

• 단점 : 할당시간을 너무 짧게 설정하면 문맥교환의 오버헤드가 증가해 전체 시스템의 성능을 저하시킬 수 있다.

• 유의할 점: 동일한 CPU 버스트 시간을 가지는 프로세스들에 라운드 로빈 스케줄링을 적용할 경우 평균 대기시간 및 평균 소요시간이 더 길어진다. 이럴 때는 FCFS가 더 효율적이다.

5) 멀티레벨 큐 (multi-level queue)

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

• 일반적으로 멀티레벨 큐에서 준비 큐는 대화형 작업을 담기 위한 ‘전위 큐’와 ‘후위 큐’를 둔다.
  • 전위 큐(foreground queue) : 응답시간을 짧게 하게 위해 라운드 로빈 스케줄링을 사용한다.
  • 후위 큐(background queue) : 응답시간이 큰 의미를 가지지 않기 때문에 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄인다.
• 여러 개의 준비 큐에 대해서 어느 큐에 CPU를 할당할 것인지 결정하는 스케줄링 방식으로 두가지가 있다.
  • 고정 우선순위 방식(fixed priority scheduling) : 전위 큐에 있는 프로세스에게 우선적으로 CPU가 할당되고 전위 큐가 비어있는 경우에만 후위 큐에 있는 프로세스에게 CPU가 할당된다.
  • 타임 슬라이스(time slice) : 큐에 대한 기아 현상을 해소할 수 있는 방식으로, 각 큐에 CPU 시간을 적절한 비율로 할당한다.

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

• CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.
• 프로세스들의 다양한 성격을 반영해 구현할 수 있다. 예를 들어 우선순위 스케줄링에서 기아 현상을 해결하기 위해 등장했던 노화 기법을 멀티레벨 피드백 큐 방식으로 구현할 수 있다. 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시키는 방식이 그것이다.

7) 다중처리기 스케줄링 (multi-processor system)

• CPU가 여러 개인 시스템인 다중처리기 시스템에서 일부 CPU에 작업이 편중되는 현상을 방지하기 위한 스케줄링이다.

• 각 CPU별 부하가 적절히 분산되도록 하는 부하균형(load balancing) 메커니즘을 필요로 한다.

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

8) 실시간 스케줄링 (real-time sysmtem)

• 실시간 시스템에서 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야할 때 사용되는 스케줄링이다. 두가지 방식으로 구분된다.
  • 경성 실시간 시스템 (hard real-time system) : 미사일 발사, 원자로 제어 등 정해진 시간안에 반드시 작업이 완료되도록 스케줄링해야 한다.
  • 연성 실시간 시스템 (soft real-time system) : 데드라인이 존재하기는 하지만 데드라인을 지키지 못했다고 해서 위험한 상황이 발생하지는 않는다. 멀티미디어 스트리밍 시스템이 대표적인 예이다.
• 먼저 온 요청을 처리하기보다는 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earliest Deadline First) 스케줄링이 널리 사용된다.

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

스케줄링 알고리즘의 성능을 평가하는 방식이 세 가지가 있다.

• 큐잉모델(queuing model) : 확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 주면 복잡한 수학적 계산을 통해 각종 성능지표(performance index)인 CPU의 처리량, 프로세스의 평균 대기시간 등을 구하게 된다.

• 구현 및 실측(implementation & measurement) : 동일한 프로그램을 원래 커널과 CPU 스케줄러를 수정한 커널에서 수행시켜보고 실행시간을 측정하여 알고리즘의 성능을 평가한다.

• 시뮬레이션(simulation) : 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떠한 결과가 나오는지 확인하는 방법이다.

참고

• 서적 ‘운영체제와 정보기술의 원리’