기본적인 CPU 스케줄링 알고리즘들
FCFS(First Come First Served)(비선점 스케줄링)
- 도착한 순서대로 처리
Shortest Job First(비선점 스케줄링)
- 가장 짧은 스레드 우선 처리
Shortest remaining time first(선점 스케줄링)
- 남은 시간이 짧은 스레드가 준비 큐에 들어오면 이를 우선 처리
Round-robin(선점 스케줄링)
- 스레드들이 돌아가면서 할당된 시간(타임 슬라이스)만큼 실행
Priority Scheduling(선점/비선점 스케줄링 둘다 구현 가능)
- 우선 순위를 기반으로 하는 스케줄링. 가장 높은 순위의 스레드 먼저 실행
Multilevel queue scheduling(선점/비선점 스케줄링 둘다 구현 가능)
- 스레드와 큐 모두 n개의 우선순위 레벨로 할당, 스레드는 자신의 레벨과 동일한 큐에 삽입
- 높은 순위의 큐에서 스레드 스케줄링, 높은 순위의 큐가 빌 때 아래 순위의 큐에서 스케줄링
- 스레드는 다른 큐로 이동하지 못함
- ex) background process, Foreground process
Multilevel feedback queue scheduling(선점/비선점 스케줄링 둘다 구현 가능)
- 큐만 n개의 우선순위 레벨을 둠. 스레드는 동일한 우선순위
- 스레드는 제일 높은 순위의 큐에 진입하고 큐타임슬라이스가 다하면 아래 레벨의 큐로 이동
- 낮은 레벨의 큐에 오래 있으면 높은 레벨의 큐로 이동
FCFS(First Come First Served)
알고리즘
- 선입 선처리
- 먼저 도착한(큐에 맨 앞에 있는) 스레드 먼저 스케줄링
스케줄링 파라미터 : 스레드 별 도착 시간
스케줄링 타입 : 비선점 스케줄링
스레드 우선 순위 : 없음
기아 : 발생하지 않음
- 스레드가 오류로 인해 무한 루프를 실행한다면, 뒤 스레드 기아 발생
성능 이슈 :
- 처리율이 낮음
- 호위 효과(convoy effect)발생
- 긴 스레드가 CPU를 오래 사용하면, 늦게 도착한 짧은 스레드가 오래 대기
SJF(Shortest Job First)
알고리즘
- 최단 작업 우선 스케줄링
- 예상 실행 시간이 가장 짧은 스레드 선택
- 스레드가 도착할 때,
- 예상 실행 시간이 짧은 순으로 큐 삽입, 큐의 맨 앞에 있는 스레드 선택
스케줄링 파라미터 : 스레드 별 예상 실행 시간
- 이 시간을 아는 것은 불가능. 비현실적
스케줄링 타입 : 비선점 스케줄링
스레드 우선 순위 : 없음
기아 : 발생 가능
- 짧은 스레드가 계속 도착하면, 긴 스레드는 실행 기회를 언제 받을 지 예측할 수 없음
성능 이슈
- 짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화
문제점
- 실행 시간의 예측이 불가능하므로 현실에서는 거의 사용하지 않음.
SRTF(Shortest Remaining Time First)
알고리즘
- 최소 잔여 시간 우선 스케줄링
- 남은 실행 시간이 가장 짧은 스레드 선택
- SJF의 선점 스케줄링 버전
- 실행 시간에 짧은 순으로 스레드들을 큐에 삽입, 한 스레드가 끝나거나 실행 시간이 더 짧은 스레드가 도착할 때, 가장 짧은 스레드 선택
- 큐의 맨 앞에 있는 스레드 선택
스케줄링 파라미터 : 스레드 별 예상 실행 시간과 남은 실행 시간 값
- 이 시간을 아는 것은 불가능, 비현실적
스케줄링 타입 : 선점 스케줄링
스레드 우선순위 : 없음
기아 : 발생 가능
- 짧은 스레드가 계속 도착하면, 긴 스레드는 실행 기회를 언제 얻을 지 예상할 수 없음
성능 이슈 :
- 실행 시간이 짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화
문제점 :
- 실행 시간 예측이 불가능하므로 현실에서는 거의 사용되지 않음.
RR(Round-robin)
알고리즘
- 스레드들에게 공평한 실행 기회를 주기 위해
- 큐에 대기중인 스레드들을 타임 슬라이스 주기로 돌아가면서 선택
- 도착하는 순서대로 큐에 삽입
- 스레드가 타임 슬라이스를 소진하면 큐 끝으로 이동
스케줄링 파라미터 : 타임 슬라이스
스케줄링 타입 : 선점 스케줄링
스레드 우선 순위 : 없음
기아 : 없음
- 스레드의 우선순위가 없고, 타임 슬라이스가 정해져 있어, 일정 시간 후에 스레드는 반드시 실행된다.
성능 이슈 :
- 공평하고, 기아 현상 없고, 구현이 쉬움
- 잦은 스케줄링으로 전체 스케줄링 오버헤드 큼. 특히 타임 슬라이스가 작을 때 더욱 큼
- 균형된 처리율 : 타임슬라이스가 크면 FCFS에 가까움. 적으면 SJF/SRTF에 가까움, 늦게 도착한 짧은 스레드는 FCFS보다 빨리 완료되고, 긴 스레드는 SJF보다 빨리 완료됨.
Priority 스케줄링
알고리즘
- 우선순위에 따라 스레드를 실행시키기 위한 목적
- 가장 높은 순위의 스레드 선택
- 현재 스레드가 종료되거나 더 높은 순위의 스레드가 도착할 때, 가장 높은 순위의 스레드 선택
- 모든 스레드에 고정 우선 순위 할당, 종료 때까지 바뀌지 않음.
- 도착하는 스레드는 우선 순위 순으로 큐에 삽입
스케줄링 파라미터 : 스레드 별 고정 우선 순위
스케줄링 타입 : 선점 스케줄링/ 비선점 스케줄링
- 선점 스케줄링 : 더 높은 스레드가 도착할 때 현재 스레드 강제 중단하고 스케줄링
- 비선점 스케줄링 : 현재 실행 중인 스레드가 종료될 때 비로소 스케줄링
스레드 우선 순위 : 있음
기아 : 발생 가능
- 높은 순위의 스레드가 계속 도착하는 경우, 실행 기회를 언제 얻을 지 예상할 수 없음
- 큐 대기 시간에 비례하여 일시적으로 우선순위를 높이는 에이징 방법으로 해결 가능
성능 이슈
- 높은 우선순위의 스레드일수록 대기 혹은 응답시간 짧음
특징
- 스레드별 고정 우선 순위를 가지는 실시간 시스템에서 사용
MLQ(Multi-level Queue) 스케줄링
설계 의도
- 스레드들을 n개의 우선순위 레벨로 구분, 레벨이 높은 스레드를 우선 처리하는 목적
알고리즘
- 고정된 n개의 큐 사용, 각 큐에 우선순위 할당
- 스레드들의 우선순위도 n개의 레벨로 분류
- 각 큐는 나름대로의 기법으로 스케줄링
- 스레드는 도착 시 우선 순위에 따라 해당 레벨 큐에 삽입. 다른 큐로 이동할 수 없음
- 가장 높은 순위의 큐가 빌 때, 그 다음 순위의 큐에서 스케줄링
스케줄링 파라미터 : 스레드의 고정 우선 순위
스케줄링 타입 : 비선점 / 선점 모두 가능
- 비선점 스케줄링 : 현재 실행중인 스레드가 종료될 때 비로소 스케줄링
- 선점 스케줄링 : 높은 레벨의 큐에 스레드가 도착하면 중단하고 높은 레벨 큐에서 스케줄링
스레드 우선 순위 : 있음
기아 : 발생 가능
- 높은 순위의 스레드가 계속 도착하는 경우 실행 기회를 언제 얻을 지 예상할 수 없음
성능 이슈와 활용 사례
- 스레드의 고정 순위를 가진 시스템에서 활용
- 예) 전체 스레드를 백그라운드 스레드와 포그라운드 스레드의 2개의 그룹으로 구성
- 예) 시스템 스레드, 대화식 스레드, 배치 스레드 등 3개의 레벨로 나누고 시스템 스레드를 우선적으로 스케줄링
- 예) 메시징 서버에서 메시지 종류를 매우 긴급/긴급/보통/낮음의 우선순위 4개로 나누고 스케줄링
MLFQ(Multi-Level Feedback Queue)스케줄링
설계 의도
- 1962년에 개발된 알고리즘
- 기아를 없애기 위해 여러 레벨이 큐 사이에 스레드 이동 가능하도록 설계
- 짧은 스레드와 I/O가 많은 스레드, 대화식 스레드의 우선 처리. 스레드 평균 대기시간을 줄임
n개의 레벨 큐
- n개의 고정 큐. 큐마다 서로 다른 스케줄링 알고리즘
- 큐마다 스레드가 머물 수 있는 큐 타임슬라이스 있음. 낮은 레벨의 큐일수록 더 긴 타임 슬라이스
- I/O 집중 스레드(대화식 스레드)는 높은 순위의 큐에 있을 가능성이 높음
알고리즘
- 스레드는 도착 시 최상위 레벨 큐에 삽입
- 가장 높은 레벨 큐에서 스레드 선택. 비어 있으면 그 아래의 큐에서 스레드 선택
- 스레드의 CPU-burst가 큐 타임 슬라이스를 초과하면 강제로 아래 큐로 이동시킴
- 스레드가 자발적으로 중단한 경우, 현재 큐 끝에 삽입
- 스레드가 I/O로 실행이 중단된 경우, I/O가 끝나면 동일 레벨 큐 끝에 삽입
- 큐에 있는 시간이 오래되면 기아를 막기 위해 하나 위 레벨 큐로 이동
- 최하위 레벨 큐는 주로 FCFS나 긴 타임 슬라이스의 RR로 스케줄. 스레드들은 다른 큐로 이동 못함.
스케줄링 파라미터 : 각 큐의 큐 타임 슬라이스
스케줄링 타입 : 선점 스케줄링
스레드 우선 순위 : 없음
기아 : 발생하지 않음.
- 큐에 대기하는 시간에 오래되면, 더 높은 레벨의 큐로 이동시킴(에이징 기법)
성능 이슈
- 짧거나 입출력이 빈번한 스레드, 혹은 대화식 스레드를 높은 레벨의 큐에서 빨리 실행 -> CPU 활용률이 높음
'IT 공부 > 운영체제' 카테고리의 다른 글
| 5-1. 프로세스의 문제점 (0) | 2023.04.15 |
|---|---|
| 6-4. 멀티 코어 CPU에서의 스케줄링 (0) | 2023.04.15 |
| 6-2. CPU 스케줄링 기본 (0) | 2023.04.13 |
| 6. CPU 스케줄링 개요 (0) | 2023.04.13 |
| 2. 운영체제의 태동 (0) | 2023.04.11 |
