CPU Scheduling
Concept
커널 레벨의 스레드는 OS에 의해 스케줄링됨
앞에 내용은 process scheduling임
프로세스 실행은 CPU 실행과 I/O 대기의 주기로 구성됨
CPU burst동안은 CPU 사용가능
I/O burst동안은 CPU 사용 불가능
CPU Scheduler
CPU 스케줄러는 ready queue에 있는 프로세스들 중 하나를 택해 코어를 할당해줌
밑에 있는 상황들 중 하나일때 스케줄링을 함
1. running -> waiting
2. running -> ready
3. waiting -> ready
4. terminate
1과 4는 무조건 새 프로세스를 선택함
2와 3은 새거 아님 기존거 둘다 가능
Preemptive & Nonpreemptive Scheduling
Nonpreemptive scheduling
CPU burst동안은 기존 프로세스를 안 내쫓음
1아님 4의 상황
Preemptive scheduling
CPU burst동안에도 기존 프로세스를 쫓아낼 수 있음
1,2,3,4 상황 모두 가능함
보통 priority에 의해 발생함
대부분의 OS가 쓰는 방식
Scheduling Criteria
높으면 좋은거
CPU Utilization
CPU 사용률, CPU를 많이 쓸수록 좋음
Throughput
시간당 처리한 프로세스의 개수
낮으면 좋은거
Turnaround Time
특정 프로세스를 실행시킨 시간 (finish time - arrival time)
Waiting Time
프로세스가 ready queue에서 기다린 시간
Response Time
요청이 제출된 후 첫 번째 응답이 생성될 때까지 걸리는 시간
waiting time은 ready queue에 기다린 총 시간이지만, resposne time은 ready queue에 처음왔을 때 기다린 시간임
Scheduling Algorithms
First-Come First-Served (FCFS) Scheduling
간단한 큐 형태로 들어온 순서대로 나가게하는 FIFO구조 (nonpreemptive)
평균적인 waiting time이 길어져서 좋은 구조는 아님
밑에 처럼 큰 애가 앞에 들어오면 waiting time이 진짜 길어짐
Shortest-Job-First (SJF) Scheduling
짧은 애를 먼저 스케줄링하는 구조 (nonpreemptive)
평균 waiting time에서는 optimal하긴 함
다음 CPU burst시간 예측이 어려워 실제로 optimal하지는 않음
Determining Next CPU Burst Length
exponential averaging로 다음 CPU burst 길이를 추정해보자
알파가 0이면 n에 대한 estimation값으로 예측한거
알파가 1이면 n에 대한 실제값으로 예측한거
보통 알파를 1/2로 놓음
얼추 비슷하게 나옴
Shortest Remaining Time First (SRTF) Scheduling
가장 짧게 남은 애를 시행하는 구조
SJF의 preemptive 버전
1) 새로운 process가 도착하거나 2) 기존 프로세스가 종료되면
그 때 스케줄링을 함
Round Robin (RR) Scheduling
process마다 동일한 시간(q)을 번갈아가면서 사용하고 지정된 시간이 지나면 끝냄
기다리는 시간이 공평하고 response time에서 장점을 가짐
근데, SJF에 비해 평균적으로 높은 turnaround time을 가짐
q는 context switch하는 시간보다 커야함
q가 너무 커지면 FCFS로 퇴화함
q가 너무 작아지면 context switch overhead가 증가함
Priority Scheduling
우선 순위가 높은 애를 먼저 스케줄링하는 구조
preemptive랑 nonpreemptive 둘다 가능
우선순위가 낮은애는 시행이 안되는 starvation 문제가 생길 수 있는데 시간이 지날수록 우선 순위가 높아지는 aging을 통해 해결 가능함
우선순위가 같은애들은 Round Robin을 통해 같이 시행할 수도 있음
Multilevel Queue
ready queue는 여러개의 큐들로 구성됨
Multilevel queue scheduler는 큐의 개수, 각 큐마다의 스케줄링 알고리즘, 어떤 큐에 프로세스를 넣을지 등을 정함
이렇게 큐마다 우선순위를 가짐
Multilevel Feedback Queue
프로세스는 큐들 사이로 막 이동할 수 있음
Multilevel Feedback Queue는 큐의 개수, 큐마다의 스케줄링 알고리즘, 프로세스를 언제 업그레이드-강등할지, 어느 큐에 들어가게 할지를 정함
아까 말한 Aging 기법은 Multilevel Feedback Queue로 구현함
이렇게 각 큐마다 다른 알고리즘을 적용할 수 있음
Multiple-Processor Scheduling
CPU 스케줄링이 복잡해지면서 여러 CPU가 운용이 가능하게 됨
Symmetric multiprocessing (SMP)은 각 프로세서가 각자 스케줄링하는거
Load Balancing
SMP는 CPU에 대한 부하 분산을 고르게 유지해야함
Push migration 각 프로세서의 부하를 주기적으로 확인하고, 발견되면 과부하된 CPU에서 다른 CPU로 푸시 작업을 수행함
Pull migration 한가한 프로세서가 대기 중인 작업을 바쁜 프로세서로부터 가져옴
Processor Affinity
스레드가 특정 프로세서에서 실행 중일 때 프로세서의 캐시는 스레드의 메모리 액세스를 저장함
이거를 Processor Affinity(프로세스 친밀도)라고 부름
스레드가 다른 프로세서로 이동할 수 있으므로 로드 밸런싱은 프로세서 친밀도에 영향을 줄 수도 있음
Soft affinity 운영 체제는 동일한 프로세서에서 스레드를 계속 실행하려고 하는데 보장하지는 않음
Hard affinity 프로세스가 실행할 수 있는 프로세서 세트를 지정함
Multicore Processors
요즘 트랜드는 물리적 칩에다가 여러 프로세스 코어를 놓는거임
하나의 스레드가 compute할 때 다른 스레드가 memory stall 작업을 할 수 있어 memory stall에서 이점을 가져갈 수 있음
OS context switching도 안해서 개꿀임
Multithreaded Multicore System
Chip-multithreading(CMT)는 각 코어에 여러개의 하드웨어 스레드를 놓음
OS가 논리적 CPU에서 돌릴 software thread를 정하면 그게 물리적 코어까지 이어짐
Real-Time CPU Scheduling
Soft real-time systems 중요한 실시간 작업이 최우선 순위를 차지하지만 완료에 대한 보장은 없음
Hard real-time systems 작업이 마감일까지 무조건 완료되어야 함
데드라인을 넘으면 가치가 하락하는 모습
real-time system은 preemptive, priority scheduling을 지원함
hard는 데드라인을 만족하는 기능 또한 제공
Periodic Task Scheduling
주기적으로 task를 실행함
주기는 p, 데드라인은 d, 작업 속도는 1/p
Rate Monotonic Scheduling
우선순위가 주기와 반비례하도록 설정함(static priority)
주기가 짧으면 우선순위 높게, 길면 우선순위 낮게
밑에처럼 다음 P2가 들어올때까지 직전 P2가 안끝나면 deadline miss가 발생할 수도 있음
Earliest Deadline First Scheduling (EDF)
우선순위가 deadline이 가까울수록 높게 결정됨(dynamic priority)
deadline이 가까우면 높게, 늦으면 낮게
t=100일때 보면 preemption방식으로 P1을 시행하는 것을 볼 수 있음
