Chapter 9-2. Uniprocessor Scheduling

우선순위의 기준이 무엇이냐에 따라 좋은 스케쥴러가 달라진다.

우선순위: Queue 에 들어온 순서

• 공정성 ↑
• 예측가능성 ↑ : 내가 언제 실행을 끝낼 수 있는지 예측할 수 있음

SPN (Shortest Process Next), SRT (Shortest Remaining Time)

• Response Time 이 중요한 시스템에서 좋다.
• 그러나 시간예측과 Starvation 의 문제점이 있다.

 

Response Time	Fairness
SRT(Shortest Remaining Time)	Round-Robin
SPN(Shortest Process Next)	FCFS(First-Come-First-Service)

Preempted ↔ Non-Preempted : 기준으로도 나눌 수 있다.

Preempted	Non-Preempted
SRT(Shortest Remaining Time)	SPN(Shortest Process Next)
Round-Robin	FCFS(First-Come-First-Service)

---

Use Of Exponential Averaging

• x축: Time
• y축: T 값
• 검정색 찬 네모 그래프: 실제 시간당 실행시간을 나타낸 그래프이다.
• 검정색의 빈 네모 그래프: 산술평균으로 예측한 그래프이다. → 예측도가 낮다.
• 파란색 찬 동그라미 그래프: 알파 값이 0.8인 그래프로 실제 값과 비슷하다.
• 파란색 빈 동그리미 그래프: 알파 값이 0.5인 그래프로 실제 값과 비슷하다.

각각의 시간에 몇시간씩 작업하는지를 보여준다.

실행시간이 증가하는 그래프에서는 괜찮았지만 감소하는 그래프에서 exponential 예측 그래프의 경우 exponential 의 첫번째 값을 모르기 때문에 기본값은 1로 시작한다.
⇒ 처음엔 조금 헤매는 형태를 보인다.
↔ 나중엔 예측을 잘하는 모습을 보인다.
⇒ SPN, SRT 등을 실제로 구현할 수 있다는 의미이다.

SRT(Shortest Remaining Time)

Preemted 기법이다.

내가 실행하다 나보다 늦게 큐에 도착했어도, 실행 시간이 나보다 짧은 애가 오면 CPU 를 뺏긴다.

남아 있는 시간과 비교하기 때문에 "Ramining" Time 기법이라고 한다.

---

Shortest Remaining Time

1. 2시에 B가 왔지만 A의 실행시간이 1시간 남은 상태이므로 A가 끝까지 실행하고 CPU 가 B에게 넘어간다.
2. B가 1시간 실행하다 4시에 C가 오는데 B의 실행시간은 5시간 남았지만 C의 실행시간은 4시간 남은 상태이므로 CPU 를 C에게 빼앗기게 된다.
3. D가 6시에 도착했지만, 실행시간이 5시간인 D는 C보다 실행시간이 길므로 CPU를 빼앗지 않고, C가 끝까지 실행을 하게 된다.
4. 8시에 E가 오게 되어 총 3개의 프로세스의 실행시간을 비교하게 된다.
   • E(2) Vs. B(5) Vs. D(5) ⇒ E가 실행시간이 제일 짧으므로 E가 CPU 를 잡고 실행하게 된다.
5. B Vs. D 인 상황인데, 실행시간이 같으면 먼저온 프로세스가 먼저 실행하게 되므로 B가 실행하게 된다.
6. D가 실행한다.

A, C, E 는 Waiting Time 이 존재하지 않는다. B, D 만 Waiting Time 이 존재한다.

• Preemptive version of SPN(Shortest Process Next) Policy
• Must estimate processing time

Shortest Remaining Time의 Response Time

Response Time = Waiting Time + Service Time

• Service Time: 고정값
• Waiting Time: 다른 프로세스의 서비스 타임
  ⇒ 프로세스의 실행시간이 짧은걸 먼저 실행하게 되면 전체적인 Response Time이 감소하게 된다.

↔ But, 모든 프로그램이 SRT 를 사용하는가? → No! → Starvation 발생 가능성이 있다!

---

Highest Response Ratio Next (HRRN)

실행시간 짧은걸 먼저 실행하지만, 공정성도 잡을 수 있다.
⇒ Waiting Time이 긴 것을 먼저 실행시키기 때문에 Starvation 을 없앤다.

Ratio

• HRRN에서의 우선순위 = Ratio
  ⇒ Ratio 값이 큰 값을 먼저 실행시킨다.
• Ratio = 1 + W/S = Waiting Time/Service Time + 1
  ⇒ Ratio 값은 Waiting Time 이 길수록, Service Time 이 작을 수록 높아진다.

1. A 는 혼자 있기 때문에 계산할 필요가 없다.
2. B 는 혼자 있기 때문에 계산할 필요가 없다.
3. B 가 끝나면 큐에는 C, D, E 가 존재한다.
   • 이 때 Ratio 를 계산하면 C 가 가장 크므로 C 를 실행한다.
   • C 가 실행하는 동안 D, E 의 Ratio 값이 달라진다.
