CPU Scheduling

개념
Process 작업수행을 위해 언제, 어느 Process에 CPU를 할당할 것인지를 결정하는 작업 Multi-Processor 환경하에서 Processor 간의 우선순위를 저장함으로써 CPU 활용을 극대화하기 위한 방법

I. CPU의 효율적인 사용, CPU(프로세스) 스케줄링의 개요
    가. CPU Scheduling 의 정의

  • Process 작업수행을 위해 언제, 어느 Process에 CPU를 할당할 것인지를 결정하는 작업
  • Multi-Processor 환경하에서 Processor 간의 우선순위를 저장함으로써 CPU 활용을 극대화하기 위한 방법

 

    나. CPU Scheduling의 기준

  • 바람직한 동작을 보이는 프로세스에게 더 좋은 서비스 제공
  • I/O Bound와 CPU Bound 프로세스의 적절한 혼용
  • Process의 작업형태, 우선순위, Burst시간, 잔여실행시간을 복합적으로 고려

 

    다. CPU Scheduling의 요건(Scheduling Criteria)

요건

설명

처리능력 (Throughput) 최대화

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

반환(경과)시간 (Turnaround time)

최소화

 전체작업 수행시간을 최소화 (system in à system out 시간)

대기시간 (waiting time) 최소화

 ready queue에서 기다리는 시간 최소화

응답시간 (Response time) 최소화

 대화식 시스템에서 첫 응답까지의 시간 최소화

CPU 이용률(Utilization) 극대화

 CPU를 정해진 시간 내 100% 가동

II. Process 상태전이도와 Scheduler의 종류 및 역할
    가. 프로세스 상태 전이도
   


    나. Scheduler의 종류 및 역할

종류

역할

Scheduling Queue

• 주 기억 장치의 할당을 기다림 (보류상태, 디스크에 위치)

장기(Job) Scheduler

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

중기(Process) Scheduler

• 프로세스 수에 따라 디스크로 보냄 (대기보류)

단기 Scheduler

• 실행 준비된 프로세스에 CPU 할당 (준비실행)

 

 

III. CPU scheduling 기법과 알고리즘
    가. Scheduling 기법

구분

선점(Preemptive) 스케줄링

비선점(Non-preemptive) 스케줄링

개념

- 한 프로세스가 CPU 를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 점유 가능

- 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용

- 한 프로세스가 CPU를 할당 받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유불가

장점

- 비교적 빠른 응답

- 대화식 시분할 시스템에 적합

- 응답시간 예상이 용이

- 모든 프로세스에 대한 요구를 공정하게 처리

단점

- 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래

- 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기

 

 

    나. CPU scheduling 알고리즘
1) 선점 스케줄링 알고리즘

알고리즘

처리방식

RR

- Round Robin

- 대화식 사용자를 위한 시분할 시스템(Time Sharing System)을 위해 고안

- 준비뷰(FCFS)에 의해 보내진 각 프로세스는 같은 크기의 CPU 시간을 할당 받음

- 프로세스가 할당된 시간 내에 처리 완료 못하면 준비큐 리스트의 가장 뒤로 보내지고 CPU는 대기중인 다음 프로세스로 넘어감

- 할당 시간이 가장 중요하며, 일반적으로 시간 할당량은 100 밀리 초에서 1,2초 사이 값

- 할당시간이 크면 FCFS 와 같게 되고, 작으면 문맥 교환이 자주 발생

 

SRT

- Short Remaining Time

- 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행

- 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점됨

- 긴 작업은 SJF 보다 대기 시간이 길다

다단계 큐

- Multi-level Queue

- 작업들을 여러 종류의 그룹의 분할

- 여러 개의 큐를 이용 상위단계 작업에 의해 하위단계 작업이 선점 당함

- 준비 상태 큐를 여러 종류로 분할(작업 분류별 묶음) 하지만 다른 큐로 작업 이동 불가

- 각 큐는 자신만의 독자적인 스케줄링을 가짐

 

다단계 피드백 큐

- Multi-level Feedback Queue

- 입출력 위주와 CPU 위주인 프로세스의 특성에 따라 큐마다 서로 다른 CPU Time Slice (Quantum)를 부여

- 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동 (맨 마지막 단계에서는 Round Robin 처리)

- 하위단계일수록 할당시간은 증가 (공평성 부여)

 
2) 다단계 큐와 다단계 피드백 큐의 비교

구분

다단계 큐

다단계 피드백 큐

대기 큐

Time Quantum

동일

다름

우선순위

작업별

순서별

큐간 이동

없음

있음

공통점

무한대기방지, 선점 스케줄링

 

 

