<운영체제> CPU SCHEDULING - Priority, HRRN ,Round-Robin
본 게시물은 영남대학교 곽종욱 교수님의 강의를 기반으로 작성됨
Priority(우선순위) 스케쥴링이란?
- 프로세스의 PCB의 proc내에 있는 Priority라는 정수값을 토대로 CPU스케쥴링을 진행하는 방식
- 이 또한 선점과 비선점 방식이 가능하고, 만약 비선점형식을 취하게 될 경우, 우선순위가 높은 프로세스가 레디큐에 들어왔음에도 실행 되지 않는 Priority-Inversion이 발생 할 수 있다.
- 선점과 비선점 둘 다 공통적으로 Starvation의 문제를 발생 시킬 수 있다.
- Starvation해결법 : Aging을 사용
HRRN이란?
- Highest Response Ratio Next의 약자로 높은 Response Ratio를 가지는 프로세스를 실행시킨다.
- 위 단락의 Aging기법의 종류로서, Starvation에 대한 solution이다.
- Response Ratio = (waiting time + required CPU time) / required CPU time
- 즉, 대기시간이 증가하면 Response Ratio가 증가하며, 실행될 확률이 높아진다.
- 오랫동안 레디큐에 있었던 프로세스들에 대한 조치가 이뤄지는 정책이다.(Starvation방지)
- 만약 대기시간이 동일할 경우, 실행시간(required CPU time)이 짧은 프로세스가 Response Ratio가 더 높다.
Round-Robin이란?
- Time-Sharing을 사용하는 CPU의 경우 필수적으로 사용한다.즉 우리가 사용하는 대부분의 CPU 스케쥴링에 포함이 되어 있다고 봐도 무방하다.
- FIFO에 근간을 두고 있지만, 완전히 다른 성능을 자랑한다.
- 선점형 방식으로만 구현된다.
- 먼저 time-slice 또는 time-quantum 이라는 아주 작은 시간 단위를 지정하고 난 뒤, 레디큐에 순서대로 대기중인 프로세스들을 해당 time-quantum만큼 실행시키고 레디큐의 가장 뒤쪽으로 보내는 방식이다.
- 즉, 짧은 시간 동안 CPU에 들어가서 실행되고, 다시 레디큐의 마지막으로 들어가는 구조이다.
- 이러한 방식의 가장 큰 장점은 response-time(레디큐에 들어간 시점부터 작업이 시작되는 시점까지의 시간)을 굉장히 줄일 수 있다.
Round-Robin 구조
Round-Robin의 한계
- 기본적으로 CPU에서 프로세스의 실행을 바꾼다는 동작 또한 시간이 소요되는 동작인데, 만약 이러한 동작 소요 시간이 time-quantum보다 크다면, 비효율적인 방식 될것이다.
- 즉 context-switching 보다 time-quantum 이 큰 값이어야만 더 효율적인 스케쥴링 방식이 될것이다.
- 그렇다고 해서 time-quantum을 매우 큰 값으로 설정하게 되면 사실 상 FIFO 와 다를게 없는 알고리즘이 되어버리므로 이 부분 또한 신경을 써야한다.
Time-Quantum vs Context Switch Time
Time-Quantum과 Turnaround Time
- 위의 그림을 보면 두 개의 값들 사이에 특정한 패턴 또는 기울기는 존재하지 않음
- 하지만, Turnaround Time은 Time-Quantum에의해서 그 값이 변경된다, 즉 Time-Quantum에 종속적인 변수이다라고 볼 수 있다.
- Turnaround Time : 레디큐에 들어가는 시점부터 Job이 끝나는 시점까지의 시간