CPU 스케줄링

실행 대기중인 프로세스(스레드)중 하나를 선택하는 과정.

CPU의 유휴 시간(CPU가 노는 시간)을 최소화하여 CPU의 활용률을 극대화한다.

컴퓨터 시스템 처리율의 향상을 목적으로 한다.

 

CPU 스케줄링이 시행되는 4가지 경우

1. 스레드가 시스템 호출 끝에 I/O를 요청하여 Block될 때.

2. 스레드의 CPU 타임 슬라이스를 모두 소진하여 타이머 인터럽트가 발생할 때..

3. 스레드가 자발적으로 CPU를 반환하여 새로운 스레드를 선택해야 할 때.

4. 더 높은 우선순위의 스레드가 요청한 입출력 작업이 완료되어 인터럽트가 발생할 때.

 

타임 슬라이스

커널이 스케줄을 단행하는 주기 시간.

스케줄 된 스레드에게 할당하는 CPU 시간.

CPU는 타이머 인터럽트의 도움을 받아 타임 슬라이스를 단위로 스케줄링한다.

타임 슬라이스가 다한 스레드의 경우 강제 중단(선점)당하여 준비 리스트에 삽입된다.

 

선점, 비선점 스케줄링

스레드를 강제중단할 수 있느냐 없느냐에 따라 선점과 비선점이 갈린다.

선점 스케줄링

운영체제가 실행중인 프로세스(스레드)를 강제로 중단시키고 다른 프로세스(스레드)를 선택하여 CPU를 할당.

시분할 시스템의 기본 스케줄링.

타임 슬라이스가 지나 타이머 인터럽트가 발생할 때, 인터럽트나 시스템 호출 종료 시점에 더 높은

우선순위의 프로세스(스레드)가 진입하거나 준비 상태일 때 선점 스케줄링이 실행된다.

범용 운영체제 대부분은 선점 스케줄링 방식을 수용한다.

 

비선점 스케줄링

현재 실행중인 프로세스를 강제로 중단시키지 않는 방식.

CPU를 사용할 수 없게 된 경우(I/O 요청 등)와 자발적으로 CPU를 양보하는 경우, 스레드가 종료되는 경우

비선점 스케줄링이 실행된다.

 

CPU 스케줄링 알고리즘

CPU가 스케줄링을 할 때 사용하는 알고리즘들.

FCFS(First Come First Served)

큐에 도착한 순서대로 프로세스를 실행시킨다. 단순하고 구현하기 쉬운 것이 주요 특징

비선점 스케줄링 타입. 우선순위가 없으며 기아가 발생하지 않는다. 하지만 성능이 비효율적임.

 

SJF(Shortest Job First)

실행 시간이 가장 짧은 프로세스를 먼저 실행시켜 프로세스들의 평균 대기시간을 최소화한다.

프로세스가 도착할 때, 실행 시간이 짧은 순으로 큐에 삽입된다.

비선점 스케줄링 타입, 우선 순위가 없음. 기아 발생 가능.

지속적으로 짧은 프로세스가 도착하는 경우 긴 프로세스는 실행 기회를 얻지 못한다.

aging 기법으로 해결 가능하지만 실행 시간 예측이 현실적으로 불가능하므로 사용되지 않는 알고리즘.

 

SRTF(Shortest Remaining Time First)

SJF와 기본적으로 같으나 선점 스케줄링 타입이다. 컨텍스트 스위칭이 자주 발생함.

남은 실행시간이 가장 짧은 프로세스를 선택.

프로세스가 실행 중 다른 프로세스가 도착하고 도착한 프로세스의 실행 시간이 더 짧으면 실행하고 있던

프로세스를 강제 종료하고 더 짧은 시간의 프로세스를 실행.

이 방법 또한 실행 시간 예측이 불가능하다는 이유로 사용되지 않는 알고리즘.

 

Round Robin

모든 프로세스에게 공평한 실행 기회를 제공하기 위해 타임 슬라이스 간격으로 프로세스를 번갈아 실행.

큐에 대기중인 프로세스들을 타임 슬라이스를 주기로 돌아가면서 선택.

도착하는 순서대로 큐에 삽입된다. 타임 슬라이스가 지나고 프로세스가 끝나지 않았다면 큐의 끝에 삽입됨.

선점 스케줄링. 타임 슬라이스에 의해 강제 중단된다.

우선순위가 없으며 기아가 발생하지 않는다.

공정하며, 구현이 쉽지만 잦은 스케줄링으로 스케줄링 오버헤드가 크다.

타임 슬라이스가 클수록 FIFO에 가까워지고 작을수록 SJF/SRTF에 가까워지는 알고리즘.

