Basic Concepts
코어가 하나인 시스템에서는, 한 순간에 오직 하나의 프로세스만이 실행될 수 있다.
나머지 프로세스는 CPU 코어가 가용 상태가 될 때까지 기다려야 한다.
어떤 프로그램이 한 번 CPU를 점유하면 다 쓸 때까지 CPU를 반환하지 않는 단순한 시스템을 생각해보자.
하나의 프로세스는 실행 중에 I/O 요청이 완료되기를 기다려야만 하는 경우가 있다. 위의 단순한 시스템에선, CPU는 유의미한 활동을 하지 못하고 놀고 있게만 된다.
이런 낭비를 막기 위해 다중 프로그래밍에선 다수의 프로그램을 메모리에 올려놓고 어떤 프로세스가 I/O를 위해 대기해야 하는 경우 CPU를 프로세스로부터 회수해 다른 프로세스에게 할당한다. 이러한 패턴은 반복된다...
이러한 종류의 CPU 스케줄링은 운영체제의 기본적인 기능이면서 핵심이다.
프로세스의 두 가지 작업 : CPU burst, I/O burst
프로세스는 CPU를 활용하는 CPU 실행과 I/O 요청 후 대기하는 I/O 대기, 두 가지 상태가 반복되는 사이클의 연속이다. 프로세스의 실행은 CPU burst로부터 시작되어 중간중간 I/O burst가 발생하고, 최후엔 프로그램을 종료하기 위한 CPU burst를 일으키며 끝난다.
맥락상 CPU, I/O burst는 CPU 실행 혹은 I/O 대기가 시작 된 후 다른 상태로 전환되기 전까지의 시간을 의미하는 것 같다.
프로세스는 CPU BURST와 I/O BURST의 연속이다.
프로세스에 따라 I/O burst가 자주 일어나는 프로세스와 CPU 버스트가 자주 일어나는 프로세스가 있을 것이다. 전자를 I/O bound job, 후자를 CPU bound job이라고 부른다.
종류 | 내용 | 예시 |
I/O bound job | I/O burst가 자주 일어나는 프로세스 | 유저의 입력을 받아야 하는 사용자 반응형 프로그램 |
CPU bound job | CPU를 활용한 처리가 많은 프로세스 | 데이터 처리를 위해 연산을 길게 가져가야 하는 AI 알고리즘 수행 프로그램 |
CPU 스케줄러
참고로 CPU 스케줄러와 디스패처는 모두 OS의 소프트웨어이다.
CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중에서 하나를 선택해 실행한다. 선택 절차는 CPU 스케줄러에 의해 수행된다. 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에 하나를 선택하여, 이들 중 하나에게 CPU를 할당한다.
준비 큐에 있는 레코드들은 일반적으로 프로세스의 PCB 블록이다.
선점 및 비선점 스케줄링
CPU 스케줄링은 다음 4가지 경우에서 발생한다.
1.
프로세스가 실행 상태에서 대기상태로 전환될 때(예를 들어 I/O 요청이나 자식 프로세스가 종료되기를 기다리기 위해 wait()를 호출했을 때)
참고로 CPU 스케줄러와 디스패처는 모두 OS의 소프트웨어이다.
2.
프로세스가 실행 상태에서 준비 완료 상태로 전환될 때(예를 들어 인터럽트가 발생했을 때)
3.
프로세스가 대기 상태에서 준비 완료 상태로 전환될 때(예를 들어 I/O의 종료 시)
4.
프로세스가 종료할 때
1번과 4번 상황에선 스케줄링 측면에서 보자면 반드시 다른 프로세스로의 전환이 일어나야 한다. 그러나 2,3번 상황에선 선택의 여지가 있다.
1,4번 상황에서만 스케줄링이 발생하는 경우, 비선점(nonpreemptive) 또는 협조적(cooperative)이라고 부른다. 2,3번에서도 스케줄링이 일어나면 선점(preemptive)이라고 한다.
비선점 스케줄링에선 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 또는 대기 상태로 전환해 CPU를 방출할 때 까지 CPU를 점유한다.
위 방식은 스케줄링 상에 비효율을 초래할 수 있기 때문에 Window, MacOS, Linux 및 Unix를 포함한 대부분의 운영체제는 선점 스케줄링을 사용한다.
선점 스케줄링은 데이터가 다수의 프로세스에 의해 공유 될 때 경쟁 조건을 초래할 수 있는데, 이에 대해선 나중에 다시 알아보자.
디스패처
CPU를 할당 할 때 실제로 CPU 코어의 제어를 프로세스에게 넘겨주는 역할을 하는 모듈이 있는데, 디스패처(dispatcher) 이다. 디스패처의 작업엔 다음과 같은 작업이 포함된다.
•
프로세스에서 다른 프로세스로 문맥을 교환(context switch)하는 일
•
사용자 모드로 전환하는 일
•
프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)하는 일
스케줄링의 기준
여러 CPU 스케줄링 알고리즘이 있고, 스케줄링 알고리즘은 각각 다른 특성이 있다. 각각의 알고리즘을 비교하기 위해 여러 기준이 제시되었다. 비교하는 데 사용되는 지표에 따라 알고리즘의 성능이 달라지는데, 다음과 같은 지표들을 사용한다.
CPU 이용률 (utilization)
우리는 가능한 CPU가 바쁘길 바란다. 개념상으로는 CPU 이용률은 0에서 100%까지 이른다. 실제 시스템에서는 40%(부하가 적은 시스템)에서 90%(부하가 큰 시스템)범위를 가져야 한다. (Linux, macOS 및 UNIX에선 top명령어를 사용해 CPU 이용률을 얻을 수 있다.)
top 명령어를 사용하여 CPU 이용률을 확인할 수 있다.
처리량 (throughput)
CPU가 프로세스를 수행하느라 바쁘다면, 작업이 진행되고 있다는 뜻이다. 작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수로, 이것을 처리량이라고 한다. 긴 프로세스의 경우 몇 초 동안 한 프로세스가 될 수 있고, 짧은 트랜잭션의 경우 초당 수십 개의 프로세스가 될 수도 있다.
총처리 시간(turnaround time)
프로세스의 제출 시간과 완료 시간의 간격을 총처리 시간이라고 부른다.
대기 시간(waiting time)
CPU 스케줄링 알고리즘은 프로세스의 실행 시간이나 I/O를 하는 시간의 양에 영향을 미치진 않는다. 스케줄링 알고리즘은 단지 준비 큐에서 대기하는 시간의 양에만 영향을 준다. 대기 시간은 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합이다.
응답 시간(response time)
대화식 시스템(interactive system)에서 총처리 시간은 최선의 기준이 아닐 수 도 있다. 프로세스가 어떤 출력을 매우 일찍 생성하고, 앞서의 결과가 사용자에게 출력되는 사이에 새로운 결과를 얻으려고 연산을 계속하는 경우가 종종 있다. 응답 시간은 유저가 하나의 요구를 제출 한 뒤 첫 번째 응답이 나올 때 까지의 시간이다. 첫번 째 응답의 기준은 응답이 시작되는 데 까지 걸리는 시간이고, 출력하는 데 걸리는 시간은 포함하지 않는다.
연구자들은..
기본적으로 CPU 이용률과 처리량은 최대화 하고, 총처리시간 / 대기시간 / 응답시간은 최소화하는 것이 바람직하다.
연구자들은 대화식 시스템(PC 데스크톱 또는 노트북)의 경우에는 평균 응답시간을 최소화 하기 보다는 응답 시간의 편차(varicnce)를 최소화하는 것이 중요하다고 제시하고 있다. 즉, 합리적인 응답 시간을 가진 시스템이 평균 속도는 빠르지만 응답시간이 들쭉날쭉한 시스템보다 바람직하다고 여기는 것이다. 안타깝게도 편차를 최소화하는 알고리즘에 대한 연구는 거의 없다.
스케줄링 알고리즘
선입 선처리 스케줄링 FCFS
first come, first served scheduling의 준말. 비선점형 알고리즘이다. 가장 단순한 선입 선처리 알고리즘이다. 해당 알고리즘의 구현은 선입선출(FIFO) 큐로 간단하게 관리할 수 있다.
flow
1.
프로세스가 준비 큐에 진입하면, 프로세스의 제어블록(PCB)를 큐의 끝에 연결한다.
2.
CPU가 가용 상태가 되면, 준비 큐의 앞부분에 있는 프로세스에 할당된다.
3.
이 실행 상태의 프로세스는 제거된다.
3개의 프로세스가 있고, 처리시간은 다음과 같다.
프로세스 | 처리시간(ms) |
A | 24 |
B | 3 |
C | 3 |
3개의 프로세스가 ABC 순서대로 준비 큐에 도착했다고 생각해보자. 프로세스의 평균 대기시간은 몇 초일까?
{A 0초 + B 24초 + C 27초} / 3 = 17ms
하지만 BCA 순서로 도착한다면, 프로세스의 평균 대기시간은 훨씬 개선된다.
{A 6초 + B 0초 + C 3초} / 3 = 3ms
한계점
이러한 감소는 상당히 큰 것이다. 따라서 선입 선처리 정책에서 평균대기시간은 일반적으로 최소가 아니다.
이외에도 긴 CPU burst를 가진 CPU bound Job이 수행되면 나머지 수많은 IO bound job들이 CPU를 오래동안 활용하지 못하는 Convoy 효과가 생기기도 한다.
다양한 프로세스가 규칙적인 간격으로 CPU를 얻는 것이 중요한 대화형 시스템에선 써서는 안 된다.
최단 작업 우선 스케줄링 SJF
shortest-job-first의 준말이다. 이 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연관시킨다.
CPU가 이용 가능해지면, 가장 작은 다음 CPU 버스트를 가진 프로세스에 할당한다.(동일한 길이면 먼저들어온 프로세스)
이 알고리즘은 프로세스의 전체 길이가 아닌, 다음 CPU 버스트 길이에 의해 스케줄링 된다. 사실 최단 다음 CPU burst first 알고리즘이라고 불러야 적합하다.
flow
프로세스 | 다음 CPU burst 처리시간(ms) |
A | 6 |
B | 8 |
C | 7 |
D | 3 |
준비큐에 ABCD 순서로 들어와도, 버스트 길이에 의해 수행순서를 조정한다.
SJF 알고리즘은 주어진 프로세스 집합에 대해 평균대기시간이 최소인, 최적의 알고리즘이다.
선점형 SJF, 비선점형 SJF
SJF 알고리즘은 선점형이거나 비선점형일 수 있다. 새로운 프로세스가 준비 큐에 도착했는데, 현재 실행되고 있는 프로세스의 남은 시간 보다도 더 짧은 CPU burst 시간을 가질 수 도 있다. 이 때 선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스를 선점할 것(빼앗아 새로운 프로세스에게 준다)이고, 비선점형 SJF는 현재 실행하고 있는 프로세스가 CPU burst를 끝내도록 허용한다.
선점형 SJF 알고리즘은 위의 동작방식으로 인해서 최소 잔여 시간 우선(shortest remaining time first) 스케줄링 이라고도 불린다.
비선점형 SJF의 flow
프로세스 | 도착 시간(ms) | 다음 CPU burst 처리시간(ms) |
A | 0 | 8 |
B | 1 | 4 |
C | 2 | 9 |
D | 3 | 5 |
A가 프로세스가 선점당해 뒤로 밀리는 것을 볼 수 있다.
한계점
1.
SJF 알고리즘의 문제점은 각 프로세스의 다음 CPU burst 길이를 알 방법이 없다는 것이다. 이를 위해 다음 CPU burst를 예측하는 방법을 활용한다. 예측은 이전의 CPU burst들의 길이를 지수평균 한 값으로 활용한다.
2.
프로세스의 기아(starvation) 문제가 발생할 수 있다. 기아 문제는 CPU burst 처리시간이 지나치게 긴 프로세스는 계속 선점당해 아무도 CPU를 안 쓰게 될 때 까지 영원히 CPU를 못 쓰는 현상을 뜻한다.
우선순위 스케줄링
Priority Scheduling. 프로세스들마다 우선순위를 부여하며, 가장 높은 우선순위를 가진 프로세스 CPU를 할당한다. SJF 알고리즘도 일종의 우선순위 스케줄링이다. (짧은 CPU burst로 우선순위를 부여한)
우선순위 스케줄링 또한 선점형과 비선점형으로 구분할 수 있다. 선점형은 현재 실행되는 프로세스보다 우선순위가 높은 프로세스가 준비 큐에 들어오면 해당 프로세스에 CPU를 할당하는 방식, 비선점형은 단순히 준비 큐에 머리 부분에 새로운 프로세스를 넣는 방식으로 이루어진다.
한계점과 극복
해당 문제를 해결하기 위해 노화(aging) 방식을 활용하는데, 오랫동안 시스템에서 대기하는 프로세스의 우선순위를 점진적으로 증가시킨다. 예컨데 0부터 127의 범위를 가지는 우선순위가 있다면, 주기적으로(예 : 1초마다) 대기중인 프로세스들의 우선순위를 1씩 증가시켜 보자. 이러면 처음엔 우선순위가 127이었던 프로세스도 결국 최고의 우선순위를 갖게 되어 실행될 것이다. 이 경우 가장 낮은 우선순위를 가진 프로세스더라도 실행되기까지 2분 정도의 시간밖에 걸리지 않는다.
라운드 로빈
Round Robin, RR 스케줄링 알고리즘은 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다. 현대의 OS들은 대부분 RR 스케줄링에 기반해 만들어진다.
시간 할당량(time quantum), 혹은 타임 슬라이스(time-slice)라고 하는 작은 단위의 시간을 정의한다. 시간 할당량은 일반적으로 10에서 100밀리초 동안이다. 준비 큐는 원형 큐(circular queue)로 동작한다. CPU 스케줄러는 준비 큐를 돌면서 한 번에 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다. 시간 할당이 초과하면 프로세스를 선점하기 때문에, RR은 선점형이다.
flow
준비 큐를 선입선출 큐로 동작하게 만들고, 새로운 프로세스는 준비 큐의 꼬리에 추가한다. CPU 스케줄러는 준비 큐에서 첫 번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머(timer)를 설정한 뒤, 프로세스를 디스패치(dispatch) 한다.
두 가지 케이스가 있다.
1.
프로세스의 CPU burst가 한 번의 시간 할당량 보다 짧은 경우.
a.
이 경우 프로세스 자신이 CPU를 자발적으로 방출한다. 스케줄러는 준비 큐에 있는 다음 프로세스로 진행할 것이다.
2.
프로세스의 CPU burst가 한 번의 시간 할당량 보다 긴 경우.
a.
이 경우 문맥 교환(context switch)가 일어나고 실행하던 프로세스는 준비 큐의 꼬리에 넣어진다. 그 후 스케줄러는 준비 큐의 다음 프로세스를 선택한다.
프로세스 | CPU burst 처리시간(ms) |
A | 24 |
B | 3 |
C | 3 |
모든 프로세스가 돌아가며 동일한 시간할당량을 할당 받는다.
RR 정책은 SJF보다는 종종 평균 대기시간이 길어진다. 위의 케이스에서 평균 대기시간은 5.66 ms인데 ({6 + 4 + 7} / 3), SJF였다면 2ms 였을 것이다. ({0 + 0 + 6} / 3) 그러나 평균 응답시간에서 이점이 있다.
시간 할당량과 RR의 성능
RR 알고리즘은 시간 할당량에 매우 큰 영향을 받는다. 극단적으로 시간 할당량이 크다면, RR 정책은 선입 선처리 정책과 동일할 것이다. 이와 반대로 시간 할당량이 매우 적다면 (예. 1ms) RR 정책은 매우 많은 문맥 교환(context switch)을 야기할 것이다.
시간 할당량은 문맥 교환 시간과 비교해 커야한다. 문맥 교환 시간이 시간 할당량의 10%라면, CPU 시간의 10%는 문맥 교환에 사용될 것이다.
현대 대부분의 운영체제들은 10에서 100밀리초 범위의 시간 할당량을 가지고 있는데, 문맥 교환에 걸리는 시간은 보통 10ms 미만이다.
시간 할당량이 커지면 커질수록 총처리 시간은 개선될 테지만, (문맥 교환 시간이 줄어드므로) RR이 선입 선처리 정책으로 퇴보하게 된다. 공룡책 저자 경험상 CPU 버스트의 80%는 시간 할당량보다 짧아야 한다고 한다.
다단계 큐 스케줄링
Multilevel Queue Scheduling.
우선순위와 라운드 로빈 스케줄링을 사용할 때 모든 프로세스가 단일 큐에 배치되고 스케줄러는 우선순위가 가장 높은 프로세스를 선택하여 실행한다. 큐가 관리되는 방식에 따라 우선순위가 가장 높은 프로세스를 결정하기 위해 O(n) 검색이 필요하다.
이를 개선하기 위한 것이 다단계 큐이다. 우선순위마다 별도의 큐를 갖게 만들고, 동일한 우선순위 내에선 라운드 로빈 순서로 실행된다.
다단계 큐 스케줄링 예시
flow
위의 이미지 예시를 보면서 설명해보자.
프로세스 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하기 위해 다단계 큐 스케줄링 알고리즘을 분할한다. 예를 들어, 포그라운드(대화형) 프로세스와 백그라운드(배치) 프로세스를 구분한다.
두 가지 유형의 프로세스는 응답시간 요구 사항이 다르므로 프로세스 요구사항이 다를 것이다. 또한 포그라운드 프로세스는 백그라운드 프로세스 보다 더 높은 우선순위를 가져야 한다는 요구사항 또한 있을 것이다.
이를 위해 각각의 큐에 걸맞는 스케줄링 알고리즘을 세팅한다. 예를 들어 백그라운드 큐는 FCFS, 포그라운드는 RR 알고리즘에 의해 스케줄되도록 한다.
추가로 큐와 큐 사이에 스케줄링을 세팅하고, 고정 우선순위의 선점형 스케줄링으로 구현한다. 예를 들어 실시간 큐는 대화형 큐보다 절대적으로 높은 우선순위를 가진다. 이러면 하위 큐에 있는 프로세스는 상위 큐에 어떠한 프로세스도 없을 때에만 실행된다. 예컨데 배치 프로세스는 실시간, 시스템, 대화형 프로세스가 없을 때에만 실행할 수 있고, 상위 큐에 프로세스가 들어오면 선점된다. (기아 상태 발생 가능성)
혹은 큐 들 사이에 시간을 나누어 사용할 수 도 있다. 가장 중요한 실시간 큐에 80%의 시간을 할당하고, 배치에는 20%의 시간을 할당하는 식이다.
다단계 피드백 큐 스케줄링
Multilevel Feedback Queue.
다단계 큐에선 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 특정 큐에 할당된다. 예컨데 포그라운드 큐에 특정 프로세스가 할당되고 나면, 영원히 백그라운드 큐로 이동하지 않는다. 이러한 방식은 스케줄링 오버헤드에 장점이 있으나 융퉁성이 적다. (딱딱 성격이 나누어 떨어지는 프로세스가 얼마나 있을것인가?)
다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용 한다. 기본 컨셉은 CPU 버스트 시간에 따라 구분하는 것이다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위 큐로 이동한다. 이 방법에선 I/O bound job(CPU burst가 짧은)을 상위 우선순위 큐에 넣는다. 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동시킴으로써 기아 상태를 예방한다.
flow
3개의 우선순위 큐를 둔다. 각 큐의 설정은 다음과 같다.
큐 순위 | 설명 |
Q0 | 8ms의 시간 할당량을 가지는 RR 스케줄링 |
Q1 | 16ms의 시간 할당량을 가지는 RR 스케줄링 |
Q2 | 선입선출 스케줄링 |
스케줄링 흐름도
스케줄링
1.
새로운 Job이 Q0으로 들어간다.
2.
CPU를 잡아서 8ms동안만 수행된다.
3.
8ms 동안 끝내지 못했으면 Q1으로 내려간다.
4.
Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행된다.
5.
16ms에서 끝내지 못한 경우 Q2로 쫓겨난다.
이 스케줄링 알고리즘은 CPU burst가 8ms 이하인 프로세스에게 최고의 우선순위를 부여한다. 이러한 프로세스는 빨리 CPU를 할당받아서, CPU 버스트를 끝내고 다음의 I/O 버스트로 간다. 8ms 이상 24ms 이하의 프로세스들은 더 짧은 프로세스들 보다는 낮은 우선순위를 받지만, 그래도 서비스를 빨리 받는다. 긴 프로세스는 자동으로 Q2로 가게 되어, Q0과 Q1이 사용하지 않는 때에 선입 선처리 방식으로 처리된다.
한계점
다단계 피드백 큐 스케줄러의 정의에 의하면 이 스케줄링 알고리즘은 가장 일반적인 알고리즘이다. 그러나 큐의 개수, 각 큐의 스케줄링 알고리즘, 상위 큐로 올려주는 알고리즘, 하위 큐로 내려주는 알고리즘, 프로세스가 들어갈 큐를 결정하는 방법... 다양한 설정이 필요하여 가장 복잡한 알고리즘이라는 점이 있다.
다중 처리기 스케줄링
Multiple-Processor Scheduling
프로세서가 여러개인 경우, 여러 스레드가 병렬로 실행될 수 있으므로 부하 공유(Load Sharing)이 가능해진다. 스케줄링 문제는 그에 상응하여 더욱 복잡해진다. 많은 시도가 있었으나, 위에서 본 다양한 싱글코어 CPU 스케줄링에서 보았던 거서럼 최상의 해결책은 없다.
다중 처리기 스케줄링에 대한 접근 방법
Asymmetric Multiprocessing
하나의 프로세서를 마스터 서버로 두어 모든 스케줄링 결정과 I/O 처리, 그리고 다른 시스템의 활동을 취급하게 하고, 나머지 처리기는 단지 사용자 코드만 수행하도록 하는 것이다. 이 방식은 하나의 코어만 시스템 자료구조에 접근하고 자료 공유의 필요성을 배제하기 때문에 간단하다. 단점은 마스터 서버가 전체 시스템 성능을 저하하는 병목 지점이 될 수 있다. 100개의 하위 프로세서들이 마스터 서버를 졸라대는 모습을 상상해보라.
Symmetric Multiprocessing (SMP)
각 프로세서가 각자 알아서 스케줄링을 결정하게 하는 것이다. 스케줄되는 스레드를 위해 두가지 전략이 가능하다.
1.
각 프로세스 별로 별개의 스레드 큐를 이용하는 방법
2.
공동의 큐에서 스레드를 모두 관리하는 방법
첫 번째 옵션을 선택하면 공유 준비 큐에 경쟁 조건이 생길 수 있으므로 두 개의 다른 프로세서가 동일한 스레드를 스케줄 하지 않도록, 또 큐에서 스레드가 없어지지 않도록 보장해야한다. 락킹을 통해 가능하겠지만, 락킹에 의한 성능 저하가 발생할 수 있다.
두 번째 옵션은 프로세서가 자신만의 큐에서 스레드를 사용하는, SMP 시스템에서 가장 일반적인 옵션이다. 또한 프로세스 별로 붙어있는 캐시 메모리를 효육적으로 사용할 수 있다. 이 방식은 큐마다 부하량이 다를 수 있다는 단점이 있다. 이를 위해 균형 알고리즘을 사용하여 모든 프로세스 간에 부하를 균등하게 만들 수 있다.
Window, Linux, macOS 등의 운영체제와 Android, iOS의 모바일 시스템을 포함한 거의 모든 최신 운영체제는 SMP를 지원한다.
다중 코어 프로세서
SMP 시스템은 다수의 물리 처리기를 제공하여 다수의 프로세스가 병렬로 실행되게 한다.
그러나 현대 컴퓨터 하드웨어는 하나의 물리적 칩 안에 여러 개의 처리 코어를 장착한 다중 코어 프로세서(multicore proccessor)이다. 각 코어는 구조적인 상태를 유지하고 있어 운영체제 입장에서는 개별적인 논리적 CPU로 보이게 되는 구조이다. 다중 코어 프로세서를 사용하는 SMP 시스템은, 각 CPU가 물리칩을 가지는 모델보다 속도가 빠르고 적은 전력을 소모한다.
다중 코어 프로세서는 메모리 스톨 현상으로 스케줄링 문제를 복잡하게 한다. 메모리 스톨은 프로세서가 메모리에 접근할 때 데이터가 사용 가능해지기를 기다리면서 시간을 허비하는 현상을 말한다. 프로세서가 메모리보다 훨씬 빠른 처리 속도를 가지고 있기 때문에 주로 생긴다. 때때로 캐시 미스(캐시 메모리에 없는 데이터를 엑세스)로 인해 생길 수 도 있다.
이러한 상황을 해결하기 위해 최근의 다중 코어 프로세서는 다중 스레드 처리 코어를 구현하였다. 이러한 설계에선 하나의 코어에 2개 이상의 하드웨어 스레드가 할당된다. 이렇게 하면 메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환할 수 있다.
다중 스레딩 다중 코어 시스템. C는 계산, M은 메모리 스톨을 의미한다.
운영체제 관점에서 보자면, 각 하드웨어 스레드는 명령어 포인터 및 레지스터 집합과 같은 구조적 상태를 유지하므로 소프트웨어를 실행 시킬 수 있는 논리적 CPU로 보인다. 이러한 기술을 칩 다중 스레딩(chip multi threading, CMT)라고 한다.
4개 코어에 8개의 스레드. 운영체제 관점에선 8개의 CPU로 보인다.
인텔 i7 같은 경우 코어당 2개의 스레드를 지원하는 반면 Oracle Sparc M7은 코어당 8개의 스레드를 지원하는 등, 제조사마다 차이가 있다.
2단계 스케줄링 구조
하드웨어 스레드는 캐시 및 파이프라인 같은 물리적 코어를 공유한다. 그로 인해 처리 코어는 동시에 한 개의 스레드만 처리할 수 있다! 그래서 다중 스레드 다중 코어 프로세서는 두 개의 다른 스케줄링 단계가 필요하다. 이 2단계 스케줄링을 도식화 하면 다음과 같다.
•
level 1에선 운영체제가 각 하드웨어 스레드(논리적 CPU)에서 실행할 소프트웨어 스레드를 선택할 때 결정해야 하는 스케줄링 결정을 한다. 이 단계에서 OS가 FCFS, SJF, RR 등 위에서 학습한 싱글코어 알고리즘을 포함한 알고리즘 중, 임의의 알고리즘을 선택할 수 있다.
•
level 2에선 각 코어가 실행할 하드웨어 스레드를 결정하는 방법을 명시한다. 여러가지 전략이 있을 것이다.
◦
round robin 알고리즘
▪
단순하게 번갈아 가며 스케줄한다. UltraSPARC T3 에 의해 채택되었다.
◦
동적 긴급도 방식
▪
Intel Itanium에서 쓰는 방식이다.
▪
0에서 7까지의 동적 긴급도(ungency vlaue)를 하드웨어 스레드마다 배정한다. 0이 낮은 긴급도, 7이 높은 긴급도를 의미한다. Itanium은 스레드 교환을 촉발할 수 있는 5가지 이벤트를 식별하고, 이 이벤트 중 하나가 발생하면 스레드 교환 회로가 두 스레드의 긴급도를 비교하여 높은 긴급도를 가진 스레드를 선택해 처리 코어에서 실행한다.
•
level 1 과 level 2가 반드시 상호 배타적일 필요는 없다. 예컨데 2개의 처리 코어와, 각 코어에 2개의 스레드가 있는 칩을 가정하자. 이 시스템에 2개의 서로 다른 소프트웨어 스레드가 배정될 때, 하나의 처리 코어에 2개를 맡기는 것 보다 각각 다른 코어에 맡기는 것이 더 빠르게 수행될 것이다. (각 하드웨어 스레드는 프로세서 자원을 공유하기 때문이다.) 운영체제가 프로세서 자원 공유 수준을 알고 있으면 자원을 공유하지 않는 논리 프로세서에 소프트웨어 스레드를 스케줄 할 수 있다.
실시간 CPU 스케줄링
Real-time Scheduling.
실시간 운영체제에서 CPU를 스케줄링 할 때 연성(soft) 실시간 시스템과 경성(hard) 실시간 시스템으로 구분한다.
경성 실시간 시스템
경성 실시간 시스템(hard real-time systems)는 정해진 시간 안에 태스크를 반드시 끝내도록 스케줄링 하는 방식을 의미한다.
연성 실시간 시스템
연성 실시간 시스템(soft real-time computing)은 중요 실시간 프로세스가 그렇지 않은 프로세스보다 우선권을 가진다는 것만 보장한다. 경성 실시간 시스템과 비교하면, 실시간 프로세스가 스케줄 되는 시점에 관해 아무런 보장을 하지 않는다.
실시간 운영체제 스케줄링
실시간 운영체제에서 중요한 것은 실시간 프로세스에 CPU가 필요할 때 바로 응답을 해주는 것이다. 따라서 실시간 운영체제의 스케줄러는 선점을 이용한 우선순위 기반의 알고리즘을 지원해야한다. 리눅스나 윈도우, 솔라리스 같은 운영체제에선 실시간 프로세스에게 가장 높은 스케줄링 우선권을 부여한다.
예컨데 윈도우에선 32개의 우선순위가 존재하는데, 높은 순위에 해당하는 16 ~ 31의 값이 실시간 프로세스 들에 할당되어 있다. 리눅스와 솔라리스도 비슷하다.
이처럼 선점과 우선순위 기반의 스케줄러를 제공하는 것은 연성 실시간 기능을 제공하는 것에 해당하는데, 그러므로 실시간 태스크가 마감시간 내에 확실히 수행하는 것을 보장하지 않는다. 경성 실시간 시스템에 걸맞게 작성하려면 별도의 스케줄링 알고리즘이 필요하다.
공룡책엔 Rate-Monotonic 스케줄링과 Earliest-Deadline-First 스케줄링(EDF) 이 소개된다. 본문에서 해당 내용은 다루지 않는다. 리눅스에서 사용하는 POSIX 실시간 스케줄링만 알아보자.
POSIX 실시간 스케줄링
•
SCHED FIFO
◦
FCFS에 기반한 스케줄러이다. 먼저 온 것을 먼저 서비스하는 정책에 따라 스레드를 스케줄 하고, 따라서 FIFO 큐 선두에 있는 최고 우선순위 스레드는 종료되거나 블록될 때 까지 CPU를 할당받는다.
•
SCHED RR
◦
라운드 로빈 정책을 사용한 스케줄러이다. 같은 우선순위의 스레드에 시간 할당량을 제공하는 것을 제외하면 SCHED FIFO와 비슷하다.
•
SCHED OTHER
◦
이 클래스는 구현을 정의하지 않아 시스템마다 각자 구현하는 예비용 클래스이다.
POSIX API 는 스케줄링 정책에 관한 정보를 지정하고 얻어내는 두개의 함수를 제공한다.
// attr은 스레드의 속성 집합의 포인터. policy는 현재의 스케줄링 정책이거나, 위 3개의 클래스를 표현하는 정수값
pthread_attr_getschedpolicy(pthread_attr_t *attr, int *policy);
pthread_attr_getschedpolicy(pthread_attr_t *attr, int policy);
C
복사
스레드 스케줄링
각 CPU의 수행 단위가 되는 스레드. 사용자 수준과 커널 수준의 스레드를 구별했다. 대부분의 최신 운영체제에서 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다.
Local Scheduling
•
사용자 수준 스레드는 스레드 라이브러리에 의해 관리되고 커널은 그 존재를 알지 못한다. 커널은 프로세스에 CPU를 할당할 뿐이고, 프로세스 내부에서 스레드 라이브러리를 호출함으로써 어떤 스레드를 스케줄 할 지 결정하는 방식이다.
•
즉, OS가 아니고 사용자 어플리케이션이 어떤 스레드에 CPU를 줄 지 결정하는 방식!
Global Scheduling
•
커널 수준 스레드의 경우 일반 프로세스와 마찬가지로 단기 스케줄러가 어떤 스레드를 스케줄할지 결정한다.
•
즉, OS가 직접 스레드에 CPU를 할당하는 방식이다.
알고리즘 평가
Algorithm Evaluation, 특정 시스템을 위한 CPU 알고리즘을 선택하기 위해 사용할 수 있는 방법론이다. 위에서 봤듯이 수많은 스케줄 알고리즘이 있고, 각각이 다른 파라미터를 가지고 있다. 특정 알고리즘을 선택하기 쉽지 않다.
1.
먼저 알고리즘을 선택하는 데 사용할 기준을 정의한다. 위에서 봤듯이 여러가지 상대적인 기준이 있는데, 이 기준 중 내 시스템에 적합한 상대적인 중요도를 정의해야 한다. 다음은 예시이다.
•
최대 응답 시간이 300ms이며 CPU 이용률이 극대화 되어야 해!
•
총 처리 시간이 전체 실행시간에 평균적으로 비례하도록, 처리량을 극대화해야 해!
2.
선택 기준이 정의되면 여러 비교군 알고리즘을 평가해야 한다. 다음과 같은 방법들이 있다.
a.
Queueing models
•
확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산. 알고리즘을 구현하기 앞서, 사전 테스트 해볼 수 있는 모델이다.
Queueing models
b.
Implementation (구현) & Measurement(성능 측정)
•
실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
•
실제 리눅스 와, 리눅스 커널을 일부 수정한 모델을 동시에 실험해 성능을 측정한다.
c.
Simulation (모의 실험)
•
실제 구현 방식이 지나치게 자원을 많이 잡아먹을 때 쓰는 방식
•
알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
레퍼런스
반효경 교수님 Process Management 강의 2강, 후반부 49분 부터
반효경 교수님 CPU scheduling 강의 1강
반효경 교수님 CPU scheduling 강의 2강
공룡책
