books/OS

[OS] CPU 스케줄링

836586697769 2024. 3. 26. 12:48

@notion

<운영체제와 정보기술의 원리> 반효경 저

 

프로그램 실행과 관련된 기계어 명령은 크게 세 가지로 나뉜다.

  • CPU 내에서 수행되는 명령
    • e.g. Add 명령: CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저장
    • CPU 내에서만 수행되므로 명령의 수행 속도가 매우 빠름
    • 사용자 프로그램이 직접 실행할 수 있는 일반명령에 해당
  • 메모리 접근을 수행하는 명령
    • e.g. Load: 메모리에 있는 데이터를 CPU로 읽어들임
    • e.g. Store: CPU에서 계산된 결괏값을 메모리에 저장
    • 전자보다는 시간이 오래 소요되지만 비교적 짧은 시간에 수행 가능
    • 사용자 프로그램이 직접 실행할 수 있는 일반명령에 해당
  • 입출력을 동반하는 명령
    • 오랜 시간이 소요됨
    • 특권 명령이기 때문에 운영체제를 통해 서비스를 대행

사용자 프로그램이 수행되는 과정은 CPU를 직접 가지고 빠른 명령을 수행하는 단계와 I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계의 반복으로 구성된다.

  • 전자를 CPU 버스트, 후자를 I/O 버스트라고 부름

각 프로그램마다 CPU 버스트와 I/O 버스트가 차지하는 비율이 균일하지는 않다.

  • I/O 바운드 프로세스: I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
    • 주로 사용자로부터 인터랙션을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램이 해당
    • 짧은 CPU 버스트를 많이 가지고 있음
  • CPU 바운드 프로세스: I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스
    • 프로세스 수행의 상당 시간을 CPU 작업에 소모하는 계산 위주의 프로그램이 해당
    • 소수의 긴 CPU 버스트로 구성

우리가 사용하는 시분할 시스템에서는 이와 같이 CPU 버스트가 균일하지 않은 다양한 프로그램들이 공존하므로 효율적인 CPU 스케줄링 기법이 반드시 필요하다.

CPU 스케줄링을 할 때 CPU 버스트가 짧은 I/O 바운드 프로세스에 우선적으로 CPU를 사용할 수 있도록 하는 스케줄링이 바람직하다. 대화형 프로세스의 빠른 응답성 제공 외에, CPU를 잠깐만 사용한 후 곧바로 I/O 작업을 수행할 수 있으므로 I/O 장치의 이용률이 높아지기 때문이다.

 

1. CPU 스케줄러

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

1. 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우, 2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우, 3. I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우, 4. CPU에서 실행 상태에 있는 프로세스가 종료되는 경우, 호출된 CPU 스케줄러가 준비 큐에서 CPU를 기다리는 프로세스 중 하나를 선택에 CPU를 할당한다.

CPU 스케줄링 방식에는 비선점형 방식과 선점형 방식이 있다.

  • 비선점형(nonpreemptive): CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법 (e.g. 위의 1, 4)
  • 선점형: 프로세스가 CPU를 계속 사용하기를 원해도 강제로 뺏을 수 있는 방법 (e.g. 위의 2, 3)

 

2. 디스패처

CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지 결정하면 선택된 프로세스에게 실제로 CPU를 이양하는 작업이 필요하다.

  • 디스패처(dispatcher): 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드
  1. 디스패처는 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고
  2. 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후
  3. 시스템의 상태를 사용자모드로 전환해 사용자 프로그램에게 CPU의 제어권을 넘긴다.
  4. 사용자 프로그램은 복원된 문맥 중 프로그램 카운터로부터 현재 수행할 주소를 찾는다.
  • 디스패치 지연시간: 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간으로, 대부분 문맥교환 오버헤드에 해당

 

3. 스케줄링의 성능 평가

  • 시스템 관점의 지표
    • CPU 이용률(CPU utilization): 전체 시간 중 CPU가 일을 한 시간의 비율로, CPU가 휴먼(idle) 상태에 머무르는 시간을 최대한 줄이는 것이 스케줄링의 중요한 목표
    • 처리량(throughput): 주어진 시간 동안 CPU 버스트를 완료한 프로세스의 개수를 나타내며, 주어진 시간에 더 많은 프로세스들이 CPU 작업을 완료하기 위해 CPU 버스트가 짧은 프로세스에 우선적으로 CPU를 할당하는 것이 유리
  • 사용자 관점의 지표
    • 소요시간(turnaround time): 프로세스가 CPU를 요청한 시점부터 해당 CPU 버스트가 끝날 때까지 걸린 시간
    • 대기시간(waiting time): CPU 버스트 기간 중 이번 CPU 버스트가 끝날 때까지 준비 큐에서 기다린 시간의 합
    • 응답시간(response time): 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 얻기까지 걸린 시간

 

4. 스케줄링 알고리즘

선입선출(First-Come First-Served: FCFS) 스케줄링: 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식

CPU를 먼저 요청한 프로세스에게 CPU를 먼저 할당하고 그 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않는다.

CPU 버스트가 긴 프로세스가 먼저 도착할 경우 평균 대기시간이 길어지는 반면, CPU 버스트가 짧은 프로세스가 먼저 도착하게 되면 평균 대기시간은 짧아지게 된다.