※ SRT(Shortest Remaining Time First)
- 신규프로세스가 들어오는 시점에 각 프로세스의 남은 시간을 체크
 


1) 대기시간
     - P1 = 1 + 2 = 3, P2 = 0, P3 = 8, P4 = 0, P5 = 3
     - 평균 대기시간 = (3 + 8 + 3) / 5 = 2.4
2) 반환시간(turnaround time)
     - P1 = 8-0 = 8, P2 = 2-1 = 1, P3 = 16-2 = 14, P4 = 5-3 = 2, P5 = 11-4 = 7
     - 평균 반환 시간 = (8 + 1 + 14 + 2 + 7) / 5 = 6.4

3) 비선점 스케줄링 알고리즘

알고리즘

처리방식

우선순위 스케줄링

- 각 프로세스에 우선순위가 주어지고 우선순위에 따라 CPU 할당

- 동일한 우선순위간은 FCFS 처리

- 우선순위 결정 : 관리자에 의한 결정, 자원요구량에 의한 결정, CPU처리 시간에 의한 결정, 시스템에서 보낸 시간에 의한 결정 등 사용

- 우선순위가 높은 작업이 계속적으로 들어오게 될 우선순위가 낮은 프로세스는 Starvation 발생 à Aging 기법으로 해결가능

기한부

스케줄링

- 작업들이 명시된 시간이나 기한내에 완료되도록 계획

- 사용자는 사전에 작업이 요구하는 정확한 자원을 제시

- 작업시간이나 상황 등 정보를 미리 예측하기가 어려움

FCFS

- First Come First Service

- 프로세스가 대기큐(준비큐)에 도착한 순서에 따라 CPU 할당

- 가장 간단한 스케줄링 알고리즘으로 FIFO(First Input First Out)알고리즘 이라고 함

- Convoy Effect 발생 가능 (Burst time이 긴 프로세스가 CPU 독점)

- 단독적 사용이 거의 없으며, 다른 스케줄링 알고리즘에 보조적으로 사용 (우선순위 스케줄링, RR 스케줄링 등)

SJF

- Shortest Job First

- 준비 큐 내의 작업중 수행시간이 가장 짧다고 판단되는 것을 먼저 수행

- 각 프로세스에서 CPU 버스트 길이를 비교하여 CPU 가 이용 가능해지면 가장 작은 CPU 버스트를 가진 프로세스를 할당

- 주어진 프로세스 집합에 대해서 평균대기 시간이 최소가 되는 최적 알고리즘

- CPU 요구시간이 긴 작업과 짧은 작업간의 불평등 심하여, CPU 요구시간이 긴 프로세스는 Starvation 발생 à HRN 사용

HRN

- Highest Response Ratio Next

- Response Ratio = [대기시간+서비스 시간) /서비스 시간

- 대기중인 프로세스 중 현재 Response Ratio 가 가장 높은 것을 선택

- 대기중인 프로세스 중 현재 Response Ratio 가 가장 높은 것을 선택

- SJF의 약점을 보완한 기법으로 긴 작업과 짧은 작업간의 불평등을 완화

※ SJF(Shortest Job First)
    - 실행 시간이 가장 짧은 작업 순으로 CPU수행
 
1) 대기 시간
     - P1 = 0, P2 = 4, P3 = 9, P4 = 3, P5 = 4
     - 평균 대기 시간 = (4+9+3+4) / 5 = 4
2) 반환 시간(turnaround time)
     - P1 = 5-0 = 5, P2 = 6-1 = 5, P3 = 16-2 = 14, P4 = 8-3 = 5, P5 = 11-4 = 7
     - 평균 반환 시간 = (5+5+14+5+7) / 5 = 7.2

 

※ HRN(Highest Response Ratio Next)
    - 우선순위 = (대기시간 + 서비스 받을 시간) / 서비스 받을 시간
 
    - 5초일 때에 HRN에 따른 우선순위 계산
           P2 = (4 + 1) / 1 = 5, P3 = (3 + 5) / 5 = 1.6, P4 = (2 + 2) / 2 = 2, P5 = (1 + 3) / 3 = 1.3
          따라서, 우선순위가 가장 높은 P2가 CPU를 선점함.
    - 6초일 때에 HRN에 따른 우선순위 계산
          P3 = (4 + 5) / 5 = 1.8, P4 = (3 + 2) / 2 = 2.5, P5 = (2 + 3) / 3 = 1.6
          따라서, 우선순위가 가장 높은 P4가 CPU를 선점함.
    - 8초일 때에 HRN에 따른 우선순위 계산
          P3 = (6 + 5) / 5 = 2.2, P5 = (3 + 3) / 3 = 2
         따라서, 우선순위가 가장 높은 P3가 CPU를 선점함
      1) 대기 시간
            - P1 = 0, P2 = 4, P3 = 6, P4 = 3, P5 = 9
            - 평균 대기 시간 = (4+6+3+9) / 5 = 4.4
      2) 반환 시간(turnaround time)
            - P1 = 5-0 = 5, P2 = 6-1 = 5, P3 = 13-2 = 11, P4 = 8-3 = 5, P5 = 16-4 = 12
            - 평균 반환 시간(turnaround time) = (5+5+11+5+12) / 5 = 7.6

 

