0. 새로운 조건 사항
이제 새로운 상황이 부여 되었다. CPU time(burst)과 I/O time(burst) 둘로 나뉘었다. CPU time이란 CPU가 명령어를 실행하는데 소모하는 시간이고 I/O time은 cpu가 I/O 작업하는 걸 기다리는 시간이다. 즉, 이전 7상태 process에서 Running 상태일 때 두 가지 경우가 생긴 것이다. CPU가 작업을 하고 있거나 I/O 작업을 하고 있거나. 이를 CPU-I/O burst cycle이라고 부른다.
이런 특징에 따라서 process 도 종류가 나뉘었다. I/O bound와 CPU bound. I/O 작업 사이사이 CPU burst가 짧은 프로세스를 I/O bound라고 부른다. 이에 반해 I/O 작업 이전에 CPU time이 긴 process를 CPU bound process라고 부른다.
0.1 scheduling 측정 방식
이제 scheduling을 다각도로 바라보기 위해 최적화의 기준도 많아졌다.
* CPU utilization: CPU가 최대한 지속적으로 일을 할 수 있게 끔.
* Throughput: 특정 시간 동안 처리된 process의 수
* Turnaround time: 특정한 프로세스를 실행하고 종료하는데 까지 걸리는 시간
* Response time: process가 "나 실행시켜줘"라고 말하고 cpu가 "그래그래 이제 시작하자" 하는데 걸리는 시간. 즉, process 시작하는 순간까지 걸리는 시간.
* Deadline: deadline을 충족하는 비율
* Fairness: 각 process에게 할당된 시간 중에서 실제로 작업한 시간의 비율.
이런 다양한 측정 기준이 있지만 이 모두를 만족하기는 정말 정말 어렵다. 단지 분야에 따라 더 중요한 기준이 있을 뿐이다.
- Super computer: cpu utilization, throughput이 중요하다. cpu burst가 큰 작업들이어야지 굉장히 빠르게 빠르게 처리 될 수 있다.
- PC: 우리의 컴퓨터는 모니터, 키보드, 마우스, 음향... 등등 상호작용이 굉장히 많다. 즉, I/O bound process에게 유리한 기준들을 중심으로 최적화를 해야한다. 가장 중요한 기준은 turnaround time과 response time.
- Embedded System: 극한의 상황이 굉장히 많다. 예로 자율주행만 하더라도 사고가 날 수 있는 상황을 최대한 빠르게 처리하는 것이 굉장히 중요하다는 것은 납득하기 쉽다. 즉 deadline이 중요하다고 볼 수 있다.
- Server Computer for Cloud Server: 돈 더 많이 낸 사람에게 더 많은 cpu 작업을 할당해 주는 것이 당연지사. 즉 fairness를 만족해야 한다.
1. 스케줄링 알고리즘 들의 분석 비교
- FIFO vs SPN/RR
* A:20, B:30, C:10 인 service time과 0초에 전부 요청이 들어왔다고 가정하자. RR의 time quantum은 10ms이다.
FIFO: avg turnaround time: (20+50+60)/3 = 43.3
| A | A | B | B | B | C |
SPN: avg turnaround time: (10+30+60)/3 = 33.3
| C | A | A | B | B | B |
RR: avg turnaround time: (30+40+60)/3 = 43.3
| A | B | C | A | B | B |
* 이번엔 A,B,C 모두 service time이 20일 때를 가정하자
FIFO: avg turnaround time: (20+40+60)/3 = 40
| A | A | B | B | C | C |
SPN: avg turnaround time: (20+40+60)/3 = 40
| A | A | B | B | C | C |
RR:avg turnaround time: (40+50+60)/3 = 50
| A | B | C | A | B | C |
모든 프로세스의 수행시간이 비슷할 때는 FIFO가 제일 이득임을 알 수있다. 엥? SPN이 이득 아냐? 라고 할 수 있지만 SPN은 수행시간을 예측하고 process들의 수행시간을 계속 비교해야 하기 때문에 FIFO가 훨씬 이득이라고 볼 수있다.
2. 이번엔 RR에 대해 좀 더 자세히 다루어 보자.
예시를 들지 말고 조금 더 원론 적으로 생각해보자. service time의 종류 분포 상관 없이 time slice(quantum)이 작을 수록 response time은 당연히 줄어들 것이다.
만약, service time의 종류가 굉장히 다양하다고 해보자. 이 경우 quantum이 작을 수록 짧은 프로세스는 먼저 끝나고 긴 프로세스는 후반에 집중 케어를 받을 수 있기 때문에 avg turnaround time 측면에서 굉장히 이득일 것이다.
하지만 service time의 종류가 다들 엇 비슷 하다면 q가 작다고 해서 어차피 RR의 대기 큐의 사이즈는 모든 프로세스가 종료될 때 즈음에야 줄어들지 계속 같은 크기를 유지할 것이다.
뿐만 아니라 q의 크기가 작을 수록 context switch의 비용도 커진 다는 것을 기억해야한다. RR은 정말 q 값이 작으면 작을 수록 SPN에 근접할 수 있기도 하지만 switch overhead를 걱정해야 하고 service time이 다양해야 좋지 비슷하면 정말 최악이다..
이번엔 I/O opertion까지 합쳐서 RR을 이야기 해보자. A와 B process가 있는데 A는 10초 일하고 50초 동안 I/O 작업을 해야 한다. B의 경우 I/O 작업이 없는 cpu intensive인 200초가 필요한 작업이다.
RR의 q값이 100일 경우: A-10초 지나고, I/O 50초 하는 동안 B가 100초 작업을 할 것이다. 즉, A의 50초 I/O 작업과 B의 CPU 작업이 동시에 작동하다가 A의 I/O 작업이 끝나도 B는 50의 작업을 더 하게 된다. 다시말해, A는 50초동안 멍 때리고 기다려야 한다.
q값이 10일 경우: A- 10초, I/O 50초 하는 동안 B를 10초씩 5번 작업 하고, 다시 A를 작업을 10초 할 수 있게 된다.
즉 q값이 작을 수록 I/O opertion의 효율은 증가한다. 물론 두 경우 모두 cpu 효율은 100%이다. 계속 작업하니깐. q가 작으면 I/O bound process가 이득이고 클수록 cpu bound process가 이득이다.
2.1 Virtual RR
I/O bound process들은 CPU burst가 quantum에 비해 작을 수 있다. 위의 예 처럼 A의 경우 time slice인100 중에서 10만큼만 쓰고 I/O 하러 가니 굉장히 불리하다. 그렇다고 A같은 녀석들을 위해 time slice를 무작정 줄일 수는 없다. 그래서 보조 큐를 하나 더 만들어 둔다. 이 큐에 있는 프로세스는 ready queue보다 우선순위가 높다.
만약 어떤 프로세스가 time slice를 다 쓰지 못하고 I/O 하고 돌아올 때 보조 큐에 넣는다. 이후 CPU가 다음 process를 고를 때 보조 큐에 있는 녀석을 먼저 고른다.
3. Multi-level FeedBack queue
대기 큐를 여러개 만드는 것이다. 대기 큐 사이에도 우선순위를 두어 어떤 task가 time slice를 다 소진 했음에도 불구하고 cpu 작업이 더 필요하다면 우선순위를 낮춘 큐에 대기시킨다. 해당 큐에서 나온 task들은 time slice를 2배 늘려서 처리해준다. 즉 q 값을 유동적으로 조정할 수 있게 된 것. 물론 I/O block된 녀석들은 blocked queue에 들어간다.
정리하자면 time slice가 작은 queue가 우선순위가 높아 I/O bound를 우대한 것이고 cpu bound일수록 우선순위가 낮은 큐에 들어가면서 time slice를 더 많이 주어 해결해 준다. 심지어 맨 밑의 큐는 FIFO로 설정하기도 한다.
하지만 문제는 이럴 경우 CPU bound인 작업이 밑에 큐에서 기다리고 있는데 I/O bound 작업이 계속 들어와 버리면,, CPU bound는 starvation을 겪게 된다.
4. Multiprocessor Scheduling
지금껏 단일 프로세스의 경우에 대해서만 고민해왔다. 하지만 그 시대는 일찍이 종료 되었다. cpu 여러 종류가 하나의 컴퓨터에 들어갔고 이제 우리는 이에 따라 일을 어떻게 분배할 지 고민 해야한다. 분배 측면에는 ready queue를 공유할지 말지, cache 친화력에 적합한지 등을 고려해야 한다. 고려해야할 사항 부터 하나씩 알아보자.
- Cache affinity(cache 친화력): cpu가 들고있는 cache의 효과를 톡톡이 보고 있는 지를 따진다. 수행시간이 동일한 두 개의 task와 두 프로세스가 있을 때 당연히 하나씩 전담 하는게 제일 좋다. cache 효과를 볼 수 있기 때문이다.
- Concurrency: int x = 3; 이라는 단순한 코드도 assembly로 바꾸면 3줄 가량 된다. 이 3줄 움직 이는 동안 두 개의 cpu가 같이 값을 조정하게 되면 문제가 생길 것이 보인다. 마치 싱글톤 객체에 필드를 선언한 것과 같달까. 이러한 문제를 race condition 또는 Concurrency 문제라고 한다. 이러한 문제를 해결하는 것을 mutual exclusion이라고 부른다. 이에 대한 이야기는 synchronization에서 자세히 다룰 테니 일단 cache affinity를 기준으로 아래 글을 읽어보자.
4.1 SQMS vs MQMS
MS는 multiprocessor의 준말 이고 SQ는 single queue, MQ는 multiqueue를 의미한다. 이 queue는 당연히 ready queue를 의미하지요.
SQ는 각 cpu는 ready queue에 있는 작업을 있는 대로 가져오기만 하면 된다. 만약 4개의 processor에 5개의 task(A~E)가 들어 왔다고 하고 time slice가 똑같다면 아마 하나의 processor에서 보면 중구 난방 5개를 전부 다 실행해야 할 것이다. 첫번째 프로세스는 A -> E -> D -> C -> B -> A / 두번째는 B -> A -> E -> D -> C -> B 이런 느낌.즉 cache affinity가 최악 중의 최악이라고 볼 수 있다.
이를 보안하기 위해 locking, 즉 taks와 cpu 관계를 매칭해서 고정할 수 있지만 이러한 방식은 확장성이 굉장히 떨어진다. 물론 장점도 있다. 단순하다는 것과 cpu가 5개 task 4개 같은 상황이라면야 뭐.. 공간도 아끼고 좋지
MQ는 프로세스마다 전용 ready queue를 만들어 주어 거의 남남처럼 돌아갈 수 있다. 동기화 문제도 피할 수 있고 cache 친화력도 좋을 것이고 각 프로세서마다 ready queue에서 어떤 걸 뽑아 올지 다른 스케줄링 정책을 적용 할 수 있다.
하지만 fairness 문제가 생긴다. 두 프로세서에게 정확하게 같은 작업량을 부여한다는 건 굉장히 어려운 일이다. 만약 어떤 프로세스는 끝나서 놀고 있는데 다른 프로세스는 A,B 작업을 번갈아 하느라 바쁘다면 노는 프로세서에게 A를 맡기거나 하면 되겠다.(migration) 하지만 이 작업은 당연히 cache 친화력과 반비례 하고 cost가 꽤나 큰 작업이다. 적당하게 서로 주고 받게끔 해야 하지만 그 정도를 맞추는 건 쉽지 않다.
5. O(1) scheduler
RTOS에서 자주 볼 수 있는 형태이다. 기본적으로 MQMS이다. int 배열 형식으로 bitmap을 만든다. 또 다른 priority 배열이 존재한다. 해당 배열은 인덱스가 작을 수록 우선순위가 높다. 배열은 linked list 형태로 엮여져 있는 task를 가리키고 있다. priority 배열의 어느 인덱스에 task가 하나라도 있다면 bitmap의 같은 인덱스 위치도 1로 켜져 있다.
그렇게 탐색은 bit map 보고 우선순위 제일 높은 bit 파악 후 해당 idx를 가지고 있는 priority 배열을 보고 task를 실행한다. 실행이 끝난 task는 똑같이 만들어진 expired run queue에 쌓인다. 반대로 현재 진행 중인 queue는 active run queue라고 한다. 이렇게 expired로 빼내는 작업 덕에 active run queue에 있는 우선순위가 낮은 task의 starvation을 해소할 수 있다. 만약 active에 있는 task들이 다 실행 되었을 경우 expired와 active의 이름을 서로 바꾼다.
프로세스의 수와 상관 없이 task를 탐색하는데 int 배열 크기 값 정도면 된다. 그래서 O(1)스케줄러.