4. D, E가 큐에 있는데 Ratio 가 E 가 더 크므로 E가 실행된다.

⇒ 모든 프로세스가 같은 시간을 기다리지만, 수식에 따라 Service Time 이 작을 수록, Service Waiting Time 을 크게 느끼게 설정된다!

• Fair 하며 성능 까지 고려하는 로직이다.
• Non-Preemptive
• Preemptive 의 경우 새로운 프로세스가 나타날때마다 계속 계산을 해주어야 한다.
  ⇒ 그렇기 때문에 Non-Preemptive 로 구현한 것이다.

Highest Response Ratio Next (HRRN) 의 Response Time

HRRN 은 두 그룹의 중간정도의 성능과 Fair 을 가진다.

실제 큐는 1개가 아니라 여러개이기 때문에 여기서 배운 기법들을 응용한 기법을 사용한다.

---

Feedback

스케줄링 기법으로 앞에 5가지 기법을 응용한다.

1. 실행시간 ↓ O
2. 시간 계산 하고 싶지 않음 O
   ↳ 시간 예측을 프로세스마다 해주는 것을 하고 싶지 않음
3. Starvation 안 일어나게 하기 O

위의 3가지를 모두 해결한 방식이다. → 대부분 feedback scheduling 을 응용한 방법을 사용한다.

• Feedback q = 1
  ↳ Starvation 가능성이 매우 높다.
• Feedback q = 2^i
  ↳ i는 Queue 의 번호이다. 1번 Queue 의 경우 2시간 실행, 2번 Queue 의 경우 4시간 실행, ... Queue 의 번호가 커질 수록 CPU 를 잡으면 오랫동안 작업할 수 있다. → 아래쪽 Queue 는 CPU 를 차지하기 어렵다.
  ↔ 하지만, 한 번 CPU 를 잡으면 오랫동안 작업을 하기 때문에 할당량을 끝마칠 수 있도록 한다.

• Penalize jobs that have been running longer
• Don’t know remaining time process needs to execute

---

Multi-level Feedback Queue

• CPU 가 1개인 시스템이다.
• 3개의 Queue 가 존재한다.
• 모든 프로세스들은 0번 Queue 에서 실행을 시작한다.
  

  

1. 0번 Queue 에 있는 모든 프로세스들이 CPU 를 잡고 Timeout(Preemptive) 되어 다시 Queue로 돌아갈 때는 Queue1로 들어가게 된다.
2. 1번 Queue 는 0번 Queue 가 비었을 때만 실행시킨다. 0번 Queue 때와 마찬가지로 1번 Queue 의 모든 프로세스들이 CPU 를 잡고 실행하다가 Timout 되어 다시 Queue 로 돌아갈때는 Queue2로 들어간다.
3. 0번, 1번 Queue가 빌 경우에만 스케쥴링된다. 이제 갈 Queue가 없기 때문에 Round Robin 방식으로 작업된다.

---

Multi-level Feedback Queue (2)

Round Robin 방식은 Queue 를 그려가면서 진행 방식을 확인하자!

---

Fair-Share Scheduling

3가지 중에 Burst Time 계산 X But, 실행시간 짧은 애한테 우선권을 줬다고 직접적으로 말하지는 못하지만, 짧으면 0번 Queue 나 1번 Queue 에서 실행을 끝냈을 것이다.

실행시간이 짧을 수록, 0번 Queue 나 1번 Queue 에서 실행을 끝냈을 것이다.

• 0번 Queue, 1번 Queue : Queue 에 들어있는 프로세스의 실행시간이 길수도 짧을 수도 있다.
• 후반대의 Queue: 무조건 프로세스의 실행시간이 긴 프로세스들이 존재한다.
  ⇒ 즉, 후반대의 Queue에 들어있는 프로세스일 수록 우선순위가 낮다.
  ⇒ 실행시간이 길수록 실행될 확률이 낮다. ← 일종의 Penalty 라고 볼 수 있다.
  ↔ 실행시간이 낮을 수록 실행될 확률이 높아진다.

⇒ 따라서, 실행시간이 짧은 프로세스에게 우선권을 준다고 말할 수 있다!

프로그램 작성
→ 여러개의 프로세스로 작업
⇒ 프로그램의 여러개의 Process 나 Thread 를 동시에 실행하게 되면, Ready Queue 에 동시에 5명이 기다린다고 하면 6개의 프로세스 10개의 Thread 가 있다고 할 때, 5개의 Thread 를 갖고 있는 Process 가 전체의 50% 를 이용하게 된다.
⇒ Fair-Share Scheduling → User 의 Process 나 Thread 가 많은 CPU 들에 어느 애플리케이션에 속해있는지

• User’s application runs as a collection of processes (threads)
• User is concerned about the performance of the application
• Need to make scheduling decisions based on process sets

• Process A: t 하나의 App 에서 나온 하나의 Process
• Process B, C: 같은 App 에서 나온 두개의 Processes

A → B → C 순 X
A → B or A → C
⇒ Fairness 를 최대한 살린 프로그램이라고 할 수 있다.

---

Traditional UNIX Scheduling

