운영체제 (공룡책) - 5

67557 단어 공룡책 운영체제 CPU 스케줄링 CPU 스케줄링

2. 프로세스 관리

5. CPU 스케줄링

다중 프로그래밍 운영체제의 기초. CPU에서 프로세스 간 전환을 통해 생산성 증가.

"프로세스 스케줄링"과 "스레드 스케줄링"은 보통 같은 의미로 사용. 여기서는 프로세스 스케줄링 process scheduling으로 일반적인 스케줄링 개념을 칭하고, 스레드 스케줄링 thread scheduling은 스레드에만 해당되는 내용을 의미할 것.

코어 core가 어떻게 CPU의 기본 연산 단위가 되는지를 다룰 것. 즉, "CPU를 돌릴" 프로세스를 스케줄링한다고 할 때, 프로세스가 CPU의 코어에서 돈다는 것을 의미함.

단원 목표

여러 CPU 스케줄링 알고리듬 이해하기
스케줄링 평가 기준에 따라 CPU 스케줄링 알고리듬 평가하기
다중 프로세서와 다중 코어 스케줄링에서 발생하는 문제 이해하기
여러 실시간 스케줄링 알고리듬 이해하기
모델링과 시뮬레이션을 적용하여 CPU 스케줄링 알고리듬 평가하기
여러 CPU 스케줄링 알고리듬을 구현한 프로그램 설계하기

5.1. 기본 개념

CPU 코어가 하나면 한 번에 프로세스 하나 밖에 못 돎. 다중 프로그래밍의 목표는 매 시간마다 프로세스를 실행시켜 CPU의 효율을 높이는 것. 개념은 쉬움. 프로세스가 입출력 등을 대기하면 CPU도 아무것도 안하고 쉬고 있을 것임. 다중 프로그래밍 적용하면 이 시간을 활용함. 여러 프로세스를 메모리에 한 번에 올리고, 한 프로세스가 대기 중이면 CPU를 다른 프로세스에게 부여함.

이런 스케줄링이 핵심 운영체제 함수. 거의 모든 컴퓨터 자원은 사용되기 이전에 스케줄링이 되어있음. CPU도 핵심 컴퓨터 자원이니 마찬가지임.

5.1.1. CPU-입출력 버스트 주기

CPU 스케줄링의 성공은 프로세스의 속성에 달려있음: 프로세스 실행은 CPU 실행 주기 cycle와 입출력 대기로 나뉨. 이 두 상태를 왔다 갔다 함. 프로세스는 우선 CPU 버스트 CPU burst로 실행이 시작되며, 나중에 입출력 버스트 I/O burst가 되고, 다시 CPU 버스트가 되며 시스템에게 실행을 종료하는 요청을 보냄:

CPU 버스트의 소요 시간은 확장적으로 측정됨. 프로세스 바이 프로세스, 컴터 바이 컴터로 당연히 다른데, 아래 그림과 유사한 곡선을 가지긴 함. 보통 지수적, 혹은 과지수적인 형태를 띠어 자주 발생하는 짧은 CPU 버스트와 적게 발생하는 긴 CPU 버스트로 고성됨. 입출력 제약 프로세스의 경우 짧은 CPU 버스트가 많음. CPU 제약 프로그램은 긴 CPU 버스트가 몇 개 있을 수 있음. 이 분배가 CPU 스케줄링 알고리듬 구현할 때 중요한 부분임

5.1.2. CPU 스케줄러

CPU가 놀고 있으면 CPU 스케줄러 CPU scheduler가 메모리에서 실행 가능한 프로세스 골라서 CPU에 해당 프로세스 할당해줘야 함.

준비 큐가 반드시 선입선출 큐가 아닐 수도 있음. 우선순위 큐, 트리, 정렬 안 된 연결 리스트 등도 가능함. 개념적으로는 CPU에 실행되도록 줄 서있는 큐라고 생각. 큐의 원소는 보통 프로세서의 프로세서 제어 블록(PCB).

5.1.3. 선점 / 비선점 스케줄링

CPU 스케줄링할 때 내릴 결정들은 다음 경우에 발생:

프로세스가 실행 상태에서 대기 상태로 바뀔 때 (입출력 요청이나 wait() 호출 등)
프로세스가 실행 상태에서 준비 상태로 바뀔 때 (인터럽트 등)
프로세스가 대기 상태에서 준비 상태로 바뀔 때 (입출력 완료 등)
프로세스 종료할 때

1, 4번엔 딱히 스케줄링이라 할 만한게 없음. 그냥 새 프로세스 (준비 큐에 있으면) 실행하면 됨.

이런 걸 비선점적 nonpreemptive 혹은 협력적 cooperative 스케줄링 계획이라 부름. 반대로 2, 3번은 선점적 preemptive라 부름. 비선점적 스케줄링해선 프로세스가 종료되거나 대기 상태로 교환되지 않는 이상 프로세스가 계속 CPU 붙잡고 있음. 사실상 모든 현대적인 운영체제는 선점적 스케줄링 알고리듬 사용.

선점적 스케줄링의 경우 프로세스 간 자료를 공유할 때 경합 조건에 놓이게 됨. 만약 A가 자료 수정 중에 선점 당해서 B가 실행됐다고 가정. 근데 B가 수정 중이던 자료를 읽으려 한다면?

선점은 운영체제 커널의 설계에도 영향을 미침. 시스템 호출 처리하면 커널이 해당 호출을 처리하느라 바쁠 것. 근데 여기서 처리하는게 중요한 커널 자료(입출력 큐 등)를 수정하는 걸 수도 있음. 근데 이 프로세스가 수정 중간에 선점 당했는데, 이후에 커널(혹은 장치 드라이버)이 똑같은 자료를 읽거나 수정하려 한다면? ㅈ됨. 커널은 비선점/선점 둘 중 하나로 구현 가능. 비선점 커널의 경우 시스템 호출이 완료될 때까지, 혹은 프로세스가 입출력 완료 대기할 때까지 막는 동안 대기함. 이후에 문맥 교환. 이러면 커널 구조를 단순화해줌. 근데 이건 실시간 컴퓨팅 입장에선 별로 안 좋음. 작업이 주어진 시간 간격 내에 완료되어야 하기 때문. 선점적 커널은 상호 배제 잠금을 통해 공유 자료에 대한 경합 조건 방지. 대부분의 현대적인 운영체제는 커널 모드에서도 완전히 선점적임.

인터럽트는 이론상 언제라도 일어날 수 있고, 커널이 무시할 수도 없으므로 인터럽트에 의해 영향 받을 수 있는 코드들은 동시 사용에 대비하여 보호해야함. 그러므로 여러 프로세스에 의해 동시에 접근이 불가해야 함. 이 경우 시작할 때 인터럽트를 비활성화하고, 끝나면 인터럽트를 재활성화해줌. 물론 인터럽트 비활성화하는 코드 부분은 자주 발생하지 않고, 명령어도 적음.

5.1.4. 디스패처

디스패처 dispatcher는 CPU 스케줄링 함수의 한 성분으로 CPU 스케줄러가 선택한 프로세스에 CPU의 코어에 대한 제어권을 줌:

프로세스 간 문맥 교환
사용자 모드로 교환
사용자 프로그램에 알맞은 위치로 도약하여 프로그램 재개

디스패처는 매 문맥 교환마다 실행되므로 최대한 빨라야 함. 프로세스 하나 중단하고 다른 거 실행시키는 데 걸리는 시간을 디스패치 지연 속도 dispatch latency라 부름:

그래서 문맥 교환이 얼마나 자주 일어남? 리눅스 체제의 경우 시스템 단의 문맥 교환 정보를 vmstat 명령어로 얻을 수 있음:

vmstat 1 3

1초 간격으로 세 줄을 출력함:

------cpu-----
24
225
339

첫번째 줄이 시스템 부팅 후 1초 간 평균 문맥 교환 수고, 뒤에 두 줄은 두 번의 1초 간격 간 몇 번의 문맥 교환이 일어났는지 보여줌.

/proc 파일 체제로 주어진 프로세스의 문맥 교환 횟수 알 수 있음. /proc/2166/status의 경우 pid = 2166인 프로세스에 대한 여러 통계를 볼 수 있음:

cat /proc/2166/status

이러면 다음 결과가 나옴:

    voluntary_ctxt_switches			150
    nonvoluntary_ctxt_switches		8

프로세스 일생 동안의 문맥 교환 횟수임. 자의적 voluntary과 타의적 nonvoluntary 문맥 교환이 구분되어있음. 자의적 문맥 교환은 프로세스가 현재 사용 불가능한 자원을 요청해서 CPU의 제어를 포기한 경우. 타의적 문맥 교환은 CPU가 다른 프로세스에게 뺏긴 경우. 주어진 시간이 다 됐거나 더 우선순위가 높은 프로세스에 의해 선점 되었을 수도.

5.2. 스케줄링 평가 기준

CPU 알고리듬마다 특징이 다 다름. 그래서 상황마다 알고리듬을 잘 골라야 함.

그래서 알고리듬 간 평가 기준이 필요:

CPU 효율 CPU utilization. CPU를 최대한 놀지 않게. 개념적으로 CPU 효율은 0부터 100%까지. 실제로는 40%(탑재량이 가벼운 체제)에서 90%(탑재량이 무거운 체제). (리눅스, macOS, 유닉스 체제에서는 top 명령어로 CPU 효율 볼 수 있음.)
처리율 throughput. CPU가 프로세스 실행하느라 바쁘면 됨. 작업에 대한 단위로, 처리율 throughput이란 시간 단위 당 완료된 프로세스의 수를 의미.
턴어라운드 시간 turnaround time. 특정 프로세스 입장에서는 자기 프로세스 얼마나 오래 실행할 수 있냐가 중요함. 프로세스 제출 시간부터 완료 시간까지의 간격이 턴어라운드 시간. 준비 큐에서 대기한 시간, CPU에서 실행된 시간, 입출력 처리한 시간 전부 포함.
대기 시간 waiting time. CPU 스케줄링 알고리듬은 프로세스가 실행하는 시간이나 입출력 처리하는 시간에 영향 안 줌. 오로지 준비 큐에서 대기하는 시간에만 영향을 줌. 대기 시간은 준비 큐에서 대기한 기간의 합임.
반응 시간 response time. 상호작용 체제에선 턴어라운드 시간이 최상의 기준이 아닐 수도. 보통 프로세스들은 빠르게 출력을 내고, 새로운 결과를 계산하는 동안 출력을 사용자에게 보여주고 있을 것. 그러므로 요청이 처음으로 들어왔을 때 이걸 처리하기 시작하는 데까지 걸린 시간, 즉 반응 시간이 하나의 평가 기준. 요청을 완료할 때까지 걸린 시간이 아니라, 요청에 대응하기 시작한 데 걸린 시간임.

CPU 효율과 처리율을 극대화하고 턴어라운드 시간, 대기 시간, 반응 시간을 최소화하는게 베스트긴 한데, 상황 바이 상황이라 한 쪽에 더 집중하는 최적화 전략을 할 수도.

해본 사람들이 말하길 상호작용 체제에서는 평균적인 반응 시간 줄이기보다 변동성을 줄이는 게 더 중요하다고 함. 보통 반응 시간이 적당하고, 예측이 가능한 경우가 평균적으로는 더 빠르더라도 예측하기 어려운 것보다 더 나을 수도 있음. 그러나 CPU 스케줄링 알고리듬 중 이 변동성을 줄이는 연구는 별로 안 되어있음.

앞으로 여러 CPU 스케줄링 알고리듬을 다룰텐데, 그림 자료를 구체적으로 명시할 경우 프로세스마다 수백 개의 CPU / 입출력 버스트의 연속 등을 전부 명시해야하지만, 단순성을 위해 프로세스 당 한 CPU 버스트(ms 기준)만 다룸.

5.3. 스케줄링 알고리듬

CPU 스케줄링이란 준비 큐의 어떤 프로세스를 CPU 코어에 할당하느냐의 문제. 요즘 현대 CPU 구조는 다중 프로세싱 코어지만, 여기서 다루는 스케줄링은 코어가 하나만 있을 때를 가정함.

5.3.1. 선도착 선처리 스케줄링

가장 간단한 알고리듬인 선도착 선처리 first-come first-serve (FCFS) 스케줄링 알고리듬. CPU에 먼저 할당 요청한 프로세스가 우선적으로 처리됨. 단순 선입선출 큐로 구현 가능. 구현도 쉽고 이해하기도 쉬움.

단점이라면 평균 대기 시간이 보통 긴 편임. 다음 프로세스들이 시간 0에 도착한다고 가정. 주어진 CPU 버스트의 길이의 단위는 ms:

프로세스	버스트 시간
P1	24
P2	3
P3	3

위의 순서로 도착하면 아래의 간트 차트 Gantt chart대로 될 것:

P1의 대기 시간은 0 ms, P2의 대기 시간은 24 ms, P3의 대기 시간은 27 ms. 평균 대기 시간은 17 ms. 2, 3, 1 순서로 왔다면 다음과 같음:

