KOCW - 운영체제(이화여대 반효경 교수)
4장 CPU 스케줄링

CPU 스케줄링

스케줄링이 필요한 이유

CPU and I/O Bursts in Program Execution

• 프로세스는 CPU의 사용 + I/O 의 반복이다.

CPU-burst Time의 분포

• CPU를 짧게 쓰는 프로그램(I/O bound job) : CPU를 사용하는 중간에 I/O가 자주 발생하는 프로그램, 사람과 상호작용하는 프로그램이 다수

• CPU를 길게 쓰는 프로그램(CPU bound job) : CPU를 한 텀에 길게 사용하는 프로그램

어떤 프로그램한테 CPU를 할당하면 좋을까?

-> I/O bound job 이다. 사람과 상호작용하는 프로그램이기 때문에, 빠른 응답시간을 제공하기위해서 먼저 CPU를 할당해야한다.

프로세스의 특성 분류

1. I/O-bound process : I/O 위주의 job

2. CPU-bound process : 계산 위주의 job

프로세스는 특성에 따라 두 가지 분류로 나뉘고, 섞여서 실행되기 때문에 CPU에 어떤 프로그램을 할당할지에 대한 스케줄링이 필요해지는 것이다.

CPU scheduler & Dispatcher

스케줄러와 디스패쳐 모두 각 기능(스케줄러는 CPU 할당 결정, 디스패쳐는 그 결정을 CPU를 넘기는 역할)을 수행하는 코드를 말한다.

CPU Scheduler

• Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

Dispatcher

• CPU의 제어권을 스케줄러의 결정에 따라 프로세스에 넘겨주는 역할
• 이 과정에서 문맥교환(context switch)이 발생한다.

CPU 스케줄링이 필요한 경우

CPU 스케줄링은, 프로세스에게 다음과 같은 상태변화가 있을 경우 필요해진다.

1. Running -> Blocked (예 : I/O 요청 시스템 콜)

2. Running -> Ready (예 : 할당시간 만료로 timer interrupt)

3. Blocked -> Ready (예 : I/O 완료후 인터럽트)

4. Terminate (프로세스 종료)

❗ 1, 4번의 경우에 필요한 스케줄링은 nonpreemptive(프로세스가 CPU 자진 반납)한 경우이고, 이외의 다른 모든 경우에서는 preempotive(프로세스에게서 CPU 강제로 가져옴)한 경우이다.

CPU 성능 척도

어떤 알고리즘의 CPU 스케줄링이 어떤 식으로 좋은지에 대한 판단 척도

1. CPU utilization (이용률) : 전체 시간 중에서 CPU가 일한 시간의 비율

2. Throughput (처리량) : 단위 시간당 처리량(CPU가 얼마나 많은 일을 했느냐)

3. Turnaround time(소요시간, 반환시간) : 대기시간 + CPU 사용 시간 (I/O 시스템콜 전까지)

4. Waiting time(대기 시간) : Ready queue에서 프로세스가 대기한 시간의 총합

5. Response time(응답 시간) : 프로세스 I/O를 완료하고 처음으로 CPU를 얻기까지 걸린 시간

• 1, 2는 많(높)을수록, 3, 4, 5는 짧을수록 성능이 좋은 것으로 판단할 수 있다.

🚥 CPU Scheduling Algorithm

FCFS(First-Come First-Served)

• 프로세스의 도착 순서대로 CPU를 할당

• Convoy effect(호위 효과) 발생 가능 : short process behind long process, Burst time이 긴 프로세스가 자리를 차지하고 있을 때, 뒤에 있는 프로세스들의 대기 시간이 길어지는 현상

SJF(Shortest-Job-First)

• Burst time이 짧은 프로세스부터 CPU를 할당

1. Nonpreemptive version : CPU를 할당 받으면 Burst가 완료될때까지 CPU를 뺏기지 않음

2. Preemptive version : 현재 남은 burst time보다 더 짧은 CPU burst time을 가지는 프로세스가 도착하면 CPU를 빼앗김(SRTF라고도 부름)

• SJF의 문제점
  • Starvation 현상 발생 : burst time이 긴 프로세스는 영원히 CPU를 못쓰게 될 수도 있음
  • CPU Burst time을 정확하게 알 수가 없음 : CPU를 할당 받아도 I/O Burst로 인해 CPU를 뱉어낸다거나 변수가 발생할 수 있음

다음 CPU Burst Time의 예측

추정(estimate)만이 가능하다

• 과거의 CPU burst time을 이용해서 추정한다(exponential averaging). -> 과거 N번의 CPU burst 값(현재에 가까워질수록 더 가중치를 둬서 반영)과 최초 예측 값을 가중치를 둬서 더하여 추정

Priority Scheduling

우선순위가 높은 프로세스에게 CPU를 할당(SJF는 일종의 Priority scheduling)

• highest priority를 가진 프로세스에게 CPU 할당

• Preemptive의 경우 우선순위가 더 높은 프로세스가 오면 남은 bursttime에 상관없이 할당

• nonpreemptive현재 할당된 프로세스가 끝날때까지 CPU 할당

• SJF와 마찬가지로 Starvation 발생 가능

❗ Starvation의 해결책

• Aging : 오래 기다릴수록 프로세스의 우선순위를 높여준다(경로우대)

Round Robin(RR)

❗ 현재 가장 많이 사용하는 CPU스케줄링의 근간이 되는 알고리즘

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐

