오퍼레이팅 시스템 [7] - Scheduling이란?(1)

in STUDY LOG / OS

‘유니프로세서의 스케줄링의 방법들’

Uniprocessor Scheduling

  • 단일 프로세서의 시스템에서의 스케줄링을 다룬다.

  • 멀티프로그래밍의 가장 중요한 부분은 바로 실행될 프로그램의 순서를 정하는 Scheduling이다.

Process 7 state에서 각 scheduling이 적용되는 상황

조금더 자세하게 표현한, 각 State에서 대기하는 프로세스들의 Queue와 그 작동원리

Scheduling의 종류

  • 빈번함의 차이에 따라 3종류와 I/O 스케줄링으로 나뉜다.
  1. Long-Term Scheduling
    Job들 중 어떤것을 실행할 프로세스로 분류할지 결정한다. 즉 시스템에서 실행될 프로세스의 개수를 조절한다.
    • 프로세스가 처음 생성될때 실행된다. (Ready State 혹은 Not)
  2. Medium-Term Scheduling
    디스크에 있는 어떤 프로세스들을 메인메모리에 올릴지 말지 결정한다.
  3. Short-Term Scheduling
    가장 자주 호출되는 스케줄링으로, 실제로 어떤 프로세스를 실행할지 결정한다. (Execute State 혹은 NOT)
    • 이번 글에서는 해당 스케줄링에 대해 다룬다.
  4. I/O Scheduling

Scheduling Level

  • Scheduling 방식은 Processor bound 와 I/O bound를 섞고, I/O사용을 적절히 조절한다.
    • Burst : CPU혹은 I/O가 요청된 작업을 수행하는데 걸리는 시간 (작동시간)
    • CPU Bound : I/O에 의해 block 되기전의 긴 Burst
    • I/O Bound : I/O에 의해 block 되기전의 짧은 Burst

Scheduling 기준

각 시스템마다 중요한 부분과 성능을 고려하여 스케줄링 방식을 최적화한다.

  • 슈퍼컴퓨터
    • 크고, 오래걸리는 작업을 계속해서 진행하는 경우가 대부분
    • CPU Bound의 비율이 높고, I/O 요청은 거의 없음
  • 클라우드 서버
    • 각 task들이 자원을 공평하게 나눠받아야한다.
    • Fairness(공정성) 중요
  • 개인용 컴퓨터
    • 개인이 상호작용하는 시스템
    • I/O 의 사용이 자주일어남
    • Turnaround Time, respone time중요!
  • 임베디드, Real-Time 시스템
    • 신속한 Interrupt 처리가 요구됨
    • Deadline 중요

Scheduling 방식들

  • 각 방식들을 설명하기 앞서 알아야할 중요요소
    • 선택함수(Selection Function) : 다음 실행될 프로세스를 결정하는데 있어 고려되는 여러 요소들.
      1. w : 지금까지 시스템안에서 실행되지 않을채로 기다린 시간
      2. e : 실행되고 있는 프로세스가 지금까지 CPU를 사용한 시간
      3. s : 예상 총수행시간, 남은 시간이 아니라 총 수행시간 이므로 e를 포함한다.

      ex) FCFS 방식에서는 선택함수 max[w]에 따라 우선순위가 결정된다.

    • 결정 모드(Decision Mode)
      1. Non-preemptive : 비선점모드. 무조건 프로세스가 한번 실행되면 완전히 종료될때까지 혹은 I/O를 기다리기 위해 스스로를 Block할때까지 실행한다.
      2. Preemptive : 선점모드. 스케쥴링에 따라 우선순위가 높은 새ㅗ운 프로세스가 들어오면 이전 프로세스 실행도중 전환이 가능하다.

1. FIFO

  • First In, First Out 방식으로 흔히 우리가 아는 선입선출 방식이다. FCFS(fisrt come, fisrt served)라고도 부른다.

  • 현재 프로세스가 종료되면, Ready List 에서 가장 오래 기다린 프로세스가 실행된다.

  • 선택함수 : max[w] - 가장 오래기다린 Process 부터
  • 결정모드 : Non-Preemptive
  • 장/단점
    • 간단하게 ready Queue하나로 구현가능하다.
    • 짧게 끝나는 프로세스(I/O-bound process)보다 오래걸리는 프로세스(CPU-bound process)에게 유리하다. (빨리 끝남에도 불구하고, 순서대로 다같이 기다려야하므로)
      • CPU-bound process 중, I/O 장치는 대부분 IDLE하게 대기하게 된다.
 Arrival TimeService Time(Ts)Start TimeFinish TimeTurnaround Time(Tr)Tr/Ts(효율)
W010111
X110011011001
Y21101102100100
Z31001022021991.99

ex) s(총수행시간)=1 인 프로세스의 경우, s=100 인 프로세스 직후에 Queue에 들어오게 되면 service time = 1 에 비해 Turnaround Time = 100이 매우 길어지며, 효율이 낮아진다.

2. SPN

  • Shortest Process Next 방식으로, 도착시간과 상관없이 가장 빨리 끝나는 프로세스부터 실행하는 방식이다.

  • FIFO 방식의 Long Process가 불리한 경우를 줄이기 위해 고안된 접근.

  • 선택함수 : min[s] - 총 수행시간이 짧은 프로세스부터
  • 결정모드 : Non-Preemptive
  • 장/단점
    • 전체적인 성능이 FIFO보다 훨씬 좋아진다. (Turnaround Time이 확 줄어든다!)
    • 하지만, Long Process가 실행되기 전에 계속해서 Short Process들이 들어와 Ready Queue앞에 추가되면 Long Process는 계속해서 대기하는 Starvation 문제가 발생할 수 있다.
    • 순서가 계속해서 변동되다보니 프로세스가 완료될때 까지의 시간을 예측하기가 힘들다.
      • 미래값을 예측하는 Simple Average, Exponential Average 방식을 사용하여 예측할 수 있다.
  • SPN vs FIFO 어떤 스케줄링이 더 효율적일까?
    • 일반적으로 짧은 Process를 먼저 실행시키는 SPN의 경우가 Turnaround Time이 작으므로 더 나은 성능을 보인다.
    • 하지만, 만약 모든 프로세스의 s(Sevice time)이 같은 경우와 같이 SPN과 FIFO의 Turnaround Time이 같다면, FIFO에 비해 SPN은 각 프로세스의 s값을 비교하여 Ready Queue를 다시 조정하는 추가 정보, 과정이 필요하므로 간단한 FIFO가 더 나은 성능을 보일 수도 있다.

