05. CPU스케줄링

1 CPU 스케줄링 개요

준비 상태의 스레드 중 하나를 선택하는 스레드 스케줄링이다.

1.1 다중프로그래밍과 스케줄링

다중프로그램이 도입된 이후 운영체제는 다음 2가지 스케줄링을 시행하였다.

• 작업 스케줄링(job scheduling)
• CPU 스케줄링(CPU scheduling)

1.2 CPU burst와 I/O burst

프로그램의 실행 과정에서 CPU가 코드를 집중적으로 실행하는 상황을 CPU burst라고 부르고 이 시간을 CPU burst 시간이라고 한다. 그리고 I/O 장치에 의해 입출력이 이루어지는 상황을 I/O burst라고 부르고 이 시간을 I/O burst 시간이라고 한다.

1.3 CPU 스케줄링의 기본 목표

• CPU 활용률 향상
• 컴퓨터 시스템 처리율 향상

1.4 CPU 스케줄링의 기준(criteria)

• CPU 활용률(CPU utilization)
• 처리율(throughput)
• 공평성(fairness)
• 응답 시간(response time)
• 대기 시간(waiting time)
• 소요 시간(turnaround time)
• 시스템 정책 우선(high policy enforcement)
• 자원 활용률(high resource efficiency)

1.5 CPU 스케줄링과 타임 슬라이스

운영체제는 스레드가 CPU를 사용할 타임 슬라이스(time slice)를 정하고 이 시간 동안 CPU를 사용하게 한다. 타임 슬라이스는 스레드가 CPU 사용을 보장받는 시간이며 커널이 CPU 스케줄링을 하는 주기 시간이다.

리눅스는 CFS가 time slice를 조정(유동적)

2 CPU 스케줄링 기본

2.1 CPU 스케줄링과 디스패치(dispatch)

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

CPU 스케줄링을 담당하는 별도의 커널 스레드나 프로세스가 없다. CPU 스케줄링 코드는 시스템 호출이나 인터럽트 서비스 루틴이 서비스를 마치는 마지막 과정에서 스케줄링이 필요할 때 호출된다.

디스패처(dispatcher) 코드 실행

디스패처 코드는 스케줄러 코드에 의해 선택된 스레드를 CPU가 실행하도록 하는 커널 코드의 한 부분이다.

컨텍스트 스위칭?

2.3 스케줄링 타입: 선점 스케줄링과 비선점 스케줄링

비선점 스케줄링

스레드가 실행을 시작하면 완료되거나 CPU를 더 이상 사용할 수 없는 상황이 될 때까지 스레드를 강제로 중단시키지 않고, 실행중인 스레드가 더 이상 CPU를 사용할 수 없는 다음의 상황에서야 비로소 스케줄링을 시행한다.

• CPU를 더 이상 사용할 수 없게 된 경우: I/O로 인한 블록 상태, sleep()
• 자발적 CPU 양보: yield() 시스템 호출
• 스레드 종료 현재는 거의 사용 X SRTF, Priority 스케줄링(non-preemptive 버전) 등이 있음

선점 스케줄링

현재 실행 중인 스레드를 강제로 중단시켜 준비 리스트로 이동시키고 스케줄링하는 방식이다. 선점 스케줄링을 채택하는 스케줄링 알고리즘은 대체로 다음의 상황에서 강제로 스케줄링한다.

• 타임 슬라이스가 소진되었을 때
• 인터럽트나 시스템 호출 종료 시점에서 더 높은 순위의 스레드가 대기 상태에 있을 때 대부분의 운영체제에서 사용 RR, SJF, Priority(preemptive 버전) 등이 있음

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

2.4 기아와 에이징

스레드가 스케줄링 과정에서 선택되지 옷한 채 오랜 동안 준비 리스트에 있는 상황을 기아(starvation) 라고 한다. 우선순위를 기반으로 하는 시스템이나 실행 시간이 짧은 스레드를 우선 실행시키는 알고리즘이 사용되는 경우 스레드가 기아에 빠지게 된다. 이를 해결하기 위해 많이 활용되는 것이 에이징(aging) 기법으로, 스레드가 준비 리스트에 머무르는 시간에 비례하여 우선순위를 높여주는 기법이다.

3 다양한 CPU 스케줄링 알고리즘

