Operating System - Ch05. CPU Scheduling

본 글은 Operating System Concepts 10판을 기준으로 작성되었습니다...!

 

 

 

이번에는 CPU 스케줄링에 대해서 알아보자.

 

CPU Scheduler: 어떤 녀석에게 CPU자원을 사용할 권한을 줄 것인가를 결정함

 

CPU burst: I/O 연산이 아닌 CPU연산을 중심으로 하는 구간

I/O burst: I/O 요청을 위해서 기다리는 구간 (I/O wait)

 

CPU-bound process: CPU burst의 비율이 높은 녀석, 연산이 많이 필요한 경우. 단순하면서 높은 성능을 내도록 설계

  ex) 슈퍼컴퓨터, Simulation

I/O-bound process: I/O burst의 비율이 높은 프로세스, 네트워크 통신이나 로컬 파일과 동작하는 경우가 많을 때. 컴퓨터와 유저간의 응답성이 중요할 때.

  ex) 우리가 PC에서 사용하는 대부분의 프로그램은 I/O-bound process.

 

 

 

---

 

Dispatch: 스케줄러가 선택한 프로세스에게 CPU core의 제어권을 주는 행동.

Dispatch: Dispatch 하는 놈.

 

 - switch context (프로세스간 context switching)

 - switching to the user mode (유저 모드로 전환)

 - jumping to the proper location in the user program to restart that program (유저 프로그램을 위한 적절한 위치로 점프)

 

넓은 의미의 스케줄링은 Dispatch까지 포함한다.

디스패처는 Context switching 할 때마다 실행되기 때문에 빨라야 하며, 프로세스를 중단하고 다른 프로세스를 실행하는 데까지 걸리는 시간을 dispatch latency라고 한다.

---

Preemptive vs Non-preemptive (선점 vs 비선점)

 

(Kernel로 넘어와서 I/O처리를 할 때는 상관이 없다, 프로세스 수행중에만)

P0라는 일을 열심히 하고있고 이 일이 끝나면 P1을 해야한다.

근데 P4이라는 중요한 일이 왔을때 뭐부터 할까?

 

Non-preemptive scheduling: 하던거 하고 다음 스케줄러에서 P4하자.

Preemptive scheduling: 우선순위가 높은 P4부터 하자.

 

현존하는 거의 대부분의 OS들은 Preemptive scheduling 방식을 채택하고 있다.

 

---

Scheduling criteria 스케줄링 기준

스케줄링을 할 때 고려되는 여러 기준들.

 

1. CPU utilization (CPU 사용률)

  CPU 사용률을 최대한으로 할 수 있는 접근으로 스케줄링함

2. Througtput (처리량)

  단위시간당 처리량을 의미함. 최대한 많이 하는게 좋다.

3. Turnaround time 

  특정 프로세스가 수행되고 끝날 때까지의 시간. 낮출수록 좋다.

4. Waiting time (대기 시간)

  waiting queue가 아니라 ready queue에서 running 이 되기 전까지 기다리는 시간. 낮출수록 좋다.

5. Response time

  사용자에게 보여지는 반응 시간. 낮출수록 좋다. 우선적으로 스케줄링 해줄수록 반응 시간도 짧아진다. 따라서 preemtive scheduling이 더 많이 쓰인다. 중요한 연산을 더 빨리 끝내니까.

 

Context switching 을 많이 할수록 CPU 사용률과 처리량은 떨어진다. 

Context switching의 주기가 짧을수록 시간을 낮추는 데에 유리하고, 주기가 길수록 사용률과 처리량을 늘리는 데에 유리하다. (Trade - off)

 

Scheduling Goals

스케줄링의 목표

 

All systems: 모든 시스템

 - Fairness: 공평하게 스케줄링하는 것이 가장 중요하다.

 - Balance: 시스템 전체가 바쁘게 움직이도록 한다.

 

Batch systems: CS개념도 없고 하나의 프로세스만 동작하는 시스템

 - Throughput

 - Turnaround time: 하드웨어 성능에 따라 갈림

 - CPU utilization: 사용률이 100%에 수렴하도록 한다.

 

Interactive systems: time sharing 되고, 멀티프로세스 되는 일반적인 시스템

 - Response time: 아주 중요. 사용자의 경험과 바로 직결됨.

 - Waiting time

 - Proportionality: Response time 추구하면 자연스럽게 달성됨

 

