선점 스케줄링
선점 스케줄링
- 선점 스케줄링이란 우선순위가 높은 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 점유하는 스케줄링 기법이다.
- 비교적 응답이 빠르다는 장점이 있으나, 처리 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 계속 들어오는 경우 오버헤드가 발생하게 된다.
- 선점 스케줄링 알고리즘으로 다음과 같은 기법들이 있다.
- RR (Round Robin)
- SRT (Shortest Remaining Time)
- 다단계 큐 (Multi-level Queue)
- 다단계 피드백 큐 (Multi-level Feedback Queue)
RR (Round Robin)
- 라운드 로빈은 프로세스마다 같은 크기의 CPU 시간을 할당받는다.
- 프로세스가 할당된 시간 내에 작업을 처리하지 못하면 준비 큐 리스트의 맨 뒤로 보내지며, CPU는 대기 중인 다음 프로세스로 넘어간다.
- 모든 프로세스가 CPU를 균등하게 점유하므로 기아현상이 발생하지 않는다.
- 할당된 시간이 크면 FCFS와 유사해지며, 작으면 잦은 문맥교환으로 인한 오버헤드가 발생한다.
기아현상(Starvation)이란?
자신보다 우선순위 높은 프로세스 때문에 오랫동안 CPU 할당을 받지 못하고 무한정 기다리게 되는 현상
SRT (Shortest Remaining Time)
- SRT는 이전 비선점형 스케줄링 포스팅에서 언급한 SJF를 선점형으로 변경한 스케줄링 기법이다.
- 남은 시간이 가장 적은 프로세스를 먼저 수행한다.
- 만약 더 짧은 처리 시간의 프로세스가 들어오면 실행 중인 프로세스를 중단시키고 더 짧은 처리시간의 프로세스를 처리한다.
- 처리 시간이 짧은 프로세스가 계속 추가되면 기아 현상이 발생할 수 있다.
다단계 큐 (Multi-level Queue)
- 작업들을 각 목적에 맞게 여러 종류의 그룹으로 분할을 한다.
- 각 그룹의 큐에는 독자적인 스케줄링 알고리즘(라운드 로빈, FCFS 등)을 사용할 수 있다.
- 더 높은 우선순위를 갖는 큐가 비워지지 않는 경우에는 기아 현상이 발생할 수 있다.
다단계 피드백 큐 (Multi-level Feedback Queue)
- 각 준비상태 큐마다 서로 다른 CPU 할당 시간을 부여하여 처리하지 못한 프로세스를 다음 단계의 큐로 이동시킨다.
- 하위 단계로 내려갈수록 할당시간을 증가 시킨다.
- 마지막 단계에서는 라운드 로빈 또는 FCFS로 처리한다.
- 최하위 큐에서 너무 오래 대기 시 에이징 기법을 통해 상위로 이동시켜 처리한다.
면접에 나올 수 있는 질문
- 선점형 스케줄링에 대하여 설명
- 선점형 스케줄링에 사용되는 알고리즘에 대하여 설명
참고
기여자
Junho Moon
📦