스케줄링 알고리즘의 선택 기준

스케줄링 알고리즘을 비교할 때 참조할 수 있는 기준은 다음과 같다.

1) 프로세서 사용률 - CPU가 놀지 않고 얼마나 많이 사용되고 있는가?
2) 처리율 - 단위시간당 처리하는 일의 양
3) 반환시간 - 수행 요청을 한 다음 끝날때까지 걸리는 시간
4) 대기시간 - 작업이 준비 큐에서 기다리는 시간
5) 반응시간 - 대화형으로 동작할 때 작업 요청 후 반응하는데 까지의 간격

라운드 로빈 스케줄링

라운드 로빈 스케줄링은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나이다.

라운드 로빈 스케줄링은 작은 단위의 시간인 규정 시간량(time quantum)또는 시간 할당량(time slice)을 정의한다. 보통 규정 시간량은 10ms ~ 100ms정도이다. 준비 큐를 순환 큐로 설계해서 스케줄러가 준비 큐를 돌아가며 한 번에 한 프로세스에 정의된 규정 시간량만큼 프로세서를 제공한다. 준비 큐는 FIFO(First In First Out) 큐로 되어있어 새로운 프로세스를 추가할 때는 준비 큐의 맨 뒤에 붙인다.

스케줄러는 준비 큐의 가장 앞부분의 프로세스에 프로세서를 할당하는데, 해당 프로세스가 규정 시간 안에 작업을 마친 경우엔 프로세서가 준비 큐의 다음 프로세스에 할당된다. 규정 시간을 초과한 경우에는 운영체제가 인터럽트해 중단된 프로세스의 레지스터들을 PCB에 저장하고 프로세스는 준비 큐의 마지막 위치에 들어간다.

라운드 로빈 스케줄링의 장단점

장점 1. 모든 프로세스가 프로세서의 동일한 점유율과 제한된 대기시간으로 공정해 기아상태가 발생하지 않는다.
  2. 실행 큐에 프로세스 수를 알고 있을 때 구현이 용이하다
  3. 강한 상호작용과 프로세스의 짧은 응답시간, 특히 프로세스 최악의 응답시간을 알 수 있다.
  4. 작업 길이가 다양할 때는 이전 작업을 마친 후보다 규정 시간량을 마치고 다음 작업으로 이동하기 때문에 평균 대기시간이 FIFO와 최소작업 우선 스케줄링보다 적다.
단점 1. 성능은 규정 시간량의 길이에 따라 달라지므로 작업이 비슷한 길이가 좋다. 너무 길면 FIFO와 다를게 없고 너무 짧으면 문맥교환이 지나치게 많이 이루어져 오버헤드가 크다.
  2. 하드웨어 타이머가 필요하다.
  3. 미완성 작업은 각 규정 시간량을 마친 후 프로세서를 기다리므로 평균 처리 시간이 높다.

 

 

다단계 큐 스케줄링

각 작업을 여러개의 큐에 분할하여 스케줄링 하는 방식이다.

각 큐는 각자 독자적인 스케줄링을 가지고, 고정된 선점 우선순위를 가진다.

이때 하위 우선순위를 가진 큐는 상위 우선순위를 가진 큐가 다 처리되어야만 처리가 가능하다. 이 때문에 기아 상태가 발생할 수 있다. 

다단계 피드백 큐 스케줄링과 다른 점은 작업이 하나의 큐에 고정된다는점이다.

다단계 피드백 큐 스케줄링

모든 프로세스는 다 같이 가장 우선순위가 높은 큐에 들어온다. 이 때 큐에 지정된 time-quantum을 채운(초과한) 프로세스는 그보다 한단계 아래 우선순위의 큐에 들어가게 된다.

 

HRN 스케줄링

각 작업의 우선순위에 따라 서비스해주는 스케줄링 방법이다.

이 때, 우선순위는 다음과 같이 정한다.

우선순위 = (서비스를 받을 시간 + 대기한 시간)/서비스를 받을 시간

HRN 스케줄링은 자원을 효율적으로 사용하고, 기아가 발생하지 않는 특징이 있다.

이에 반해 오버헤드가 높은 단점이 있다.

 

+ Recent posts