스케줄링 알고리즘의 종류

2025. 1. 29. 15:48·운영체제/CPU 스케줄링
목차
  1. 1. 선입 선처리 스케줄링(FCFS: First Come First Served)
  2. 1.1 개념
  3. 1.2 특징 요약
  4. 2. 최단 작업 우선 스케줄링(SJF: Shortest Job First)
  5. 2.1 개념
  6. 2.2 특징 요약
  7. 3. 라운드 로빈 스케줄링(Round Robin)
  8. 3.1 개념
  9. 3.2 타임 슬라이스가 중요한 이유
  10. 4. 최소 잔여 시간 우선 스케줄링(SRTF: Shortest Remaining Time First)
  11. 4.1 개념
  12. 4.2 특징 요약
  13. 5. 우선순위 스케줄링(Priority Scheduling)
  14. 5.1 개념
  15. 5.2 기아(Starvation)와 에이징(Aging)
  16. 6. 다단계 큐 스케줄링(Multilevel Queue)
  17. 6.1 개념
  18. 6.2 특징
  19. 7. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue)
  20. 7.1 개념
  21. 7.2 특징
  22. 8. 정리
  23. 참고 자료

다양한 스케줄링 알고리즘

운영체제에서 프로세스에 CPU 등의 자원을 할당할 때는 여러 스케줄링 알고리즘을 사용한다. 각 알고리즘은 프로세스들을 어떤 순서로 우선 실행시킬지 결정하는 전략을 가지고 있으며, 실행 환경이나 요구사항(반응 속도, 처리량 등)에 따라 그 장단점이 달라진다. 이번 장에서는 대표적인 스케줄링 알고리즘들을 간략히 살펴본다.

 


1. 선입 선처리 스케줄링(FCFS: First Come First Served)

1.1 개념

  • 준비 큐(Ready Queue)에 도착한 순서대로 프로세스에 CPU를 할당하는 비선점형 스케줄링 방식이다.
  • 단순하고 이해하기 쉽지만, CPU 사용 시간이 긴 프로세스가 먼저 오면 호위 효과(Convoy Effect) 가 발생해 이후 프로세스들이 장시간 대기하는 문제가 있다.

Image

(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)

1.2 특징 요약

  • 장점: 구현이 쉽고 공정해 보인다(도착 순으로 처리).
  • 단점: 긴 CPU 버스트를 가진 프로세스가 먼저 오면, 뒤에 온 짧은 프로세스가 오래 대기(호위 효과).

 


2. 최단 작업 우선 스케줄링(SJF: Shortest Job First)

2.1 개념

  • 준비 큐에 있는 프로세스 중 CPU 이용 시간이 가장 짧은 프로세스부터 먼저 실행한다.
  • 비선점형 방식으로 구현된 경우가 일반적이지만, 선점형 버전(최소 잔여 시간 우선, SRTF)도 존재한다.

Image

(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)

2.2 특징 요약

  • 장점: CPU 사용 시간이 짧은 프로세스를 빨리 끝낼 수 있어 평균 대기 시간을 줄일 수 있다.
  • 단점: 새로 오는 프로세스의 CPU 사용 시간을 정확히 예측하기 어렵다.
  • 문제점: CPU 사용 시간이 긴 프로세스가 기아(Starvation) 상태에 빠질 수 있다(짧은 프로세스가 계속 선점).

 


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

3.1 개념

  • 선입 선처리(FCFS) 방식에 타임 슬라이스(Time Quantum) 개념을 추가한 선점형 스케줄링이다.
  • 프로세스는 정해진 짧은 시간(q 밀리초) 동안 CPU를 사용하고, 시간이 끝나면 문맥 교환이 발생해 다음 프로세스로 넘어간다.
  • 남은 작업이 있다면 준비 큐 뒤에 다시 들어가 차례를 기다린다.

Image

(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)

3.2 타임 슬라이스가 중요한 이유

  • 너무 크면: 사실상 FCFS와 다를 바 없어 호위 효과 발생.
  • 너무 작으면: 문맥 교환(Context Switch) 비용이 증가, 오버헤드가 커져 CPU가 스위칭에만 많은 시간 낭비.

 


4. 최소 잔여 시간 우선 스케줄링(SRTF: Shortest Remaining Time First)

4.1 개념

  • SJF(최단 작업 우선) 과 Round Robin(선점형) 을 합친 형태.
  • 정해진 타임 슬라이스마다, 현재 남은 CPU 시간이 가장 짧은 프로세스에게 CPU를 할당한다(혹은 새 프로세스가 도착할 때마다 재결정).
  • 선점형 최단 작업 우선으로 이해할 수 있다.

4.2 특징 요약

  • 장점: 평균 대기 시간을 최소화하는 효과가 큼(짧은 작업 우선).
  • 단점: 남은 시간 추정이 필요하고, 긴 작업이 계속 뒤로 밀려 기아 가능성이 높다.

 


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

5.1 개념

  • 각 프로세스에 우선순위(Priority)를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 CPU를 할당하는 방식.
  • 선점형과 비선점형 모두 가능.

Image

(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)

5.2 기아(Starvation)와 에이징(Aging)

  • 문제: 우선순위가 낮은 프로세스는 계속 후순위로 밀려 기아(영원히 실행되지 않음) 상태가 될 수 있다.
  • 해결: 오랫동안 대기 중인 프로세스의 우선순위를 점차 높여 주는 에이징(Aging) 기법을 사용한다.

 


6. 다단계 큐 스케줄링(Multilevel Queue)

