1. 개요
(0) 들어가기 앞서
스케쥴링은 아직까지도 나름 활발하게 연구되고 있는 분야다.
현존하는 프로세서들은 각자 조금씩 다른 스케쥴링 정책을 가지고 있고, 각 프로세서 별 최적화된 스케쥴링을 만드는 것 만으로도 상당한 실력이 필요하다.
우리는 스케쥴링이 무엇인지, 왜 필요한지, 어떻게 이루는지, 무엇을 기준으로 만드는지를 알아볼 것이다.
최적의 스케쥴링 방법을 알아보는건 대학원 가서 알아서 하시라.
(1) CPU 가상화
이전 포스트에서 간단히 설명했는데,
CPU 가상화는 여러 프로세스들 간에 CPU를 시간에 따라 나눠 쓰는 것을 말한다.
OS는 프로세스한테 마치 가용 CPU 코어가 남아있는 것처럼 환상을 준다.
여기에 낚인 프로세스는 대기열에 서게 되고,
시간 단위로 CPU를 썼다가 뺏겼다가 하면서 나눠쓴다.
가상화를 제한하는 요소(constraints)는 두 가지 있는데,
1) 성능(Performance) 측면
가상화에 너무 많은 간접처리시간(overhead)를 필요로 해서는 안된다. 해야할 일 보다 정리하는데 더 시간을 많이 쓰는건 손해라는 뜻이다.
2) 제어(Control) 측면
OS는 프로세스가 효율적으로 돌아가면서도 시스템 보호를 위해 그 실행을 조종할 수 있어야한다.
보통은 제어<-->효율 에서 trade off가 일어나는데, 너무 효율을 잡겠다고 OS에서의 제어를 소홀히 해서는 안된다는 뜻이다.
(2) 커널 모드, 시스템 콜
1) 직접 실행(Direct Execution)
프로그램이 그냥 CPU에 때려박혀서 실행되는걸 직접실행이라고 한다.
(+) 간접적으로 조종하는 OS가 없으니 매우 빠르게 실행되지만,
(-) 프로세스가 이상한 행동(malicious, illegal operations)을 해도 제지할 방법이 없다.
프로세스가 작업을 다 끝내고 나서 return을 할 때 까지 OS는 손가락만 빨고 있어야한다.
2) 커널 모드(Kernel Mode)와 유저 모드(User Mode)
커널 모드는 컴퓨터 자원에 접근할 권한을 모두 가지고 있는 경우고,
유저 모드는 컴퓨터 자원에 접근할 권한이 일부 없는 경우다.
보통은 OS가 커널 모드이고, 일반 프로그램이 실행되는 프로세스가 유저 모드이다.
만약 유저 모드에서 프로세스가 권한이 없는 행동을 요청하면, 예외(Exception)를 일으키고, OS가 프로세스를 죽인다.(Kill)
3) 인터럽트(interrupt), 예외(exception), 트랩(trap)
바로 위에서 예외가 나타나는 경우인 유저 모드에서 권한이 없는 행동을 요청을 예시로 말해보았다.
조금만 더 자세히 살펴보자.
예외(Exception)는 어떠한 사건에 대한 반응으로 OS 커널에 신호를 전달해 주는 행위를 말한다.
종류로는 비동기식(Asynchronous)와 동기식(Synchronous) 가 있다.
비동기식 예외는 인터럽트(Interrupt) 또는 외부 인터럽트라고도 하며, 프로세서 외부에서 발생한 예외를 말한다. 키보드 I/O, USB 인식, 클럭(timer tick) 등이 있다. 이 경우 Handler는 다음 Instruction을 return한다.
동기식 예외는 Instruction을 실행한 결과로 발생한 예외로, 내부 인터럽트라고도 한다.
Trap, Fault, Abort의 세 종류가 있다.
Trap은 프로그래머가 의도한 의도적인 예외로, 다음 Instruction을 반환한다.
예시로는 system call, breakpoint trap이 있다.
Fault는 의도하지는 않았지만 복구 가능한 예외로, 현재 Instruction을 재실행하거나 abort한다.
예시로는 page fault, protection fault가 있다.
Abort는 의도하지 않았고 복구 불가능한 예외로, 아무것도 return하지 않고 abort한다.
예시로는 허용되지 않은 instruction 실행, parity error, machine check가 있다.
모든 종류의 예외는 발생시 Exception Table이라는 곳을 검색하여 예외 종류에 맞는 Exception handler를 찾아간다.
위에 써져있다시피, 인터럽트와 Trap은 핸들러 실행 후 다음 Instruction으로 가고, Fault는 재실행하고, Abort는 abort한다.
우리는 프로세서 내부에서 일어나 컨트롤이 가능하고, 우리가 의도적으로 일으켜서 제어가 가능한 Trap에 대해 더 알아볼 것이다.
4) 트랩(Trap)과 시스템 콜(system call), 그리고 신호(signal)
트랩은 계속 말했듯이 프로세서 내부에서 일어났으며, 의도적으로 일으킨 예외다.
프로그래머가 예측한 종류의 예외들이니 여러가지 처리가 가능한데, 보통은 귀찮으니 죽여버린다.(kill)
하지만 이렇게 죽이지 않고 살려서 잘 써먹는 친구가 있으니, 바로 시스템 콜이다.
시스템 콜은 Trap의 한 종류로,
파일을 여는 등 정형화된 작업을 커널에서 하거나
별도 메모리를 가진 다른 프로세스에게 신호를 주는 일을 하는 등
유저 모드에서는 권한이 없는 일을 OS를 통해서 할 필요가 있을 때 필요한 친구다.
그러니 얼마나 중요하겠는가!
시스템 콜을 일으키는 Instruction을 특별히 Trap instruction이라고 하고,
시스템 콜의 Exception Table이 가리키는 Table과 그 핸들러를 특별히 Trap table, Trap handler라고 부를 정도다.
시스템 콜의 종류는 굉장히 많지만, 예시를 하나 들어보자.
printf("Hello world!"); 위 코드는 터미널창에 Hello world! 라는 메시지를 출력한다.
하지만, 터미널 역시 프로세스 혹은 파일이라고 볼 수 있다는 걸 고려하면,
저 printf를 사용한 프로세스는 다른 프로세스를 건드린다는 "월권행위"를 저지른 것이다.
그리고 이 "월권행위"는 결코 직접 하지 못하고, OS 커널만이 할 수 있다.
우리는 이 함수를 의도해서 사용했으니, 시스템 콜을 한 것이다.
...
movl $SYS_write, %eax
int 0x40
...
movl $SYS_exit, %eax
int 0x40
...위의 코드가 유저 모드에서 실행되었다고 해보자.
1 : movl $SYS_write을 %eax라는 레지스터에 옮겼다.
2 : 0x40번의 인터럽트를 발생시켰다. Exception Table의 0x40으로 이동할 것이다.
3 : Interrupt Descriptor Table(Exception Table)의 0x40번에는 syscall 함수에 대한 포인터가 있다.
즉, int 0x40는 시스템 콜이었다.
4 : syscall 함수는 trap table에서 %eax 레지스터 안에 있는 값을 담당하는 함수로 보낸다.
이 경우 %eax는 $SYS_write이었고, sys_write()으로 보냈다.
(3) 스위칭
CPU는 개념적으로는 여러 프로세스를 동시에(Concurrently) 실행하지만, 물리적으로 한 번에 한 프로세스만을 실행할 수 있다.
유저 모드 프로세스와 커널 모드 프로세스(OS)를 동시에 실행할 수는 없고, 번갈아가며 실행해야 한다는 말이다.
어떻게 하면 번갈아가면서 실행할 수 있을까?
1) Cooperative Switching
유저 모드 프로세스가 자기 실행을 다 끝낸 다음 OS에 넘겨주면 된다. 아니면 중간에 자발적으로 넘겨줘도 된다.
OS는 유저 모드 프로세스가 언젠가 넘겨주기를 기다리고 있다.
좋은 점은 커널에 많은 신경을 안 쓰고, 유저 프로세스가 정기적 또는 비정기적으로 커널에게 돌려주면 된다는 것이고
나쁜 점은 한 프로세스가 영원히 독점할 수 있다는 것이다.
당연히 후자가 더 크겠지?
이런 영원한 루프를 해결하는 방법은 몇 가지가 있는데,
trap으로 간주하고 죽여버리거나,
Undetected corner case라고 생각해서 재부팅 해버리면 된다.
아니면 Cooperative Switching을 안 쓰면 되겠지?
2) Context Switching
위 Cooperative Switching 에서 발생하는 문제를 해결하려면
OS가 수동적으로 기다리지 말고, 적극적으로 달라고 하면 된다.
보통 그 수단으로는 Timer Interrupt를 사용하는데,
얘는 프로세서 밖에서 들어오는 외부 인터럽트다.
율무는 전기전자 전공이니 조금 더 설명해보자면,
전압을 가하면 진동하는 쿼츠를 하나 놓고(시계랑 똑같은 원리),
필요한 경우 이 진동을 카운팅하는 디지털 카운터를 거쳐서,
프로세서에 일정 시간마다 상승/하강 엣지를 주도록 만들면 된다.
아무튼 타이머 인터럽트가 일어났으면,
기존의 프로세서는 차지하고있던 CPU 자리를 비켜줘야 하지 않나?
근데 아직 return 까지 못갔는데, 그냥 가면 여태 작업한 건 다 날아가니
현재 상태를 저장해야겠다. 아! 그래서 이전 포스트 process에서 PCB를 그렇게 설명했구나.
이걸 Context switching 이라고 한다.
2. Sheduling 기본
(1) Scheduling이란?
위에서 프로세스가 CPU 자리를 넘겨주는 방법을 설명했다.
그런데, 넘기는 방법은 알겠는데, 누구한테 줄 것인가?
메이플처럼 인맥한테 줄 건가?
한 번 연구해보자.
프로세서(CPU)에서 실행되고 있는 프로세스는 "Job" 또는 "Workload" 라고 불린다.
Scheduling은 Job들간의 순서를 조율하는 일이다.
순서는 보통 전체적인 성능에 따라 조율하므로,
"성능"을 수치화한 단위(Metric)가 필요하고,
이 단위 중 무엇을 최적화할 지에 따라 방법이 달라진다.
그리고 그 전에, 성능 비교에는 공리가 필요하므로 아래의 비현실적인 가정을 한다.
1) 모든 Job은 같은 실행 시간을 가진다.
2) 모든 Job은 같은 시간에 시스템에 도착한다.
3) 모든 Job은 I/O 요청 없이 오직 CPU만을 사용한다.
4) 전체 Job의 실행시간은 미리 알려져있다.
5) 모든 Job은 시스템에 도착한 순간 queue에 배정받는다.
(2) 성능 비교 단위(Metric)
1) Turnaround time
Job이 시스템에 도착했을 때 부터 실행이 완료되기까지의 시간이다.
2) Wating time
Job이 시스템에 도착했을 때 부터 Ready queue에 배정받기까지의 시간이다.
3) Response time
Ready queue에 배정받은 순간부터 처음 실행이 시작되기까지의 시간이다.
4) Throughput
일정 시간동안 끝낸 프로세스의 수를 말한다.
단, 위의 공리에서 시스템의 도착과 queue 배정이 같은 시간이라 가정했으므로,
wating time은 항상 0이며
response time은 시스템 도착시~처음 실행시
로 가정한다.
(3) 기본 전략(Policy)
1) First-In, First-Out(FIFO) == First-come, First-Served(FCFS)
먼저 온 놈이 먼저 나간다는 소리다.
0초에 A,B,C가 들어왔다면
A 20초, 그다음 B 20초, 그다음 C 20초이니
Turnaround time은 A 20, B (20+20), C (20+20+20) 이다.
Response time은 A 0, B 20, C (20+20) 이다.
언뜻 합리적이지만, A가 B나 C보다 오래 걸리는 작업일 때는 그렇지 않다.
이런 경우에는 누가 봐도 다른 전략이 필요하다.
2) Shortest Job First(SJF)
남은 시간이 제일 짧은 Job을 먼저 배치하겠다는 것이다.
오, 꽤 개선되었다.
그러나, 이 전략은 A, B, C가 다른 시간에 도착한 경우 전혀 효과적이지 못하다.
A는 0초, B는 10초, C는 20초에 도착했다고 가정해보자.
여전히 A가 맨 앞에서 트롤을 하고있다.
이 것을 "Convoy Effect"라고 한다.
3) Preemptive Shortest Job First (PSJF) == Shortest Time-to-Completion First(STCF)
위의 SJF에서 preemtive라는 단어를 넣었다.
Preemptive는 "선점"이란 뜻으로, 실행 중 인터럽트를 허용하는 경우에 쓴다.
프로세스 실행 중간에 다른 프로세스가 끼어들 수 있다는 뜻이다.
이런 경우 어떻게 되는지 살펴보자.
Turnaround time이 훨씬 개선되었다.
PSJF의 경우 우선순위가 있으므로, 여러가지 문제점이 생기는데
대표적으로 우선순위 높은 애들이 계속 쓰는 Starvation problem이 있다.
좀이따 MLFQ에서 살펴보자.
4) Round Robin
무언가 잊지 않았는가?
위에서 여러가지 Metric을 설명해놓고선 Turnaround time만 보고있었다.
이번엔 Response time을 살펴보자.
어떻게 하면 Response time을 줄일 수 있을까?
아마 A, B, C를 더 잘게 쪼개는 게 대안이 될 것이다.
이를 Round Robin 방법이라고 한다.
물론... 장점만 있지는 않다.
인터럽트가 많아지니 context switching이 잦아져 overhead가 커진다.
별로 신경은 안쓰이겠지만, time slice가 너무 짧을 경우 queue가 길어져 메모리를 많이 차지한다.
그러니 적절한 time slice를 찾는게 중요하다고 할 수 있다.
그리고 예상했겠지만, turnaround time과 response time은 최적화 했을 때에는 trade-off 관계에 있다.
3. MLFQ
(0) 개요
여태까지는 I/O가 없는 경우만을 살펴보았다.
이제 Job A에 I/O가 계속 들어오는 경우를 살펴보자.
흠... CPU가 놀고있다.
우리 공돌이들은 이런거 좋아하지 않는다.
보기에 한결 낫다.
이럴 때 A의 I/O를 sub-job 취급한다고 한다.
A != A(I/O) 요렇게.
그런데, 우린 공리로 각 프로세스의 실행시간을 미리 안다고 했었다.
실제론 모르지 않나?
그러면 위의 방식을 Round robin 말고 PSJF로는 못한다는 소리 아닌가?
가장 짧은 Job이 뭔질 모르는데 어떻게 우선순위로 놔?
그러면 가장 짧은 Job을 우선 순위로 놓지 말고, 긴 애들을 낮은 순위로 놓으면 되겠네.
어떻게 긴지 아나? 여태까지의 실행시간을 보면 알지.
그런 의미에서 도입된게 MLFQ다.
그리고 MLFQ를 보기 전에 짤막하게 MLQ을 보고 가자.
(1) Multi-Level Queue
PSJF는 하나의 대기열에 우선순위가 다른 여러 Job이 생긴다.
왜 그런짓을 하지? Segregated List같은 모양을 쓰면 우선순위가 다른 여러 대기열을 만들 수 있는데.
음. 나쁘지 않은 생각인 것 같다.
문제는 3 4 5 6 ... 의 크기를 가진 애들은 거의 기회를 못 받는다는 것이다.
아까전에 PSJF에서 이 문제를 어떻게 해결했지? Round Robin을 썼다.
그게 뭐였더라? 일정 시간으로 Job을 자르는 것이었다.
어 그럼 Job 시간 다 같아지니까 우선순위가 의미가 없어지는 거 아냐?
그러면 Multi-level queue에 PSJF 말고 Round Robin 결합한 알고리즘은 어떻게 구현하면 될까?
(2) Multi-Level Feedback Queue
Feedback이라는 이름이 붙었다.
MLQ와는 달리 Queue간에 내용물이 이동 가능하다는 뜻이다.
잘 모르겠으면 도식화해서 보자.
Q2>Q1>Q0이라는 우선순위로 봤을때, Round robin을 했으면서도 PSJF와 비슷한 결과물이 나왔다.
신기하다!
MLFQ에는 몇가지 규칙이 있다.
1) A 우선순위 > B 우선순위 면 A를 실행
2) A와 B의 우선순위가 같으면 Round Robin
3) 새로운 Job이 들어오면 Highest Priority
4) 한 Job이 time slice 하나를 다쓰면 우선순위 하나 내림, 다 쓰기 전에 CPU를 놓으면 우선순위 유지
와. 꽤 합리적으로 보인다. 긴 Job은 점점 낮아지고, 짧은 Job은 금방 해치울 수 있겠네.
문제가 당연히 있다.
1) Starvation 문제
I/O는 짧은 Job이니 Highest Priority고, time slice를 다 쓰기 전에 끝나니 계속 Highest하다.
근데 다른 종류의 I//O가 계속 들어오면 A는 작업을 하지를 못한다.
I/O의 우선순위를 낮추면 문제가 많이 생길테니까, A의 우선순위를 올려줘야겠다.
일정 시간마다 모든 Job(또는 오랫동안 실행이 안된 Job)의 Priority를 초기화해주는 Priority Boosting 방법이다.
A의 작업을 어느정도 보장 받을 수 있다.
만약 Job 수가 많아서 한번에 모두 boosting하기 부담스럽다면, 시간에 따라 천천히 올려주는 Aging 방법도 있다.
당연히 두 방법 모두 boosting/aging period에 따라 성능이 크게 영향받는다.
2) Gaming 문제
다 차지하면 boosting하고 마는데, 얘는 가지고 논다.
time slice의 99%만 쓰면 일단 다 쓴건 아니니 priority가 내려가질 않는다.
이런 경우 단순하게 생각해서, B가 해당 priority를 사용한 총 시간을 계산하면 된다.
Time allotment를 지정해서, 한 Job이 같은 Priority내에서 allotment를 다 사용했으면 time slice 전부를 사용했는지 여부와 관계 없이 priority를 내려준다.
3) 성능 조절
위의 조건들을 다 만족시키는 MLFQ를 만들면 구조가 아주 복잡하다.
성능에 변수가 너무나도 많은데, 대표적인 예시를 들어보자.
- Priority level
- Time slice interval
- Boosting/Aging period
- Time allotment
이거 하나라도 설계를 잘못하면 그냥 Roundrobin 무식하게 때려넣는 것보다 성능이 안나올 수 있다.
4. Fair-share Scheduling
여태까지 난리를 친 이유가 다 무엇이냐?
급한일, 중요한일을 먼저 하자는 것이다.
근데 Fair-Share 는 먼저 하는 것 보다는, CPU 사용률의 일정 퍼센트를 차지하는 걸 목표로 한다.
코딩도 아주 쉽고, 현실적으로 잘 먹힌다.
두가지만 살펴보자.
(1) Proportional Share
Job 별 보유 티켓을 전체 티켓 수로 나누어, 확률로 결정한다.
중요한 Job은 티켓을 많이 주고, 덜 중요한 Job은 적게주면 되겠다.
코드도 아주 쉽다. linked list로 구현하면 된다.
int winner = rand() % 100;
int counter = 0;
node_t *job = scheduler->head;
while(job) {
counter += job->num_tickets;
if(counter > winner) { break; }
job = job->next;
}
if(job) {
scheduler->run(job);
}
(2) Stride Scheduling
위의 방법은 Random assignment를 사용하기 때문에,
같은 프로세스들이 계속 존재하며 100번 이상 실행되지 않고
금방 끝나는 I/O같은 Job만 들어올 경우 ticket과 같은 비율을 보장하지 않는다.
Stride Scheduling은 이를 보완한 방법으로,
중요치가 클 수록 작은 stride를 부여받아, 현존 Job중 가장 작은 누적 stride를 보유한 Job을 실행한다.
위의 경우 ABCAAABAAABAAABAAABC 순으로 실행되게 되는데,
비록 실행 순서가 randomness하게 정해지지는 않지만 fair함은 훨씬 정교해졌다.
아, Stride는 어떻게 부여하냐고?
위에 Proportional할 때 사용한 ticket을 그대로 이용해서,
큰 수 N을 ticket으로 나눈 수를 stride로 사용하면 된다.
위의 경우는 A,B,C의 ticket이 각자 75, 20, 5 였기 때문에 300/75, 300/20, 300/5를 부여하였다.
실제 코드를 짤 때는 N = (A->ticket)*(B->ticket)*(C->ticket) 으로 해서 N=7500으로 하는 게 편하다.
5. 기타
(1) Real Time
주로 MCU나 AP에서 많이 쓰이는 방식으로, 전체 process를 끝내기 위한 deadline이 정해져 있는 경우다.
주로 센서(주기적 인터럽트)를 많이 사용하고 신뢰성이 중요시 여겨지는 항법, 로봇, 차량 제어 등에서 많이 사용된다.
비주기적 인터럽트나 Conflict(dispatch)가 발생하면 커널로 스위칭하는 지연이 꽤 길기 때문에 최대한 non-determinstic한 커널모드의 사용을 줄여야한다.
이러한 특성 때문에 기존의 방법과는 다른 스케쥴링 방식이 필요하다.
1) Rate Monotonic
우선순위를 작업시간이나 fair CPU가 아닌 출현 빈도에 놓는 스케쥴링 방법이다.
2) Earliest Deadline First
데드라인이 먼저 오는 것을 우선순위의 위로 놓는다.
(2) Process 외의 적용
여태까지는 process간의 Scheduling을 가정했는데,
다른 곳에서도 Job의 단위가 나올 수 있다.
1) Thread
Thread 역시 일종의 Scheduling을 필요로 하는 경우가 많다.
한 프로세스 안에서 실행되기에, 주로 유저는 유저끼리, 커널은 커널끼리 경쟁하게 된다. 유저끼리는 preemptive하고 커널끼리는 non-deterministic하므로 주의해야한다.
주의해야할 점은, process는 서로 메모리공간을 공유하지 않지만, thread는 공유하기 때문에 오작동할 염려가 크다는 점이다.
2) Multi-Core
한 프로세서에 코어가 여러개 있는 경우 Scheduling이 필요하다.
이 경우 캐시를 공유하기에 유저모드 thread간 스케쥴링과 마찬가지로 데이터 수정 면에서 주의해야한다.
캐시를 사용하지 않고 메모리에서 직접 로드할 경우 버스의 전송속도로 인해 memory stall(대기시간)이 발생하는데,
대기시간 동안 서로 스위칭하면서 stall cycle을 번갈아 사용할 수 있어 효율적이다.
3) Multi-Processor
모두 동일 성능의 CPU임을 가정했을 때(Homogenous),
Asymmetric(마스터 프로세서가 정해줌) <-> Symmetric(각 프로세서마다 스케쥴러 별도)
Soft Affinity(프로세서를 바꿀 수 있음) <-> Hard Affinity(프로세서를 바꾸지 못함)
UMA(메모리 접근시간이 같음) <-> NUMA(메모리 접근시간이 다름)
Push Migration(바쁜 프로세서가 넘겨줌) <-> Pull Migration(한가한 프로세서가 가져옴)
작업 균형을 맞추기 위해선 각 프로세서별로 할당된 작업량이 비슷해야하는데,
- NUMA이고 Soft Affinity인 경우 프로세서를 가장 빠른 위치로 바꾸는 게 좋음
- Asymmetric한 경우 작업량을 분배하기에 더 좋음
- Migration 활성화가 중요함
(3) 평가하는 법
1) Deterministic Modeling
Throughput, Wating time, Turnaround time, Response time 기준으로 평가하는 방법이다. 가장 일반적으로 사용된다.
2) Queueing Modeling
queue의 overflow, underflow여부와 남은 Job 개수의 표준편차를 기준으로 평가하는 방법이다. 가장 현실적인 성능을 나타낸다.
3) Simulation
Golden Testbench 기준으로 시뮬레이션하여 평가한다. Testbench 만들기 빡세다.
4) Implementation
실제 프로그램을 돌려서 평가한다. Firestrike를 생각하면 된다.
'System > OS' 카테고리의 다른 글
| [OS] Process (0) | 2020.05.02 |
|---|---|
| [OS] Introduction, Properties (0) | 2020.05.01 |
