[OS] Scheduling

스케줄링 평가 기준

• Turn around time(반환 시간)
  = 작업 완료 시간 - 작업 도착 시간
  
  
• Response time(응답 시간)
  = 시스템으로부터 첫번째 응답이 온 시간
  = 작업 시작 시간 - 작업 도착 시간
  
  
• Fairness(공정성)
  = 얼마나 고르게 여러 프로세스에 cpu에 분배했느냐에 대한 척도 (성능과 상충)

 

preemption vs non-preemption

preemption(선점)은 다른 프로세스가 선점하고 있는 cpu를 빼앗을 수 있는 것을 의미하고

non-preemption(비선점)은 반대로 빼앗을 수 없다는 것을 의미한다.

---

여러가지 스케줄링 기법

현실적인 os가 아닌 다음의 가정을 따른다는 하에 성립되는 이론들

1. 모든 task는 동일한 시간 동안에 실행된다.
2. 모든 task는 동일한 시간에 도착한다.
3. 모든 task는 시작되면 완료될 때까지 실행된다.
4. 모든 task는 CPU만 사용한다. (I/O 배제)
5. 모든 task의 실행 시간은 알려져 있다.

First In First Out (FIFO)

• 선입선출 방식에 의한 스케줄링
• non-preemption
• 장점: 간단하고 구현이 용이
• 단점: convoy effect - 매우 짧은 시간이 소요되는 task임에도 늦게 들어왔다는 이유로 매우 긴 시간을 대기해야하는 상황

​

Shortest Job First (SJF) / Shortest Process Next (SPN)

• 짧은 작업 시간을 가진 프로세스 먼저 스케줄링
• non-preemption
• 장점: convoy effect 해결
• 단점: starvation effect - 작업 시간이 긴 프로세스는 계속 우선순위가 밀려 오랫동안 할당 받지 못하는 상황

​

Shortest Time-to-Completion First (STCF) / Shortest Remaining Time (SRT)

• 새로운 프로세스가 들어올 때마다 최소 잔여 시간을 가진 프로세스 먼저 스케줄링
• preemption
• 장점: convoy effect 해결
• 단점: 여전히 starvation effect 해결 x

​

Highest Response Ratio Next (HRRN)

• 대기 시간과 작업 시간을 둘다 고려한 수식에 따라 스케줄링
• (대기 시간 + 작업 시간) / 작업 시간 => 큰 값의 프로세스 선택
• non-preemption
• 장점: starvation effect를 보완

​

Round Robin (RR) / Time Slicing

• time slicing 마다 돌아가면서 큐에 들어온 순서대로 스케줄링
• preemption
• 장점: 평균 응답 속도가 굉장히 빨라 실시간 시스템에 유리
• 단점: 평균 반환 시간이 최악 -> 짧은 task에 불리
• time slicing 단위가 너무 클 경우 비선점 FIFO 기법과 같아지게되며
  너무 작을 경우 context switch 횟수가 급격히 늘어나 overhead가 발생

 

※ 스케줄링 기법 비교

Scheduling	선택 함수	preemption	응답 시간	문맥 교환 비용	유리한 process	Starvation
FIFO/FCFS	max[w]	non-preemption	길 수 있음	최소	연산 많은 process	X
SJF/SPN	min[s]	non-preemption	연산 적을수록 짧음	커질 수 있음	짧은 process	O
STCF/SRT	min[s-e]	preemption	짧음	커질 수 있음	연산 적은 process	O
HRRN	max((w+s)/s)	non-preemption	짧음	커질 수 있음	다소※ 공정	X
RR	상수	preemption	연산 적을수록 짧음	최대	모두에게 공정	X

---

MLFQ(Multi Level Feedback Queue)

• 큐를 여러개 두고 스케줄링하는 방식
• 각 큐는 다른 우선순위가 부여되며 같은 큐 안의 프로세스들의 우선순위는 동일 -> Round Robin
• 높은 우선순위큐에 있는 프로세스가 높은 우선순위를 가짐
• 낮은 우선순위큐로 갈수록 사용가능한 TQ가 길어짐 
• 각 프로세스는 규칙에 따라 우선순위가 변함

​

MLFQ Rule

1. 우선순위가 더 높은 (더 상단의 Queue에 위치한) task를 먼저 수행
2. 우선순위가 같은 (같은 Queue에 위치한) task 중에서는 먼저 들어온 task를 수행
3. 처음 실행되는 task에 대해서는 가장 높은 우선순위를 부여(최상단 Queue에 push)
4. TQ를 모두 소모하면, 우선순위가 낮아짐(아래의 Queue에 push)
5. TQ를 모두 소모하기 전에 CPU 점유를 해제하면, 같은 우선순위를 유지(같은 Queue에 push)

​※ MLFQ는 대화형 작업(I/O 위주)인 프로세스에 유리

​

MLFQ의 한계

1. starvation effect 발생 가능성
2. 무의미한 I/O를 빈번히 발생시켜 우선순위를 강제로 유지하도록 조작 가능성
3. 시간에 따라 프로세스의 특성이 달라져도 한 번 내려간 우선순위 조정 불가

​

MLFQ 개선

• 일정 시간 S가 지나면 모든 프로세스들을 최상위 큐로 초기화시킴(Boosting)
  S의 주기 설정이 중요 => 너무 크면 starvation, 너무 작으면 대화형 작업에 불리
  => 1번 3번 한계를 해결할 수 있음

• 해당 큐 안에서 cpu 사용 시간의 합이 TQ에 다다를 경우 우선순위를 낮춤
  => 2번 한계를 해결할 수 있음

---

Proportional Share scheduling

반환 시간이나 응답 시간을 최적화하면서 각 프로세스에 cpu를 일정 비율로 할당하는 스케줄링

Ticket이라는 개념을 사용하는데 이는 프로세스가 받아야할 자원의 몫을 의미한다

만약 전체 티켓이 100장이고 해당 프로세스가 소유한 티켓이 75장이라면 75%의 cpu를 할당받는다

​

Lottery Scheduling

• 스케줄러는 전체 티켓의 수를 알고있어야 함
• TQ가 끝날 때마다 확률적으로 ticket을 선택
• 프로세스가 오래 실행되면 티켓 수의 비율대로 cpu를 할당받게될 가능성이 높아짐

 

Ticket Mechanisms

• time currency
  사용자가 추첨권을 자신의 화폐 가치로 티켓을 마음대로 할당할 수 있게 허용
  즉, 각 프로세스가 가진 전체 티켓을 고려하여 global currency를 맞춰 줌
  
  
• ticket transfer
  한 프로세스는 다른 프로세스에게 일시적으로 티켓을 빌려줌

• ticket inflation
  프로세스는 일시적으로 자신이 소유한 티켓 수를 늘이거나 줄일 수 있음
  경쟁적 시스템이므로 실질적 불가능

---