CPU 스케줄링 | Operating System

기본 개념

다중 프로그래밍 환경에서 우리는 CPU를 최대한 많이 이용하고 싶다. 운영체제는 CPU 자원을 회수하고 적절히 분배하는 스케줄링을 잘 해야 한다.

CPU-입출력 버스트 사이클

프로세스는 CPU 연산과 입출력 반복한다. CPU 연산을 시작해서 block될 때까지를 CPU 버스트, block되고 I/O 작업을 수행하고 다시 준비 큐로 이동할 때까지를 입출력 버스트라 부르고 둘을 합쳐 한 사이클이라 한다. CPU 버스트는 2~3ms 정도의 짧은 시간이 대부분이다. 또 입출력 중심 프로그램은 CPU 버스트가 짧을 것이고, 연산 중심 프로그램은 CPU 버스트가 길 것이다.

CPU 스케줄러

CPU가 유휴(idle) 상태일 때마다, 운영체제는 준비 큐에 있는 프로세스 중 하나를 선택해 CPU에게 넘겨야 한다. 이때 선택은 단기 스케줄러가 한다.

선점 스케줄링

프로세스가 block 되거나 종료하면 운영체제는 반드시 스케줄링을 해야 한다.
프로세스가 실행/대기 상태에서 준비 상태로 바뀔 때는 스케줄링을 할 지 안할 지 선택할 수 있다.

1번 조건만 만족하는 방식을 비선점 혹은 협조적 스케줄링이라 한다. 1번과 2번 조건을 모두 만족하면 선점 스케줄링이라고 한다.

선점 스케줄링은 CPU를 기민하게 사용할 수 있지만 경쟁 상황을 초래해 오류를 야기할 수 있다. 심각한 경우에는 커널 작업을 할 때 선점하면 커널 자체에 오류가 발생할 수도 있다. 그렇다고 선점을 안할 수는 없다. 인터럽트는 언제나 발생할 수 있고, 항상 무시될 수 없기 때문이다. 따라서 선점은 하되 인터럽트에 영향을 받는 코드는 반드시 한 번에 한 프로세스만 접근하도록 해야 한다.

디스패처

디스패처(dispatcher)는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이다. 자세하게 하면, 문맥을 교환하고 사용자 모드로 전환하고 프로그램의 적절한 위치(PC)로 이동하는 일을 수행한다. 디스패처는 모든 프로세스의 문맥 교환 시 호출되기 때문에 매우 빨라야 한다. 디스패처가 한 프로세스를 정지하고 다른 프로세스를 시작하는데까지 걸린 시간을 디스패치 지연이라 한다.

스케줄링 기준

CPU 이용률 : 실제 시스템에서는 40~90% 정도
처리량(throughput) : 단위 시간당 완료된 프로세스 개수
총처리 시간(turnaround time): 프로세스의 제출부터 완료까지 걸린 시간. 기다린 시간까지 포함한다.
대기 시간 : 준비 큐에서 머무른 시간
응답 시간 : 프로세스의 제출부터 첫 응답까지 걸린 시간

스케줄링 알고리즘

선입 선처리(First-Come, First-Served, FCFS)

FCFS는 말 그대로 먼저 CPU를 요청하는 프로세스에게 먼저 할당하는 방식이다. 준비 큐를 FIFO로 만들 고 하나씩 pop하면 된다. 평균 대기 시간이 매우 길고 비효율적이다. 또한 비선점형이기 때문에 하나의 연산을 다 끝내야 다음 연산을 진행한다.

입출력 중심 프로세스는 CPU를 짧게 자주 써야 한다. 그런데 연산이 긴 프로세스가 CPU를 계속 차지하고 있기 때문에 입출력 중심 프로세스는 하염없이 기다려야 한다. 이걸 반복하다 보면 입출력 중심 프로세스를 끝내는 데는 매우 오래 걸릴 것이다. 이렇게 모든 프로세스가 하나의 긴 프로세스를 기다리는 것을 호위 효과(convoy effect)라고 한다.

최단 작업 우선 스케줄링(Shortest-Job-First, SJF)

