Scheduling 2

  이전 글에서는 싱글코어 CPU가 여러 프로세스들을 다루는 방법을 알아봤다. 하지만 우리가 현재 쓰고 있는 컴퓨터들은 대부분 멀티코어를 사용한다. 그렇기 때문에 지금부터는 멀티코어에서 일어나는 스케줄링에 대해 알아볼 것이다.

NUMA and CPU Scheduling

fig 7-1

  fig 7-1을 보면 CPU를 볼 수 있는데(왼쪽 0, 오른쪽 1) 멀티코어는 CPU내부에 코어가 여러개 존재하는 것이다. 그리고 각 CPU는 직접적으로 연결된 메모리가 존재한다. 여기서 더 큰 스케일의 컴퓨터라면 이러한 CPU가 2개 이상 설치될 수도 있다. 이러한 상황에서 CPU의 코어는 인접한 다른 CPU의 메모리에도 접근할 수 있다. 하지만 이때의 속도는 직접적으로 연결된 메모리 접근속도보다 당연히 더 느릴 것이다. 이런 경우를 Non Uniform Memory Access(NUMA)라고 한다.

  예를 들어 0번 CPU에 프로세스를 올릴 때 프로세스가 0번 메모리에 위치해 있다면 빠르게 불러올 수 있겠지만, 프로세스가 1번 메모리에 위치해 있다면 계속해서 느린 속도로 프로세스를 불러와야 한다. 그렇기 때문에 해당 아키텍처의 스케줄러는 최대한 CPU에서 프로세스를 불러올 때 직접적으로 연결된 메모리에 위치한 프로세스를 불러오게끔 해야한다. 용어로 표현하자면 affinity를 고려해야 한다는 것이다.

 

Multiple-Processor Scheduling - Load Balancing

  그렇기 때문에 코어가 많을 때는, queue안에서 어떠한 프로세스를 선택하는 것 뿐만 아니라 한쪽 CPU가 붐비고 있으면 로드 시 균형을 맞춰야 CPU가 골고루 동작하게 하는 Load balancing을 해줘야 한다. 이를 위한 두가지 기법이 있는데 하나는 주기적으로 각 프로세서의 상태를 체크하여 overloaded CPU가 있으면 작업을 덜 바쁜 CPU로 이동시키는 Push migration 기법이고, 다른 하나는 idle한 프로세서가 바쁜 프로세서에 있는 작업을 가져오는 Pull migration이다.

 

Multicore Processor

fig 8-1

  조금 헷갈릴 것 같은 용어를 정리하고 넘어가자. 이전에, CPU에는 하나의 코어밖에 없었는데 이러한 CPU를 여러개 합쳐서 멀티 프로세서 시스템을 만들었다. 하지만 현재는 CPU에 여러개의 코어가 들어간다. 그리고 이것을 멀티코어라고 하고 프로세서라고 통칭한다. 최근 트렌드는 다수의 프로세서 코어를 동일한 물리적 칩에 위치시킨다. 이렇게 하면 빠른 속도와 높은 전력 효율을 얻을 수 있다. 

 

Multi-threaded Multicore System

  CPU가 명령을 실행할 때 메모리에서 정보를 가져와서 이를 해석하여 명령을 수행하는데 이때 메모리에 갔다오는 것은 CPU입장에서는 굉장히 오버헤드가 큰 작업이다. 즉 memory stall이 발생하는 중에는 CPU에 있는 많은 HW유닛들을 활용할 수 없게 된다. 그렇기 때문에 코어들을 더 효과적으로 다루기 위해서 multiple threads를 사용하는데 여기서의 쓰레드의 의미는 이전에 본 SW적 의미의 쓰레드가 아니다. 

fig 9-1

    fig 9-1을 보자. 하나의 코어에서 HW적 쓰레드가 하나뿐이라면 memory stall상태에서는 compute를 할 수 없다. 하지만 다중 쓰레드를 구현하게 되면 memory stall상태에서 쓰지 않고 있는 코어 자원을 다른 쓰레드(sw쓰레드, 다른 프로세스, ...)에서 활용할 수 있다. 이렇기 때문에 physical한 코어는 하나 뿐이지만 두 개의 쓰레드가 동시에 진행되는 것 처럼 보인다.

 

