[운영체제] 5. CPU 스케줄링

프로세스의 실행단위인 스레드를 실행할 때 어떤 스레드를 실행할지 스케줄링을 통해 선택된다고 설명해왔었다. 

 

이제 그 스케줄링이 무엇인지 그리고 어떤 스케줄링 알고리즘들이 존재하는지 알아보자. 

 

1. 스케줄링 개요 

한정된 자원에 대한 경쟁이 있을 때 우린 누구에게 자원을 할당해줘야 할지 선택해야 한다. 

즉 CPU 자원을 누구에게 할당할 것인지 결정하는 것이 CPU 스케줄링인 것이다. 

여기서 선택의 대상이 되는 스레드는 '준비' 상태에 있는 스레드들이다. 

 

스케줄링이 필요하게 배경에는 다중 프로그래밍의 등장이 있다. 

CPU가 쉬는시간인 CPU 유휴 시간을 줄이기 위해 만들어진 다중 프로그래밍 기법은 I/O이 발생하면 실행하고 있는 프로세스를 중단하고 다른 프로세스를 실행한다. 

 

그런데 어떤 프로세스를 메모리에 가져올 것인지, 그리고 메모리에 있는 작업중 어떤 작업을 선택해야할 것인지를 결정해야 했다. 

 

이를 해결하기 위해  응용프로그램 작업물을 디스크에 저장하고, 이를 선택해 메모리에 적재하는 '작업 스케줄링'과 작업 스케줄링된(즉 메모리에 있는 프로그램) 중 어떤 프로그램을 CPU가 실행할지에 대한 CPU 스케줄링이 등장한다. 

 

따라서 다중 프로그래밍의 효율성을 높여 CPU의 활용률을 높이고, 컴퓨터 시스템 처리율을 향상 시키기 위해 스케줄링이 등장한 것이다. 

 

그럼 어떤 기준으로 스케줄링을 하게 되는 것일까? 

그 기준은 CPU 활용률, 처리율, 공평성, 응답시간, 대기시간, 소요시간, 자원 활용률 등.. 

다양할 것이며, 스케줄링을 하는 컴퓨터 시스템의 목적에 따라 정해질 것이다. 

 

대부분은 스레드가 CPU를 사용하는 시간을 정하고 사용하도록 하는 Time Slice 기법을 사용한다. 즉 스레드를이 CPU 사용을 보장받는 것이다. 

 

2. 스케줄링 기본 

스케줄링은 언제 시행되는가?

스케줄링이 되는 경우는 기본적으로 4가지가 있다.

1. 스레드가 I/O을 요청하는 시스템 호출을 실행해 Blocked 상태가 될 때. 이때 다른 스레드에 CPU를 할당한다. 

2. 자발적으로 스레드가 CPU사용을 반납할 때 

3. 타임 슬라이스가 끝나 인터럽트 서비스 루틴이 발생할 때

4. 더 높은 우선순위 스레드의 I/O가 완료되었을 때 

 

Dispatcher 코드 

CPU 스케줄링은 커널에 의해 이루어지는데, 

CPU 스케줄링을 담당하는 별도의 커널 스레드나 프로세스가 존재하는 것은 아니다. 시스템 호출이나 서비스 루틴에 의해 호출되는 코드의 형태로 스케줄링이 실행되며, 이 코드를 dispatcher 코드라고 한다. 

 

스케줄링의 타입은 비선점과 선점 두 방식이 존재한다. 

이는 실행중인 스레드를 강제로 중단하는지, 안하는지에 따라 달라지는데 

강제로 중단하지 않은 스케줄링 타입을 비선점 타입, 강제로 중단하는 스케줄링 타입을 선점 타입이라고 한다. 

 

비선점 타입은 스레드가 CPU를 더 이상 사용하지 않을 때 ex) I/O Blocked, sleep() 혹은 자발적으로 자원을 양보하는 yield(), 그리고 스레드가 종료될 때 스케줄링 되는 것을 의미한다. 스레드가 강제로 중단되는 것이 아님을 확인할 수 있다. 

선점 타입은 타입 슬라이싱 기법이나 더높은 순위의 스레드가 대기 상태일 때 스케줄링이 발생하는 것이다. 이와 관련된 스케줄링 기법은 뒤에서 더 다룰 것이다. 

 