SJF는 다음 CPU 버스트 시간이 가장 짧은 프로세스에게 할당하는 방식이다. ~~사실 최단 “다음” 작업 우선 스케줄링이라는 표현이 더 정확하다.~~ 이 방식으로 짧은 프로세스부터 실행하면 전체 프로세스의 평균 대기 시간을 많이 줄일 수 있다. 또 선점형과 비선점형을 선택할 수 있는데, 선점형의 경우 준비 큐에 더 짧은 CPU 버스트를 가진 프로세스가 있으면 바로 선점한다.

SJF의 가장 큰 어려움은 다음 CPU 버스트 시간을 파악하는 것이다. 장기 스케줄링에서는 가능하지만 단기 스케줄링에서 파악하는 것은 불가능하다. 그래서 다음 CPU 버스트 길이는 이전 버스트 길이를 지수 평균한 값으로 예측한다. $ \tau_{n+1} $는 예측한 다음 CPU 버스트 길이이다. $\tau_n$은 예측한 이전 길이고, $t_n$는 실제 이전 버스트 길이이다. $\alpha$는 가중치로 이 값을 통해 이전에 예측한 값과 실제 값을 어떤 비중으로 계산할지 결정한다. 그러니까 다음 버스트 길이는 이전 예측치와 실제값을 적절히 섞은 것이다.

$$ \tau_{n+1} = \alpha t_n + (1+\alpha) \tau_n $$

우선순위 스케줄링

SJF가 버스트 시간만 고려했다면, 우선순위 스케줄링은 내부적 요인(메모리, CPU 등)과 외부적 요인(컴퓨터 사용료, 부서, 정치적 요인)을 복합적으로 고려한다. 순위가 같다면 FCFS 순서로 처리한다. 우선 순위는 일반적으로 0~7 또는 0~4095 범위를 사용한다. 그러나 0이 최상위인지 최하위인지에 대한 합의는 없기 때문에 운영체제별로 다르다.

우선순위 스케줄링의 주요 문제는 우선순위가 낮은 프로세스는 실행이 안될 수도 있다는 점이다. 이를 무한 봉쇄 또는 기아 상태라 한다. 이걸 해결하는 방안은 프로세스가 대기하는 시간에 따라 우선순위를 점진적으로 높이는 것이다. 이 방법을 노화(aging)라 한다.

라운드 로빈 스케줄링(Round-Robin, RR)

RR은 시분할 시스템을 위해 만들어졌고 선점형 FCFS라 봐도 무방하다. 라운드 로빈에서는 시간 할당량 또는 시간 조각이라고 하는 시간 단위를 정한다. 일반적으로 시간 할당량은 10~100ms이다. RR은 시간 할당량만큼 타이머를 설정하고, 그때마다 프로세스를 디스패치한다.

만약 버스트 시간이 시간 할당량보다 작으면 자발적으로 방출할 것이고, 스케줄러는 다음 프로세스를 할당할 것이다. 반대로 버스트 시간이 더 길다면, 타이머가 시간 할당량에 맞춰 인터럽트를 발생시킨다. 그러면 문맥 교환이 일어나고 실행 중이던 프로세스는 준비 큐의 제일 마지막에 들어간다. 그런 다음 준비 큐의 제일 앞 프로세스를 CPU에 할당한다.

RR은 시간 할당량이 얼마인가에 성능이 크게 좌우된다. 극단적으로 시간 할당량이 크면 FCFS와 같게 된다. 반대로 너무 작으면 문맥 교환을 너무 자주해 오버헤드가 지나치게 커진다. 특히 평균 총처리 시간이 시간 할당량에 따라 심한 변화를 보인다. 보통 문맥 교환 시간의 10배 정도로 잡는다.

다단계 큐 스케줄링

포그라운드/백그라운드나 시스템/대화형/일괄처리 프로세스처럼, 프로세스는 유형별로 구분할 수 있다. 다단계 큐(Multilevel Queue) 스케줄링은 준비 큐를 프로세스 유형별로 여러 개의 큐로 나눈다. 그런 다음 큐별로 각기 다른 알고리즘을 적용할 수 있다. 예를 들어 포그라운드 큐는 RR을 사용하고, 백그라운드 큐는 FCFS를 사용할 수 있다.

