CPU스케줄링
1) 정의
- 작업을 처리하기 위해 프로세스들에게 중앙처리 장치나 각종 처리기들 을 할당하기 위한 정책을 계획하는 것 입니다.
2) 방법별 분류
① 선점(preemptive) 스케쥴링
- 한 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세 스를 중지시키고 자신이 CPU를 차지할 수 있는 경우 입니다.
- 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용 합니다.
- 빠른 응답시간을 요구하는 시분할 시스템에 유용 합니다.
- 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래합니다.
② 비선점(nonpreemptive) 스케쥴링
- 한 프로세스가 CPU를 할당받으면 다른 프로세스는 CPU를 점유못합니다.
- 짧은 작업을 수행하는 프로세스가 긴 작업이 종료될 때까지 기다려야 합니다.
- 모든 프로세스들에게 공정하고 응답시간의 예측이 가능 합니다.
3) CPU 스케쥴링 알고리즘별 분류
① 우선순위(priority) 스케줄링
- nonpreemptive
- 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리 합니다.
‧ 단점 : 우선순위 낮은 프로세스는 기아 현상 발생 가능합니다.
☞ 해결책: aging - 시간이 지나면 우선순위 올라합니다.
ㄱ) 정적(static) 우선순위 방법
- 주변 환경 변화에 적응하지 못하여 실행중 우선순위를 바꾸지 않습니다.
- 구현이 쉽고 오버헤드가 적습니다.
ㄴ) 동적(dynamic) 우선순위 방법
- 상황 변화에 적응하여 우선순위를 변경, 구현이 복잡, 오버헤드 많습니다.
- 시스템의 응답속도를 증가시켜 효율적 입니다.
② 기한부(deadline) 스케줄링 - nonpreemptive
- 작업을 명시된 시간이나 기한내에 완료되도록 계획 합니다.
- 작업시간이나 상황등 정보를 미리 예측하기가 어렵습니다.
③ FIFO 스케줄링 - nonpreemptive
- 프로세스들은 대기 큐에 도착한 순서대로 CPU를 할당 받는다
- 일괄처리 시스템에서 주로 사용, 작업 완료 시간을 예측하기 용이 합니다.
‧ 장점 : 알고리즘이 간단하고, 공평합니다.
‧ 단점 : 성능(반환시간)이 좋지 않습니다. 큰 job이 앞에 있으면 짧은 job도 기다린다.
④ 라운드로빈(round robin) 스케줄링
- preemptive
- FCFS에 의해서 프로세스들이 보내집니다.
- 각 프로세스는 같은 크기의 CPU 시간을 할당 받습니다.
- 시분할 방식에 효과적, 할당시간의 크기가 매우 중요합니다.
- 할당시간이 크면 FCFS와 같게되고, 작으면 문맥교환이 자주 일어나게 됩니다.
‧ 장점 : 골고루 서비스 가능, 대화식 시스템에 적합합니다.
‧ 단점 : time slice가 적으면 문맥교환에 많은 시간 낭비합니다.
⑤ SJF(shortest job first) 스케줄링 - nonpreemptive
- 준비큐내의 작업중 수행시간이 가장 짧다고 판단되는 것을 먼저 수행 합니다.
- FCFS보다 평균 대기 시간을 감소, 큰 작업은 시간 예측이 어렵습니다.
- 짧은 작업에 유리합니다.
⑥ SRT(short remaining time) 스케줄링
- preemptive
- 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행합니다.
- 남은 처리 시간이 더 짧다고 판단는 프로세스가 준비큐에 생기면 언제라도 실행중인 프로세스가 선점됩니다.
- 긴 작업은 SJF보다 대기 시간이 길다
⑦ HRN(highest response ratio next) 스케줄링
- nonpreemptive
- 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법입니다.
- 짧은 작업이나 대기시간이 긴 작업은 우선순위가 높아집니다.
(대기시간 + 서비스를 받을 시간)
☞ 우선순위 = -------------------------------------
서비스를 받은 시간
⑧ 다단계 큐(multilevel queue) 스케줄링
- preemptive
- 작업들을 여러 종류의 그룹으로 나누어 여러개의 큐를 이용하는 기법입니다.
- 예를 들어 foreground 작업은 라운드 로빈 스케줄링 방식의 큐에, 일괄처리 작업은 FCFS 스케줄링 방식의 큐에 둔다.
- 라운드 로빈 스케줄링 방식의 큐에 많은 CPU 시간을 할당할 수 있습니다.
⑨ 다단계 피드백 큐(multilevel feedback queue) 스케줄링
- preemptive
- 여러 개의 큐를 두고 시간이 지나면 우선순위가 떨어지는 큐로 밀려난다. 즉, 실행 시간이 긴 작업에게 벌칙을 주는 방식입니다.
- 위의 큐는 CPU 차지 빈도 많고, 차지 시간은 짧다.
- 맨 아래 큐는 라운드 로빈 방식 입니다.
- 맨 아래에서 너무 오래 머물면 aging 방식을 사용합니다.
‧ 장점 : - 적응(adaptive) 메커니즘 (각 큐의 CPU 할당 시간 정할 수 있다)
- 가장 널리 사용되고, 일반적인 방법입니다.
‧ 단점 : - 최상의 스케줄러를 정의하기 위한 요소를 찾기 어렵다.
[ 스케쥴링 알고리즘의 목표 ]
±# 모든 시스템
® - 공정성 (Fairness) : 모든 프로세스들에게 공정히 CPU 시간 할당합니다.
® - 효율성 (Balance) : CPU의 사용률 극대화합니다.
- CPU이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화 하는게 바람직한 스케줄링의 기준이 된다.
±# Batch 시스템
® - 높은 처리량 (High Throughput) : 시간당 처리되는 작업의 수 높일수 있습니다.
® - 짧은 반환시간 (Short turnaround time) : 작업이 시스템에 도착해서 완료 되는데 까지의 시간 최소화합니다.
±# 대화식 시스템
® - 짧은 응답시간 (Short Response Time) : 대화식 작업에 빠르게 CPU 할당합니다.
±# 실시간 시스템
® - 데드라인 만족 : 주어진 시간 안에 프로세스가 실행될 수 있게 합니다.
±# 상호 모순성
® - 스케쥴링의 목표는 상호모순 일 수 있습니다.
® - 예를 들어 짧은 응답 시간과, 데드라인 만족은 서로 공존할 수 없습니다.
® - 따라서 어떤 스케쥴링 목표를 세울지는 시스템의 특성에 따라 결정합니다.
[ CPU 스케줄러 ]
- CPU가 유휴 될때마다, 운영체제는 준비 완료 큐에 있는 프로세스들 중에서 하나를 선택해 실행해야 합니다.
- 선택 절차는 CPU 스케줄러 의해 수행되며, 스케줄러는 실행 준비가 되어 있는 메모리내의 프로세스들 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다.
- 준비완료 큐는 반드시 선입 선출 방식의 큐가 아니어도 되는것에 유의해야 합니다.
- 준비완료 큐는 선입선출큐 , 우선 순위큐, 트리 또는 단순히 순서가 없는 연결 리스트로 구현할 수 있다.
- 준비완료 큐에 있는 모든 프로세스들은 CPU에서 실행 될 기회를 기다리며 대기하고 있다.
- 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어블록(PCB)들이다.
- PCB : 모든 프로세스는 완료될 때까지 여러상태변환을 거치는데 스케줄러 안에 있는 트래픽 제어기가 프로세스의 상태를 파악하게 되는데 이를 위하여 프로세스에 관한 모든 정보를 가지고 있는 데이타베이스 PCB가 필요하게 된다.
# 디스패처 : CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈로서 이 기능은 다음을 포함합니다.
-문맥을 교환하는일
-사용자 모드로 전환하는 일
-프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일
덧글