[OS] 프로세스 스케줄링 알고리즘

CPU 스케줄링이 필요한 경우

• Running→Blocked(예: I/O요청하는 시스템 콜)
• Running→Ready(예: 할당시간 만료로 timer interrupt)
• Blocked→Ready(예: I/O완료 후 인터럽트)(선점형일 때)
• Terminate→Running→Blocked와 Terminate에서의 스케줄링은 nonpreemptive(비 선점형)→나머지 경우는 preemptive(선점형)→ 현대적인 cpu 스케줄링은 대부분 선점형 스케줄링을 사용

Scheduling Criteria (Scheduling Algorithm 의 성능 척도)

• CPU utillization(이용률)→시스템 입장에서 성능척도(cpu 하나가지고 최대한 일을 많이 시키면 좋음)
  • 전체 시간중 cpu 가 놀지 않고 일한 시간 비율 (0%~100%)
• Throughput(처리량)→시스템 입장에서 성능척도
  • 주어진 시간동안 과연 몇개의 일을 처리했는가?
• Turnaround time(소요시간 ,반환시간)→프로그램 입장에서 성능척도(내가 cpu를 빨리 얻어서 빨리 끝내면 좋음, 시간을 얼마나 빨리 처리할 수 있는가?)
  • cpu를 사용하러 들어와서 다 처리후 나갈때 까지 걸리는 시간
  • T(turnaround) = T(completion) - T(arrival)
• Wating time(대기시간)→프로그램 입장
  • cpu를 사용하기 위해 기다린 시간들
• Response time(응답시간)→프로그램 입장
  • 최초 cpu를 얻기 까지 기다린 시간

스케줄링 알고리즘 목표

• Maximize the CPU utilization 
• Maximize the throughput
• Minimize the turnaround time
• Minimize the waiting time
• Minimize the response time
  • It may be more important to minimize the variance than the average of response
  time.
  • E.g. interactive system
• 낮은 기아 현상 발생률

선점과 비선점 스케줄링 알고리즘

비선점(Preemptive):FCFS,SJF

• 장점
  • 모든 프로세스에 대한 공정한 처리
  • 문맥교환으로 인한 오버헤드가 적음
• 단점
  • burst time이 긴 프로세스에 의해 burst time 이 짧은 프로세스가 기다리는 현상이 생길 수 있음

선점(Nonpreemptive): SRTF,RR

• 장점
  • 우선순위가 높은 프로세스에 빠른 응답시간 보장
• 단점
  • 프로세스간 문맥교환이 자주 발생
  • Starvation발생가능

스케줄링 알고리즘 종류

FCFS (First - Come First - Serverd)

• 먼저 도착한 순서대로 처리
• 비 선점형 스케줄링
• cpu 를 오래 쓰는 프로그램이 먼저 도착해서 cpu를 잡아버리면 짧은 프로그램이라도,기다려야함
• 앞에 어떤 프로세스가 버티고 있느냐에 따라 기다리는 시간에 상당한 영향을 줌
• Convoy effect: 긴 프로세스가 먼저 도착해서 짧은 프로세스가 오래 기다려야 하는 현상을 말함

일반적인 예시

Convoy effect 예시

SJF (Shortest Job First)

CPU burst time 이 가장 짧은 프로세스를 제일 먼저 스케줄

• Nonpreemptive
  • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때 까지CPU를 선점당하지 않음
  • CPU를 다 쓰고 나가는 시점에 스케줄링을 할지말지 결정

일반적인 예시

문제점: 각 일들이 언제든 도착할 수 있다.

STCF(Shortest Time-to-Completion First)

SJF에 preemption 을 추가 - SJF를 선점/ 비선점으로 나누기도 하는듯

• Preemptive 방식
  • 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
  • 이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부름
  • 새로운 프로세스가 도착하면 언제든지 스케줄링이 이뤄짐
  • SRTF(=SRT) 방식은 주어진 프로세스들에 대해 minimum average waiting time 을 보장

 

 

위 두 방식의 문제점 

• Starvation(기아 현상): CPU 사용시간이 긴 프로세스는 영원히 CPU를 사용하지 못할수 있음
• CPU 사용시간을 미리 알수 없음→SJF 는 CPU사용시간을 알아야 가능
  • 과거의 CPU burst time 을 이용해서 추정

우선순위 스케줄링이란?

우선순위가 제일 높은 프로세스에게 CPU를 줌 (보통 정수값으로 표현, 대부분 정수중에서 작은 정수가 우선순위가 높다고 표현)

• SJF 는 일종의 priority scheduling 임(priority=predicted next CPU burst time)
• Preemptive
  • 더 높은 우선순위 프로세스가 들어오면 CPU를 빼앗김
• Nonpremptive
  • 더 높은 우선순위 프로세스가 들어와도 기존 프로세스가 완료될때 까지 CPU를 선점 당하지 않음
• 문제점
  • Starvation(기아 현상):우선순위가 낮은 것들은 영원히 CPU를 사용하지 못할수도 있음