또한 큐와 큐 사이에서도 스케줄링이 있어야 한다. 보통 큐마다 우선순위를 고정으로 할당하고 우선순위 스케줄링을 사용한다. 혹은 큐별로 CPU 시간의 몇 퍼센트씩 실행할 수 있도록 설정할 수도 있을 거다.

다단계 피드백 큐 스케줄링

다단계 큐에서는 프로세스가 큐와 큐를 넘어다니지 않는다. 왜냐하면 프로세스의 유형은 고정이기 때문이다. 다단계 피드백 큐(Multilevel Feedback Queue)는 준비 큐를 우선순위를 기준으로 큐를 나누며 프로세스는 큐와 큐 사이를 이동할 수 있다.

그림은 다단계 피드백 큐의 예시이다. 참고로 큐의 숫자가 낮을 수록 우선순위가 높다고 가정한다.

처음 프로세스가 준비 큐에 들어오면 큐 0에 들어간다. 8ms 시간 할당량만큼 실행되고 만약 끝나지 않는다면 큐 1으로 들어간다. 조금 대기하다가 이번에는 16ms 동안 실행된다. 그래도 끝나지 않으면 큐 2로 들어간다. 큐 0에 프로세스가 있으면 무조건 해당 프로세스부터 할당한다. 큐 0가 비어있다면 큐 1을, 큐1이 비어있다면 큐 2에 있는 프로세스를 할당한다.

스레드 스케줄링

경쟁 범위 (Contention Scope)

스케줄러 액티베이션 참조하면, 스레드 라이브러리는 사용자 수준 스레드를 사용 가능한 LWP에 스케줄링한다. 그리고 운영체제는 커널 수준 스레드를 CPU에 스케줄링한다.

프로세스-경쟁 범위(PCS) : 같은 프로세스에 속한 스레드 사이에서 CPU를 경쟁하는 것을 말한다.
시스템-경쟁 범위(SCS) : 시스템 상의 모든 스레드 사이에서 CPU를 경쟁하는 것을 말한다.

Windows, Liunx 같이 일대일 모델을 사용하는 시스템은 LWP가 없기 때문에 SCS만 사용한다. 반면, 다대일과 다대다 모델을 구현하는 시스템은 PCS로 LWP에 사용자 스레드를, SCS로 CPU에 커널 스레드를 할당한다.

멀티 프로세서 스케줄링

여러 개의 CPU를 사용하면 부하 공유가 가능해지지만 문제는 더욱 복잡해진다.

접근 방법

비대칭 다중 처리(asymmetric multiprocessing)

주 서버라는 하나의 프로세서에서 모든 스케줄링 결정과 입출력 처리, 그리고 다른 시스템의 활동을 취급하게 하는 것이다. 나머지 프로세서는 사용자 코드만을 수행한다. 주 서버만 시스템 자료구조에 접근하기 때문에 자료 공유의 필요성을 배제한다.

대칭 다중 처리(symmetric multiprocessing, SMP)

각 프로세서의 스케줄러가 준비 큐를 검사해서 프로세스를 선택한다. 이때 다른 프로세서가 같은 프로세스를 선택할 수 없어야 하고, 프로세스가 큐에서 사라지지 않는다는 것을 보장해야 한다. 대부분 운영체제가 SMP를 지원한다.

처리기 친화성

프로세서는 각자 작업을 한 프로세스를 캐시 메모리에 채운다. 다음 작업도 같은 프로세서에서 굳이 할 필요는 없지만, 다른 프로세서에게 넘기려면 불필요하게 캐시 메모리를 지우고 다시 싣어야 하는 단점이 있다. 그래서 SMP 시스템은 기왕이면 프로세서는 캐시 메모리에 있는 프로세스를 처리하려 하는데, 이를 처리기 친화성(processor affinity)이라 한다.

연성(soft) 친화성 : 프로세서가 캐시 메모리에 있는 프로세스를 실행하려고 노력하지만 보장하지는 않는다.
강성(hard) 친화성 : 프로세스는 시스템 호출을 통해 자신이 실행될 프로세서 집합를 정할 수 있다.