평균 대기 시간은 3 ms. 순서 좀 달라졌다고 평균 대기 시간이 달라짐. 그래서 FCFS 정책의 경우 평균 대기 시간이 최적의 경우가 아닐 뿐더러 프로세스의 CPU 버스트 간 차이가 클 수록 예측하기 힘들어짐.

만약 CPU 제약 프로세스가 하나고 나머지는 전부 입출력 제약 프로세스라는 동적인 환경이라면 다음과 같은 일이 발생함: 우선 CPU 제약 프로세스가 CPU를 차지함. 이 동안 다른 프로세스가 입출력 완료하고 준비 큐에서 CPU 대기할 것. 그동안 입출력 장치들은 놀고 있음. 언젠가 CPU 제약 프로세스가 완료되면 입출력 제약 프로세스는 빠르게 처리 가능하니 빠르게 처리하고 다시 입출력 큐에 들어갈 것임. 이러면 또 CPU가 놀고 있음. CPU 제약 프로세스가 다시 준비 큐에서 빼내서 실행이 될 거고, 다시 입출력 프로세스는 또 기다려야함. 큰 프로세스 하나가 CPU 뱉을 때까지 대기하는 현상을 호위 상태 convoy effect.

비선점적임. 그래서 상호작용 체제에 적합하지 않음.

5.3.2. 최단 작업 우선 스케줄링

최단 작업 우선 shortest-job-first (SJF) 스케줄링 알고리듬은 각 프로레스의 다음 CPU 버스트를 바탕으로 작동. 앞으로 남은 CPU 버스트가 제일 적은 프로세스를 우선적으로 실행. 만약 둘이 같ㅇ다면 FCFS 스케줄링으로 처리. 사실 더 적합한 이름은 최단 잔여 CPU 버스트 shortest-next-CPU-burst 알고리듬임.

예시:

프로세스	버스트 시간
P1	6
P2	8
P3	7
P4	3

간트 차트:

평균 대기 시간 7 ms. FCFS 였으면 10.25 ms였음.

주어진 프로세스에 대해 최소 대기 시간을 얻을 수 있다는 점에서 제일 최적임. 짧은 프로세스를 먼저 처리해서 짧은 프로세스들의 대기 시간 줄이는게 큰 프로세스의 대기 시간 증가하는 것보다 더 강해서 평균 대기 시간 줄어 듦.

최적이긴 한데 CPU 스케줄링 단계에서 구현은 불가함. CPU 버스트가 얼마나 걸릴 지 모르니까. 이를 해결하려 했던 것이 근사 SJF 스케줄링. 값은 몰라도 예측은 가능하니깐. 다음 CPU 버스트는 기존과 유사할 것이라는 생각으로 근사.

다음 CPU 버스트는 보통 기존 CPU 버스트 측정 값의 지수 평균 exponential average으로 예측함. tn이 n 번째 CPU 버스트 길이라 하고, τn + 1이 다음 CPU 버스트 추정치라 하면, 0 ≤ α ≤ 1인 α에 대해:

τn + 1 = αtn + (1 - α)τn

tn이 제일 최근 정보, τn이 과거 정보. 매개변수 α로 최근 기록과 과거 기록의 상대적 가중치를 결정. α = 0이면 최근 기록은 아무런 영향이 없고, α = 1이면 오로지 최근 기록으로만 결정됨. 일반적으론 α = 1/2로 두고 처리함:

지수 평균의 영향을 이해하려면 τn + 1의 공식을 확장하여:

τn + 1 = ατn + (1 - α)αtn - 1 + … + (1 - α)jαtn - j + … + (1 - α)n + 1αt0

각 계수가 직전 계수보다 더 작은 값을 가짐.

SJF는 비선점, 선점 둘 다 가능. 남은 CPU 버스트가 실행 중인 프로세스보다 짧은 새 프로세스가 준비 큐에 올 경우, 선점적 SJF 알고리듬에서는 현재 실행 프로세스를 선점할 것이고, 비선점적 SJF 알고리듬에서는 CPU 버스트 다 끝낼 때까지 대기함. 선점적 SJF 스케줄링을 보통 최단 잔여 시간 우선 shortest-remaining-time-first 스케줄링이라고도 함.

예시:

프로세스	도착 시간	버스트 시간
P1	0	8
P2	1	4
P3	2	9
P4	3	5

간트 차트:

시작 시 P1가 유일한 프로세스이므로 실행됨. 나중에 P2오면 얘가 남은 버스트 시간 더 짧으니까 P2 실행. 결국 평균 대기 시간은 6.5 ms. 비선점적 SJF 스케줄링의 경우 평균 대기 시간이 7.75 ms.

5.3.3. 라운드 로빈 스케줄링

라운드 로빈 round-robin (RR) 스케줄링 알고리듬은 선점이 추가된 FCFS와 유사. 시간 단위 time quantum 혹은 시간 구획 time slice이라는 이름의 짧은 시간의 단위를 정의. 보통 10 ms에서 100 ms. 준비 큐는 순환 큐. CPU 스케줄러는 이 레디 큐를 돌면서 1 시간 단위 정도 씩 프로세스를 할당함.

RR 스케줄링 구현하려면 레디 큐를 선입선출 큐로 간주. 첫번째 프로세스 빼고, 1 시간 단위 이후에 인터럽트하도록 타이머 설정하고 프로세스 디스패치.

둘 중 하나 발생할 것. 1 시간 단위보다 짧은 CPU 버스트 가질 경우 프로세스 자체가 자의적으로 CPU를 해제해줌. 그럼 스케줄러는 다음 프로세스 실행하면 됨. 만약 1 시간 단위보다 더 길면 타이머가 인터럽트 실행하여 문맥 교환이 되어 프로세스가 준비 큐의 꽁무니로 돌아감.

RR 정책의 평균 대기 시간은 긴 편임. 예시:

프로세스	버스트 시간
P1	24
P2	3
P3	3

시간 단위가 4 ms라고 가정할 때, 위의 예시를 간트 차트로 표기:

평균 대기 시간은 5.66 ms.

RR 스케줄링 알고리듬에선 그 어떠한 연속으로 1 시간 단위 초과 할당 받지 않음. 초과하면 바로 선점 당하고, 준비 큐 뒤로 돌아가야 함. 즉, RR 알고리듬은 선점적임.

준비 큐에 n 개의 프로세스가 있고 시간 단위가 q라면 각 프로세스는 CPU 시간의 1/n을 최대 q 번의 시간 단위만큼 가짐. 즉, 각 프로세스는 다음 시간 단위까지 최대 (n - 1) × q 시간 단위만큼 대기함. 만약 다섯 개의 프로세스가 20 ms의 시간 단위로 돈다면 각 프로세스는 100 ms마다 최대 20 ms 얻음.

RR 알고리듬의 성능은 시간 단위의 크기가 결정. 다음 그림처럼 충분히 시간 단위가 크면 CPU 버스트 큰 것도 한 번에 처리 가능. 하지만 애매하게 시간 단위 6에 프로세스 CPU 버스트도 6이면 두번째 처리하다가 10에서 문맥 교환 발생함. 시간 단위가 1이면 문맥 교환이 자주 일어남:

문맥 교환 시간에 따라 시간 단위가 적당히 커야함. 만약 문맥 교환 시간이 시간 단위의 10%면 CPU 시간의 10%가 문맥 교환에 사용되고 있다는 것. 실무에서는 대부분의 현대적인 운영 체제는 10에서 100 ms 사이의 시간 단위 사용. 보통 문맥 교환에 걸리는 시간이 10 ms가 안되므로, 시간 단위의 작은 부분임.

턴어라운드 시간도 시간 단위 크기에 의존함. 아래 그림에서 볼 수 있듯이 시간 단위가 증가한다고 평균 턴어라운드 시간이 개선되지는 않음. 일반적으로 평균 턴어라운드 시간은 대부분의 프로세스가 한 시간 단위에 CPU 버스트를 전부 소진할 때 제일 좋음.

시간 단위가 문맥 교환 시간보다는 커야겠지만, 너무 커서는 안됨. 너무 크면 사실상 FCFS 정책이랑 같아져버림. 보통 CPU 버스트의 80%는 시간 단위보다는 짧아야 함.

5.3.4. 우선 순위 스케줄링

SFJ는 우선 순위 스케줄링 priority-scheduling 알고리듬의 한 형태라 볼 수 있음. 각 프로세스마다 우선순위를 가지며, 가장 우선순위가 높은 프로세스가 CPU를 차지. 우선순위가 동일할 경우 FCFS순으로 처리. SJF의 경우 우선순위(p)가 (예상) 다음 CPU 버스트의 역수일 뿐임.

여기서 우선순위가 높다 high 낮다 low라는 표현을 사용. 우선순위는 0에서 7, 0에서 4095 등의 보통 고정된 범위 내의 숫자를 사용하지만, 0이 제일 낮은 건지 높은 건지에 대한 통일된 규격은 없음.

예시:

프로세스	버스트 시간	우선순위
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

간트 차트:

평균 대기 시간은 8.2 ms.

우선순위는 내부적으로든 외부적으로든 정의 가능. 내부적으로 정의할 경우 프로세스의 우선순위를 결정할 정량적인 자료(시간 한계, 메모리 소요, 연 파일 수, 평균 입출력 버스트 대 CPU 버스트율 등)를 사용. 외부적인 속성은 운영체제 외적인 기준(프로세스의 중요도, 컴퓨터 사용에 들어간 금액적 비용, 작업을 후원하는 부서, 정치적 요소 등)으로 설정.

우선순위 스케줄링도 선점 / 비선점 둘 다 가능. 프로세스가 레디 큐에 들어오면 현재 실행 중인 프로세스와 우선순위 비교. 선점적이면 새 프로세스의 우선순위가 더 높으면 원래 실행하던거 뺌.

우선순위 알고리듬의 제일 큰 문제는 무한 막기 indefinite blocking 혹은 기아 상태 starvation. 실행 준비는 됐는데 대기 중인 프로세스는 막힌 상태라고 함. 우선순위 스케줄링 알고리듬의 경우 우선순위 낮은 프로세스가 무한정 대기할 수도 있음. 부하가 많을 경우 계속해서 우선순위 높은 프로세스가 끊임없이 흐르니 우선순위 낮은 프로세스는 CPU 만나지도 못할 수도 있음. 보통 이럴 땐 언젠가(일요일 새벽 2시 등)는 프로세스가 실행이 되거나, 컴퓨터가 뻗고 모든 우선순위 작은 프로세스 사라짐. (소문에 의하면 1973년에 종료시킨 MIT의 IBM 7094에 보니 1967년에 입력 받은 우선순위 낮은 프로세스가 아직 남아있었다 카더라...)

이걸 해결하는 방법으로는 노화 aging가 있음. 기다린 만큼 우선순위 높여주는 것임.

아니면 라운드 로빈과 우선순위 결합해서 우선순위 높은 프로세스를 실행하고, 같은 우선순위끼리 라운드로 로빈 방식으로 스케줄링. 예시로:

프로세스	버스트 시간	우선순위
P1	4	3
P2	5	2
P3	8	2
P4	7	1
P5	3	3

시간 단위 2로 두고 간트 차트:

5.3.5. 다단계 큐 스케줄링

우선순위와 라운드 로빈 스케줄링 둘 다 프로세스를 하나의 큐에 놓음. 큐 관리 법에 따라 우선순위 높은 프로세스 탐색하는 데 O(n)의 탐색 시간 걸릴 수도 있음. 실무에서는 특정 우선순위에 해당하는 큐를 따로 갖곤 함. 일반적으로 보면 우선순위란 정적으로 각 프로세스에 할당되고, 프로세스는 실행 중엔 계속 같은 큐에 존재:

다단계 큐 스케줄링은 프로세스 유형에 따라 큐를 구분해줄 수도 있음:

일반적으로는 전면 foreground (상호작용) 프로세스와 배경 background (배치) 프로세스 간의 구분이 있음. 이 둘은 각각 반응 시간 소요가 다르므로 서로 다른 스케줄링 방법으로 처리. 추가적으로 전면 프로세스가 배경 프로세스보다 더 우선순위가 높은 경향을 보일 것임. 이렇게 처리해주고 전면 큐는 RR 알고리듬으로, 배경 큐는 FCFS 알고리듬으로 처리.

큐 간에도 스케줄링 필요. 보통은 고정 우선순위 선점적 스케줄링을 사용. 예를 들어 실시간 큐는 상호작용 큐보다 절대적으로 높은 우선순위를 가질 것임.

네 개의 큐를 갖는 다단계 큐 스케줄링 알고리듬의 예시. 우선순위 순으로 배치함:

실시간 프로세스
시스템 프로세스
상호작용 프로세스
배치 프로세스

각 큐는 아래 큐보다 절대적인 우선순위가 높음. 1, 2, 3 번이 비지 않는 이상 배치를 실행하지 않음. 배치 실행 중에 상호작용 프로세스 들어오면 선점 당할 것.