• 해결책
  • Aging: 아무리 우선순위가 낮은 프로세스라도, 오래기다릴 경우 우선순위를 높혀줌

RR(Round Robin) = Time Slicing Scheduling

현대적인 컴퓨터 시스템에서 사용하는 CPU스케줄링은 RR에 기반

• 응답시간을 빠르게 하기 위한 방식! T(response) = T(first run) - T(arrival) 
• 앞서 설명한 방식들은 응답 시간이 좋지 못하다.
• 각 프로세스는 동일한 크기의 할당 시간 (Time quantum)을 가짐 (일반적으로 10~100milliseconds)
• 누가 CPU를 오래쓸지 모르는 상황에서 예측할 필요 x, CPU를 짧게 쓰는 프로세스가 실행되고 빨리 나갈수 있도록 해줌
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 섬
• CPU를 사용하는 시간에 따라 기다리는 시간이 비례함 (RR특징)
• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit 인 경우 각 프로세스는 최대 q time unit 단위로 CPU시간의 1/n을 얻음
• →어떤 프로세스도 (n-1) q time unit 이상 기다리지 않음

Time slice의 길이가 중요!

• q 를 너무 키울경우→응답 시간 증가, FCFS
• q 를 너무 작게 할 경우→context switch 오버헤드가 커짐, 응답 시간 감소
• 일반적으로 SJF 보다 average turn around time 은 길지만 response time 은 더 짧음
• Trade off가 있기 때문에 시스템 설계하는 사람의 결정에 따름.

Incorporating I/O

사이 사이 일을 끼워넣어 CPU utilization을 극대화

Multi-level Feedback Queue

• 일반적인 CPU 스케줄러: Workload에 대한 사전 지식 없음 -> 미래를 예측하기 위해 과거로부터 배우기
  (branch predictors or cache algorithms에서와 같이)

• 프로세스는 다양한 큐를 움직일 수 있다.
• MLFQ는 다양한 큐 가짐(각 큐는 다른 우선순위 레벨 할당 받음)/ 실행 준비된 일은 단일 큐에 있어야한다. 같은 우선 순위면 RR에서 돌아감.
• Interactive jobs (I/O intensive jobs): 우선순위 높게(러닝타임 짧으나 높은 응답속도 필요)
• CPU Intensive jobs: 우선순위 낮게(긴 시간 필요. 응답 속도 상관 없음)

MLFQ의 두 가지 기본 규칙

• 규칙 1 : Priority(A) > Priority(B) 이면, A가 실행된다. (B는 실행X)
• 규칙 2 : Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다. 

MLFQ 우선순위 조정 알고리즘

1. 작업이 시스템에 들어가면 작업이 가장 높은 우선 순위에 놓입니다
2. 작업이 실행되는 동안 전체 타임 슬라이스를 사용하면 우선 순위가 줄어듭니다(즉, 대기열에서 아래로 이동).
3. 작업이 타임슬라이스가 작동하기 전에 CPU를 포기하면 동일한 우선 순위 수준을 유지합니다.4. 일정 기간이 지나면 시스템의 모든 작업을 맨 위 대기열로 이동합니다.

일반 MLFQ의 문제

• Starvation:
  • If there are “too many” interactive jobs in the system. 
  • Long-running jobs will never receive any CPU time.
• Game the scheduler
  • After running 99% of a time slice, issue an I/O operation.
  • The job gain a higher percentage of CPU time.
• A program may change its behavior over time.
  • CPU bound process à I/O bound process

MLFQ  요약

• 규칙 1 : 우선순위(A) > 우선순위(B) 이면 A실행. B는 실행되지 않음

• 규칙 2 : 우선순위(A) = 우선순위(B) 이면 A, B를 RR로 실행

• 규칙 3 : 작업이 도착하면 가장 높은 우선순위에서 시작

• 규칙 4 : 작업이 지정된 단계에서 배정받은 시간을 소진하면 (CPU 포기 횟수 무관) 우선순위 감소 (한단계 아래 큐로 이동)

• 규칙 5 : 일정 주기 S 마다 모든 작업을 가장 높은 우선순위 큐로 이동

 

좀 더 자세한 설명

2-4장. 스케줄링 : 멀티 레벨 피드백 큐(MLFQ)

 

Multilevel Queue

• Ready queue를 여러개로 분할
  • foreground(interactive)
    • foreground에는 유저 인터랙션이 있는 작업이 많이 들어감
    • 유저 인터랙티브한 작업의 우선순위가 높은 경향을 가진다
  • background(batch - no numan interaction)
  • (batch job: 오래 CPU를 잡고 쓰는것을 의미)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground -RR
  • background- FCFS
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling (우선순위가 foreground 가 높을경우, foreground 에 해당하는 것들을 다 처리 후 background queue 사용 가능)
    • 문제점 starvation이 발생할 수 있음
  • 해결방법
    • Time slice→각 큐에 CPU을 적절한 비율로 할당