스케쥴링의 목적
단일 처리 시스템에서 실행중인 프로세스 'A'가 존재하는데 다른 프로세스의 요청이 들어온다면, 그 프로세스('B')는 이전의 프로세스가 끝날때? 자원을 놓을때까지 대기해야한다.
하지만
다중 프로그래밍에서는 여러 프로세스들이 동시에 돌아가며, 자원 요청시 운영체제는
그 자원을 적절히 분배하여 프로세스를 할당한다.
장점
1. CPU의 활용 극대화
2. 프로세스 처리율을 늘릴수 있다.
+@ 스케쥴링 성능 기준
알고리즘에 대한 성능평가 기준 5가지
⬜ 프로세서 이용률(CPU Utilization)
◽ 시간당 CPU를 사용한 시간의 비율
◽ 프로세서를 실행상태로 항상 유지하여 유휴상태가 되지 않도록 한다. 가능하면 입출력(I/O) 중심의 작업보다 프로세서 중심의 작업을 실행해야한다.
⬜ 처리율(Throughput)
◽ 시간당 처리한 작업의 비율
◽ 단위 시간당 완료되는 작업 수가 많도록 짧은 작업을 우선 처리하거나 인터럽트 없이 작업을 실행한다.
⬜ 반환시간 또는 소요시간(Turnaround Time)
◽ CPU burst time(쓰고 나갈때까지의 시간, 누적되지 않음)
◽ 작업이 시스템에 맡겨져서 메인 메모리에 들어가기까지의 시간, 준비 큐에 있는 시간, 실행시간, 입출력시간 등 작업 제출 후 완료되는 순간까지의 소요시간이 최소화되도록 일괄 처리 작업을 우선 처리한다.
⬜ 대기시간(Waiting Time)
◽ 대기열에 들어와 CPU를 할당받기까지 기다린 시간
◽ 작업의 실행시간이나 입출력시간에는 실제적인 영향을 미치지 못하므로 준비 큐애서 기다리는 시간이 최소화되도록 사용자 수를 제한한다.
⬜ 반응시간 또는 응답시간(Response Time)
◽ 대기열에서 처음으로 CPU를 얻을때까지 걸린시간
◽ 반응시간은 의뢰한 시간에서부터 반응이 시작되는 시간까지의 간격으로 대화형 시스템에서 중요한 사항이다. 따라서 대화식 작업을 우선 처리하고 일괄 처리 작업은 대화식 작업의 요구가 없을때까지 처리한다.
선점형 VS 비선점형
Ready Queue에 있는 프로세스를 대상으로 다음에 어떤 작업을 CPU에 할당할 것인지를 정하는 알고리즘.
선점(preemptive) : 우선순위가 높은 작업이 오거나, 해당 작업이 더 우선되어야 한다고 판단되면 해당 작업에게서 CPU를 빼앗을 수 있다.
비선점(non-preemptive) : 일단 CPU를 할당받으면 해당 프로세스가 끝날때까지 CPU를 빼앗기지 않는다.
스케쥴링 알고리즘
FCFS(First Come First Served)
특징
선입선출 비선점형 스케줄링 비효율적
단점
응답시간이 길어질 수 있음
Convey Effect(호위 효과)
👉🏻 Short process behind long process, 하나의 프로세서 중심 프로세스가 프로세스를 떠나기를 기다리는 현상
SJF(Shortest Job First)
특징
CPU burst time이 짧은 작업을 우선으로 할당하는 방법
각 프로세스와 다음번 CPU burst time을 가지고 스케줄링에 할당
👉🏻 일종의 우선순위 기법 priority = predicted next CPU burst time
비선점형(SJF)과 선점형(SRTF) 방식이 있음
최소 평균 대기 시간을 보장한다.
단점
Starvation(기아 현상) 발생 가능성이 있음
SRTF 또는 SRF(Shortest Remaining Time First)
특징
SJF의 선점형 스케줄링 방식
남은 프로세스의 burst time보다 더 짧은 process가 도착하면 CPU를 빼앗음
프로세스가 새로 들어올때마다 갱신됨
단점
Starvation
새로운 프로세스가 들어올때마다 스케줄링이 변경되므로 CPU 사용 시간(burst time)을 정확히 예측하기 어렵다.
Priority Scheduling
특징
highest priority를 가진 프로세스에게 CPU를 할당
👉🏻 highest priority = smallest inteager
선점형 방식에서는 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스보다 높으면 CPU를 선점한다.
비선점형 방식에서는 더 높은 우선순위의 프로세스가 들어오면 Ready queue의 head 부분에 넣는다.
단점
Starvation
무한 정지(infinite blocking) : 프로세스가 CPU를 사용할 준비가 되었지만 우선순위가 낮을 경우 무한 대기하는 상태가 되는 것
👉🏻 [해결법] Aging 기법으로 큐에 남아있었던 시간으로 가중치를 부여해, 해당 문제점을 해결할 수 있다.
RR(Round Robin)
특징
현대식 기법으로 시분할 시스템을 위해 설계되었다.
선점형 스케줄링 기법
각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가지고, 할당 시간이 지나면 프로세스는 선점 당하고 Ready queue의 맨 뒤로 가게 된다.
n개의 프로세스가 Ready queue에 있고 할당시간이 q time unit이라면 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
👉🏻 어떠한 프로세스도 q time unit 이상 기다리지 않는다. 공정한 알고리즘이다.
CPU 사용시간이 랜덤할때 더욱 효율적이다.
문맥교환을 통해 프로세스의 Context를 저장할 수 있기 때문에 가능한 기법이다.
평균 대기 시간(Average Waiting Time)은 조금 길어질 수 있으나, 응답시간(Response)이 짧아진다.
단점
q time unit이 커지면 FCFS와 같아져 비효율적일 수 있다.
q time unit이 지나치게 작으면, 문맥교환이 대량으로 발생해 오버헤드가 증가한다.
HRN (Highest Response ratio Next)
정의
짧은 작업에 유리한 SJF의 단점을 개선한 기법이다.
실행시간 추정과 선점 기능 때문에 스케줄러가 복잡해지고 남은 계산 시간들을 저장해 놓아야 하는 단점을 보완한다.
각 작업의 우선순위로 서비스해주는 스케쥴링
◽ 에이징: 오랫동안 대기하는 프로세스의 우선순위를 증가시키는 방법.
◽ 기아상태를 해결할수 있다.
👉🏻 (대기시간 + 서비스시간)/서비스시간
MLQ 다단계 큐 스케줄링 (MultiLevel Queue Scheduling)
◽ 우선순위마다 준비 큐 형성
◽ 항상 가장 높은 우선순위 큐의 프로세스에 CPU를 할당 (우선순위가 낮은 큐에서 작업 실행 중이더라도 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗는 선점형 스케줄링)
◽ 각 큐는 라운드 로빈이나 FCFS등 독자적 스케줄링 사용 가능
◽ 대화형, 배치(Background)등의 프로세스 성격에 따라 우선순위 부여
◽ 큐들 간의 프로세스 이동이 불가하기 때문에 스케줄링 부담이 적지만 유연성이 떨어짐
◽ 우선순위가 낮은 프로세스가 오랬동안 CPU 할당을 기다리는 기아 현상이 발생할 수도 있음
MLFQ 다단계 피드백 큐 스케줄링 (MultiLevel Feedback Queue Scheduling)
◽ 다 단계 큐 + 동적인 프로세스 우선 순위 변화 적용
◽ 프로세스 생성 시 가장 높은 우선 순위 준비 큐에 등록되며 등록된 프로세스는 FCFS 순서로 CPU를 할당받아 실행된다. 해당 큐의 CPU 시간 할당량(Time Quantum)이 끝나면 한 단계 아래의 준비 큐에 들어간다.
◽ 단계가 내려갈수록 시간 할당량(Time Quantum)이 증가한다.
◽ 큐 사이의 프로세스 이동 가능하며 CPU Burst는 낮은 우선순위의 큐, I/O Burst는 높은 우선순위의 큐에 배치한다.
◽ 가장 하위 큐는 FCFS 스케줄링
◽ 맨 아래 큐에서 너무 오래 대기하면 다시 상위 큐로 이동 (에이징 기법을 통한 기아상태 예방)
MLQ VS MLFQ의 차이점 ❓
MLQ 스케쥴링의 경우 큐와 큐 사이에 프로세스들이 이동을 할 수 없는 반면,
MFQ 스케쥴링의 경우 큐 사이에 프로세스들이 이동을 할 수 있다.
따라서 MFQ 스케쥴링에비해 MLQ 스케쥴링은 부담이 적지만, 유연성이 떨어진다.
또한 MLQ 스케쥴링은 하위 단계의 큐에 있을수록 CPU할당을 받지 못하여 기아현상이 발생할수도 있지만 MFQ 스케쥴링의 경우는 에이징 기법을 통해 기아 현상을 예방할 수 있다.