기아와 aging

스케줄링의 과정에서 선택되지 못하고 오랫동안 준비 상태로 존재하는 상태를 기아상태라고 한다. 스케줄링 기법에 다라 기아가 존재하기도 하고 존재하지 않기도 하지만 대부분 우선순위 기반 스케줄링에서 기아가 발생하게 된다. 

이를 해결하기 위해 준비 리스트에 머문 시간에 비래해 우선순위를 높여주는 aging 기법이 사용되기도 한다. 

 

3. 스케줄링 알고리즘 

그럼 어떤 스케줄링 기법이 존재하는지 알아보자. 

스케줄링의 성능을 측정하는 방식은 다양하겠지만 여기서는 준비리스트에서 스레드가 대기하는 시간을 성능으로 하겠다. 

준비리스트는 queue를 사용한다.

 

이와 같이 준비큐에 스레드가 존재한다고 생각하자.

스레드	도착시간	실행하는데 소요되는 시간
T1	0	4
T2	1	3
T3	2	1
T4	5	3

 

FCFS(First Come First Serve) 

• FIFO라고도 불리는 선입선출 알고리즘이다. 
• 파라미터는 스레드별로 준비 큐에 도착한 시간이다. 
• 타입은 비선점이며
• 우선순위는 존재하지 않고
• 기아도 존재하지 않는다
• 준비큐에 스레드가 도착하는데로 실행시키는 가장 간단한 스케줄링 알고리즘이다
• 하지만 앞서 도착한 스레드가 무한 루프를 돈다면 이를 해결할 방법이 없다. 
• 처리율은 낮지만 구현하기 쉽다. 
• 성능은 0+3+5+3 / 4 = 2.75ms이다.

STF(Shortest Job First)

• 실행시간이 짧은 스레드를 우선 선택하는 방식이다
• 평균 대기시간을 최소화 하는 방법인데 큐에서 가장 짧은 스레드를 선택하거나 짧은 순으로 준비큐에 스레드를 넣으면 된다. 
• 파라미터는 스레드별 예상 실행시간이다
• 타입은 비선점이며
• 우선순위는 존재하지 않고
• 기아는 존재할 수 있다. (계속해서 더 짧은 실행 시간을 갖은 스레드가 도착할 경우)
• 평균적인 대기시간이 가장 낮다. 하지만 스레드 실행시간을 예측한다는 것이 불가능에 가깝기 때문에 실현하기 어렵다. 
• 성능은 0+4+2+3 / 5 = 2.25ms 이다

SRTF(Shortest Remaining Time First)

• STF의 선점 버전이다. 
• 실행 중에 더 짧은 실행시간 스레드가 준비큐에 들어오면 실행할 스레드를 바꾼다.
• 파라미터는 스레드 별 예상 실행시간
• 타입은 선점
• 우선순위는 없다
• 기아는 존재할 수 있다
• 성능은 1+4+0+3 /4 = 2ms로 좋지만 STF와 마찬가지로 스레드 실행시간을 예측할 수 없다. 

RR(Round Robin)

• 타임 슬라이스 주기로 스레드를 실행하는 기법이다. 
• 큐 끝에 스레드를 삽입하고, 앞에 존재하는 스레드부터 실행시킨다. 그리고 할당된 타임 슬라이스가 끝나면 커널에 의해 강제 종료되고 다시 큐 끝에 삽입된다. 
• 파라미터는 time slice이다.
• 타입은 선점 타입이고
• 우선순위는 존재하지 않으며
• 기아는 발생하지 않는다.
• 공평하게 스레드가 실행괴며, 기아가 발생하지 않고 구현도 쉽지만 스케줄링이 자주 발생해 컨텍스트 스위칭이 자주 발생한다. 
• time slice를 길게하면 FCFS와 비슷하고, 짧게하면 SJF와 비슷해진다. 따라서 time slice를 잘 설정해야 한다. 

Priority

