운영체제 요약 - 5. CPU 스케줄링

5.1. 기본 개념(Basic Concepts)

다중 프로그래밍에서는 CPU 이용률을 최대화하기 위해 다수의 프로세스들을 메모리 내에 유지한다. 어떤 프로세스가 입출력 등으로 인해 대기해야 할 경우, 운영체제는 CPU를 다른 프로세스에 할당한다.

5.1.1. CPU-입출력 버스트 사이클(CPU-I/O Burst Cycle)

프로세스 실행은 CPU 실행과 입출력 대기의 사이클로 구성된다. 프로세스는 이 두 상태 사이를 왔다 갔다 한다. 일반적으로 입출력 대기시간으로 인해 CPU 사용 시간이 적은 프로세스들이 많으며, 이러한 분포는 CPU 스케줄링 알고리즘에서 중요하다.

5.1.2. CPU 스케줄러(CPU Scheduler)

CPU가 유휴 상태가 될 때마다, 운영체제는 준비 완료 큐(ready queue)에 있는 프로세스들 중에서 하나를 선택해 실행한다. 단기 스케줄러(또는 CPU 스케줄러)가 메모리 내의 프로세스를 선택하여 CPU에게 할당한다.

5.1.3. 선점 스케줄링(Preemptive Scheduling)

CPU 스케줄링 결정은 프로세스가 네 가지 상황일 때 발생한다.

1. 실행 상태에서 대기 상태로 전환(입출력, 자식 프로세스 기다림)
2. 실행 상태에서 준비 완료 상태로 전환(인터럽트 등)
3. 대기 상태에서 준비 완료 상태로 전환(입출력 종료 등)
4. 종료할 때

1, 4에서만 스케줄링이 발생하는 경우, 비선점(non-preemptive)라고 한다. 이는 프로세스가 1, 4 상황이 아니라면 자원을 반환하지 않는다. 다른 프로세스가 자원에 접근하지 못하므로 실시간 컴퓨팅을 지원하기에는 좋지 않다.

1~4 전부 가능할 경우 선점(preemptive)라고 한다. 예를 들어, 정해진 시간이 지나면 다른 프로세스에게 자원이 넘어갈 수 있다. 다수의 프로세서가 접근하는 공유 데이터의 일관성이 깨질 수 있다.

5.1.4. 디스패처(Dispatcher)

디스패처는 단기 스케줄러가 선택한 프로세스에게 주는 모듈이다. 이는 다음과 같은 작업을 포함하며, 하나의 프로세스를 정지하고 다른 프로세스를 시작하는데 소요되는 시간을 디스패치 지연(dispatch latency)이라고 한다.

• 문맥 교환
• 사용자 모드 전환
• 프로그램 재시작을 위해 프로그램의 적절한 위치로 이동(jump)

5.2. 스케줄링 기준(Scheduling Criteria)

CPU 스케줄링 알고리즘을 비교하기 위한 기준은 아래 외 여러가지가 사용된다.

• CPU 이용률(utilization)
• 처리량(throughput)
  • 단위 시간당 완료된 프로세스의 개수이다.
• 총처리 시간(turnaround time)
  • 프로세스의 제출 시간과 완료 시간의 간격이다.
  • 메모리에 들어가기 전 대기 시간, 준비 완료 큐에서 대기한 시간, CPU에서 실행한 시간, 입출력 시간을 합한 시간이다.
• 대기 시간(waiting time)
  • 실행, 입출력 시간을 제외한 준비 완료 큐에서 대기한 시간이다.
• 응답 시간(response time)
  • 하나의 요구를 제출한 후 첫 번째 응답이 나올때까지의 시간이다.

5.3. 스케줄링 알고리즘(Scheduling Algorithms)

CPU 스케줄링은 준비 완료 큐에 있는 어느 프로세스를 CPU에 할당하는 것인지 결정하는 것이다.

5.3.1. 선입 선처리 스케줄링(First-Come, First-Served Scheduling)

FIFO 큐를 사용하여 CPU를 먼저 요청하는 프로세스에게 CPU를 할당한다. 이는 비선점형 알고리즘이기에, 모든 다른 프로세스들이 하나의 긴 프로세스를 기다리는 호위 효과(convoy effect)가 나타날 수 있다.

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