6.1 개념

  • 우선순위별(혹은 다른 분류 기준별)로 준비 큐를 여러 개 두고, 우선순위가 높은 큐부터 우선적으로 스케줄링하는 방식.
  • 큐마다 서로 다른 스케줄링 알고리즘을 적용할 수도 있다.
  • 예: 입출력 집중 프로세스(우선순위 높음) vs. CPU 집중 프로세스(우선순위 낮음)로 큐를 분리.

Image

(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)

6.2 특징

  • 장점: 프로세스 종류나 특성에 맞는 맞춤형 스케줄링 가능(예: 대화형 프로세스 vs. 배치 프로세스).
  • 단점: 한 큐에 속하면 우선순위나 분류가 변경되지 않아, 기아 문제 등이 발생할 수 있다.

 


7. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue)

7.1 개념

  • 다단계 큐에서 프로세스가 다른 큐로 이동할 수 있게 한 개선된 방식.
  • 새 프로세스는 일단 높은 우선순위 큐에 들어가고, CPU를 일정 시간만 써도 완료되지 않으면 더 낮은 우선순위 큐로 내려간다.
  • 반대로, 오랫동안 낮은 우선순위 큐에서 대기 중인 프로세스의 우선순위를 에이징으로 끌어올릴 수도 있다.

Image

(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)

7.2 특징

  • CPU를 많이 쓰는 프로세스는 점차 낮은 우선순위 큐로 이동
  • CPU를 적게 쓰는(짧은 작업) 프로세스는 높은 우선순위 큐에서 빨리 끝낼 수 있다
  • 기아 방지: 오래 대기하면 우선순위 상승(에이징) 으로 상위 큐로 이동 가능
  • 현대 OS에서 매우 일반적으로 사용되는 스케줄링 방식

Image

(그림 출처: 혼자 공부하는 컴퓨터 구조 + 운영체제)

 


8. 정리

  1. FCFS(선입 선처리)
    • 가장 간단하나 호위 효과 발생 가능. 비선점형.
  2. SJF(최단 작업 우선) / SRTF(최소 잔여 시간 우선)
    • 짧은 작업 먼저 처리, 평균 대기 시간 최소화. 긴 작업 기아 문제 발생 가능.
  3. 라운드 로빈(Round Robin)
    • 타임 슬라이스 기반으로 선점형 동작. 공정하나 슬라이스 설정이 중요.
  4. 우선순위 스케줄링
    • 높은 우선순위부터 실행. 기아 문제가 있고, 에이징으로 해결 가능.
  5. 다단계 큐(Multilevel Queue)
    • 큐를 여러 개 두어 우선순위별 처리. 프로세스가 다른 큐로 이동 불가.
  6. 다단계 피드백 큐(Multilevel Feedback Queue)
    • 프로세스가 큐 간 이동 가능, CPU 많이 쓰면 우선순위 낮춤, 오래 대기하면 우선순위 높임.
    • 현대 OS에서 매우 일반적.

각 알고리즘은 특정 목표(예: 짧은 응답 시간, 높은 처리량, 공정성 등)에 맞춰 선택되고, 실제 운영체제는 종종 둘 이상의 기법(예: 우선순위 + 라운드 로빈 + 다단계 피드백) 등을 혼합하여 사용하기도 한다.

 


참고 자료

  • 혼자 공부하는 컴퓨터 구조 + 운영체제
  • Operating System Concepts (A. Silberschatz, P.B. Galvin, G. Gagne)
  • Modern Operating Systems (A.S. Tanenbaum, H. Bos)

'운영체제 > CPU 스케줄링' 카테고리의 다른 글

선점형과 비선점형 스케줄링  (0) 2025.01.28
프로세스 우선순위 (Process Priority)  (0) 2025.01.20
  1. 1. 선입 선처리 스케줄링(FCFS: First Come First Served)
  2. 1.1 개념
  3. 1.2 특징 요약
  4. 2. 최단 작업 우선 스케줄링(SJF: Shortest Job First)
  5. 2.1 개념
  6. 2.2 특징 요약
  7. 3. 라운드 로빈 스케줄링(Round Robin)
  8. 3.1 개념
  9. 3.2 타임 슬라이스가 중요한 이유
  10. 4. 최소 잔여 시간 우선 스케줄링(SRTF: Shortest Remaining Time First)
  11. 4.1 개념
  12. 4.2 특징 요약
  13. 5. 우선순위 스케줄링(Priority Scheduling)
  14. 5.1 개념
  15. 5.2 기아(Starvation)와 에이징(Aging)
  16. 6. 다단계 큐 스케줄링(Multilevel Queue)
  17. 6.1 개념
  18. 6.2 특징
  19. 7. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue)
  20. 7.1 개념
  21. 7.2 특징
  22. 8. 정리
  23. 참고 자료
'운영체제/CPU 스케줄링' 카테고리의 다른 글
  • 선점형과 비선점형 스케줄링
  • 프로세스 우선순위 (Process Priority)
iOS Developer
iOS Developer
myungsun-e 님의 블로그 입니다.
  • iOS Developer
    myungsun-e
    iOS Developer
  • 전체
    오늘
    어제
    • 분류 전체보기 (25)
      • 컴퓨터 네트워크 (11)
        • 응용계층 (11)
      • 운영체제 (14)
        • 운영체제 시작하기 (2)
        • 프로세스 상태와 계층 구조 (3)
        • 프로세스와 스레드 (1)
        • CPU 스케줄링 (3)
        • 동기화란 (2)
      • iOS (0)
        • Swift-문법 (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    IOS
    SWIFT
    컴퓨터 네트워크
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
iOS Developer
스케줄링 알고리즘의 종류

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.