• 스레드마다 우선순위를 부여하고, 큐에서 우선순위가 높은걸 먼저 실행한다. 
• 파라미터는 우선순위 값이다
• 선점, 비선점 방식 모두 가능하다
• 우선순위가 존재하며
• 기아는 발생할 수 있다(우선순위가 높은 스레드가 계속 큐에 들어올 경우)
• 스레드마다 고정 순위를 갖는 실시간 시스템에서 자주 사용된다. 
• Linux, Window, Java 등에서 사용되며 이때 우선순위는 가변적으로 할당된다.

MLQ(Multi Level Queue)

• 스레드들을 n개의 우선순위로 구분하고, 우선순위 LV이 높은 스레드 먼저 우선처리한다
• N개의 LV 큐가 존재하며, 부여된 우선순위에 따라 큐에 삽입된다. 
• 가장 높은 큐의 앞 스레드를 싱행하고, 큐가 비면 그 밑의 우선순위 큐를 실행한다. 
• 파라미터는 스레드 우선순위이고
• 타입은 선점, 비선점 모두 가능하다
• 우선순위는 고정 우선순위를 갖고
• 기아는 발생할 수 있다
• 큐간 스레드 이동이 불가능해 기아 문제가 자주 발생한다

MLFQ(Multi Level Feedback Queue)

• MLQ에서 발전한 스케줄링 기법이다
• CPU brust가 짧은 스레드, I/O가 많은 스레드, 대화식 스레드를 우선 실행하는 기법으로 
• 레벨로 구별된 n개의 큐가 존재하고, 큐마다 별도의 스케줄링 정책을 적용할 수 있다. 보통 RR 기법을 적용한다. 
• 큐마다 time slice를 다르게 설정하고, 낮은 레벨의 큐는 time slice를 더 길게 설정한다. 
• 실행중인 스레드의 CPU burst가 타임 슬라이싱 소진으로 넘어가면 강제 종료하고, 아래 레벨 큐로 이동하고 또 타임 슬라이스가 끝나면 스레드는 동일한 큐에 삽입된다.
• 준비큐로 도착하는 큐는 가장 높은 레벨의 큐로 삽입되고 스레드가 자발적으로 CPU를 양보했을 때는 동일한 큐로 다시 삽입한다. 
• I/O 시에도 해당 동일한 큐에 삽입된다. 
• 스레드가 준비큐에서 대기한 시간이 길어지면 보다 상위 큐로 이동해 기아 문제를 해결했다. 
• 파라미터는 큐의 개수, 각 큐의 알고리즘, 우선순위 격하시점과 격상 시점, 도착 스레드 진입할 큐
• 선점 타입이며 RR을 주로 사용한다.
• 우선순위는 없고 기아도 발생하지 않는다. 
• 성능은 CPU burst가 짧거나 I/O 빈번한 스레드가 스레드, 대화 스레드에 유리하다. 
• 그렇지만 알고리즘이 복잡해 구현하기 어렵고, CPU 오버헤드가 증가한다. 

이렇게 스케줄링 알고리즘에 대해서 알아보았다. 

다양한 스케줄링 알고리즘이 존재하고, 목적에 따라 스케줄링 알고리즘을 적용하는 것이 중요할 것이다. 

 

 

그런데 멀티코어 CPU에서 스케줄링 할 때는 2가지 문제가 발생한다. 

 

먼저 컨텍스트 스위칭이 많아 오버헤드가 증가한다는 거싱다. 

한번도 해당 스레드를 실행하지 않은 코어에서 해당 스레드를 실행히 코드-데이터가 캐시에 적재되는데 시간이 더 많이 소요된다. 

따라서 스레드를 동일한 CPU에서 실행하도록 하는 CPU 친화성이 요구된다.

그리고 코어별 부하가 불균형할 수 있다는 점이다. 

이를 해결하기 위해선 부하 균등화 기법이 사용된다. 부하 균등화 기법에는 

push migration -스레드 큐를 감시하는 큐를 설정해 스레드 큐가 짧거나 실행할 스레드가 없는 큐가 있을 때 다른 스레드 큐로부터 스레드를 가져오도록 한다. 

pull migration - 스레드 큐가 비면 다른 스레드를 가져온다.

 

지금까지 CPU 스케줄링이 무엇인지, 왜 필요하게 되었고 언제 시행되는 것인지, 또 어떤 스케줄링 알고리즘이 존재하는지 알아보았다.