Real-Time CPU Scheduling

  CPU는 빠른 속도로 동작하기 때문에 스케줄링을 실시간으로 해줘야 한다. 이를 위한 두가지 종류의 시스템이 있다.

  hard real-time systems에서는 어떤 작업이 무조건 정해진 deadline까지 맞춰져야 한다. 군사, 임베디드 등에서는 쓰일 수 있겠지만 모든 작업이 deadline에 맞추기는 어렵다. 이러한 시스템은 soft real-time systems라고 한다. 그럼 deadline에 맞추고자 할 때 영향을 주는 요소는 무엇이 있을까?

  첫번째로는 interrupt가 발생하여 이에 대한 루틴이 시작하기까지의 시간인 interrupt latency가 있고, 두번째로는 현재 돌고 있는 프로세스를 거두고 새로운 프로세스로 스케줄링 하기까지의 시간인 dispatch latencty가 있다.

Priority-based Scheduling in Real-Time

fig 10-1

  그리고 real time scheduling에서는 작업에 우선 순위를 두고 우선 순위가 높은 작업부터 처리하려고 한다. 그렇기 때문에 높은 우선순위의 작업들은 낮은 우선 순위의 작업들의 자원을 preempt할 수 있어야 한다. 그리고 hard real-time에서는 deadline을 무조건 충족시킬 수 있는 기능을 제공해줘야 한다. fig 10-1을 보자. 프로세스들은 새로운 특성을 갖는데, 프로세스들이 정해진 간격(interval)마다 주기적으로 CPU를 요구한다. 이것이 p이다. p시간 안에 프로세스가 얼마만큼의 deadline(d)을 갖고 실제로 실행되는지(t)에 따라 p, d, t를 구분할 수 있다. 이 개념을 가지고 다음을 살펴보자.

Rate Monotonic Scheduling (RMS)

 

fig 10-2

  이 방법에서는 p가 낮을 수록 높은 우선순위를 갖는다. fig 10-2를 보자. P1(50,20), P2(100,35)이라고 하자. 첫번째 수는 period, 두번째 수는 processing time이다. 즉 P1은 50마다 cpu를 요구하고, P2는 100마다 cpu를 요구하고 각각 period동안 20, 35동안 cpu를 사용해햐 한다. 이때는 P1이 더 높은 우선 순위를 가진다. 이 그림에서는 큰 문제가 없어 보인다.

fig 10-3

    이런 경우에는 어떨까? P1은 문제가 없어 보이지만 P2는 35만큼 걸리는 작업을 deadline안에(적어도 80보다 많이 걸렸으니) 다 끝내지 못했다. U는 CPU의 사용률을 나타낸다. fig 10-3같은 경우에는 \(25/50+35/80=0.9375\)가 되므로 높은 사용률을 가진다. 그럼에도 P2는 deadline을 맞출 수 없었다. 그러므로 hard real-time에서는 문제가 될 수 있다.

  그리고 프로세스의 수를 n이라고 할 때, RMS에서의 U는 다음과 같은 thoretical bound를 가진다.

\(U<n(2^{1/n}-1)\)

  그러므로 n이 무한대로 커지면 U는 최대 69%가 된다. 그러므로 RMS는 프로세스의 수가 커질 수록 낮은 U를 가지게 된다.

Earliest Deadline First Scheduling (EDF)

fig 10-4

  이 방법은 deadline이 더 빨리 마감되는 프로세스가 높은 우선순위를 가진다. fig 10-4는 fig 10-3과 같은 상황이다. 우선 첫번째 P1이 deadline안에 끝나고 25~60동안 P2가 수행 중이다. RMS였다면 50에서 P1이 수행되었어야 하지만 EDF에서는 P2의 deadline이 우선이니 계속 P2를 수행하게 된다. 이런 식으로 진행되면 전 처럼 deadline을 못지키는 일이 없어지게 된다.