또다른 방법으로는 큐 간 시간 단위를 부여하는 것. 이러면 각 큐 별로 CPU 시간의 일부를 부여 받을 것임. 예를 들어 전면 큐에는 CPU 시간의 80%를 주어 RR 스케줄링을 하고, 배경은 나머지 20%를 받아 FCFS로 처리.

5.3.6. 다단계 피드백 큐 스케줄링

보통 다단계 큐 스케줄링을 사용할 경우 프로세스가 들어갈 큐는 정해져있음. 큐 간에 프로세스가 이동하지 않음. 이게 스케줄링 부담이 없긴 한데 유연성이 적음.

다단계 피드백 큐 multilevel feedback queue는 반대로 큐 간 이동이 가능해짐. CPU 버스트에 따라 프로세스를 구분하자는 것임. 프로세스가 CPU 너무 많이 사용하면 우선순위 낮은 큐로 옮기는 것. 그러면 입출력 제약 및 상호작용 프로세스처럼 CPU 버스트가 짧은 애들이 우선순위가 높아짐. 또한 너무 오랜 기간 우선순위 낮은 큐에 있으면 우선순위 높은 큐로 옮겨주기도 하는 식으로 기아 상태 방지를 위한 노화를 적용.

아래 그림에서처럼 프로세스가 첫번째 큐에 들어갔을 때, 시간 단위 8 내에 못 끝내면 두번째 큐의 끝에 넣어주고, 거기서도 시간 단위 16 내에 못 끝내면 마지막 FCFS 큐에 넣어줌. 기아 상태 방지를 위해 너무 오랫동안 FCFS 큐에서 기다리면 위로 올려줌.

일반적으로 다단계 피드백 큐 스케줄러는 다음 매개변수를 가짐:

큐의 개수
각 큐 별 스케줄링 알고리듬
프로세스를 더 높은 우선순위로 승격하는 방법
프로세스를 더 낮은 우선순위로 강등하는 방법
프로세스를 서비스해야할 때 어떤 큐에 배치할 지를 결정할 방법

다단계 피드백 큐 스케줄러가 가장 일반적인 CPU 스케줄링 알고리듬. 설계에 따라 특정 목적을 만족하게 해줄 수도 있음. 물론 가장 좋은 알고리듬을 만드려면 모든 매개변수에 대한 값을 선택해야한다는 점에서 가장 복잡한 알고리듬이기도 함.

5.4. 스레드 스케줄링

스레드는 사용자 스레드와 커널 스레드로 나뉨. 대부분의 현대적인 운영체제는 프로세스가 아니라 커널 스레드가 운영체제에 의해 스케줄링됨. 사용자 스레드는 스레드 라이브러리에서 관리하고, 커널은 여기에 관여하지 않음. 걍 모름. CPU에서 돌아가려면 사용자 스레드가, 물론 LWP의 형태로 간접적이든 뭐든 여튼 반드시 커널 스레드랑 손 잡아야 함. 이때 여기서 사용자 스레드와 커널 스레드의 스케줄링을 배울 것.

5.4.1. 경합 영역

사용자 스레드와 커널 스레드의 차이점은 스케줄링 방식. 다대일이나 다대다의 경우 스레드 라이브러리가 사용자 스레드를 LWP에 대해 스케줄링. 이게 프로세스 경합 영역 process-contention scope(PCS). 같은 프로세스의 스레드 간에 CPU 점유를 위해 경쟁하니까(스레드 라이브러리가 사용자 스레드를 LWP에 스케줄링한다는 것은 스레드가 실제 CPU에서 돌게한다는 것과는 다름). 어떤 커널 스레드를 CPU에 할당할지 스케줄링할 때는 커널이 시스템 경합 영역 system-contention scope(SCS). SCS 스케줄링 사용 시 모든 스레드 간에 CPU 점유 경쟁. 일대일 사용하는 시스템은 오로지 SCS만 사용.

보통 PCS는 우선순위에 따라 처리. 사용자 스레드의 우선순위는 프로그래머가 설정해고 스레드 라이브러리가 수정해줄 수 없음. 그럼 PCS에서는 선점적으로 처리할텐데, 스레드 간 고르게 시간 분할(5.3.3절)을 한다는 보장은 없음.

5.4.2. Pthread 스케줄링

Pthread는 다음과 같이 경합 영역 값을 구분함:

PTHREAD_SCOPE_PROCESS
PTHREAD_SCOPE_SYSTEM

다대다 모델 구현하는 경우 PTHREAD_SCOPE_PROCESS 정책으로 사용자 스레드를 LWP에 할당. LWP의 개수는 스레드 라이브러리가 스케줄러 활성(4.6.5절) 등을 통해 관리. PTHREAD_SCOPE_SYSTEM 정책은 다대다 체제에서 각 사용자 스레드마다 LWP 생성하고 바인딩해주고, 일대일에선 효율적으로 스레드 매핑을 해줌.

Pthread IPC(프로세스 간 통신)은 경합 영역 정책을 설정하고 불러올 두 함수 제공:

pthread_attr_setscope(pthread_attr_t* attr, int scope)
pthread_attr_getscope(pthread_attr_t* attr, int* scope)

첫번째 매개변수는 스레드의 속성 집합을 가리키는 포인터. 세터에서 두번째 매개변수는 PTHREAD_SCOPE_SYSTEM 아니면 PTHREAD_SCOPE_PROCESS 값으로 경합 영역을 설정해줌. 게터의 경우 두번째 매개변수는 현재 경합 영역의 값을 갖는 int 값을 가리키는 포인터임. 오류 나면 둘 다 0이 아닌 값을 반환함.

아래 코드가 Pthread 스케줄링 API 예시. 우선 존재하는 경합 영역을 불러오고 이걸 PTHREAD_SCOPE_SYSTEM으로 설정. 이후 다섯 개의 스레드를 만들어 SCS 정책에 따라 실행. 참고로 몇몇 운영체제에서는 특정 경합 영역만 가능. 리눅스와 macOS의 경우 PTHREAD_SCOPE_SYSTEM만 가능:

#include <pthread.h>
#include <stdio.h>

#define NUM_THREADS 5

void* runner(void* params);

int main(int argc, char* argv[])
{
    int i;
    int scope;
    pthread_t tid[NUM_THREADS];
    pthread_attr_t attr;
    
    /* 기본 속성 가져오기 */
    pthread_attr_init(&attr);
    
    /* 현재 영역 확인 */
    if (pthread_attr_getscope(&attr, &scope) != 0) {
    	fprintf(stderr, "Unable to get scheduling scope\n");
    } else {
    	if (scope == PTHREAD_SCOPE_PROCESS) {
            printf("PTHREAD_SCOPE_PROCESS");
        } else if (scope == PTHREAD_SCOPE_SYSTEM) {
            printf("PTHREAD_SCOPE_SYSTEM");
        } else {
            fprintf(stderr, "Illegal scope value.\n");
        }
    }
    
    /* 스케줄링 알고리듬을 PCS 혹은 SCS로 설정 */
    pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
    
    /* 스레드 생성 */
    for (i = 0; i < NUM_THREADS; ++i) {
    	pthread_create(&tid[i], &attr, runner, NULL);
    }
    
    /* 각 스레드 마다 조인 */
    for (i = 0; i < NUM_THREADS; ++i) {
    	pthread_join(tid[i], NULL);
    }
}

/* 각 스레드마다 이 함수에서 제어 시작 */
void* runner(void* params)
{
	/* 무언가를 함 */
	
	pthread_exit(0);
}

5.5. 다중 프로세서 스케줄링

지금까지는 코어 하나일 때만 다룸. 코어 여러 개면 부하 분담 load sharing을 통해 여러 스레드가 병렬적으로 돌 수 있게 되어 더 복잡해짐. 당장 단일 코어의 경우에서도 최적의 해라는 게 존재하지 않았는데, 다중 코어면...

보통 다중 프로세스 multiprocessor라는 말은 물리적인 프로세서가 여럿인 경우를 칭함. 요즘 현대적인 컴퓨팅 체제에서는 다중 프로세서란 다음 구조를 의미함:

다중 코어 CPU
다중 스레드 코어
NUMA 체제
비균일 다중 프로세싱

이 구조들을 바탕으로 다중 프로세서 스케줄링 다룰 것. 첫 세번째는 프로세서가 서로 기능 면에서 같은, 즉 균일한 프로세서들끼리 다루는 것. 마지막은 기능이 서로 같지 않은 경우를 다룸.

5.5.1. 다중 프로세서 스케줄링 접근법

스케줄링 결정, 입출력 처리 등 모든 체제 활동을 하나의 프로세서, 즉 마스터 서버가 처리하게 하는 것. 다른 프로세서는 사용자 코드만 실행. 이런 비대칭 다중 프로세싱 asymmetric multiprocessing의 경우 한 코어만 시스템 자료 구조에 접근하니까 자료 공유의 필요성도 줄어들어 단순해짐. 단점이라면 마스터 서버가 병목점이 되어 전체 성능이 낮아질 수도 있음.

일반적으로 다중 프로세서를 처리하는 법은 대칭 다중 프로세싱 symmetric multiprocessing(SMP)임. 각 프로세서는 자기 스스로 스케줄링함. 각 스케줄러가 준비 큐를 확인하고 실행할 스레드를 선택. 이러면 스레드 스케줄링하려고 구조화할 때 두 가지 전략이 나옴:

모든 스레드가 동일한 준비 큐를 사용
각 프로세서마다 개인 스레드 큐 가질 수도.

위의 전략은 아래 그림에서 확인 가능. 첫번째 전략의 경우 공유된 준비 큐에 대한 경합 조건이 설정되므로 두 프로세서가 동일한 스레드를 스케줄링하지 않도록, 그리고 스레드가 큐에서 사라지지 않도록 확인해야 함. 6 단원에서 언급하겠지만 일종의 잠금으로 공동의 준비 큐를 보호하는 법도 있음. 하지만 큐에 접근할 때마다 이 자물쇠가 너의 것이냐?를 해야해서 성능 병목점이 될 수도 있음. 두번째 방법으로는 각 프로세서가 개인 실행 큐를 가지도록 하는 것. 사실 SMP에선 두번째 방법이 제일 일반적임. 5.5.4절에서 언급하겠지만 프로세서 당 개인 실행 큐를 갖는게 캐시 메모리 활용에 있어 더 효율적임. 물론 문제도 있음. 대표적으로 크기가 서로 다른 작업들임. 그래서 프로세서에 고르게 작업을 분배하는 균형 잡는 알고리듬을 논할 것임.

사실상 모든 현대적인 운영체제(윈도우즈, 리눅스, macOS, 안드로이드, iOS 등)가 SMP를 지원하므로 앞으로 CPU 스케줄링 알고리듬은 전부 SMP 체제에서 발생하는 것들.

5.5.2. 다중 코어 프로세서

보통 SMP 체제는 여러 개의 물리적인 프로세서를 바탕으로 프로세스를 병렬 처리했었음. 근데 요즘 현대적인 컴퓨터 하드웨어는 다중 연산 코어를 하나의 칩에 넣고 다중 코어 프로세서 multicore processor 구조로 감. 각 코어는 구조를 갖는 상태를 가지므로 운영체제 입장에선 마치 분리된 논리 CPU로 인식이 됨. 다중 코어 프로세서 사용하는 SMP 체제가 사실 CPU 마다 물리적인 칩을 갖는 경우보다 더 빠르고 전력도 덜 먹음.

다중 코어 프로세서 때문에 스케줄링이 좀 복잡해짐. 예를 들어 프로세서가 메모리에 접근을 할 때, 해당 메모리의 자료를 사용할 수 있을 때까지 대기하는 시간이 생각보다 꽤 됨을 발견함. 이럴 때를 메모리 지연 memory stall이 발생함. 이게 요즘 프로세서가 메모리보다 빨라서 발생하는 것임. 근데 이 뿐만 아니라 캐시 미스(캐시 메모리에 없는 자료에 접근) 때문에 발생하기도 함. 아래 그림이 메모리 지연. 이 경우 프로세서는 자료 사용할 수 있을 때까지 대기하는데 자기 시간의 50%를 사용한다고 함:

이 상황을 처리하려고 현대적인 하드웨어 설계는 두 개 이상의 하드웨어 스레드 hardware thread가 각 코어에 할당되는 다중 스레드 프로세싱 코어를 구현함. 이러면 한 하드웨어 스레드가 메모리 대기하느라 지연되면 코어는 다른 스레드로 교환할 수 있게 됨. 아래 그림이 이중 스레드 프로세싱 코어임.

운영체제 입장에서는 각 하드웨어 스레드가 각자 구조적 상태(명령어 포인터, 레지스터 집합 등)를 유지하므로 마치 소프트웨어 스레드를 돌릴 수 있는 논리 CPU로 보임. 이 기술을 칩 멀티스레딩 chip multithreading(CMT)이라 부름. 아래 그림의 경우 프로세서가 네 개의 연산 코어를 갖고, 각 코어마다 두 개의 하드웨어 스레드를 가짐. 운영체제 입장에서는 논리 CPU가 여덟 개인 것임.

