[OS 공룡책] 5. CPU Scheduling
하나의 cpu를 왜 sharing 해야하는지는 처음에 알아봤다
복습해보면
전제는 cpu는 굉장히 빠르기 때문에 처리량에 비해 놀고 있는 상황이고,
cpu utilization 즉 사용량을 극대화 하기 위해 여러가지 프로세스를 번갈아 가며 처리하기 위함
이는 기본적으로 IO bound가 cpu bound보다 훨씬 길기 때문에 발생한다
이제 cpu를 어떤 프로세스에게 어떻게 분배할것인가? 가 스케줄링이다
좀더 구체적으로 ready queue에 들어가있는 프로세스들에게 어떻게 할당할것인가?
크게 두가지가 있는데
- FIFO Queue
- Priority Queue
그리고 구체적인 방법론을 이해하기 위해
- Preemptive 선점형
- Non-preemptive 비선점형
개념이 나온다
이게 말이 좀 헷갈리는데
주체는 cpu 스케줄러이다
cpu 스케줄러가 preemptive하면 즉 선점형이면
현재 돌아가고 있는 프로세스들을 쫓아낼 수 있는 것이고
non preemptive하면 한번 점유한 프로세스는 자발적으로 끝나거나 waiting 상태가 될때까지 돌아간다는 것
그리고 하나더 몰랐던건
context switching때 switch할 다음 작업을 선택하는 것이 스케줄러이고
선택된 작업을 프로세서에게 할당하는 것은 dispatcher라고 따로 있다고 한다
다시 본론으로 돌아와 스케줄링할때 가장 중요한 지표는
- waiting time
- turnaround time
들어가기 앞서
좀 당연해보이지만 헷갈리는 부분은
프로세스를 기준으로 스케줄링한다고 배우는데
실질적으로는 스레드 단위로 스케줄링 하는게 일반적이라고 한다
스케줄링 알고리즘
간단하게 목록부터 보면
- FCFS : first come first served (Non - preemptive)
- SJF / SRTF : Shortest Job First / Shortest Remaining Time First (Non - preemptive / preemptive)
time sharing
- RR : Round Robin
- Priority Based
- MLQ : Multi Level Queue
- MLFQ : Multi Level Feedback Queue
FCFS
가장 간단하다
fifo 큐에 넣어주면 된다
Non - preemptive
waiting time
P1 : 0
P2 : 24
P3 : 27
평균 17초를 기다린다
turn around time
P1 : 24
P2 : 27
P3 : 30
완료될때까지 평균 27초
waiting time
P1 : 6
P2 : 0
P3 : 3
평균 3초를 기다렸다
P1 : 30
P2 : 3
P3 : 6
완료될때까지 평균 13초
들어오는 순서만 바뀌었는데 엄청난 차이가 난다
근본적으로 실행시간이 짧은데도 오래 기다려야 하기 때문에 이런 일이 발생한다
SJF Shortest Job First & SRTF Shortest Remaining Time First
위 문제를 해결하기 위해 실행시간이 가장 짧은 프로세스를 실행하는 아이디어
Non - preemptive OR preemptive
도착 순서와 무관하게 하나의 간트차트가 나온다
waiting time
P1 : 3
P2 : 16
P3 : 9
P4 : 0
평균 7초
왜 preemptive일수도 있는가
P1이 5초 작업이 걸리고
P2가 1초 작업이 걸리는데 P1을 1초 실행중에 P2가 들어온다면
P1 -> P2 -> P1순으로 작업할 수도 있다
이게 SRTF이다
RR Round Robin
CS에서 되게 많이 나오는 말인데 빙글빙글 돈다
그냥 고루고루 돌아가면서 쓰는 방식
preemptive - time sharing
그냥 time quantum
단위시간동안 쓰고 돌아가는 방식이다
보통 10 ~ 100 ms사이를 사용한다고 한다
구현은 circular queue사용
time quantum을 얼마로 두느냐가 굉장히 중요한 알고리즘
너무 적게 줘도 turn around time이 늘어나고
넘누 많이 줘도 문제다
Priority Based
프로세스에 우선순위를 부여해 실행하는 방식이고
모든 프로세스 우선순위가 같다면 FCFS 순으로 먼저 들어온 프로세스를 먼저 처리한다
SJF가 일종의 priorioty based라고 볼 수 있다
-> SJF에서 next cpu burst를 예상해 계산하기 때문 (수행 시간을 우선순위로 두는 것)
이 알고리즘에서는 starvation 문제가 발생할 수 있다
(우선순위가 높은것만 계속 실행하는 문제)
이를 해결하기 위해 aging을 사용할 수 있다
실행하지 못한 프로세스의 우선순위를 높여주는 방법
또한 여기서 preemptive하게 할것인가 non-preemptive하게 할것인가 선택이 존재한다
결론적으로 RR + Priority 섞어서 사용하게 되는데
같은 우선순위를 가지면 RR