CPU 버스트(실행) 시간이 작은 프로세스를 먼저 할당한다. 장기 스케줄러에서는 사용자가 작업을 제출할 때 지정한 처리 시간 제한을 CPU 버스트 시간으로 사용해 SJF 스케줄링을 할 수 있다.

하지만, 단기 스케줄러에서는 실제 CPU 버스트 시간을 알 수 없다. 따라서 이전 CPU 버스트 시간을 지수(exponential) 평균내어 다음 CPU 버스트 시간을 예측한다.

SJF 스케줄링은 선점형이거나 비선점형일 수 있다. 선점형일 경우에는, 현재 실행되고 있는 프로세스보다 새로운 프로세스의 CPU 버스트 시간이 더 짧을 경우, 새로운 프로세스가 끼어들어 실행된다. 선점형 SJF 스케줄링을 최소 잔여 시간 우선(shortest remaining time first) 스케줄링이라고도 한다.

5.3.3. 우선순위 스케줄링(Priority Scheduling)

우선순위 스케줄링은 선점형, 비선점형이 가능하다. 우선순위가 높은 프로세스를 스케줄링한다.

우선순위는 내부적 또는 외부적으로 정해질 수 있다. 시간 제한, 메모리, 열린 파일 수 등의 내부 요인과 프로세스 중요성, 작업 사용자 등의 외부 요인이 있다.

무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation) 문제가 생길 수 있다. 높은 우선순위의 프로세스들이 계속 들어와 낮은 우선순위의 프로세스들이 무한히 대기하는 경우이다. 한 해결 방안은 노화(aging)이며, 이는 시간이 흐름에 따라 대기 중인 프로세스의 우선순위를 증가시키는 것이다.

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

RR 스케줄링은 선점형이다. 이는 시간 할당량(time quantum) 또는 시간 조각(time slice)이라 하는 작은 단위의 시간을 사용한다. 10~100밀리초의 작은 시간이 지나면 다음 프로세스에게 CPU자원이 할당된다.

시간 할당량이 너무 크면 선입 선처리 스케줄링이 된다. 반대로 너무 작으면 매우 많은 문맥 교환이 이루어져 비효율적이 된다.

5.3.5. 다단계 큐 스케줄링(Multilevel Queue Scheduling)

프로세스의 특성에 따라 유형을 나누고, 그에 맞게 여러개의 큐를 만든다. 예를 들어, 시스템 프로세스, 대화형 프로세스, 일괄처리 프로세스 큐 등으로 나눌 수 있다. 프로세스는 자신의 유형에 맞는 큐에 들어가게 된다.

각 큐는 위에서 설명한 서로 다른 스케줄링 알고리즘을 가질 수 있다. 그리고 큐들간의 스케줄링도 사용된다. 큐들에 우선순위를 정하거나, 할당 시간을 정할 수 있다.

3.6. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

다단계 큐 스케줄링에서 프로세스는 하나의 큐에 배정받은 후에 다른 큐로 이동할 수 없다. 대조적으로, 다단계 피드백 큐 스케줄링에서는 프로세스가 다른 큐로 이동할 수 있다.

좋은 스케줄러로 동작되기 위해서는 다음과 같은 매개변수 값들이 정해져야 한다.

• 큐의 개수
• 각 큐의 스케줄링 알고리즘
• 프로세스를 높은 우선순위 큐로 올려주는 시기 결정
• 프로세스를 낮은 우선순위 큐로 강등시키는 시기 결정
• 프로세스가 들어갈 큐를 결정

5.4. 스레드 스케줄링(Thread Scheduling)

운영체제는 커널 스레드만 관리한다. 사용자 스레드는 스레드 라이브러리에 의해 관리되고, CPU상에서 실행되기 위해 LWP를 통한 간접적 방식일지라도 커널 스레드에 사상(mapping)되어야 한다.

5.4.1. 경쟁 범위(Contention Scope)

스레드 라이브러리는 사용자 스레드를 가용 LWP 상에서 스케줄 한다. 동일한 프로세스의 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스-경쟁 범위(process-contention-scope, PCS)라고 한다.

스레드 라이브러리가 LWP에서 스케줄을 하더라도, 사용자 스레드가 실제로 CPU 상에서 실행되기 위해서는 운영체제가 커널 스레드를 CPU로 스케줄 해야 한다. 어느 커널 스레드를 스케줄할 지 정하는 것을 시스템-경쟁 범위(system-contention scope, SCS)라 한다.

