[OS] Scheduling Schemes (스케줄링 기법 종류)

2024.01.09 - [CS 지식/Operating System] - [OS] Process Scheduling (프로세스 스케줄링)

앞선 글에서 프로세스 스케줄링에 대해서 알아보았다. 여느 것들과 마찬가지로 프로세스 스케줄링에도 여러가지 기법들이 존재한다. 어떤 것들이 있고 각각의 장단점을 살펴보자.

---

FCFS (First-Come-First-Service) scheduling

• Non-preemptive scheduling → time quantum X
• Scheduling criteria
  • 도착 시간 (ready queue)
  • 먼저 도착한 프로세스가 우선순위를 가진다.
• 높은 자원 이용률을 가진다.
• batch systems에 적합하지만, interactive systems엔 적합하지 않다.
• 단점
  • Convoy effect: 많은 프로세스들이 하나의 큰 프로세스 때문에 기다려야 하는 경우가 발생한다.
  • mean response time이 길다.

 

RR (Round-Robin) scheduling

• Preemptive scheduling
• Scheduling criteria → FCFS와 동일하다.
  • 도착 시간 (ready queue)
  • 먼저 도착한 프로세스가 우선순위를 가진다.
• 각 프로세스마다 time quantum이 존재한다.
  • system parameter
  • time quantum을 모두 소모한 프로세스는 CPU를 내놓고 ready 상태로 돌아간다. (timerrunout)
    • 프로세스의 CPU 독점을 예방할 수 있다. → 앞선 FCFS의 단점인 Convoy effect 예방
• preemption들로 인해 높은 context switching overhead를 가지게 된다.
• interactive systems, time-sharing systems에 적합하다.
• Round-Robin 기법은 time quantum에 따라 성능이 크게 달라진다.
  • Very large (infinite) time quantum → FCFS
  • Very small time quantum → processor sharing (n개의 프로세스가 CPU를 공평하게 나눠쓴다.), 매우 큰 Context switching overhead를 초래한다.

 

SPN (Shortest-Process-Next) scheduling

• Non-preemptive shceduling
• SJF (Shortest Job First) scheduling으로 불리기도 한다.
• Scheduling criteria
  • Burst time
  • burst time이 짧은 프로세스가 먼저 실행된다.
• 장점
  • 모든 프로세스들에 대해 average waiting time을 최소화할 수 있다.
  • 시스템 내의 프로세스 수를 최소화할 수 있다.
    • ready queue의 크기와 더불어 전체적인 필요 공간을 줄일 수 있다.
  • 많은 프로세스들에 대해  빠르게 반응할 수 있다. (위 예제에서도 많은 프로세스들의 waiting time이 0인 것을 볼 수 있다.)
• 단점
  • Starvation, 무기한 연기 (blocking)이 발생할 수 있다.
    • burst time이 긴 프로세스들에 대해 나타난다.
    • aging 기법을 활용해 해결할 수 있다.
  • 사실, 다음 CPU의 burst time이 얼마나 되는지는 실행하기 전에는 알지 못한다. 즉, SPN을 엄격하게 적용하기에는 비현실적이다.
    • 따라서 주로 기존까지의 CPU burst time의 기하평균을 활용해 다음 CPU의 burst time을 추정한다.

 

SRTN (Shortest Remaining Time Next) scheduling

• SPN 스케줄링의 변형된 버전이다. (preemptive SPN)
• Preemptive scheduling
  • SPN과 같이 burst time이 가장 짧은 프로세스를 실행하는 도중에 보다 짧은 burst time을 가진 프로세스가 ready queue에 들어왔을 때 preemption 된다.
• 단점
• SPN과 마찬가지로 burst time을 추정하는 데에 overhead가 발생한다.
• 추가적으로, 현재 실행중인 프로세스의 남은 burst time을 측정하는 overhead도 발생한다.
• 높은 Context switcing overhead가 발생한다.

 

HRRN (High-Response-Ratio-Next) scheduling

• aging 기법을 활용한다. → burst time이 긴 프로세스에 대해서도 기회를 준다.
• Scheduling criteria
  • response-ratio가 높은 프로세스가 먼저 실행된다.