인텔 프로세서는 하이퍼 스레딩 hyper-threading(동시 멀티스레딩 simultaneous multithreading 혹은 SMT라고도 함)이라는 용어로 여러 하드뤠어 스레드를 한 프로세서 코어에 할당. 현대적인 인텔 프로세서는 코어 당 스레드 두 개를 지원함. 오라클 Sparc M7 프로세서의 경우 코어 당 여덟 개의 스레드를 지원하고, 프로세서 당 코어가 여덟 개이므로 총 64 개의 논리 CPU를 제공함.

일반적으로 프로세싱 코어를 멀티스레딩하는 방법은 두 가지임: 조립 coarse-grained 멀티스레딩과 세립 fine-grained 멀티스레딩임. 조립 멀티스레딩의 경우 메모리 지연과 같이 지연 속도가 긴 이벤트 발생 전까지 스레드가 코어에서 실행됨. 이때 지연이 길기 때문에 코어는 반드시 다른 스레드로 교환해야 함. 하지만 스레드 간 교환 시 기존 스레드가 사용하던 명령어 파이프라인을 깨끗이 비워야 새 스레드가 사용할 수 있으므로 교환 비용이 높음. 세립(혹은 교차) 멀티스레딩은 더 미세한 수준으로 교환이 이루어짐. 보통 명령어의 경계에서 일어남. 세립 체제에서의 구조적 설계에는 스레드 교환에 대한 로직도 포함하므로 스레드 간 교환 비용이 적음.

물리적인 코어의 자원들(캐시, 파이프라인 등)이 반드시 하드웨어 스레드 간 공유가 되어야 함. 그러므로 프로세싱 코어는 한 순간에 한 스레드만 실행이 가능함. 그러면 아래 그림에서처럼 사실상 멀티스레드 다중 코어 프로세서는 두 가지 스케줄링 단계를 가짐.

첫번째 단계는 운영체제가 어떤 소프트웨어 스레드를 어떤 하드웨어 스레드(논리 CPU)에 돌릴지를 결정할 스케줄링 결정. 이 부분이 실질적으로 제일 중요해서 이 단원에서 주로 다루었던 것. 그러므로 5.3 단원에 있던 스케줄링 방법 아무거나 고르면 됨.

두번째 단계는 코어가 어떤 하드웨어 스레드를 실행시킬지를 결정하는 스케줄링. 여러 전략이 있는데, 첫번째는 그냥 단순히 라운드 로빈 알고리듬으로 하드웨어 스레드를 프로세싱 코어에 스케줄링하기가 있음. UltraSPARC T3가 실제 이 방법 사용. 다른 방법으로는 인텔 Itanium이라는 코어 당 하드웨어 스레드가 두 개인 듀얼 프로세서에서 사용한 방법이 있음. 이 방법의 경우 하드웨어 스레드마다 동적으로 0과 7 사이의 긴급도 urgency 값을 부여함. 0이 제일 낮은 긴급도고 7이 제일 높은 것임. Itanium에서 스레드 교환이 일어나는 이벤트는 다섯 가지임. 이 이벤트가 발생할 시 스레드 교환 로직이 두 스레드 간의 긴급도를 비교해서 긴급도가 더 높은 스레드를 프로세서 코어에 붙임.

여기서 두 단계의 스케줄링이 꼭 상호 배타적이지는 않음. 사실 운영체제 스케줄러는 프로세서 자원 공유에 대한 지식이 있기 때문에 더 효율적으로 스케줄링 결정 내릴 수 있음. 예를 들어 프로세싱 코어가 두 개 있는 CPU에서 각 코어가 하드웨어 스레드 두 개 씩 있다고 가정. 소프트웨어 스레드 두 개가 지금 돌고 있으면 같은 코어에서 실행 될 수도, 별개의 코어에서 실행될 수도 있음. 둘 다 같은 코어에서 실행되도록 스케줄링되면 프로세서 자원을 공유하니까 따로 하는 것보다는 느릴 것임. 이에 대한 지식이 있으면 소프트웨어 스레드를 자원을 공유하지 않는 논리 프로세서에 스케줄링하면 되니까.

5.5.3. 부하 분산

SMP 체제에서는 부하 분산 load balancing을 통해 프로세스 간 작업을 고르게 분산해서 다중 프로세서의 이득을 최대한 땡겨야함. 특히 프로세서가 각자 개인 준비 큐가 있는 체제에서 필요함. 실행 큐 공동 소유 중이면 한 프로세서가 노는 상태가 되는 순간 바로 공동 실행 큐에서 실행 가능한 스레드 빼오면 되니깐 딱히 부하 분산이랄게 없음.

일반적으로 두 가지 방법이 있음: 푸시 이동과 풀 이동임. 푸시 이동 push migration의 경우 특정 작업이 현재 각 프로세서의 부하를 확인하고, 불균형하다 싶으면 스레드 간 부하를 덜 바쁘거나 놀고 있는 프로세서로 옮겨줌(밀어줌). 풀 이동 pull migration의 경우 놀고 있는 프로세서가 바쁜 프로세서에서 대기 중인 작업을 갖고 오는 것임. 푸시, 풀 이동은 딱히 상호 배타적일 필요가 없고, 사실 부하 균형 체제에서 병렬적으로 구현하는 편임. 리눅스의 CFS 스케줄러(5.7.1절 참고)와 FreeBSD 체제의 ULE 스케줄러는 두 기술을 다 구현함.

"균형 잡힌 부하"라는 개념은 여러 가지. 누구는 단순히 모든 큐가 대략적으로 같은 수의 스레드를 가질 때 균형 잡혔다고도 함. 모든 큐에 고르게 우선순위가 분배된 걸 균형 잡혔다고도 함. 어떤 경우에서는 이 두 방법이 충분하지 않을 수도 있음. 심지어 스케줄링 알고리듬의 목적에 반하게 작동할 수도 있음.

5.5.4. 프로세서 친화도

스레드가 프로세서에서 돌 때 스레드에서 자주 접한 자료가 프로세서의 캐시에 들어가있을 것임. 어차피 자주 계속 들락날락할 자료라서 계속해서 캐시 메모리에서 해당 자료 찾을 수 있을 것임("따뜻한 캐시"라고 부름). 근데 스레드가 부하 분산 등의 이유로 다른 프로세서로 가면? 그럼 새로운 프로세서의 캐시 메모리 내용이 당연히 다를 거라서 다시 스레드가 사용할 내용으로 채워야할 것임. 이게 기존 캐시 무효화하고 새 캐시로 채우는 과정이 좀 비싼 연산이라 SMP 지원하는 대부분의 운영체제들은 스레드를 프로세서 간 이동시키는 걸 좀 피하려고 함. 최대한 따뜻한 캐시를 유지하려는 것. 이게 프로세서 친화도 processor affinity임.

5.5.1절에서 스레드 큐를 조직화하는 두 가지 방법이 암시적으로 프로세서 친화도를 주려는 것임. 공동 준비 큐 사용할 경우 스레드가 기존의 돌던 프로세서 아닌 애한테 가면 당연히 캐시 내용물 자기걸로 다시 채워야 함. 프로세서 당 개인 준비 큐 사용하면 스레드는 언제나 같은 프로세서에서 돌테니 따뜻한 캐시를 가질 것. 꽁 프로세서 친화도 ㄳ.

프로세서 친화도란 여러 형태를 가짐. 운영체제가 최대한 프로세스를 같은 프로세서에서 돌게 정책을 짰더라도, 그걸 보장하지 않으면 약친화도 soft affinity를 갖는다고 함. 여기선 프로세스를 한 프로세서에 유지는 하겠다고는 하지만 부하 분산 때 프로세스가 다른 프로세서로 이동될 수 있다는 것임. 반대의 경우는 강친화도 hard affinity로, 프로세스가 자기가 돌 프로세서들을 명시해주는 것임. 대부분의 체제들은 둘 다 갖고 있음. 리눅스는 약친화도를 구현했지만 sched_setaffinity() 시스템 호출로 실행 가능한 CPU 집합 명시하게 해주어 강친화도도 제공함.

시스템의 주메모리 구조도 프로세서 친화도에 영향을 줌. 아래 그림은 각자 CPU와 지역 메모리를 갖는 물리적인 프로세서 칩 두 개에서의 비균등 메모리 접근(NUMA)임. NUMA 체제에서 CPU 간 상호연결해서 서로 같은 메모리 공간을 사용하더라도 당연히 남의 메모리보다는 자기 메모리 접근이 더 빠름. 만약 운영체제의 CPU 스케줄러와 메모리 배정 알고리듬이 NUMA를 인식하고 있다면 특정 CPU에 스케줄링된 스레드는 해당 CPU와 제일 가까운 메모리에 할당이 될 것임.

흥미롭게도 부하 분산은 프로세서 친화도가 주는 이득과 반대로 작동하기도 함. 스레드를 다른 프로세서로 넘겨버리니까. NUMA 체제에서도 마찬가지로 프로세서 간 이동하면 페널티가 있음. 애초에 부하 분산이랑 메모리 접근 시간 줄이는 거랑 자연스레 경쟁 관계가 된다는 것임. 그래서 요즘 다중 코어 NUMA 체제에서 스케줄링하는 알고리듬은 상당히 복잡함. 5.7.1절에서 리눅스 CFS 스케줄링 알고리듬으로 이 두 가지 토끼를 어떻게 잡는지 균형 잡는 법을 볼 것.

5.5.5. 불균등 다중 프로세싱

지금까지는 프로세서가 전부 동일한 기능을 갖는다고 가정했음. NUMA 체제에서도 마찬가지로 프로세서 간 유일하게 서로 다른 점이라면 부하 분산과 프로세서 친화도 정책에 따라 메모리 접근 시간이 다르다는 점.

모바일도 이젠 다중 코어 구조지만 코어끼리 명령어 집합은 같은데 클럭 속도나 전력 관리가 서로 다를 수도 있음. 이런 체제가 바로 불균등 다중 프로세싱 heterogeous multiprocessing(HMP)임. 이건 5.5.1절의 비대칭 다중 프로세싱이랑 다른 것임. HMP의 경우 전력 관리 때문에 하는 것임.

ARM 프로세서 중 HMP 지원하는 애들을 big.LITTLE이라고 함. 고성능인 big 코어가 전력 소모 효율성이 좋은 LITTLE 코어랑 같이 쓰까있는 것임. Big 코어는 에너지 많이 먹으니 적은 시간 동안만 사용해야하고, little 코어는 오래 사용해야 함.

장점이 몇 가지 있는데, 성능 차이가 나다보니까 고성능 필요 없지만 오래 돌아야하는 애들은 little 코어에 할당해서 배터리 소모 줄임. 성능 중시하면서 짧게만 돌 상호작용 어플의 경우는 big 코어에 할당. 모바일 장치를 절전 모드에 놓을 때의 경우 big 코어를 비활성화시키기도 함. 윈도우즈 10에서 HMP 스케줄링 지원해서 전력 관리 요구에 적합한 스케줄링 정책 선택함.

5.6. 실시간 CPU 스케줄링

일반적으로 약실시간 체제와 강실시간 체제로 구분. 약실시간 체제 soft real-time system의 경우 중요한 실시간 프로세스가 언제 처리될지는 모름. 그냥 덜 중요한 애들보다는 우선권이 있다 수준임. 강실시간 체제 hard real-time system은 더 빡셈. 데드라인이 있음. 데드라인 지나면 서비스 유통기한 지났다고 간주해서 서비스 없는 걸로 간주함.

5.6.1. 지연 속도 최소화

실시간 체제가 이벤트 기반임을 우선 알아야 함. 보통 이벤트 발생할 때까지 대기하는데, 이벤트란 타이머 종료같은 소프트웨어 이벤트랑 센서처럼 하드웨어 이벤트 등이 있음. 여튼 이벤트 발생하면 최대한 빠르게 대응해야하는데, 이때 이벤트 발생 시간부터 서비스된 시간까지를 이벤트 지연 속도 event latency라 부름.

이벤트 별로 당연히 지연 속도 소요가 다름. 어떤 애는 3에서 5 ms 내로 처리해야할 수도 있고 몇 초까지 봐주는 경우도 있고.

실시간 체제의 성능에 영향을 주는 두 가지 지연 속도들:

인터럽트 지연 속도
디스패치 지연 속도

인터럽트 지연 속도란 인터럽트가 CPU에 도착하는 시점부터 이에 대응하는 서비스가 시작할 때까지를 의미함. 인터럽트 발생하면 운영체제는 일단 자기가 실행 중이던 명령어 끝내고 나서 무슨 인터럽트인지 확인. 현재 프로세스의 상태 저장하고 특정 인터럽트 서비스 루틴(ISR)에 따라 서비스를 함. 이때 걸린 총 시간이 인터럽트 지연 속도.