예로, POSIX Pthread 는 운영체제 시스템의 경쟁 범위 허용 정책을 얻어낼 수 있으며, PCS, SCS 스케줄링 정책을 정할 수 있다.

5.5. 다중 처리기 스케줄링(Multiple-Processor Scheduling)

다중 처리기들이 동일하다고 가정한다.
처리기들은 큐에 있는 임의의 프로세스를 실행할 수 있다. 그러나 한 처리기의 버스에 부착된 입출력 장치를 사용하는 프로세스는 반드시 그 처리기에서 수행되어야 한다.

5.5.1. 다중 처리기 스케줄링에 대한 접근 방법(Approaches to Multiple-Processor Scheduling)

주 처리기가 모든 스케줄링을 결정하고, 다른 처리기들은 사용자 코드만을 수행하는 방식은 비대칭 다중 처리(asymmetric multiprocessing)이라고 하며, 거의 쓰이지 않는다.

대신 대칭 다중 처리(symmetric multiprocessing, SMP)를 사용한다. 각 처리기가 독자적으로 스케줄링을한다. 모든 프로세스는 공동 준비 완료 큐에 있거나, 각 처리기에 있는 로컬 준비 완료 큐에 있게 된다.

5.5.2. 처리기 친화성(Processor Affinity)

처리기에 의해 가장 최근에 접근된 데이터가 그 처리기의 캐시를 채우게 된다. 프로세스가 다른 처리기로 이동할 경우, 이전 처리기의 캐시 메모리는 무효화되고 다음 처리기의 캐시는 다시 채워져야 한다. 하지만 이는 시간이 많이 들기 때문에 되도록이면 처리기간 이동을 피하는 처리기 친화성을 가지려고 한다.

운영체제가 동일한 처리기에서 프로세스가 실행되도록 노력하지만 보장하지는 않을 때, 연성 친화성(soft affinity)를 가진다고 한다. 반면, 프로세스가 실행될 처리기 집합을 명시할 수 있는 시스템은 강성 친화성(hardd affinity)를 가진다.

5.5.3. 부하 균등화(Load Balancing)

부하 균등화는 SMP 시스템의 모든 처리기 사이에 부하가 고르게 배분되도록 한다. 부하 균등화에 쓰이는 방법은 push 이주와 pull 이주 방식의 두 가지 일반적인 접근법이 있으며, 같이 쓰이기도 한다.

push 이주에서는 특정 테스크가 주기적으로 각 처리기의 부하를 검사하고, 과부하의 처리기에서 덜 바쁜 처리기로 프로세스를 이동시킨다. pull 이주 방식은 쉬고 있는 처리기가 바쁜 처리기에서 프로세스를 가져온다.

5.5.4. 멀티코어 프로세서(Multicore Processors)

멀티코어 프로세서는 하나의 물리 칩안에 여러 개의 처리기 코어가 있어 속도가 빠르고 적은 전력을 소모한다. 하지만 프로세서가 메모리를 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 허비한다. 메모리 멈춤(memory stall)이라 불리는 이 상황은 캐시 미스(L2 캐시 공유 등) 등의 여러 원인이 있다.

이를 해결하기 위해, 둘 이상의 하드웨어 스레드가 각 코어에 할당될 수 있는 멀티스레드 프로세서 코어를 구현한다. 한 스레드가 메모리를 기다리면, 코어는 다른 스레드로 전환할 수 있다.

일반적으로 처리기를 다중스레드화 하는 데에는 거친(coarse-grained)와 세밀한(fine-grained) 멀티 스레딩 2가지 방법이 있다. 거친 멀티 스레딩에서는 메모리 멈춤과 같은 긴 지연시간을 가진 사건이 발생할 때 다른 스레드를 실행한다. 이때 명령어 파이프라인을 완전히 정리하기 때문에 스레드간 교환 비용이 많이 든다.

세밀한 멀티 스레딩은 명령어 주기 종료시점과 같은 시점에서 스레드 교환이 일어난다. 이 시스템의 구조에는 스레드 교환을 위한 회로가 있어 스레드 교환 비용이 적어진다.

