CPU 스케줄링
burst
무언가를 사용하는 상태. 사용하기 때문에 불태운다고 표현
CPU burst
- 프로세스가 CPU 위에 올라가서 수행을 하는 상태
- CPU를 불태워서(burst) 사용하므로 CPU burst
I/O burst
- 프로세스가 I/O를 사용하는 상태
- I/O 장치를 불태워서(burst) 사용하므로 I/O burst
프로세스 flow
한 프로세스는 CPU burst와 I/O burst 상태를 수 없이 많이 전환
CPU Bound Process
- CPU burst time이 I/O burst time보다 상대적으로 긴 프로세스
- 딥러닝, 계산기 프로그램처럼 CPU의 연산 능력을 많이 요구하는 프로세스
I/O Bound Process
- I/O burst time이 CPU burst time보다 상대적으로 긴 프로세스
- 게임, 편집프로그램처럼 사용자와 interative한 활동을 많이 요구하는 프로세스 (일반적인 프로그램들)
I/O Bound Process의 중요성
- 대부분의 CPU Bound Process들은 백그라운드에서 실행
- 사용자들은 별로 신경쓰지 않아서 중요도가 낮고, I/O Bound Process가 더 중요
Dispatcher
Short Term Scheduler(CPU Scheduler) 과정의 내부에 포함되어 있음
Short Term Scheduler
ready queue에서 프로세스를 선택해서 CPU로 올리기 위해 PCB를 저장하고 CPU의 권한을 프로세스로 넘기는 이런 처리의 모든 과정
Dispatcher
ready queue의 프로세스를 CPU로 올리기 위해, 원래 CPU에 올라와있던 프로세스를 ready queue로 내리고, ready queue의 프로세스를 올리는 작업
Dispatch latency
이전 프로세스가 종료된 시점에서 디스패치가 완료되는 사이의 지연시간
Scheduling
Non Preemptive Scheduling(비선점형 스케줄링)
- 일단 하던 프로세스를 다 끝내고 스케줄러가 다음 실행할 프로세스를 실행
- 현실 인간사회에선 비선점형 스케줄링 방식을 많이 사용
공부를 하는데 일단 하던 것을 끝내놓고 다른 일을 해야 집중도도 높고 빠르게 가능 or 밥 먹는데 먼저온 사람이 먼저 받아야지! 새치기 금지!
Preemptive Scheduling(선점형 스케줄링)
- 프로세스가 실행중이었는데, 우선순위가 높은 프로세스가 들어오면 인터럽트 발생 후 바로 전환
- 이 방법이 현재로썬 제일 효율적이고 빨라서 대부분의 OS는 선점형 스케줄링 방식을 채택
Scheduling Criteria
- CPU Utilization: CPU가 가능한 바쁘게 놀지않고 계속 실행할 수 있는 정도
- Throughput: 정해진 시간안에 실행할 수 있는 프로세스의 수
- Turnaround Time: 특정 프로세스가 실행하다가 종료되는 사이의 시간
- Waiting Time: ready queue에서 프로세스가 선점되어 실행되기 전까지 기다리는 시간
- Response Time: 특정 프로세스의 요청이 들어오고나서 첫 번째 응답이 반응될 때까지의 시간
- CPU Bound Process: CPU Utilization, Throughput이 크고 나머지가 작음
- I/O Bound Process: Time관련된 것이 크고 나머지가 작음
- Trade Off관계: 서로 양립할 수 없는 관계이므로 그 중간 지점을 찾는 것이 중요
Scheduling Goals & Non-gaols
All systems
모든 시스템들이 가져야할 소양
- Fairness: CPU안에서 차지하는 프로세스를 고루 실행되게 끔 공정성 부여
- Balance: 어떠한 시스템이라도 놀지 않도록 CPU, I/O Burst Process를 균형있게 실행
Batch systems
과거의 성능이 좋지 않은 컴퓨터
- Throughput: 정해진 시간에 많은 일들을 처리
- CPU Utilization: CPU가 놀지 않고 바쁘게 돌아가야함
- Turnaround Time: 프로세스의 런타임이 짧아야 많은 명령들을 처리할 수 있음
Interactive systems
현대의 컴퓨터처럼 사용자와 interaction이 많은 시스템
- Response Time: 사용자가 입력하면 빠르게 반응해야 함
- Waiting Time: 대기시간 없이 최대한 빠르게 실행되어야 함
- Proportionality: 우선순위의 비율을 잘 정해서 사용자의 기대치를 만족해야함
ex) 롤 칼바람 큐창에서 모르는 챔프가 나와서 op.gg검색해야하는데 롤이 우선순위가 높아서 op.gg가 느리게 성능저하되며 실행되면 룬특성 빨리 못찍음
Real Time systems
- Meating Deadlines: 데드라인 지키기
- Predictability: 프로세스가 얼마나 걸릴지 예측
Non-goals
- Starvation: 스케줄러가 일을 하지 않아서 다른 프로세스들은 굶어죽고 동기화 문제도 발생
Scheduling Algorithms
FCFS(First Come First Served)
FIFO(선입선출): 먼저온 프로세스가 먼저 실행이 됨
- 실생활의 선착순 개념이라 이해하기 쉬움
- Non Preemptive: 중간에 실행되다가 context swtich되지 않고 할거 다 끝내고 전환
- No Starvation: 기다리다보면 끝나기에 언젠가는 내 차례가 온다
- Convoy Effect: 긴 프로세스가 먼저 온다면 뒤의 프로세스는 많이 기다려야함
- I/O, CPU Bound개념을 고려하지 않음 →
대기가 많은 프로세스기 때문에 Interactive하지 않음
SJF(Shortest Job First)
Burst Time이 짧은 프로세스를 먼저 실행
- optimal: 평균 대기시간을 최소화하는 방법 중 이보다 나은 방법이 없다
- Non Preemptive: 중간에 실행되다가 context swtich되지 않고 할거 다 끝내고 전환
- Yes Starvation: Burst Time이 제일 긴 프로세스가 먼저 들어왔는데 그 보다 짧은 프로세스들이 계속 들어오면 긴 프로세스는 평생 실행되지 않는다
- Burst Time을 정확히 예측하는 것은 불가능하다
SRTF(Shortest Remaining Time First)
남아 있는 수행시간이 짧은 프로세스를 우선으로 실행
SJF에서 Preemptive하게만 바꾼 방법
- Preemptive: 단위시간마다 프로세스가 얼마나 실행시간이 남아있는지 확인하고 context swtich
- SRTF도 SJF와 마찬가지로 정확한 burst time을 예측 불가능하기에 정확하지는 않다
Priority Scheduling
정수의 우선순위를 도입해서 프로세스를 구분
- Arrival Time이 낮은 프로세스를 높은 우선순위로? FCFS
- Remain Time이 낮은 프로세스를 높은 우선순위로? SRTF
- Burst Time이 낮은 프로세스를 높은 우선순위로? SJF
- Starvation: 우선순위가 높은 프로세스가 계속 들어오면 낮은 프로세스는 절대 실행되지 않음
- Aging: 일정시간마다 우선순위의 우선도를 증가시키는 방식
RR(Round Robin) Scheduling
Robin이라는 새는 새끼에게 먹이를 줄 때 조금씩 나눠서 돌아가며 주는 원리
Time Qunatum(q): 일정시간마다 프로세스가 계속 context swtich
q가 크면? context swtich가 거의 일어나지 않아서 FCFS와 같아짐
q가 작으면? context swtich를 자주해서 오버헤드↑ response time↓
보통 q는 10ms 와 100ms 사이, context swtich소요시간은 10us
- 엄지의 법칙: CPU burst time의 80%보다 짧게 q를 결정
- 같은 우선순위의 프로세스는 RR로 돌린다
Multilevel Queue Scheduling
ready queue의 분할: foreground, background 프로세스 두 분류로 나눔
- foreground: interative한 상호작용이 많고 response time이 중요한 프로세스(I/O Bound Process)
- background: batch처럼 계산하고 사용자는 신경안써도 되는 프로세스(CPU Bound Process)
- foreground는 RR: response time이 짧은 프로세스들이므로 공정하게 돌아가며 실행
- background는 FCFS: reponse time이 중요하지 않으므로 FCFS로 실행
- Time Slice: 80%는 foreground, 20%는 background 이런 실행 비율을 정함
Multilevel Feedback Queue Scheduling(MLFQ)
1. q를 초기에는 8의 값으로 낮게 부여
1-1. 만약 q가 적당하다면? Foreground Process 취급 후 RR
1-2. 만약 q가 8로도 부족하다면? 2단계
- q를 16으로 높혀서 실행
2-1. 만약 q가 적당하다면? 중간 우선순위로 등급하락
2-2. 만약 q가 16으로도 부족하다면? Background Process 취급 후 FCFS
- 실제로 UNIX에서도 사용하는 canonical(정식으로 인정받은) 알고리즘
- q를 조절함으로써 Foregound인지 Background인지 구분할 수 있어서, 이는 I/O Burst인지 CPU Burst인지 구분할 수 있다는 것과 같음
Multiple Processor Scheduling
코어가 여러개있는 시스템에서 사용하는 Scheduling 방식
- Push & Pull migration: 일이 없는 코어가 있으면 일이 많은 코어가 일을 주고(Push), 노는 코어는 일을 받음(Pull)
- Soft Affinity: 일을 하나씩 나누어서 코어에 분배, 일을 다해서 비어있는 코어에 다음의 일을 던져줌
- 장점: Hard Affinity보다 간단해서 스케줄러 오버헤드가 작음
- 단점: 어떤 태스크를 주어야할지 설계 난이도가 높고, 연관성 없는 일을 코어가 받으면 캐시 사용률이 낮아서 성능이 나쁨
- Hard Affinity: 연관되어 있는 일을 코어에게 분배
- 장점: 코어별로 연관되어 있는 일을 하기에 캐시 사용률이 높아 성능이 좋음
- 단점: 스케줄러가 일들의 연관성까지 판단해야해서 오버헤드가 큼
Real Time Scheduling
Burst Time, Peroid, Deadline을 반드시 지켜야함
-
Static Priority Scheduling(Rate-Monotonic)
무조건 period가 짧은 프로세스를 먼저 -
Dynamic Priority Scheduling(Earliest Deadline First)
Deadline이 임박하는 프로세스를 먼저 -
Embeded System에선 Static 방식
Dynamic은 Deadline과의 거리를 계속 판단하는 오버헤드가 커서 구조도 간단하고 자원을 덜 먹는 방식을 채택
다양한 운영체제의 스케줄링방식
- 리눅스: 0~99는 Real-Time(커널 프로세스) 100~139는 Normal(유저 프로세스)우선순위는 CFS 이진트리로 관리
- 윈도우: 우선순위가 큰게 먼저, 우선순위 테이블 존재
- 솔라리스: 리눅스보다 더 세세하게 구분하고 윈도우처럼 우선순위 큰게 먼저
Algorithm Evaluation
알고리즘은 설계하면 항상 검증을 해야함, 위에서 아래로 어렵고 현실적
Deterministic modeling
수학적인 분석으로 이상적이고 쉽다
Queueing modeling
마르코프 체인같은 변수들을 모두 추가해 좀 더 정확하게 분석
Simulation
스타벅스가 매장을 어디 입점시킬지 찾는 방식 (그 지역 유동인구, 나이대, 취향 등 분석)trace tape를 통해 실제 환경과 비슷한 테스크 케이스를 만듦
Emulation
실제 여러모든 변수들을 모두 고려해 스타벅스가 그 위치에 테스트매장을 운영 후 판단
Imlementation
그냥 실제로 구현한 후 테스트