Proportional Share Scheduling

  이 방법은 CPU의 자원을 T 등분했다고 보면 된다. 그리고 각 프로세스가 이것의 일부를 가져가는 것이다. 예를 들어 T = 100이라고 하자. A=50, B= 15, C=20이라면, A는 전체 프로세서 시간의 절반을, B는 15%를, C는 20%를 사용하여 총 85%를 프로세스들이 사용하게 된다. 이때 만약 D=30이 들어오게 되면 admission controller가 D의 출입을 막는 식으로 작동한다. 이 방법에서는 더 많이 사용할 프로세스에게 많은 파이를 가져다 줄 수 있다.

 

Algorithm Evaluation

  앞서 몇가지 스케줄링 기법들에 대해 살펴보았는데 '완벽한' 스케줄링 기법은 없다. 그러므로 시스템의 목적에 따라 적절한 스케줄링 기법을 선택해야 한다. 이를 위해 기준을 정하고 어떤 알고리즘이 적합할지 평가해봐야 한다.

Deterministic Evaluation

fig 11-1

fig 11-2

  waiting time을 최소로 가져가고 싶은 스케줄러를 선택하고 싶을 때는 fig 11-1같은 케이스를 가져와서 계산해보면 fig 11-2같은 결과를 얻을 수 있다. 하지만 이런 상황은 굉장히 단순하므로 실제 상황에서 따르는 부수적인 현상들을 반영하지는 못한다.

Queueing Models

fig 11-3

  예를 들어 프로세스들이 큐로 다뤄질 때 프로세스들이 큐에 도착하거나 대기하는 상황에 따라 성능이 달라질 수도 있다. 이러한 것 까지 감안하여 수학적, 확률적으로 모델을 세우고 formulation할 수 있다. 여기서 다루기에는 조금 난이도가 있는 이야기인 것 같다. 간단하게 나타내면 fig 11-3과 같겠다.

Evaluation of Schedulers by Simulation

fig 11-4

  어찌됐든 모델링을 통해 뭔가 효과적일 것 같다 싶으면 이제는 시뮬레이션을 통해 좀더 구체적으로 구현을 해보는 것이다. 보통은 fig 11-4 처럼 실제 프로세스를 실행한 다음에 trace tape에 CPU는 얼마나 쓰는지, I/O는 얼마나 걸리는지 등의 정보를 기록한다. 그리고 이것을 각 스케줄러의 시뮬레이터에 넣어줘서 퍼포먼스가 어떻게 되는지 확인한다.

Implementation

  어찌됐든 가장 정확한 것은 실제로 구현해보는 것이다. 그렇지만 실제환경은 매우 변화무쌍하고 작은 것에도 영향을 받을 수 있기 때문에 검증하는데에 많은 코스트가 필요하다. 

 

Linux Scheduling

  그럼 이제는 리눅스 환경에서의 스케줄링을 예시로 살펴보자.

Scheduling Policy: Linux process proiority

fig 12-1

  리눅스에서는 보통의 프로세스는 nice value라는 -20~+19까지의 priority를 가지는데(기본값은 0) 높은 값일 수록 낮은 priority를 가진다. 만약 real-time 프로세스로 설정하면 0~99까지의 값을 가질 수 있게 되고이때는 높은 값이 높은 priority를 가진다. real-time 프로세스는 항상 표준(nice) 프로세스보다 먼저 실행된다.

  fig 12-1을 보면 알겠지만 커널 입장에서는 프로세스는 0~139의 priorty를 가질 수 있다.

Scheduling Policy: timeslice in Linux CFS (Completely Fair Scheduling)

  리눅스에서도 timeslice를 가진다. 하지만 앞서 말했듯이 time slice가 너무 길면 반응성에 문제가 생기고, 너무 짧으면 context switching의 비용이 많이 발생하게 된다. 그렇기 때문에 default timeslice를 결정하는 것은 쉬운 일이 아니다.

  만약 싱글코어에서 두 개의 작업이 올려져 있다면 어떤 식으로 스케줄링을 수행하게 될까? 하나의 작업은 text editor로 I/O bound이면서 latency sensitive하다(자판에 입력하는데로 화면에 표시되는 걸 생각해보자). 다른 작업은 video encoder로 CPU bound하며, background job이다. 스케줄링의 목표는 text editor에서는 run 준비가 되었을 때(입력을 하여 이를 화면에 표시하려고 할 때), video encoder를 preempt하여 높은 반응성을 얻는게 좋고, video encoder는 가능한 CPU 캐시의 효과를 보기 위해 가능한 길게 실행해야 좋다.