3.1 FCFS(First Come First Served)

• 알고리즘 큐에 먼저 도착한 스레드를 먼저 스케줄링한다.
• 스케줄링 파라미터 - 스레드 별 큐 도착 시간
• 스케줄링 타입 - 비선점 스케줄링
• 스레드 우선순위 - 없음
• 기아 - 발생하지 않음 정상적인 경우 발생 X, 앞서 도착한 스레드가 무한 루프를 실행하는 오류가 있는 경우 이를 멈출 수 있는 방법이 없어 뒤 스레드들이 기아에 빠질 수 있다.
• 성능 이슈 호위효과(Convoy Effect)가 나타날 수 있지만 처리율이 낮지만 단순하고 구현이 용이
• 스케줄링 사례

3.2 SJF(Shortest Job First)

• 알고리즘 준비 큐에서 예상 실행 시간이 가장 짧은 스레드를 우선 선택한다.
• 스케줄링 파라미터 - 스레드 별 예상 실행 시간 스레드별 실행 시간 정보를 필요로 하는데 이 시간을 정확이 예측하는 것은 현실적으로 불가능
• 스케줄링 타입 - 비선점 스케줄링
• 스레드 우선순위 - 없음
• 기아 - 발생 가능 짧은 실행 시간을 가진 스레드가 계속 큐에 도착하면 긴 스레드에 기아가 발생할 수 있다.
• 성능 이슈 짧은 스레드를 먼저 실행하면 대기 중인 모든 스레드의 개기 시간이 짧아지므로 평균 대기 시간은 최소화된다. 하지만 스레드의 실행 시간을 예측할 수 없기 때문에 현실에서 사용 불가능
• 스케줄링 사례 $평균대기시간:(0+4+2+3)/4=2.25ms$

3.3 SRTF(Shortest Remaining Time First)

• 알고리즘 SJF의 선점 스케줄링 버전으로 남은 실행 시간이 가장 짧은 스레드를 우선 스케줄한다. 현재 실행 중인 스레드의 시간보다 더 짧은 실행 시간을 가진 스레드가 큐에 도착하면 현재 스레드의 실행을 중단시키고 도착한 스레드를 실행시킨다.
• 스케줄링 파라미터 - 스레드 별 예상 실행 시간
• 스케줄링 타입 - 선점 스케줄링
• 스레드 우선순위 - 없음
• 기아 - 발생 가능 짧은 실행 시간을 가진 스레드가 지속적으로 큐에 도착하면, 긴 스레드는 언제 실행될 지 예측할 수 없어 기아가 발생할 수 있다.
• 성능 이슈 SJF와 동일
• 스케줄링 사례 $평균대기시간:(1+4+0+3)/4=2ms$

3.4 RR(Round-Robin)

• 알고리즘 스레드들에게 공평한 실행 기회를 주기 위해 큐에 대기중인 스레드들을 타임 슬라이스 주기로 돌아가면서 선택한다.
• 스케줄링 파라미터 - 타임 슬라이스
• 스케줄링 타입 - 선번 스케줄링
• 스레드 우선순위 - 없음
• 기아 - 없음
• 성능 이슈 공평하고 기아가 없고 구현이 쉬운 장점, 잦은 스케줄링으로 인해 스케줄링과 컨텍스트 스위칭에 소요되는 시간이 큰 단점이 있다. 타임 슬라이스가 작을수록 스케줄링 횟수도 증가하므로 성능 저하도 심해진다.
• 스케줄링 사례
  • 타임 슬라이스가 2ms인 경우
    • 평균 대기 시간: $(3+4+2+3)/4=3ms$
    • 스케줄링 횟수: 6번
    • 컨텍스트 스위칭 횟수: 5번(스케줄링 번호 10에서는 컨텍스트 스위칭 일어나지 않음)
  • 타임 슬라이스가 1ms인 경우 - 평균 대기 시간: $(5+4+1+3)/4=13/4=3.25ms$ - 스케줄링 횟수: 10번 - 컨텍스트 스위칭 횟수: 9번(스케줄링 번호 10에서는 컨텍스트 스위칭 일어나지 않음)

3.5 Priority

