CPU 스케줄링

CPU 스케줄링이 필요한 이유

• CPU, 디스크, 프린터, 파일, 데이터베이스 등과 같은 자원(Resource)에 대한 스레드들의 경쟁속에서 스레드 하나를 선택해야 함. 

 

컴퓨터 시스템 내의 다양한 스케줄링

• 작업(job) 스케줄링
  - batch 시스템에서 대기중인 작업(job) 중 메모리에 적재할 작업을 선택하는 스케줄링
• CPU 스케줄링
  - 프로세스/스레드 중 하나를 선택하여 CPU를 할당하는 스케줄링이며 오늘날 운영체제의 스케줄 단위는 스레드
• 디스크 스케줄링
  - 디스크 장치 내에서 입출력 요청 중 하나를 선택하는 스케줄링
• 프린터 스케줄링
  - 프린팅 작업 중 하나를 선택하여 프린터에 할당하는 스케줄링

 

 

다중프로그래밍의 도입 목적과 다중프로그래밍과 함께 도입된 스케줄링

 

다중프로그래밍 도입 목적 -> CPU 유휴시간을 줄여 활용률을 높이기 위함

• 다중프로그래밍과 함께 도입된 스케줄링
  - 작업 스케줄링(job scheduling) : 디스크 장치로부터 메모리에 올릴 작업을 선택하는 스케줄링으로 메모리에 처음 올리거나 이후 프로세스가 종료될때마다 작동
  - CPU 스케줄링(CPU scheduling) : 메모리에 적재된 작업 중 CPU에 실행시킬 작업을 선택 (Ready Queue)

 

CPU Burst와 I/O Burst

• CPU Burst : 프로그램 실행 도중 CPU 연산작업이 연속적으로 실행되는 상황
• I/O Burst : 프로그램 실행 중 I/O장치의 입출력이 이루어지는 상황

-> CPU Burst가 대부분인 프로세스는 CPU Intensive Process

-> I/O Burst가 대부분인 프로세스는 I/O Intensive Process

 

 

CPU 스케줄링의 정의와 목적

목적 -> 실행 준비 상태(Ready Queue에 삽입된) 스레드 중 하나를 선택하는 과정

목표 -> CPU 활용률 향상에서 오는 컴퓨터 시스템 처리율 향상

※ 하지만 컴퓨터 시스템에 따라 CPU 스케줄링의 목적은 다를 수 있음
- 예시로 실시간 운영체제의 경우 활용률 향상보다 스케줄링된 작업의 완료를 우선으로 함

 

 

CPU 스케줄링의 기준

• CPU 활용률(CPU Utilization)
  - 전체 시간 중 CPU가 쉬지않고 사용하는 시간의 비율, 운영체제 입장에서의 평가 기준
• 처리율(Throughput)
  - 단위 시간 당 처리하는 스레드 개수의 비율, 운영체제 입장에서의 평가 기준
• 공평성(Fairness)
  - CPU를 스레드들에게 공평하게 배분하는 것, 사용자 입장에서의 평가 기준
  - 시분할로 스케줄링하여 무한정 대기하는 기아 스레드(Starving Thread)가 생기지 않도록 스케줄링
• 응답 시간(Response Time)
  - 대화식 사용자에 대한 응답시간, 사용자 입장에서의 평가 기준
• 대기 시간(Waiting Time)
  - 스레드가 준비 큐(Ready Queue)에서 머무르는 시간, 운영체제와 사용자 양방향에서의 평가 기준
• 소요 시간(Turnaround Time)
  - 스레드가 컴퓨터 시스템에 도착한 후(혹은 생성된 후) 완료까지 걸린 시간, 사용자 입장에서의 평가 기준
  - 주로 batch 시스템에서의 스케줄링 기준
