7장 스케쥴링

7장 스케쥴링

7.1 워크로드에 대한 가정

7.2 스케줄링 평가 항목

7.3 선입선출

7.4 최단 작업 우선

7.5 최소 잔여시간 우선

7.6 새로운 평가 기준: 응답 시간

7.7 라운드 로빈

7.8 입출력 연산 고려

7.9 no more oracle

7.10 요약

 

8장 MLFQ: 멀티 레벨 피드백 큐

8.1 MLFQ 기본 규칙

8.2 우선순위 변경

8.3 우선순위 상향 조정

8.4 더 나은 시간 측정

8.5 MLFQ 조정, 다른 쟁점들

8.6 요약

 

9장 비례 배분

9.1 추첨권이 당신이 몫

9.2 추첨 기법

9.3 구현

9.4 예제

9.5 추첨권 배분 방식

9.6 왜 결정론 방법을 사용을 하지 않는가?

9.7 요약

 

10장 멀티프로세서 스케쥴링

10.1 멀티프로세서 구조

10.2 동기화를 잊지마라

10.3 캐시 친화성

10.4 단일 큐 스케줄링

10.5 멀티 큐 스케줄링

10.6 linux 멀티 프로세서 스케줄러

10.7 요약

 

---

7장 스케쥴링

7.1 워크로드에 대한 가정

원칙(discipline)

워크로드(workload)

일련의 프로세스들이 실행하는 상황

 

 

비현실적 가정

1. 모든 작업은 같은 시간 동안 실행 된다

2. 모든 작업은 동시에 도착한다

3. 각 작업은 시작되면 완료될 때까지 실행된다.

4. 모든 작업은 cpu만 사용한다(입출력을 수행하지 않는다)

5. 각 작업의 실행 시간은 사전에 알려져 있다.

 

---

7.2 스케줄링 평가 항목(scheduling metric)

성능 측면에서의 평가 기준

반환 시간(turnaround time): 작업 완료된 시각에서 작업이 시스템에 도착한 시각을 뺀 시간으로 정의

 

공정성 측면에서 평가 기준

공정성(fairness): 성능과 공정성은 스케줄링에서는 서로 상충되는 목표

---

7.3 선입선출(First In First Out, First Come First Served)

시스템에 3개의 작업 A, B, C가 거의 동시에 도착했다고 가정하자

평균 반환 시간은 (10+20+30) / 3 = 20

 

convoy effect

 

작업 A가 B와 C 보다 먼저 100초 동안 실행된다. 따라서 시스템의 평균 반환 시간은 110초로 늘어난다

 

(100 + 110 + 120) /3 = 110

 

convoy Effect

짧은 시간 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상

-> 이런 경우에는 짧은 작업을 먼저하는 것이 효율적이다.

---

7.4 최단 작업 우선(Shortest Job First, SJF)

 

(100 + 110 + 120) /3 = 110

(10 + 20 + 120) / 3 = 50

2배 성능 좋아짐

 

 

그러나.. 지켜지지 않는다.

B,C 보다 A가 먼저오면 방법이 없죠..

 

따라서 필요해진 것이.. 선점하지 않는 것이다.

 

---

 

비선점(non-preemptive) 스케줄러

각 작업이 종료될 때까지 계속 실행한다

 

---

7.5 최단 잔여시간 우선(Shortest Time-to-Completion First, STCF)

언제든 새로운 작업이 시스템에 들어오면, 이 스케줄러는 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고

그 중 가장 적은 잔여 실행 시간을 가진 작업을 스케줄한다

 

• 작업의 길이를 미리 알고 있고
• 작업이 오직 CPU만 사용하며
• 평가 기준이 반환 시간 하나라면

STCF는 매우 훌륭한 정책이다

 

 

 

((120−0)+(20−10)+(30−10)) / 3 = 50

 

 

---

7.6 새로운 평가 기준: 응답 시간(response time)

 

전제: A는 시간 0, B 와 C는 시간 10에 도착

응답 시간: A는 0, B는 0, C는 10, 평균 3.33이 된다

 

---

7.7 라운드 로빈(Round-Robin, RR)

RR은 작업이 끝날 때까지 기다리지 않는다. 

대신 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다.

이때 작업이 실행되는 일정 시간을 

• 타임 슬라이스(time slice) 
• 스케줄링 퀀텀(scheduling quantum)

타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수

 

RR 평균 응답 시간: (0+1+2) / 3 =1

SJF의 평균 응답 시간: (0+5+10) / 3 = 5

 

타임 슬라이스가 짧을수록, 응답 시간 기준으로 RR의 성능은 더 좋아진다.

 

그러나 타임 슬라이스를 너무 짧게 지정하면 문제가 생긴다. 

짧게 지정하면 문맥 교환 비용이 전체 성능에 큰 영향을 미치게 된다

 

문맥 교환 비용

• 레지스터를 저장/복원
• CPU 캐시
• TLB
• 분기 예측
• 다른 하드웨어에도 프로그램과 관련된 다양한 작업 정보들이 저장되어 있다.

 

모두 갱신되어야 한다. 

 

공정한 정책

작은 시간 단위로 모든 프로세스에게 CPU 를 분배하는 정책은 반환 시간과 같은 평가 기준에서는 성능이 나쁘다

---

7.8 입출력 연산 고려

 

 

프로세스의 입출력이 끝나기를 기다리는 동안 CPU는 다른 프로세스에 의해 사용되어 연산의 중첩이 가능해진다

---

7.9 no more oracle

 

---

7.10 요약