Scheduling
- CPU는 하나의 프로세스만 수행하기 때문에 CPU를 최대한 효율적으로 활용할 수 있도록 하는 프로세스
- 선점 스케줄링
- 프로세스의 수행 중 강제로 종료하고 새로운 프로세스를 수행시킬 수 있는 스케줄링 방식.
- 비선점 스케줄링
- IO를 제외하고 강제로 프로세스를 끝낼 수 없고 프로세스를 끝까지 실행시키는 스케줄링 방식
- 선점 스케줄링
프로세스 상태
- New : 프로세스 생성 중 (커널 공간에 PCB가 만들어진 상태)
- Ready : 프로세스가 CPU를 기다리는 상태 (CPU를 제외하고 필요한 자원을 모두 얻은 상태)
- Running : 프로세스가 CPU를 할당 받아 명령어를 수행중인 상태
- Blocked : 프로세스가 CPU를 할당 받아도 당장 실행할 수 없는 상태 (현재 프로세스가 I/O 작업 등을 처리 중인 상태를 의미)
- Terminated : 프로세스의 실행 종료 (프로세스 실행이 완료되고 할당된 CPU를 반납, Kernel 내의 PCB는 남아있음)
- Suspended : 프로세스의 중지 상태 (메모리를 강제로 뺏긴 상태로 특정한 이유로 프로세스 수행이 정지된 상태를 의미한다. 외부에서 다시 재개시키지 않는 이상 활성화될 수 없음.)
Scheduling 종류
① FIFO(First In First Out) 스케줄링
가장 간단한 스케줄링 기법으로, 먼저 대기 큐에 들어온 작업에게 CPU를 먼저 할당하는 비선점 스케줄링 방식
② Priority 스케줄링
각 작업마다 우선순위가 주어지며, 우선순위가 제일 높은 작업에 먼저 CPU가 할당되는 방법
우선 순위가 낮은 작업은 Indefinite Blocking 이나 Starvation에 빠질 수 있고, 이에 대한 해결책으로 체류 시간에 따라 우선 순위가 높아지는 Aging 기법을 사용할 수 있음
③ Deadline 스케줄링
작업이 주어진 제한 시간이나 Deadline 시간 안에 완료되도록 하는 기법
④ Round Robin
FIFO 스케줄링 기법을 Preemptive 기법으로 구현한 스케줄링 방법으로 프로세스는 FIFO 형태로 대기 큐에 적재되지만, 주어진 시간 할당량(Time Slice) 안에 작업을 마쳐야 하며, 할당량을 다 소비하고도 작업이 끝나지 않은 프로세스는 다시 대기 큐의 맨 뒤로 되돌아감(선점 스케줄링)
사용자에게 적합한 응답시간을 제공해주는 대화식 시분할 시스템에 적합하다.
⑤ SJF(Shortest Job First) 스케줄링
SJF는 비선점 스케줄링 기법으로, 처리하여야 할 작업시간이 가장 적은 프로세스에 CPU를 할당하는 기법
평균 대기 시간이 최소인 최적의 알고리즘이지만, 각 프로세스의 CPU 요구 시간을 미리 알기 어렵다는 단점이 있음
⑥ SRT(Shortest Remaining Time) 스케줄링
SJF 스케줄링 기법의 선점 구현 기법으로, 새로 도착한 프로세스를 비롯하여 대기 큐에 남아 있는 프로세스의 작업이 완료되기까지의 남아있는 실행 시간 추정치가 가장 적은 프로세스에 먼저 CPU를 할당하는 방법
⑦ HRN(High Response Ratio Next) 스케줄링
Brinch Hansen이 SJF 스케줄링 기법의 약점인 긴 작업과 짧은 작업의 지나친 불평등을 보완한 스케줄링 기법
(대기 시간 + 서비스 시간) / (서비스 시간)으로 우선순위를 결정한다.
서비스 시간이 분모에 있어 짧은 작업의 우선순위가 높아지고, 대기 시간을 분자에 둠으로써 긴 작업도 대기 시간이 큰 경우 우선순위가 높아지게 됨
⑧ Multilevel Feedback Queue 스케줄링
다양한 특성의 작업이 혼합된 경우 매우 유용한 스케줄링 방법으로, 새로운 프로세스는 그 특성에 따라 각각 대기 큐에 들어오게 되며, 그 실행 형태에 따라 다른 대기 큐로 이동함
예를 들어 연산 위주의 프로세스들은 처음에 RR 방식의 대기 큐에서 주어진 시간 할당량이 만료되면 다음 단계의 큐에 배치되고, 실행 시간이 길수록 점점 낮은 우선 순위를 지니게 되어 마지막 가장 낮은 우선 순위의 큐에 도달하면 작업이 끝날 대까지 RR 방식으로 스케줄링된다.
좋은 스케줄링의 판단기준
-
CPU 이용률
모든 CPU 스케줄링 알고리즘의 목적은 CPU를 최대한 바쁘게 유지하는 것 -
처리량
CPU에서 수행한 작업의 척도. 시간당 실행되고 완료되는 프로세스의 수 -
반환시간
프로세스 요청시간에서 완료시간 까지의 경과시간 -
대기시간
프로세스가 레디큐에 들어가기 위해 대기한 시간 -
응답시간
프로세스의 요청에서 첫번째 응답이 생성될 때 까지 걸리는 시간
