Week-03 📚

8.0 스케줄링 : 멀티 레벨 피드백 큐

• MLFQ가 해결하려고 하는 기본적인 문제는 두 가지 이다.

1. 짧은 작업을 먼저 실행시켜 반환 시간을 최적화 하는 것.
2. 대화형 사용자에게 빠른 시스템이라는 느낌을 주기 위해서 응답 시간을 최적화 하는 것.

• 이 과정에서 해결해야 하는 가장 큰 문제는 다음과 같다. “우리가 프로세스에 대한 정보가 없다면 이러한 스케줄러를 어떻게 구현할 수 있을까?”

• 위의 문제는 이 장의 핵심 질문으로 이어진다.

8.1 MLFQ: 기본 규칙

• MLFQ는 여러개의 큐로 구성되며, 각각 다른 우선순위를 가진다.

• 실행 준비가 된 프로세스는 이 중 하나의 큐에 존재한다.

• MLFQ는 프로세스 실행을 결정할 때 우선순위를 사용한다.

• 물론 하나의 큐에 여러개의 작업이 들어갈 수 있지만, 이 경우 RR을 사용한다.

• 여기까지는 쉬운데 어려운건 우선순위를 어떻게 정할 것인가이다.

• MLFQ는 각 작업에 고정된 우선순위를 부여하는 것이 아니라, 작업의 행동에 따라 우선순위를 동적으로 조절한다.

• 예를들어 대화형 프로세스처럼 빠른 반응이 필요한 프로그램은 우선순위를 높게 설정하고, 한 작업이 긴 시간동안 CPU를 사용하면 우선순위를 낮추는 방식이다.

• MLFQ의 두 가지 규칙은 다음과 같다.

  1. 규칙 1 : Priority A > Priority B 이면, A의 프로세스는 B의 프로세스보다 먼저 실행된다.
  2. 규칙 2 : Priority A = Priority B 이면, A와 B는 RR을 사용하여 실행된다.

• 당장은 위의 그림과 같이 작업이 구성된다고 했을 때, A B가 RR으로 처리되면 CD는 실행되지도 않는 문제가 발생한다.

• 아래의 목차에서 작업 수선순위자체가 변경되는 방법에 대해 알아보자.

8.2 MLFQ: 우선순위의 변경

• 첫번째 변경은 다음과 같은데 주로 대화형 프로세스와 cpu bound 프로세스를 구분하는 방법이다.

  1. 대화형 프로세스는 짧은 시간동안 CPU를 사용하고, 대기시간이 길다.
  2. CPU bound 프로세스는 긴 시간동안 CPU를 사용하고, 대기시간이 짧다.

• MLFQ에 추가된 규칙

• 규칙 3 : 작업이 시스템에 들어오면, 우선순위는 가장 높은 큐에 할당된다.

• 규칙 4-a : 작업이 타임슬라이스를 전부 사용하면, 우선순위는 낮은 큐로 이동된다.

• 규칙 4-b : 타음 슬라이스를 사용하지 않고 CPU를 양도하면, 우선순위는 유지된다.

• 이 규칙의 의의는 일단 전부 짧은 시간을 사용하는 프로세스라 가장하고, 실제로 실행시간이 짧다면 위에 두거나 우선순위가 하락하는 동안 끝내는 것이고,

• 실행시간이 길다면 우선순위가 하락하면서 아래로 내려가게 된다.

• 대화형 프로그램에서는 굳이 살피지 않아도 잘 동작함을 알 수 있다.

현재 MLFQ의 문제점

• 일견 완벽해 보이지만, MLFQ에도 문제점이 존재한다.

1. 기아 상태(starvation)가 발생할 수 있다. (예를 들어 대화형 프로세스가 너무 많은 경우)
2. 지금 상태를 알 수 있다면, CPU를 독점 하는 프로세스를 만들 수 있다.
3. 프로그램의 구분이 바뀔 수 있다.

8.3 우선순위의 상향 조정

• 당연히 기본적인 아이디어는 우선순위를 상향 조정하는 것이다.

• 이를 위해 다음과 같은 규칙을 추가한다.

• 규칙 5 : 일정 기간 S가 지나면, 모든 프로세스의 우선순위를 최상위 큐로 이동시킨다.

• 이 규칙을 통해 기아 상태와 프로그램의 구분이 바뀔 수 있는 문제를 해결할 수 있다.

• 물론 여기에도 많은 고민이 남아있는데, 바로 S의 값을 어떻게 설정할 것인가이다.

• S의 값이 너무 작으면, 대화형 작업이 적절한 시간동안 실행되지 않을 수 있고, 너무 크면 기아 상태가 발생할 수 있다.