• 시스템 정책(Policy Enforcement) 우선
  - 컴퓨터 시스템의 특수 목적을 달성하기 위한 스케줄링, 운영체제 입장에서의 평가 기준
  - ex) RT OS에서는 스레드가 특정 Deadline 이내에 이루어지도록 하는 정책을 채택
  - ex) 은행 시스템에서는 안전을 관리하는 스레드를 우선 실행하는 정책을 채택
• 자원 활용률(Resource Efficiency)

 

타임 슬라이스

오늘날 대부분의 운영체제에서 하나의 스레드가 너무 오랫동안 CPU를 점유하는 것을 허용하지 않음

• 타임 슬라이스 (Time Slice)
  - 스케줄 된 스레드에게 한 번 할당하는 CPU 시간을 의미
  - 커널이 스케줄을 시행하는 주기 시간을 의미
  - 커널에서 타이머 인터럽트의 도움을받아 해당 타임 슬라이스 단위로 CPU를 스케줄링 함
  - 타이머 인터럽트로 설정한 타임 슬라이스가 오버되면 강제 중단(Preemption)한 뒤 준비 큐(Ready Queue)에 삽입

 

CPU 스케줄링이 실행되는 상황

• 스레드가 시스템 호출로 I/O를 요청하여 Block될 때 -> CPU 활용률 향상 목적
  - 스레드를 Block 상태로 만들고 블록 큐(Block Queue)나 I/O 대기 큐(I/O Queue)에 삽입한다.
  - 이후 준비 큐(Ready Queue)의 다른 스레드를 스케줄하여 실행한다.
• 스레드가 자발적으로 CPU를 반환할 때
  - yield() 시스템 호출 등을 통해 스레드가 자발적으로 CPU를 반환
  - 반환시 커널은 현재 스레드를 준비 큐(Ready Queue)에 넣고 준비 큐(Ready Queue)에서 다른 스레드를 스케줄
• 스레드의 타임 슬라이스가 소진되어 타이머 인터럽트가 발생한 경우 -> 균등한 CPU 분배 목적
  
• 더 높은 순위의 스레드가 요청한 I/O 작업이 완료되어 인터럽트 발생 시 -> 우선순위를 지키기 위한 목적
  - 인터럽트 요청한 스레드보다 우선순위가 낮은 현재 스레드를 강제 중단시켜 준비 큐(Ready Queue)에 삽입
  - 인터럽트 요청한 높은 우선순위의 스레드를 깨워 스케줄링

 

CPU 스케줄링 코드의 위치와 실행 시점

스케줄링 코드 : 준비 큐에서 어떤 스레드를 선택하는 코드

• 스케줄링을 담당하는 커널 스레드나 프로세스는 따로 존재하지 않는다
• 스케줄링을 담당하는 스케줄링 코드는 커널 코드의 일부로서 호출되어 실행되는 커널 내 함수의 형태이며 독립적으로 실행되는 프로세스나 스레드가 아님
• 스케줄링 코드는 시스템 호출이나 인터럽트 서비스 루틴의 마지막 단계에서 실행

 

디스패처 코드 : 선택된 다음 컨텍스트 스위칭을 시행하는 코드

• 스케줄러 코드로 선택된 스레드를 CPU가 실행하도록 하는 작업
• 커널 모드에서 사용자모드로 전환하는 작업도 겸함

-> 스케줄링코드와 디스패처코드의 실행시간은 사실상 오버헤드이므로 둘 다 실행시간이 짧도록, 효율적으로 작성해야함

 

 

선점 스케줄링과 비선점 스케줄링

실행중인 스레드의 강제 중단 여부에 따라 비선점 스케줄링과 선점 스케줄링으로 나누어진다

• 비선점 스케줄링
  - 현재 실행중인 스레드를 강제로 중단시키지 않는 방식
  - 스케줄링 시점은 스레드의 I/O요청, sleep, yield, 스레드 종료(타임슬라이스를 기반으로한 강제중단은 없음)
  - 현재 실행중인 스레드가 매우 긴 작업일 경우, 후위의 스레드는 스케줄링되지 않는 기아 스레드가 발생함