• 알고리즘 스레드마다 고정 우선순위가 정해져 있는 상황에서, 큐에서 가장 높은 우선순위의 스레드를 선택한다.
• 스케줄링 파라미터 - 스레드들의 우선순위 값
• 스케줄링 타입 - 선점/비선점 모두 가능 더 높은 순위의 스레드가 도착할 때 현재 스레드를 중단하고 도착한 스레드를 실행시키면 선점 스케줄링(Preemptive Fixed Priority) 이 되고, 현재 실행 중인 스레드가 종료한 후 스케줄링을 하게 되면 비선점 스케줄링(Non Preemptive Fixed Priority) 이 된다.
• 스레드 우선순위 - 스레드마다 고정 우선순위
• 기아 - 발생 가능 지속적으로 높은 순위의 스레드가 큐에 도착하는 경우, 스레드에 기아 발생 가능 에이징 기법을 결합하면 해결 할 수 있다.
• 성능 이슈 우선순위가 높은 스레드일수록 대기 시간이나 응답 시간이 짧다. 스레드마다 고정 우선순위를 가지는 실시간 시스템에서 주로 사용 Linux, Windows, Java Platform 등 대부분의 운영체제들은 우선순위를 반영하여 스케줄링한다. 이 경우 우선순위는 고정되지 않고 가변적이다.

3.6 MLQ(Multi-level Queue)

• 설계 의도 스레드들을 n개의 우선순위 레벨로 구분하고 레벨이 높은 스레드를 우선 처리할 목적으로 설계되었다.
• 알고리즘 n개의 레벨 큐(우선순위 큐)를 두고, 스레드를 레벨(우선순위)에 따라 큐에 삽입, 스레드는 도착한 순서대로 큐에 삽입되며 다른 큐로 이동할 수 없다. MLQ 스케줄러는 가장 높은 레벨의 큐에서 맨 앞에 있는 스레드를 선택하며, 높은 레벨의 큐가 비어 있을 때 그 아래 레벨의 큐에서 스레드를 선택한다. 큐마다 별도의 큐 스케줄러를 둘 수 있다.
• 스케줄링 파라미터 - 스레드 우선순위
• 스케줄링 타입 - 선점/비선점 모두 가능
• 스레드 우선순위 - 고정 우선순위(n 레벨 중 하나)
• 기아 - 발생 가능
• 활용 사례 및 성능 이슈 스레드 별로 고정 우선순위를 두고 높은 순위의 스레드를 먼저 실행시키는 시스템에서 사용된다. 높은 순위를 가진 스레드들의 대기 시간이나 응답 시간이 짧은 장점이 있다. 하지만, 낮은 레벨의 큐에 있는 스레드가 높은 레벨의 큐로 이동할 수 없어 지속적으로 높은 레벨의 스레드가 도착하면 기아가 발생한다.

3.7 MLFQ(Multi-level Feedback Queue)

• 설계 의도 CPU burst가 짧은 스레드나 I/O 작업이 많은 스레드, 혹은 대화식 스레드를 우선 실행시켜 스레드의 평균대기시간을 줄여 사용자의 응답시간을 짧게 하소 스레드에 기아가 발생하지 않게 한다. 구현에 따라 다를 수 있기 때문에 이 책에서는 알고리즘의 핵심만 소개한다.
• n개의 레벨 큐 우선순위(레벨)로 구분된 n개의 큐를 둔다. 스레드는 우선순위가 없고 도착할 때 가장 높은 레벨의 큐에 삽입된다. 높은 레벨의 큐를 먼저 스케줄링하며, 높은 레벨의 큐가 비어 있을 때만 아래 레벨의 큐에서 스케줄링한다. 큐마다 별도의 스케줄링 정책을 사용할 수 있지만 RR이 가장 무난하다. 각 큐는 CPU burst와 관계있다. 큐마다 타임 슬라이스가 다르게 설정되는데, 낮은 레벨의 큐일수록 타임 슬라이스가 크게 설정된다. 실행 중인 스레드의 CPU burst가 큐의 타임 슬라이스를 넘어가면 강제 중단되어 아래 레벨 큐로 이동된다. 타임 슬라이스 전에 스레드의 CPU burst가 끝나면 스레드는 동링한 큐에 다시 삽입된다.
• 알고리즘
  • 도착하는 스레드는 가장 높은 레벨 큐에 삽입된다.
  • MLFQ 스케줄러는 가장 높은 레벨 큐에서 스레드를 선택하여 실행시킨다. 큐가 비었으면 아래 레벨 큐에서 선택하는 식으로 처리한다.
  • 실행 중인 스레드의 CPU burst가 큐 타임 슬라이스보다 길어지면, 강제로 중단시켜 아래 레벨의 큐로 이동시킨다.
  • 스레드가 실행 중 자발적으로 중단하면 동일 큐에 다시 삽입된다.
  • 스레드가 I/O를 요청하면 해당 큐에서 나오지만, I/O 작업이 끝나면 동일한 큐로 다시 삽입된다.
  • 큐에서 대기하는 시간이 오래되면 기아를 막기 위해 한 레벨 위의 큐로 이동시킨다.
  • 최하위 레벨의 큐는 주로 FCFS나 긴 타임 슬라이스의 RR로 스케줄된다.