당연히 이 지연 속도 줄이는 게 좋음. 특히 강실시간 체제면 이걸 단순히 줄이는 게 아니라, 체제의 소요를 맞추기까지 해야 함.

인터럽트 지연 속도에 기여하는 요소 중 하나가 커널 자료 구조가 갱신 중에 얼마나 인터럽트가 비활성화되느냐임. 실시간 운영체제에서는 인터럽트를 정말 짧은 시간만 비활성화해야함.

한 프로세스를 멈추고 다른 걸 실행하기 위한 디스패처를 스케줄링하는데 걸리는 시간이 디스패치 지연 속도 dispatch latency. CPU에 즉시 접근해야하는 작업의 경우 이 지연 속도도 줄여야함. 가장 효과적인 방법은 선점적인 커널을 제공하는 것. 강실시간 체제의 경우 보통 몇 ms 수준임.

아래 그림이 디스패치 지연 속도.

디스패치 지연 속도의 충돌 단계 conflict phase는 두 성분으로 구성됨:

커널에서 도는 임의의 프로세스 선점
고우선순위 프로세스가 필요한 자원을 저우선순위 프로세스에서 뺏기

충돌 단계 이후엔 디스패치 단계가 고우선순위 프로세스를 CPU에 스케줄링.

5.6.2. 우선순위 기반 스케줄링

실시간 운영체제에서 제일 중요한 기능은 실시간 프로세스가 CPU가 필요할 때 즉시 대응하는 것임. 그러므로 실시간 운영체제는 반드시 선점적 우선순위 기반 알고리듬이어야 함.

선점적 우선순위 기반 스케줄링 알고리듬은 5.3.4절에서 다뤘고, 5.7절에서는 리눅스, 윈도우즈와 솔라리스 운영체제에서의 약실시간 스케줄링을 배움. 얘네도 실시간 프로세스가 우선순위 젤 높음. 윈도우즈는 우선순위가 32 단계임.

선점적 우선순위 기반 스케줄러만 갖고는 약실시간 밖에 안됨. 강실시간까지 가려면 마감 시간 소요까지 적용해야하므로 추가적인 스케줄링 기능 필요. 이 절의 남은 부분에서는 강실시간에 대한 내용만을 다룸.

각 스케줄러 다루기 전에 스케줄링할 프로세스의 특징을 봐야함. 우선 프로세스는 주기적 periodic임. 상수 기간(주기)마다 CPU를 필요로 한다는 뜻임. CPU 얻으면 고정된 처리 시간 t가 있고, CPU는 반드시 마감 기한 d 전에 처리해야 함. 또한 주기 p가 있음. 이 관계는 0 ≤ t ≤ d ≤ p임. 주기적 작업의 주기율 rate은 1/p. 아래 그림이 시간에 대한 주기적 프로세스의 실행에 대한 그림. 이를 바탕으로 스케줄러가 프로세스의 마감 기한이나 주기율 소요를 바탕으로 우선순위 배정.

특이한 점은 프로세스가 스케줄러에게 자기 마감 기한 지켜야 한다고 슈퍼을짓을 할 수 있다는 것임. 그러면 승인 제어 admission-control 알고리듬에 의해 스케줄러는 다음 둘 중 하나를 함. 프로세서의 요청을 ㅇㅈ해주고 시간 내에 해줄 수 있도록 보장해주거나, 마감 기한 내에 서비스 불가능해보이면 요청 씹음.

5.6.3. 비율 단조 스케줄링

비율 단조 rate-monotonic 스케줄링 알고리듬이란 정적 우선순위 정책을 통해 주기적 작업을 선점적으로 스케줄링함. 주기적 작업은 시스템에 들어온 순간 자기 주기의 역수를 우선순위로 가짐. 주기가 짧을 수록 우선순위가 높고 길수록 우선순위가 낮다는 소리임. 이 정책을 하는 이유는 CPU를 자주 쓰는 애한테 우선순위 계속 주겠다는 것임. 게다가 주기적 프로세스의 처리 시간이 각 CPU 버스트마다 동일하다고 가정함. 즉, 프로세스가 CPU 요청할 때마다 CPU 버스트가 동일하다는 것임.

예를 들어 두 프로세스 P1, P2가 있고, 각각 주기가 p1 = 50, p2 = 100이고, 처리 시간이 t1 = 20, t2 = 35라 가정. 마감 기한의 경우 각 프로세스마다 다음 주기 시작 전에는 CPU 버스트를 다 써야한다는 것임.

우선 마감 기한에 맞추어 스케줄링 가능한지를 봐야함. 프로세스의 CPU 효율을 버스트 대 주기, 즉 t/p라 가정하면 P1는 0.4, P2는 35/100으로, 총 75%임. 그러므로 마감 기한 시키면서 CPU 사이클에 여유분을 남길 수 있음.

P2가 P1보다 우선순위 높다고 가정하면 아래 그림처럼 될 것임. P2가 우선 실행되고, 시간 35에서 끝나고, 이후에 P1 시작하고 자기 CPU 버스트를 55에 끝냄. 근데 P1의 첫번째 마감 기한은 50이니까 스케줄러가 마감 기한 놓친 것임.

만약 비율 단조 스케줄링을 적용하면 P1이 우선순위가 더 높아질 것임. 이 경우엔 아래 그림처럼 P1이 먼저 시작하고 자기 CPU 버스트를 20에 끝내서 마감 기한 지킴. 다음 P2의 경우 50까지 돌고, 이 순간 5 ms가 남아있어도 P1에 의해 선점 당함. P1이 70에 종료되면 P2가 75에 종료되어 마감 기한 지킴. 100까지 가만히 있다가 다시 P1부터 재시작.

비율 단조 알고리듬은 프로세스가 이 알고리듬에 의해 스케줄링이 안된다면, 정적 우선순위를 갖는 다른 모든 알고리듬에서도 스케줄링이 안된다는 점에서 최적임. 이러한 예시 이제 볼 것.

P1의 주기 p1 = 50, CPU 버스트 t1 = 25. P2의 경우 p2 = 80, t2 = 35. 총 CPU 효율은 (25/50) + (35/80) = 0.94로 충분. 하지만 아래 그림 보면 알겠지만 우선순위가 더 높은 P1이 처리되고, P2처리하다가 선점적으로 P1이 다시처리. 얘 끝나고 P2해봤자 85에서 끝나서 마감 기한인 80이 지남.

최적이긴 한데 한 가지 한계점이 있음: CPU 효율이 유계이고, 언제나 CPU 자원을 100%로 최대화하기 힘듦. N 프로세스에 대한 CPU 효율 최악의 경우:

N(21/N - 1)

프로세스가 하나면 CPU 효율이 100%이지만 프로세스 수가 무한대로 갈수록 69%에 근사함. 프로세스 두 개면 83%. 사실 위의 예시에서도 효율이 75%라서 마감 기한 내에 스케줄링이 가능했다는 것임. 마지막 예시는 94%라서 마감 기한 내에 스케줄링하지 못했던 것임.

5.6.4. 최단 마감 우선 스케줄링

최단 마감 우선 earliest-deadline-first(EDF) 스케줄링은 마감 기한에 따라 동적으로 우선순위 부여함. 마감 기한이 빠른 순으로 우선순위 부여하는 것. 프로세스가 실행 가능할 때 반드시 시스템에 자기 마감 기한 소요를 알려서 우선순위 갱신해야 함. 비율 단조처럼 정적 우선순위가 아님.

위의 비율 단조의 마지막 예시를 EDF로 해본게 아래 그림. P1이 마감 기한 빠르니 우선순위 더 큼. 얘 끝나야 P2 실행. 근데 비율 단조와 달리 선점 안됨. P2 우선순위가 더 크니까. 그렇게 계속 가다가 145부터 150까지 놂.

비율 단조 알고리듬과 달리 프로세스가 굳이 주기적이지 않아도 되고, 버스트 당 상수 CPU 시간을 필요로 하지도 않음. 그냥 실행 가능할 때 마감 기한만 스케줄러한테 알려주면 됨. 이론적으론 최적이고, CPU 효율도 100%라는 점에서 매력적. 실무에서는 근데 프로세스 간 문맥 교환이랑 인터럽트 처리 때문에 그 수준의 CPU 효율은 불가능함.

5.6.5. 비례적 스케줄링

비례적 proportional share 스케줄러는 모든 어플리케이션에 T만큼의 지분을 할당해줌. 어플리케이션은 N 개의 시간 지분을 받을 수 있어 모든 어플리케이션이 총 프로세서 시간의 N/T를 가짐. 예를 들어 총 T = 100의 지분이 있고, 이걸 A, B, C에 각각 지분을 50, 15, 20으로 준다고 가정.

비례적 스케줄러는 승인 제어 정책과 같이 협력해서 어플리케이션이 자기 지분만큼의 시간을 받도록 보장해야 함. 물론 충분한 지분이 남아있어야 클라이언트의 요청을 받아줄 수 있음. 이 예시의 경우 50 + 15 + 20 = 85 지분이니 여유 있음. 만약 새 프로세스 D가 지분 30 요청하면 승인 제어가 D 입구컷 시킬 것임.

5.6.6. POSIX 실시간 스케줄링

POSIX.1b에 실시간 컴퓨팅 확장 기능 있음. POSIX의 실시간 스레드용 스케줄링 클래스 두 가지:

SCHED_FIFO
SCHED_RR

전자는 선도착 선처리 정책. 근데 동일 우선순위 스레드 간에는 시간 쪼개기 없음. 그러므로 우선순위가 제일 높은 실시간 스레드가 큐 맨 앞에 있으며, 종료하거나 막히기 전까지 CPU 부여 받음. 후자의 경우 라운드 로빈 정책. 전자와 유사하나 동일 우선순위 스레드 간에는 시간 쪼개기가 있음. 추가적인 스케줄링 클래스로 SCHED_OTHER가 있는데, 이건 따로 정의되어있지 않고, 시스템에 따라 달라서 시스템별로 다르게 작동함.

POSIX API에는 스케줄링 정책 불러오거나 설정할 때 다음 함수 사용:

pthread_attr_getschedpolicy(pthread_attr_t* attr, int* policy)
pthread_attr_setschedpolicy(phtread_att_t* attr, int policy)

첫번째 매개변수는 스레드의 속성 집합을 가리키는 포인터. 두번째 매개변수는 (1) 현재 스케줄링 정책을 불러올 정수 포인터, (2) SCHED_FIFO, SCHED_RR, SCHED_OTHER 등의 스케줄링 정책으로 설정할 정수값. 둘 다 오류 발생 시 0이 아닌 값을 반환함.

아래 코드가 예시. 현재 스케줄링 정책을 확인하고 스케줄링 알고리듬을 SCHED_FIFO로 설정함.

#include <pthread.h>
#include <stdio.h>

#define NUM_THREADS 5

void* runner(void* param);

int main(int argc, char* argv[])
{
	int i = 0;
	int policy = 0;
	pthread_t tid[NUM_THREADS];
	pthread_attr_t attr;

	/* 기본 속성 불러오기 */
	pthread_attr_init(&attr);

	/* 현재 스케줄링 정책 불러오기 */
	if (pthread_attr_getschedpolicy(&attr, &policy) != 0) {
		fprintf(stderr, "Unable to get policy.\n");
	} else {
		if (policy == SCHED_OTHER) {
			printf("SCHED_OTHER\n");
		} else if (policy == SCHED_RR) {
			printf("SCHED_RR");
		} else if (policy == SCHED_FIFO) {
			printf("SCHED_FIFO\n");
		}
	}

	/* 스케줄링 정책을 FF, RR, 혹은 OTHER로 설정 */
	if (pthread_attr_setschedpolicy(&attr, SCHED_FIFO) != 0) {
		fprintf(stderr, "Unable to set policy.\n");
	}

	/* 스레드 생성 */
	for (i = 0; i < NUM_THREADS; ++i) {
		pthread_create(&tid[i], &attr, runner, NULL);
	}

	/* 각 스레드 별로 조인 */
	for (i = 0; i < NUM_THREADS; ++i) {
		pthread_join(tid[i], NULL);
	}

	return 0;
}

/* 각 스레드는 이 함수에서 제어를 시작 */
void* runner(void* param)
{
	/* do some work ... */

	pthread_exit(0);
}

5.7. 운영체제 예시

여기서 프로세스 스케줄링을 일반적인 의미로 사용할 것. 사실상 솔라리스와 윈도우스 체제에서는 커널 스레드 스케줄링, 리눅스에서는 작업을 스케줄링한다고 할 것임.

5.7.1. 예시: 리눅스 스케줄링

리눅스 커널은 2.5 버전 전까지 전통적인 UNIX 스케줄링 알고리듬에서 돌았음. 근데 이건 SMP 체제를 고려한 게 아니라서 다중 프로세서를 잘 지원하지 못함. 게다가 프로세스 여러 개 실행하면 성능 떨어짐. 2.5 버전 이후부터는 O(1)이라 불리는 스케줄링 알고리듬이 추가되어 시스템의 작업 개수와 상관 없이 상수 시간에 돎. 또한 SMP 체제를 지원해 프로세서 친화도와 부하 분산을 지원함. 실무에서 O(1) 스케줄러가 SMP 시스템에선 훌륭한 성능을 보였으나 상호작용 프로세스에선 반응 속도가 별로였음. 2.6 커널 개발 땐 다시 수정 시작해서 2.6.23부터 *완전 공정 스케줄러 completely fair scheduler(CFS)가 리눅스 스케줄링 알고리듬의 기본이 됨.

