[Operating System] Scheduling

[1] Scheduling (Single-Processor의 경우)

CPU Virtualization

CPU virtualization이란 실제로는 여러 프로세스가 CPU와 메모리 자원을 공유하지만 각각의 프로세스에게는 마치 독점적으로 CPU와 메모리를 사용하는 듯한 착각을 주는 것을 의미한다.

CPU virtualization은 context switch를 통한 time sharing, 그리고 가상 메모리를 활용한 space-sharing을 통해 이루어진다.

 

CPU virtualization을 위해서는 dispatcher(어떻게 context switch를 할지, 어떤 context를 save-restore할지)와 scheduler(어떤 프로세스를 실행 시킬지)가 필요하다.

 

Scheduler 성능 평가의 Metric

• turnaround time 최소화: job이 도착부터 끝날 때까지
• response time 최소화: job이 도착부터 시작될 때까지
• waiting time 최소화: ready queue에서 스케줄링을 기다린 시간
• throughput 최대화: 단위시간 동안 처리한 job
• utilization 최대화: hierarchy가 높은 자원을 최대한 busy하게
• overhead 최소화: 컨텍스트 스위치를 최소화
• fairness 최대화: 단위시간 동안 모든 job이 얼마나 공평하게 스케줄링 되었는가

 

FIFO (FCFS)

• 만약 모든 job이 동일한 시간에 도착하였다면 fairness가 최악
• turnaround time은 나쁘지 않음
• 처음 들어온 job의 runtime이 길고 뒤에 들어온 job은 짧다면 매우 비효율
• non-preemptive

 

SJF (Shortest Job First)

• turnaround time 좋음 / fairness도 나쁘지 않음
• 다만 새로운 job이 들어올 때마다 새로 스케줄링 되는 것이 좋음 --> STCF(PSJF)

 

STCF (Shortest Time to Completion First)

• = PSJF(Preemptive Shortest Job First)
• 새로운 job이 도착한 시점에 새롭게 스케줄링

 

Round Robin (RR)

 

• Response time에 최적화
• 각 task는 고정된 크기의 time slice를 가짐
• 각 process job이 혼자서 CPU를 독점적으로 사용하는 듯한 착각을 줌
• 각 job의 길이를 미리 알 수 없는 경우 짧은 job을 일찍 끝낼 수 있음
• 만약 모든 job의 길이가 동일하다면 turnaround time은 최악
• Time slice의 크기를 잘 정하는 것이 중요함
  • context switch의 오버헤드를 고려해야함
  • 만약 interactive job이 주어졌다면 time slice가 작은 것이 좋음
• Context switch의 오버헤드가 큼

 

I/O와 스케줄링

Disk I/O를 하는 동안에는 CPU가 필요 없으므로 현재 process는 block 하여 스케줄링 되지 않도록 하고 다른 process에게 더 많은 기회를 준다. I/O가 끝나서 인터럽트가 발생하면 다시 해당 프로세스를 ready queue에 넣어준다.

 

DMA (Direct memory access)를 통해서 I/O를 하는 동안에도 CPU는 다른 작업을 수행할 수 있다.

 

 

MLFQ (Multi-level Feedback Queue)

• Interactive Job (빠르게 끝남): response time 최소화가 중요
• Batch Job (시간이 오래 걸림): turnaround time 최소화가 중요
• Priority에 따라서 multi-level queue가 존재함
  • Interative: 높은 priority
  • Batch: 낮은 priority

작동 Rules

• 높은 priority job 먼저 스케줄링 한다.
• Priority가 같다면 RR로 돌리되 time slice의 크기는 낮은 prior일수록 길게 한다.
• 만약 time slice 내에 job을 마치고 yield 하였다면 priority를 유지하고, time slice를 다 썼으면 demote 시킨다. (SJF과 같은 효과)
• 새로운 job이 들어오면 최상위의 priority 부여

 

문제점

• Starvation: 만약 interactive job이 너무 많다면 batch job들은 스케줄링 될 기회가 사라진다. 이를 방지하기 위해서 priority boost가 필요!
  • Priority Boost: priority가 낮은 batch job들도 일정 주기로 높은 priority queue로 올려준다.
• Gaming: 어플리케이션에서 demote가 되지 않도록 고의적으로 CPU를 반복적으로 점유하여 시스템을 악용할 수 있음.
  • 이를 막기 위해서 각 job이 특정 level의 queue에서 머무른 총 시간을 함께 고려한다. 만약 하나의 priority queue에서 특정 시간 이상 머물렀으면 낮은 level로 demote 시킨다.
• 튜닝이 어렵다. (큐의 개수, priority boost의 간격과 정도, time slice 등등)
  • 각각의 priority queue마다 다른 time slice 길이를 정해야한다. priority가 높을 수록 짧은 time slice.
  • Context switch의 오버헤드와 fairness 간에는 trade-off가 존재함을 고려해서 policy를 만들어야 한다.

Starvation 상황(left)과 이를 해결하기 위한 Priority Boosting 결과(right)

Run queue의 priority에 따른 time slice의 길이

 

Fare-Share Scheduler

• Turnaround time이나 response time 보다는 fairness를 올리는데 초점
• 각각의 job이 미리 정해진 특정 비율만큼 CPU를 점유하도록 함

 