멀티 프로세서 에서 배운 것처럼 NUMA에서 CPU는 가까운 메인 메모리에 빠르게 접근할 수 있다. 그렇기 때문에 운영체제의 알고리즘을 적절히 사용한다면, 할당하고 싶은 CPU에 제일 가까운 위치에 프로세스를 싣을 수도 있다.

부화 균등화(Load Balancing)

SMP 시스템에서 모든 프로세서는 최대한으로 일해야 한다. 모든 프로세서가 하나의 실행 큐를 공유한다면, 그냥 바로바로 큐에서 새 프로세스를 가져가면 되기 때문에 부화 균등화가 필요없다. 따라서 부화 균등화는 통상 각 프로세서가 각자의 실행 큐를 가진 시스템에서만 필요하다.

부화 균등화 방법은 푸시 이주와 풀 이주가 있다. Linux와 Unix의 ULE 스케줄러는 두 방식 모두 지원한다.

푸시(push) 이주 : 특정 태스크가 프로세서별 부하를 검사하고 프로세스를 분배한다.
풀(pull) 이주 : 쉬고 있는 프로세서가 바쁜 프로세서의 프로세스를 가져온다.

부화 균등화는 처리기 친화성에 상충한다. 처리기 친화성이 프로세스를 머무르게 하는 반면, 부화 균등화는 프로세스를 이주시키기 때문이다. 따라서 사용하기 나름인데, 몇몇 시스템에서는 불균형 상태가 임계치를 넘을 때만 프로세스를 이주시키는 정책을 사용한다.

멀티코어 프로세스

프로세서는 메모리에서 데이터를 가져오려고 기다릴 때 많은 시간을 쓴다. 이 현상은 캐시 미스 등의 원인에 의해 발생하고 메모리 멈춤(Memory stall)이라 불린다. 이를 해결하기 위해 한 코어에 여러 개의 스레드를 할당하는 다중스레드 프로세서 코어가 등장했다. 코어에 여러 스레드를 할당하면 한 스레드가 메모리를 기다리는 동안 다른 스레드가 코어에서 연산하면 되기 때문에 코어를 최대한으로 활용할 수 있게 된다.

코어 안에서 할당 가능한 스레드 공간을 하드웨어 스레드라고 한다. 운영체제는 하드웨어 스레드를 소프트웨어 스레드를 실행할 수 있는 논리 프로세서로 본다. 따라서 2코어 2스레드 시스템에서 운영체제는 4개의 논리 프로세서를 가진다.

거친(Coarse-grained) 다중스레딩 : 스레드가 메모리 멈춤 현상으로 긴 시간 동안 멈출 때 스레드를 바꾼다. 명령어 파이프라인을 완전히 정리해야 하기 때문에 비용이 많이 든다.
세밀한(Fine-grained) 다중스레딩 : 명령어 사이클 경계에서 스레드를 교환한다. 회로적인 지원이 필요하지만 교환 비용이 감소한다.

다중스레드 다중코어 프로세서는 사실상 두 단계의 스케줄링이 필요하다.

운영체제는 소프트웨어 스레드를 어느 논리 프로세서에 할당할지 결정한다. 지금까지 배운 프로세스 스케줄링 방법을 사용한다.
코어는 어떤 하드웨어 스레드를 실행할지 결정한다. UltraSmRC T3 프로세서는 RR을 사용하는 등 정말 다양하고 복잡한 알고리즘을 사용한다.

실시간 CPU 스케줄링

실시간 임베디드 시스템 에서 실시간 임베디드 시스템이 사용하는 스케줄링이다. 여기서는 스케줄되는걸 서비스를 받는다고 표현하는 것 같다.

경성 실시간 시스템 : 태스크는 반드시 마감시간까지 서비스를 받아야 한다. 늦게 받은 건 안받은 거다.
연성 실시간 시스템 : 마감시간이 없다. 다만 프로세스 간의 우선순위는 보장한다.

지연 시간 최소화

