다양한 스케줄링 알고리즘

안녕하세요~ 저번 시간에 이어서 이번 시간에는 스케줄링 알고리즘의 종류와 멀티코어 CPU에서의 스케줄링에 대해 알아보는 시간을 가지겠습니다~ 그럼 시작하겠습니다!

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

CPU를 먼저 요청하는 프로세스/스레드가 CPU를 먼저 할당 받음
- 비선점형 스케줄링
가장 간단한 알고리즘
ready 큐를 FIFO 큐로 쉽게 구현
일반적으로 기아는 발생되지 않음
처리율이 낮음
- 평균 대기시간이 길어질 수 있음

※ FCFS 스케줄링의 예

※ 호위 효과(Convoy Effect)

긴 CPU burst를 가진 프로세스/스레드에게 CPU가 할당되길 다른 프로세스/스레드들이 기다림
- 하나의 CPU-bound 프로세스/스레드 A와 다수의 I/O-bound 프로세스/스레드들 B를 가정
  - A가 CPU 사용시, B들은 I/O를 마치고 CPU 대기
  - A가 I/O 처리시, B들은 CPU 사용을 마치고 I/O 대기
CPU와 I/O 장치들은 idle time(유휴 시간)이 커짐
- 빨리 끝날 수 있는 프로세스/스레드부터 처리하자
  - Shortest Job First Scheduling => SJF 스케줄링

2. SJF(Shortest-Job-First) Scheduling (최소 작업 우선 스케줄링)

Shortest-next-CPU-burst scheduling
- 다음에 수행할 프로세스/스레드들 중 가장 짧은 CPU burst를 갖는 프로세스/스레드를 우선 선택
- 동일한 수행시간을 갖는다면 FCFS로 처리
특징
- 평균 대기 시간이 작음(최적)
- 다음 CPU burst의 길이 파악이 어려움
  - 현실에서는 사용되지 못함
- 기아 발생 가능

※ SJF 스케줄링의 예

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

선점형 SJF
- ready 큐에 현재 실행 중인 프로세스 A의 잔여 CPU burst보다 더 짧은 CPU burst를 가진 프로세스 B가 ready 큐에 도착하면 A는 B에게 선점됨 (B가 CPU를 강제로 뺏음)
특징
- 기아 발생 가능
- 평균 대기 시간 최소화

※ SRTF 스케줄링의 예

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

각 프로세스/스레드에 우선순위 지정
가장 높은 우선순위를 가진 프로세스/스레드에게 CPU 할당
- 선점형 vs 비선점형
  - 선점형 : 우선순위가 높은 프로세스/스레드가 들어오면 CPU 강제로 뺏음
  - 비선점형 : 우선순위가 더 높은 프로세스/스레드가 들어와도 끝까지 실행
기준
- 내부/외부적 요인들
- FCFS : ready 큐에 들어온 순서
- SJF : (추정된) CPU burst의 길이
- SRTF : (추정된) 잔여 CPU burst의 길이

※ Priority Scheduling의 문제점

기아(Starvation) / 무한봉쇄(Indefinite Blocking)
- 낮은 우선순위의 프로세스들이 무한히 대기
  - 실행 준비는 되어 있으나 CPU를 할당 받지 못함
해결책 : 에이징(Aging)
- 오래도록 처리되지 못하고 남아있는 프로세스에 대해 점진적으로 우선순위를 올려주는 기법

5. RR(Round-Robin) Scheduling (순환 할당 스케줄링)

시분할 시스템을 위해 설계됨
규정 시간량(Time quantum) / 시간 할당량(Time slice)
- 각 프로세스에게 한 번에 할당되는 CPU 시간
  - 보통 10 ~ 100msec
- 이 시간이 만료되어 설정된 타이머에서 완료 인터럽트 발생시 디스패치
선점형 FCFS
- FCFS와 유사하나 프로세스들 사이를 강제로 옮기기 위한 선점이 추가
- 순환 FIFO ready 큐
일반적으로 평균 대기 시간이 길다

※ RR 사례(Time slice = 2ms일 때)

※ RR 사례(Time slice = 1ms일 때)

※ RR 스케줄링의 성능

