CPU 스케줄링

• 운영체제는 한 번에 하나의 프로세스에 CPU를 할당해 줄 수 있다. 특히 프로세스마다 계산 중심의 작업(CPU Burst Process) 또는 I/O 중심 작업(I/O Burst Process)과 같이 특성이 다르기 때문에 어떤 프로세스에 CPU를 언제, 얼마나 줄지 결정하는 효율적인 메커니즘이 필요하다.

CPU 스케줄링

• CPU Scheduler는 Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 결정하는 역할을 한다. 해당 과정에서 프로세스 전환(Context Swithch)이 필요하므로 이를 담당하는 DisPatcher가 필요하다.
• Dispatcher는 CPU Scheduler에 의해 선택된 프로세스에 CPU 제어권을 실제로 넘겨주는 역할을 한다.
• 여기서 CPU Scheduler와 Dispatcher는 하드웨어 장치가 아니라 운영체제의 일부분으로 구현된 코드로 이해해야 한다.

프로세스에 다음과 같은 상태 변화가 있을 경우 CPU Scheduling이 필요하다.

1. Running -> Blocked (ex: I/O 요청하는 시스템 콜)
2. Running -> Ready (ex: 할당시간 만료로 Timer Interrupt)
3. Blocked -> Ready (ex: I/O 완료 후 인터럽트)
4. Terminate

• 1, 4의 경우 스케줄링은 비선점(nonpreempive)방식으로 강제로 CPU를 빼앗지 않고 자진 반납한다.
• 나머지 스케줄링은 선점(preemptive)방식으로 강제로 CPU를 빼앗는다.

CPU 스케줄링 평가 항목

• CPU 스케줄링 정책을 비교하기 위해서는 평가 항목이 필요하다. 프로그램의 특성에 맞게 평가 기준이 설정되어야 한다. 1,2는 시스템 관점에서 3,4,5는 프로그램 관점에서 평가 기준을 제공한다.

1. CPU utilization(이용률)

• CPU가 작업을 처리하는 데 실제로 소요되는 시간의 비율을 나타낸다. 유휴 시간을 제외한 비율로 시스템의 효율성을 나타낸다.

2. Throughput(처리량)

• 주어진 시간 동안 CPU가 몇 개의 작업을 완료했는지 나타낸다. 시스템 처리 능력 지표로 사용된다.

3. Turnaround time(소요 시간, 반환시간)

• CPU를 얻기 시작한 순간부터 처리가 완료되어 결과가 반환될 때까지 전체 시간을 나타낸다. 여기에는 대기 시간, 실행 시간, I/O 처리 시간이 포함될 수 있다.

4. Waiting time(대기 시간)

• CPU를 얻기 위해 기다린 시간을 나타낸다. interrupt, system call로 Waiting time은 점점 증가할 수 있다.

5. Response Time(반응 시간)

• 처음으로 CPU를 얻기까지 기다린 시간을 나타낸다.

여기에서 시간은 프로세스가 생성되고 종료되기까지의 시간을 의미하는 것이 아니다. CPU를 사용하기 위해 기다리고, I/O 등으로 프로세스가 전환되기까지 일련의 시간을 의미한다. (한 번의 Burst Time)

CPU 스케줄링 알고리즘

1. 선입선출(FCFS, First Come First Served)

• 먼저 들어온 작업부터 처리한다. 단순하고, 구현하기 쉽다는 장점을 가진다.
• convoy effect가 발생한다. 예를 들어, 처음에 Burst Time이 많이 필요한 작업이 생긴다면, 그 이후에 온 작업의 Turnaround time이 증가한다.
  

2. 최단 작업 우선(SJF, Shortest Job First)

• 가장 짧은 Burst Time 작업부터 처리한다. 모든 작업이 동시에 도착한다면 최적(Optimal)을 보장한다. 여기서 최적이란 minimum average wait time을 말한다.
• 기본적으로 비선점(non-preemptive)이기에 오래 걸리는 특정 작업이 먼저 도착한다면 여전히 convoy effect가 발생한다.
  