Real-time systems: 정해진 시간안에 요청을 처리하는 것이 realtime

 - Meeting deadlines: realtime이니까 기한 안에 일을 마쳐야 한다. 가장 중요

 - Predictability

 

Starvation(기아 상태): 피해야 할 것.

 여러 프로세스가 있는데, 스케줄러가 어떤 프로세스를 선정해주지 못하는 상태. Fairness가 보장될 수 있도록 알고리즘을 잘 짜야 이 현상을 최소화할 수 있다.

 

 

---

 

스케줄링 알고리즘

 

FCFS Scheduling (First Come, First Served)

먼저 온 프로세스를 먼저 처리하는 스케줄링 방식

non-preemptive

 

장점: Fairness의 보장이 잘 되기 때문에 starvation이 적다.

단점: Waiting time이 길어질 수 있다.

 

Conyou effect : 긴 시간을 소요하는 프로세스 뒤에 짧은 시간을 소요하는 프로세스가 있는 것.

 

긴 burst time을 가지는 프로세스가 앞에 있을수록 더 많은 waiting time이 발생함

이를 해결하기 위해서 Short-Job-First 방식이 있다.

 

Short-Job-First (SJF)

CPU burst time이 가장 짧은 프로세스부터 수행하는 스케줄링 방식

Preemptive, Non-preemptive

preemptive일 경우에는 Shortest Ramaining Time First(SRTF)라고 한다.

 

장점: Waiting time이 줄어든다.

단점: Starvation이 발생할 수 있다, CPU burst time을 예측할 확실한 알고리즘이 존재하지 않는다.

 

Priority Scheduling

우선순위를 구현을 하고, 우선순위가 높은 프로세스부터 수행하는 방식

Preemptive, Non-preemptive

Fairness가 보장되지 않기 때문에 FCFS 방식의 안티체제라고 볼 수 있음

 

장점: Flexible하다. 설계자가 우선순위를 구현하기 때문에, 특정 목적에 맞는 시스템에 알맞다.

단점: Fairness가 보장되지 못하므로 Starvation이 심하다. 우선순위가 낮은 프로세스는 실행되지 않을 수도 있다. 이를 방지하기 위해서 Aging기법을 사용한다. 

 

Aging: 기다리는 시간이 긴 프로세스들의 우선순위를 높여준다.

 

Round Robin Scheduling

프로세스들에게 우선순위를 부여하지 않고, 정해진 시간 동안 각자 일을 수행하는 스케줄링 방식을 Round Robin Scheduling이라고 한다.

 

이 때 프로세스에게 부여하는 CPU time을 time quantum(q) 라고 한다. 이는 프로세스가 한 번 스케줄링 될 때 주어지는 최대의 시간이다. 프로세스는 이보다 적은 시간을 쓸 수 있지만, 더 많이 쓸 수는 없다. (마감은 꼭 지키도록.)  time quantum이 지나면 timer interrupt가 걸려서 스케줄러가 동작한다. 테러리스트와 협상은 없다.

 

Time quantum이 길수록 오버헤드가 적고, 짧을 수록 오베헤드가 많아진다. 따라서 Time quantum을 줄이면 response는 잘 되지만, context switching이 늘어나게 되고 자연스럽게 오버헤드가 늘어난다 (Trade-off). 이 때 CPU 사용률과 처리율이 떨어지게 된다.  반대로 Time quantum이 무한대로 커진다면 FCFS와 동일하게 동작하게 된다. 이러면 의미가 없음. 따라서 적절하게 Time quantum을 만들어야하고, 이 때 SJF보다 평균 Turnaround time이 길지만 Response time이 짧아진다.

  

적절한 Time quantum을 설정하기 위해서, 일단 Time quantum은 문맥전환 시간보다 커야 한다. x86환경에서 주로 10ms ~ 100ms정도가 된다. A rule of thumb라는 이론이 있는데, CPU burst time의 80%를 time quantum으로 둘 때 가장 좋다는 이야기다.

 

---

Multilevel Queue Scheduling 다단계 큐 스케줄링

 

Queue를 따로 여러개로 나누고 앞서 배운 여러 스케줄링 알고리즘을 각각의 Queue의 특성에 맞게 섞어서 사용하는 스케줄링방식

 