• 선점 스케줄링
  - 현재 실행중인 스레드를 강제 중단시키고 다른 스레드를 선택하는 방식
  - 스케줄링 시점은 비선점 스케줄링의 시점과 더해 타임슬라이스 소진으로 인한 타이머 인터럽트와 더 높은 우선순위의 스레드가 준비 상태일 때

 

기아와 에이징

• 기아(Starvation) : 스레드가 스케줄링에서 선택되지 못한 채 오랫동안 준비 큐(Ready Queue)에 있는 상황
  - 사례 1 : 우선순위 기반 시스템에서 더 높은 순위의 스레드가 계속 시스템에 들어오는 경우
  - 사례 2 : 짧은 스레드를 우선 스케줄하는 시스템에서 자신보다 짧은 스레드가 계속 들어오는 경우
  - 이 기아 스레드가 발생하지 않도록 알고리즘 설계를 면밀히 해야함
• 에이징(Aging) : 기아 스레드 발생의 해결책으로, 스레드가 준비 큐에 머무르는 시간에 비례하여 스케줄링 순위를 점차 높이는 기법
  - 이 기법으로 오래 기다릴 수도 있지만, 언젠가 높아진 순위로 스케줄링 받는 것을 보장함

 

CPU 스케줄링 알고리즘의 종류

• 비선점 스케줄링
  - FCFS(First Come First Served) : 도착한 순서대로 처리하는 스케줄링 기법
  - SJF(Shortest Job First) : 짧은 실행시간을 가지는 스레드를 우선으로 처리하는 스케줄링 기법
• 선점 스케줄링
  - SRTF(Shortest Remaining Time First) : 남은 작업 시간이 짧은 스레드가 준비 큐에 들어오면 이를 우선적으로 처리하는 기법
  - RR(Round - Robin) : 스레드들을 돌아가면서 할당된 다임슬라이스 만큼 실행하는 기법
  - MLFQ (MultiLevel Feedback Queue scheduling)
  1. 큐만 n개의 우선순위 레벨로 할당하고, 스레드는 동일한 우선순위
  2. 스레드는 제일 높은 순위의 큐에 삽입되고 큐의 타임슬라이스가 다하면 아래 레벨의 큐로 이동
  3. 낮은 레벨의 큐에 오래 있으면 높은 레벨의 큐로 이동
• 비선점 / 선점 스케줄링을 둘 다 구현 가능한 스케줄링 기법
  - Priority Schedulling (우선순위 스케줄링) : 우선 순위를 기반으로 하는 스케줄링 기법. 가장 높은 순위의 스레드를 먼저 실행
  - MLQ (MultiLevel Queue scheduling)
  1. 스레드와 큐 모두 n개의 우선순위 레벨로 할당하고 스레드는 자신과 동일한 레벨의 큐에 삽입됨
  2. 가장 높은 우선순위의 큐에서 스케줄링을 하며, 해당 큐가 비었을 경우 차순위의 큐에서 스케줄링
  3. 스레드는 다른 큐로 이동하지 못함

 

 

1. FCFS (First Come First Served)

• 알고리즘 : 선입선출, 선입 선처리로 먼저 도착하여 준비 큐의 맨 앞에있는 스레드를 먼저 스케줄링
• 스케줄링 알고리즘 변수 : 스레드 별 준비 큐에 도착한 시간, 10시 1분, 10시 2분에 도착한 두 스레드 중 더 일찍 도착한 10시 1분의 스레드를 선택
• 스케줄링 타입 : 비선점 스케줄링
• 스레드 우선순위 : 없음
• 기아 스레드 : 발생하지 않으나 현 스레드가 무한 루프에 빠지면, 비선점 방식으로 인해 중단할 수 없으므로 뒤의 스레드에 기아가 발생할 수 있음
• 성능 특징 
  - 처리율이 낮음 : 실행 시간이 매우 긴 스레드가 CPU를 점유중일 때 실행 시간이 짧은 다른 스레드들이 준비 큐에 있어도 스케줄링 되지 않으므로 처리율이 낮을 수 밖에 없음(호위 효과, Convoy Effect)
  - 호위 효과(Convoy Effect) : 실행 시간이 긴 스레드가 CPU를 점유하고 있을 때, 실행 시간이 짧은 다른 스레드들이 마치 부하가 호위하는 형태처럼 뒤따라서 계속 기다리고 있다는 것을 뜻하는 효과

 

