[운영체제] 02. scheduling

여러 개의 프로세스가 대기 상태에 있을 때, 다음에 실행할 프로세스를 스케줄러가 선택하는데

이때 스케줄러의 알고리즘을 스케줄링(scheduling)이라고 한다.

CPU 사용 시간에 따른 스케줄링 알고리즘이 필요하다.

 

process behavior

(a) CPU-bound process: CPU burst가 길다

(b) I/0-bound process: CPU burst가 짧다. I/0를 기다리는 시간이 빈번하게 발생

 

When to schedule

1. 새로운 프로세스를 생성할 때
2. 프로세스를 종료할 때
3. 프로세스가 블록 상태가 되어 대기해야 할 때
4. I/O interrupt 가 발생했을 때

 

clock interrupt를 다루는 방식에 따라 두 가지로 나뉨

1. nonpreemptive(비선점): 자발적으로 CPU를 반환할 때까지 계속 수행, 강제로 중단 불가능
2. preemptive(선점): 프로세스를 선택하고 최대 시간을 넘지 않는 범위에서 실행, 높은 우선순위가 나타나면 switching이 일어남

 

Categories of Scheduling Algorithms

→fairness(공정성), policy enforcement(정책대로 수행), balance(효율적인 사용)

 

1. Batch 

Nonpreemptive or preemptive with long time

reduce process switches and improve performance

→throughput(처리율 최대화), turnaround time(실행부터 종료까지의 시간 최소화), CPU utilization(CPU 최대 활용)

 

2. Interactive 

preemptive 

process하나가 CPU를 오래 독식하는 것을 막음

→response time(빠른 응답), proportionality

 

3. Real time

preemption is not needed

→meeting deadlines, predictability

 

---

Scheduling in Batch Systems

 

1. First-Come First-Served (FCFS)

먼저 온 작업을 먼저 수행

nonpreemptive

아주 간단한 방법

→ 긴 작업이 짧은 작업을 지연시킬 수 있음, 우선순위가 반영 안 됨, 비선점형 방식으로 비효율적인 cpu사용

 

2. Shortest Job First

수행시간이 빠른 작업부터 먼저 수행

nonpreemptive

각 프로세스의 실행 시간을 알고있을때 사용

모든 job들이 동시에 도착했을때 최적의 결과를 냄

 

⭐️average turnaroundtime 구하는 방법 중요함

 

3. Shortest Remaining Time Next

남은 실행 시간이 제일 짧은 작업부터 먼저 수행

preemptive version of shortest job first

 

---

Scheduling in Interactive Systems

 

1. Round Robin Scheduling

순차적으로 돌아가면서 실행

각 프로세스에게 시간할당량 (time quantum)이라 불리는 시간 주기가 할당되며 한 번에 이 시간 동안만큼만 실행됨

quantam의 길이

너무 짧으면- process switching이 자주 발생하고 CPU의 효율성이 낮아짐 (lowers the CPU effciency)

너무 길면- 늦은 응답(poor response)

 

2. Priority Scheduling

우선순위 스케줄링

각 프로세스에게 우선순위가 할당되며 가장 높은 우선순위를 가진 실행 가능한 프로세스가 다음에 수행됨

같은 우선순위에 있는 프로세스는 라운드 로빈 형태로 한 번씩 할당 시간 동안 실행되며 낮은 우선순위 클래스로부터 방해받지 않음

→낮은 우선순위 클래스는 기아 상태 발생 우려

 

(높은 우선순위의 프로세스가 무한히 실행되는 것을 막기 위해 스케줄러는 클록 인터럽트마다 현재 실행 중인 프로세스의 우선순위를 낮출 수 있음)

각 프로세스는 최대로 실행할 수 있는 할당 시간을 가짐

 

priority assignment

-static(정적): user의 권한과 실행시간에 따라 결정

-dynamic(동적): giving good service to I/O bound process

우선순위는 1/f 로 할당 (f: 프로세스가 사용하고 남은 할당 시간 비율)

 

3. Multiple Queues

CTSS

1. CPU-bound process에게 큰 값을 주어야 더 효율적이구나 깨달음
2. 그러나 너무 큰 시간을 할당하면 poor response
3. 우선순위 클래스들을 설정함

가장 높은 우선 순위 클래스에게 1 quantum, 다음 우선순위 클래스에게 2 quantum, 다음에는 4 quantum

(프로세스가 할당된 시간을 모두 소비하면 한 단계 낮은 클래스로 이동

 

XDS 940

네 개의 우선순위 클래스: 터미널, I/O, 짧은 시간 할당, 긴 할당 시간

 

4. Shortest Process Next

예상 실행 시간이 가장 짧은 프로세스를 실행하는 것

 

-Aging기법

estimate: aT0 + (1-a) T1

(T0: 예상시간, T1: 측정된 다음 실행 시간)

 

5. Guaranteed Scheduling

n개의 프로세스가 실행 중 일 때, 각 프로세스는 1/n만큼의 CPU사용을 보장받음

각 프로세스가 생성된 이후 얼마나 많은 CPU시간을 받았는지 추적해야 함

주어진 시간에 비해 적게 사용한 작업부터 실행

 

6. Lottery Scheduling

 

스케줄링 결정을 내릴 때마다 무작위로 복권 티켓을 선택하고, 이 티켓을 가진 프로세스가 자원을 할당받음

f 비율의 티켓을 가지면 f 비율만큼 자원을 받게 됨

협동하는 프로세스들이 원할 경우 티켓을 교환 가능

 

7. Fair-Share Scheduling

스케줄링하기 전에 프로세스의 소유자를 고려

각 사용자는 CPU시간의 일정 비율을 할당받으며 스케줄러는 이 비율이 지켜지도록 프로세스를 선택

 

---

Scheduling in real-time systems

시간이 핵심 역할을 수행, 컴퓨터는 고정된 시간(deadline) 안에 적절하게 반응해야 함

 

-hard real-time: deadline 지켜야 함, soft real-time: 간헐적으로 지키지 못해도 괜찮음

-periodic: 일정한 주기로 규칙적으로 실행, aperiodic: 예측 불가

-static, dynamic

 

⭐️schedulable(스케줄가능)

m개의 이벤트가 존재할 때 각 이벤트 i는 Pi의 주기로 발생하고 이 이벤트 처리에 Ci초의 CPU 시간이 필요하다면 시스템의 부하가 다음과 같을 때만 처리가능

 

---

Policy vs Mechanism

정책이 결정되면 그에 맞는 메커니즘이 필요함

policy(정책): 시스템의 목표

mechanism(메커니즘): 정책을 실행하는 방법

 

Thread Scheduling

user level

한 프로세스 내에서만 스레드가 스케줄링됨, 전환 속도가 매우 빠르지만 한 프로세스가 차단되면 해당 프로세스 내 모든 스레드가 차단됨

kernel level

프로세스 간의 스레드들이 스케줄링, 특정 스레드가 차단되어도 다른 스레드는 계속 실행됨