[OS][운영체제] 5. CPU Scheduling / CPU 스케줄링

1. 스케줄링의 개념
2. 스케줄링의 기준
3. 스케줄링 알고리즘
4. Issues
5. OS 예시
6. 알고리즘 평가

---

1. 스케줄링의 개념

CPU Scheduling

메모리의 프로세스 중 하나를 실행 준비를 위해 CPU로 골라 할당한다.

멀티프로그래밍(I/O 작업 시에 CPU는 다른 프로세스를 잡는 시스템)을 포함하는 CPU 활용을 최대화하며,

CPU burst, I/O burst(CPU wait)의 순환이 짧게짧게 이뤄진다.

 

*CPU Utilization = CPU 활용시간(I/O or CPU) / CPU 활용시간 + 오버헤드

 

[사진 1] CPU

 

- 스케줄링 하는 프로세스는 다음과 같다:

• non-preemptive(interrupt 될 수 없음) 방식은 중단되었거나, 실행되다가 waiting(I/O 작업) 할 때
• preemptive(새로운 프로세스의 우선 순위가 높다면 interrupt 될 수 있음) 방식은 ready(interrupt) 상태가 될 때
  • -> SRTF; Shortest Remaining Time First

- Dispatcher: short term 스케줄러에 의해 선정된 한 프로세스에 CPU 제어를 넘겨준다.

이는 kernel에서 user mode로 전환된다.

-> 다른 프로세스 실행으로 교체되는 switching context (PCB0에 저장, dispatch, PCB1에서 reload)

 

시간은 Dispatch latency로 나타낸다

 

[사진 2] Dispatch

---

2. 스케줄링의 기준

1. 높은 CPU 활용도
2. 높은 시간당 처리량(Throughput)
3. 적은 프로세스 실행에 걸리는 시간(Turnaround time)
4. 적은 Waiting 시간(in the ready queue) -> “Turnaround time - Burst time”
5. 적은 반응 시간(시분할 시스템에서 고려된다)

---

3. 스케줄링 알고리즘

FCFS(First-Come, First-Served)

ready queue에 들어온 순서대로 처리한다

 

- Convoy effect: FCFS에서 짧은 프로세스가 보다 뒤에서 waiting할 경우 Average waiting time이 늘어나게 된다

 

SJF(Shortest-Job First)

CPU burst time이 작은 순서대로 처리하는 알고리즘으로, Average waiting time 측면에서 좋다

• non-preemptive 방식
• preemptive 방식: 평균 waiting time은 좋을 수 있지만, context switching이 잦아 오버헤드가 늘어난다

- Priority 스케줄링은 우선순위의 정수 값을 부여해 처리하는 알고리즘으로, 예측한 다음 CPU burst시간이 우선순위가 된다

(a값을 이용하여 τ(n+1) = a*t(n) + (1-a)*τ(n) 식으로 a값에 따른 다음 CPU burst를 예측할 수 있다)

 

[식 1] next CPU burst

[식 2] next CPU burst

 

낮은 우선순위의 프로세스가 계속 밀리는 문제(starvation)는 waiting 시간에 따라 우선순위를 조금씩 높여주며 해결한다(Aging 방식)

 

RR(Round Robin)

CPU에 할당 받을 때 실행 시간이 정해져 있다 -> 시간 quantum만큼 n개의 프로세스가 돌아가며 쓴다

 

[그림 3] RR

q가 크면 FIFO와 같아지고, q가 작으면 context switch가 잦아져 오버헤드가 늘어난다

SJF에 비해 평균 turnaround time은 길지만 반응 시간은 적다

- Rule of Thumb: RR 알고리즘은 약 90프로의 프로세스가 한 번에 끝날 time quantum일 경우 가장 좋다

 

Multilevel Queue

Ready Queue를 나눠 프로세스를 나눠 처리한다.

ex) foreground는 RR 방식으로 처리 / background는 FCFS 방식으로 처리

- 분할한 큐마다 Priority를 설정한다 (-> starvation 문제의 가능성이 있다)

- 분할한 큐마다 CPU time을 지정한다: Time slice

ex) foreground: 80% / background: 20%

 

[그림 4] Multilevel Queue

 

Multilevel Feedback Queue

프로세스들이 다음 요인을 통해 aging 방식(우선순위를 조정)을 더하고, 다른 큐로 이동할 수 있다.

• 큐의 수
• 각 큐의 스케줄링 알고리즘
• 프로세스를 다른 큐로 승격/강등하는 방법
• 어떤 큐로 들어갈지 정하는 방법

[그림 5] Multilevel Feedback Queue

 

ex) job이 q=8에서 안 끝나면 다음 큐로 이동 -> q=16에서 안 끝나면 FCFS 큐로 이동

---

4. Issues

이슈 1. Multiple-Processor Scheduling

멀티 프로세서 스케줄링의 구조는 다음과 같다.

• 비대칭적 구조: 한 프로세서가 마스터로써 시스템 데이터 구조에 접근하여 다른 프로세서들에게 일을 준다(Push migration). 이는 데이터 공유의 필요성을 완화(alleviate)한다.
• 이외의 프로세스들은 동등한 위치로 대칭적(SMP; Symmetric MP) 구조를 가진다. 이들은 일을 받는다(Pull migration).
• -> Load Sharing: Push & Pull

- 프로세서 관련성(affinity): 모든 CPU는 프로세서를 잡고 작업을 처리한다. 이후 작업을 처리할 때 잡았던 프로세서를 다시 잡는다면 “유효한 캐시 비율(Cache hit ratio)”을 고려하게 된다.

-> Hard affinity / Soft affinity

 

이슈 2. Real-Time Scheduling

• Hard real-time systems: 중요한 작업을 주어진 시간을 보장하여 처리하는 시스템
• Soft real-time systems: 우선순위를 높여 최대한 처리하는 시스템

 

이슈 3. Thread Scheduling

시스템 프로세싱의 단위가 스레드일 경우 다음과 같이 두 가지로 분류된다.

• Local Scheduling: 유저 레벨의 threads library가 어떻게 LWP; Lightweight Process(Virtual processor)에 할당되는가
• Global Scheduling: 커널이(CPU)가 LWP에 대응되는 어느 커널 thread에 할당되는가

[그림 6] Thread Scheduling

---

5. OS 예시

Solaris 2

다른 classes에 queues를 나누고, priority와 time quantum 값이 반비례 관계이다.

 

Windows XP

각 class와 class 관계에 priority 값을 준다.

 

Linux

신용도 기반(credit-based)으로 Time-sharing을 한다. 신용도가 점점 차감되며 0이 되면 다른 프로세스가 선택된다. 후에 우선순위와 기록 기반으로 신용도를 재할당한다 (Soft real-time)

---

6. 알고리즘 평가

다음과 같은 방법으로 알고리즘을 평가할 수 있다.

• Deterministic 모델링: 각 프로세스의 workload를 그려 성능을 평가한다
• Queuing 모델: n [Queue length] = λ [Arrival rate] * W [Waiting time in the queue]
• Simulation 모델: CPU의 trace를 tape에 담고, 데이터 값으로 통계를 내 성능을 평가한다.