fig 12-2

 결론적으로, 리눅스에서는 절대적인 timeslice가 없다. timeslice는 시스템의 load, 프로세스의 priority에 따라 달라진다.  이를 수식화해보자면 fig 12-2와 같다. sched_latency는 RR로 모든 프로세스를 실행하는데 걸리는 시간이라고 보면된다. 이는 모든 프로세스가 적어도 한번은 실행되어야 함을 보장해준다. 그리고 min_granularity는 일단 프로세스가 스케줄 되면 min_granualrity동안은 preempt되지 않아햐 한다는 뜻이다. 이는 너무 자주 switching이 발생하면 안되기 때문에 설정해 준 값이다.

  timeslice(TS)를 구하는 공식에서 P(period)를 곱하고 있는데 이는 n의 값에 따라 곱하는 P값이 달라진다. nr_latency는 위에서 말한 sched_latency와 min_granularity를 나눈 값이다. 즉 nr_latnecy는 sched_lantecy를 만족시키면서 min_granularity동안 preempt되지 않게끔 하는 n의 최댓값인 것이다.  그렇기 때문에 n이 nr_latency이상일 때는 'min_granularity*n'을 통하여 P값을 증가시켜줘야 한다.

fig 12-3

  fig 12-3와 같은 상황에서 프로세스들이 같은 priority('weight/runqueue's total weigth'는 1/n 형태가 된다)를 가지고 nr_running = 2라면, 각각의 작업에는 3ms의 timeslice가 할당되게 된다. 만약 nr_running이 7개라면 sched_nr_latency보다 크므로 각 작업은 timeslice 1ms(min_granularity)를 가지게 된다.

  그리고 CFS에서는 각 프로그램의 실제 CPU 사용 시간을 추적한다. 이를 통해 만약, 프로세스 C가 실행되고 있는데, P(C와 priortiy 동일)가 runnable 되었을 때, 만약 P가 C보다 CPU를 더 적게 사용했으면 P는 C를 preempt할 수 있다. 이를 위에 예시에 적용해보면, text editor와 video encoder에 각각 50%, 50%의 proportion을 할당했을 때, text editor는 대부분 사용자 입력을 기다리고 있고, video encoder는 preempt되기 전까지 계속 실행 중일 것이다. 이때 text editor가 입력을 받고 깨어났을 때, CFS는 video encoder보다 CPU를 덜 사용했으므로 text editor가 video encoder를 preempt한다.

fig 12-4

  그러므로 CFS로 인해 더 좋은 interactive performance(사용자 경험)과 background, CPU-bound performance를 얻을 수 있다.

Process selection in CFS

fig 12-5

  기존에는 프로세스들이 queue에서 대기하는 것으로 표현하였다. 하지만 이 방법은 priority등을 확인하기 위해 순회할 때 많은 시간이 소요된다. 리눅스에서는 적게 실행된 프로세스를 더 우선적으로 실행한다고 했다. 프로세스의 실행시간을 vruntime이라고 하면 스케줄러는 vruntime이 제일 작은 것을 선택해야 한다.

  리눅스에서는 이를 빠르게 찾아내기 위해 red-black tree(rbtree)를 사용한다. 이러한 balanced-tree 구조를 사용하여 큐보다 더 빠른 탐색시간을 얻을 수 있다. 일반 일차원 큐의 탐색 시간복잡도는 O(n)이 걸리지만 rbtree에서의 탐색 시간복잡도는 O(logn)이기 때문이다.

---

• Operating System Concepts, Avi Silberschatz et al.
• Operating Systems: Three Easy Pieces
  • Remzi H.Arpaci-Dusseau andAndreaC.Arpaci-Dusseau
  • Available(withseveraloptions)athttp://ostep.org