4.CPU스케줄링 교과명 : 운영체제 학 과 : 컴퓨터 소프트웨어 학 번 : 200812116 이 름 : 최 은 선 학 과 : 컴퓨터 소프트웨어 학 번 : 200812116 이 름 : 최 은 선 교수명 : 박승기 교수님 제출일 : 2009.10.13

CPU스케줄링의 정의와 결정시점 ☆결정시점 ☆CPU 스케줄링이란? 작업을 처리하기 위해 프로세스들에게 중앙처리 장치나 각종 처리기들 을 할당하기 위한 정책을 계획하는 것이다. ☆결정시점 - CPU 스케줄링의 결정 시점은 다음과 같은 프로세스의 상태 변화가 있을 때이다. 1. 수행 → 대기 2. 수행 → 준비 3. 대기 → 준비 4. 수행 → 종료

스케줄링의 목적 ☆ 모든 시스템  - 공정성 (Fairness) : 모든 프로세스들에게 공정히 CPU 시간 할당  - 효율성 (Balance) : CPU의 사용률 극대화   - CPU이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화 하는게 바람직한 스케줄링의 기준이 된다. ☆ Batch 시스템  - 높은 처리량 (High Throughput) : 시간당 처리되는 작업의 수 높임   - 짧은 반환시간 (Short turnaround time) : 작업이 시스템에 도착해서 완료 되는데 까지의 시간 최소화 ☆ 대화식 시스템  - 짧은 응답시간 (Short Response Time) : 대화식 작업에 빠르게 CPU 할당 ☆ 실시간 시스템  - 데드라인 만족 : 주어진 시간 안에 프로세스가 실행될 수 있게 함 ☆ 상호 모순성  - 스케쥴링의 목표는 상호모순 일 수 있음  - 예를 들어 짧은 응답 시간과, 데드라인 만족은 서로 공존할 수 없음.  - 따라서 어떤 스케쥴링 목표를 세울지는 시스템의 특성에 따라 결정  

선점형 스케줄링과 비선형점 스케줄링 ☆선점(preemptive) 스케쥴링 - 한 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 경우 - 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용 - 빠른 응답시간을 요구하는 시분할 시스템에 유용 - 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래 ☆비선점(nonpreemptive) 스케쥴링 - 한 프로세스가 CPU를 할당받으면 다른 프로세스는 CPU를 점유 못함 - 짧은 작업을 수행하는 프로세스가 긴 작업이 종료될 때까지 기다려야 함 - 모든 프로세스들에게 공정하고 응답시간의 예측이 가능

스케줄링의 종류 ☆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 - 작업들을 여러 종류의 그룹으로 나누어 여러개의 큐를 이용하는 기법

스케줄링의 종류 ☆ 다단계 피드백 큐(multilevel feedback queue) 스케줄링 - preemptive - 여러 개의 큐를 두고 시간이 지나면 우선순위가 떨어지는 큐로 밀려난다. 즉, 실행 시간이 긴 작업에게 벌칙을 주는 방식이다.  - 위의 큐는 CPU 차지 빈도 많고, 차지 시간은 짧다.  - 맨 아래 큐는 라운드 로빈 방식  - 맨 아래에서 너무 오래 머물면 aging 방식 사용 ‧ 장점 : - 적응(adaptive) 메커니즘 (각 큐의 CPU 할당 시간 정할 수 다) 가장 널리 사용되고, 일반적인 방법 ‧ 단점 : - 최상의 스케줄러를 정의하기 위한 요소를 찾기 어렵다.