스케줄링의 목적
근본적인 스케줄링의 목적은 시스템 성능의 향상이다. 시스템 성능은 응답시간, 작업 처리량, 자원활용도 등의 지표로 결정되는데, 각각의 지표를 향상시키는데 적합한 스케줄링을 사용할 수 있다. 예를들어 대화형, 실시간 시스템에서는 응답시간을 향상시키는 목적의 스케줄링을, 작업의 처리량 향상에는 일괄처리 시스템 등을 적용할 수 있다.
일반적인 시스템에서는 다음과 같은 목적을 공통적으로 지닌다.
-
No starvation : 각각의 프로세스들이 오랜시간동안 CPU를 할당받지 못하는 상황이 없도록 한다.
-
Fairness : 각각의 프로세스에 공평하게 CPU를 할당해준다.
-
Balance : Keeping all parts of the system busy
Batch System 일괄처리 시스템
온라인처럼 일에 대한 요청이 발생했을 때, 즉각적으로 처리하는 것이 아닌 일정기간 또는 일정량을 모아뒀다가 한번에 처리하는 방식
-
Throughput : 시간당 최대의 작업량을 낸다.
-
Turnaround time : 프로세스의 생성부터 소멸까지의 시간을 최소화한다.
-
CPU utilization : CPU가 쉬는 시간이 없도록 한다.
Interactive System 대화형 시스템
온라인과 같이 일에 대한 요청에 대해 즉각적으로 처리하여 응답을 받을 수 있는 시스템
-
Response time : 즉각적으로 처리해야하는 시스템이므로 요청에 대해 응답시간을 줄이는 게 중요하다.
-
Time Sharing System
: 각 프로세스에 CPU에 대한 일정시간을 할당하여 주어진 시간동안 프로그램을 수행할 수 있게하는 시스템 -
Meeting deadlines : 데이터의 손실을 피하며, 끝내야하는 시간 안에 도달해야한다.
Predictability : 멀티미디어 시스템에서의 품질이 저하되는 부분을 방지해야한다.
선점형 vs. 비선점형
preemptive scheduling, 선점형 스케줄링
한 프로세스가 CPU를 할당받아 실행하고 있을 때, 다른 프로세스가 CPU를 사용하고 있는 프로세스를 중지시키고 CPU를 차지할 수 있ㅎ는 스케줄링 기법.
우선 순위가 높은 프로세스를 먼저 수행할 때 유리하고 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 유용. 하지만 잦은 context switching으로 인한 overhead 발생.
e.g. round robin, SRT, 선점 우선 순위 등의 알고리즘
non-preemptive scheduling, 비선점 스케줄링
이미 다른 프로세스에 CPU가 할당되어 있는 경우, 빼앗아오지 못하고 사용이 끝날 때까지 기다리는 스케줄링 기법. 이후 CPU 를 할당받으면 작업이 끝날 때까지 사용 후 스스로 자원을 반납.
응답시간을 예측할 수 있고, 일괄 처리방식이 적합. 모든 프로세스의 요구에 공정.
하지만, 중요도가 높은 작업이 낮은 작업이 끝나기를 기다리는 경우가 발생할 수 있음. 즉, 우선순위 역전이 잦아지며 프로세서를 점유한 프로세스의 응답시간이 전체 평균 응답시간에 영향을 끼치게 된다.
e.g. FCFS(First Come First Served), SJF(Shortest Job First), 우선순위, HRN(Highest Response Next) 등의 알고리즘.
스케줄링 알고리즘
FCFS, First Come First Served (선입 선처리)
가장 간단한 스케줄링 알고리즘으로, 프로세서를 요청하는 순서대로 할당해준다. 이때 구현은 Queue로 하며 FIFO로 진행된다.
장점
- 구현이 쉬움
- Ready Queue에 있는 모든 프로세스가 실행될 수 있어서 starvation(기아상태)이 없다
- 프로세서가 지속적으로 프로세스를 처리하므로 처리율이 높음
단점
- 비선점식이라 대화식 프로세스에는 부적합.
- 장기 실행 프로세스가 단기 실행 프로세스를 모두 지연시켜 평균 대기시간이 길어지게 됨.
SJF, Shortest Job First (최단 작업 우선)
최소작업 우선 스케줄링은 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능할 때 실행시간이 가장 짧은 프로세스부터 자원을 할당해주는 방식.
FCFS와 방법은 같지만, 실행시간이 작은 순서대로 우선순위 큐를 이용하는 방법.
장점
- 항상 실행 시간이 짧은 작업을 가장 먼저 실행하므로 평균 대기시간이 가장 짧음
단점
- 초기의 긴 작업이 짧은 작업들이 끝날 때까지 기다려야해서 startvation 현상이 일어남.
- 항상 짧은 작업이 항상 먼저 시작되어서 불공평.
- 실행시간 예측이 어려움.
HRN, Highest Response Ratio Next
SJF 방식에서 짧은 실행 시간을 가진 것들만 프로세서를 차지하는 것을 어느정도 보완하고지 만듦. 대기시간과 실행시간을 혼합하여 어느 작업에 CPU를 사용할지 결정하는 방법.
실행시간이 낮을수록, 대기시간이 길수록 우선순위가 높아짐.
장점
- 자원을 효율적으로 활용할 수 있음.
- starvation 상태가 발생하지 않음.
단점
- 잦은 context switching 으로 인한 overhead 발생 높음
Round Robin
프로세스가 프로세서에서 동작할 수 있는 시간을 할당해줌 (c.f. alarm clock)
라운드 로빈 큐는 원형 큐로 설계되어, 프로세스가 할당된 시간을 다 쓰면 OS가 인터럽트를 걸어 현재 PCB가 큐의 가장 뒤로 가는 방식.
장점
- 모든 프로세스가 공정하게 시간을 할당받기 때문에 starvation 현상 발생하지 않음
- 프로세스의 최악의 응답시간을 아는데 용이
단점
- 하드웨어 타이머가 필요하다
- 작업시간 할당을 너무 짧게하면 context switching이 자주 일어나 overhead 발생
SRT, Shortest Remaining Time
SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식. 최소 잔류시간 우선 스케줄링 이라고도 한다. 준비 큐에 남아있는 작업시간이 가장 적은 프로세스를 선택하고 타임 슬라이스를 부여하여 작업시간에 제한을 둔다
장점
- SJF 스케줄링과 평균 대기시간을 비교했을 때, SRT 스케줄링의 평균 대기시간이 더 짧다.
단점
- 현재 실행중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 context switching을 해야함. SJF 스케줄링에서는 없던 작업이 추가.
- 운영체제가 프로세서의 종료시간을 예측하기 어려움 starvation현상이 일어남
MLQ, Multi-level Queue (다단계 큐)
준비 상태 큐를 여러 종류별, 단계별로 분할해 자신만의 독자적 스케줄링 구현이 가능. 즉, 시스템 프로세스는 우선순위 큐로, 학생 프로세스는 round robin으로 등.
각 큐는 절대적 우선순위를 가지며, 우선순위 높은 큐가 모두 비어있기 전에는 낮은 우선순위 큐에 있는 프로세스를 실행할 수 없음.
장점
- 응답이 빠르다
단점
- 여러 준비 큐와 스케줄링 알고리즘 때문에 추가 overhead 발생
- 우선순위가 낮은 큐의 프로세스는 starvation 현상이 일어날 수 있음
MLFQ, Multi-level Feedback Queue (다단계 피드백 큐)
다단계 큐 스케줄링에서 계속해서 프로세서를 선점하지 못하는 프로세스에 대해 큐의 이동을 시켜주는 방식을 이용. 즉, 다단계 큐 방식에서 오래 대기한 프로세스가 높은 레벵릐 대기 큐로 이동, 혹은 프로세서 버스트 시간이 짧은 프로세스에 높은 우선순위를 주어 일시 종료시키거나 시간이 너무 오래걸리면 낮은 우선순위로 변경.
장점
- 매우 유연하여 스케줄러를 특정 시스템에 맞게 구현 가능
- 자동으로 입출력 중심, 프로세서 중심 프로세스를 구분
- 적응성이 높아 프로세스의 사전정보 없이도 최소작업 우선 스케줄링의 효과를 보여줌
단점
- 설계와 구현이 매우 복잡