크게 두 분류로 Foreground(interactive), Background(batch)의 구분이 있다. Foreground는 I/O bound 위주의 프로세스들, Background는 CPU-bound 위주 프로세스들로 구분된다. Foreground는 Response time이 중요하기 때문에 RR, Background는 FCFS 스케줄링 방식을 설정해서 수행함. 

 

이 때 foreground 큐와 background 큐 간의 스케줄링을 어떻게 하는가?

1. Fixed priority scheduling : 우선순위를 두고 스케줄링, 기아가 발생할 수 있음.

2. Time slice scheduling : 시간을 쪼개서 foreground가 쓰는 시간과 background가 쓰는 시간을 구분하는 스케줄링.

예를 들면 실시간 큐는 다른 큐들 보다도 더 높은 우선순위를 가질 것이다.

 

요약하면, 프로세스의 속성에 따라 여러 큐를 나눠 프로세스들을 수행하고 이 때 각 큐는 속성에 맞는 스케줄링 방식을 사용함. 각 큐는 우선순위를 두어 스케줄링하는 스케줄링 방식으로 보면 된다.

 

 

Multilevel Feedback Queue Scheduling 다단계 피드백 큐 스케줄링

 

기본적으로 Unix에서 제공하는 스케줄링 알고리즘

다단계 큐 스케줄링에서는 프로세스가 무조건 하나의  큐에 포함되지만, 다단계 피드백 큐 스케줄링에서는 프로세스가 여러 큐를 옮겨다닐 수 있다. CPU Burst time이 짧을 수록 높은 우선순위를 부여하고, 길수록 낮은 우선순위를 부여한다. 자연스럽게 상호작용 큐나 I/O Bound가 중요한 큐들이 높은 우선순위를 부여받는다. 

Time quantum 8만큼을 썼는데도 프로세스가 일을 완료하지 않으면 Time quantum이 16인 큐에 넣어주고, 여기서도 일을 완수하지 못하면 FCFS 큐에 넣어준다. FCFS 큐에서 프로세스가 끝내 수행되어 Terminated되거나 기아가 발생하지 않도록 오랜 시간동안 대기한 큐는 다시 위로 올려준다.

 

---

 

Multi-processor Scheduling 멀티프로세서 스케줄링

 

지금까지는 코어가 하나일 때만 다뤘다. 코어가 하나가 아니라 여러개일 경우 더욱 복잡해짐. 다중 프로세서 스케줄링이 필요해진다. 

 

Load balancing 부하 분산

SMP(Symmetric multiprocessing) 시스템에서 부하 분산을 통해 작업을 나눈다. 부하 분산은 프로세스들이 각자 고르게 작업하도록 작업을 분산해서 최대의 효율로 일할 수 있도록 한다. 다음 두 가지 팡법을 통해 부하를 분산한다.

 - Push migration: 여유가 없는 프로세서가 덜 바쁜 프로세서에게 작업을 밀어줌(Push).

 - Pull migration: 여유가 있는 프로세서가 바쁜 프로세스의 작업을 당겨옴(Pull).

 

Processor affinity

Soft vs Hard affinity

 - Soft: 하나의 레디 큐를 두고 이 레디 큐에서 코어를 하나하나 가져다가 쓰는 개념, 레드 큐가 하나로 통합되어 있어 구현이 쉬운 반면 Cache hitting rate이 떨어진다.

 - Hard: 각 코어마다 큐를 두어 수행하는 개념, 각각의 코어마다 큐를 따로 관리하니 스케줄링이 무겁다. 

 

 

 

Real-time Scheduling 실시간 스케줄링

 

Real-time에서 가장 중요한 것은 바로 Deadline.

 

Hard real-time systems: 정해진 시간(Deadline) 안에 해야 하는 일들을 반드시 처리해야 함.

Soft real-time systems: 정해진 시간에서 약간은 벗어나도 됨.

 

Periodic task in real-time systems : Real-time 시스템에서는 주기를 가지고 일을 수행한다.

 

Static vs Dynamic priority scheduling

 

Static

Rate-Monotonic algorithm: 주기가 짧은, 자주 실행되는 프로세스에게 우선순위를 주는 알고리즘.

 

Dynamic

EDF (Earliest Deadline First) algorithm: 데드라인이 적게 남은 프로세스에게 우선순위를 주는 알고리즘.