스레드를 지원하는 운영체제에서는 실질적으로 운영체제는 프로세스가 아니라 커널 수준 스레드를 스케줄 한다.
프로세스 스케줄링과 스레드 스키줄링은 상호교환적으로 사용된다.
일반적인 스케줄링 개념을 논의하는 경우 프로세스 스케줄링을 사용하고 스레드에 국한된 개념을 가리키는 경우 스레드 스케줄링이라는 용어를 사용한다.
기본 개념
단일 프로세서 시스템에서는 한 순간에 오직 하나의 프로세스만이 실행할 수 있다.
다중 프로그래밍의 목적은 CPU 이용률을 최대화 해 항상 실행중인 프로세스를 가지게 하는데 있다.
하나의 프로세스는 전형적으로 어떤 입출력 요청이 완료되기를 기다려야 할 떄 까지 실행된다.
이러한 대기시간은 낭비다.
어떤 프로세스가 대기해야할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에게 할당한다.
이러한 스케줄링은 운영체제의 기본적인 기능이다.
CPU I/O 버스트 사이클
프로세스 실행은 CPU실행과 입출력 대기의 사이클로 구성된다.
프로세스들은 이들 두 상태 사이를 교대로 오간다.
프로세스 실행은 CPU버스트 → 입출력버스트 → 또다른 CPU버스트 등등으로 실행된다.
CPU 스케줄러
CPU는 유휴 상태가 될 때마다, 운영체제는 준비 완료 큐에 있는 프로세스 들 중에서 하나를 선택해 실행해야 한다.
선택 절차는 단기 스케줄러에 의해 수행된다.
스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스들 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다.
선점 스케줄링
CPU 스케줄링의 결정은 다음의 네가지 상황에서 발생한다.
한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (wait()를 호출)
프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (인터럽트 발생)
프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (입출력의 종료)
프로세스가 종료할 때
1과 4의 경우는 비선점 스케줄링이라 한다.
2와 3의 경우는 선점 스케줄링이라 한다.
자료가 다수의 프로세스에 의해 공유될 때 race condition을 초래한다.
대부분의 운영체제들은 context switching을 수행하기 전에 system call이 완료되거나 입출력 요구에 따른 블로킹이 일어나기를 기다리는 방법을 사용한다. 커널의 자료구조가 일관성 없는 상태에 있을 동안 커널이 해당 프로세스를 선점하지 않기 때문에 이러한 방법은 커널 구조를 단순하게 만든다.
인터럽트에 의해서 영향을 받은 코드는 반드시 동시사용으로부터 보호되야 한다.
입력을 잃어버리거나 출력이 겹칠수 있기 때문에 운영체제는 항상 인터럽트를 받아들일 필요가 있다.
Dispatcher
디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이다.
context switching
사용자 모드로 전환하는 일
프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일
디스패처는 모든 프로세스의 context switching이 일어날 때 호출되므로, 가능한 가장 빨리 수행되야 한다.
디스패처가 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데 소요되는 시간을 디스패치 레이턴시라고 한다.
스케줄링 기준
CPU 스케줄링 알고리즘을 비교하기 위한 아래와 같은 기준이 있다.
CPU 이용률 : CPU가 항상 바쁘기를 기대한다. (40~90%)
처리량 (Throughput) : 작업량의 측정 방법은 단위 시간당 완료된 프로세스의 갯수다.
총처리 시간 (turn around time) : 프로세스의 제출 시간과 완료 시간의 간격을 총 처리 시간이라고 한다.
총처리 시간 = 메모리에 들어가기 위해 기다린 시간 + 준비 완료 큐에서 대기한 시간(대기 시간) + CPU 실행 시간 + 입출력 시간
대기 시간 (waiting time) : 준비완료 큐에서 대기하면서 보낸 시간의 양
응답 시간 (response item) : 응답이 시작되는 데까지 걸린 시간.
대부분의 경우 평균 측정시간을 최적화 하려고 한다.
그러나 어떤 경우에는 평균 보다는 최솟값 또는 최댓값을 최적화 하는 것이 바람직할 수도 있다.
예를 들어 모든 사용자들이 좋은 서비스를 얻도록 보장하기 위해, 최대응답시간을 최소화 하려고 할 수도 있다.
스케줄링 알고리즘
CPU 스케줄링은 준비 완료 큐에 있는 프로세스 중 어떤 프로세스에게 CPU를 할당 할 것인지를 결정한다.
FCFS; 선입 선처리 스케줄링
FCFS는 가장 간단한 스케줄링 알고리즘이다.
CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는다.
FCFS정책은 FIFO 큐로 관리된다.
프로세스가 준비 완료 큐에 진입 하면 PCB를 큐의 끝에 연결한다.
FCFS는 대기시간이 길 수 있다.
모든 프로세슫르이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 효과를 호위효과 convoy effect라고 한다.
FCFS는 비선점형 스케줄링이다.
일단 CPU가 한 프로세스에 할당 되면, 드 프로세스가 종료하든지 또는 입출력 처리를 요구하든지 하여 CPU를 방출할때까지 CPU를 점유한다.
SJF; 최단 작업 우선 스케줄링
SJF 알고리즘은 각 프로세스에 다음 PCU버스트 길이를 연관시킨다.
CPU가 이용가능해지만 다음 CPU버스트가 가장 짧은 프로세스에게 할당한다.
다음 CPU 버스트의 길이에 의해 스케줄링 되기 때문에 shortest-next-CPU-burst라는 말도 적합하다.
SJF 스케줄링은 평균 대기 시간이 짧다는 특징이 있다.
그러나 CPU요청의 길이를 파악하는것은 어렵다.
단기 스케줄링에서 PCU 버스트의 길이를 알 수 있는 방법은 없다.
SFJ는 선점형이거나 비선점형일 수 있다.
선점형 SJF는 현재 실행하는 프로세스를 선점할 것이다
비선점형 SJF는 현재 실행하고 있는 프로세스가 자신의 CPU버스트를 끝내도록 허용한다.
Priority 우선순위 스케줄링
SJF알고리즘은 일반적인 우선순위 알고리즘의 특별한 경우다.
우선순위가 연관되어있으면 CPU는 가장 높은 우선순위를 가진 프로세스에게 할당 된다. 우선순위가 같으면 FCFS순서로 스케줄 된다.
우선순위의 정의
내부적 우선순위 정의 : 프로세스의 우선순위를 계산하기 위해 측정 가능한 양을 사용한다 (시간제한, 메모리요구, 열린 파일의 수, 버스트 비율 등)
외부적 우선순위 정의 : 프로세스의 중요성 등 정량적이지 않는 기준
우선순위 스케줄링은 선점형이거나 비선점형일 수 있다.
선점형은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 선점한다.
비선점형은 단순히 큐의 머리 부분에 새로운 프로세스를 넣는다.
우선순위 스케줄링의 주요 문제는 무한 봉쇄 또는 기아 상태다. 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 블로킹 된 것으로 간주될 수 있다.
R-R 라운드 로빈 스케줄링
RR 스케줄링은 시분할 시스템을 위해 설계됐다.
time slice라고 하는 작은 단위를 정의한다.
준비 완료 큐는 원형 큐로 동작한다.
CPU 스케줄러는 준비완료 큐를 돌면서 한번에 한 프로세스에게 한번의 시간할당량 동안 CPU를 할당한다.
RR알고리즘의 성능은 시간할당량의 크기에 매우 많은 영향을 받는다.
시간할당량이 매우 크면 RR정책은 FCFS와 같다
시간할당량이 매우 작다면 많은 context switching을 야기한다.
Multilevel queue 다단계 큐 스케줄링
프로세스는 foreground(상호작용) 프로세스들과 background(배치작업) 프로스들로 구분된다.
이 두 유형은 응답시간의 요구에 따른 스케줄링 종류와 작업의 특성상 우선순위가 다르다.
다단계 큐 스케줄링은 준비 완료 큐를 다수의 별도 큐로 분류한다.
예를들어 foreground는 RR알고리즘을 사용하고 background는 FCFS를 사용할 수도 있다.
Multilevel feedback queue 다단계 피드백 큐 스케줄링
일반적으로 프로세스들은 하나의 큐에 할당된다. 프로세스들은 다른 큐로 이동하지 않는다. 이런 방식은 오버헤드가 적지만 융통성이 없다.
다단계 피드백 큐 스케줄링에서는 프로세스가 큐를 이동하는것을 허용한다. 이렇게 하면 프로세스가 너무 오래 대기하는 것을 방지할 수 있기 때문에 기아상태를 방지할 수 있다.
다단계 피드백 큐 스케줄러는 가장 일반적인 CPU 스케줄링 알고리즘이다.
스레드 스케줄링
운영체제에서 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드다.
사용자 수준 스레드는 스레드 라이브러리에 의해 관리되고 커널은 그들의 존재를 알지 못한다.
사용자 수준 스레드는 궁극적으로 연관된 커널 수준 스레드에 mapping 되어야 된다.
경쟁 범위
사용자 수준과 커널 수준 스레드의 차이중 하나는 어떻게 스케줄 되느냐에 있다.
프로세스-경쟁-범위 PCS : N:1과 N:M 모델을 구현하는 시스템에서는 스레드 라이브러리는 LWP상에서 스케줄한다. 이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁한다는 정의
PCS는 우선순위에 따라 행해진다. 가장 높은 우선순위를 가진 프로세스를 선택한다.
사용자 수준 스레드의 우선순위는 프로그래머에 의해 지정된다.
PCS는 일반적으로 더 높은 우선순위의 스레드를 위해 현재 실행중인 스레드를 선점한다.
같은 우선순위의 스레드들 사이에 시간할당량 보장은 없다.
실제로 CPU상에서 실행되기 위해서는 운영체제가 커널 스레드를 물리적인 CPU로 스케줄 하는 것을 필요로 한다.
시스템-경쟁-범위 SCS : CPU상에서 어느 커널 스레드를 스케줄 할 것인지 결정하기 위한 커널 기법.
SCS스케줄링에서 CPU에 대한 경쟁은 시스템 상의 모든 스레드 사이에서 일어난다.
1:1모델을 사용하는 시스템 (Windows, Linux)는 오직 SCS만 사용해 스케줄링 한다.
Pthread 스케줄링
(생략)
멀티 프로세서 스케줄링
여러개의 CPU를 사용할 수 있으면 부하 공유가 가능해진다. 그러나 스케줄링 문제는 더 복잡해진다.
프로세스의 기능들이 동일한(homogeneous) 경우만 다룬다. 즉, 프로세서들은 큐에 있는 임의의 프로세스를 실행시킬 수 있다.
멀티 프로세서 스케줄링에 대한 접근 방법
비대칭 다중 처리 : Master server라는 하나의 프로세서가 모든 스케줄링 결정과 입출력 처리 그리고 다른 시스템의 활동을 취급하게 하는것. 하나의 프로세스만 시스템 자료구조에 접근하기 때문에 자료공유가 필요없어 간단하다.
대칭 다중 처리 : 각 프로세서가 독자적으로 스케줄링 한다. 모든 프로세스는 공동의 준비 완료 큐에 있거나 각 프로세서마다 가지고 있는 private한 준비 완료 큐에 있게 된다.
Process Affinity 프로세스 친화성 (유사성)
프로세스가 특정 프로세서에서 캐시를 채운 후 다른 프로세서로 이주하게 되면 채워놓은 캐시는 무시된다. 그리고 다시 채우게 되는 오버헤드 비용이 크기 때문에 이주를 피하고 같은 프로세스에서 실행하려고 하는것을 Process affinity라고 한다.
Soft affinity : 운영체제가 동일한 프로세서에서 프로세스를 실행하려는 보장을 하지 않는 경우
Hard affinity : system call을 통해 프로세스는 자신이 실행될 프로세서 집합을 명시할 수 있다.
시스템의 메인 메모리 구조가 프로세스 친화성 이슈에 영향을 줄 수 있다.
NUMA 비균등 메모리 접근 : 이러한 구조를 가지는 시스템은 CPU가 메인 메모리의 일부분을 접근할 때 다른 부분보다 빠르게 접근하게 된다. (나중에 추가 자료 찾아볼것)
로드 밸런싱
SMP(대칭형 다중 프로세서) 시스템에서 프로세서가 하나 이상이라는 것을 최대한 활용하려면 부하를 모든 프로세서에 균등하게 배분하는것이 중요하다.
로드밸런싱은 일반적으로 각 프로세서가 실행할 프로세스를 위한 자기 자신만의 큐를 가지고 있는 시스템에서만 필요한 기능이다.
공통 큐만 있는 시스템은 한 프로세스가 쉬게 되면 곧바로 공통 큐에서 새로운 프로세스를 선택하여 실행하기 때문에 로드 밸런싱이 필요하지 않다.
SMP 시스템은 다수의 물리 프로세서를 제공함으로써 다수의 스레드가 동기에 실행되게 한다. 그러나 최근의 관행은 하나의 물리적인 칩 안에 여러개의 프로세서 코어를 장착하는 것이다. 이런 구조를 멀티코어 시스템이라고 한다.
멀티코어 프로세서를 사용하는 SMP 시스템은 각 프로세서가 자신의 물리 칩을 가지는 시스템에 비해 빠르고 적은 전력을 소모한다.
Memory stall : 프로세서가 메모리를 접근할 때 데이터가 가용해지길 기다리며 많은 시간을 허비하는 현상. Cache miss 등 여러 원인이 있음.
프로세서를 멀티스레딩하는데는 두가지 방법이 있다.
Coarse-grained multi threading : 스레드가 메모리 멈춤과 같은긴 지연시간을 가진 사건이 발생할 때 까지 한 프로세스에서 실행된다. 긴 지연시간을 가진 이벤트 에 의한 지연때문에 프로세서는 다른 스레드를 실행하게 된다. 그러나 그 프로세서 코어에서 다른 스레드가 수행되기 전에 명령어 파이프라인이 완전히 정리되어야하기 때문에 스레드간 교환 비용이 크다. 새로운 스레드가 실행을 시작하면 자신의 명령어들로 파이프라인을 채우기 시작한다.
fine-grained multi threading : 보통 명령어 주기의 경계에서 같이 좀 거 세밀한 정밀도를 가진 시점에서 스레드 교환이 일어난다. 그러나 세밀한 시스템의 구조적 설계는 스레드 교환을 위한 회로를 포함시킨다. 결과적으로 스레드 간 교환 비용이 적어진다
멀티 스레드 멀티코어 프로세서는 두 단계의 스케줄링이 필요하다.
어느 소프트웨어 스레드가 각 하드웨어 스레드에서 실행되야 하는지 운영체제가 결정한다.
각 코어가 어떤 하드웨어 스레드를 실행시킬지 지정해야 한다.
실시간 CPU 스케줄링
Soft real-time systems : 중요한 실시간 프로세스가 스케줄 되는 시점에 관해 보장하지 않는다. 오직 중요 프로세스가 그렇지 않은 프로세스들에 비해 우선권을 가진다는 것만 보장한다.
Hard real-time systems : 태스크는 반드시 마감시간까지 서비스를 받아야하며 마감시간이 지난 이후에 서비스를 받는 것은 서비스를 전혀 받지 않는 것과 동일한 결과를 초래한다.
레이턴시 최소화
실시간 시스템의 event-driven 에서 시스템은 일반적으로 실시간으로 발생하는 이벤트를 기다린다.
이벤트가 발생하면 시스템은 가능한 빨리 그에 응답을 하고 동작을 수행해야 한다.
Event-latency : 이벤트가 발생해서 그에 맞는 서비스가 실행될 때까지의 시간을 말한다.
다음의 두가지 유형의 레이턴시가 실시간 시스템의 성능을 좌우한다.
인터럽트 레이턴시 : CPU에 인터럽트가 발생한 지점부터 해당 인터럽트 처리 루틴이 시작하기 까지 시간.
디스패치 레이턴시 : 스케줄링 디스패처가 하나의 프로세스를 블로킹하고 다른 프로세스를 시작하게 하는데 걸린 시간. 디스패치 지연시간을 최소하는 방법은 선점형 커널이다.
디스패치 레이턴시의 구성요소
디스패치 레이턴시의 충돌 단계는 다음의 두 요소로 구성된다
커널에서 동작하는 프로세스에 대한 선점
높은 우선순위의 프로세스가 필요한 자원을 낮은 우선순위 프로세스 자원이 방출 (이게 무슨말임?)
우선순위 기반 스케줄링
각각의 프로세스 중요성에 따라 그 우선순위를 부여한다.
더 중요한 태스크가 그렇지 않은 태스크들 보다 더 높은 우선순위를 갖게 된다.
스케줄러가 선점 기법을 제공한다면, 현재 CPU를 이용하고 있는 프로세스가 더 높은 우선순위를 갖는 프로세스에게 선점될 수도 있다.
선점 및 우선 순위 기반 스케줄러를 제공하는 것은 단지 소프트 실시간 시스템을 제공하는 것에 불과하다. 하드 실시간 시스템은 작업이 수행되는것이 보장되야 하며 그렇기 때문에 부가적인 스케줄링 기법이 필요하다.
Rate-Monotonic 스케줄링
선점 가능한 정적 우선순위 정책을 이용해 주기 태스크들을 스케줄 한다.
Earliest-Deadline-First 스케줄링
마감시간에 따라서 우선순위를 동적으로 부여한다.
일정 비율의 몫 스케줄링
모든 어플리케이션에 T개의 시간 몫을 할당하여 동작한다
한 개의 어플리케이션이 N개의 시간 몫을 할당 받으면 그 어플리케이션은 시간 중 N/T 시간을 할당받게 된다.
POSIX 실시간 스케줄링
(나중에 다시 찾아볼것)
알고리즘의 평가
알고리즘을 선택하는데 사용할 기준의 정의
최대 응답 시간이 1초라는 제약 조건 하에서 CPU이용률을 극대화 한다
총 처리 시간이 전체 실행 시간에 평균적으로 선형 비례가 되도록 처리량을 극대화 한다.
결정론적 모델링
분석적 평가 : 주어진 작업 부하에 대한 알고리즘의 성능을 평가하는 공식이나 값을 생성하기 위해 주어진 알고리즘과 시스템 작업 부하를 이용한다.
결정론적 모델링 : 사전에 정의된 특정한 작업 부하를 받아들여 그 작업 부하에 대한 각 알고리즘의 성능을 정의한다.
