💻 [OS 오퍼레이팅시스템] #8 | Process Scheduling 2 | scheduling기준, Virtual Round Robin, 스케쥴링 알고리즘 비교, 다단계 피드백 큐 스케쥴링, MFQS

 

 

---

💻 용어 정리

- Burst (time)
CPU Burst : CPU가 실행한 소요시간
I/O Burst : CPU가 I/O기다리는 시간
cycle : CPU Burst와 I/O Burst 사이클을 반복하다가 언젠가 종료

- Bound
I/O Bound : CPU burst가 더 작은 프로세스 또는 프로그램
CPU Bound (CPU intensive) : CPU burst가 더 큰 프로세스 또는 프로그램으로, CPU process, CPU task로도 불림
2개 믹스된 프로세스도 있다.

---

💻 스케쥴링 기준(Criteria)

- 최적화(Optimization) 기준
CPU utilization : 얼마나 CPU를 활용해서 idle한 상태를 줄이는가
Throughput : 시간당 프로세스 처리량으로, 클수롤 좋음
Turnaround time : 들어가고 실행하고 나오기까지의 시간으로, 적을수록 좋음
Response time : 반응시간. 들어가고 실행이 시작되기까지의 시간
Deadline : 마감 시간. 요청한 시간을 스케쥴러가 얼마나 만족시키는가
Fairness : 최근 중요해짐. 할당할 때의 공정한 정도. 과금.

- 종류에 따른 특성
슈퍼 컴퓨터 : large, long running job사용하고, I/O보다는 CPU task가 많다 -> CPU burst가 크고 CPU bound 많다.
개인용 컴퓨터 : 사람과 상호작용 많이하고, I/O 사용 많다 -> I/O bound 많다.
임베디드 시스템 : 긴급한 task 많다 -> 긴급도 표시 priority, deadline 중요하다.
클라우드 서버를 위한 서버 컴퓨터 : share, fairness 중요

---

💻 스케쥴링 알고리즘의 실제적 비교상황

⬇️ 여러가지 스케쥴링 알고리즘 개념 설명은 이전 게시물 참고 ⬇️

💻 [OS 오퍼레이팅시스템] #7 | Process Scheduling 1 | Long-Term, Medium-Term, Short-Term, FCFS, SJF, SPN, Rount-Robin,

- FIFO vs SPN / RR
SPN(비선점)과 SRT(선점), HRRN(starvation X)은 비슷해서 SPN을 대표로 두고 설명함.

 

1. 각 프로세스의 service time이 다른경우 (SPN, SJF가 GOOD!)

다른 프로세스들 예시 그림

 

2. 각 프로세스의 service time이 유사한 경우 (유사프로세스 -> FIFO가 GOOD!)

유사 프로세스 예시 그림

 

* 워크로드 : 주어진 기간에 시스템에 의해 실행되어야 할 작업의 할당량. 워크로드에 따라 제일 좋은 알고리즘이 달라진다.

- RR (according to TS)

shorter time slice : Response time 반응시간 감소, turnaround time 반환시간 증가할 수도(유사프로세스일때), SPN과 유사(+process switch overhead)

longer time slice : overhead 감소, FCFS와 유사

 

1. 각 프로세스의 service time이 다른경우

다른 프로세스들 예시 그림

 

2. 각 프로세스의 service time이 유사한 경우  

유사 프로세스 예시 그림

 

- 통합 스케쥴링 I/O
(Scheduling Incorporating I/O). I/O Burst도 같이 고려해야함.

time slice 감소하면, I/O Utilization이 향상. I/O Bound 입장에서 좋음. CPU Utilization은 동일

CPU Bound에게는 time slice 감소하면 계속 인터럽트 발생하니까 핸들링을 계속 해주어야함, overhead 증가

 

예시 그림

-Time quantum
service time(처리하는데 필요한 시간)보다 조금만 더 크게 해야한다. 짧으면 굳이 두 번이상 수행해야하니까.
보통 통계 내보면, 대부분 특정 burst duration이 나온다.

위 차트에서는, 8이 특정 burst duration

---

💻 Virtual Round Robin

- Virtual Round Robin
Round Robin 단점 해결. longer 프로세스에게 편중되는 편향을 줄임.
auxiliary queue : 보조큐. 프로세서는 보조큐에 있는 프로세서부터 처리 후 레디큐의 프로세스 처리

Virtual Round-Robin 스케쥴러의 Queueing 다이어그램

* time slice 소진 유무 : 보통 I/O bound는 time slice 다 못쓰고(이벤트 기다림), CPU bound는 다 쓴다.

---

💻 Multi-Level Feedback Queues

- Multi-level feedback queues 다단계 피드백 큐 스케줄링 기법
커널 내의 준비 큐를 여러 개의 큐로 분리하여 큐 사이에도 우선순위를 부여하는 스케줄링 알고리즘
그냥 다단계 큐 스케줄링과의 차이점은 프로세스들이 큐를 갈아탈 수 있다는 점.

레디큐는 Foregroud(interactive) + Background(batch)로 나뉘어진다. 또는 I/O Bound + CPU Bound. (하여튼 여러 큐로 분리됨)
또한, 각각의 큐에 대해 다른 스케줄링 알고리즘을(RR, FCFS 등 독립적으로) 적용가능

우선순위가 낮은 프로세스가(long running job) CPU 할당을 계속 기다리는 기아 현상이 발생할 수도 있음 (해결방법으로 임계점 넘으면 승진시키는 방법이 있음)

처음에는 가장 높은 우선순위 큐에서 실행된다.
만약, 프로세스가 시간 할당량을 모두 쓰면, 우선순위가 1 감소하여 낮은 우선순위의 큐로 들어가고, time slice를 2배 증가시킨다.

* adapted algorithm : 환경에 따라 달라지는 알고리즘
워크로드에 따라 전략을 다르게 짜자는게 취지

 

---