티스토리 뷰
CPU 스케쥴링
하나의 cpu를 여러 가지 프로세스가 메모리에 로드되어서, 프로세스가 cpu를 선점해서 concurrent 하게 실행하는 것을 멀티 프로세싱, 멀티프로그래밍, 멀티 태스킹이라고 한다. 이때 CPU의 효율성을 높이기 위해 CPU스케쥴링을 한다.
cpu burst time, i/o burst time
CPU burst time이 많은 것을 CPU bound라고 하고, I/O burst time이 많은 것을 I/O bound라고 한다.
선점형(preemptive)과 비선점형(non-preemptive)
선점형은 현재 작업 중인 프로세스를 쫓아내고 CPU를 점유하는 방식이다. 반면에 비선점형은 프로세스가 CPU를 선점하고 나면 자발적으로 나오기 전까지 내버려 두는 방식이다.
Decision Making
프로세스가 running 상태에서 waiting 상태로 바뀌는 경우 비선점형
running -> ready 선점형
waiting-> ready 선점형
프로세스가 terminates 되는 것 비선점형
Dispatcher
Context switch를 해주는 모듈을 dispatcher라 한다. 디스패처는 다음과 같은 기능을 한다.
- 한 프로세스에서 다른 프로세스로 Context switching
- 유저 모드로 바꿈
- 새로운 프로세스의 적당한 위치에 재개함
P0의 PCB를 어딘가 저장하고 P1의 PCB를 어디선가 restore 하는데, 이때 걸리는 시간을 dispatch latency, 즉 디스패처 지연시간이라고 한다. 리눅스에서 vmstat 명령어를 통해 Context switch가 얼마나 일어나는지 확인할 수 있다.
CPU 스케쥴링의 이유
- CPU utilization - CPU가 가능한 한 바쁘게 작업할 수 있도록 하기 위해
- Throughput - 단위 시간당 프로세스 완료 수를 늘리기 위해
- Turnaround time - 프로세스가 시작되고 종료되기까지의 시간을 줄이기 위해
- Waiting time - 어떤 프로세스가 Ready queue에서 대기하는 시간을 줄이기 위해
- Response time - 응답 시간을 줄이기 위해
스케쥴링 알고리즘
FCFS (First-Come, First-Served)
- 비선점형
- 먼저 요청한 프로세스를 먼저 할당하는 방식
- 평균 대기 시간이 CPU burst time에 따라 달라진다.
- Convoy Effect가 발생할 수 있다.
SJF (Shortest-Job-First)
- 작업 시간이 짧은 프로세스를 할당하는 방식
- 만약 작업시간이 같다면 FCFS 방식을 사용
- 평균 대기시간이 가장 적음
하지만, 다음 프로세스의 burst time을 알 수 없기 때문에, 구현할 수가 없다. 따라서 과거의 CPU burst time을 보고 지수적 평균을 내서 예측한다. 그럼에도 불구하고 구현하기가 쉽진 않다. 이상적인 스케쥴링이라고 보면 될 것 같다.
또한, SJF는 선점형일 수도, 비선점형 일 수도 있다. 선점형 SJF를 SRTF(shortest-remaining-time-first)라고 한다.
RR (Round-Robin)
- 선점형 FCFS
- 일정 시간(time quantum)이 지나면 선점
- time quantum을 얼마로 할 거냐에 따라 성능이 좌지우지된다.
Priority-base
- 우선순위를 주어서 스케쥴링 하는 방식, 앞서 정리한 SJF도 Priority-base 스케쥴링
- 기아 현상이 발생할 수 있다. - 해결 방법으로 aging이 있음
- 선점형, 비선점형 둘 다 가능
RR과 Priority를 같이 사용하는 경우가 일반적이다.
MLP (Multi-Level Queue)
Priority의 레벨을 나눠서 스케쥴링하는 방식이다. 여기서 조금 더 발전된 것이 MLFQ이다.
MLFQ (Multi-Level Feedback Queue)
우선순위가 높은 것을 quantum을 상대적으로 적게 주어서, CPU bound가 낮을수록 적은 시간을 점유하도록 하는 것이다.
기타
RTOS의 스케쥴링
Real-Time, 즉 주어진 시간내에 작업을 완료할 수 있어야 하는 OS를 의미한다. Soft Realtime은 중요한 프로세스가 덜 중요한 프로세스보다 빨리 끝나는 것을 보장하는 것이다. Hard real-time은 어떤 임무가 반드시 데드라인 안에 수행되는 것을 보장하는 것이다.
쓰레드 스케쥴링
프로세스로 스케쥴링을 공부했지만, 현대 컴퓨터에서는 실제로 프로세스가 아닌 쓰레드 스케쥴링을 한다. 유저 스레드는 스케쥴링 커널스레드에 매핑만 해줄 뿐, 커널 스레드에만 스케쥴링해준다.