SRT 우선 스케쥴링
Shorted Remaining Time
SJF 스케쥴링과 라운드 로빈 스케쥴링을 혼합한 방식으로, 최소 잔류 시간 우선 스케쥴링이라고 한다.
SJF 스케쥴링의 선점형 버전으로 CPU를 할당받을 프로세스를 선택할 떄 남아 있는 작업 시간이 가장 적은 프로세스를 선택하고, 시간을 할당한다.
P1 대기시간 = 0 + 10 + 9 + 8 = 27
P2 대기시간 = 10 + 9 - 3 = 16
P3 대기시간 = 10 - 4 = 6
총 47 밀리초이므로 평균 대기시간은 15.66 밀리초이다.
SJF 와 비교했을 때, SRT의 평균 대기 시간이 짧으나 이 역시 좋은 알고리즘은 아니다.
현재 실행 중인 프로세스와 큐에 있는 포레슷의 남은 시간을 주기적으로 계싼하고, 남은 시간이 더 적은 프로세스와 문맥교환을 해야하므로 SJF 스케쥴링에는 없는 작업이 추가된다.
또한 SJF와 마찬가지로 프로세스의 종료 시간을 예측하기 어렵고, 아사 현상이 일어나기 때문에 잘 사용하지 않는다.
우선순위 스케쥴링
프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케쥴링 알고리즘이다.
어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있다.
FCFS에서 작업 시간이 짧은 프로세스의 우선순위를 높게 설정했다고 가정해보자.
먼저 온 P1이 실행되고, 그 후 P2,P3 중 우선순위가 높은 것은 P3 이므로 먼저 실행되고 이후 P2가 실행된다.
우선순위 방식은 비선점형, 선점형 방식 모두에 적용할 수 있다.
우선순위 알고리즘은 다음 2가지가 있다.
-
고정 우선순위 알고리즘 : 한번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정된다. 단순하게 구현하지만 운영의 효율성이 떨어진다.
-
변동 우선순위 알고리즘 : 일정 시간마다 우선순위가 변한다. 매번 새로 계산해서 시스템이 복잡하지만 효율적인 운영이 가능하다.
우선순위 스케쥴링은 준비큐에 있는 프로세스의 순서를 무시하고, 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로, 공평성을 위배하고 아사 현상을 일으킨다는 것이 문제이다.
준비 큐에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템 효율성이 떨어진다.
이러한 단점에도 불구하고, 우선순위는 시스템의 효율성이 아니라 프로세스의 중요도를 기준으로 결정한다.
왜냐하면 커널 프로세스보다 일반 프로세스가 우선 실행된다면 커널이 제 역할을 못하기 때문이다.
다단계 큐 스케쥴링
multilevel queue
우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다.
프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다.
프로세스가 큐에 삽입되는 것만으로 우선순위가 결정
고정형 우선순위를 사용하여 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.
우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스가 작업을 할 수 없으므로 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기되는데, 이러한 문제를 해결하기 위한 것이 다단계 피드백 큐 스케쥴링이다.
다단계 피드백 큐 스케쥴링
multilevel feedback queue
우선순위가 낮은 프로세스에 불리한 다단계 큐 스케쥴링의 문제점을 보안한 방식
다단계 큐 스케쥴링과 같이 여러 개의 큐를 사용하지만 CPU를 사용하고 난 프로세스의 우선순위가 낮아지고, 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다.
물론 프로세스의 우선순위가 낮아진다고 할지라도 커널프로세스가 일반 프로세스의 큐에 삽입되지는 않는다.
또 다른 특징은 우선순위에 따라 타임 슬라이스의 크기가 다르다는 것이다.
우선순위가 낮은 프로세스의 실행 기회를 확대하려 하지만, 그렇다고 해도 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스보다 CPU를 얻을 확률이 여전히 낮으므로 CPU를 얻으면 좀 더 오랫동안 사용할 수 있도록 타임슬라이스를 크게 한다.
마지막 큐에 있는 프로세스는 결국 무한대의 타임 슬라이스를 얻어 CPU를 빼앗기지 않고, 끝까지 작업을 마치게 된다. 다단계 피드백 큐에서 마지막 큐에 들어온 순서대로 작업을 마치는 FCFS 스케쥴링 방식으로 동작한다.
오늘날의 운영체제가 일반적으로 사용하는 스케쥴링 알고리즘이며 변동 우선순위 알고리즘의 전형적인 예이다.
참조한 책 및 사이트
쉽게 배우는 운영체제
https://yansigit.github.io/blog/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-cpu-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/