2. SJF (Shortest Job First)

• 알고리즘 : 최단 작업 우선 스케줄링, 즉 실행 시간이 가장 짧은 스레드 순으로 준비 큐에 삽입하고, 맨 앞에 있는 스레드를 선택하는 방식
• 스케줄링 알고리즘 변수 : 스레드 별 예상 실행 시간, 하지만 스레드의 실행 시간을 아는 것은 불가능하므로 비현실적
• 스케줄링 타입 : 비선점 스케줄링
• 스레드 우선순위 : 없음
• 기아 스레드 : 발생 가능하며 짧은 스레드가 계속 도착하면, 긴 스레드는 실행 기회를 얻지 못한 채 기아 스레드 상태에 빠질 수 있음
• 성능 특징
  - 장점 : 가장 짧은 스레드가 먼저 실행되므로 평균 대기시간을 최소화할 수 있음
  - 단점 : 실행 시간이 예측 불가능하므로 현실에서는 사용되지 않음

 

3. SRTF (Shortest Remaining Time First)

• 알고리즘 : 최단 잔여 시간 우선 스케줄링, 즉 남은 실행 시간이 가장 짧은 스레드 순으로 준비 큐에 삽입하고, 맨 앞의 스레드를 선택하여 선점 스케줄을 시행하는 방식. SJF의 선점 스케줄링 버전
• 스케줄링 알고리즘 변수 : 스레드 별 예상 실행 시간과 남은 실행 시간, 하지만 이 값들을 아는 것은 불가능하므로 여전히 비현실적
• 스케줄링 타입 : 선점 스케줄링
• 스레드 우선순위 : 없음
• 기아 스레드 : 발생 가능하며 SJF와 같이 짧은 스레드가 계속 도착하면 긴 스레드는 실행  기회를 얻을 수 없음
• 성능 특징 : SJF와 같음

 

4. RR(Round - Robin)

• 알고리즘 : 스레드들에게 공평한 실행 기회를 제공하기 위해 큐에 대기중인 스레드들을 타임슬라이스 주기로 돌아가면서 선택함.
  - 스레드는 도착하는 순서대로 큐에 삽입되며, 스레드가 타임 슬라이스를 소진하면 큐의 맨 뒤로 돌아감
• 스케줄링 알고리즘 변수 : 타임 슬라이스
• 스케줄링 타입 : 선점 스케줄링
• 스레드 우선순위 : 없음
• 기아 스레드 : 발생하지 않음. 스레드의 우선순위가 없고 타임슬라이스가 소진되면 강제로 큐의 맨 뒤로 삽입되므로, 후위 스레드는 일정 시간 이후에는 반드시 실행됨
• 성능 특징
  - 장점
  1. 공평하고, 기아 스레드가 발생하지 않으며 구현이 쉬움.
  2. 균형된 처리율 제공 : 늦게 도착한 짧은 스레드는 FCFS보다 빠르게, 늦게 도착한 긴 스레드는 SJF/SRTF보다 빠르게 완료되며 타임 슬라이스가 크면 FCFS에 수렴하고 타임슬라이스가 작으면 SJF/SRTF에 수렴함
  - 단점 : 잦은 스케줄링으로 인해 컨텍스트 스위칭이 자주 일어나 스케줄링의 오버헤드가 커짐. 이는 타임 슬라이스가 작을수록 극대화
  
  

 

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