리눅스 스케줄링은 스케줄링 클래스 scheduling class에 기반함. 각 클래스엔 특정 우선순위가 부여됨. 서로 다른 스케줄링 클래스를 통해 커널이 시스템의 요구와 프로세스에 따라 적합한 스케줄링 클래스를 적용함. 리눅스 서버의 경우 리눅스에서 도는 모바일과 당연히 스케줄링 평가 기준이 다를 것임. 즉, 우선순위가 제일 높은 스케줄링 클래스가 판단하는 가장 우선순위가 높은 작업을 다음에 돌릴 것임. 표준 리눅스 커널은 두 스케줄링 클래스를 구현함: (1) CFS 스케줄링 알고리듬을 이용한 기본 스케줄링 클래스와 (2) 실시간 스케줄링 클래스. 당연히 새로운 스케줄링 클래스 추가 가능.

CFS 스케줄러는 상대적 우선순위 값과 시간 단위의 길이 대신 각 작업에 CPU 처리 시간의 일부를 할당함. 이 비율은 각 작업에 할당된 배려 값 nice value에 기반해서 계산됨. 배려 값은 -20에서 19 사이로, 낮을 수록 더 높은 상대적 우선순위를 가짐. 기본 배려 값은 0임. (배려 nice라는 건 작업의 배려 값이 증가할 수록 자기 우선순위가 내려가니 남들 배려한다는 뜻임.) 이산적인 시간 단위 값을 사용하지 않고, 목표 지연 속도 targeted latency를 사용함. 이건 각 실행 가능한 작업이 최소한 한 번 실행될 수 있는 시간 간격을 의미함. 목표 지연 속도는 기본 값과 최소 값이 있을 뿐만 아니라 시스템의 활성화 작업이 특정 기준을 넘어갈 수록 증가함.

CFS 스케줄러는 직접적으로 우선순위를 부여하지 않고 작업 별로 vruntime이라는 변수를 통해 가상 실행 시간 virtual run time이라는 것을 통해 각 작업이 얼마나 오래 실행됐는지를 기록함. 가상 실행 시간은 작업의 우선순위에 기반한 감소 요소에 영향을 받음: 우선순위가 낮은 작업은 우선순위가 높은 작업보다 더 높은 감소율을 가짐. 일반적인 우선순위를 갖는 작업의 경우(배려 값이 0인 경우) 가상 실행 시간은 실제 물리적 실행 시간과 동일함. 그렇기에 기본 우선순위를 갖는 작업이 200 ms만큼 실행되면 vruntime은 200 ms보다 클 것임. 마찬가지로 우선순위가 높은 작업이라면 vruntime은 200 ms보다 작을 것임. 스케줄러는 다음에 어떤 작업을 실행할 지는 단순히 가장 작은 vruntime을 갖는 작업을 고름. 추가적으로 당장 실행이 가능한 우선순위가 높은 작업은 우선순위가 낮은 작업을 선점할 수 있음.

실제 CFS가 작동하는 법: 두 작업이 같은 배려 값을 갖는다고 가정. 하나는 입출력 제약이고 다른 하나는 CPU 제약이라고 가정. 일반적으로 입출력 제약 작업은 추가적인 입출력에 의해 막히기 전까지 짧은 시간만큼 실행되고 CPU 제약 작업은 프로세서에서 실행될 기회가 있기만 하면 시간을 소비함. 그러므로 우선순위가 더 높은 입출력 제약 작업이 vruntime의 값이 더 낮을 것임.

리눅스는 POSIX 표준 바탕의 실시간 스케줄링을 구현했음. SCHED_FIFO나 SCHED_RR 실시간 정책으로 스케줄링된 모든 작업은 일반적인 작업(비실시간 작업)보다 높은 우선순위를 갖고 실행됨 리눅스엔 두 가지 서로 다른 우선순위 범위가 존재함. 하나는 실시간용이고, 다른 하나는 일반적인 작업용임. 실시간은 0에서 99의 폐구간에서의 정적 우선순위를 할당받고, 일반적인 작업은 100에서 139의 폐구간에서의 우선순위를 할당받음. 이 두 영역의 값은 결국 전체적으로보면 수치적으로 낮은게 상대적으로 우선순위가 더 높다는 전역 우선순위 스킴을 가짐. 일반적인 작업에는 배려 값에 따라 우선순위를 받는데, 값이 -20이면 우선순위가 100이고, 값이 +19이면 139으로 매핑됨.

CFS는 부하 분산을 프로세싱 코어 간 부하를 동일하게 유지하면서도 NUMA를 인식하며 스레드 간의 이동을 최소화하는 복잡한 기술을 통해 지원함. CFS에서는 각 스레드의 부하를 스레드의 우선순위와 해당 스레드의 평균 CPU 활용률의 조합으로 정의함. 그러므로 우선순위가 높으면서도 입출력 제약을 대부분 처리 중이라 CPU 활용률이 낮은 스레드는 일반적으로 우선순위는 낮지만 CPU 활용률은 높은 스레드와 비슷한 수준으로 낮은 부하를 받음.

5.5.4. 절에서 언급했듯 스레드 간 이동에는 비유효 캐시 내용물을 갖게 되거나 NUMA 체제에서는 메모리 접근 시간이 길어지는 등 메모리 접근에 문제가 생길 수 있음. 이를 해결하기 위해 리눅스는 스케줄링 영역 scheduling domain이라는 서로 부하 분산이 가능한 CPU 코어 집합의 계층적 체제를 사용함. 아래 그림에서 이를 볼 수 있음. 각 코어는 시스템에서 자원을 어떻게 공유하느냐에 따라 스케줄링 영역으로 집합을 이루고 있음. 예를 들어 아래 그림에서 각 코어가 자신만의 1수준(L1) 캐시를 갖는 것처럼 보이지만 코어의 짝이 2수준(L2) 캐시를 공유하므로 각각 영역0과 영역1로 독립적으로 조직화됨. 당연히 이 둘 사이엔 공유하는 3수준(L3) 캐시가 있을 수도 있어 프로세서 단 영역으로 조직화될 수 있음(이를 NUMA 노드 NUMA node라 부름). 여기서 한 단계 더 나아가면 NUMA 체제에서는 시스템 단 영역이 클 수록 서로 다른 프로세서 단 NUMA 노드를 결합시킬 것임.

CFS의 영역 내 일반적인 부하 분산 전략은 가장 하위 계층에서부터 시작함. 위의 그림을 예시로 들면, 우선 스레드는 오로지 같은 영역 내의 스레드에서만 이동함. 다음 수준에서의 부하 분산은 영역0과 영역1 간에 이루어질 것임. CFS는 스레드가 자신의 지역 메모리에서 몰어질 것 같으면 서로 다른 NUMA 노드 간에 이동을 잘 하려고 하지 않기에 이런 이동은 오로지 부하가 심각하게 불균형이 일어났을 때만 처리해줘야함. 일반적으로 전체 시스템이 바쁘면 CFS는 NUMA 체제에서 메모리 지연 속도 문제를 피하기 위해 각 코어에 지역적인 영역을 벗어난 수준으로 부하 분산하지 않을 것임.

5.7.2. 예시: 윈도우즈 스케줄링

윈도우즈는 우선순위 기반 선점적 스케줄링 알고리듬을 사용함. 윈도우즈 스케줄러는 우선순위가 가장 높은 스레드가 언제나 실행됨을 보장함. 윈도우즈 커널에서 스케줄링을 처리하는 부분을 디스패처 dispatcher라 부름. 디스패처가 실행하려고 선택한 스레드는 다른 우선순위가 더 높은 스레드에 의해 선점되기 전까지, 혹은 종료될 때까지, 혹은 시간 할당량이 끝날 때까지, 혹은 입출력과 같이 막는 시스템 호출을 하기 전까지 실행됨. 우선순위가 낮은 스레드가 실행 중에 우선순위가 높은 스레드가 준비 상태가 되면 선점당함. 이런 선점을 통해 실시간 스레드가 CPU 필요할 때마다 줄 수 있음.

디스패처는 스레드 실행의 순서를 결정하기 위해 32-수준 우선순위 스킴을 사용함. 우선순위는 두 가지 클래스로 구분함. 가변 클래스 variable class는 1부터 15까지의 우선순위를 가지며, 실시간 클래스 real-time class는 16부터 31까지의 우선순위를 가짐. (메모리 관리에 사용되는 우선순위 0의 스레드도 있긴 함) 디스패처는 각 스케줄링 우선순위마다 큐를 사용하며, 높은 것부터 낮은 것 순으로 준비 상태의 스레드를 각 큐에서 찾음. 준비 상태의 스레드가 없다면 디스패처는 유휴 스레드 idle thread라는 특수한 스레드를 실행함.

윈도우즈 커널과 윈도우즈 API의 우선순위 값 사이에는 관계가 존재함. 윈도우즈 API는 다음에 속할 수 있는 6 가지 우선순위 클래스를 가짐:

IDLE_PRIORITY_CLASS
BELOW_NORMAL_PRIORITY_CLASS
NORMAL_PRIORITY_CLASS
ABOVE_NORMAL_PRIORITY_CLASS
HIGH_PRIORITY_CLASS
REALTIME_PRIORITY_CLASS

일반적으로 프로세스들은 프로세스의 부모가 IDLE_PRIORITY_CLASS이거나 프로세스가 생성될 때 클래스를 따로 명시해준 경우가 아니면 NORMAL_PRIORITY_CLASS에 속함. 프로세스의 우선순위 클래스는 윈도우즈 API의 SetPriorityClass() 함수를 통해 수정해줄 수 있음. REALTIME_PRIORITY_CLASS를 제외한 모든 클래스는 가변적이므로 우선순위 클래스를 변경시켜줄 수 있음.

동일한 우선순위 클래스 내에서도 상대적인 우선순위를 가짐:

IDLE
LOWEST
BELOW_NORMAL
NORMAL
ABOVE_NORMAL
HIGHEST
TIME_CRITICAL

각 스레드의 우선순위는 자기가 속한 우선순위 클래스와 그 클래스 내에서의 상대적인 우선순위에 따라 결정됨. 아래 그림에서 확인할 수 있음. 우선순위 클래스의 값이 위 행에 나와있음. 왼쪽 열이 상대적 우선순위 값을 가짐.

추가적으로 각 스레드는 본인이 속한 클래스의 우선순위 범위 내의 값을 의미하는 기반 우선순위를 가짐. 기본적으로 기반 우선순위의 값은 상대 우선순위 NORMAL인 값임. 각 우선순위 클래스의 기반 우선순위는 다음과 같음:

REALTIME_PRIORITY_CLASS - 24
HIGH_PRIORITY_CLASS - 13
ABOVE_NORMAL_PRIORITY_CLASS - 10
NORMAL_PRIORITY_CLASS - 8
BELOW_NORMAL_PRIORITY_CLASS - 6
IDLE_PRIORITY_CLASS - 4

스레드의 초기 우선순위는 스레드가 속한 프로세스의 기반 우선순위임. 물론 윈도우즈 API의 SetThreadPriority() 함수로 스레드의 기반 우선순위를 변경해줄 수 있음.

스레드가 시간 할당량 다 사용하면 인터럽트가 됨. 만약 스레드가 가변 우선순위 클래스에 속했다면 우선순위가 낮아지게 됨. 물론 기반 우선순위보다 낮아지지는 않음. 우선순위를 낮추는 것으로 연산 제약 스레드의 CPU 소비를 제어할 수 있게 됨. 가변 우선순위 스레드가 대기 연산에서 풀리면 디스패처는 우선순위를 높여줌. 높여주는 정도는 스레드가 무엇을 대기했느냐에 따라 다름. 스레드가 키보드 입출력을 대기했다면 많이 높여줄거고, 디스크 연산을 대기했다면 적당히 높여줄 것임. 이 전략을 통해 마우스와 창을 사용하는 상호작용 스레드에 좋은 반응 속도를 줄 수 있게 됨. 또한 입출력 제약 스레드가 입출력 기기들을 바쁘게 만들어 연산 제약 스레드가 남는 CPU 사이클을 배경에서 사용할 수 있도록 해줌. 이 전략은 UNIX 등의 다른 운영체제에서도 사용함. 추가적으로 사용자가 현재 상호작용 중인 창 내에서는 반응 속도 개선을 위해 우선순위가 높아지게 됨.

