Operating System Concepts 5장 CPU Scheduling
5 CPU 스케줄링
생성 -> ready -> Run -> 종료
Preemption : Run상태에서 Time out으로 인해 주도권을 뺏기는것
5.1.3
run에서 wait 상태로 넘어 갔을 때는 시간을 다 못쓰고 넘어간거니까 그 프로세스한테 priority를 부여한다.
preemptive : 선점형 (시간이 다 끝나면 뺏는다.)
non Preemptive : 비선점형 (다 끝날 때까지 cpu를 뺏지 않는다.)
Run -> wait : 1
Run -> Ready : 2 (preemption)
Ready -> Run : (dispatch)
Wait -> Ready : 3
Run -> 종료 : 4 라고 할 때
1,4는 비선점형 2,3은 선점형
2는 time-out에 의해 3은 priority에 의해 선점
요즘 사용하는 모든 os들은 선점형을 쓴다.
store(save) : timeout 되고 난뒤의 상태를 저장
restore : resume 될때 전에 상태를 불러옴
scheduler : 다음에 어떤 프로세스가 올지 정함
dispatcher : CPU의 제어권을 다음 프로세스에 넘긴다.
A-> B로 바뀌는 과정을 context switching이라고 부른다
디스패쳐는 가능한한 빨라야 한다. => dispatch latency는 짧을 수록 좋다
5.2 Scheduling criteria (스케줄링 평가)
- Throughput : 단위시간당 처리량
cpu의 throughput은 MIPS (초당 처리할 수 있는 instruction)
- Turn - Around Time : Waiting time + Service time
- CPU Utilization : 일하는 효율성 ( 0 - 100퍼센트)
ex) 8시간 일하는데 유틸이 0.5면 4시간 일했다.
- Response time : 응답이 얼마나 빠르냐
은행을 예로 들면 throughput은 주인이 중요시하고
trun-around time은 고객이 중요시한다.
5.3.1 First-Come, First -Served Scheduling (FCFS)
- 먼저 온 애를 서비스해주고 떠난다.
- non - preemptive
5.3.2 Shortest -Job -First Scheduling (SJF)
- 짧은 일을 먼저 처리하는 스케줄링
- Mean(평균) waiting time이 최소화 된다.
- 전체적인 고객의 만족도를 높인다.
- a : 1, b: 5,c : 10모든 프로세스를 끝내는 시간은 abc로 하나 cba로 하나 똑같다.
Sortest Remaining Time First (SRTF)
- SJF의 preemption 버전 : 남아 있는 시간이 짧은 프로세스 먼저
5.3.3 Round - Robin방법
- 돌아가면서 한번씩 하자
- Time quantum을 할당해서 돌아가면서 cpu를 할당받는다.
- TIme quantum이 너무 짧으면 context -switching이 너무 자주일어난다.=> overhead
- TIme quantum이 너무 길면 다음 프로세스까지의 시간이 오래 걸린다.
Starvation - priority가 낮은 프로세스가 계속 뒤로 밀리는 현상
Aging - priority가 낮아 계속 밀린 프로세스의 priority를 올려주는 것
ex) 주택청약 - 계속 떨어지면 순위를 올려준다.
Real-time processes : 실시간으로 바로바로 처리한다.
Batch processes : 백업한다.?
5.3.6 Multilevel Feedback Queue Scheduling
FCFS + R.R. 을 사용
ㄴ> 8msec안에 끝나면 exit, 못끝나면 다음 큐로 넘어간다.
그리고 큐1원 큐1이 비어있어야 실행된다
5.4 Thread Scheduling
- 유저레벨 쓰레드와 커널레벨 쓰레드
- 유저레벨 쓰레드는 cpu를 갖기 위한 경쟁이 두단계로 이루어진다.
5.4.1 Conetention Scope
- 유저레벨은 두번
5.5 Muliti - Processor Scheduling
- 각 고객마다 service time이 다르기 때문에 b번은 어떤 줄은 길어지고 짧아지며 편차가 생긴다. load balacing에 문제가 생긴다.
- 하지만 컴퓨터는 cache memory를 사용하기 때문에 (b)번이 Hit ratio가 높기 때문에(b)번을 사용한다.
- 하지만 load unbalancing 문제는 여전히 남아있기 때문에 process를 다른쪽으로 넘기는 process migration을 한다.
성능분석 유인물
Req -> Design -> Product(소프트웨어 프로그램)
ㄴ> Functional, Performance, Reliability
- 성능척도
- Performance => (Throughput, Turn Around Time, Capacity 등등…)
- 성능분석의 목적
- 선정 평가(Selection evaluation) 고객이 필요한 정보
- 성능 예측(Performance projection) 개발자가 필요한 정보
- 성능 감시(Performance monitoring) 시스템 운영자가 필요한 정보 => 시스템이 잘 돌고 있는가
- 분석방법
- 관찰 : 주로 운영자가 한다.
- benchmark Test(수준점) : 여러 가지 작업을 대표하는 성능테스트 프로그램/방법
- Simulation Model : 모의시험, 모의로 시뮬레이션을 돌려본다.
- Queueing Model : 기본적으로 대기열, 큐에 대한 분석, 대기열이 얼마나 생기느냐를 봐서 utilization과 고객의 평균 대기시간을 알아낸다.
5.6 Real-Time CPU Scheduling
real - time은 기능에 시간적 제약이 추가된다.
ex) 드론, 로봇 명령을 입력하면 즉시 처리
얘또한 Dispatch latency가 짧아야 좋다.
Eearliest -Deadline -First Scheduling
- Deadline이 가장 빠른 거부터 처리한다.
p.238 Real time task는 우선순위가 가장 높다. (highest)
Real time task는 그래서 거의 항상 preemption이 일어난다.
long term - 작업자체를 받아들일 건지, ready로 가는 큐
short term - Ready에서 Run으로 가는 큐