멀티태스킹 - 2
스케줄링
Task의 실행 순서를 정하는 것을 스케줄링이라고 한다. 가장 크게 나누면 두 개로 나눌 수 있다. 바로 선점형과 비선점형 스케줄링이다.
선점형 vs 비선점형
프로세스가 끝나기전에 다른 프로세스가 먼저 실행 할 수 있다면 선점형 현재 실행 중인 프로세스가 종료되기 전에 다른 프로세스가 먼저 실행될 수 없다면 비 선점형이다. 비선점형 스케줄링은 일괄처리 시스템에 적합하고 선점형 스케줄링의 경우 우리가 흔히들 사용하는 상용 OS의 대부분이며 멀티태스킹은 이러한 선점형 방식에서 일어난다. 왜냐하면 Timeslice를 두고 Task를 돌아가면서 실행하는 게 현재 상용 OS의 기본 방식이기 때문이다. 그게 아니라면 키보드나 마우스 이벤트와 같이 짧은 Deadline을 가지고 있는 인터럽트 루틴을 처리할 수가 없다.
아무튼 선점형과 비선점형 모두 스케줄링 방법이 여러가지 종류가 있는데, 그 중에 몇 가지만 알아보도록 하겠다.
비 선점형
- FCFS(First come first service)
Task가 입력된 순서대로 실행하는 방법이다. FIFO(First In First Out)이라고도 한다. 가장 기본적인 방식이다. Task를 들어온 순서대로 처리하며 먼저 들어온 Task가 모두 처리되지 않으면 절대로 그다음 Task로 전환될 수 없다.
- SJF(Shortest Job First)
Task가 실행 될 때 대기 시간이 짧으면 그 스케줄링 방법이 좋다고 볼수 있다. 아무래도 빨리 실행할 경우에 빨리 종료가 될 가능성이 높고, 응답시간도 짧아지기 때문일텐데. 짧은 Task 순으로 처리할 경우에 이러한 대기시간은 가장 짧다. 하지만 특정 Task가 실행 시간이 긴 경우 계속해서 순위가 밀려서 실행이 되지 않는 기아(Starvation) 상태에 빠질 가능성이 있다.
HRN(Highest Response-ratio Next)
실행시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로 대기 시간과 서비스 시간을 이용하는 방식이다. ‘우선순위 = (대기시간+서비스시간)/서비스시간’ 의 공식을 이용하여 우선순위를 계산하여 우선순위가 높은 것부터 실행하는 방식으로 이렇게되면 대기시간이 길어질 수록 우선 순위가 올라가게 되어 결국에는 실행이 된다. SJF보다 좀 더 나은 방식이라고 할 수 있으나 이 경우 Task가 추가될때마다 새로 우선순위를 계산해줘야한다.
선점형
- RR(Round Robin)
프로세스가 들어온 순서대로 단위 시간으로 CPU를 할당하는 방식이다. 이러한 단위 시간을 Time slice라고 하는데 이러한 time slice의 경우 보통 10ms ~ 100ms이고 단위 시간 동안 한번 수행한 프로세스는 준비 큐의 가장 마지막으로 밀려나게 된다. time slice가 짧은 경우 문맥 전환 (context switching)의 오버헤드가 커서 실제 통째로 실행하는 시간보다는 전체 실행시간이 늘어나게 되지만 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하다. time slice가 아주 커질 경우 FCFS와 같이 된다.
-SRT(Shortest Remaining Time First)
비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법이다. SJF 같이 점유시간이 가장 짧은 프로세스에 CPU를 먼저 할당하지만 더 실행시간이 짧은 프로세스가 들어온 경우 해당 프로세스를 두고 더 짧은 프로세스가 cpu를 선점하여 실행되는 식이다. 이 역시 SJF가 그러하듯 프로세스 실행시간이 긴 경우 기아 상태에 빠질 수 있다.
- 우선순위 큐
여러 개의 Task가 입력이 들어왔을 때 Task의 우선 순위를 부여하여 우선 순위가 높은 Task를 먼저 실행하는 것이다. Deadline이 중요한 서비스 같은 경우에는 아주 좋으나 우선 순위가 높은 Task가 계속 해서 추가될 경우 우선 순위가 낮은 Task의 순서가 계속 밀려서 기아 상태에 빠질 수 있다.
- 멀티 레벨 큐
멀티 레벨 큐는 우선 순위 큐와 비슷하지만 여러 개의 큐를 둬서 각 큐의 우선 순위를 매기는 방식이다. 예를 들면 아래의 그림과 같다.
높은 우선 순위 큐에 있는 Task를 한번 다 돌면 그 다음 우선 순위의 Task를 한번 실행시키는것이다. 이러면 한번은 실행이 되는 것인데 이것도 문제는 높은 우선 순위 큐에 Task가 많다면 결국에 그 다음 순위들은 기아현상을 겪게 될수 밖에 없다.
그래서 나온게 aging 기법이 추가된 방식으로 멀티 레벨 피드백 큐라는 것이다
하위 레벨 큐에 있는 Task들도 대기 시간이나 상위 큐에 따라 가중치를 둬서 상위 큐로 이동 할 수 있게 해주는 것으로 이렇게되면 기아현상을 최대한 방지한채로 분배할 수 있다.
번외
선점형에서 이야기하는 Time slice는 과연 고정 값일까? 적어도 Linux에서는 아니라고 한다. CFS(Completely Fair Scheduler)라는 스케줄러가 time slice를 유동적으로 조절하며 TSL(target scheduling latency)이라는 파라미터를 기준으로 조절하게 된다. 가령 TLS이 20ms 이고 Task가 4개면 Time slice가 5ms가 되고 Task가 5개면 Time slice가 4ms가 되는 식이다. 그렇다면 Task가 무한정 늘어나면 Time slice가 0에 수렴하게 되는가? 그건 아니다 minimum granularity라는 값이 있어서 이 값 이하로 내려가진 않는다. (이 값은 약 1밀리초로 되어있다) 하지만 Task가 많이 있으면 어쨌든 문맥 교환 빈도가 늘어나 오버헤드가 커지게 되고 전체 성능이 떨어지기 때문에 Linux에서는 스레드(Task의 최소 단위)를 너무 많이 만들지 않는 것이 좋다.
참고 문헌
- 64Bit 멀티코어 OS의 구조 - 한승훈 저
- 개발자를 꿈꾸는 프로그래머:티스토리
- 쉬운 코드 기술 블로그
- 어게인 빈산토
업데이트
- 20240222 : 스케줄링 기법 업데이트
- 20240224 : 스케줄링 기법 업데이트