4 min read

<운영체제> CPU SCHEDULING - Priority, HRRN ,Round-Robin

본 게시물은 영남대학교 곽종욱 교수님의 강의를 기반으로 작성됨

Priority(우선순위) 스케쥴링이란?

  1. 프로세스의 PCB의 proc내에 있는 Priority라는 정수값을 토대로 CPU스케쥴링을 진행하는 방식
  2. 이 또한 선점과 비선점 방식이 가능하고, 만약 비선점형식을 취하게 될 경우, 우선순위가 높은 프로세스가 레디큐에 들어왔음에도 실행 되지 않는 Priority-Inversion이 발생 할 수 있다.
  3. 선점과 비선점 둘 다 공통적으로 Starvation의 문제를 발생 시킬 수 있다.
  4. Starvation해결법 : Aging을 사용

HRRN이란?

  1. Highest Response Ratio Next의 약자로 높은 Response Ratio를 가지는 프로세스를 실행시킨다.
  2. 위 단락의 Aging기법의 종류로서, Starvation에 대한 solution이다.
  3. Response Ratio = (waiting time + required CPU time) / required CPU time
  4. 즉, 대기시간이 증가하면 Response Ratio가 증가하며, 실행될 확률이 높아진다.
  5. 오랫동안 레디큐에 있었던 프로세스들에 대한 조치가 이뤄지는 정책이다.(Starvation방지)
  6. 만약 대기시간이 동일할 경우, 실행시간(required CPU time)이 짧은 프로세스가 Response Ratio가 더 높다.

Round-Robin이란?

  1. Time-Sharing을 사용하는 CPU의 경우 필수적으로 사용한다.즉 우리가 사용하는 대부분의 CPU 스케쥴링에 포함이 되어 있다고 봐도 무방하다.
  2. FIFO에 근간을 두고 있지만, 완전히 다른 성능을 자랑한다.
  3. 선점형 방식으로만 구현된다.
  4. 먼저 time-slice 또는 time-quantum 이라는 아주 작은 시간 단위를 지정하고 난 뒤, 레디큐에 순서대로 대기중인 프로세스들을 해당 time-quantum만큼 실행시키고 레디큐의 가장 뒤쪽으로 보내는 방식이다.
  5. 즉, 짧은 시간 동안 CPU에 들어가서 실행되고, 다시 레디큐의 마지막으로 들어가는 구조이다.
  6. 이러한 방식의 가장 큰 장점은 response-time(레디큐에 들어간 시점부터 작업이 시작되는 시점까지의 시간)을 굉장히 줄일 수 있다.

Round-Robin 구조

Round-Robin의 한계

  1. 기본적으로 CPU에서 프로세스의 실행을 바꾼다는 동작 또한 시간이 소요되는 동작인데, 만약 이러한 동작 소요 시간이 time-quantum보다 크다면, 비효율적인 방식 될것이다.
  2. context-switching 보다 time-quantum 이 큰 값이어야만 더 효율적인 스케쥴링 방식이 될것이다.
  3. 그렇다고 해서 time-quantum을 매우 큰 값으로 설정하게 되면 사실 상 FIFO 와 다를게 없는 알고리즘이 되어버리므로 이 부분 또한 신경을 써야한다.

Time-Quantum vs Context Switch Time

Time-Quantum과 Turnaround Time

  • 위의 그림을 보면 두 개의 값들 사이에 특정한 패턴 또는 기울기는 존재하지 않음
  • 하지만, Turnaround Time은 Time-Quantum에의해서 그 값이 변경된다, 즉 Time-Quantum에 종속적인 변수이다라고 볼 수 있다.
  • Turnaround Time : 레디큐에 들어가는 시점부터 Job이 끝나는 시점까지의 시간