시간 할당량(Time quantum)의 크기와 성능
- 잦은 스케줄링으로 전체 스케줄링 오버헤드가 큼
  - 시간 할당량이 무한대인 경우, FCFS랑 유사
  - 시간 할당량이 매우 작은 경우
    - n개의 프로세스는 각각 1/n 속도로 실행되는 자신만의 프로세서를 가지고 있는 것처럼 보여짐
기아가 발생하지 않음

6. MLQ(Multi-Level-Queue) Scheduling (다단계 큐 스케줄링)

프로세스/스레드를 n개의 우선순위 레벨로 구분, 높은 레벨을 먼저 처리할 경우에 유용
- 1950년대 후반
ready 큐를 다수의 독립적인 큐로 분류하여 구성
- 각 프로세스/스레드는 특성에 따라 영구적으로 특정 큐에 할당
  - 다른 레벨의 큐로 이동 불가
- 각 큐는 자신만의 스케줄링 알고리즘을 가지고 스케줄 가능

※ MLQ 스케줄링의 특징

각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가짐
- 비선점 : 스레드 종료시 스케줄링
- 선점 : 높은 레벨의 큐에 도착시 스케줄링
  - 기아 상태 발생 가능
스레드별로 고정 우선순위를 두고 높은 우선순위의 스레드를 먼저 실행시키고자 할 때 유용
- 포그라운드 > 백그라운드
- 시스템 스레드 > 대화식 스레드 > 배치 스레드
- 교수자 스레드 > 대학원생 스레드 > 학부생 스레드

7. MLFQ(Multi-Level-Feedback-Queue) Scheduling (다단계 피드백 큐 스케줄링)

MLQ의 큐 사이에 프로세스들의 이동을 허용
- 평균 대기시간과 응답시간을 줄이고 기아 방지
  - CPU burst가 짧은 스레드, I/O 작업이 많은 스레드, 대화식 스레드를 우선 실행
    - CPU 시간을 많이 사용하는 스레드는 lower-priority 큐로 이동
  - lower-priority 큐에서 너무 오래 대기하는 프로세스/스레드는 higher-priority 큐로 이동
가장 일반적인 CPU 스케줄링 알고리즘
성능에 영향을 미치는 매개변수들이 많아 복잡
- 큐 개수, 각 큐의 스케줄링 알고리즘
- 프로세스의 큐 이동 시기(L <=> H) 결정 방법
- 프로세스 생성시 진입할 큐 결정 방법

8. 멀티코어 시스템에서의 CPU 스케줄링 이슈

단일 코어 시스템의 CPU 스케줄링 적용시(1)
- 컨텍스트 스위칭 오버헤드 증가
  - 이전에 실행된 적이 없는 코어에 스레드 배치시, 캐시에 새로운 스레드 코드/데이터 적재 오버헤드 발생
CPU 친화성(CPU affinity) 적용
- 스레드를 동일한 코어에서만 실행하도록 제한
- CPU 친화성 = 코어 친화성(core affinity) = CPU 피닝(pinning) = 캐시 친화성
코어 당 스레드 큐 사용
단일 코어 시스템의 CPU 스케줄링 적용시(2)
- OS가 스레드를 무작위로 스케줄링하면 코어별 부하 불균형 발생
  - 각 코어마다 처리할 스레드 수의 불균형 발생
부하 균등화(load balancing) 기법으로 해결
- 푸시 마이그레이션(push migration)
- 풀 마이그레이션(pull migration)

지금까지 스케줄링 알고리즘의 종류와 멀티코어 CPU에서의 스케줄링에 대해 설명하였습니다.

휴.. 여러분 많이 힘드시죠? 저도 힘든데, 여러분은 얼마나 힘들까요.. 하지만 돌이켜보면 지금 이 시간들이 나중에 빛을 발하게 될 것이라고 확신합니다. 그러니 저 또한 최선을 다해서 설명하는 블로거가 되겠습니다!!

다음 시간에는 스레드 동기화의 필요성 및 개념, 상호 배제에 대해 알아볼 예정입니다!

좋은 하루 되시길 바랍니다~!

저작자표시 비영리 변경금지

Passionate Engineer