이번 수업은 지난 수업에서도 했던 CPU Scheduling에 대한 내용이 나왔다.
그래서 이에 대해서 주요한 것만 정리하려 한다!
CPU Scheduling 역할
스케줄링은 다음과 같은 역할을 수행하기 위해 필요하다!!
⭐ 프로세스 안에 있는 CPU burst와 I/O burst를 관리하는 역할
⭐ reday 상태의 프로세스 중 CPU를 누구에게 할당할지 결정하는 역할
공평 보다는 효율적인 스케줄링이 되어야함
Scheduling Algorithm
- 비선점형(nonpreemptive)
: CPU를 강제로 빼앗지 않고 자진 반납
- 선점형(preemptive)
: 강제로 빼앗음
Scheduling Criteria
스케줄링이 잘 되었는지에 대한 성능 척도(performance index)이다.
이는 두 가지 입장으로 분류할 수 있다.
-
System 입장에서의 성능척도
: CPU 하나로 최대한 많은 일을 시킬 수 있는지~- CPU utilization
- Throughput
-
Process 입장에서의 성능척도
: CPU를 빨리 얻어서 빨리 끝낼 수 있는지~- Tunrnaround time
- Waiting time
- Response time
구체적으로 알아보자!
1. System에서의 성능 척도
system의 입장은 음식점의 사장님 입장과 같다.
고용한 직원(CPU)가 최대한 많은 일을 했으면 하는 것이다!
1) CPU utilization
- 이용량
- 전체 시간에서 CPU가 놀지 않고 일한 비율
👉 CPU에게 최대한 많은 일을 시켜라! CPU는 중요한 자원이니까!
2) Throughput
- 처리량
- 주어진 시간동안 몇개의 작업을 완료했는가?
💡 CPU가 일을 많~이 해주는 알고리즘이 좋다!
2. Process에서의 성능 척도
👉 가능한 빨리 처리하고 집에 가고싶음
process의 입장은 손님 입장과 비슷하다.
손님이 가능한 빨리 집에가고싶진 않겠지만, 받을 음식(CPU)를 빨리 받고싶은 것은 마찬가지일 것이다.
1) Turnaround time
- 소요시간, 반환시간
- CPU를 사용하기 위해 들어와서 대기한 시간부터 다 쓴 시간까지 걸린 시간
ex. 코스요리 주문 시, 각 음식을 기다리는 시간과 먹은 시간을 모두 합한 값
2) Waiting time
- 대기시간
- CPU를 사용하기 위해 기다린 시간
- CPU를 뺏기고 다시 할당받는 과정에서 걸린 시간의 총합
ex. 각 음식을 받을 때까지 걸린 시간
3) Response time
- 응답시간
- CPU를 사용하기 위해 들어와서 처음으로 CPU를 얻기까지 걸린 시간
ex. 첫 번째 음식을 받을 때까지 걸린 시간
CPU Scheduling Algorithm
1. FCFS(First-Come First-Served)
- 먼저 들어온 프로세스를 먼저 처리하는 방식
- 효율적이지 ❌
- 따라서, 먼저 들어온 프로세스가 길수록 다음 프로세스가 기다려야 하는 시간이 늚 👉 convoy effect
2. SJF(Shortest-job-first)
'FCFS 방법이 비효율적이었다. 아무래도 프로세스 시간이 짧은 순으로 처리하는게 나을것 같은데?' 해서 나온 알고리즘이다!
- CPU burst가 가장 짧은 작업부터 처리!
- average waiting time이 가장 짧은 알고리즘
- 선점형, 비선점형 방식으로 구분할 수 있다.
SJF는 FCFS보다 더 효율적이긴 하지만, 문제가 존재한다.
<문제점>
-
starvation(기아현상): 우선순위가 낮은 프로세스가 너무 오랜 시간 기다려야 함
👉 영원히 CPU 할당을 못받을 수도 있음 -
CPU 사용시간을 미리 알 수 없음
👉 프로세스가 과거에 사용한 CPU 사용 이력을 보고 다음 사용 시간을 추정함
( = exponential averaging)
3. Priority Scheduling
- 우선순위가 높은 프로세스 순으로 CPU 할당
- 선점형, 비선점형 방식으로 나눌 수 있음
SJF와 유사한 방식을 가지고 있어 문제점 또한 비슷하다.
이러한 기아현상을 해결하기 위한 방법이 있다.
🔻
aging(노화)
: 아무리 낮은 우선순위를 갖고 있더라도 시간이 지나면(나이가 들면~) 우선순위가 조금씩 높아짐
4. Round Robin(RR)
현대적인 컴퓨터 시스템의 CPU Scheduling은 RR 알고리즘에 기반을 둔다.
- 각 프로세스에게 동일한 크기의 할당시간을 줌
- 할당시간이 끝나면 다른 프로세스에게 CPU를 선점당하고, 맨 뒤에서 줄을 섬
👉 즉, RR은 선점형 방식
👉 응답 시간이 빨라진다 & 대기시간이 줄어든다는 큰 장점!
그러나 이것도 문제점이 존재한다.
<문제점>
- 할당 시간이 너무 작으면 context switch가 빈번하게 발생해 오버헤드가 커진다.
