OS

다양한 OS 스케줄링 기법

둠치킨 2025. 6. 24. 20:11

멀티스레딩 또는 멀티프로세스 환경에서의 스케줄링 기법

멀티스레딩 혹은 멀티프로세스를 사용할 때 운영체제는 어떤 프로세스를 언제 실행할지를 결정하는 스케줄러를 사용한다.
이때 사용되는 여러 스케줄링 정책들은 각기 다른 목적과 환경에 최적화되어 있으며, 시스템 성능과 사용자 경험에 큰 영향을 준다.

1. FCFS (First-Come, First-Served)

  • 가장 먼저 도착한 프로세스를 먼저 실행하는 방식
  • 큐에 들어온 순서대로 처리되므로 구현이 간단하다
  • 단점: 실행 시간이 긴 프로세스가 먼저 들어오면 짧은 프로세스가 오래 대기하는 현상이 발생할 수 있다 (Convoy Effect)
  • 주로 배치 처리 시스템에서 사용

2. Round Robin (RR)

  • 모든 프로세스에 동일한 시간 할당량(타임퀀텀)을 부여
  • 실행 중 타임퀀텀이 만료되면, 현재 프로세스를 대기열 뒤로 보내고 다음 프로세스를 실행
  • 멀티스레드 환경에서 가장 일반적인 방식 중 하나
  • 장점: 공정성, 응답 시간 보장
  • 단점: 타임퀀텀 설정이 성능에 큰 영향을 미친다
    • 너무 짧으면 빈번한 문맥 교환으로 오버헤드 발생
    • 너무 길면 응답성이 낮아짐

3. Priority Scheduling

  • 각 프로세스에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행
  • 우선순위는 정적(static) 또는 동적(dynamic)으로 설정 가능
    • 정적: 미리 지정된 우선순위 기준
    • 동적: 대기 시간, CPU 사용량 등에 따라 조정
  • 단점: 낮은 우선순위 프로세스가 계속 기다리는 기아(Starvation) 문제가 발생할 수 있음
    • 해결: 에이징(Aging) 기법 사용

4. Multilevel Queue Scheduling

  • 프로세스를 특성에 따라 여러 개의 큐로 분류
    • 예: 시스템 프로세스, 사용자 프로세스, 대화형 프로세스 등
  • 각 큐는 서로 다른 스케줄링 정책을 사용 가능 (FCFS, RR 등)
  • 큐 간 이동은 일반적으로 허용되지 않음 (고정된 우선순위 계층 구조)

5. Multilevel Feedback Queue (MLFQ)

  • Multilevel Queue 스케줄링을 기반으로 하되, 프로세스의 행동에 따라 큐 간 이동이 가능
    • CPU를 많이 사용하는 프로세스는 더 낮은 우선순위 큐로 이동
    • 오랫동안 기다린 프로세스는 우선순위가 높아짐
  • 대화형(인터랙티브) 작업과 배치 작업을 동시에 처리하는 데 적합
  • 동적인 큐 이동을 통해 효율성과 응답성을 모두 확보할 수 있어, 실제 운영체제에서 널리 사용

6. Linux 커널의 스케줄링 기법

Completely Fair Scheduler (CFS)

  • 현재 리눅스 커널에서 사용하는 기본 스케줄러
  • 공정성(Fairness)을 기반으로 설계
  • 각 프로세스의 실행 시간을 추적하는 가상 런타임(vruntime)을 사용
  • red-black tree 자료구조로 프로세스를 정렬하여, 가장 적게 실행된 프로세스를 먼저 실행
  • 우선순위(nice 값)에 따라 vruntime에 가중치를 둠

O(1) Scheduler (이전 커널)

  • 각 우선순위마다 런큐(run queue)를 유지하고, 실행할 프로세스를 O(1) 시간에 선택
  • 프로세스의 수에 관계없이 일정한 시간 내에 스케줄링 결정 가능
  • 단점: 공정성 확보가 어려움, 대화형 프로세스 대응이 부족해 현재는 사용되지 않음
저작자표시 (새창열림)