8.4 우선순위의 하향 조정

• 나머지 문제(스케줄러를 독점하는 이슈)도 하나의 규칙으로 해결할 수 있다.

• 규칙 6 : 우선 순위 단계에서 시간 할당량을 사용하면, 우선 순위를 하향 조정한다.

8.5 MLFQ조정과 다른 이슈들

• MLFQ의 아이디어는 위와 같지만, 아직 실제 구현에는 많은 문제가 남아있다.

• 타임슬라이스의 길이를 어떻게 설정할 것인가?

• S의 값을 어떻게 설정할 것인가?

9.0 스케줄링 : 비례 배분

• 이번 장에서는 스케줄러의 또 다른 방법인 비례 배분에 대해 알아본다.

• 비례 배분의 목표는 간단한데, 반환시간이나 응답시간을 최적화 하는 대신 스케줄러가 각 프로세스에 CPU 시간을 공평하게 분배하는 것이다.

• 가장 좋은 예시는 Waldspurger와 Weihl의 연구인 lottery scheduling이다. (간단하게 말하면, 각 프로세스에 티켓을 부여하고, 스케줄러가 랜덤하게 티켓을 뽑아서 실행하는 방식 더 중요한 프로세스에 더 많은 티켓을 준다)

9.1 기본 개념 : 추첨권이 당신의 지분이다

• 추첨권이라는 기본적인 개념이 추천 스케줄링의 근간을 이룬다.

• 기본적인 아이디어는 위와 같고, 장점은 무작위성이다.

무작위성이 장점인 이유

1. 기본적으로 기존의 문제를 해결한다 (LRU의 예시를 생각해보자)
2. 가볍다 (관리해야 할 정보가 거의 없다)
3. 빠르다 (로직이 덜 붙어 난수생성 시간정도에 불과하다)

9.2 추첨 기법

• 추첨권을 다루는 다양한 기법이 있는데, 그 중 가장 먼저 고려할 것 은 추첨권 화폐이다.

• 이 개념은 사용자가 추첨권을 자신의 화폐 가치로 추첨권을 자유롭게 할당 할 수 있게 한다. (시스템은 자동적으로 화폐 가치를 변환한다)

• 이건 다른 사용자와 다른 프로세스가 할당한 추첨권의 가치를 비교할 수 있게 해준다.

• 그리고 추첨권 양도라는 개념도 있는데, 이는 다른 프로세스에게 추첨권을 양도할 수 있게 해준다.

• 이를 통해 사용자는 자신의 추첨권을 다른 프로세스에게 양도할 수 있고, 이는 다른 프로세스가 더 많은 추첨권을 가지게 해준다.

• 마지막으로 추첨권 팽창라는 개념도 있는데, 이는 시스템이 특정 이벤트가 발생할 때 추첨권을 증가시키는 것이다.

9.3 구현

// counter : 당첨자를 발견했는지 확인하는 변수
int counter = 0;

// winner : 0부터 총 추첨권의 수까지 랜덤하게 추첨된 당첨자
int winner = getRandom(0, total_tickets);

// 추첨권을 가진 프로세스를 찾는다.
node_t *current = head;

while (current) {
  counter += current->tickets;
  if (counter > winner) {
    // 당첨자를 발견했으므로 프로세스를 실행한다.
    run(current->process);
    break;
  }
  current = current->next;
}

• 위의 코드는 추첨권을 가진 프로세스를 찾아 실행하는 코드이다.

9.4 추첨권 시스템 예제

• 기본적으로 불공정 지표 U를 정의한다.(U = 1 - (첫 작업 종료 시간 / 두 번째 작업 종료 시간))

• 기본적으로는 1(가장 공정함)으로 수렴하긴 하지만 랜덤의 특성상 초반에는 불공정함이 발생할 수 있다.

• 다만 추첨권 시스템에서 가장 큰 문제는 추첨권을 어떻게 할당할 것인가이다.

• 이는 추첨권을 어떻게 할당할 것인가에 따라 성능이 달라질 수 있고 아직 미해결 상태이다.

9.6 결정론적 스케줄링

• 결정론적 스케줄링은 랜덤성을 제거하고, 스케줄링을 결정론적으로 만드는 것이다.

• 대표적으로 보폭 스케줄링(stride scheduling)이 있다.

• 보폭 스케줄링은 각 프로세스에 보폭을 할당하고, 스케줄러는 가장 작은 보폭을 가진 프로세스를 실행한다.

• 이를 통해 랜덤성을 제거하고, 스케줄링을 결정론적으로 만들 수 있다.

curr = remove_min(queue);
schedule(curr);
curr->pass += curr->stride;
insert(queue, curr);

