CPU - 스케쥴링

CPU 스케쥴링

 

 

(개념) 어떤 프로세스에 CPU를 할당할지(Dispatch) 우선순위 결정 기법

- 스케줄링 알고리즘에 따라 시스템의 전반적인 응답 속도에 큰 영향

(목적) 

- 한정된 자원을 프로세스에게 잘 배분, 효과적 사용

- 이용률, 처리율, 반환 시간, 대기시간, 응답시간을 향상

 

1. CPU Scheduling : 프로세스 작업수행을 위해 언제, 어느 Process에 CPU를 할당할 것인지를 결정하는 작업

 

2. CPU Scheduling 운영 기준

  1) 처리능력 (Throughput) 최대화 : 주어진 시간에 최대한 많은 작업 처리(처리된 프로세스 수 / 시간)

  2) 반환(경과)시간 (Turnaround time) : 전체작업 수행시간을 최소화 (system in → system out 시간)  >> 종료시간 - 도착시간

  3) 대기시간 (waiting time) : ready queue에서 기다리는 시간 최소화 >> 반환시간 - 실행시간

  4) 응답시간 (Response time) : 대화식 시스템에서 첫 응답까지의 시간

  5) CPU 사용률 (Utilization) : 단위 시간당 CPU가 작업을 수행하는 총 시간 비율

  6) Fairness : 프로세스별 CPU 자원 할당의 공정성

  7) Deadline : 실시간 환경 등에서의 즉시처리 한계시간

 

3. Process 상태전이도와 스케줄러의 종류,역할

  1) CPU 상태 Ready State, Running State, Blocked State

  2) Scheduling Queue (보류상태) : 주기억장치 할당 기다림

  3) Job Scheduler (보류준비) : 주기억장치 할당, 프로세스 선택

  4) Process Scheduler (대기보류) : 프로세스 수에 따라 디스크로 보냄

  5) 단기 Scheduler (준비실행) : CPU할당

 

 

[ 스케쥴링 알고리즘의 목표 ]

 

±# 모든 시스템

® - 공정성 (Fairness) : 모든 프로세스들에게 공정히 CPU 시간 할당합니다.

® - 효율성 (Balance) : CPU의 사용률 극대화합니다.

 - CPU이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화 하는게 바람직한 스케줄링의 기준이 된다.

±# Batch 시스템

® - 높은 처리량 (High Throughput) : 시간당 처리되는 작업의 수 높일수 있습니다.

® - 짧은 반환시간 (Short turnaround time) : 작업이 시스템에 도착해서 완료 되는데 까지의 시간 최소화합니다.

±# 대화식 시스템

® - 짧은 응답시간 (Short Response Time) : 대화식 작업에 빠르게 CPU 할당합니다.

±# 실시간 시스템

® - 데드라인 만족 : 주어진 시간 안에 프로세스가 실행될 수 있게 합니다.

±# 상호 모순성

® - 스케쥴링의 목표는 상호모순 일 수 있습니다.

® - 예를 들어 짧은 응답 시간과, 데드라인 만족은 서로 공존할 수  없습니다.

® - 따라서 어떤 스케쥴링 목표를 세울지는 시스템의 특성에 따라 결정합니다.

(종류) 선점형 스케줄링, 비선점형 스케줄링

 

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 할당 시간 정할 수 있다)

          - 가장 널리 사용되고, 일반적인 방법입니다.

‧ 단점 : - 최상의 스케줄러를 정의하기 위한 요소를 찾기 어렵다..

 

선점형 스케줄링

다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있는 CPU 스케줄링

 

 

비선점형 스케줄링

어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장하는 CPU 스케줄링

 

 

[ CPU 스케줄러 ]

- CPU가 유휴  될때마다, 운영체제는 준비 완료 큐에 있는 프로세스들 중에서 하나를 선택해 실행해야 합니다.

- 선택 절차는 CPU 스케줄러 의해 수행되며, 스케줄러는 실행 준비가 되어 있는 메모리내의 프로세스들 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다.

- 준비완료 큐는 반드시 선입 선출 방식의 큐가 아니어도 되는것에 유의해야 합니다.

- 준비완료 큐는 선입선출큐 , 우선 순위큐, 트리 또는 단순히 순서가 없는 연결 리스트로 구현할 수 있다.

- 준비완료 큐에 있는 모든 프로세스들은 CPU에서 실행 될 기회를 기다리며 대기하고 있다.

- 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어블록(PCB)들이다.

- PCB : 모든 프로세스는 완료될 때까지 여러상태변환을 거치는데 스케줄러 안에 있는 트래픽 제어기가 프로세스의 상태를 파악하게 되는데 이를 위하여 프로세스에 관한 모든 정보를 가지고 있는 데이타베이스 PCB가 필요하게 된다.

 

 

# 디스패처 : CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈로서 이 기능은 다음을 포함합니다.

-문맥을 교환하는일

-사용자 모드로 전환하는 일

-프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

 

출처 : http://egloos.zum.com/heilow/v/583384