스케줄링 기법(Scheduling Method)

지난 포스팅에서 프로세스 스케줄링과 종류에 대해 다뤘다. 이번에는 선점, 비선점 스케줄링의 기법들에는 어떤 것들이 있는지 간단히 포스팅 하려고 한다.

---

비선점형 스케줄링(Non-preemptive scheduling)

FIFO(First In First Out)

가장 간단한 방식으로 선입선출의 방식이다. 먼저 들어오면 먼저 나가는 방식. 아무리 중요한 작업이 있다 하더라도 그 작업보다 먼저 들어온 작업이 끝나기 전까지는 절대 먼저 실핼될 수 없는 비효율적인 방식.

FIFO라고도 하고 FCFS(First Come First Served)라고도 한다.

SJF(Shortest Job First)

평균 대기 시간을 최소화 하기 위해 CPU점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식이다.

실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 무기한 연기 상태에 빠질 수 있다는 단점이 있다.

HRN(Highest Response-ratio Next)

실행 시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로 대기 시간과 서비스 시간을 이용하는 방식.

' 우선순위 = ( 대기시간 + 서비스시간 ) / 서비스 시간 '의 에이징 기법*을 이용하여 우선순위를 계산하여 우선 순위가 높은 것부터 실행하는 방식.

에이징 기법 - 프로세스 자원을 기다리고 있는 시간에 비례하여 우선순위를 부여함으로써 무기한 연기의 문제를 방지하는 기법을 말한다.

---

선점형 스케줄링(Preemptive scheduling)

SRT(Shortest Remaining Time)

비선점 스케줄링인 SJF기법을 선점형태로 변경한 기법이다. SJF처럼 CPU점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식. 단지 차이점은 선점형으로 바뀌어 중요한 프로세스가 있으면 점유시간이 길어도 먼저 실행시킬 수 있는 권한이 생겼다는 점이다.

RR(Round Robin)

프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간 단위로 CPU를 할당하는 방식이다. 보통 시간 단위는 10ms~100ms정도이고 시간 단위동안 수행한 프로세스는 준비큐의 끝으로 밀려나게 된다. 문맥교환의 오버헤드가 큰 반면, 응답시간이 짧아지는 실시간 시스템에 유리하다. 할당하는 시간이 클 경우 비선점 FIFO 기법과 같아지게 된다.

MLQ(Multi-Level Queue, 다단계 큐)

프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비 상태 큐를 사용하는 기법

프로세스가 특정 그룹의 준비 상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없다.

하위 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 준비 상태 큐에 프로세스가 들어오면 상위 프로세스에게 CPU를 할당해야 한다. 각 준비 상태 큐에서는 RR기법이 적용된다.

Level1 큐가 모두 완료되어야 Level2 큐의 작업이 CPU를 사용할 수 있고, Level3도 마찬가지이다. 하위 단계 큐에 있는 작업을 진행중이더라도 상위 단계 큐에 작업이 들어오면 상위 단계 큐의 작업을 우선적으로 실행한다.

MFQ(Multi-Level Feedback Queue, 다단계 피드백 큐)

특정 그룹의 준비 상태 큐에 들어간 프로세스가 다른 준비 상태 큐로 이동할 수 없는 다단계 큐 기법을 보완하여 다른 준비 상태 큐로 이동할 수 있도록 개선한 기법이다.

출처 : http://blog.naver.com/bsy9109/130167321031