멀티스레드 멀티코어 프로세서는 두 단계의 스케줄링이 필요하다. 먼저 소프트웨어 스레드가 어느 하드웨어 스레드에서 실행될지 정해야 한다. 그리고 각 코어가 어떤 하드웨어 스레드를 실행시킬지 지정해야 한다.

5.6. 실시간 CPU 스케줄링(Real-Time CPU Scheduling)

실시간으로 스케줄링 되야하는 프로세스들은 아래와 같은 특성을 가질 수도 있다. 프로세스들은 주기적으로 CPU를 필요로 하며, 수행시간 t, 마감시간 d, 주기 p가 있다. 일반적으로 t <= d <= p 이다.

실시간 운영체제는 연성(soft), 경성(hard) 실시간 시스템으로 구분된다. 연성 실시간 시스템은 프로세스가 스케줄 되는 시점에 관해 아무런 보장을 하지 않는다. 단지 중요 프로세스가 우선권을 가진다는 것만 보장한다. 반면 경성 실시간 시스템에서는 테스크의 마감기한이 반드시 지켜져야 한다.

5.6.1. 지연 시간 최소화(Minimizing Latency)

사건 지연 시간은 사건이 발생해서 그에 맞는 서비스가 수행될 때까지의 시간을 말한다. 사건이 시스템에 요구하는 지연 시간보다 오랜 응답 시간이 발생하면 서비스를 제대로 제공하지 못할 수 있다.

인터럽트, 디스패치 지연시간이 실시간 시스템의 성능을 좌우한다. 인터럽트 지연시간은 CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴(ISR)이 시작하기까지의 시간이다. 디스패치 지연시간은 디스패처가 하나의 프로세스를 멈추고 다른 프로세스를 시작하는데 걸리는 시간이다.

5.6.2. 우선순위 기반의 스케줄링(Priority-Based Scheduling)

프로세스의 중요성에 따라서 우선순위를 결정하고, 더 높은 우선순위를 가진 프로세스가 선점이 가능한 스케줄링이다. 하지만 이는 테스크가 마감시간 내에 확실히 수행되는 것을 보장 못하기에, 경성 실시간 시스템을 만족하지 못한다.

프로세스가 마감시간을 스케줄러에게 알리고, 마감시간 내에 완수할 수 없다면 실행하지 않는 승인 제어(admission-control) 알고리즘을 사용할 수도 있다.

5.6.3. Rate-Monotonic 스케줄링

주기에 따라서 우선순위를 결정하고 선점 가능한 정적 우선순위 정책을 이용하여 스케줄 한다. 주기가 짧은 테스크는 높은 우선순위가, 주기가 길면 낮은 우선순위가 배정된다.

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

마감시간에 따라서 우선순위를 동적으로 부여한다. 마감시간이 빠를수록 우선순위가 높아지고, 늦을수록 낮아진다.

프로세스는 실행가능하게 되면 자신의 마감시간을 시스템에 알려야 한다. EDF 스케줄링에서는 프로세스들이 주기적일 필요가 없으며, 이론적으로 최적이다.

5.6.5. 일정 비율의 몫 스케줄링(Proportionate Share Scheduling)

승인 제어 정책과 함께 프로세스에게 시간을 할당하여 동작한다. 예로, 시간 T=100을 A=50, B=15, C=20 (합 85)으로 부여할 수 있다. 여기서 D=30이 요구되면 승인 제어기가 이를 거부한다.

5.7. 알고리즘 평가(Algorithm Evaluation)

5.7.1. 결정론적 모델링(Deterministic Modeling)

사전에 정의한 테스크 부하 시간에 대한 각 알고리즘의 성능(스케줄링 기준)을 계산한다.

5.7.2. 큐잉 모델(Queueing Models)

CPU와 입출력 버스트(실행 시간)의 분포를 측정하여 근사 값을 계산하거나 추정한다. 프로세스들이 시스템에 도착하는 시간의 분포도 기술할 수 있다.

이들 두 분포로부터 몇몇 알고리즘에 대한 평균 처리량, 이용률, 대기 시간등을 계산한다.

5.7.3. 모의 실험(Simulation)

수학(uniform, exponential 등) 또는 경험적 사건들의 분포를 사용하여 프로세스, CPU 버스트 시간 등을 생성하여 실험을 진행한다.

5.7.4. 구현(Implementation)

실제 코드로 작성해 운영체제에 넣고 실행하는 것이다.