사용자가 상호작용 프로그램을 실행 중이라면 체제는 더 좋은 성능을 보장해야함. 그래서 윈도우즈는 NORMAL_PRIORITY_CLASS의 프로세스에 대해 좀 특별한 스케줄링 규칙을 갖고 있음. 윈도우즈는 현재 화면에서 선택된 전면 프로세스 foreground process와 선택되지 않은 배경 프로세스 background process를 구분함. 프로세스가 전면 프로세스가 되면 어떤 계수만큼(보통 3) 스케줄링 할당량을 늘려줌. 이러면 전면 프로세스가 시간 공유 선점 당하기 전까지의 시간(즉, 자기 시간 할당량)이 전보다 세 배나 더 늘어남.

윈도우즈 7에선 사용자 모드 스케줄링 user-mode scheduling(UMS)이라는게 나오는데, 어플리케이션이 커널과 독립적으로 스레드를 생성하고 관리할 수 있도록 해줌. 스레드 여러 개 만드는 어플리케이션의 경우 스레드를 굳이 커널의 간섭 없이 사용자 모드에서 스케줄링하는게 더 효율적임.

초기 윈도우즈에서는 섬유 fiber라는 비슷한 기능이 있어 여러 사용자 모드 스레드(섬유)를 하나의 커널 스레드에 매핑될 수 있도록 했었음. 근데 실무에서 한정적으로 사용되었음. 우선 모든 섬유는 자기가 실행 중인 스레드의 스레드 환경 블록(TEB)을 공유했기에 윈도우즈 API를 호출할 수 없었음. 그래서 만약 윈도우즈 API 함수가 상태 정보를 한 섬유를 갖는 TEB에 넣어준다면 나중에 어차피 다른 섬유가 이 정보를 덮어 쓸 것임. UMS가 사용자 모드 스레드마다 각 스레드 문맥을 제공하는 것으로 이를 해결함.

섬유와는 달리 UMS는 프로그래머가 직접 사용하도록 의도된 것이 아님. 사용자 모드 스케줄러 작성하는 건 힘들고, 그런게 UMS에 있지도 않음. 대신 UMS 위에 얹을 수 있는 프로그래밍 언어 라이브러리에서 스케줄러를 갖고 옴. 예를 들어 마이크로소프트는 동시성 런타임 Concurrency Runtime(ConcRT)를 통해 C++의 동시성 프로그래밍 프레임워크를 제공함. 이 프레임워크는 다중 코어 프로세서에서의 작업 기반 병렬화(4.2절)를 위해 설계됨. ConcRT는 사용자 모드 스케줄러에 프로그램을 작업으로 분해하는 기능을 추가해 이를 프로세싱 코어 간 스케줄링 될 수 있도록 해줌.

윈도우즈는 또한 5.5. 절에서 언급했던 다중 프로세스 체제 스케줄링도 지원함. 이는 스레드를 해당 스레드 입장에서 가장 최적의 프로세싱 코어에 스케줄링을 시도하는 것으로 처리함. 이는 스레드가 선호하는, 그리고 가장 최근에 사용한 프로세서를 추적하는 것으로 처리함. 윈도우즈가 사용하는 방법 중 하나로는 논리적인 프로세서의 집합(SMT 집합 SMT set이라 부름)을 생성하는 것이 있음. 하이퍼 스레딩된 SMT 체제에서 같은 CPU 코어에 속한 하드웨어 스레드는 마찬가지로 동일한 SMT 집합에 속함. 논리 프로세서는 0부터 시작하는 숫자를 부여받음. 예를 들어 이중 스레드/4중 코어 체제에서는 총 8 개의 논리 프로세스를 가지며, 네 개의 SMT 집합을 가짐: {0, 1}, {2, 3}, {4, 5}, {6, 7}. 5.5.4. 절에서 언급한 캐시 메모리 접근 문제를 피하기 위해 스케줄러는 스레드가 동일한 SMT 집합 내의 논리 프로세서에서 실행되도록 함.

서로 다른 논리 프로세스 간 부하 분산을 하기 위해 각 스레드는 스레드의 선호 프로세서를 의미하는 숫자인 이상 프로세서 ideal processor에 할당됨. 각 프로세스는 자신이 속한 프로세스의 이상 CPU를 의미하는 초기 시드 값을 가짐. 이 시드는 프로세스에서 새 스레드를 생성할 때마다 증가하여 서로 다른 논리 프로세스 간 부하를 분산함. SMT 체제에서는 다음 이상 프로세서를 위한 증가는 곧 다음 SMT 집합을 의미함. 예를 들어 이중 스레드/4중 코어 체제에서 특정 프로세스의 스레드에 대한 이상 프로세서는 0, 2, 4, 6, 0, 2, … 순으로 증가함. 각 프로세스의 첫번째 스레드가 전부 프로세스 0을 할당 받지 않게 하기 위해 프로세스는 서로 다른 시드 값을 갖게 되어 스레드의 부하를 체제 내의 모든 물리적 프로세싱 코어에 대해 분산하게 해줌. 위의 예시에서 계속하자면, 만약 두번째 프로세스의 시드가 1이라면 이상 프로세서는 1, 3, 5, 7, 1, 3 순으로 할당 받을 것임.

5.7.3. 예시: 솔라리스 스케줄링

솔라리스는 우선순위 기반 스레드 스케줄링 사용함. 각 스레드는 다음 여섯 가지 클래스 중 하나에 속함:

시간 공유 (TS)
상호작용 (IA)
실시간 (RT)
체제 (SYS)
공평 공유 (FSS)
고정 우선순위 (FP)

각 클래스마다 우선순위가 다르며, 스케줄링 알고리듬도 달라짐.

기본 스케줄링 클래스는 시간 공유. 시간 공유 클래스의 스케줄링 정책은 우선순위를 동적으로 변경하고, 다단계 피드백 큐를 통해 길이가 다른 시간 단위를 할당함. 기본적으로 우선순위와 시간 단계 사이엔 반비례 관계를 가짐. 상호작용 프로세스는 보통 높은 우선순위를 갖고, CPU 제약 프로세스는 낮은 우선순위를 가짐. 이 정책을 통해 실시간 프로세스에는 좋은 반응 시간을 제공하고, CPU 제약 프로세스에게는 좋은 처리율을 제공함. 상호작용 클래스의 스케줄링 정책은 시간 공유 클래스의 정책과 동일하지만, 이는 창 어플리케이션에게 부여됨. 즉, KDE나 GNOME 창 관리자가 생성한 창 어플리케이션에게 성능을 위해 더 높은 우선순위를 부여함.

아래 그림이 시간 공유와 상호작용 스레드 스케줄링할 때 사용할 디스패치 표를 단순화한 것임. 이 두 스케줄링 클래스는 60 개의 우선순위 단계를 가지지만, 간단하게 표현하기 위해 몇가지만 소개함. (전체 디스패치 표를 보고 싶다면 솔라리스 체제나 VM에서 dispadmin -c TS -g 명령어를 실행하면 됨.) 디스패치 표는 다음 내용을 담고 있음:

우선순위 priority. 클래스(시간 공유 / 상호작용)에 의해 결정. 숫자가 높을 수록 우선순위가 높음.
시간 할당량 time quantum. 우선순위와 반비례 관계: 최저 우선순위(우선순위 0)가 최다 시간 할당량(200 ms)을 가지며, 최고 우선순위 (우선순위 59)가 최소 시간 할당량(20 ms)을 가짐.
시간 할당량 만료 time quantum expired. 막히지 않고 시간 할당량을 전부 사용한 스레드의 새 우선순위. 이런 스레드는 CPU에 집중하는 것으로 간주함. 표에서 보이듯, 이런 스레드는 우선순위가 낮춰짐.
수면에서 복귀 return from sleep. 수면 상태(입출력을 위한 대기 등)에서 벗어난 스레드의 우선순위. 표에서 보이듯 입출력이 대기 스레드에서 사용 가능하다면 우선순위가 50에서 59 사이 수준으로 증가하여 상호작용 프로세스의 좋은 반응 속도를 제공하는 스케줄링 정책을 지원함.

실시간 클래스가 가장 우선순위가 높음. 실시간 프로세스는 다른 클래스의 프로세스 이전에 실행이 됨. 이를 통해 실시간 프로세스는 정해진 기간 내에 시스템으로부터 응답이 보장됨. 허나 일반적으로 실시간 프로세스에 속하는 건 적음.

솔라리스는 커널 스레드를 돌릴 때 스케줄러나 페이징 다이몬과 같은 시스템 클래스를 사용함. 시스템 스레드의 우선순위가 정해지면 변하지 않음. 시스템 클래스는 커널에서 사용하도록 예약이 됨(커널 모드에서 도는 사용자 프로세스는 시스템 클래스가 아님).

고정 우선순위 및 공평 공유 클래스는 솔라리스 9에서 처음 나옴. 고정 우선순위 클래스 스레드는 시간 공유 클래스와 같은 우선순위 범위를 갖지만 동적으로 우선순위가 변하지 않음. 공평 공유 클래스는 우선순위 대신 CPU 지분 share을 통해 스케줄링이 됨. CPU 지분이란 사용 가능한 CPU 자원에 대한 사용 권리를 의미하며, 프로세스의 집합(프로젝트 project라 부름)에 할당됨.

각 스케줄링 클래스는 여러 우선순위를 가짐. 하지만 스케줄러는 클래스에 특정된 우선순위를 전역 우선순위로 치환하여 가장 우선순위가 높은 스레드를 선택함. 이 스레드는 CPU에서 (1) 막히거나 (2) 시간 단위 다 쓰거나 (3) 더 높은 우선순위 스레드에 의해 선점되기 전까지 실행됨. 만약 같은 우선순위를 갖는 여러 스레드가 존재할 경우 라운드 로빈 큐를 사용함. 아래 그림이 여섯가지 스케줄링 클래스가 어덯게 연관이 되어있고, 전역 우선순위에 어떻게 매핑이 되는지를 의미함. 커널이 인터럽트를 처리하기 위해 열 개의 스레드를 사용함에 주목. 이 스레드는 그 어떠한 스케줄링 클래스에도 속하지 않으며 가장 높은 우선순위(160-169)를 가짐. 언급했듯이 솔라리스는 전통적으로 다대다 모델(4.3.3. 절)을 사용했으나 솔라리스 9 이후부터는 일대일 모델(4.3.2. 절)을 사용하기 시작.

5.8. 알고리듬 평가

특정 체제를 위한 CPU 스케줄링 알고리듬을 선택하는 건 어려움.

첫번째 문제: 알고리듬 정할 기준 정하기. 5.2. 절에서 보았듯 CPU 활용, 반응 시간, 처리율 등의 따라 기준이 정해짐. 이런 기준들을 정해야함. 예시:

최대 반응 시간이 300 ms일 때 CPU 효용 최대화
턴어라운드 시간이 (평균적으로) 전체 실행 시간에 선형적으로 비례하도록 처리율 최대화

기준만 정하면 알고리듬을 이 기준에 따라 평가하면 됨.

5.8.1. 결정적 모델링

대표적인 평가 방법 중 하나가 분석적 평가 analytic evaluation임. 주어진 알고리듬과 시스템 작업량을 통해 공식이나 숫자를 통해 작업량에 대한 알고리듬의 성능을 평가하는 것임.

결정적 모델링 deterministic modeling이란 분석적 평가 방법 중 하나. 이 방법은 특정 사전정의된 작업량을 받아 이 작업량에 대해 각 알고리듬의 성능을 정의하는 것임. 예를 들어 아래와 같이 작업량을 갖고 있다고 가정. 이 다섯 개의 프로세스가 전부 시간 0에 도착하며, 주어진 순서에 따라 CPU 버스트 시간을 ms 단위로 주어짐:

프로세스	버스트 시간
P1	10
P2	29
P3	3
P4	7
P5	12

이 프로세스 집합에 대해 FCFS, SJF, RR(할당량 = 10 ms) 스케줄링 알고리듬을 적용한다고 가정하면 어떤 알고리듬이 최소 평균 대기 시간?

FCFC:

평균 대기 시간은 (0 + 10 + 39 + 42 + 49) / 5 = 28 ms.

비선점적 SJF 스케줄링:

평균 대기 시간은 (10 + 32 + 0 + 3 + 20) / 5 = 13 ms.

RR 알고리듬:

평균 대기 시간은 (0 + 32 + 20 + 23 + 40) / 5 = 23 ms.

SJF 정책의 평균 대기 시간이 FCFS 스케줄링의 시간의 절반이고, RR 알고리듬은 그 중간 값을 가짐.

결정적 모델은 단순하면서 빠름. 정확한 숫자를 얻을 수 있어 알고리듬 간 비교가 가능. 허나 정확한 입력의 정확한 값이 필요하고, 이에 대한 답이 정확히 그 경우에만 적용됨. 결정적 모델링의 주된 용도는 스케줄링 알고리듬을 설명하고 예시를 제시할 때임. 같은 프로그램을 계속해서 실하기에 프로그램의 처리 소요를 정확하게 측정할 수 있을 때 정도면 결정적 모델링을 사용할 수는 있을 것. 또한 여러 예시에 대해서 결정적 모델링을 적용할 시 일종의 트렌드를 분석하고 독립적으로 증명할 수 있음. 예를 들어 위의 예시 환경에서 SJF 정책은 언제나 최소의 대기 시간을 제공함.