운영체제 연산 에서 현대 운영체제는 인터럽트 구동식이라고 했었다. 이 방식은 인터럽트(사건) → 디스패치 → 응답의 과정을 거친다. 지연 시간은 사건 발생부터 응답까지 걸린 시간이다.

인터럽트(사건)이 발생한 후 인터럽트를 처리하는 과정이다.

인터럽트 유형 결정 : 운영체제는 일단 실행 중인 명령어를 끝내고, 인터럽트의 종류를 결정한다.
문맥교환 : 현재 실행 중인 프로세스의 상태를 저장하고, 인터럽트 서비스 루틴(ISR)을 불러온다.
ISR 수행 : 해당 인터럽트를 처리한다.

실시간 시스템에서 인터럽트 지연을 줄이는 것이 큰 과제이다. 특히 커널 자료구조를 갱신하는 동안에는 인터럽트가 미뤄지는데, 이 시간을 최대한 짧게 해야 한다.

디스패치 지연은 하나의 프로세스를 block하고 다른 프로세스를 시작하는 데까지 걸리는 시간이다. 디스패치 지연의 충돌 단계는 커널 프로세스의 선점과 우선 순위가 낮은 프로세스 자원을 방출하는 단계이다. CPU에 즉시 접근해야하는 실시간 작업이 있다면 이 지연 시간을 최소화 해야한다. 선점형 커널이 가장 효과적인 방법이다.

우선순위 기반 스케줄링

실시간 운영체제는 프로세스가 CPU를 필요로 할 때 바로 응답해줘야 한다. 따라서 선점을 이용한 우선순위 기반 스케줄러가 유리하다. 우선순위 스케줄링를 설명했었지만 이 방법은 연성 실시간 시스템에 불과하다. 경성 실시간 시스템에서는 마감시간 내에 확실히 수행됨을 보장해야 하기 때문에 추가적인 기법이 필요하다.

프로세스는 주기적이다. 다시 말해 프로세스는 매 주기(p)마다 CPU를 필요로 하고 마감시간(d) 내에 실행되어야 하며 실행 시간(t) 만큼 실행된다. 스케줄러는 프로세스의 마감시간을 확인하고 마감시간 내에 실행이 가능할 때만 실행을 허락한다. 이때 승인 제어 알고리즘을 사용한다.

Rate-Monotonic (RM) 스케줄링

Rate-Monotonic 스케줄링은 선점형 우선순위 알고리즘을 이용해 주기 태스크를 스케줄한다. 각 주기 태스크는 시스템에 진입할 때 주기에 따라 우선순위가 정해지는데, 주기가 짧을 수록 우선순위가 높다. 또한 여기서는 주기 프로세스의 실행시간은 CPU 버스트와 같다고 가정한다.

예를 들어, 두 프로세스 $P_1(t = 20, d=50) = 50$과 $P_2(t = 35, d=100)=100$가 있다고 가정하자. 50과 100은 각 프로세스의 주기이다. 먼저 $P_1$의 CPU 이용률($t/P$)은 0.4 이고 $P_2$는 0.35이다. 따라서 총 CPU 이용률은 0.75이므로 넉넉하게 실행될 수 있다. 그 다음, 스케줄링하면 아래 그림처럼된다.

이 스케줄링 기법은 최적이지만 많은 제약이 있다. CPU 이용률에 한계가 있는데, 프로세스의 수가 증가하면 69%까지 떨어질 수가 있다. 프로세스가 두 개일 경우 최대 CPU 이용률은 약 83%이기 때문에 75%인 위 예시가 통과할 수 있었던 것이다.

Earliest-Deadline-First (EDF) 스케줄링

EDF 스케줄링에서는 마감시간이 빠를수록 우선순위가 높다. 프로세스는 실행 가능해질 때마다 마감시간을 시스템에 알려야 하고 우선순위는 계속 변경된다. 이 점이 우선순위가 고정된 RM 스케줄링과 다르다. 또한 EDF는 프로세스들이 주기적일 필요도 없고 CPU 할당 시간도 고정될 필요가 없다. 이론상 EDF의 CPU 이용률은 100%이다. 물론 인터럽트 핸들링과 문맥 교환 오버헤드가 있어서 100%는 불가능하다.