(1) Lottery Scheduling

Lottery scheduling에서는 스케줄러가 run queue의 task priority에 따라 ticket을 분배한다. 그리고 매 스케줄링 시점마다 ticket 중 하나를 랜덤하게 뽑고, 해당 번호의 ticket을 가진 run queue의 task를 스케줄링한다.

 

Ticket 메커니즘

• Priority를 고려하지만 priority가 높은 job이 많이 있다고 해서 낮은 job이 starvation 되지는 않음
• Priority를 고려하여 각 프로세스에게 티켓을 할당함 (높을 수록 많은 티켓)
• 랜덤하게 번호를 뽑아서 해당 번호의 티켓을 가진 process의 job을 스케줄링함
• 전체 티켓(global currency)을 어떻게 정할지, priority 당 티켓을 몇개 발행할지, job이 도중에 종료되면 어떻게 할지 등에 대해서 정해야함
• Ticket Transfer: 다른 process에게 티켓을 양도함으로써 priority boosting
• Ticket Inflation: 일시적으로 자신의 티켓 개수를 증가시켜서 priority boosting
• Job의 길이가 길수록(티켓의 개수가 많을 수록) 더 많은 스케줄링 기회를 갖게 된다.

 

int counter = 0;
int winner = get_random(0, total_tickets);
node_t *current = head;

while(current) {
    counter += current->tickets;
    if(counter > winner)
        break;
    current = current->next;
}

// current is the winner!

 

 

(2) Stride Scheduling

 

• 각 프로세스마다 priority에 따라서 stride가 하나씩 부여됨
• priority가 높을 수록 stride가 작음
• 0으로 시작해서 process가 돌때마다 해당 프로세스의 pass value에 stride 값 만큼을 더해줌
• 스케줄링 시점에 가장 낮은 pass value를 가진 프로세스를 스케줄링 함
• 만약 중간에 새로운 job이 들어온다면 현재 시점에서 가장 낮은 pass value로 초기화

 

 

---

[2] Multiprocessor Scheduling

• 어떤 코어에서 어떤 job을 돌릴지도 스케줄러가 결정해야할 문제
• context switch 시에 캐시를 가능한 보존할 수 있는 방향으로 CPU 코어와 job 간에 매칭을 해주어야함 (Cache Affinity)

 

Cache Coherence

• 동일한 메모리를 공유하는 CPU 간에 sync가 필요함
• 이를 위해서 Bus Snooping을 수행. 데이터 버스를 지속적으로 관찰하면서 자신이 캐시에 보관 중인 데이터에 change가 발생하면 이를 알아차리고 invalidate하거나 update를 함

 

Cache Coherence를 유지하기 위한 방법

1. Update 기반
특정 캐시 블록에 write가 이루어지면 bus snooping을 통해서 모든 다른 캐시들의 copy들도 업데이트 한다. Bus를 통해 write를 broadcast하는데, 이로 인하여 bus의 트래픽이 커지는 문제가 있다.

2. Invalidation 기반
특정 캐시 블록에 write가 이루어지면 bus snooping을 통해서 모든 다른 캐시의 copy들을 invalidate 한다. 이후에 invalidate 된 캐시 블록에 접근을 하는 프로세스가 있다면 coherence cache miss가 발생하면서 메모리에서 최신 값을 읽어온다. 이 때도 bus snooping을 하게 되는데, 만약 다른 캐시에서 최신 버전의 캐시 블록을 가지고 있다면 메모리에 접근하려던 것을 취소하고 해당 캐시 블록을 사용한다.

 

Cache Affinity

• 하나의 프로세스가 돌아가면서 사용했던(접근했던) 메모리는 캐시에 올라와 있는데 context switch 이후에 다른 프로세스가 코어에 올라가면 캐시 미스가 발생하여 캐시의 내용이 크게 바뀔 수 있음
• 이를 방지하기 위해서(cache affinity 를 위해서) 하나의 프로세스는 가능한 하나의 CPU에서만 처리하도록 스케줄링하는 것이 효율적임

 

1. Cache Affinity - SQMS (Single-Queue Multiprocessor Scheduling)

 

• 여러 개의 코어가 있는데 스케줄링은 하나의 큐에서만 진행
• 이 때 큐는 공유 자원이므로 sync가 되어야함
• 장점: job들이 코어들마다 공평하게 분배됨
• 단점: 공유 자원인 큐에 대한 locking 오버헤드

 

2. Cache Affinity - MQMS (Multi-Queue Multiprocessor Scheduling)

 

• 각 코어마다 하나씩 큐를 가지고 있음
• SQMS보다 affinity가 좋음(프로세스마다 자신의 큐가 있기 때문)
• 어느 곳이 busy하고 어느 곳이 idle한지에 대한 전체의 큰 그림을 볼 수가 없음
  • 이를 해결하기 위해서 load balancing이 필요

 

Load Balancing

• 각 CPU 큐는 독립적이므로 정보 공유를 하지 않기 때문에 서로의 상태를 알지 못함
• Work Stealing
  • 스케줄러가 가장 여유로운 CPU의 큐를 source 큐로 선택
  • target 큐로 임의 선택된 큐가 source 큐보다 busy하면 source 큐는 target 큐의 job을 stealing(migrate) 한다