FCFS(First Come First Service)
선착순
선점 방식(한번 자원을 할당받으면 빼앗기지 않음)이며,
도착시간(Ready Queue 기준)으로 먼저 도착한 프로세스를 먼저 처리한다.
프로세스 변경에 의한 Context Switch Overhead가 낮고, 프로세스가 계속 일할 수 있어
자원을 효율적으로 사용 가능하지만
하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 Convoy Effect 현상과
긴 평균 응답시간이 단점으로 꼽힌다.
2초면 끝날 프로세스가 3분 걸리는 프로세스로 인해 오래 기다려야 하는 현상이 생기는 것
일괄처리 시스템에 적합하며, 대화형 시스템(Interactive System)에 부적합하다.
도착시간: Arrival Time(AT)
처리시간: Burst Time(BT)
대기시간: Wating Time(WT) = TT-BT
반환시간: Turnaround Time(TT) = BT+WT
정규화된 반환시간: Normalized TT(NTT) = BT/TT
NTT가 1일 경우 가장 이상적인 상황이고, 늘어날 수록 비 효율적인데, NTT가 커지는 상황을 Conyoy Effect라 한다.
RR(Round Robin)
돌아가면서 쓰자
FCFS와 같이 먼저 도착한 프로세스부터 먼저 처리하지만 자원사용 제한시간Time Quantum이 존재한다.
이 Time Quantum은 시스템에서 설정할 수 있는 parameter이며,
프로세스는 할당한 시간이 지나면 자원을 반납한다. Timer-Runout
특정 프로세스의 자원 독점Monopoly를 방지하지만 Context Switch Overhead가 크다.
대화형 시스템, 시분할 시스템에 적합하다
Time Quantum이 시스템 성능을 결정하는 핵심 요소이다.
이 Time Quantum이 무한대라면 FCFS와 같으며,
0에 수렴한다면 사용자는 모든 프로세스가 각각의 프로세서 위에서, 동시에 실행되는 것처럼 느끼게 된다.
체감 프로세서 속도는 실제 프로세스 성능의 1/(프로세스의 수)
Time Quantum이 낮아질수록 Context Switch Overhead가 커진다.
만약 P1의 자원 사용시간이 끝나면, ReadyQueue의 맨 뒤에 줄을 서게 된다.
FCFS에 비해 NTT가 균등한 것을 볼 수 있다.
만약 Time Quetum이 3초로 늘어난다면 평균 응답시간(TT)가 10.80에서 9.80으로 줄어든 것을 볼 수 있다
Time Quentum을 늘린다고 무조건 평균 응답시간이 빨라지는것은 아니지만,
TimeQuntum의 길이에 따라 시스템 성능이 바뀐다는것을 기억하자
SPN(Shortest Process Next)
빨리 할 수 있는거부터 하자
FCFS와 RR와는 달리, 먼저 오는 프로세스 순으로 실행하지 않는다
실행시간 기준이며, Burst Time이 가장 작은 프로세스를 먼저 처리한다.SJF(Shortest Jop First)
평균 대기시간WT와 시스템 내 프로세스 수가 최소화되며,
스케줄링 부하가 감소되고 메모리도 절약되어 시스템 효율이 향상된다.
하지만 Burst Time이 긴 프로세스는 자원을 할당받지 못해
무한대기 현상Starvation이 발생할 수 있으며(Aging 등으로 해결)
프로세스의 정확한 실행 시간을 알 수 없어 실행시간 예측 기법이 필요하다.
도착한 프로세스들의 실행 시간을 비교하여 가장 빨리 끝나는 프로세스부터 먼저 처리한다.
가장 긴 프로세스인 P2는 1에 도착했지만, 실행시간이 길어 13에 시작, 20에 끝나게 된다.
이것이 무한 대기현상Starvation 현상이다
SRTN(Shortest Remaining Time Next)
Remaining Time = 남은시간
남은 시간이 짧은 거부터 하자
SPN의 변형이며, 잔여 실행시간이 더 적은 프로세스가 Ready상태가 되면(등장하면) 선점된다.
즉 뺏길 수 있다.
SPN의 장점인 평균 대기시간이 짧다는 점을 극대화 할 수 있지만,
SPN과 마찬가지로 프로세스의 총 실행시간 예측이 필요하며
잔여실행을 계속 추적해야 함으로 OverHead가 증가한다
위와 같은 문제 때문에 구현 및 사용이 비현실적이다.
HRRN(High Response Ratio Next)
오래 기다리신 분에게 추가 기회 제공
SPN의 변형이며, 무한 대기현상 발생을 해결하기 위해 기존 SPN에 Aging concepts를 더한 기법이다.
Aging concepts는 프로세스의 대기시간WT을 고려하여 기회를 제공한다.
응답률Response ratio이 높은 프로세스를 우선한다.
얼마나 오래 기다렸는가를 나타내는 수식은 다음과 같다.
SPN의 장점에 무한대기현상Starvation을 방지하는 기법이며,
SPN과 마찬가지로 실행시간 예측 기법이 필요해 Overhead가 증가한다.
MLQ(Multi Level Queue)
줄을 우선순위에 맞게 따로따로 서주세요
SPN의 단점인 실행시간 예측이 부하가 크고 힘들다는 점을 해결하기 위해,
실행시간 예측 없이 SPN과 비슷한 효과를 내보자고 만들어진 알고리즘이다.
작업or우선순위 별 별도의 Ready Queue를 가지며, 프로세스들은 최초 배정된 Queue를 벗어나지 못한다.
각각의 Queue는 자신만의 스케줄린 기법을 사용하며,
Queue사이에는 우선순위 기반의 스케줄링을 사용한다.
우선순위가 높은 중요한 일은 빠른 응답시간을 볼 수 있으나, 덜 중요한 일은 그만큼 느리다.
여러개의 Queue를 관리해야 하니 스케줄링 Overhead가 증가하고,
우선순위가 낮은 Queue는 무한대기현상Starvation이 발생할 수 있다.
MFQ(Multi Level Feedback Queue)
다른 줄로 이동가능
최초 배정된 Queue를 벗어날 수 없는 MLQ와 다르게, 프로세스 간의 Queue이동이 허용된다.
Feedback을 통해 우선순위를 보정하며, 이는 현재까지의 프로세서 사용정보(패턴)을 활용한다.
프로세스에 대한 사전정보 없이 SPN, SRTN, HRRM기법의 효과를 볼 수 있다.
하지만 설계 및 구현이 복잡하며 여전히 스케쥴링 overhead와 무한대기현상 문제가 존재한다.
변형
1. 각 준비 큐마다 시간 할당량Time Quantum을 다르게 배정
-프로세스의 특성에 맞는 형태로 시스템 운영 가능
2. 입출력 위주 프로세스들을 상위 단계의 큐로 이동시켜 우선순위를 높여준다.
-입출력 위주 프로세스I/O Bounded는 CPU를 비교적 적은 시간동안 사용하므로 빨리빨리 처리 가능하다.
-프로세스가 block될 때 상위의 준비 큐로 진입시킨다.
-시스템 전체의 평균 응답시간을 줄이며, 입출력 작업을 분산시킬 수 있다.
3. 대기시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
-Aging기법
우선순위가 동적이며 자원을 빼앗길 수 있는 선점 스케쥴링이다.