3. 최소 잔여시간 우선(STCF, Shortest Time-to-Completion First)

• 새로운 작업이 들어오면, 스케줄러는 남아 있는 작업과 새로운 작업의 잔여 시간을 계산하고 더 적은 잔여 실행 시간을 가진 작업을 선택한다. SJF와 달리 선점형(preemptive)이다.
• 항상 minimum average wait time을 보장한다.
• SJF와 STCF는 다음의 문제점을 가진다.
  - 기아(starvation)문제가 발생할 수 있다.
  - 프로세스 Burst Time을 사전에 모두 알고 있어야 한다.
  - 응답 시간(Response Time)에 민감한 프로그램에는 적합하지 않다.
  

4. 라운드 로빈(RR, Round Robin)

• 일정 시간 동안(time slice 또는 time quantum) 프로그램을 실행한 후 선점(Preemptive)당하여 다시 대기 큐에 들어간다.
• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit이라면 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
• 타임 슬라이스의 길이가 매우 중요하다. 타임 슬라이스가 짧을수록 응답 시간은 점점 좋아진다. 하지만 짧을수록 프로세스 전환 비용(Context Swith)이 커진다.
  • Context Switch 비용에는 레지스터 저장과 복원하는 작업, CPU 캐시, TLB, 분기 예측 등 다양한 하드웨어 정보가 저장되어 있는데 이를 갱신해야 하는 것이다. 이는 성능 문제를 유발할 수 있다.
• Response Time(응답 시간) 기준에서는 효과적이나 Turnaround Time(반환 시간) 기준에서는 거의 최악이다.

5. 멀티 레벨 피드백 큐(MLFQ, Multi-Level Feedback Queue)

• MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위(priority level)가 배정된다.
• MLFQ는 각 작업에 고정된 우선순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다. 예를 들어 키보드 입력을 기다리며 반복적으로 CPU를 양보하면 MLFQ는 해당 작업의 우선순위를 높게 유지한다.
• MLFQ의 두 가지 기본 규칙
  1. Priority(A) > Priority(B)이면, A가 실행된다.
  2. Priority(A) = Priority(B)이면 RR(Round Robin)방식으로 실행된다.

이러한 방식은 우선순위가 낮은 작업은 실행될 수가 없다. 이를 보완하기 위해 추가 규칙을 적용한다.

3. 작업이 시스템에 진입하면, 가장 높은 우선순위를 가진다.
4. 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다.
5. 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

• 특정 작업이 들어올 때 MLFQ 동작 과정을 살펴보자.
  1. 한 개의 긴 실행 시간을 가진 작업
     • 최고 우선순위로 진입하다가 주어진 타임 슬라이스를 사용하면서 점점 낮은 우선순위 큐로 이동하게 된다.
  2. 짧은 작업
     • 스케줄러는 짧은 작업인지, 긴 작업인지 알 수 없기 때문에 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여한다. 짧은 작업이 아니라면 서서히 아래 큐로 이동하여 SJF 방식을 근사하게 된다.
  3. 입출력 작업
     • 규칙 5를 보면, 프로세스가 타임 슬라이스를 소진하기 전에 양도하면 같은 우선순위를 유지한다. 이는 대화형 작업에서 계속 CPU를 양도하기 때문에 높은 우선순위를 유지할 수 있다.

여전히 2가지 문제가 있다.
첫째로 기아가 발생한다. 긴 작업은 일정 시간을 사용하고 점점 우선순위가 낮아지므로 CPU 점유할 기회가 점점 없어지는 것이다.
둘째로 악의적인 사용자에 취약하다. 일정 시간이 끝나기 전에 출력 작업을 하여 높은 우선순위가 유지할 것이다. 이는 CPU를 거의 독점적으로 사용하는 게 가능하다.

• 기아 문제를 해결하기 위해 새로운 규칙을 추가한다.
  • 규칙 6. 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.
    • 이는 기아 문제를 자연스럽게 해결한다. 추가로 어떤 프로세스가 CPU 위주의 작업에서 대화형 작업으로 변경되었더라도 우선순위 상향을 통해 높은 반응성을 제공할 수 있다.