타임 슬라이스를 적당히 조절하는 것이 중요하다.

 

Fixed Priority preemptive scheduling

프로세스에 우선순위를 두는 컴퓨터 시스템에서 우선순위에 따라 프로세스를 실행.

가장 높은 우선순위의 프로세스를 선택한다.

모든 프로세스에 고정 우선순위를 할당. 종료될 때까지 바뀌지 않는다.

선점 스케줄링.

우선순위가 존재하며 기아가 발생할 수 있다.

지속적으로 높은 우선순위의 프로세스가 들어올 경우 우선순위가 낮은 프로세스에게서 기아가 발생할 수 있음.

이 또한 aging 기법으로 해결이 가능.

 

MLQ(Multi-Level Queue scheduling)

프로세스들을 n개의 우선순위 레벨로 구분하여 n개의 큐를 준비 각 큐에 우선순위를 할당하여

우선순위가 높은 큐 안의 프로세스 먼저 스케줄하는 방식.

가장 높은 우선순위의 큐가 빌 경우 그 다음 우선순위의 큐의 프로세스가 실행되는 방식.

선점, 비선점 모두 가능.

우선 순위가 존재함, 기아가 발생할 수 있음.

 

MLFQ(Multi-Level Feedback Queue scheduling)

MLQ와 같지만 우선순위가 할당된 큐 사이에 프로세스 이동이 가능하도록 설계된 스케줄 방식.

프로세스는 도착 시 항상 최상위 우선순위의 큐 끝에 삽입됨.

각 큐는 큐 시간 할당량을 가지며 프로세스가 시간 할당량을 넘어서면 아래 우선순위의 큐로 이동.

프로세스가 큐에 있는 시간이 오래되면 기아를 방지하기 위해 위의 우선순위의 큐로 이동.

우선순위를 가지지만 기아가 발생하지 않는 스케줄링 방식.

 

CPU 스케줄링 알고리즘의 평가 기준

- CPU 활용률

전체 시간 중 CPU의 사용 시간 비율, 이를 높이는 것이 스케줄링의 기본 목표 , 운영체제 입장

- 처리율

단위 시간 당 처리하는 프로세스의 개수 , 운영체제 입장

- 응답 시간

명령에 응답하는데 걸리는 평균 시간 , 사용자 입장

- 대기 시간

프로세스가 준비 큐에서 머무르는 시간, 운영체제와 사용자 입장

- 소요 시간

스레드가 컴퓨터 시스템에 도착한 후 완료될 때까지 걸린 시간. 배치 처리 시스템에서 주된 스케줄링 기준, 사용자 입장

- 공정성

CPU를 모든 스레드에게 얼마나 공정하게 배분하는 가, 기아 스레드가 발생하는가.

- 시스템 정책

 

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

멀티 코어 시스템에서 단일 코어 시스템의 CPU 스케줄링을 그대로 사용할 경우 문제점이 생긴다.

1. 스레드 사이의 컨텍스트 스위칭 시간이 길어진다.

해당 코어 이전에 실행된 적이 없는 스레드가 배치되면

현재 캐시를 모두 새로 배치된 스레드의 코드와 데이터로 갈아 채워야 하는 문제가 발생한다.

이로 인해 발생하는 컨텍스트 스위칭 시간을 줄이기 위해 Core affinity(코어 친화성)을 도입한다.

코어에 실행된 기록이 있는 스레드를 우선하여 스케줄.

코어 당 스레드 큐를 사용.

한 스레드는 동일한 코어에서 계속 실행되도록 강제하는 방법.

 

2. 코어 사이의 부하 불균형

프로세스나 스레드를 무작위로 코어에 할당하면, 특정 코어에는 몰리고 다른 코어는 놀게 되는 문제 발생.

작업 부하의 비균등성 문제는 작업 부하 균등 알고리즘으로 해결.

Load Balancing.

다중 CPU 혹은 멀티 코어를 가진 CPU에서 프로세스들이 여러 프로세서에 균등하게 분배됨으로써

실행 시간을 최소화하는 기법.

각 코어당 run queue를 두고, idle 상태의 코어가 존재하지 않도록 작업을 분배.

푸시 마이그레이션(push migration)

별도의 커널 스레드가 run queue를 감시하고 run queue가 짧거나 idle 상태인 코어가 있는 경우.

스레드를 다른 run queue로 이동시킴.

풀 마이그레이션(pull migration)

각 코어가 커널의 스케줄링 코드를 실행하는 경우, 자신의 run queue에 처리할 스레드가 없으면 다른 run queue에 대기중인 스레드를 끌어다가 실행.