IV. CPU scheduling 선택 고려사항 및 기술동향
    가. CPU scheduling 선택 고려사항

  • I/O Bound, CPU Bound
  • 프로세스의 작업 형태[일괄처리형/대화형,실시간형]
  • 프로세스의 우선순위
  • 프로세스의 페이지 뷰재율
  • 프로세스의 자원 선점율 고려
  • 프로세스의 버스트 시간 고려
  • 프로세스의 잔여 실행시간 고려

    나. CPU scheduling 기술동향

  • Multi-thread 기반의 Scheduling Algorithm이 요구됨
  • 실시간 시스템의 경우 정해진 시간 내에 완료되는 것이 보장될 때에만 CPU를 할당하는 Scheduling 기법의 적용
  • 멀티미디어, 가상현실 시스템과 같은 복잡한 응용에 적합한 Scheduling Algorithm 연구가 활발히 추진되어야 함
  • NVC (Network Virtual Computing) 환경에서 CPU Scheduling 방안의 연구가 진행중임
  • 작업유형 측면 : 컴퓨터 작업 유형 즉, 대화형/일괄처리형이냐에 따른 적절한 CPU 스케줄링 선택을 통한 컴퓨팅 자원의 극대화 필요함
  • 실시간 시스템 측면 : embedded 시스템, RTOS 등 실시간 기반의 시스템 활용의 다양화로 빠른 응답을 처리할 수 있는 별도의 CPU 스케줄링 개발 필요

<기출 풀이>
다음표와 같이 작업이 제출되었을 때 SJF(Shortest Job First)정책으로 스케줄링 할 때의 평균 Turnaround 시간을 구하시오.

작업

제출시간

실행시간

X

0

4

Y

1

6

Z

2

3

 
① 가장 먼저 제출된 X작업 실행
② 1시간경과후, Y작업이 제출 되었으나, X작업은 1시간동안 수행되어 3시간 실행시간, Y작업은 6시간 수행시간을 갖으므로, X작업 수행 지속 (또한 SJF는 비선점이므로 X작업에 의해 할당된 CPU가 선점 될 수 없음)
③ 총 2시간경과후, Z작업이 제출 되고, X작업은 2시간 수행되어 2시간 실행시간, Z작업은 3시간 수행시간이므로, X작업 수행 지속 (또한 SJF는 비선점이므로 X작업에 의해 할당된 CPU가 선점 될 수 없음)
④ 총 4시간경과후, X작업이 완료되고, Y와 Z작업중 실행시간이 작은 Z작업이 먼저 수행됨
⑤ 총 7시간경과후, Z작업이 완료되고, Y작업이 실행됨
⑥ 총 13시간경과후, Y작업까지 완료되고 모든 작업 완료
Turnaround 시간 : 대기시간 + 실행시간
    대기시간 = 앞 프로세스 실행시간 – 도착시간
        X 작업 : 4시간
        Z 작업 : (4-2) + 3 시간 = 5시간
        Y 작업 : (7-1) + 6 시간 = 12시간
평균 : 4 + 5 + 12 = 21시간 /3 = 7시간
HRN(Highest Response-ratio Next)방식으로 스케줄링 할 경우, 입력된 작업이 다음과 같을 때 우선순위가 가장 높은 작업을 선정하는 절차를 나타내시오.

작업

대기시간

서비스 시간

A

5

5

B

10

6

C

15

7

D

20

8

    - HRN 방식의 스케줄링은 SJF의 단점을 보완하여 서비스 시간이 긴 작업이 무한정 기다리는 기아(Starvation) 현상을 해결한 스케줄링 기법임
    -우선순위 = (대기시간 + 서비스 시간)/서비스 시간, 값이 높을수록 우선순위를 가짐.
    - 위의 표를 기준으로 우선순위를 산정해 보면
    A : (5+5)/5 = 2
    B : (10+6)/6 = 2.67
    C : (15+7)/7 = 3.14
    D : (20+8)/8 = 3.5
    - 우선순위는 D → C → B → A → 순임

 

I/O bound & CPU bound
  

 

 

댓글