[OS Study] 2-2. CPU 스케쥴링 (Ch. 6~11)

안녕하세요.

이번 포스팅에선 CPU 스케쥴링에 대해 정리해 보았습니다.

1. CPU 스케쥴링

- OS는 여러 프로세스가 CPU를 효율적으로 사용 하게 하기 위해 다양한 스케쥴링 기법을 활용 함

- 스케쥴링 평가 기준으로 반환 시간 (Complete 시간과 Request 시간의 차이) 을 사용


2-1. FIFO (First in First out)

- 먼저 request 된 Job을 먼저 수행

- convoy effect 문제가 발생 : 수행 시간이 긴 Job이 먼저 들어 올 경우 수행 시간이 짧은 Job들이 오래 대기해야되는 문제


2-2. SJF (Shortest Job First)

- 수행 시간이 짧은 Job부터 수행

- 수행 시간이 긴 Job은 우선 순위가 계속 밀리는 문제가 발생 할 수 있음


2-3. STCF (Shortest Time-to-Completion First)

- 잔여 시간이 가장 짧은 Job 부터 수행 : 새로운 Job에 대한 요청이 들어 오면 남아 있는 작업과 비교하여 잔여 수행 시간이 짧은 것을 우선 배정

2-4. RR (Round Robin)

- 일정 시간 (타임 슬라이스, 스케쥴링 퀀텀) 동안 특정 Job을 수행 한 후 다음 Job을 또 일정 시간 동안 수행

- 컨텍스트 스위치 (문맥 교환) 시간 고려가 필요


3. MLFQ (Multi-level Feedback Queue)

- 알고리즘은 멀티 레벨 큐를 가지고 있으며, 지정된 작업의 우선순위를 정하기 위하여 피드백을 사용

- 규칙 1 : 우선순위가 높은 Job을 수행

- 규칙 2 : 우선순위가 같을 경우 RR 방식을 사용

- 규칙 3 : 작업이 시스템에 들어가면 최상위 큐에 배치

- 규칙 4 : 작업이 지정된 단계에서 배정 받은 시간을 소진 하면 (CPU를 포기한 횟수와 상관 없이), 작업의 우선 순위는 감소 (한 단계 아래 큐로 이동)

- 규칙 5 : 일정 주기가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동


4. 멀티프로세서 스케쥴링

 

출처 : KAIST OS Lab (원유집 교수님, https://oslab.kaist.ac.kr/OSTEPSlides/)

4-1. SQMS (Single Queue Multi-processor Scheduling)

- 단일 프로세서 스케쥴링의 기본 프레임워크를 멀티 프로세서 환경에서 그대로 사용

- 장점 : 단순함

- 단점 : 확장성 결여 / 캐시 친화성


4-2. MQMS (Multi-queue Multi-processor Scheduling)

- 여러개의 큐를 여러개의 프로세서가 사용

- 장점 : 확장성

- 워크로드의 뷸균형 문제 해결을 위해 마이그레이션 사용

- 마이그레이션 : Job을 다른 큐로 이동