• 추가로 악의적인 사용자의 입출력 요청은 어떻게 처리할까? 기존 규칙을 수정하여 MLFQ 각 단계에 CPU 총사용 시간을 측정한다. 일정 시간 동안 주어진 CPU시간을 소진하면 우선순위를 낮춘다.
  • 규칙 4, 5 -> 주어진 단계에서 CPU 할당량을 소진하면(CPU를 몇 번 양보했든지 상관없이) 우선순위는 낮아진다.

정리하면 다음과 같다.
1. Priority(A) > Priority(B) 이면, A가 실행된다.
2. Priority(A) = Priority(B) 이면 RR(Round Robin)방식으로 실행된다.
3. 작업이 시스템에 진입하면, 가장 높은 우선순위를 가진다.
4. 주어진 단계에서 CPU 할당량을 소진하면(CPU를 몇 번 양보했든지 상관없이) 우선순위는 낮아진다.
5. 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

• MLFQ에는 다음과 같은 쟁점이 남아있다. 몇 개의 큐가 존재해야 하는가? 큐당 타임 슬라이스의 크기는 얼마로 해야 하는가? 얼마나 자주 우선순위가 상향 조정되어야 하는가? 이러한 질문에 쉽게 대답할 수 없고, 워크로드에 대해 충분히 경험하고 계속 조정해 나가면서 균형점을 찾아야 한다고 한다.

6. 비례 배분 스케줄링(Proportion Share)

• 반환 시간이나 응답 시간을 최적화하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것이 목적이다.

특정 비율로 CPU를 배분하는 스케줄러를 어떻게 설계할 수 있을까?

1) 추첨권 방식 스케줄링

• 추첨권은 프로세스가 받아야 할 자원의 몫을 나타내는 데 사용된다. 예를 들어 A와 B 프로세스가 각각 75장의 추첨권, 25장의 추첨권을 가지고 있을 때 A에게는 CPU의 75%, B에게는 CPU의 25%를 할당하는 것이 목적이다.
• 추첨 스케줄링은 확률적으로 이러한 목표를 달성한다. 100장의 추첨권(0~99) 중에 무작위로 뽑는다. 0~74라면 A가 실행되고, 75~99라면 B가 실행된다.

이렇게 추첨권을 무작위로 뽑는 건 어떤 이점이 있을까?

• 무작위 방식은 전통적인 결정 방식에 비해 세 가지 장점이 있다고 한다.
  1. 특이 상황에 잘 대응한다. (ex: LRU는 좋은 교체 알고리즘이지만, 반복되는 순차적인 접근 패턴에선 최악의 성능을 보인다. 무작위 방식에서는 최악의 경우가 발생하지 않음)
  2. 매우 가볍다. (관리해야 할 상태 정보가 거의 없다. 아래 살펴볼 보폭 스케줄링은 프로세스별 보폭 정보를 계속해서 유지해야 한다. 이는 확장성을 제한함)
  3. 매우 빠르다. (난수 발생 시간이 빠르기만 하면 결정 역시 빠르게 된다. 물론 속도를 증가시키기 위해 추첨 과정을 덜 무작위로 만들기도 함)

추첨 기법

(1) 추첨권 화폐

• 추첨권을 다루는 다양한 기법이 있지만, 추첨권 화폐(ticket currency) 개념을 살펴본다. 사용자가 추첨권을 자신의 화폐 가치로 추첨권을 자유롭게 할당할 수 있도록 허용한다. 시스템은 자동으로 화폐 가치를 변환한다.
  • 예를 들어, 사용자 A, B가 각각 100장의 추첨권을 받았고, 사용자 A는 A1, A2 프로세스에 500장의 추첨권을 할당(전체 1000장)하였다. B는 자신의 기준 화폐 10장 중 10장을 B 프로세스에 전부 할당하였다.
  • 시스템은 A1과 A2의 몫을 각각 50장으로 변환하고, B는 100장으로 변환한다. 총 200장 기준으로 추첨한다.