프로세스를 하나씩 끝내는 식으로 시간의 흐름에 따라 적어도 하나씩은 처리가 완료된 프로세스가 발생하여 평균 대기시간이나 평균 소요시간 측면에서 좋은 결과를 얻을 수 있다는 장점이 있다. 그러나 프로세스 간 대기시간이나 소요시간의 편차가 매우 크며 평균 응답시간이 지나치게 길어지는 문제점이 있다.

  • 콘보이 현상(Convoy effect): CPU 버스트가 짧은 프로세스가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상으로, FCFS 스케줄링의 대표적인 단점

 

최단작업 우선(Shortest-Job First: SJF) 스케줄링: CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식

  • SRTF(Shortest Remaining Time First): 현재 CPU에서 실행 중인 프로세스의 남은 CPU 버스트 시간보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착할 경우 CPU를 빼앗게 되는, SJF의 선점형 구현 방식

프로세스의 CPU 버스트 시간을 미리 알 수 없기 때문에 과거의 CPU 버스트 시간을 통해 예측치를 구하여 비교한다.

평균 대기시간을 최소화하는 알고리즘이기는 하지만 CPU 버스트가 짧은 프로세스에게만 CPU를 할당할 경우 CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야 하는 기아 현상(starvation) 문제가 발생할 수 있다.

 

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

우선순위는 우선순위값(priority number)을 통해 표시하며, 작을수록 높다. 우선순위를 결정하는 방식에는 여러 가지가 있는데, CPU 버스트 시간으로 정의한다면 SJF 알고리즘과 동일한 의미를 가지게 된다.

현재 CPU에서 수행 중인 프로세스보다 우선순위가 높은 프로세스가 도착하여 CPU를 선점해서 새롭게 도착한 프로세스에게 할당할 경우 선점형 방식, 우선순위가 더 높은 프로세스가 도착하더라도 CPU를 자진 반납하기 전까지 선점하지 않는다면 비선점형 방식이라 한다.

  • 노화(aging) 기법: 기아 현상의 해결 방법으로, 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 함

 

라운드 로빈 스케줄링(Round Robin Scheduling): 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당하고 이 프로세스는 준비 큐의 제일 뒤에서 다음번 차례를 기다리는 방식

  • 할당시간(time quantum): 각 프로세스가 한 번에 CPU를 연속적으로 사용 가능한 최대시간

할당시간이 너무 길면 FCFS와 같은 결과를 나타내게 되고, 너무 짧으면 CPU를 사용하는 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 커진다.

시분할 시스템의 성질을 가장 잘 활용한 방식으로, 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적이고, 소요시간(turn around time)과 대기시간이 자신이 사용하는 CPU 버스트 시간에 비례해 증가하므로 공정하다고 할 수 있다.

대기시간이나 처리시간의 편차가 크지 않으나 중간 산출물 없이 모든 프로세스가 마지막이 되어서야 함께 끝마쳐지므로 평균 대기시간과 평균 소요시간이 보다 비효율적이다.

 

멀티레벨 큐(multi-level queue): 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법

성격이 다른 프로세스들을 별도로 관리하고 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두게 되는데, 일반적으로 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영된다.

  • 전위 큐 → 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용
  • 후위 큐 → 응답시간이 큰 의미를 가지지 않으므로 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄임

어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링도 필요하다.

  • 고정 우선순위 방식(fixed priority scheduling): 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어 있을 때에만 서비스
  • 슬라이스(time slice) 방식: 각 큐에 CPU 시간을 적절한 비율로 할당하여 기아 현상을 해소할 수 있는 방식

 

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

CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시키는 등, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.

작업시간이 짧은 프로세스일수록 라운드 로빈 스케줄링을 적용하여 빠른 서비스가 가능하도록 하고, 작업시간이 긴 프로세스에 대해서는 문맥교환 없이 CPU 작업에만 열중할 수 있는 FCFS 방식을 채택할 수 있게 한다.

 

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

다중처리기 시스템에서는 일부 CPU에 작업이 편중되는 현상을 방지하기 위해 각 CPU별 부하가 적절히 분산되도록 하는 부하균형(load balancing) 메커니즘이 필요하다.

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

 

실시간 스케줄링

각 작업마다 주어진 데드라인이 있는 실시간 시스템(real-time system)에서는 빠른 서비스도 중요하지만 데드라인을 지키는 서비스가 더욱 중요하여 EDF 스케줄링을 널리 사용한다.

  • EDF(Earliest Deadline First) 스케줄링: 먼저 온 요청을 먼저 처리하기보다는 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 방식
  • 경성 실시간 시스템(hard real-time system): 시간을 정확히 지켜야 하는 시스템 (e.g. 미사일 발사, 원자로 제어 등)
  • 연성 실시간 시스템: 데드라인이 존재하기는 하지만 지키지 못했다고 하여 위험한 상황이 발생하지는 않는 시스템 (e.g. 멀티미디어 스트리밍)

 

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

  • 큐잉모델(queueing model): 확률분포를 통해 프로세스들의 도착률과 CPU 처리율을 입력값으로 주면 복잡한 수학적 계산을 통해 각종 성능지표를 구함
  • 시뮬레이션: 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떠한 결과가 나오는지 확인하는 방법
  • 구현 및 실측: 운영체제 커널의 소스 코드 중 CPU 스케줄링을 수행하는 코드를 수정해서 커널을 컴파일한 후 시스템에 설치한 후, 동일한 프로그램을 원래 커널과 CPU 스케줄러를 수정한 커널에서 수행시켜보고 실행시간을 측정
저작자표시 비영리 변경금지 (새창열림)