5.8.2. 큐 모델

대부분의 체제에서 실행하는 프로세스들은 매일마다 달라져서 결정적 모델링으로 사용할 정적 프로세스 집합(혹은 시간)이 없음. 유일하게 결정할 수 있는 것은 CPU와 입출력 버스트의 분포임. 이런 분포를 측정하여 근사하거나 단순히 추정함. 결과적으로 특정 CPU 버스트에 대한 확률을 의미하는 수학적 공식을 얻게 됨. 보통 이 분포는 지수적이며 그 평균으로 작성 가능. 유사하게 프로세스가 시스템에 도달하는 시간도 분포를 구할 수 있음(도착 시간 분포). 이 두 분포로부터 대부분의 알고리듬의 평균 처리율, 효용, 대기 시간을 구할 수 있음.

컴퓨터 체제란 서버의 네트워크임. 각 서버는 대기 프로세스의 큐를 가짐. CPU는 대기 큐를 갖는 서버이며 입출력 체제도 마찬가지로 장치 큐를 가짐. 도착률과 서비스율만 알면 효용, 평균 큐 길이, 평균 대기 시간 등을 구할 수 있음. 이런 걸 공부하는 분야를 큐 네트워크 분석 queueing network analysis라 부름.

만약 n이 평균 장기 큐 길이(서비스 중인 프로세스 제외)라 가정하고, W가 큐에서의 평균 대기 시간이라 가정하고 λ가 큐의 새 프로세스의 평균 도착율이라 가정(예를 들어 초당 세 프로세스). 프로세스가 대기하는 시간 W 동안 λ × W 만큼 새 프로세스가 큐에 도착함. 시스템이 안정된 상태라면 큐를 떠나는 프로세스의 개수는 들어온 프로세스의 개수와 같아야 하므로,

n = λ × W

이 방정식을 리틀 공식 Little's formula라 부름. 이건 모든 스케줄링 알고리듬과 도착 분포에 대해 유효하기에 유용함. 예를 들어 n이 상점 안의 고객의 수일 수도 있음.

리틀 공식을 통해 나머지 두 미지수가 무엇인지 안다면, 다른 하나를 구할 수 있음.

큐 분석은 스케줄링 알고리듬 비교할 땐 유용하지만 한계가 있긴 함. 당장은 처리할 수 있는 알고리듬이나 분포의 클래스가 한정되어있음. 복잡한 알고리듬과 분포의 수학은 처리하기에 복잡한 편임. 그러므로 도착 및 서비스 분포는 보통 수학적으로 다루기 쉬운 것, 즉 덜 현실적인 방법으로 정의함. 게다가 몇가지 독립적인 가정(정확하지 않을 수도 있는 가정들임)들을 일반적으로 해야 함. 이런 문제들 때문에 큐 모델이 실제 체제의 근사로서 사용할 뿐이라 정확하지 않을 수도 있음.

5.8.3. 시뮬레이션

스케줄링 알고리듬을 좀 더 정확하게 평가하려면 시뮬레이션을 해보면 됨. 시뮬레이션을 돌리려면 컴퓨터 체제를 모델링을 해줘야함. 체제의 핵심 성분을 표현하는 소프트웨어 자료 구조를 정해야함. 시뮬레이터는 시계를 의미하는 변수를 가짐. 이 변수의 값이 증가할 때마다 시뮬레이터는 체제의 상태가 장치의 활동, 프로세스, 스케줄러를 반영할 수 있는 상태로 변경해줌. 시뮬레이션이 실행하면서 알고리듬의 성능을 의미하는 통계를 수집하고 출력해줌.

시뮬레이션을 돌릴 데이터는 여러 방법으로 생성 가능. 가장 일반적인 방법은 확률 분포를 바탕으로 난수 생성을 통해 프로세스, CPU 버스트 시간, 도착, 출발 등을 생성. 분포는 수학적(균일, 지수, 푸아송)으로든 경험적으로든 정의해주면 됨. 만약 분포를 경험적으로 정의한다면 실제 체제에 대한 측정이 이미 이루어져있어야 함. 이 결과가 실제 체제의 이벤트에 대한 분포를 정의하게 됨. 이 분포를 바탕으로 시뮬레이션 돌리면 됨.

분포 기반 시뮬레이션은 실제 체제에서 연속된 이벤트 간의 관계 때문에 정확하진 않을 수 있음. 빈도 분포는 각 이벤트가 얼마나 발생했는지를 의미하지, 발생 간의 순서에 대한 내용은 없음. 이 문제를 해결하려면 추적 파일 trace file을 사용하면 됨. 아래 그림처럼 실제 체제를 모니터링하고 실제 이벤트를 순서대로 기록하는 것으로 추적을 생성할 수 있음. 이제 이 순서를 바탕으로 시뮬레이션하면 됨. 추적 파일은 정확히 똑같은 실제 입력에 대해 두 알고리듬을 비교하기 좋은 방법을 제공함. 정확한 결과를 얻을 수 있음.

시뮬레이션은 보통 비싸고 시간도 오래걸림. 시뮬레이션에 디테일이 추가될 수록 결과의 정확도는 올라가지만 컴퓨터 시간도 더 오래 걸림. 게다가 추적 파일도 저장 공간을 많이 먹을 것임. 게다가 시뮬레이터의 설계, 코딩, 디버깅이 중요 작업임.

5.8.4. 구현

시뮬레이션도 정확도가 떨어지므로, 정확하게 스케줄링 알고리듬을 평가할 수 있는 유일한 방법은 직접 구현해보고 운영체제에 넣어 어떻게 도는지 보는 것임.

비용이 없는 것은 아님. 알고리듬을 구현하고 운영체제가 이를 지원하도록(필수 자료구조도 마찬가지) 수정하는 것이 바로 비용임. 또한 변경 사항에 대해 테스트를, 심지어 실제 전용 하드웨어가 아닌 가상 기계에서 테스트하는 비용도 듦. 회귀 테스트 regression test를 통해 변경 사항이 아무 것도 악화시키지 않았으며, 새로운 버그나 옛 버그를 야기하지 않았음(새 알고리듬으로 교체하느라 기존에 버그 처리하던 코드가 사라져서 발생할 수도 있음)을 확인해줘야 함.

다른 문제로는 알고리듬이 사용될 환경도 변경된다는 것임. 새로운 프로그램이 작성되고 문제의 유형도 바뀌는 것에 의해 일반적인 방법으로 환경이 변하는 것 외에도 스케줄러의 성능에 의해 환경이 변하는 부분도 있음. 만약 짧은 프로세스에게 우선순위를 부여한다면, 프로그래머들이 긴 프로세스를 짧은 걸로 나눌 수도 있음. 만약 상호작용 프로세스에게 우선순위를 부여한다면 사용자가 상호작용 용도로 교체할 수도 있음.이 문제는 보통 모든 액션을 캡슐화한 도구나 스크립트를 통해, 그리고 이 도구를 반복적으로 사용하고 이 도구로 결과를 측정함으로써(그리고 새 환경에서 이들이 야기할 문제를 검출함으로써) 알 수 있음.

물론 사람이나 프로그램이 스케줄링 알고리듬을 회피할 수도 있음. 만약 연구자들이 상호작용과 비상호작용을 자동으로 터미널 입출력으로 구분한다고 가정. 터미널 입출력에 1초 간격으로 아무런 입출력이 없으면 비상호작용 프로세스라 구분한다면, 이를 피할 꼼수로 1초 이내로 임의의 문자를 터미널에 출력해주면 됨.

일반적으로 대부분의 유연한 스케줄링 알고리듬은 시스템 관리자나 사용자가 자신의 특정 어플리케이션이나 어플리케이션들에 대해 수정할 수 있는 것임. 하이엔드 그래픽스 어플리케이션을 돌리는 워크스테이션의 경우 웹 서버나 파일 서버와 다른 스케줄링이 필요함. 어떤 운영체제, 특히 몇몇 UNIX 버전의 경우 시스템 관리자가 특정 시스템 설정에 대해 스케줄링 매개변수를 미세조정할 수 있게 해줌. 예를 들어 솔라리스는 dispadmin 명령어로 시스템 관리자가 5.7.3. 절에 언급한 스케줄링 클래스의 매개변수를 수정할 수 있게 해줌.

다른 접근법으로는 프로세스나 스레드의 우선순위를 변경할 수 있는 API를 사용하는 것. Java, POSIX, 윈도우즈 API가 이러한 함수를 제공함. 이 방법의 단점이라면 시스템이나 어플리케이션의 성능 조정은 대부분 일반적인 상황에서 그렇게 성능이 크게 개선되지 않는다는 점임.

5.9. 요약

CPU 스케줄링이란 준비 큐로부터 대기 중인 프로세스를 선택하여 CPU를 할당하는 작업을 의미. CPU는 디스패처에 의해 선택된 프로세스에 할당됨.
스케줄링 알고리듬은 선점적(프로세스의 CPU를 뺏을 수 있음)일 수도, 비선점적(프로세스가 반드시 자발적으로 CPU를 반납해야함)일 수도 있음. 대부분의 현대 운영체제는 선점적임.
스케줄링 알고리듬은 다음 다섯 가지 기준으로 평가 가능: (1) CPU 효용, (2) 처리율, (3) 턴어라운드 시간, (4) 대기 시간, (5) 반응 시간
선도착 선처리(FCFS) 스케줄링이 가장 단순한 스케줄링 알고리듬이지만 짧은 프로세스가 매우 긴 프로세스를 대기해야 함.
최단 작업 우선 (SJF) 스케줄링은 최소 평균 대기 시간을 제공한다는 점에서 최적임. 허나 다음 CPU 버스트의 길이를 예측하는 것이 어렵기 때문에 SJF 구현은 어려움.
라운드 로빈 (RR) 스케줄링은 CPU를 각 프로세스에 시간 할당량에 따라 할당함. 프로세스가 시간 할당량이 끝나기 전까지 CPU를 반환하지 않는다면 프로세스를 선점하여 다른 프로세스를 다음 시간 할당량 동안 실행되도록 함.
우선순위 스케줄링은 각 프로세스에 우선순위를 부여하여 높은 우선순위부터 CPU를 할당함. 같은 우선순위를 갖는 프로세스 간에는 FCFS나 RR 스케줄링을 사용.
다단계 큐 스케줄링은 프로세스를 우선순위에 따라 여러 독립된 큐로 분할하여 스케줄러가 우선순위가 높은 큐의 프로세스부터 실행함. 각 큐마다 서로 다른 스케줄링 알고리듬 사용할 수 있음.
다단계 피드백 큐는 다단계 큐와 유사하나 프로세스가 큐 간에 이동할 수 있다는 점에서 다름.
다중 코어 프로세서는 하나 이상의 CPU를 같은 물리적 칩에 존재하며, 각 CPU가 하나 이상의 하드웨어 스레드를 가질 수 있음. 운영체제 관점에서는 각 하드웨어 스레드가 논리 CPU로 인식이 됨.
다중 코어 체제에서의 부하 분산이란 CPU 코어 간의 부하를 동일하게 해주기 위해 코어 간 스레드를 옮겨주어 부하의 균형을 맞추지만, 이에 의해 캐시가 유효하지 않게 되어 메모리 접근 시간이 늘게 됨.
약실시간 스케줄링은 실시간 작업에게 더 높은 우선순위를 주며, 강실시간 스케줄링은 실시간 작업에 시간적 보장을 해줌.
비율 단조 실시간 스케줄링은 주기적 작업을 선점적 정적 우선순위 정책에 따라 스케줄링을 함.
최단 마감 우선 (EDF) 스케줄링은 마감 시간에 따라 우선순위를 할당함. 마감 시간이 이를 수록 우선순위가 높음.
비례적 스케줄링은 어플리케이션에게 T 만큼의 지분을 할당함. 만약 어플리케이션에게 시간의 N 지분을 할당해준다면 총 프로세서 시간의 N/T를 보장해줌.
리눅스는 완전 공정 스케줄러(CFS)를 통해 각 작업에 CPU의 프로세스 시간의 일부분을 할당함. 이 비율은 각 작업의 가상 실행 시간(vruntime)에 기반함.
솔라리스는 전역 우선순위에 매핑된 여섯 가지 고유한 스케줄링 클래스를 가짐. CPU 중심적 스레드는 일반적으로 우선순위가 낮고(시간 할당량이 김) 입출력 제약 스레드는 일반적으로 우선순위가 높음(시간 할당량이 짧음).
모델링과 시뮬레이션은 CPU 스케줄링 알고리듬을 평가하는데 사용할 수 있음.

Author And Source

이 문제에 관하여(운영체제 (공룡책) - 5), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@alegruz/운영체제-공룡책-5

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)

C# 이미지 잘라내기 및 축소의 예

ajax.net 데이터베이스에 대한 삽입 실례

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다