3. SRT

  • Shortest Remaining Time방식으로, 프로세스의 종료까지 남은시간을 비교하여 더 빨리 끝나는 프로세스를 실행하는 방식이다.

  • SPN과 비슷하나, 프로세스 실행도중의 Remaining Time이라는 값을 도입한, SPN의 Preemptive버전이라고 볼 수 있다.

  • 선택함수 : min[s-e] - (총 수행시간 - 이미 실행된 시간) 즉, 프로세스가 들어온 시점에서 가장 빨리끝나는 프로세스부터
  • 결정모드 : Preemptive
  • 장/단점
    • SPN보다 더욱 짧은 Turnaround Time을 보여준다.
    • Preemptive방식으로 계속해서 남은시간을 계산하고, Process Switch를 해줘야 하므로 Overhead가 크다.
    • Long process가 Starvation상태에 빠질 수 있다.

4. HRRN

  • Highest Response Ratio Next방식으로, 앞서 설명한 SPN 과 SRT에서의 Long Process의 Starvation문제를 해결했다.

  • w에 비례하고, s에 반비례하는 Response Ratio라는 값을 도입하여 w가 클수록 즉, 대기한 시간이 길수록, s가 작을수록 즉, 총 수행시간이 짧을수록 우선순위를 준다.

  • 선택함수 : max[(w+s)/s]
  • 결정모드 : Non-Preemptive
  • 장단점
    • Long Process라도 대기시간이 길어질수록 Short Process보다 실행 우선권을 얻을 수 있는 가능성이 생겨 Starvation이 줄었다.
    • Response Ratio 를 계산하기 위한 추가계산과정이 필요하여 Overhead가 발생할 수 있다.

5. Round-Robin

  • FIFO방식에서 Short process들의 패널티를 줄이기 위해 고안된 방식이다.
  • 각 프로세스들이 주어진 Time Slice동안 CPU를 사용할 수 있으며, 이후 다른 프로세스에게 Preempt(선점)된다.
    • Timer를 이용한 Preemption
    • Time Slicing이라고도 불리는 기술이다.
  • 선택함수 : Constant
  • 결정모드 : Preemptive

Time slice가 3sec인 Round Robin Scheduling 알고리즘

  • 해당 스케줄링 방식은 Time Slice의 길이를 어떻게 설정하냐에 따라 달라진다.
    • The Shorter Time Slice
      • 더 빠른 Response Time
      • 매번 time slice가 종료될때마다 Clock Interrupt를 발생시켜야 하고, Process Switch와 스케줄링 함수또한 실행되어야 하므로 Overhead가 크다.
      • 짧은 프로세스부터 끝나는 SPN방식과 비슷하다.
    • The Longer Time Slice
      • 더 느린 Response Time
      • Scheduling Overhead가 줄어든다.
      • 먼저 준비된 프로세스부터 끝나는 FIFO와 비슷하다.
    • Time Slice가 짧을수록 Response Time은 빨라지지만, Turnaround Time은 느려질수도 있다.
  • 장단점
    • 프로세스당 똑같은 Time Slice를 할당해줘도, CPU-Bound process(Long process)는 일반적으로 주어진 Time quantum을 모두 사용하고 ready queue로 돌아오는 반면, I/O-Bound process(Short process)는 다 활용하지 못하고 I/O에 의해 Block되는 경우가 많다.
    • 즉, 여전히 Long Process에게 유리하다.
  • 해결방안

6. Virtual Round-Robin

  • Quantum Time을 다 사용하지 못한 Short Process의 Queue를 따로만들어(Auxiliary Queue) 한 루틴이 다 돌면 해당 Queue를 Main Ready Queue보다 우선해서 실행하는 방법이다.

7. Multi-level Feedback Queue

  • 프로세스가 여러 Queue를 이동할 수 있게 하는방식
    1. 여러 프로세스를 Cpu Burst에 따라 분류하기 위해 우선순위기 다른 여러 Queue를 만든다.
      • 일반적으로, 우선순위가 낮아질수록 Time Slice가 2배가 된다. (Long Progress에 한해 효율적)
    2. 가장 높은 우선순위를 갖는 Queue부터 실행한다.
    3. 만약 프로세스가 주어진 Time slice를 전부 사용하면, 낮은 우선순위의 Queue로 강등시킨다.
      • 시간이 지날수록 Short Process는 상위 Queue, Long Process는 하위 Queue에 위치하는 모습을 보이게된다.
      • 문제점 : Long Process의 Starvation 문제
        • 해결법 : 만약 w(waiting time)이 길어지면, 승급시킨다.

  • Queue의 개수, 각 Queue의 스케줄링 방식, 프로세스들의 승급과 강등 조건 등의 조건을 고려하여 Design해야 한다.

Scheduling 방식 Overview

정답인 스케줄링 방식은 없으며, 다양한 Scheduling 방식의 특징을 파악하고, 각 시스템과 상황에 맞춰서 적절한 것을 채택해야한다.