• Response ratio: burst time과 waiting time의 비율이다.

• aging 기법을 활용하기 때문에 앞선 SPN 기법의 문제점인 starvation을 예방할 수 있다.
• 단점
  • SPN와 마찬가지로 burst time을 추정하는 데에 overhead가 발생한다.

 

Priority scheduling

• Scheduling criteria
  • 프로세스 우선순위 (process priority)
  • Tie breaking: FCFS
• 실제 운영체제에는 우선순위가 존재한다.
  • 각 시스템 별로 우선순위의 범위는 다르다.
    • MS Windows: 1(Low) ~ 32(High)
    • Unix: 0(High) ~ 119(Low)
    • Linux: 0(High) ~ 139(Low)
• Preemptive or Non-preemptive scheduling scheduling
• starvation 문제가 발생할 수 있다. (마찬가지로 aging 기법을 활용해 해결할 수 있다.)

 

MLQ (Multi-level Queue) scheduling

• ready queue를 다수의 분리된 queue로 나누고, 각 queue는 우선순위를 갖는다.
• 프로세스들은 영구적으로 특정 queue에 속하게 된다.
• 각각의 queue는 각자 자신만의 스케줄링 기법을 가질 수 있다.
• queue들의 스케줄링은 일반적으로 fixed-priority preemptive scheduling으로 이루어진다.

 

MFQ (Multi-level Feedback Queue) scheduling

• Arrival time, burst time과 같은 프로세스에 대한 정보가 없어도 사용 가능하다.
• MLQ와 마찬가지로 여러 개의 ready queue가 존재한다.
• MFQ의 목표
  • 짧은 burst time을 가진 프로세스 또는 I/O bound process를 선호하는 것 (SPN/SRTN/HRRN)과 같다.
  • adaptability(프로세스 특성에 따라 대응하는 능력)를 향상시키는 것
• Feedback
  • 프로세스의 CPU 사용 패턴에 대한 정보를 갖고 있다.
  • 프로세스가 ready queue 사이를 오갈 수 있도록 한다.
• MFQ의 특성
  • Dynamic priority
  • Preemptive scheduling
  • Favor short burst time processes and favor I/O bound processes
  • Improved adaptability
  • 프로세스의 어떤 정보도 없이 SPN, SRTN, HRRN 스케줄링 기법의 효과를 낸다.
• MFQ의 원리
  • 새로 생성된 프로세스는 제일 높은 우선순위를 가진 RQ(0)으로 들어간다.
  • 실행중인 프로세스가 RQ(i)로부터 dispatch 되었을 때, sleep state가 되고, wake up 했을 때 다시 RQ(i)로 돌아간다.
  • 실행중인 프로세스가 RQ(i)에서 preemption 되면 RQ(i+1)로 가게 된다. (time quantum을 다 쓴 경우)
• MFQ의 variations
  • MFQ 기법의 문제점
    • 높은 overhead
    • 낮은 순위의 queue에 대한 starvation
  • Variations
    • 각 ready queue들은 다른 time quantum을 준다, 즉 낮은 우선순위에 있는 프로세스들과 compute bound 프로세스들에서 발생하는 starvation을 해소하기 위해 낮은 우선순위 queue의 time quantum을 길게 줘서 queue가 한번 실행될 때 CPU를 오래 사용할 수 있도록 한다.
    • aging 기법을 활용해 waiting time이 길어진 프로세스 queue의 우선순위를 높여줄 수 있다.
    • I/O → compute → I/O 와 같이 사이클을 가진 process의 경우 CPU burst를 하는 도중에 우선순위가 떨어지게 되므로 I/O bound process를 move up 시켜 해결할 수 있다.
• MFQ의 parameters
  • queue는 몇 개를 둘 것인지
  • 각 queue는 어떤 스케줄링 알고리즘을 사용할 것인지
  • 언제 특정 프로세스를 높은 또는 낮은 우선순위로 바꿀 것인지에 대한 메서드
  • 첫 번째 프로세스가 어떤 큐로 들어갈 것인지에 대한 메서드

MFQ 스케줄링 기법은 현대 운영체제들의 근간이 되었다.