Featured image of post CPU 스케줄링과 스케줄링 알고리즘

CPU 스케줄링과 스케줄링 알고리즘

CPU 스케줄링의 기본 개념과 알고리즘

CPU 스케줄링이란?

CPU 스케줄링이란 운영체제가 CPU 자원을 효율적으로 관리하기 위해 프로세스를 선택하여 CPU를 할당하는 과정이다. 다중 프로그래밍 환경에서는 하나의 프로세스가 I/O 작업을 기다리는 동안 CPU가 놀지 않고 다른 프로세스를 실행하여 CPU 이용률을 최대화한다.

CPU-I/O 버스트 사이클

CPU 스케줄링의 핵심은 프로세스가 CPU 실행과 I/O 대기를 반복하는 특성에 기반한다. 프로세스는 CPU 버스트로 시작하여, 이후 I/O 버스트와 CPU 버스트가 교차하며 진행된다. 일반적으로 CPU 버스트는 짧은 경우가 많고 긴 경우는 드물다. 이는 CPU 스케줄링 알고리즘 설계에 중요한 영향을 미친다.

CPU 스케줄링 유형

선점형과 비선점형 스케줄링

선점형 스케줄링은 실행 중인 프로세스를 중단시키고 다른 프로세스에 CPU를 할당할 수 있는 반면, 비선점형 스케줄링은 프로세스가 자발적으로 CPU를 놓아줄 때까지 CPU를 계속 점유하게 한다. 대부분의 현대 운영체제는 선점형 스케줄링을 사용한다.

주요 CPU 스케줄링 알고리즘

  1. 선입선처리(FCFS)

    • 가장 간단한 방법으로, 먼저 도착한 프로세스부터 처리한다.
    • 단점: 긴 프로세스 뒤에 짧은 프로세스들이 기다리는 convoy effect가 발생할 수 있다. convoy effect는 호위 효과라고도 하는데, 마트에서 나는 음료수 한 캔만 계산하면 되는데 앞사람들이 카트 가득 물건을 싣고 계산하고 있는 경우와 같다.
  2. 최단 작업 우선(SJF)

    • CPU 버스트가 가장 짧은 프로세스를 먼저 처리하여 평균 대기 시간을 최소화한다.
    • 다음 CPU 버스트 길이를 정확히 예측하기 어렵기 때문에 일반적으로 근사한 예측값을 사용한다.
  3. 라운드 로빈(RR)

    • 각 프로세스에 동일한 시간 할당량을 부여하며 순차적으로 처리한다.
    • 시간 할당량이 너무 작으면 잦은 문맥 교환으로 성능이 저하되고, 너무 크면 FCFS와 같은 단점을 가진다.
  4. 우선순위 스케줄링

    • 우선순위가 높은 프로세스를 먼저 처리한다.
    • 단점: 낮은 우선순위 프로세스가 CPU를 무한히 기다리는 기아 상태(starvation)가 발생할 수 있으며, 이를 방지하기 위해 노화(aging) 기법을 사용한다.
  5. 다단계 큐 스케줄링

    • 여러 큐를 만들어 각 큐마다 다른 우선순위와 스케줄링 방식을 적용한다.
    • 프로세스는 특정 큐에 고정되며, 큐 간에도 스케줄링을 한다.
  6. 다단계 피드백 큐 스케줄링

    • 프로세스가 큐 사이를 이동할 수 있으며, CPU 사용량에 따라 우선순위를 동적으로 조정한다.
    • 기아 상태 방지를 위해 프로세스를 상위 큐로 이동시키는 노화 기법을 사용한다.

스케줄링 성능 평가 기준

스케줄링 알고리즘의 성능을 평가할 때 기준은 여러 가지가 있다.

  • CPU 이용률(utilization): CPU를 최대한 효율적으로 사용하는 비율
  • 처리량(throughput): 단위 시간당 처리되는 프로세스 수
  • 총처리 시간(turnaround time): 프로세스가 시스템에 들어와서 완전히 끝날 때까지의 총 시간
  • 대기 시간(wating time): 프로세스가 준비 큐에서 대기한 총 시간
  • 응답 시간(response time): 사용자의 요청 후 첫 응답이 나타날 때까지 걸리는 시간

이러한 기준들을 통해 상황에 맞는 적절한 스케줄링 알고리즘을 선택하는 것이 바람직하다.