한 프로세스가 차지하는 비율을 퍼센트가 아닌 숫자로 나타내는 방식이다. 예를 들어 전체값 T=100이고, 프로세스 A가 50몫, 프로세스 B가 30몫을 차지한다면 각각 50%, 30%의 CPU를 할당받았다고 말할 수 있다. 또한 프로세스들이 가지는 몫이 T를 넘을 수 없도록 승인 제어를 해야 한다. 만약 프로세스 C가 30몫을 요구한다면 프로세스 몫의 합이 T보다 크게 될 것이므로 거부된다.

POSIX 실시간 스케줄링

POSIX에서는 먼저 우선 순위별로 FIFO 큐에 넣는다. 가장 앞에 있는, 가장 우선순위가 높은 프로세스에게 CPU를 할당하고 종료 또는 block될 때까지 기다린다. 만약 우선 순위가 같다면 RR가 흡사하게 시간 할당량을 통해 제어한다.

운영체제 사례들

Linux는 태스크 스케줄링을 설명하고, Windows는 커널 스레드 스케줄링에 대해 설명한다.

Linux: Completely Fair Scheduler (CFS)

다단계 큐 스케줄링과 비슷하게, CFS는 유형별로 클래스를 나누는 스케줄링 클래스에 기반을 둔다. 클래스는 각자 우선순위와 스케줄링 알고리즘이 부여된다. 표준 Linux 커널은 CFS 스케줄링을 사용하는 디폴트 스케줄링 클래스와 실시간 스케줄링 클래스로 구분한다. 이 외에 새로운 클래스를 추가할 수 있다.

CFS 스케줄러, 디폴트 스케줄링

CFS는 고정된 시간 할당량을 사용하지 않고 각 태스크에게 CPU 처리시간 비율을 할당한다. 이 비율은 각 태스크가 가지고 있는 nice 값을 통해 계산한다. nice는 -20~19 범위를 가지며, 값이 낮을 수록 우선순위는 높다. 디폴트는 0이다. nice 값을 올리면 상대적으로 다른 태스크의 우선순위가 높아지기 때문에 다른 태스크들에게 나이스하게 대한다 해서 nice다. nice를 통해 구한 CPU 처리시간 비율을 목적 지연시간이라 한다. 목적 지연시간은 최소값과 디폴트 값을 가지며, 모든 수행 가능한 태스크를 한 번씩을 실행할 수 있는 시간 간격을 나타낸다. 시스템에 활성 태스크가 임계값보다 많아지면 목적 지연시간은 증가할 수 있다.

CFS는 태스크의 vruntime이라는 변수에 태스크가 실행된 시간을 기록한다. vruntime은 가상 실행시간으로 우선순위에 따라 값이 바뀐다. 바뀌는 정도는 우선순위에 기반한 감쇠 지수(decay factor)가 결정하는데, 우선순위가 높을 수록 실제 실행시간에 비해 vruntime은 작아진다. nice가 0이면 vruntime은 감소하지 않는다. 다음 태스크는 vruntime이 가장 작은 태스크를 선택해 CPU를 선점한다. 따라서 우선순위가 큰 값들은 실행시간에 비해 vruntime이 작기 때문에 다음 번에 실행될 가능성이 더 커진다.

이 방식이 유리한 이유는 입출력 방식의 경우 짧게 자주 실행되어야 하는데, 짧게 실행되기 때문에 vruntime이 매우 짧다. 따라서 실행가능해지자마자 바로 CPU 선점해서 실행할 수 있게 된다.

실시간 스케줄링

POSIX 실시간 스케줄링 를 사용한다. 실제 Linux의 우선순위는 0~139까지 있다. 이 중 0~99까지는 정적 우선위로 실시간 태스크에게 할당한다. 100~139는 nice의 -20~19와 똑같은데, 100은 -20 nice이고, 139는 19 nice이다. 여기서도 우선순위 값이 낮을 수록 우선순위는 높다. 따라서 실시간 태스크의 우선위가 일반 태스크보다 높다.

Windows: 우선순위 기반 선점형 스케줄링