(2) 추첨권 양도

• 추첨권 양도(ticket transfer)를 통해 프로세스는 일시적으로 추첨권을 다른 프로세스에 넘겨줄 수 있다. 이는 클라이언트/서버 환경에서 특히 유용하다. 작업이 빨리 완료될 수 있도록 클라이언트는 서버에게 추첨권을 전달하고 서버가 자신의 요청을 수행하는 동안 서버의 성능을 극대화하려고 한다. 요청을 완수하면 서버는 추첨권을 다시 클라이언트에게 돌려준다.

(3) 추첨권 팽창

• 프로세스는 일시적으로 자신이 소유한 추첨권의 수를 늘리거나 줄일 수 있다. 이는 서로 신뢰하는 프로세스 간의 경우에만 유효하다. 어떤 프로세스가 더 많은 CPU 시간이 필요하다면 시스템에이를 알리는 방법으로 다른 프로세스들과 통신하지 않고 혼자 추첨권의 가치를 상향 조정한다.

구현

// counter: 당첨자를 발견했는지 추적하는 데 사용
int counter = 0;

// winner: 0부터 총 추첨권의 수 사이의 임의의 값을 얻기 위해 난수 발생기 호출
int winner = getrandom(0, totaltickets);

// current: 작업 목록을 탐색하는 데 사용
node_t *current = head;

// 티켓 값 > winner를 만족할 때까지 반복
while (current) {
    counter = counter + current->tickets;
    if (counter > winner)
        break; // 당첨자 발견
    current = current->next;
}
// current는 당첨자를 가리킴. 이를 실행할 수 있도록 준비

• https://github.com/chyyuu/os_tutorial_lab/tree/master/ostep Ostep에서 제공하는 추첨권 방식 시뮬레이터. 작업 실행 시간, 티켓 수, 작업 수, 최대 작업 길이, 최대 티켓값, 퀀텀(CPU 할당 시간)을 조절하여 비례 배분 스케줄링이 어떻게 동작하는지 직접 눈으로 볼 수 있다.

2) 보폭 스케줄링

• 무작위성을 이용하면 스케줄러를 단순하게 만들 수는 있지만, 정확한 비율을 보장할 수 없다. 이 말은 추첨권 방식의 경우 실제 실행 과정에서 특정 작업에 몰릴 수 있다는 것이다. 보폭 스케줄링을 사용하면 짧은 기간에서도 일정한 비율을 보장할 수 있다.

구현

current = remove_min(queue);        // pass 값이 최소인 클라이언트 선택
schedule(current);                  // 자원을 타임 퀀텀만큼 선택된 프로세스에 할당
current->pass += current->strides;  // 다음 pass 값을 보폭 값을 이용하여 갱신
insert(queue, current);             // 다시 큐에 저장

• 예를 들어 세 작업(A, B, C) 각자 보폭이 100, 200, 40인 경우 각자 pass 값은 0부터 시작한다. 처음에는 pass 값이 같으므로 아무 프로세스나 실행된다. 가장 먼저 A가 실행된다고 하면 실행 과정은 다음과 같다.

{0,0,0}       A선택
{100,0,0}     B선택
{100,200,0}   C선택
{100,200,40}  C선택
{100,200,80}  C선택
{100,200,120} A선택
{200,200,120} C선택
{200,200,160} C선택
{200,200,200}

• 이처럼 보폭 스케줄링은 정확하지만, 상태 정보를 가진다는 단점이 있다. 만약에 스케줄링 중간에 새로운 작업이 도착했다면 해당 작업에 pass 값은 얼마가 되어야 할까? 만약 0이라면 CPU를 독점하게 될 것이다. 반면에 추첨권 방식의 경우 새 프로세스를 추가할 때 해당 프로세스가 가진 추첨권의 개수, 전체 추첨권의 개수만 갱신하면 쉽게 스케줄링할 수 있다.

참고자료

• 2014 이화여대 반효경 운영체제 강의
• 운영체제, 아주 쉬운 세 가지 이야기