📍 CPU 스케줄링(Short-term Scheduler)
✅ 스케줄링 대상은 Ready Queue 에 있는 프로세스들이다.
✅ 선점/비선점 스케줄링으로 나뉜다.
비선점 스케줄링(Non-preemptive Scheduling)
▪️ 어떤 프로세스가 실행 상태에 들어가면 그 프로세스가 끝나거나 CPU를 자진 반납하는 경우가 아니면 계속 실행되는 상태를 의미한다.
▪️ Context switch에 대한 오버헤드가 없다.
- 일괄 처리 시스템에 적합하며 응답 시간 예측이 쉬운 장점이 있다.
- 짧은 작업이 긴 작업을 기다리는 경우 전체 시스템의 처리 효율 떨어진다.
FCFS 스케줄링(First-Come First-Served)
▪️ FIFO 스케줄링이라고도 하며 준비큐에 먼저 도착한 순서에 따라 CPU를 할당하는 스케줄링 기법
▪️ 먼저 들어온 프로세스가 먼저 처리되어 공평성은 유지되나, 중요한 작업(burst time이 짧은 작업)이 중요하지 않은 작업(긴 작업)을 기다릴 가능성이 있다. (Convoy Effect 라고 함)
SJF 스케줄링(Shortest Job First)
▪️ 실행 시간이 가장 짧은 프로세스에 먼저 CPU를 할당하는 스케줄링 기법
▪️ 프로세스들의 평균 대기 시간(Average waiting time)이 가장 짧다.
▪️ 기아 상태(Starvation)가 발생할 수 있다. 기아는 에이징으로 해결한다.
📍 Starvation ? Aging ?
✅ Starvation : 계속해서 우선순위가 높은 프로세스(burst time 짧은)가 먼저 실행되어 먼저 도착했어도 우선순위가 낮은 프로세스(burst time 긴)가 계속해서 CPU를 할당받지 못하는 현상
✅ Aging : 시스템에서 특정 프로세스의 우선순위가 낮아서 무한정 기다리는 경우를 방지하기 위해 기다린 시간에 비례해 일정 시간이 지나면 우선순위를 한 단계씩 높여주는 방법으로, 무한 연기 or starvation을 예방하기 위한 기법이다.
SJF + Aging -> HRN 기법
HRN 스케줄링(Highest Response Ratio Next)
▪️ SJF의 문제점을 보완한 스케줄링이다.
▪️ 실행시간과 대기 시간을 둘 다 고려해 우선순위를 정하고, 각 프로세스의 우선순위에 따라 CPU를 할당한다.
▪️ 우선순위 = (waiting time + burst time) / burst time
우선순위 스케줄링
▪️ 각 프로세스마다 우선순위를 부여하고, 각 프로세스의 우선순위에 따라 CPU를 할당
▪️ 우선순위는 시간제한, 메모리 요구, 열린 파일의 수, 평균 실행 시간, 프로세스의 중요도, 자원 사용량을 복합적으로 고려하여 정한다.
▪️ Starvation 발생
📍 선점 스케줄링으로 구현하게 된다면 더 높은 우선순위의 프로세스가 도착했을 때 실행중인 프로세스를 멈추고 해당 프로세스가 CPU를 선점하게 된다.
선점 스케줄링(Preemptive Scheduling)
▪️ 어떤 프로세스가 사용 중인 CPU를 다른 프로세스가 강제로 빼앗을 수 있음
▪️ 시분할 시스템에 적합하며 응답 시간이 빠르다.
▪️ CPU를 선점할 프로세스에게 일정한 시간을 배정하기 위해 인터럽트용 타이머가 필요하다.
▪️ 비선점 스케줄링에 비해 context switch에 대한 오버헤드가 크다.
Round-Robin 스케줄링
▪️ 시분할 시스템을 위해 설계된 스케줄링으로, FCFS 스케줄링과 유사하며 선점이 가능하도록 시간 단위(Time Slice/Quantum) 개념이 추가되어 있다.
▪️ 준비 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만, 각 프로세스는 Time Slice만큼만 실행된 후 다시 준비 큐로 돌아간다.
▪️ Time Slice가 커지면 FCFS와 같아지고, Time Slice가 작아지면 Context Switch가 자주 발생하여 오버헤드가 커진다.
SRTF(Shortest Remaining Time First)
▪️ 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
▪️ 현재 수행중인 프로세스는 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺏긴다.
▪️ starvation 발생
▪️ 새로운 프로세스가 도달할 때마다 스케줄링을 다시 하기 때문에 CPU 사용시간 측정 불가
MLQ(multi level Queue)
▪️ 프로세스들을 특정 그룹으로 분리하여, 각 그룹마다 Queue를 이용하여 스케줄링 하는 기법
▪️ 전면작업(Foreground Task, 우선순위 높음)와 후면작업(Background Task, 우선순위 낮음)로 프로세스를 분리한다. 이외에도 프로세스의 특성 및 종류에 따라 여러개로 나눈다.
▪️ 전면작업은 Round-Robin과 같이 효율적으로 빠르게 실행될 수 있는 기법을 적용하고 후면작업은 FIFO 기법으로 진행된다.
▪️ 하지만 한번 특정 큐에 들어가면 다른 큐로의 이동이 불가능하기 때문에 스케줄링에 대한 오버헤드가 낮다는 장점이 있으나 유연성이 떨어진다는 단점이 있다.
MLFQ(multi level Queue)
▪️ 다단계 큐 스케줄링의 유연성을 제공하는 방식이다.
▪️ 프로세스는 우선순위가 다른 큐로 이동이 가능하다. (큐 사이의 프로세스 이동이 가능!)
▪️ IO Burst의 경우 우선순위가 높은 큐로 이동시키고, CPU Burst의 경우 낮은 우선순위 큐로 이동시키면서 프로세스 처리의 유연성을 높이는 것이다.
▪️ Aging 등의 방식을 적용해서 대기 시간이 긴 프로세스도 높은 우선순위 큐에 올려서 기아 상태를 방지하는 장점을 얻을 수 있다.
▪️ 하지만 큐의 수, 큐가 가지는 알고리즘, 우선순위 조절, 프로세스의 이동 등 관리의 복잡함이 증가된다.
