CPU(스케줄링) Flashcards
CPU 스케줄링
[정의] 멀티프로세스 환경에서 CPU 활용을 극대화하기 위한 CPU-프로세스 할당 정책 결정 기법
[분류]
- 선점 스케줄링 : RR, SRT, MLQ, MLFQ, RM, EDF
- 비선점 스케줄링 : 우선순위, 기한부, FCFS, SJF, HRN
[정책결정기준] (처반대응공CD)
1. 처리능력 (Throughput-시간당 처리) 최대화
2. 반환시간 (종료-도착, in-out) 최소화
3. 대기시간 (반환-서비스, queued)
4. 응답시간 (Response time) : 대화식 시스템의 첫 응답까지 시간
5. 공정성 : 프로세스별 CPU 자원 할당 공정성
6. CPU 사용률(Utilization) : 단위 시간 내 CPU 작업시간/단위시간
7. Deadline : 처리 한계시간
* 사용 효율, 처리율은 최대화 하고 반환/대기/응답 시간은 최소화 하는 알고리즘 선택
선점 CPU 스케줄링
[정의] 진행중인 작업에 인터럽트를 걸고 다른 작업에 CPU 할당하는 스케줄링 전략
* 비교적빠른 응답, 대화식 시분할 시스템 적합, 높은 프로세스 진입시 오버헤드 초래
[알고리즘]
1. RR : 시분할(규정시간 할당), 대화형 시스템, 할당된 시간내, 미완료된 작업은 FCFS 큐
2. SRT : 남은 서비스 시간 짧은 순, SJF보다 오버헤드
3. MLQ : 작업 유형별 우선 순위, 여러 큐(각각의 알고리즘)
4. MLFQ : FIFO 형태의 우선 순위 큐, 마지막 큐 RR (Aging 고려)
비선점 CPU 스케줄링
[정의] 프로세스가 CPU 할당 받으면 반환시까지 다른 프로세스 점유 불가한 CPU스케줄링 방법
* 응답시간 예상용이, 모든 프로세스 요구 공정 처리, 짧은 작업수행 프로세스가 긴작업프로세스 인해 작업종료시까지 대기
[알고리즘] (우기에 풋(F)살(S)한다(H))
1. 우선 순위(Priority) : 우선 순위 부여, 낮은 순위의 기아 현상 -> Aging
2. 기한부 : 명시 시간, 기한 내 완료 목표 계획/사전 요구자원 제시 필요, 예측 어려움
2. FCFS : 도착 순서, 호위효과(Convoy effect)
3. SJF : 수행 시간이 짧은 순, 기아 현상, 무한 대기
4. HRN : 우선순위=(대기한시간+서비스 시간)/ 서비스 시간, SJF 단점 극복
실시간(선점형) CPU 스케줄링
[정의] RTOS환경, 우선순위/선점/Latency 최소화, Deadline 보장 기법
1. RM : 주기가 짧을수록 높은 순위, Sort RTOS에 적합
2. EDF : 마감시간이 짧을수록 높은 순위, Hard RTOS에 적합
RR
[정의] 프로세스간 우선순위 없이 순서대로 정해진 할당 시간동안 CPU를 할당하는 선점형 스케줄링 기법
[특징] 공평한 할당, 기아상태/무한봉쇄 미발생, 할당 시간의 크기가 동작에 큰 영향
[동작]
1. 할당 시간 지정
2. FCFS 방식으로 프로세스를 대기큐에 저장
3. 순차 처리, 할당된 CPU 시간내에 처리 못한 프로세스는 대기큐의 가장 뒤로 이동
4. CPU는 대기큐의 다음 프로세스를수행
[적용] 시분할 방식 시스템
* 할당 시간을 짧게 하면 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점 있어 실시간 시스템에 유리
SRT
[정의] CPU자원의 효율성 극대화를 위해 계속해서 서비스 시간이 적은 작업을 파악하여 우선적으로 CPU를 할당하여 처리하는 선점형 스케줄링 기법
[특징]
- (장점) 시분할 시스템에 활용 시 유용, SJF에 비해 평균 대기시간이나 반환시간에서 효율적
- (단점) 오버헤드 증가
- 우선 순위 = 남은 서비스 시간 최소(매 Clock 체크)
- SJF 기법에 선점방식을 도입한 변형된 방법
* 실행시간이 짧은 프로세스가 자주 도착할 경우 잦은 선점으로 인한 문맥교환의 부담
MLQ
[정의] 프로세스를 특정 그룹으로 분류하고 그 그룹에 따라 각기 다른 준비상태 큐를 사용하는 선점형 스케줄링 기법
[특징]
- 그룹 별 다른 스케줄링 기법 사용
- 다른 그룹 큐로 이동할 수 없음
- Starvation 문제 발생 -> MLFQ로 해결
MLFQ
[정의] 각 그룹별 준비상태 큐마다 시간할당량을 부여하고 그 시간동안 완료하지 못한 프로세스는 다음단계의 준비상태 큐로 이동하는 기법
[특징]
- MLQ의 변형. Starvation 문제 보완
- 상위단계 큐일수록 우선순위가 높고 시간 할당량이 작음
- 마지막 큐에선 라운드로빈 사용
- 선점, 피드백 : 미처리 작업 하위 Queue로 이동
- 규정 시간량(Quantum) : 우선순위가 낮은 큐로 이동할 때마다 프로세스가 부여 받는 규정 시간량이 증가
RM
[정의] 주기가 짧을수록 높은 우선 순위를 부여하는 정적 방식의 선점형 스케쥴링 기법
[특징]
- (정책) 정적 우선 순위
- (CPU) n(n루트2 -1), 1개 100%, 2개 83%, …. n개 69%
- (목적) CPU를 더 자주 필요하는 프로세스에게 우선 순위
- 오버헤드 낮음
- Soft RTOS(실시간 운영체제)에 적합
[사례]
EDF
[정의] 임의의 실행 시점에서 가장 가까운 마감시간을 갖는 프로세스에게 높은 우선순위를 할당하는 동적 방식의 스케줄링 기법
[특징]
- (정책) 동적 우선 순위
- (CPU) 이론적으로 100%
- (목적) 마감 시간에 따라 우선 순위 동적 부여
- 오버헤드 높음
- Hard RTOS(실시간 운영체제)에 적합
우선순위
[정의] 각 프로세스에 우선순위가 주어지고 우선순위에 따라 CPU 할당
[동작]
- 동일한 우선순위 간은 FCFS 처리
- 우선순위 결정 : 관리자에 의한 결정, 자원요구량에 의한 결정, CPU처리 시간에 의한 결
정, 시스템에서 보낸 시간에 의한 결정
- 높은 우선순위가 지속될 경우 기아현상
기한부 스케줄링
[정의] 작업들이 명시된 시간이나 기한 내에 완료되도록 계획하고, 사용자는 사전에 작업이 요구하는 정확한 자원을 제시
[특징] 작업시간이나 상황 등 정보를 미리 예측하기가 어려움
FCFS
[정의] 프로세스가 대기큐(준비큐)에 도착한 순서에 따라 CPU 할당
[특징]
- 가장 간단한 스케줄링 알고리즘으로 FIFO(First Input First Out)알고리즘 이라고 함
- Convoy Effect 발생 가능 (Burst time이 긴 프로세스가 CPU 독점)
- 단독적 사용이 거의 없으며, 다른 스케줄링 알고리즘에 보조적으로 사용 (우선순위 스케줄링, RR 스케줄링 등)
SJF
[정의] CPU 점유 시간이 가장 짧은 프로세스에 먼저 할당하는 비선점 CPU 스케쥴링 알고리즘
[특징]
- (장점) 평균 대시 시간에 최적
- (단점) 무한 연기, 기아 현상 발생
- 우선 순위 = 서비스 시간 최소
- 평균대기 시간이 최소가 되는 최적 알고리즘
- 긴 작업과 짧은 작업간의 불평등 심하여, CPU 요구시간이 긴 프로세스는 Starvation 발생 → HRN 사용
HRN
[리드] 기아상태 방지
[정의] 대기시간이 긴 프로세스, 또는 실행시간이 짧은 프로세스의 우선순위를 높여 프로세스 간 자원 점유 불평등을 보완하는 비선점 스케줄링 기법
[특징]
- (장점) 시분할 시스템에 활용 시 유용, SJF의 무한 연기, 기아 현상 방지, Aging
- (단점) 오버헤드 증가, 긴급한 프로세스 우선 순위 밀림
- 우선순위 = (대기시간+서비스시간)/서비스시간