• 알고리즘
  - 우선순위에 따라 스레드를 실행시키기 위해 가장 높은 순위의 스레드를 선택(현재 스레드가 종료되거나 더 높은 순위의 스레드가 도착할 때 스케줄링 시행)
  - 모든 스레드에 개별적으로 고정 우선순위를 할당하며, 이는 스레드가 종료할 때 까지 바뀌지 않음
  - 우선순위가 할당된 스레드들은 우선순위 순으로 준비 큐에 삽입
• 스케줄링 알고리즘 변수 : 스레드 별 할당된 고정 우선순위
• 스케줄링 타입 : 선점 스케줄링 / 비선점 스케줄링 둘 다 가능
  - 선점 스케줄링의 경우 : 더 높은 우선순위의 스레드가 도착하면 현재 스레드를 preemption하고 스케줄링함
  - 비선점 스케줄링의 경우 : 더 높은 우선순위의 스레드가 도착하여도 일단 현재 실행중인 스레드가 종료되면 스케줄링 함
• 스레드 우선순위 : 있음
• 기아 스레드 : 발생 가능
  - 높은 순위의 스레드가 계속 도착할 경우, 실행 기회를 얻지 못해 기아 스레드 발생
  - 이는 에이징 기법으로 해결 가능
• 성능 특징
  - 높은 우선순위의 스레드일수록 대기시간, 응답시간이 짧음
  - 스레드별 고정 우선순위를 가지는 실시간 시스템(RT-os)에서 사용

 

 

6. MLQ(MultiLevel Queue Scheduling) 스케줄링

스레드들을 n개의 우선 순위 레벨로 구분하고, 레벨이 높은 스레드를 우선으로 처리하기 위해 설계된 스케줄링 기법

• 알고리즘
  - 고정된 n개의 큐를 사용하며, 각 큐는 우선 순위 레벨 별로 구분된다.
  - 스레드들도 큐와 같이 n개의 우선 순위 레벨로 분류된다.
  - 각 큐는 해당 큐에 맞는 자신만의 스케줄링 기법을 사용한다. 즉 각 레벨의 큐마다 스케줄러가 따로 존재함 (예시로 Level 0의 큐에는 FCFS, Level 1의 큐에는 SJF를 기용할 수 있음)
  - 스레드는 도착 시 우선순위에 따라 해당 레벨의 큐에 삽입되며, 다른 큐로 이동할 수 없다.
  - 가장 높은 우선 순위 레벨의 큐가 비어 있다면, 그 다음 순위의 큐에서 스케줄링한다.
• 스케줄링 알고리즘 변수 : 스레드의 고정 우선 순위
• 스케줄링 타입 : 비선점 / 선점 스케줄링 모두 가능
  - 비선점 스케줄링 : 더 높은 우선순위의 스레드가 도착하여도 일단 현재 실행중인 스레드가 종료되면 스케줄
  - 선점 스케줄링 : 높은 우선 순위 레벨의 큐에 스레드가 도착한다면, 현재 스레드를 preemption하고 높은 우선 순위 레벨의 큐에 도착한 해당 스레드를 스케줄링
• 스레드 우선순위 : 있음
• 기아 스레드 : 발생 가능.
  - 높은 우선 순위 레벨의 큐에 스레드가 계속 도착할 경우 낮은 레벨의 큐에 존재하는 스레드들은 언제 실행될 지 예상할 수 없음
• 성능 특징
  - 스레드의 고정 순위를 가진 시스템에서 활용
  - 예) 전체 스레드를 백그라운드 스레드, 포그라운드 스레드, 총 두 개의 그룹으로 구성하여 포그라운드 스레드를 우선으로 스케줄

MLQ Scheduling

 

 

7. MLFQ  (MultiLevel Feedback Queue Scheduling) 스케줄링

기아 스레드 발생을 없애기 위해 MLQ에서 큐 사이에 스레드의 이동을 가능하도록 설계하였으며 짧은 스레드와 I/O가 많은 스레드, 대화식 스레드를 우선적으로 처리하여 스레드들의 평균 대기시간을 줄임

