CPU Scheduling
운영체제의 중요한 기능 중 하나.
여러 프로세스나 쓰레드가 CPU를 최대한 공정하고 효율적으로 사용할 수 있도록 관리하는 방식
-> CPU 사용률을 최대화하고 프로세스 응답 시간을 최소화하며, 사용자와 시스템 요구 사항을 충족시키도록!
비선점형 스케줄링(Non-Preemptive)
: 일단 CPU를 할당 받은 프로세스가 완전히 종료되거나 I/O 요청 등으로 대기 상태가될 때까지 CPU를 계속 사용하는 방식
-> 프로세스가 CPU를 독점할 수 있어 context switch 오버헤드가 적지만 높은 우선 순위의 작업이 대기해야 하는 상황도 발생할 수 있다.
FCFS(First Come First Served)
- 먼저 도착한 프로세스를 가장 먼저 처리
- but, 짧은 작업이 긴 작업 뒤에 도착하면 오래 기다려야 함 =>
Convoy effect: CPU를 많이 필요로 하지 않는 프로세스들이 CPU를 오랫동안 사용하는 프로세스가 끝나기를 바라는 현상
SJF(Shortest Job First)
- 실행 시간이 가장 짧은 프로세스를 먼저 처리.
평균 대기 시간을 최소화할 수 있지만, 실행 시간을 미리 알아야 함.
그러나 작업 시간이 긴 프로세스가 실행 중일 때 작업 시간이 짧은 프로세스가 큐에 들어가도 기아 상태 / convoy effect가 발생 가능.
선점형 스케줄링(Preemptive)
: 현재 실행 중인 프로세스를 중단 시키고 다른 프로세스에게 CPU를 할당할 수 있는 스케줄링 방식.
-> 높은 우선 순위의 작업이 도착하면 즉시 CPU 할당 받아 빠른 처리가 필요한 작업에 유리하다.
Shortest Remaining Time First)
: SJF 스케줄링을 비선점 -> 선점 기능 추가.
현재 실행 중인 작업의 잔여 실행 시간과 새로운 작업의 잔여 실행 시간을 비교하여, 잔여 실행 시간이 가장 작은 작업 스케줄함.-> 여전히 단점 존재
우선 순위는 예상되는 next CPU burst time이 낮은 순서로 높음
: 1. starvation 2. CPU 사용시간을 미리 알 수 없다는 점
Round Robin:
각 프로세스가 동일한 크기의 할당 시간인 타임 퀀텀(Time Quantum)을 가지고 실행. 할당 시간이 지나면 프로세스는 선점되어 ready queue의 맨 뒤로 가서 다시 줄을 섬.
-> 응답시간이 빨라진다는 장점
각 프로세스는 할당 시간만큼 CPU 번갈아가면서 사용, 프로세스가 CPU를 기다리는 시간이 감소함.
Multilevel Queue Scheduling
규칙 1. Priority(A) > Priority(B) 이면, A가 실행된다. (B는 실행되지 않는다.)
규칙 2. Priority(A) = Priority(B)이면, A와 B는 RR 방식으로 실행된다.
- Ready Queue를 여러개로 분할 -> 다양한 종류의 프로세스를 효율적으로 관리하기 위한 전략
- foreground 큐: 주로 상호작용이 필요한 작업 -> 사용자가 직접 입력을 주고 결과를 기다리는 등의 interactive한 성격. 빠른 응답 시간이 중요
=> RR 스케줄링 방식. 모든 프로세스가 동일한 시간 동안 CPU를 사용할 수 있게. 응답 시간을 짧게 유지하도록 - background 큐: batch 작업 -> 사람의 상호 작용 없이 CPU를 오래 사용하는 작업 처리. 데이터 처리, 계산 작업
=> FCFS, 먼저 도착한 작업 먼저 처리하도록 - switch overhead 줄일 수 있게 스케줄링할 수 있다.
큐에 대한 스케줄링이 필요함
Fixed Priority Scheduling
foreground 큐 먼저 처리되고 나서 background 큐 처리. Foreground 큐의 작업이 응답성을 높이지만, background 큐의 작업 처리가 지연되어 starvation 발생 가능Time Slice
foreground 큐와 background 큐에 적절한 비율 할당 -> CPU 시간의 80%를 foreground, 20% background에 할당하는 방식
=> 쉽게 설명하면 카페에서 하루 대부분의 시간을 바로 만들어 줄 수 있는 간단한 음료, 나머지 시간에 복잡한 음료 처리하는 방식
Multilevel Feedback Queue Scheduler(MLFQS)
다단계 큐 스케줄링 + 동적인 프로세스 우선순위 변화
=> 프로세스가 다른 큐들 사이를 이동할 수 있게함. 실행 패턴에 따라 동적으로 우선순위 조정.
=> CPU를 많이 사용하는 프로세스(CPU-bound) - 하위 큐로 보냄, I/O 요청 등 대기 상태가 되는 프로세스(I/O-bound)는 상위 큐로 이동.
- 기아 상태 방지 : 낮은 우선 순위 큐에서 오래 대기하는 프로세스는 높은 우선순위 큐로 이동시키는 Aging 기법을 사용해서 기아 상태 예방
처음에 quantum = 8 시간 소모하면 그 다음 quantum = 16 -> 그 다음 FCFS
Busy Waiting(Spinlock)
프로세스/스레드가 특정 조건이 만족될 때까지 계속해서 조건 검사
-> CPU 시간을 사용하여 조건을 반복적으로 평가. 조건이 참이될 때까지 실행 계속
장점: 응답 시간이 매우 빠르다. 프로세스/스레드는 조건이 참이 되자마자 즉시 작업을 계속할 수 있다.
단점: CPU 자원 낭비 -> 조건이 참이 될 때까지 CPU는 유용한 작업을 수행하지 않고 단순히 조건을 평가하는데 시간 소비, 멀티 프로세스 환경에서는 효율성 떨어짐. 여러 프로세스가 동일한 조건에 대해서 busy waiting 수행하면 그만큼 CPU 자원 낭비 심해짐
semaphore mutex;
do {
P(mutex); // critical section 들어가는 경우 - 세마포어 값 감소
critical section
V(mutex); //세마포어 값 증가시킴, 자원 반납
remainder section
} while(1);busy waiting
=> P(mutex) 연산의 값이 양수인 경우에만 critical section 진입, 그렇지 않을 경우에는 계속 대기하게 됨. 계속 mutex 값을 확인.
프로세스가 mutex 값을 확인하고 양수가 아닌 경우에는 계속 반복문 수행하며 CPU 낭비
스핀 락은 프로세스가 락을 기다려야 함 -> context switch가 필요하지 않음.
다중 코어 컴퓨팅 시스템에서 스핀 락은 많이 사용됨
Block and Wakeup(sleeplock)
프로세스/스레드가 특정 조건이 만족되기를 기다리는 동안 실행을 중지(block)하고, 조건이 만족되면 운영체제가 해당 프로세스/스레드를 깨워(wakeup) 실행을 재개하도록 하는 방식
장점: 자원 사용이 효율적. 프로세스/스레드가 block 상태일 때는 CPU 시간을 소비하지 않으므로 달느 프로세스/스레드가 그 시간동안 실행될 수 있음
단점: 응답 시간이 busy waiting에 비해 느릴 수있음. 프로세스/스레드가 깨어나는데 시간이 걸릴 수 있음.
운영체제의 스케줄러가 관련 프로세스/스레드를 관리해야하므로 context switch과 같은 추가 오버헤드가 발생 가능.
일반적으로 조건이 곧 만족될 것 같으면 busy waiting, 그렇지 않으면 block and wake up