WIndows 커널에서 스케줄링은 디스패처가 담당한다. 디스패처는 스레드의 우선순위를 32 단계와 2 클래스로 나눈다. 가변 클래스는 1~15까지, 실시간 클래스는 16~31이다. 우선순위가 0인 스레드는 메모리 관리용을 뜻한다. 디스패치는 준비 상태에 있는 높은 우선순위를 찾아 실행시키는데, 아무것도 없으면 idle 스레드를 실행시킨다.

스레드의 시간 할당량이 끝나면 인터럽트된다. 그런 다음, 가변 스레드는 우선순위가 낮아진다. 가변 스레드가 block에서 풀려나면 우선순위를 높여주는데, 키보드/마우스 입출력을 기다렸던 스레드라면 많이 높여준다. 이렇게 하면 유저에게 빠르게 응답할 수 있다. 또한 백그라운드보다 포어그라운드 프로세스가 3배 많은 시간 할당량을 가진다.

Windows 7부터 사용자 모드 스케줄링(UMS)가 도입되었다. 어플리케이션은 커널의 도움없이 독립적으로 스레드를 생성, 관리할 수 있다. 이 개념은 어플리케이션 자체보다는 라이브러리가 직접 스케줄링을 할 수 있게 도와준다.

알고리즘 평가

결정론적 모델링

프로세스들은 날마다 변하기 때문에 비교하기 어렵다. 하지만 CPU와 입출력 버스트의 분포는 측정할 수 있고 수학적으로 추정이 가능하다. 이 분포도로부터 알고리즘의 평균 처리량, 이용률, 대기시간 등을 구한다. 또한 한 대의 컴퓨터는 CPU에 있는 준비큐, 입출력 장치에 있는 장치 큐 등으로 나눌 수 있고, 평균 큐의 길이와 큐별로 도착하는 프로세스를 계산할 수 있다. 이러한 분석을 큐잉 네트워크 분석이라 한다.

샘플 데이터셋을 가지고 직접 알고리즘에 대입하는 방식이다. 단순하고 빠르며 정확하다. 하지만 정확한 데이터셋이 필요하고 주어진 값만으로 비교하는 것이기 때문에 수학적인 비교가 불가능하다.

큐잉 모델

n은 평균 큐의 길이, W를 큐에서의 평균 대기 시간, $\lambda$를 평균 도착률(단위 시간당 큐에 도착하는 프로세스의 수)이라고 하자. 시스템이 안정적이라면 큐에 들어오는 프로세스와 나가는 프로세스의 수가 같아야 하므로 아래 식이 성립한다. 이 식을 Little’s formula라고 한다.

$$ n= \lambda W $$

세 변수 중 두 개만 안다면 나머지 하나도 구할 수 있다. 큐잉 분석은 유용하나 분포를 계산하기가 어렵고 너무 특정 상황에 제한되어 있다. 그리고 이 분석은 근사치라서 오차가 있을 수 있다.

모의 실험

시스템을 모델링해서 실제 돌아가는 것처럼 꾸민 후 분석하는 방법이다. 데이터셋은 확률 분포에 따라 난수를 통해 만든다. 확률 분포는 수학적으로(균등, 지수, 포아송) 또는 경험적으로 정의할 수 있다. 다만, 경험적으로 정의하는 분포는 실제 측정을 한 결과를 기반으로 하기 때문에 부정확할 수 있다. 실제 시스템에서는 너무 많은 변수가 존재해 결과를 흐린다는 것이다.

이를 해결하기 위해 추적 테이프를 사용한다. 추적테이프는 실제 사건들의 순서를 기록하기 때문에, 동일한 입력을 여러 스케줄러로 전달할 수 있다. 이 방법의 가장 큰 단점은 시간과 비용이 많이 소모된다는 것이다. 그리고 아직도 완벽하지는 않다.

구현

완벽하게 평가하는 방법은 실제 코드를 작성하고 운영체제 안에 넣어보는 것이다. 물론 이 방법은 비용이 매우 크다. 코드를 작성하는 것에 더해 계속 업데이트되는 운영체제에 맞처 코드를 업데이트해줘야 한다.

Sunghun Son / Operating System / CPU 스케줄링