[운영체제 공룡책] 스레드 스케줄링, 다중 처리기 스케줄링, 실시간 CPU 스케줄링
Posted: Updated:
운영체제 스터디를 하며 ‘운영체제 공룡책’ 교재를 정리한 글입니다.
스레드 스케줄링
프로세스-경쟁-범위(process-contention scope, PCS)
스레드 라이브러리가 사용자 수준 스레드를 가용한 LWP(Light Weight Process)상에서 스케줄한다.
동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁한다.
전형적으로 가장 높은 우선순위의 실행 가능한 프로세스를 선택한다.
시스템-경쟁-범위(system-contention scope, SCS)
실제로 CPU상에서 실행하기 위해 운영체제가 LWP의 커널 스레드를 물리적인 CPU 코어로 스케줄해야 한다.
CPU상에 어느 커널 스레드를 스케줄할 것인지 정하기 위해 사용한다.
CPU에 대한 경쟁이 시스템 상의 모든 스레드 사이에서 일어나게 된다.
다중 처리기 스케줄링
여러 개의 CPU가 사용 가능할 때, 여러 스레드가 병렬로 실행될 수 있어 부하 공유(load sharing)가 가능해진다.
다중 처리기는 여러 개의 물리적 프로세서를 제공하는 시스템으로, 다중 코어 CPU, 다중 스레드 코어, NUMA 시스템, 이기종 다중 처리 등의 시스템 아키텍처에 사용할 수 있다.
비대칭 다중 처리(asymmetric multiprocessing)
마스터 서버(master server)라는 하나의 처리기가 모든 스케줄링 결정과 I/O 처리, 다른 시스템의 활동을 취급하게 한다.
다른 처리기들은 사용자 코드만을 수행한다.
하나의 코어만 시스템 자료구조에 접근하므로 간단하지만, 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다.
대칭 다중 처리(symmetric multi-processing, SMP)
다중 처리기를 지원하기 위한 표준 접근 방식으로, 각 프로세서가 스스로 스케줄링 할 수 있다.
각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택한다.
이때, 모든 스레드가 공통 준비 큐에 있는 방식과 각 프로세서가 자신만의 스레드 큐를 가질 수 있는 방식 중 하나를 택한다.
공통 준비 큐를 사용하는 경우
경쟁 조건이 생길 수 있어 두 개의 다른 프로세서가 동일한 스레드를 스케줄 하지 않도록 공통 준비 큐를 보호해야 한다.
이를 위해 락킹 기법을 사용할 수 있는데, 큐에 대한 모든 액세스에 락 소유권이 필요하므로 락킹의 경쟁이 매우 심해져 성능의 병목이 될 수 있다.
각 프로세서가 자신만의 스레드 큐를 가지는 경우
SMP를 지원하는 시스템에서 가장 일반적인 접근 방식으로 공유 실행 큐와 관련한 성능 문제를 겪지 않을 수 있다.
캐시 메모리를 보다 효율적으로 사용할 수 있다.
큐마다 부하의 양이 다를 수 있어 균형 알고리즘을 통해 모든 프로세서 간의 부하를 균등하게 만들 수 있다.
다중 코어 프로세서(multicore processor)
현대 컴퓨터 하드웨어는 동일한 물리적 칩 안에 여러 개의 처리 코어를 장착한다.
각 코어가 구조적인 상태를 유지하므로 운영체제 입장에서 개별적인 논리적 CPU로 보이게 된다.
메모리 스톨(memory stall)
프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 허비한다.
최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하여 발생한다.
캐시 미스(캐시 메모리에 없는 데이터를 액세스)로 인해 발생할 수도 있다.
칩 다중 스레딩(chip multi-threading, CMT)
하나의 코어에 2개 이상의 하드웨어 스레드를 할당한다.
메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환한다.
프로세서에 4개의 컴퓨팅 코어가 있다면 각 코어에 2개의 하드웨어 스레드가 있어 운영체제 관점에서 8개의 논리적 CPU가 존재하게 된다.
하이퍼-스레딩(동시 다중 스레딩, simultaneous multithreading, SMT)
Intel 프로세서에서 단일 하드웨어 코어에 여러 하드웨어 스레드를 할당하는 방식이다.
i7과 같은 최신 Intel 프로세서는 코어당 2개의 스레드를 지원한다.
반면 Oracle Sparc M7 프로세서는 코어당 8개의 스레드와 프로세서당 8개의 코어를 지원하여 운영체제에 64개의 논리적 CPU를 제공한다.
거친(coarse-grained) 다중 스레딩
스레드가 메모리 스톨 등 긴 지연시간을 가진 이벤트가 발생할 때까지 한 코어에서 수행된다.
지연시간이 긴 이벤트에 의한 지연이 발생하면 코어가 다른 스레드를 실행하게 된다.
이때, 사용되던 프로세스 코어에서 다른 스레드를 실행해야 하므로 명령어 파이프라인을 정리하는 스레드 간 교환 비용이 많이 든다.
세밀한(교차, fine-grained) 다중 스레딩
구조적으로 스레드 교환을 위한 회로를 포함하여 스레드 간 교환 비용이 적어진다.
거친 다중 스레딩보다 세밀한 정밀도의 시점에서 스레드 교환이 일어난다.
2단계 스케줄링
첫 번째 단계에서 운영체제가 각 하드웨어 스레드에서 실행할 소프트웨어 스레드를 선택할 때 필요한 스케줄링을 결정한다.
여기서는 임의의 스케줄링 알고리즘을 선택할 수 있다.
두 번째 단계에서는 각 코어가 실행할 하드웨어 스레드를 결정하는 방법을 정한다.
간단한 라운드 로빈 알고리즘을 사용해 처리 코어에 하드웨어 스레드를 스케줄링할 수 있다.
혹은 각 하드웨어 스레드에 0부터 7까지의 동적 긴급도(urgency value)를 배정해 스레드 교환을 촉발할 수 있는 이벤트가 발생하면 두 스레드의 긴급도를 비교해 높은 긴급도를 가진 스레드를 선택한다.
부하 균등화(load balancing)
자신만의 준비 큐를 가지는 SMP 시스템의 모든 처리기 사이에 부하가 고르게 배분되도록 한다.
push, pull 방식이 있으며 병렬적으로 구현될 수 있다.
push 이주(migration) 방식
특정 태스크가 주기적으로 각 처리기의 부하를 검사해 불균형 상태라면 덜 바쁜 처리기로 스레드를 이동(push)시킨다.
puul 이주 방식
쉬고 있는 처리기가 바쁜 처리기를 기다리고 있는 프로세스를 pull한다.
처리기 선호도(processor affinity)
스레드가 특정 처리기에서 실행 중일 때 가장 최근에 접근된 데이터가 그 처리기의 캐시를 채운다.
스레드가 다른 처리기로 이주한다면 캐시 메모리 내용을 무효화하고 이동한 처리기의 캐시를 채워야 한다.
캐시 무효화 및 다시 채우는 비용이 많이 들어가므로, 대부분은 한 프로세서에서 다른 프로세서로 이주시키지 않고 같은 프로세서에서 계속 실행히시켜 warm cache를 이용하려고 한다.
약한 선호도(soft affinity)
동일한 처리기에서 프로세스를 시키려고 노력하지만, 보장하지는 않을 때 약한 선호도를 가진다.
프로세스를 특정 처리기에서 실행하도록 하는 전략은 가지지만, 프로세스가 처리기 사이에 이주할 수 있다.
강한 선호도(hard affinity)
프로세스가 자신이 실행될 처리기 집합을 명시할 수 있다.
많은 시스템이 약한 선호도, 강한 선호도를 모두 지원한다.
NUMA (non-uniform memory access)
각 CPU가 메모리의 일부를 자신의 지역 메모리로 가지고 있고, 메모리의 접근하는 시간이 CPU와 메모리의 상대적인 위치에 따라 달라지는 설계 방법이다.
모든 CPU가 하나의 물리적 주소 공간을 공유하지만, 자신의 로컬 메모리에 더 빠르게 액세스할 수 있다.
동일한 프로세서에서 스레드를 계속 실행하면 캐시 메모리를 사용할 수 있어 장점이지만, 스레드를 다른 프로세서로 이동시켜 부하를 조정할 때 이러한 이점이 상쇄될 수 있다.
따라서 부하 균등화와 메모리 액세스 시간 최소화 사이에 균형을 맞춰야 한다.
이기종 다중 처리(heterogeneous multiprocessing, HMP)
모바일 시스템에서 전력 소비를 유휴 수준으로 조정하는 기능을 포함해 클록 속도 및 전력 관리 측면에서 차이가 나는 코어를 사용한 시스템이다.
작업의 특정 요구에 따라 특정 코어에 작업을 할당하여 전력 소비를 잘 관리하는 것이 목적이다.
big.LITTLE
ARM 프로세서에서 사용하는 방식으로, 고성능 big 코어가 에너지 효율적인 LITTLE 코어와 결합되었다.
big 코어는 많은 에너지를 소비하므로 짧은 시간동안 사용해야 하고, LITTLE 코어는 적은 에너지를 사용하므로 오랫동안 사용할 수 있다.
따라서 백그라운드 작업은 little 코어에 할당해 배터리 충전을 보존할 수 있다.
또한, 더 많은 처리 능력이 필요하고 짧은 기간동안 실행될 수 있는 대화형 응용 프로그램을 big 코어에 할당할 수 있다.
실시간 CPU 스케줄링
연성(soft) 실시간 시스템
중요한 실시간 프로세스가 스케줄 되는 시점에 아무런 보장을 하지 않는다.
중요 프로세스가 중요하지 않은 프로세스에 비해 우선권을 가진다는 것만 보장한다.
경성(hard) 실시간 시스템
태스크가 반드시 마감시간까지 서비스를 받아야 하며, 마감시간이 지난 뒤 서비스를 받으면 전혀 받지 않는 것과 동일해진다.
지연시간 최소화(minimizing latency)
이벤트 지연시간은 이벤트가 발생해서 그에 맞는 서비스가 수행될 때까지의 시간을 말한다.
일반적으로 이벤트가 다르면 그에 따른 지연 시간이 다르며, 실시간 시스템의 성능을 좌우하는 지연 시간에는 인터럽트 지연시간, 디스패치 지연시간이 있다.
인터럽트 지연시간은 CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기까지의 시간이다.
인터럽트가 발생했을 때 운영체제가 수행 중인 명령어를 완수하고 발생한 인터럽트의 종류를 결정하여, 해당하는 인터럽트 서비스 루틴(ISR)을 사용해 현재 수행 중인 프로세스의 상태를 저장하는 작업 등이 포함된다.
경성 실시간 시스템에서 인터럽트 지연시간을 최소화해야하며, 이는 정해진 시간보다 작아야 한다.
커널 데이터 구조체를 갱신하는 동안 인터럽트는 불능 상태가 되므로 이 시간도 매우 짧게 해야 한다.
디스패치 지연시간은 스케줄링 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 시작하는 데까지 걸리는 시간이다.
이는 선점형 커널을 통해 최소화시킬 수 있다.
디스패치 지연시간에서는 커널에서 동작하는 프로세스에 대한 선점, 낮은 우선순위 프로세스 자원이 높은 우선순위의 프로세스가 필요로 하는 자원을 방출하는 두 가지 충돌 단계가 있다.
충돌 단계 이후 디스패치 단계에서 우선순위가 높은 프로세스를 사용 가능한 CPU에 스케줄하게 된다.
우선순위 기반 스케줄링(priority-based scheduling)
실시간 운영체제의 스케줄러는 선점을 이용한 우선순위 기반의 알고리즘을 지원해야만 한다.
단순히 선점 및 우선순위 기반 스케줄러를 제공한다면 연성 실시간 기능을 제공하는 것이다.
경성 실시간 시스템을 위해서는 실시간 태스크가 마감시간 내에 확실히 수행되는 것을 보장해야만 한다.
프로세스들은 주기적이고, 일정한 간격으로 CPU가 필요하다.
각 주기 프로세스들은 CPU 사용권을 얻었을 때마다 고정된 수행시간 $t$, 마감시간 $d$, 주기 $p$가 정해져있다.
이 세 가지의 관계를 이용해 마감시간과 실행 빈도에 따라 우선순위를 정한다.
승인 제어(admission-control) 알고리즘을 이용해 마감시간 내에 완수할 수 있는 프로세스는 실행을 허용하고, 그렇지 않으면 거절한다.
Rate-Monotonic 스케줄링
선점 가능한 정적 우선순위 정책을 이용해 주기 태스크들을 스케줄한다.
낮은 우선순위 프로세스가 실행 중일 때, 높은 우선순위의 프로세스가 실행 준비가 되면, 높은 우선순위의 프로세스가 낮은 우선순위의 프로세스를 선점한다.
우선순위는 시스템에 진입할 때, 주기가 짧은 태스크에는 높은 우선순위를, 주기가 길면 낮은 우선순위를 배정한다.
CPU를 더 자주 필요로하는 태스크에 높은 우선순위를 주는 원리이다.
Earliest-Deadline-First(EDF) 스케줄링
마감시간에 따라서 우선순위를 동적으로 부여한다.
마감시간이 빠를수록 우선순위가 높아지고, 늦을수록 낮아진다.
프로세스가 실행 가능하게 되면 자신의 마감시간을 시스템에 알려야 한다.
새로 실행 가능하게 된 프로세스의 마감시간에 맞춰 우선순위를 다시 조정한다.
프로세스들이 주기적일 필요도 없으며, CPU 할당 시간도 상수로 정할 필요가 없다.
하지만 프로세스가 실행 가능해질 때 자신의 마감시간을 스케줄러에게 알려주어야 한다.
일정 비율의 몫(proportional share) 스케줄러
모든 응용들에 T개의 시간 몫을 할당하는 방식이다.
특정 응용이 $N$개의 시간 몫을 할당받으면 그 응용은 모든 프로세스의 시간 중 $N/T$ 시간을 할당받게 된다.
응용이 시간 몫을 할당받는 것을 보장하는 승인 제어 정책과 함께 동작해야 한다.
승인 제어 정책은 사용 가능한 충분한 몫이 존재할 때, 그 범위 내의 몫을 요구하는 클라이언트들에게만 실행을 허락한다.
$T=100$인 시간 몫이 있을 때, $A$가 50 몫, $B$가 15 몫, $C$가 20 몫을 할당받았다면, $A$가 50%, B가 15%, C가 20%를 할당받는다.
이 상황에서 새로운 프로세스 $D$가 30 몫을 요구하면 승인 컨트롤러가 $D$의 진입을 거부한다.
댓글남기기