• 처음부터 U가 1에 수렴하는 것을 볼 수 있다.

• 그렇다면 왜 결정론적 스케줄링을 사용하지 않을까?

• 이유는 단순한데, 새로운 프로세스가 들어오면, 스케줄러는 새로운 보폭을 할당해야 하는데, 이것이 결정론적 스케줄링의 단점이다.(랜덤 추첨권 방식에서 훨씬 쉽다)

9.7 리눅스 CFS(Completely Fair Scheduler)

• 리눅스는 기존과 다른 방식으로 공정 배분 스케줄링을 구현한다.

• 이 스케줄러의 장점은 효율성과 확장성이다.

• 효율성을 위해 CFS는 최적의 내부 설계와 자료구조를 사용한다.

• 일단 기본적으로 virtual runtime이라는 counting 기반 방식을 사용한다.

• 프로세스 실행시 virtual runtime이 증가하고, 스케줄러는 가장 작은 virtual runtime을 가진 프로세스를 실행한다.

• 이 역시 아이디어는 간단하지만, 스케줄러가 어느 시점에 멈출지를 결정하는 것이 중요하다.

• 너무 자주 스케줄러를 호출하면 오버헤드가 발생하고, 너무 늦게 호출하면 공정성이 떨어진다.

• 이를 위해 다양한 통제 변수를 사용한다.

• 첫 번째 변수로 sced_latency가 있다. 이 변수는 스케줄러가 얼마나 자주 호출되는지를 결정한다(보통 48ms).

• 예를 들어 네개의 프로세스가 있다면, CFS는 sced_latency를 1/4로 나누고 프로세스당 타임슬라이스를 해당 값으로 설정한다.

• 문제는 너무 많은 프로세스가 있다면 너무 많은 context switching이 발생할 수 있다.

• 이를 해결하기 위해 min_granularity라는 변수를 사용한다. (보통 최솟값은 6ms)

• 예를들어 10개의 프로세스가 있다면, 원래는 sced_latency에 따라 4.8ms로 나누어진다.

• 하지만 min_granularity가 6ms이므로, 6ms로 설정된다. 스케줄링의 효울성은 이렇게 보호된다.

• 이러한 방식으로 CFS는 공정성과 효율성을 모두 확보한다.

• 추가적인 기능으로 가중치(Niceness)를 사용한다. 이는 프로세스의 우선순위를 보정한다.

• 수식은 다음과 같다. time_slice = (weight_of_task / weight_of_all_tasks) * sced_latency (가중치 표는 -20 ~ 19까지에 해당하는 값을 대응 시킨다)

• 이런 수식을 도입하면 가중치에 따라서 프로세스의 타임슬라이스(재조정 시간)이 달라지게 된다.

• vruntime도 가중치에 따라서 고도화 되어있다.

• 고도화 수식은 다음과 같다. vruntime = vruntime + (weight_of_all_tasks / weight_of_task) * time_slice (가중치가 높을수록 vruntime이 느리게 증가한다)

RedBlack Tree의 활용

• CFS는 효율적인 알고리즘이 꼭 필요하다. (다음 실행할 프로세스를 빠르게 찾아야 하기 때문)

• 예를들어 대기중인 프로세스를 LinkedList로 관려하면, 검색에 너무 많은 시간이 소요된다.

• 커질수록 O(n)의 시간복잡도를 가지기 때문인데, 아주 작은 타임슬라이스 시간 안에 수천개의 프로세스가 대기할 수 있는데, 이는 매우 큰 문제이다.

I/O와 잠자는 프로세스 다루기

• CFS는 I/O와 잠자는 프로세스를 어떻게 다루는지에 대한 문제도 있다.

• 이를 위해 CFS는 vruntime을 사용한다.

• 정확히는 잠자는 프로세스가 깨어났을 때 vruntime을 업데이트한다(트리에서 찾을 수 있는 가장 작은 vruntime을 찾아서 업데이트한다)

10.0 멀티프로세서 스케줄링

• 이번 장에서는 멀티프로세서 스케줄링에 대해 알아본다.

• 원래는 병행성을 다루고 보는 것이 중요하지만, 이번 장에서는 멀티프로세서 스케줄링에 대해 알아본다.

• 다만 기존의 프로그램들(하나의 코어만 사용하도록 설계된)을 멀티프로세서에서 실행시키는 것에 대해서 알아본다.

10.1 배경: 멀티프로세서 구조

• 기본적으로 멀티 프로세서 하드웨어는 두가지 문제를 야기한다.

  1. 다수의 프로세서 간의 데이터 공유 문제
  2. 하드웨어 캐시의 사용방식 문제

