[OS] CPU 스케줄링

_ KOCW 반효경 교수님 운영체제 강의와 도서를 정리한 내용입니다._

CPU 스케줄링이 필요한 이유?

CPU 버스트 시간은 사용자 프로그램이 CPU를 직접 이용하여 명령을 수행하는 시간을 의미한다.

x축이 CPU 버스트 시간이고 y축이 빈도인 그래프를 살펴보면, 왼쪽은 CPU 버스트 시간이 짧은 작업 (입출력 요청 후 바로 다른 CPU로 전환)인 IO 바운드 프로세스이며, 오른쪽은 CPU 점유 시간이 긴 CPU 바운드 프로세스이다.

만약 모든 프로세스가 동일하다면 수행하는 작업에 따라 응답 시간의 차이는 없을 것이다. 하지만 위 그래프처럼 CPU 점유 시간이 긴 프로세스와 짧은 프로세스가 존재하기에, CPU 버스트 시간이 짧은 프로세스에게 우선적으로 CPU를 할당할 수 있는 스케줄링이 필요하다. (이렇게 할 경우, 전체 대기 시간이 줄어들기 때문이다.)

CPU 스케줄러

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

• 비선점형 방식 : CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
• 선점형 방식 : 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법

  디스패처

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

  스케줄링 성능 평가

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

  스케줄링 알고리즘

  선입선출 알고리즘 (FCFS)

  
  비선점형 스케줄러로 먼저 온 프로세스가 먼저 실행된다. 이때의 문제점은 CPU 버스트 타임이 긴 프로세스가 먼저 오면 다른 프로세스가 모두 길게 기다려야한다는 것이다. 즉, 대기시간 총합이 길어진다.

우리는 대기 시간을 줄이기 위해 CPU 버스트 타임이 짧은 것을 우선으로 실행시켜야한다.

최단작업 알고리즘 (SJF)

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 평균 대기시간을 가장 짧게 하는 최적 알고리즘이다.

방식에 따라 선점형, 비선점형 스케줄러가 될 수 있다.

• 선점형 : 버스트 타임이 더 짧은 프로세스가 오면 빼앗긴다. 프로세스가 새롭게 도착하거나 작업이 끝날 때마다 CPU 버스트 시간을 비교한다.
• 비선점형 : 버스트 타임이 더 짧은 프로세스가 와도 그대로 실행한다.

SJF 알고리즘을 쓴다면 좋겠지만 안타깝게도 여러 문제가 존재한다.

• Starvation : CPU 버스트 타임이 긴 프로세스는 영원히 CPU를 할당 받지 못할수도 있다.
• 버스트 타임 예측 불가 : 과거의 기록을 통해 유추를 하기도 한다.

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

  우선순위가 높은 프로세스를 먼저 실행시키는 스케줄링 방식이다. 최단 작업 알고리즘과 유사하게, 우선순위가 낮은 프로세스는 계속 실행되지 않을 수 있는 Starvation 문제가 발생할 수 있지만, 이는 Aging 기법을 통해 해결할 수 있다. Aging 기법은 대기 시간이 길어질수록 우선순위를 점진적으로 높여, 결국 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 하는 방법이다.

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

  선점형 스케줄러로 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다. 버스트 타임이 긴 프로세스가 전체를 위해 희생하는 모습을 보인다.
  
  할당시간을 길게 설정하는 경우 선출선입 스케줄링과 동일해지며 대기시간이 길어진다. 그렇다고 해서 너무 짧게 잡으면 Context Switching 이 빈번하게 일어나 오버헤드가 발생한다. 기본적으로 라운드로빈은 SJF 스케줄링 보다 대기시간은 길지만 응답시간은 짧다.

할당시간이 만료되어 CPU를 회수하는 방법으로는 타이머 인터럽트를 사용하게 된다.

멀티 레벨 큐 (Multi Level Queue)

준비 큐를 여러개로 분할해 관리하는 스케줄링 기법이다. 각각의 큐를 어떻게 스케줄링할지와 어떠한 큐에게 먼저 cpu를 할당할지에 대한 스케줄링이 필요하다. 먼저 큐 자체의 스케줄링에 대한건 다음과 같다.

• 전위 큐 (foreground queue) : 유저와의 대화형 작업을 담기 위한 큐로 빠른 응답 시간을 갖어야하기 때문에 라운드 로빈 기법을 쓴다.
• 후위 큐 (background queue) : 계산 위주의 작업을 위한 큐로 응답 시간이 큰 의미를 갖지 않는다. 따라서 선입선출 큐로 컨텍스트 스위칭 오버헤드를 줄이는 방법을 택한다.

다음으로는 어떠한 큐에게 CPU를 먼저 할당할지에 대한 문제인데 제일 쉽게 생각할 수 있는 방법은 고정 우선순위 방식 (Fixed Priority Scheduling) 이다. 우선 순위가 높은 전위 큐에 먼저 할당하는 방식이다.

이 외에는 타임 슬라이스 방식도 사용할 수 있다. 큐에 대한 Starvation 문제를 해소할 수 있는 방식으로 각 큐에 CPU 시간을 적절한 비율로 할당하는 방식이다.

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

멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다. 우선순위 스케줄링 기법에서 Starvation 현상을 해결하기 위해 등장했던 Aging 기법을 멀티 레벨 피드백 큐로 구현할 수 있다. 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시키는 방식이 그것이다.

프로세스가 준비큐에 도착하면 우선순위가 가장 높은 큐에 줄을 선다. 우선순위가 높은 큐는 라운드 로빈 스케줄링을 사용하기 때문에 버스트 타임이 작으면 빨리 끝나지만 아니라면 작업이 끝나지 못한다.

따라서 하위 큐로 내려가서 줄을 서게 된다. 하위 큐는 상위 큐보다 quantum time 이 크다. 여기서도 안 끝나게된다면 최하위 큐로 내려가는데 최하위 큐는 FCFS 스케줄링을 쓴다.

큐에 대한 스케줄링 방식으로는 최상위 큐가 우선적으로 CPU를 할당받는 방식이다. 이러한 방식을 이용하면 작업시간이 짧은 스케줄링은 빠르게 서비스가 가능하고, 작업시간이 긴 프로세스에 대해서는 문맥교환없이 CPU 작업에만 열중할 수 있도록 FCFS 를 택한다.