• 할당 시간이 끝나면프로세스는 선점(preempted)당하고 ready queue에 다시 line up

사용하는 이유

• Response time(응답시간)이 짧아짐

• 각 프로세스의 Burst Time이 제각각(짧은 job, 긴 job)이기 때문에 RR이 효율적일 수 있다.

할당 시간은 어느 정도로 하는게 좋을까?

• q(할당 시간)가 너무 작을 경우 : 문맥 교환 오버헤드가 커진다.

• q가 너무 클 경우(FCFS)

Multilevle Queue

• Ready queue를 여러 개로 분할(CPU는 하나, 여러 줄로 줄서기), queue가 여러 개이기 때문에 각각 스케줄링하는 알고리즘이 필요하다.

  	* foreground(interactive) - RR 사용

  • background(batch - no human interaction, long job) - FCFS(long job이기 때문에)

• Fixed priority scheduling : 모든 foreground queue가 처리된 다음에 background queue를 처리, background queue에 대해서 Starvation의 가능성 있음

• Time slice : 각 큐에 CPU time을 적절한 비율로 할당 (interactive한 job들에게 더 많이 할당)

Multilevel queue의 우선순위

1. system processes : 시스템과 관련된 프로세스로 매우 중요함

2. interactive processes : 사람과 상호작용하는 프로세스들

3. interactive editing processes

4. batch processes : CPU만 많이 쓰는 프로세스들

5. student processes

Multilevel Feedback Queue

특징

• queue의 개수를 여러개 둘 수 있다.

• 각각의 queue마다 서로 다른 알고리즘을 둘 수 있다.

• 큐의 상위 큐 승격/하위 큐 강등에 관련된 기준이 있다.
  

• 예시

  * 아래 그림의 경우에는 가장 상위 큐에서 할당시간 8의 RR 알고리즘을 가진 큐에서 CPU를 할당 받고, 해당 프로세스가 CPU를 더 사용해야 할 경우에는 하위 큐에 있는 할당시간 16인 RR, 더 사용해야하면 FCFS를 사용하는 가장 밑에 있는 큐에서 CPU를 할당받는다

  

Multiple-Processor Scheduling

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

예외적인 상황으로 크게 다룰 일은 없을 것

• 상황 예시 : 은행, 공중화장실(칸이 여러개)

Homogeneous processor

• 특별한 제약조건이 없는 경우 - queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 한다.

• 특별한 제약조건이 있는 경우 - 반드시 특정 프로세서에서 수행되어야 하는 경우(ex_미용실)
  

Load sharing

한 줄 서기 vs 여러 줄 서기

• 한 CPU에 몰릴 수 있는 문제 발생 가능 -> 특정 프로세서에 job이 몰리지 않게 하는 공유 메커니즘 필요

Symmetric Multiprocessing (SMP), Asymmetric multiprocessing

• Symmetric Multiprocessing : 각 프로세서가 알아서 스케줄링(균일한 작업을 여러 군데서 할 경우 등)

• Asymmetric multiprocessing : 한 CPU가 대장 CPU가 되어 결정을 내리고 나머지 CPU는 이 결정에 따르도록 하는 것

Real-Time Scheduling

한 프로세스에 DEADLINE이 존재하는 스케줄링

❗ DEADLINE을 만족하도록 스케줄링 해야함

1. Hard real-time systems : Hard real-time task를 DEADLINE 안에 반드시 끝내도록 스케줄링

• 온라인으로 상황에 맞게 스케줄링 하는 경우보다, 오프라인으로 미리 스케줄링을 설계해놓는 경우가 많음(온라인의 경우 프로세스가 도착했을 때의 상황에 맞춰서 스케줄링에 변화가 생김, 즉 미래에 대한 정보가 없기 때문에 상황에 마주처서 스케줄링을 하는 것)

2. Soft real-time computing : soft real-time task에게 DEADLINE을 어겨도 큰 위험은 없지만 높은 우선도를 갖도록 스케줄링 해야함 (ex 동영상 재생, 동영상의 초당 기준 프레임을 유지하고 화면에 내보내기 위해 항상 CPU가 일을 해줘야함)

Thread Scheduling

1. Local Scheduling

• 사용자 프로세스 내부에 있는 스레드를 스케줄링 하는 것으로 운영체제는 이 스레드의 존재 유무를 인지하지 못하기 때문에 이 스레드를 가지고 있는 프로세스가 CPU를 받고나서 어떤 스레드에게 CPU를 할당할지 내부적으로 스케줄링

2. Global Scheduling

• Kernel levle thread는 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 스케줄링(운영체제가 존재를 알고 있는 스레드)

📝 Algorithm Evaluation

Queueing models

❓ Queueing model? : 어떤 요청이 큐에 들어와있다가 서버에 들어가고 빠져나가는 모델(아래 그림 참고)

• 알고리즘 평가시에 server 부분을 CPU로 이해하면 된다.

용어
arrival rate : 도착률(얼마나 빠른 빈도로 요청이 도착하는지)
service rate : 처리율(CPU의 역량, 단위시간당 처리량)

위 값들은 확률분포로 주어짐

Implementation(구현) & Measurement(성능 측정)

• 실제 시스템에 알고리즘 구현 -> 실제 작업에 대해서 성능 측정

Simulation(모의 실험)

• trace를 입력하여 모의 프로그램에서 결과 비교