CPU 스케줄러란?
CPU를 누구에게 줄것인지 결정하는 것
운영체제가 관리하는것이다.
nonpreemptive(비선점형) :프로세스가 자진반납. 강제로 탈취x
preemptive(선점형) : 프로세스를 강제로 탈취
CPU스케쥴링이 필요한 이유
cpu의 스케줄링은, 여러종류의 프로그램이 섞여있기에 필요하다.
- cpu만 오랫동안써야하는 경우(수학적 계산)
- 입출력장치와 빠르게 스왑하는 경우(게임)
입출력장치는 CPU를 짧게 많이쓰고, 계산쪽은 CPU를 길고 적게쓴다.
CPU 스케줄링의 종류
성능 척도
스케줄링의 성능 척도를 판단하는 건 아래의 5가지 성능을 기반으로 함.
- CPU utilization : 전체 시간중 CPU가 놀지 않고 일 한 비율
- Throughput : 시간당 몇개의 일을 처리했는가
위의 두가지는 하드웨어 관점. 아래 3가지는 프로세스의 관점이다.
- Trunaround time : 프로세스가 CPU를 사용에 걸린 시간
- Waiting time : CPU를 쓰기 위해 ready Queue에서 기다린 시간.
- Response time : ready Queue에서 CPu를 쓰기위해 기다린 시간.(시분할 시스템에서 최초로 CPU만나기까지 기다린 시간임)
대기시간과 응답시간의 차이 : 선점형을 생각해보면, 대기시간은 여러번 발생하고, 응답시간은 한 번만 발생한다.
스케줄링을 중국집으로 비유하면 이렇다!
- CPU utilization : 요리사가 일 한 시간
- Throughput : 고객에게 얼마나 요리가 나갔는지
- Trunaround time : 고객이밥먹고 다 나갈때까지의 소요시간
- Waiting time : 손님이 기다린 시간들
- Response time: 첫번째 음식이 나오기까지 소요시간
FCFS(First-Come-First-Served)
자료구조인 Queue와 똑같다(FIFO).
먼저 오면, 먼저 CPU를 할당해준다.
아래처럼 P1의 소요시간이 길다면, CPU 대기시간이 굉장히 길어진다.
P1의 소요시간이 끔찍하게 길다면...말 할것도 없다!
이런 상황을 Convoy Effect라고 한다.
SJF (Shortest-Job-First)
FCFS방법이 잘못됐다면, 소요시간이 짧은대로 주면 되지 않을까?
그게 바로 SJF알고리즘이다.
이녀석은 확실히 최소한의 평균 대기시간을 보장한다.
SJF는 선점형과 비선점형으로 나뉜다.
선점형은 현재 프로세스 남은 소요시간보다 더 짧은 소요시간의 뉴 프로세스가 도착하면, CPU를 빼았아 더 짧은 친구에게 준다. 이 방법을 Shortest-Remaining-Time-First(SRTF)라고 부른다.
하지만 이 친구에게도 문제점이 두가지 있다.
SJF방식의 단점 두가지
-
Starvation(기아 상태)
CPU사용시간이 짧은 프로세스를 선호하기에, 사용시간이 긴 프로세스는 영영 CPU를 사용하지 못할 수도있다.(짧은 프로세스가 계속해서 옴)
이를 Starvation(기아 상태)라고 한다. 프로세스가 CPU를 받지못해 굶어 죽는것이다 -
사용시간(남은 시간)을 알 수없다.
정확히 말하자면, 추정은 가능하다. 확실히 알기 불가능 하다.
Priority Scheduling (우선순위 스케줄)
priority Queue와똑같다. 우선순위가 높은 프로세스 먼저 할당한다.
그렇기에 SJF도 우선순위 스케줄의 일종이다(CPU 소모시간이 적을수록 우선순위▲)
이녀석도 잘못하면 낮은 우선순위 프로세스가 startvation에 걸릴 수 있다.
이를 해결하기위해 Aging기법이 도입됐다.
낮은 우선순위의 프로세스라도, 시간이 지날때마다 우선순위를 올려주는것이다.
Round Robin(RR) 스케줄
현대 운영체제는 99% Round Robin스케줄기반이다.
이는 곧 시분할 시스템이다. 할당시간을 부여해서, 시간이 지나면 CPU를 프로세스에게서 빼았는다.
아주 특이한 경우 RR도 단점이 생긴다. 소요시간이 길고 같은 프로세스가 여러개인 경우, 계속 나눠서 처리하기에 average time이 오래걸린다. 하지만 보통 프로세스들의 소요시간은 제각각임.
또한, 소요시간이 짧은 프로세스가 여러개라면 Context Switching이 빈번히 일어나 오버헤드가 커진다.
- 오버헤드 : 어떤 일을 처리하기위해 간접적으로 소요되는 시간
MultiLevelQueue(MLQ)
멀티레벨 큐. 큐를 여러개 만들어서, 각 큐마다 스케줄링 기법을 다르게 적용한다.
예를들어 2개로 나눈다.
- foreground(사용자와 상호작용)
- background(사용자와 상호작용x)
1번은 사용자와 상호작용 하기에 RR스케줄링을 적용하고, 2번은 중요한 것들이기에 FCFS를 적용한다.
하지만 이는 큐에 적용된 스케줄이 일괄적이기에, 실시간으로 큐의 위치를 옮길수 없다.
이를 보완한것이 아래에 소개할 방법이다
MultiLevelFeedbackQueue(MLFQ)
RealTimeScheduling
무조건 시간 안에 끝내야하는것이 전제로 된다.
- 미사일 발사
- 인공위성 조작
- 네이비게이션
- 기타...
위와 같은 프로세스들은 오차가 생기면 큰일나는 작업들이다. 따라서 실시간 스케쥴링을 해준다!
Thread Scheduling
쓰레드도 스케쥴링을 한다!
프로세스 내부에서 하던가, 커널 단기스케줄러가 일반 프로세스처럼 스케줄링 하던가 두가지다
부록. CPU가 여러개인 경우의 스케줄링
한개인것 보다 더욱 복잡해진다.
OS에서 깊게 다루진 않기에 맛만보고 넘어갔다.