• 캐시는 지영성에 기반한다. 지역성에는 시간 지역성과 공간 지역성이 있다.

  • 시간 지역성 : 최근에 접근한 데이터는 다시 접근할 확률이 높다.
  • 공간 지역성 : 최근에 접근한 데이터와 인접한 데이터에 다시 접근할 확률이 높다.

• 이러한 특징에서, 캐시 일관성 문제가 발생한다.

• 캐시 일관성 문제를 요약하면, 캐시된 데이터를 다른 프로세서가 변경했을 때, 어떻게 처리할 것인가이다.

• 기본적인 해결책은 하드웨어에서 제공된다, 하드웨어는 메모리 주소를 계속 감시하고, 항상 올바른 순서로 처리되도록 시스템을 관리한다.

• 여러개의 프로세서가 하나의 메모리를 갱실할때는 항상 공유도되록한다.

• 버스 기반 시스템에서는 버스 스누핑이라는 기술을 사용한다. (캐시가 자신과 메모리를 연경하는 버스의 통신 내용을 감시하는 것)

10.2 동기화를 잊지 마시오

• 멀티프로세서에서는 동기화가 더욱 중요하다.

• 이건 병행성에서 다룰 것 같고, 간단히 요약하면, 동기화 문제가 발생하는 경우를 간단히 설명하는 장이다.

• lock이 대안이지만, lock을 사용하면 성능이 떨어지는 trade-off가 발생한다.

10.3 캐시 친화성

• 캐시 친화성도 문제를 야기한다 (CPU가 번갈아가며 캐시에 데이터를 올리면서 오는 지연과 낭비)

• 멀티프로세서는 이런점을 고려해서 프로세서를 스케줄링 해야 한다.

결론적으로 사실 병행성에서 나와야 하는 주제이고, 앞의 설명이 부족해서 단번에 이해가 어렵고 혼동스러울 수 있다. 멀티 프로세서 환경에서 스케줄링을 하기 위해서 고려해야할 것들에 대한 언급정도로 이해하면 될 것 같다.

10.4 단일 큐 스케줄링

• 결국 다시 스케줄링으로 돌아와서 이야기해보면, 멀티프로세서 스케줄링에서 가장 간단한 방법은 단일 큐 스케줄링이다.

• 단일 큐 멀티프로세서 스케줄링(Single Queue Multiprocessor Scheduling)은 모든 프로세서가 하나의 큐를 공유하고, 스케줄러는 가장 높은 우선순위를 가진 프로세스를 실행한다.

• 간단히 말하면, 큐에 넣고 비어있는 프로세서에게 할당하는 방식이다. (작업이 두개고 프로세서가 두개면, 두개의 프로세서에게 각각 할당하는 방식)

• 이 방식은 대부분의 단점을 무시하기도 하고, 간단하지만, 확장성이 결여되어있다.

• 이 방식은 락을 사용하는데(실행시킬 다른 프로세서를 찾을 때) 이는 성능을 떨어뜨릴 수 있다.

• 또한 아무런 보정이 없다면, 캐시 친화성이 떨어질 수 있다.

• 이를 해결하기 위해서 같은 프로세서가 같은 프로세스를 실행하도록 유도해서 오버헤드를 줄이는 방법도 있다.

• 이같은 방식은 좋지만, 구현이 어렵다는 단점이 있다.

10.5 멀티 큐 스케줄링

• 멀티 큐 스케줄링(Multi Queue Scheduling)은 단일 큐 스케줄링의 단점을 보완한 방식이다.

• 이것도 개념자체는 어렵지 않아서 간단하게 요약하면, 각 프로세서에 큐를 할당하고, 각 큐에 프로세스를 할당하는 방식이다.

• A,B,C,D 네가지 작업이 있다면, A,B는 큐1에, C,D는 큐2에 할당하는 방식이다.

• 기본적으로 캐시친화적이고, 큐로 인한 락을 줄일 수 있다.

• 단 이 방식도 문제가 있는데, 워크로드가 불균형하다면, 한쪽 큐가 너무 많은 작업을 처리하게 된다.

• 이걸 해결하기 위한 방법은 이주 (migration)이다.

• 이주는 프로세스를 다른 큐로 이동시키는 것이고 이를 통해 불균형을 해결할 수 있다.

개인적으로 모든 스케줄링 방법의 한계는 작업을 정확히 예측 할 수 없다는 것에 있다고 생각하는데, 그러한 정보의 단절 속에서 사전적인 해결책을 찾는 것이 어렵다고 생각한다. 이주는 그러한 것들을 잘 극복한 사례라고 생각한다.