• 스케줄링 사례 $$\begin{array}{rl}& T1의대기시간=3+2=5ms\\ & T2의대기시간=1+6+6=13ms\\ & T3의대기시간=3+4+6=13ms\\ & 평균대기시간=(5ms+13ms+13ms)/3=31ms/3=10.3ms\end{array}$$
• 스케줄링 파라미터 큐의 개수, 각 큐의 스케줄링 알고리즘, 우선순위 격하 시점(각 큐의 타임 슬라이스들), 우선순위 격상 시점(기아를 막기 위해 한 레벨 높은 큐로 이동시키기 위한 큐 대기 시간의 최대치), 도착하는 스레드가 진입할 큐 등 여러 사항에 대한 결정이 요구된다.
• 스케줄링 타입 - 선점 스케줄링
• 스레드 우선순위 - 없음
• 기아 - 없음
• 성능 이슈 응답 시간을 빨리하고 평균 대기 시간을 줄인다. 또한 기아를 막을 수 있고, 큐의 개수나 타입 슬라이스 값 등 스케줄링 파라미터를 조절하여 대상 시스템에 적합하게 구현할 수 있는 유연성이 뛰어나지만, 알고리즘이 복잡하여 CPU의 오버헤드가 증가되는 단점도 있다.

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

4.1 멀티 코어 CPU와 별렬 처리

4.2 멀티 코어 시스템에서 CPU 스케줄링과 작업 분배

싱글 코어 CPU에서 사용한 스케줄링 기법을 멀티 코어 CPU에서 그대로 사용하면 2가지 문제 발생

• 컨텍스트 스위칭 후 오버헤드 증가
• 코어별 부하 불균형

컨텍스트 스위칭 후 오버헤드 - 코어 친화성으로 해결

CPU 친화성: 프로세스나 스레드가 특정 CPU에서만 실행되도록 제한하는 스케줄링 특성으로 CPU 피닝(pinning)이라고도 부르며, 캐시와의 관련성 때문에 캐시 친화성(cache affinity)이라고도 한다. CPU 친화성은 멀티 코어 시스템에서는 코어 친화성(core affinity) 으로 통한다. 멀티 코어를 지원하는 운영체제는 코어 친화성을 위해 코어마다 ‘스레드 큐’를 두고, 한 코어에서 실행이 중단된 스레드를 다시 동일한 코어의 큐에 삽입하는 방법을 사용하기도 한다.

코어별 부하 불균형 - 부하 균등화 기법으로 해결

멀티 코어 시스템에서 운영체제가 스레드를 무작위로 스케줄링 한다면 코어 사이의 부하 불균형이 초래될 수 있다. 그러면 코어의 활용률과 함께 시스템 처리율이 떨어진다. 이를 해결하기위해 다음과 같은 부하 균등화 기법(load balancing) 을 사용한다.

• 푸시 마이그레이션(push migration): 시스템에 ‘스레드 큐’를 감시하는 별도의 감시 스레드를 두고, ‘스레드 큐’가 매우 짧거나 실행할 스레드가 없는 코어가 생길 때, 감시 스레드는 다른 스레드 큐로부터 스레드를 강제로 옮겨 놓는 기법
• 풀 마이그레이션(pull migration): 코어는, 스레드가 없게 될 때 다른 코어의 스레드 큐에서 스레드를 가져와 자신의 스레드 큐에 넣고 실행하는 기법이다.

Ref.

황기태, “명품 운영체제”, (주)생튼출판사(2021)