강의 목표
- CPU 스케줄링의 목표와 다양한 평가 기준에 대해 이해한다.
- CPU 스케줄링이 일어나는 상황과,
커널에서 CPU 스케줄링이 일어나는 위치에 대해 이해한다. - 선점 스케줄링과 비선점 스케줄링을 구분할 수 있다.
- 기아와 에이징의 개념을 이해한다.
- 다양한 CPU 스케줄링 알고리즘에 대해 안다.
- 리눅스에서 사용되는 CFS 스케줄링을 구체적으로 이해한다.
01. CPU 스케줄링 개요
스케줄링
- 자원에 대한 경쟁이 있는 곳에서 경쟁자 중 하나를 선택하는 과정
자원: CPU, 디스크, 프린트, 파일, 데이터베이스 등 - 컴퓨터 시스템 여러 곳에서 일어남
작업 스케줄링(job scheduling)
- 배치 시스템에서 대기중인 작업 중 메모리에 적재할 작업 결정
CPU 스케줄링
- 프로세스/스레드 중에 하나를 선택하여 CPU 할당
- 오늘날 CPU 스케줄링은 스레드 스케줄링
디스크 스케줄링
- 디스크 장치 내에서 디스크 입출력 요청 중 하나 선택
프린터 스케줄링
- 프린팅 작업 중 하나 선택하여 프린터 할당
1.1 다중프로그래밍과 스케줄링
다중프로그래밍의 도입 목적
- CPU 유휴 시간을 줄여 CPU의 활용률을 향상시키기 위함
프로세스가 I/O를 요청하면 다른 프로세스에게 CPU 할당
다중프로그래밍과 함께 2가지 스케줄링 도입
-
작업 스케줄링(job scheduling)
디스크 장치로부터 메모리에 올릴 작업 선택(초기 다중프로그래밍 시스템)
처음에 혹은 프로세스가 종료할 때마다 -
CPU 스케줄링 (CPU scheduling)
메모리에 적재된 작업 중 CPU에 실행시킬 프로세스 선택
1.2 CPU burst와 I/O burst
프로그램의 실행 특성
- CPU 연산 작업과 I/O 작업(화면 출력, 키보드, 입력, 파일 입출력)이 순차적으로 섞여 있음
- CPU-burst → I/O burst → CPU burst → I/O burst의 반복
CPU burst
- 프로그램 실행 중 CPU 연산(계산 작업)이 연속적으로 실행되는 상황
I/O burst
- 프로그램 실행 중 I/O 장치의 입출력이 이루어지는 상황
대부분의 프로세스는 두 프로세스 모두에 속함
1.3 CPU 스케줄링의 기본 목표
CPU 스케줄링
- 정의
실행 준비 상태(Ready)의 스레드 중 하나를 선택하는 과정 - 기본 목표
CPU 활용률 향상 → 컴퓨터 시스템 처리율 향상
컴퓨터 시스템에 따라 CPU 스케줄링의 목표가 다를 수 있음
1.4 CPU 스케줄링의 기준(criteria)
스케줄링 알고리즘의 다양한 목표와 기준
CPU 활용률(CPU utilization)
- 전체 시간 중 CPU의 사용 시간 비율, 운영체제 입장
처리율(throughput)
- 단위 시간당 처리하는 프로세스/스레드 개수, 운영체제 입장
공평성(fairness)
- CPU를 스레드들에게 공평하게 배분, 사용자 입장
- 시분할로 스케줄링
- 무한정 대기하는 기아 스레드(starving thread)가 생기지 않도록 스케줄
응답 시간(response time)
- 대화식 사용자의 경우, 사용자에 대한 응답 시간, 사용자 입장
대기 시간(wating time)
- 스레드가 준비 큐에서 머무르는 시간, 운영체제와 사용자 입장
소요 시간(turnaround time)
- 프로세스가 컴퓨터 시스템에 도착한 후 완료될 때까지 걸린 시간, 사용자 입장
- 배치 처리 시스템에서 주된 스케줄링의 기준
시스템 정책 우선(high policy enforcement)
- 컴퓨터 시스템의 특별한 목적을 달성하기 위한 스케줄링, 운영체제 입장
예) 실시간 시스템에서는
스레드가 완료 시한(deadline) 내에 이루어지도록 하는 정책
자원 활용률(high resource efficiency)
- CPU나 I/O 장치 등의 자원 활용률을 극대화하는 것
1.5 CPU 스케줄링과 타임 슬라이스
- 대부분의 운영체제에서
하나의 스레드가 오랜 시간동안 CPU를 사용하는 것을 허용하지 않음
타임 슬라이스(time slice)
- 스케줄된 스레드에게 한번 할당하는 CPU 시간
스레드가 CPU 사용을 보장받는 시간 - 커널이 스케줄을 단행하는 주기 시간
타이머 인터럽트의 도움을 받아 타임 슬라이스 단위로 CPU 스케줄링
현재 실행 중인 스레드 강제 중단(preemption), 준비 리스트에 삽입 - 타임 퀀텀(time quantum), 타임 슬롯(time slot)이라고도 함
02. CPU 스케줄링 기본
2.1 CPU 스케줄링이 실행되는 4가지 상황
시스템 호출에 의해 스케줄링
1) 스레드가 시스템 호출 끝에 I/O를 요청하여 블록될 때
- 스레드를 블록 상태로 만들고 스케줄링
- CPU 활용률 향상(유휴 시간 단축) 목적
2) 스레드가 자발적으로 CPU를 반환할 때
yield()시스템 호출 등을 통해 스레드가 자발적으로 CPU 반환- 커널은 현재 스레드를 준비 리스트에 넣고, 새로운 스레드 선택
- 자발적 CPU 양보
인터럽트 내에서 스케줄링
3) 스레드의 타임 슬라이스가 소진되어 타이머 인터럽트 발생
- 균등한 CPU 분배 목적
4) 더 높은 순위의 스레드가 요청한 입출력 작업 완료, 인터럽트 발생
- 현재 스레드를 강제 중단(preemption)시켜 준비 리스트에 넣고,
더 높은 순위의 스레드를 깨워 스케줄링- 우선순위를 지키기 위한 목적
2.2 CPU 스케줄링과 디스패치(dispatch)
CPU 스케줄링 코드의 위치와 실행 시점
- 스케줄링을 담당하는 커널 스레드나 프로세스는 존재하지 않는다.
- 스케줄링 코드는 커널 내 함수의 형태로 저장이 되어 있다.
스케줄링 코드는 커널 코드의 일부로서 호출되어야 실행되는 함수 형태
독립적으로 실행되는 프로세스나 스레드가 아님 - 스케줄링 코드는 시스템 호출이나
인터럽트 서비스 루틴이 끝나는 마지막 단계에서 실행
디스패처(dispatcher) 코드 실행
디스패처 코드
- 컨텍스트 스위칭을 실행하는 커널 코드
- 스케줄러 코드에 의해 선택된 스레드를 CPU가 실행하도록 하는 작업
- 커널 모드에서 사용자 모드로 전환
스케줄러와 디스패처 모두 실행 시간이 짧도록 작성되어야 함
스케줄러와 디스패처 코드가 실행되는 동안은
CPU가 동작하지 않는 유휴 시간(오버헤드)이기 때문임
2.3 스케줄링 타입: 선점 스케줄링과 비선점 스케줄링
실행중인 스레드의 강제 중단 여부에 따른 CPU 스케줄링
비선점 스케줄링(non-preemptive scheduling) 타입
- 현재 실행중인 스레드를 강제로 중단시키지 않는타입
스레드가 CPU를 할당받아 실행을 시작하면,
완료되거나 CPU를 더 이상 사용할 수 없는 상황이 될 때까지
스레드를 강제 중단시키지 않고 스케줄링도 하지 않는 방식 - 스케줄링 시점
CPU를 더 이상 사용할 수 없게 된 경우:
1) I/O로 인한 블록 상태 sleep 등
2) 자발적으로 CPU를 양보할 때
3) 종료할 때
선점 스케줄링(preemptive scheduling) 타입
- 현재 실행중인 스레드를 강제 중단시키고 다른 스레드 선택
- 스케줄링 시점
1) 타임 슬라이스가 소진되어 타이머 인터럽트가 발생할 때
2) 인터럽트나 시스템 호출 종료 시점에서,
더 높은 순위의 스레드가 준비 상태일 때
오늘날 범용 운영체제에서는 선점 스케줄링 타입을 사용한다.
2.4 기아와 에이징
기아(starving)
- 스레드가 스케줄링에서 선택되지 못한 채
오랜 시간 동안 준비 리스트에 있는 상황 - 사례
1) 우선순위를 기반으로 하는 시스템에서,
더 높은 순위의 스레드가 계속 시스템에 들어오는 경우
2) 짧은 스레드를 우선 실행시키는 시스템에서, 자신보다 짧은 스레드가 계속 도착하는 경우 - 스케줄링 알고리즘 설계 시 기아 발생을 면밀히 평가
기아가 발생하지 않도록 설계하는 것이 바람직함
에이징(aging)
- 기아의 해결책
- 스레드가 준비 리스트에 머무르는 시간에 비례하여
스케줄링 순위를 높이는 기법
오래 기다릴 수는 있지만 언젠가는 가장 높은 순위에 도달하는 것을 보장
03. CPU 스케줄링 알고리즘
3.1 FCFS(First Come First Served) 스케줄링
알고리즘
- 선입 선처리
- 먼저 도착한(큐의 맨 앞에 있는) 스레드 먼저 스케줄링
스케줄링 파라미터: 스레드 별 도착 시간
스케줄링 타입: 비선점 스케줄링
스레드 우선순위: 없음
기아: 발생하지 않음
- 스레드가 오류로 인해 무한 루프를 실행한다면, 뒤 스레드 기아 발생
성능 이슈
- 처리율 낮음
- 호위 효과(convoy effect) 발생
긴 스레드가 CPU를 오래 사용하면, 늦게 도착한 짧은 스레드 오래 대기
3.2 SJF(Shortest Job First) 스케줄링
알고리즘
- 최단 작업 우선 스케줄링
- 실행 시간(예상 실행 시간)이 가장 짧은 스레드 선택
- 스레드가 도착할 때
실행 시간이 짧은 순으로 큐 삽입 큐의 맨 앞에 있는 스레드 선택
스케줄링 파라미터: 스레드 별 예상 실행 시간
스레드의 실행 시간을 아는 것은 불가능. 비현실적
스케줄링 타입: 비선점 스케줄링
스레드 우선순위: 없음
기아: 발생 가능
- 짧은 스레드가 계속 도착하면,
긴 스레드는 실행 기회를 언제 얻을지 예측할 수 없음
성능 이슈
- 가장 짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화
문제점
- 실행 시간의 예측이 불가능하므로 현실에서는 거의 사용되지 않음
3.3 SRTF(Shortest Remaining Time First) 스케줄링
알고리즘
- 최소 잔여 시간 우선 알고리즘
- 남은 실행 시간이 가장 짧은 스레드 선택
스케줄링 파라미터: 스레드 별 예상 실행 시간과 남은 실행 시간 값
이 시간을 아는 것은 불가능. 비현실적
스케줄링 타입: 선점 스케줄링
스레드 우선순위: 없음
기아: 발생 가능
- 짧은 스레드가 계속 도착하면, 긴 스레드는 실행 기회를 언제 얻을 지 모름
성능 이슈
- 실행 시간이 가장 짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화
문제점
- 실행 시간 예측이 불가능하므로 현실에서는 거의 사용되지 않음
3.4 RR(Round Robin) 스케줄링
알고리즘
- 스레드들에게 공평한 실행 기회를 주기 위함
- 큐에 대기중인 스레드들을 타임 슬라이스 주기로 돌아가면서 선택
- 도착하는 순서대로 스레드들을 큐에 삽입
- 스레드가 타임 슬라이스를 소진하면 큐 끝으로 이동
스케줄링 파라미터: 타임 슬라이스
스케줄링 타입: 선점 스케줄링
스레드 우선순위: 없음
기아: 없음
- 스레드의 우선순위가 없고, 타임 슬라이스가 정해져 있어, 일정 시간 후에 스레드는 반드시 실행
성능 이슈 - 공평하고, 기아 현상 없고, 구현이 쉬움
- 잦은 스케줄링으로 인한 전체 스케줄링 오버헤드가 큼
특히 타임 슬라이스가 작을 때 더 큼 - 균형된 처리율
타임슬라이스가 크면 FCFS에 가까움, 적으면 SJF/SRTF에 가까움
늦게 도착한 짧은 스레드는 FCFS보다 빨리 완료되고,
긴 스레드는 SJF보다 빨리 완료됨
오늘날 운영체제는 RR 방식을 부분적으로 사용하고 있음
Time slice = 2ms인 경우
Time slice = 1ms인 경우
3.5 Priority 스케줄링
알고리즘
- 우선 순위에 따라 스레드를 실행시키기 위한 목적
- 가장 높은 우선순위를 가진 스레드 선택
현재 스레드가 종료되거나, 더 높은 우선순위를 갖는 스레드가 도착할 때,
가장 높은 순위의 스레드 선택
스케줄링 파라미터: 스레드 별 고정 우선순위
스케줄링 타입: 선점 스케줄링/비선점 스케줄링
더 높은 우선순위를 갖는 스레드가 도착했을 때,
- 선점 스케줄링: 현재 스레드 강제 중단하고 스케줄링
- 비선점 스케줄링: 현재 실행 중인 스레드가 종료될 때 스케줄됨
스레드 우선순위: 있음
기아: 발생 가능
- 높은 우선순위를 갖는 스레드가 계속 도착하는 경우,
실행 기회를 언제 얻을지 예측할 수 없음 - 큐 대기 시간에 비례하여
일시적으로 우선순위를 높이는 에이징 방법으로 해결 가능
성능 이슈
- 높은 우선순위의 스레드일수록 대기 혹은 응답시간 짧음
특징
- 스레드별 고정 우선순위를 갖는 실시간 시스템에서 사용
3.6 MQL(Multi-level Queue) 스케줄링
설계 의도
- 스레드들을 n개의 우선순위 레벨로 구분,
레벨이 높은 스레드를 우선 처리하는 목적
알고리즘
- 고정된 n개의 큐 사용, 각 큐에 고정 우선순위 할당
- 스레드들의 우선순위도 n개의 레벨로 분류
- 각 큐는 나름대로의 기법으로 스케줄링
- 스레드는 도착 시 우선순위에 따라 해당 레벨 큐에 삽입.
다른 큐로 이동할 수 없음 - 가장 높은 순위의 큐가 빌 때, 그 다음 순위의 큐에서 스케줄링
스케줄링 파라미터: 스레드의 고정 우선순위
스케줄링 타입: 선점/비선점 스케줄링
스레드 우선순위: 있음
더 높은 우선순위를 갖는 스레드가 도착했을 때,
- 선점 스케줄링: 현재 스레드 강제 중단하고 스케줄링
- 비선점 스케줄링: 현재 실행 중인 스레드가 종료될 때 스케줄됨
기아: 발생 가능
- 높은 순위의 스레드가 계속 도착하는 경우
실행 기회를 언제 잡을 지 예상할 수 없음
성능 이슈
- 스레드의 고정 순위를 가진 시스템에서 활용
예)
1) 전체 스레드를 백그라운드/포그라운드 스레드의 2개의 그룹으로 구성
2) 시스템/대화식/배치 스레드의 3개의 레벨로 나누고,
시스템 스레드를 우선적으로 스케줄링
3.7 MLFQ(Multi-level Feedback Queue) 스케줄링
설계 의도
- 1962년에 개발된 알고리즘
- MLQ의 기아를 없애기 위해 여러 레벨의 큐 사이에 이동이 가능하도록 설계
- 짧은 스레드와 I/O가 많은 스레드, 대화식 우선 처리.
스레드 평균 대기 시간 줄임
MLQ와 달리 스레드에 우선순위가 없으며, 큐에만 존재함
n개의 레벨 큐
- n개의 고정 큐
- 큐마다 서로 다른 스케줄링 알고리즘
- 큐마다 스레드가 머무를 수 있는 큐 타임 슬라이스가 있음
- 낮은 레벨의 큐일수록 더 긴 타임 슬라이스
레벨이 낮을수록 더 많은 시간 할당 - I/O 집중 스레드(대화식 스레드)는 높은 순위의 큐에 있을 가능성 높음
알고리즘
- 스레드는 도착 시 최상위 레벨 큐에 삽입
- 가장 높은 레벨 큐에서 스레드 선택
비어 있으면 그 아래의 큐에서 스레드 선택 - 스레드의 CPU-burst가 큐 타임 슬라이스를 초과하면 강제로 아래 큐로 이동
- 스레드가 자발적으로 중단한 경우, 현재 큐 끝에 삽입
- 스레드가 I/O로 실행이 중단된 경우 I/O가 끝나면 동일 레벨 큐 끝에 삽입
- 큐에 있는 시간이 오래되면 기아를 막기 위해 하나 위 레벨 큐로 이동
- 최하위 레벨 큐는 주로 FCFS나 긴 타임 슬라이스의 RR로 스케줄
스케줄링 파라미터: 각 큐의 큐 타임 슬라이스
스케줄링 타입: 선점 스케줄링
스레드 우선순위: 없음
기아: 발생하지 않음
- 큐에 대기하는 시간이 길어지면, 더 높은 레벨의 큐로 이동(에에징)
성능 이슈
- CPU 시간을 작게 소모하고,
입출력이 빈번한 , 또는 대화식 스레드가 높은 우선순위로 실행됨
04. 멀티 코어 CPU에서의 스케줄링
4.1 멀티 코어 CPU와 병렬 처리
싱글 코어의 구조
4.2 멀티 코어 시스템에서 CPU 스케줄링과 작업 분배
멀티 코어 시스템에서 싱글 코어 CPU 스케줄링을 사용할 때 문제점
-
컨텍스트 스위치 오버헤드 증가
이전에 실행된 적이 없는 코어에 스레드가 배치될 때,
캐시에 새로운 스레드의 코드와 데이터로 채워지는 긴 시간 경과 -
코어별 부하 불균형
스레드를 무작위로 코어에 할당하면,
코어마다 처리할 수 있는 스레드 수의 불균형 발생
컨텍스트 스위칭 후 오버헤드-코어 친화성으로 해결
CPU 친화성(CPU affinity)
- 스레드를 동일한 코어에서만 실행하도록 스케줄링
- 코어 친화성(core affinity), CPU 피닝(pinning),
캐시 친화성(cache affinity)이라고도 부름 - 코어 당 스레드 큐 사용
코어별 부하 불균형-부하 균등화 기법으로 해결
-
푸시 마이그레이션(push migration) 기법
감시 스레드가 짧거나,
빈 큐를 가진 코어에 다른 큐의 스레드를 옮겨 놓는 기법 -
풀 마이그레이션(pull migration) 기법
코어가 처리할 스레드가 없게 되면,
다른 코어의 스레드 큐에서 자신이 큐로 가져와 실행
