최신 운영체제에서는 실질적으로 프로세스가 아닌 커널 수준 스레드를 스케줄한다.
그러나 프로세스 스케줄링과 스레드 스케줄링 용어는 상호교환적으로 사용된다.
1. Basic Concepts
다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 데 있다.
어떤 프로세스가 대기해야 할 경우,
운영체제는 CPU를 회수해 다른 프로세스에게 할당한다.
이러한 스케줄링은 운영체제의 기본이다.
거의 모든 자원은 스케줄 된다.
1.1 CPU-I/O Burst Cycle
프로세스 실행은 CPU 실행과 I/O 대기의 cycle로 구성된다.
프로세스 실행은 CPU burst로 시작된다.
뒤이어 I/O burst가 발생하고, 이 두 가지가 반복된다.
일반적으로 짧은 cpu burst가 잦고,
긴 cpu burst는 적다.
1.2 CPU Scheduler
cpu가 유휴 상태가 될 때마다,
운영체제는 CPU 스케줄러에 의해 레디큐에서 프로세스를 하나 선택해 cpu를 할당한다.
레디큐는 FIFO, 우선순위 큐, 트리, 단순 연결 리스트 등으로 구현될 수 있다.
큐에 있는 레코드들은 일반적으로 PCB다.
1.3 선점 및 비선점 스케줄링
cpu 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있다.
- 한 프로세스가 실행 상태에서 대기 상태로 전환될 때(ex. I/O 요청이나, 자식을 기다리기 위해 wait()를 호출한 경우)
- 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때(ex. 인터럽트 발생)
- 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때(ex. I/O의 종료 시)
- 프로세스가 종료할 때
1, 4번째 상황의 경우 스케줄링 면에서 선택의 여지가 없다.
그러나 2, 3번째 상황에선 선택의 여지가 있다.
1, 4번째 상황에서의 스케줄링을, 비선점 혹은 협조적(cooperative)라고 한다.
비선점에선 cpu가 한 프로세스에 할당되면,
프로세스가 종료되거나 대기 상태로 전환해 cpu를 방출할 때까지 점유한다.
하지만 거의 모든 최신 운영체제들은 선점 스케줄링 알고리즘을 사용한다.
선점 스케줄링은 공유 데이터의 경쟁 상태를 초래할 수 있다.
선점은 또한 운영체제 커널 설계에 영향을 준다.
중요한 커널 자료 변경과 같은 시스템 콜을 처리할 동안 프로세스가 선점되면 문제가 발생할 수 있다.
따라서 공유 커널 데이터 구조에 액세스할 때는 mutex 락과 같은 기법이 필요하다.
인터럽트에 의해서 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 한다.
이러한 코드 부분은 다수의 프로세스가 접근할 수 없도록
진입할 때 인터럽트를 불능화하고, 빠져나올 때 다시 가능화해야한다.
이러한 부분은 아주 적은 수의 명령어들만 포함해야 한다.
1.4 Dispatcher
디스패처는 cpu코어의 제어를 cpu 스케줄러가 선택한 프로세스에게 주는 모듈로
다음과 같은 작업을 포함한다.
- 한 프로세스에서 다른 프로세스로 문맥 교환
- 유저 모드로 전환
- 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 jump
디스패처는 모든 프로세스의 문맥교환 시 호출되므로, 가능한 한 최고로 빨라야 한다.
디스패처가 프로세스를 정지하고 다른 프로세스를 시작하는데까지를 dispatch latency라고 한다.
- dispatch latency
2. 스케줄링 기준
특정 상황에서 알고리즘을 선택하기 위한 여러 기준이 제시되었다.
기준은 다음을 포함한다.
- CPU 이용률(utilization)
- 처리량(throughput) : 단위 시간당 완료된 프로세스의 개수
- 총처리 시간(turnaround time) : 특정 프로세스가 완료될 때까지의 총 시간
- waiting time : 프로세스가 레디큐에서 대기한 시간
- response time : 요청 후 응답(이 시작되는)까지의 시간
3. Scheduling Algorithms
cpu 스케줄링은 레디 큐에 있는 어느 프로세르에 cpu 코어를 할당할 것인지를 결정한다.
설명할 때는 코어가 하나라고 가정하고 설명한다.
3.1 FCFS Scheduling
cpu를 먼저 요청하는 프로세스가 cpu를 할당받는 비선점형 알고리즘.
FIFO 큐로 쉽게 구현할 수 있다.
하나의 긴 프로세스가 끝나기를 기다리는 convoy effect가 발생할 수 있다.
3.2 SJF Scheduling
이 스케줄링은 프로세스의 전체 길이기 아닌
다음 cpu 버스트의 길이에 의해 스케줄링 되기 때문에,
shortest-next-CPU-burst라는 용어가 더 적합하다.
실제 다음 cpu burst시간을 알 순 없으므로
구현할 수 없는 이상적인 형태다.
이와 근사하게 구현하기 위해
이전 cpu 버스트들의 길이를 지수 평균하여 다음을 예측한다.
SJF는 선점 혹은 비선점형일 수 있다.
선점형 SJF는 Shortest remaining time first)로 불리기도 한다.
3.3 Round-Robin Scheduling
time slice(일반적으로 10~100 밀리 초)를 정해 원형 큐로 동작한다.
한번의 시간 할당량 이후 인터럽터를 걸도록 timer를 설정해 프로세스를 dispatch한다.
시간 할당량을 얼마로 설정하는지가 성능에 크게 영향을 끼친다.
경험적으로 cpu 버스트의 80%는 시간할당량보다 짧아야 한다.
3.4 Priority Scheduling
우선순위 스케줄링은 선점 혹은 비선점형이 될 수 있다.
우선순위 스케줄링의 주요 문제는 비선점에서의 indefinite blocking(무기한 봉쇄)와 선점형에서의 starvation이 있다.
낮은 우선순위의 프로세스들은 무한히 대기하는 경우가 발생한다.
무기한봉쇄 대한 해결책 중 하나로 aging기법이 있다.
다른 옵션으로는 라운드 로빈과 결합하는 방식이다.
3.5 Multilevel Queue Scheduling
큐에서 우선순위가 가장 높은 프로세스를 찾기 위해 O(n)이 필요할 수 있다.
실제로 우선순위마다 별도의 큐를 갖는 것이 더 쉬운 때도 있으며
우선순위 스케줄링은 우선순위가 가장 높은 큐에서 프로세스를 스케줄 한다.
- 우선순위마다 별도의 큐
우선순위가 아닌 프로세스 유형에 따라 다단계 큐 스케줄링을 사용할 수도 있다.
예를 들어, 흔히 foreground 프로세스와 background 프로세스를 구분한다.
이 두 가지 유형의 프로세스는 응답 시간 요구 사항이 달라
스케줄링 요구 사항이 다를 수 있다.
각 유형에 따라 별도의 큐 및 별도의 자체 스케줄링을 가질 수도 있다.
추가로, 큐와 큐 사이에도 스케줄링이 필요하며
일반적으로 고정 우선순위의 선점형 스케줄링으로 구현된다.
또 다른 방법으로
각 큐마다 cpu 시간을 분배해서 관리하는 방법도 있다. (각 큐마다 스케줄링은 다를 수 있다.)
3.6 Multilevel Feedback Queue Scheduling
다단계 큐는 일반적으로 프로세스들이 영구적으로 하나의 큐에 할당된다.
대조적으로 다단계 피드백 큐는 프로세스가 큐들 사이를 이동할 수 있다.
예를 들어, 어떤 프로세스가 cpu를 너무 오래 사용하면
낮은 우선순위의 큐로 이동될 수 있다. (반대도 가능)
이러한 방식은 starvation을 예방한다.
일반적으로, 다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의된다.
- 큐의 개수
- 각 큐를 위한 스케줄링 알고리즘
- 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
- 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
- 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법
다단계 피드백 큐는 가장 일반적인 알고리즘으로
특정 시스템에 부합하도록 구성이 가능하다.
하지만 매개변수 값을 선정하는 특정 방법이 필요해 가장 복잡하다.
4. Thread Scheduling
대부분 최신 운영체제에서 스케줄 되는 대상은
프로세스가 아닌 커널 수준 스레드이다.
사용자 수준 스레드는 스레드 라이브러리에 의해 관리되고
커널은 그들의 존재를 알지 못한다.
하지만 실제 CPU에서 실행되려면 LWP를 통해 커널 수준 스레드에 매핑되어야 한다.
4.1 Contention Scope(경쟁 범위)
유저 스레드와 커널 스레드의 차이 중 하나는
그들이 어떻게 스케줄 되느냐에 있다.
유저 스레드는 동일한 프로세스에 속한 스레드 사이에서 cpu를 경쟁하기 때문에
PCS(process-contention scope)로 알려져 있다.
실제로 스레드가 cpu상에서 실행되기 위해서는 LWP의 커널 스레드를
cpu 코어로 스케줄하는 것을 필요로 한다.
cpu상에 어느 커널 스레드를 스케줄 할지 결정하기 위해 SCS(system-contention scope)를 사용한다.
SCS에서 cpu에 대한 경쟁은 시스템 상의 모든 스레드 사이에서 일어난다.
전형적으로 PCS는 우선순위에 따라 행해진다.
사용자 수준의 스레드는 프로그래머에 의해 우선순위가 결정된다.
4.2 Pthread Scheduling
스레드를 생성하면서 PCS 또는 SCS를 지정할 수 있는 POSIX Pthreads API를 강조한다.
- PTHREAD SCOPE PROCESS는 PCS를 PTHREAD SCOPE SYSTEM은 SCS를 사용하여 스케줄 한다.
5. Multiple-Processor Scheduling
다중처리기란 여러 개의 물리적 프로세서를 제공하는 시스템을 말하며,
여러개의 cpu가 사용 가능하다면, 여러 스레드가 병렬로 실행될 수 있으므로
부하 공유(load sharing)가 가능해진다.
그러나 스케줄링 문제는 더 복잡해져 여기에서도 최상의 해결책은 없다.
5.1 다중 처리기 스케줄링에 대한 접근 방법
한 가지 방법으로 마스터 서버라는 하나의 처리기가 모든 결정을 하게하는 것이다.
이런 비대칭 다중 처리는 오직 하나의 코어만
시스템 자료구조에 접근하기 때문에 간단하다.
병목이 단점이다.
표준 접근 방식은 SMP(symmetric multi processing)(대칭 다중 처리)이며 각 프로세서는 스스로 스케줄링 할 수 있다.
이 때 두 가지 가능한 전략을 제공한다.
- 모든 스레드가 공통 레디 큐에 있을 수 있다.
- 각 프로세서는 자신만의 스레드 큐를 가질 수 있다.
SMP는 2번의 방식이 일반적이다.
단점으로 큐마다 부하의 양이 다를 수 있지만,
이조차도 균형 알고리즘을 사용하여 균등하게 만들 수 있다.
5.2 Multicore Processors
현대의 하드웨어는 하나의 칩에 여러개의 처리 코어를 장착한 다중 코어 프로세서를 지원한다.
운영체제 입장에선 각각이 개별적인 CPU처럼 보이게 된다.
다중 코어 프로세서는 스케줄링이 어려운데,
프로세서가 데이터가 가용해지기를 오랫동안 기다리는 것을 memory stall라고 한다.
이를 해결하기 위해 최근엔 다중 스레드 처리 코어를 구현하였다.
여기선 하나의 코어에 여러 개의 하드웨어 스레드가 할당된다.
이러면 메모리를 기다리는 동안 코어가 다른 스레드로 전환할 수 있다.
운영체제 관점에선 이 하드웨어 스레드도 논리적 CPU로 보인다.
이러한 기술은 chip multi threading 혹은 하이퍼 스레딩이라고 불린다.
일반적으로 처리기를 다중 스레드화 하는 데에는 거친방법과 세밀한방법이 있다.
거친 다중 스레딩에선 스레드가 메모리 스톨과 같은 긴 지연시간을 가진 이벤트가 발생할 때까지 한 코어에서 수행된다.
이 방식은 명령어 파이프라인을 공유하기 때문에 스레드 간 교환에 많은 비용이 든다. (비우고 다시 채우고 해야 하기 때문에)
세밀한 다중 스레딩은 스레드를 잘게 나눈만큼 문맥교환이 많이 일어나지만,
스레드 교환을 위한 회로를 포함해 교환의 비용이 적다.
결론적으로 거친 방법은 고중량 저반복이고,
세밀한 방법은 저중량 고반복이라고 볼 수 있다.
물리적 코어의 자원은 하드웨어 스레드 간에 공유되므로
코어는 한번에 하나의 하드웨어 스레드만 실행할 수 있다.
따라서 두 개의 다른 스케줄링 단계가 필요하다.
5.3 Load Balancing (부하 균등화)
SMP 시스템에서 부하를 모든 처리기에 균등하게 배분하는 것이 중요하다.
부하 균등화를 위해선 push 이주와 pull 이주, 두 가지의 일반적인 접근법이 있다.
push 이주에선 특정 태스크가 주기적으로 각 처리기의 부하를 검사하고,
덜 바쁜 곳으로 스레드를 push 시킨다.
pull 이주는 덜 바쁜 곳에서 프로세스를 pull해서 가져온다.
실제로 이 둘은 종종 병렬적으로 구현된다.
5.4 처리기 선호도
스레드가 실행중일 때 캐시 메모리는 어떨까
스레드가 다른 처리기로 이주하면(ex. 부하 균등화 때문에)
첫 번째 프로세서의 캐시 메모리는 무효화되어야 하며,
두번째는 다시 채워져야 한다.
이는 비용이 많이 들기 때문에 대부분은 스레드를 이동시키지 않고
같은 프로세서에서 계속 warm cache 상태를 이용하려고 한다.
이를 프로세서 선호도라고 한다.
즉, 프로세스는 현재 실행 중인 프로세서에 대한 선호도를 보인다.
운영체제가 노력은하지만 보장하진 않을 때 약한 선호도라고 한다.
이땐 노력은 하지만 이주하는 것이 가능하다.
반대로 강한 선호도는 자신이 실행될 처리기 집합을 명시할 수 있다.
부하 균등화와 메모리 액세스 시간 최소화 사이는 트레이드 오프 관계다.
5.5 이기종 다중 처리
일부 시스템은 여러 측면에서 차이가 나는 코어를 사용하여 설계되었다.
이를 이기종 다중 처리(HMP)라고 한다.
HMP의 목적은 특정 요구에 따라 특정 코어에 작업을 할당하여 전력 소비를 더 잘 관리하는 것이다.
이를 지원하는 ARM 프로세서는 이를 big.LITTLE이라고 하며
고성능의 big 코어와 에너지 효율적인 LITTLE 코어를 결합하여
목적에 맞게 사용한다.
6. Real-Time CPU Scheduling
실시간 운영체제에서 cpu를 스케줄링 할 때는 특별한 쟁점을 고려해야 한다.
연성 실시간 시스템은 중요 프로세스가 우선권을 가진다는 것만 보장한다.
경성 실시간 시스템에선 태스크는 반드시 마감전에 서비스를 받아야 한다.
이러한 시스템에서 프로세스 스케줄링과 관련된 여러 쟁점에 대해 논의해보자.
6.1 Minimizing Latency
이벤트 지연시간은 이벤트가 발생하고 서비스가 수행될 때까지의 시간을 말한다.
다음 두 가지 유형의 지연시간이 실시간 시스템의 성능을 좌우한다.
- 인터럽트 지연시간
- 디스패치 지연시간
인터럽트 지연시간은 인터럽트가 발생하고 처리 루틴이 시작하기까지의 시간을 말한다.
인터럽트 지연시간에 영향을 주는 요인 중 하나는 커널 데이터 구조체를 갱신하는 동안 인터럽트가 불능케 되는 시간이다.
디스패치 지연시간은 디스패처가 프로세스를 블록시키고 다른 프로세스를 시작하는 데까지 걸리는 시간을 말한다.
이를 최소화하는 가장 효과적인 방법은 선점형 커널이다.
디스패치 지연시간의 충돌 단계는 다음의 두 가지 요소로 구성되어 있다.
- 커널에서 동작하는 프로세스에 대한 선점
- 높은 우선순위의 프로세스가 필요한 자원을, 낮은 우선순위 프로세스 자원이 방출
충돌 단계에 이어 디스패치 단계는 우선순위가 높은 프로세스를 가용한 cpu에 스케줄 한다.
6.2 Priority-Based Scheduling
실시간 운영체제에서 가장 중요한 기능은
실시간 프로세스에 cpu가 필요할 때 바로 응답을 해주는 것이다.
따라서 선점 우선순위 알고리즘을 지원해야 한다.
하지만 이것도 단지 연성 실시간 기능을 제공하는 것이고,
경성 실시간 시스템에서는 부가적인 스케줄링 기법이 필요하다.
그 전에 프로세스들의 특성을 알아보자.
프로세스들은 주기적이다.
즉, 일정한 간격으로 cpu가 필요하다.
이런 형식의 스케줄링에서 프로세스가 자신의 마감시간을 스케줄러에게 알려야 하는 경우도 있다.
따라서 승인 제어 알고리즘을 이용해서 마감시간 이내에 완수할 수 있는 프로세스는 실행을 허락하고 아니면 거절한다.
6.3 Rate-Monotonic 스케줄링
선점 가능한 정적 우선순위 스케줄링이다.
cpu를 자주 필요로 하는 태스크에 더 높은 우선순위를 부여한다.
(6천원주고 빌린 책인데 깔끔히 쓰고 돌려줘야 하는데;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ㅈㅅ.. 종이 왤케 얇음...페이지 수가 많아서 이 사기꾼 -inhkim-)
Rate-monotonic 기법으로 스케줄 할 수 없는 프로세스 집합은
다른 정적 우선순위 알고리즘 역시 스케줄 할 수 없다.
Rate-monotonic은 최적이기는 하지만 많은 제약이 있다.
(프로세스가 마감시간을 만족시킬지 보장할 수 없다.)
6.4 Earliest-Deadline-First 스케줄링
EDF 스케줄링은 마감시간에 따라 우선순위를 동적으로 부여한다.
EDF에서는 프로세스가 실행 가능하게 되면 자신의 마감시간을 시스템에 알려야 한다.
새로운 프로세스가 오면 우선순위가 재조정된다.
EDF는 프로세스들이 주기적일 필요도 없고, cpu 할당시간도 상수 값으로 정해질 필요가 없다.
EDF는 이론적으로 최적이지만, 실제로는 인터럽트 등에서 문맥 교환 비용 때문에 100%의 cpu 이용률은 불가능하다.
6.5 일정 비율의 몫 스케줄링
모든 응용들이 시간 몫을 할당하여 동작한다
6.6 POSIX 실시간 스케줄링
POSIX는 실시간 컴퓨팅용으로
실시간 스레드를 위하여 두 개의 스케줄링 클래스를 정의한다.
- SCHED FIFO
- SCHED RR
스터디 요약
로드 밸런싱에서 캐시 무효화
NUMA의 아키텍처 구현에 대해
real-time system이란?