• 우선순위 레벨 큐
  - 고정된 n개의 큐를 사용하며 각 큐마다는 서로 다른 스케줄러가 존재하고 MLQ와 같이 서로 다른 스케줄링 알고리즘을 가질 수 있음
  - 큐에는 준비(Ready) 상태의 스레드들이 저장되며 큐마다 스레드가 머물 수 있는 큐 타임 슬라이스가 존재
  - 우선순위가 높으면 낮은 큐 타임 슬라이스, 우선순위가 낮으면 높은 큐 타임 슬라이스를 가짐
  - I/O 집중 스레드(대화식 스레드)는 높은 순위의 큐에 있을 가능성이 높음
• 알고리즘
  - 스레드는 도착 시 최상위 우선순위 레벨의 큐에 삽입됨
  - 최상위 우선순위 레벨의 큐에 존재하는 스레드부터 스케줄링하며, 비어있으면 차순위 큐에서 선택
  - 스레드의 CPU-Burst가 해당 큐의 큐 타임 슬라이스를 초과하면 강제로 아래 큐로 이동시킴(Priority Down)
  - 스레드가 자발적으로 양보할 경우(yield) 현재 큐의 맨 끝에 삽입
  - 스레드가 I/O로 Block된 경우, I/O작업이 끝났을 때 동일 레벨의 큐의 맨 끝에 삽입
  -> 즉 우선순위가 감소하는(Priority Down)상황은 큐 타임 슬라이스를 초과할 때 말고는 없음
  
  - 큐에 머무르는 시간이 길어지면 기아 스레드를 막기 위해 한 단계 상위 레벨의 큐로 이동(실행 도중 우선순위를 동적으로 조정함)
  - 최하위 레벨의 큐는 FCFS나 긴 타임 슬라이스의 RR로 스케줄링
• 스케줄링 알고리즘 변수 : 각 큐의 큐 타임 슬라이스
• 스케줄링 타입 : 선점 스케줄링
• 스레드 우선순위 : 없음(처음은 최상위 큐로 삽입되며 이후 에이징 기법으로 실행 도중 동적으로 조정함)
• 기아 스레드 : 발생하지 않음
  - 큐에 대기하는 시간이 길어지면, 상위 우선 순위 레벨의 큐로 이동시킴(에이징 기법)
• 성능 특징
  - 짧거나 입출력이 빈번한 스레드, 대화식 스레드를 높은 레벨의 큐에서 빠르게 실행 -> CPU 활용률이 높음

 

 

멀티코어 시스템에서의 CPU 스케줄링

멀티코어 시스템에서 싱글 코어 CPU 스케줄링 기법을 사용할 때 문제점

1. 컨텍스트 스위칭 후 오버헤드 문제

- 스레드 복귀 시 이전에 실행된 적 없는 코어에 스레드가 배치될 때 시행되는 컨텍스트 스위칭은 오버헤드가 매우 큼
- 오버헤드 : 메모리에 저장해둔 컨텍스트(코드, 데이터 등)이 캐시에 채워지는 경과 시간

2. 코어별 부하 불균형 문제

- 스레드를 무작위로 코어에 할당하면, 코어마다 처리할 스레드의 수가 불균형함

 

1번 문제 해결 방안

• CPU 친화성(CPU Affinity) 적용
  - 스레드를 동일한 코어에서만 실행되도록 스케줄링하는 기법
  - 코어 친화성(Core Affinity), CPU 피닝(pinning), 캐시 친화성(cache affinity)라고도 명칭
• 코어 당 스레드 큐 사용

 

2번 문제 해결 방안

부하 균등화 기법 적용

• - 푸시 마이그레이션(Push migration) 기법 : 감시 스레드를 두고, 감시 스레드가 짧거나 빈 큐를 가진 코어에 다른 큐의 스레드를 옮겨놓는 기법
• - 풀 마이그레이션(Pull migration) 기법 : 코어가 처리할 스레드가 없어지면, 다른 코어의 큐에서 자신의 큐로 가져오는 기법