First come First Service(FCFS)
FCFS는 먼저 들어온 프로세스를 먼저 끝내고 다음 프로세스를 처리하는 비선점형 스케쥴링 알고리즘입니다.
은행에 들어와 번호표를 뽑는 순서대로 처리하는 방식이죠
밑에 두개의 처리가 있습니다. 서비스시간이 길고 짧은 프로세스가 어디에 위치함에 따라 AWT(Average Waiting Time)이 어떻게 변화하는지 살펴보겠습니다.
서비스시간이 짧은 프로세스들이 먼저 실행되게 되면 평균대기시간이 짧아지는 것을 확인할 수 있습니다.
이 처럼 FCFS의 단점으로는 Convoy Effect(호위효과)가 있는데요 프로세스가 호위하듯이 뒤를 이어 처리되는 것을 말합니다.
SJF
FCFS에서 서비스시간이 짧은 프로세스를 먼저 처리할 경우 평균 대기시간이 짧아진 것을 확인할 수 있었습니다. SJF는 이러한 장점을 가진 CPU 스케쥴링 알고리즘입니다.
위에는 FCFS로 처리하였고 아래는 SJF로 처리하였습니다.
FCFS는 10.25msec이고 SJF는 7msec의 평균대기시간이 걸리는 것을 볼 수 있습니다.
SJF는 가장 대기시간이 짧은 CPU 스케쥴링 알고리즘이나 모든 프로세스의 서비스시간을 알 수 없기에 비현실적이라는 단점이 있습니다.
SJF를 비선점형과 선점형 방식으로 처리해보겠습니다. 위가 비선점형 아래가 선점형입니다.
비선점형으로 처리했을 경우 평균대기시간이 더 짧아지는 모습을 볼 수 있습니다.
비선점형 SJF를 Shortest-Remaining-Time-First(최소잔여시간 우선) 알고리즘이라고 합니다.
Priority(우선순위)
우선순위 알고리즘은 정수의 우선순위를 정해 정수 값이 작은 프로세스가 가장 먼저 실행되는 알고리즘입니다.
우선순위 선정 기준은 내부적인 기준과 외부적인 기준으로 나눌 수 있습니다.
Internal
- time limit(CPU 사용시간이 짧은 순)
- memory requirement(메모리 적게 사용하는 순)
- i/o to CPU burst(i/o는 길게 CPU는 짧게 사용하는 순)
External
- amount of funds being paid(금액을 많이 지불한 순)
문제점으로는 Starvation(기아현상)이 발생할 수 있습니다. 계속해서 높은 우선순위를 가진 프로세스가 레디큐에 들어오게 된다면 낮은 우선순위를 가진 프로세스는 계속해서 CPU를 할당받지 못하게 됩니다. 이에 해결책으로는 레디큐에서 대기시간이 길어질 수 록 우선순위를 점차적으로 높여주는 againg 기법이 있습니다.
