본문으로 건너뛰기

CPU 스케줄링

CPU 스케줄링 개요

  • CPU 스케줄링: 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
  • 일반적인 프로세스의 실행 과정: CPU와 입출력장치를 번갈아가며 사용하며 실행된다. → 우선순위를 부여하여 CPU를 배분하는 것이 효율적!
  • 운영체제는 각 프로세스의 PCB에 우선순위를 명시하고 해당 순위를 기준으로 먼저 처리할 프로세스를 결정한다.
  • 운영체제는 CPU를 사용하고 싶은 프로세스들, 메모리에 적재되고 싶은 프로세스들, 특정 입출력장치를 사용하고 싶은 프로세스들을 모두 스케줄링 큐를 이용해 관리한다.

  • Ready Queue: CPU를 이용하고 싶은 프로세스들이 서는 줄

  • Waiting Queue: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

  • 선점형 스케줄링(preemptive scheduling): 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식 → 하나의 프로세스가 독점 사용 불가능

  • 비전섬형 스케줄링(non-preemptive scheduling): 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식 → 하나의 프로세스가 독점 사용 가능

  • 선점형 스케줄링 장점: 한 프로세스의 자원 독점 막고 여러 프로세스들에게 골고루 자원 분배 가능하다. 단점: context switching 증가 → 오버헤드 증가

  • 비선점형 스케줄링 장점: context switching 별로 없음 → 오버헤드 감소 단점: 자원 독점 이용 가능하여 여러 프로세스들이 골고루 자원 사용하는 것이 힘들다.

CPU 스케줄링 알고리즘

FCFS 스케줄링 (First Come First Served Scheduling, 선입 선처리 스케줄링)

  • 레디큐에 삽입된 순서대로 프로세스들을 처리
  • 비선점형 스케줄링 방식
  • 단점: CPU를 오래 사용하는 프로세스가 먼저 도착하면 다른 프로세스는 그 프로세스가 CPU를 사용하는 동안 무작정 기다려야 한다. → 호위효과(convoy effect)

SJF 스케줄링 (Shortest Job First Scheduling, 최단 작업 우선 스케줄링)

  • 레디큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행
  • 기본적으로 비선점형 스케줄링 방식, 선점형은 뒤에 나오는 SRT(최소 잔여 시간 우선 스케줄링)
  • 호위효과(convoy effect) 방지

Round Robin 스케줄링

  • 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 사용
  • 선점형 스케줄링 방식
  • 타임 슬라이스가 지나치게 크면 FCFS와 같아지고, 지나지차 작으면 context switching 비용 증가

SRT 스케줄링 (Shortest Remaining Time, 최소 잔여 시간 우선 스케줄링)

  • 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

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

  • 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행
  • 우선순위가 같다면 선입 선처리로 스케줄링
  • SJF, SRT 스케줄링도 이에 해당한다고 볼 수 있다.
  • 단점: starvation 현상 (기아현상) → 우선순위가 낮은 프로세스가 무기한 연기되는 현상
  • 해결방법: aging (에이징) → 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

Multilivel Queue Scheduling (다단계 큐 스케줄링)

  • 우선순위별로 준비 큐를 여러개 사용하는 스케줄링
  • 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리
  • 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다. → queue별로 타임 슬라이스 여러개 지정, 다른 스케줄링 알고리즘 사용 가능
  • 프로세스들의 큐 사이 이동 불가
  • 단점: starvation 현상 (기아현상) → 우선순위가 낮은 프로세스가 무기한 연기되는 현상

Multilivel Feedback Queue Scheduling (다단계 피드백 큐 스케줄링)

  • Multilivel Queue Scheduling + 프로세스들이 큐 사이 이동할 수 있다.
  • 우선순위가 가장 높은 우선순위 큐에 삽입 → 타임 슬라이스 시간 동안 실행 → 해당 프로세스가 끝나지 않는다면 다음 우선순위 큐에 삽입 → …
  • CPU를 오래 사용해야 하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고, 적게 사용하는 입출력 집중 프로세스들은 우선순위가 높은 큐에서 실행이 끝난다.
  • 우선순위 큐에서 너무 오래 기다리고 있는 프로세스는 점차 우선순위가 높은 큐로 이동시키는 aging 기법 적용하여 starvation 현상 예방 가능
  • 가장 일반적인 CPU 스케줄링 알고리즘으로 알려져있다.