🎛️ 운영체제 - 5. CPU scheduling

출처 : http://www.kocw.net/home/cview.do?lid=af8e05c97c6d60de

---

🎛️ CPU and I/O Bursts in Program Execution

둘이 왓다갓다~

---

🎛️ CPU-burst time의 분포

여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요
- Interactive job에게 적절한 response 제공 요망
- CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

프로세스는 그 특성에 따라 다음 두 가지로 나눔

- IO-bound process
• CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
• (many short CPU bursts)

- CPU-bound process
• 계산위주의 job
• (few very long CPU bursts)

---

🎛️ CPU Scheduler & Dispatcher

CPU Scheduler
- Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고름

 

Dispatcher
- CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘김
- 이 과정을 context switch（문맥 교환）라고 한다

 

 

< CPU 스케줄링이 필요한 경우 >

프로세스에게 다음과 같은 상태 변화가 있는 경우

1. Running => Blocked （예: I/O 요청하는 시스템 콜)
2. Running => Ready （예: 할당 시간만료로 timer interrupt）
3. Blocked => Ready （예: I/O 완료 후 인터럽트）
4. Terminate (프로세스 종료 시)

 

* 1, 4에서의 스케줄링은 nonpreemptive（=강제로 뺏지 않고 자진 반납）
* All other scheduling is preemptive （= 강제로 빼앗음 )

---

🎛️ Scheduling Criteria

Performance Index (= Performance Measure, 성능 척도)

 CPU utilization
- keep the CPU as busy as possible

Throughput
- # of processes that complete their execution per time unit

Turnaround time
- amount of time to execute a particular process

Waiting time
- amount of time a process has been waiting in the ready queue

Response time
- amount of time it takes from when a request was submitted until the first response is produced, not output(for time-sharing environment)

 

CPU 사용률(CPU Utilization):

이 지표는 가능한 한 CPU를 바쁘게 유지하는 것을 목표로

CPU 사용률이 높다는 것은 시스템이 CPU를 잘 활용하고 있으며, 잠재적인 처리 능력을 낭비하지 않고 있다는 것을 의미

처리량(Throughput):

이는 시간 단위당 실행을 완료하는 프로세스의 수를

처리량이 높을수록 더 많은 작업을 빠르게 처리할 수 있다는 것을 의미하며, 시스템의 효율성을 나타냄

반환 시간(Turnaround Time):

특정 프로세스를 실행하는 데 필요한 시간의 총량

반환 시간을 줄이는 것은 시스템이 작업을 빠르게 처리할 수 있음을 의미하며 사용자 경험을 향상시킬 수 있음

대기 시간(Waiting Time):

프로세스가 준비 큐에서 대기한 시간의 총량

프로세스가 CPU에 접근하기 위해 기다리는 시간을 최소화하는 것은 효율성을 높이고, 자원 활용을 극대화하는 데 중요

응답 시간(Response Time):

요청이 제출된 시점부터 첫 번째 응답이 생성될 때까지 걸리는 시간

이는 시간 공유 환경에서 중요하며, 사용자가 시스템의 반응을 빠르게 느낄 수 있도록 함

---

🎛️ Scheduling Algorithms

- FCFS (First-Come First-Service)
- SJF (Shortest-Job-First)
- SRTF (Shortest-Remaining-Time-First)
- Priority Scheduling
- RR (Round Robin)
- Multilevel Queue
- Multilevel Feedback Queue

---

🎛️ FCFS (First-Come First-Service)

---

🎛️ SJF (Shortest-Job-First)

- 레디 큐에 있는 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
- CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄

 

<Two schemes>
- Nonpreemptive
• 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption)당하지 않음
- Preemptive
• 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
• 이 방법을 Shortest-Remaining-Time-First (SRTF)이라고도 부름

 

SJF is optimal
- 주어진 프로세스들에 대해 minimum average waiting time을 보장

---

🎛️ Priority Scheduling

A priority number (integer) is associated with each process

highest priority를 가진 프로세스에게 CPU 할당
(smallest integer = highest priority).
- Preemptive
- nonpreemptive

 

+ SJF는 일종의 priority scheduling
priority => predicted next CPU burst time

 

<Problem>
- Starvation: low priority processes may never execute.

<Solution>
- Aging: as time progresses increase the priority of the process.

---

🎛️ Round Robin (RR)

- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (일반적으로 10-100 milliseconds)
- 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 섬

- n 개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 (n-1)q time unit 단위로 CPU 시간의 1/n을 얻음
=> 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다

<Performance>
- q large => FIFO
- q small => context switch 오버헤드가 커짐

---

🎛️ Multilevel Queue

Ready queue를 여러 개로 분할
- foreground (interactive) - 사람과 인터렉션이 많은
- background (batch - no human interaction) - 계산 위주의 프로세스

각 큐는 독립적인 스케줄링 알고리즘을 가짐
- foreground - RR 
- background - FCFS

큐에 대한 스케줄링이 필요
- Fixed priority scheduling
• serve all from foreground then from background. - foreground 우선권
• Possibility of starvation - 위험

-  Time slice
• 각 큐에 CPU time을 적절한 비율로 할당
• Eg. 80% to foreground in RR, 20% to background in FCFS

---

🎛️ Multilevel Feedback Queue

Multilevel Queue + 프로세스가 다른 큐로 이동 가능
- 에이징(aging)을 이와 같은 방식으로 구현할 수 있음

Multilevel-feedback-queue scheduler를 정의하는 파라미터들
- Queue의 수
- 각 큐의 scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫒는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

+ 타임 퀀텀의 길이 정하기

등

---

+

🎛️ 다음 CPU Burst Time의 예측

수 다음번 CPU burst time 을 어떻게 알 수 있는가?
(input data, branch, user...)

- 추정(estimate)만이 가능
- 과거의 CPU burst time을 이용해서 추정 (exponential averaging)
<Exponential Averaging>

---

🎛️ Multiple-Processor Scheduling

CPU가 여러 개인 경우의 스케줄링

더욱 복잡

Homogeneous processor인 경우
- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡

 

Load sharing
-일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법

 

Symmetric Multiprocessing (SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정

 

Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

---

🎛️ Real-Time Scheduling

시스템이 정해진 시간 제약을 준수하면서 태스크(task)를 실행하는 것을 보장하는 스케줄링 방법

 

Hard real-time systems
- Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함

(항공 교통 제어 시스템이나 의료 생명 유지 시스템)
Soft real-time computing
- Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

(비디오 스트리밍이나 통화 품질)

---

🎛️ Thread Scheduling

운영 체제에서 실행 준비가 된 스레드(thread) 중 어느 것을 CPU에 할당할지 결정하는 과정

 

Local Scheduling
- User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정

- 운영 체제의 커널(kernel)은 이러한 스레드의 존재를 알지 못함
Global Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

- 커널에 의해 직접 관리되고 스케줄됨

---

🎛️ Algorithm Evaluation

알고리즘 평가

스케줄링 알고리즘과 같은 시스템 알고리즘들을 비교하고 평가하는 데 중요한 단계

스케줄링 알고리즘의 성능을 평가하는 방법에는 큐잉 모델, 구현 및 측정, 모의 실험 등 다양한 방법 존재!!!!!!!!!!!!!!

Queueing models
- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산

 

Implementation(구현) & Measurement (성능 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교

 

Simulation (모의 실험)
- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교