9장에서는 CPU가 1개인 상황만을 다룬다. → CPU 가 1개인 시스템: Traditional UNIX

UNIX 는 Fairness 를 성능보다 중요하게 생각한다. (성능 < 공정성)
↳ 모든 프로세스가 CPU 를 공평하게 사용할 수 있도록 한다.

Preempted 방식인 TIMEOUT 을 사용하는데, TIMEOUT 이 되어 Queue1 로 가는 것이 아니라 다시 Queue0 으로 돌아온다.

Queue 1의 P3 이 실행되기 위해선 P1, P2 가 실행이 완전히 종료되거나 I/O 작업을 하기 위해 사라져 Queue0이 빌 경우에만 가능하다.

↑ 1초뒤, 우선순위가 바뀐다.

• P3가 Queue 0에 혼자 있는 상황
• P3 가 1초 동안 계속 실행하다가 P3 가 종료되거나 I/O 작업으로 Block 되면 1번 Queue에 P5, P4 가 실행된다.
• 결국 전부 실행 가능하게 되므로 굉장히 공정하다는 것을 알 수 있다.
  ↳ 우선순위가 낮아지는 경우는 없다.

• Multilevel feedback using round robin within each of the priority queues
  • Multilevel feedback 은 Round Robin 을 사용한다.
    ⇒ 아래의 Queue 로 내려가지 않고, 자기 Queue 로 다시 돌아온다.
  • 여러개의 Queue 가 있으므로 제일 높은 순위의 큐에 있는 애들은 Round Robin 으로 실행된다.
• Priorities are recomputed once per second
  • 우선순위는 1초마다 다시 계산된다.
  • 최근에 CPU 를 많이 사용했을 수록 우선순위가 낮아진다.
  • 최근데 CPU 를 적게 사용했다면 우선순위가 높아진다.
• Priority is based on process type and execution history
  • Process type 과 실행 기록 에 따라 우선순위를 계산한다.

---

Scheduling Formula

한시의 CPU 값 = 한시간 전 12시의 CPU 값 / 2
⇒ recursive 하게 정의한다.
⇒ 1/4, 1/8, ...

P 값이 작을수록 우선순위가 높다. P 값이 제일 작은 걸 제일 먼저 선택한다. 1초마다 한번씩 P 값을 계산한다.
→ 같은 Queue 에 우선순위가 같은 프로세스들을 순서대로 집어넣는다.
⇒ 굉장히 공정
⇒ Starvation X

• CPU 사용 ↑ → CPU 사용 못하게
• CPU 사용 ↓ → CPU 사용 하게

CPU 값이 0인 프로세스가 존재하면 확실하게 실행한다.
→ 방금 시스템 안에 들어온 Process ⇒ Queue 의 제일 앞에 들어간다.
→ 실행시간이 길지 짧을지 모른다.
⇒ 최근에 들어온 애가 먼저 실행된다.
⇒ 성능이 나쁘지 않다.

CPUj(i)

Execute History

i 초에 j Process 의 우선순위

Pj(i)

Basej

프로세스 j base priority → 무슨 작업을 하는 프로세스?

• user process 일 수록 우선순위가 낮다.
• system 작업을 하는 process 일수록 우선 순위가 높다.

다음의 순서로 우선순위가 낮아진다.
1. Swapping
2. Block
3. File
4. 문자 단위

1, 2, 3, 4, ... X

굉장히 차이가 크다. ⇒ 같은 작업하는 프로세스 사이에 우선순위가 역전하는 일이 없도록 한다.

nicej

user 가 주는 값이다. → System call 로 nice 값을 조절할 수 있다.

기본 값보다 낮출 수는 있지만, 높일 수는 있다. 이를 통해 상대적 우선순위를 높일 수 있다.

---

Traditional UNIX Scheduling(2)

Base priority divides all processes into fixed bands of priority levels

• Swapper (highest)
• Block I/O device control
• File manipulation
• Character I/O device control
• User processes (lowest)

Nice adjustment factor used to keep process in its assigned band

---

Traditional UNIX Scheduling 의 Response Time

U = Utilization → 1초마다 한번씩 시간 계산을 할 수 있다.

나 혼자 CPU 다 쓰면 U = 1 이다.

T1

• T1 = 1 → 1시간 사용 X, 비율 O
• T1 = 1/2 → 전체 1초 중 Queue 에 2명이 같이 들어 있어서 반 사용한 것
• T1 = 1/4 → 전체 1초 중 Queue 에 4명이 같이 들어 있어서 번갈아가면서 작업한 것

T2

T2: 전시간의 U의 반 값을 사용한다.

• T2 = 0 + 1/2
• T2 = 0 + 1/4
• T2 = 0 + 1/8

내가 매번 CPU 를 얼만큼 썼는지를 계산한다.
↳ 한타임 지날 수록 1/2 씩 곱해진다.
⇒ 내가 CPU 사용한 것에 가중치를 주어 더한다.
⇒ CPU 를 많이 사용하면 CPU 하게 된다.
↔ CPU 를 많이 사용하지 앟을 수록 0에 가까운 값이 된다.