[OS] 4장. CPU 스케줄링

[수업출처] 숙명여자대학교 소프트웨어학부 김주균 교수님 운영체제 수업 & [OS? Oh Yes!] 

 

1. (CPU) 스케줄링

- 시분할 시스템에서 현제 프로세스로부터 다른 프로세스로 CPU를 넘겨주어야 할 때, 기다리는 프로세스들 중에 어떤 프로세스를 선택해야할 지에 대한 방식이나 기준

 

- 수행 단계에 따라 장기, 중기, 단기 스케줄링

- 장기

    - 어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가 결정

    - 작업 스케줄링

    - 일괄처리) 작업: 디스크 → 일괄처리 큐 대기 → 장기 스케줄러 → 프로세스

    - 시분할) 사용자의 접속 시도를 허용할지 말지 결정하는 단계

    - 요청된 일을 프로세스로 만들어 시스템에 알려진 일거리로 추가하느냐 결정 → 다중 프로그래밍 정도 조절

    - 수행 횟수 적음, 대부분 FIFO 방식

 

- 중기

    - 보류 상태의 프로세스 중에서 어느 프로세스에 메모리를 할당할 것인지 결정

    - Swap In (or Resume)

 

- 단기

    - 준비 상태의 프로세스 중에서 어느 프로세스에 CPU를 할당할 것인지 결정

    - 프로세스 스케줄러 (디스패처)라 불리는 것에 의해 수행

    - 입출력, 시간 종료 인터럽트, 시스템 콜 등과 같은 다양한 이유에 의해 가동

    - 자주 수행됨 → 실행 시간 줄여야 함

 

2. 스케줄링의 목적과 기준

1) 목적

- 사용자 관점

    - 응답시간: 프로세스 요청에 의해 시스템이 최초로 출력을 내주기 시작할 때까지 걸린 시간 → 대화형 시스템

    - 반환시간: 요청으로부터 결과를 돌려받는 데까지 걸린 시간 (일괄처리)

    - 예측가능성: 요청한 일이 얼마 후쯤에는 완료될 수 있을 것이라는 예측

 

- 시스템 관점

    - 처리량: 단위 시간에 완료된 프로세스의 개수 → 일괄처리 시스템

    - 활용도: 주어진 시간동안 특정 자원이 실제로 가동된 시간의 비율

 

- 가능한 한 CPU 시간을 공평하게 나누어 주어야 함 (공평성)

- 특정 프로세스가 장기간 CPU를 받지 못하게 되는 경우 최대한 피해야 함

- 시스템에 있는 여러 자원들은 가급적 균형있게 사용되어야 함

 

- 빠른 응답시간을 주기 위해 스케줄링을 자주 한다면 문맥교환이 자주 일어나게 되고, 이것은 CPU 시간의 상당 부분이 문맥교환에 사용된다는 것을 의미 → 사용자 프로세스를 실행할 시간이 줄어 전체적으로는 처리량 감소

- 주어진 기간 동안에 많은 프로세스 처리하여 처리량을 높이려고 수행 시간이 짧은 프로세스들 주로 처리 → 수행시간이 긴 프로세스는 처리가 늦어져 응답시간이 길어짐

 

2) 고려해야 할 기준들

- 프로세스의 성격

    - CPU를 사용하는 연산이 입출력에 비해 상대적으로 많은 것: 연산 위주 프로세스 (CPU-bound)

    - 입출력이 상대적으로 많은 것: 입출력 위주 프로세스 (I/O-bound)

    - 목적에 따라 어떤 종류의 프로세스 우대할지 생각

 

- 시스템이 사용될 환경

    - 응답시간을 우선으로 할지, 처리량을 우선으로 할지

    - 특정 프로세스에게 우선적으로 빠른 응답시간을 보장해야 하는 경우 → 가능케 하는 기능 필요

    - 프로세스 크고 작음에 따라 어떤 것을 우선적으로 처리할 지 기준 필요 (CPU 요구량 & 메모리 요구량)

 

3. 스케줄링 기법들

[스케줄링이 가동되어야 할 때]

- 실행 상태에서 대기 상태로 전환될 때 (ex 입출력)

- 실행 상태에서 준비 상태로 전환될 때 (ex 시간 종료 인터럽트)

- 대기 상태에서 준비 상태로 전환될 때 (ex 입출력 종료)

- 프로세스 수행 종료

 

- 비선점 스케줄링: 프로세스가 CPU를 스스로 반납할 때까지 계속 사용

- 선점 스케줄링: 실행 중인 프로세스로부터 CPU를 빼앗아 다른 프로세스에 할당 가능

 

- 위의 4가지 경우 중 1번과 4번의 경우에만 스케줄링을 하게 되면 비선점 방식이 되고, 

- 2번과 3번에도 적용되는 스케줄링을 선점 방식이라 함

 

- Average Waiting Time 평균 대기 시간: 준비 큐에 도착한 후 실행될 때까지 걸린 시간, 사용자 만족도의 기준

 

1) FCFS (First Come First Service = FIFO) 스케줄링 

- 준비 큐에 먼저 도착한 프로세스에게 먼저 CPU 할당

- 비선점 방식

- 프로세스가 CPU를 독점하여 사용하기 때문에 아주 긴 프로세스가 실행될 경우 평균 응답시간이 길어짐

- 대화형 시스템에 적합하지 않음

- 프로세스들의 개수와 크기를 짐작할 수 있다면 각각의 프로세스들이 언제쯤 실행될 지 예측 가능, 공평함

- 실제 시스템에서 바로 사용되기는 어렵지만, 다른 스케줄링 기법의 보조 장치로서 활용 가능

 

- ex

프로세스	도착 시간	CPU 요구량 (초)
P1	0	100
P2	0	10
P3	0	10
P4	0	10

- P1, P2, P3, P4의 순서로 거의 동시에 도착했을 때

- 평균 응답시간 = (100 + 110 + 120 + 130) / 4 = 115

- 평균 대기시간 = (0 + 100 + 110 + 120) / 4 = 82.5

 

- P2, P3, P4, P1의 순서로 거의 동시에 도착했을 때

- 평균 응답시간 = (10 + 20 + 30 + 130) / 4 = 47.5

- 평균 대기시간 = (0 + 10 + 20 + 30) / 4 = 15

 

2) SPN (Shortest Process Next) 스케줄링

- 준비 큐에 있는 프로세스들 중 가장 짧은 프로세스 (CPU 요구량이 가장 적은)를 먼저 실행

- 비선점 방식

- 평균 응답시간을 최소화할 수 있지만, 실행시간이 긴 프로세스가 CPU를 할당받지 못하고 계속 대기하는 무한 대기 현상 발생

    - 긴 프로세스일수록 그 편차가 커져 예측가능성은 감소할 것

    - 무한 대기 가능성을 낮추는 방법으로는 기다린 시간만큼 우선순위를 높여 실행가능성을 높여주는 것이 있음 (Aging)

- 각 프로세스들의 크기를 실행 전에는 정확히 알 수 없음에도 그 크기를 가지고 스케줄을 해야한다는 단점

    - 해결책: 프로세스의 크기를 실행 전에 추정해보는 지수 평균 방법 (Exponential Averaging)

    - 이전에 실행되었을 때의 크기와 그때의 추정 크기로 지금 실행되어질 크기 짐작

    - 이전 단계의 실제 크기 → 다음 추정 크기

    - 추정 크기와 실제 크기의 가중치를 각각 0.5로 설정하고, 추정크기를 a, 실제크기를 b라 했을 때

    - 실제1 = 추정2 = 0.5a + 0.5b

    - 실제2 = 추정3 = 0.5(0.5a + 0.5b) + 0.5b ...

 

- ex)

프로세스	도착 시간	CPU 요구량 (초)
P1	0	10
P2	0.5	5
P3	1	2

- 평균 응답시간 = (10 + 16.5 + 11) / 3 = 12.5

- 평균 대기시간 = (0 + 11.5 + 9) / 3 = 6.84

 

3) SRT(Shortest Remaining Time) 스케줄링

- SPN을 선점 방식으로 운영하는 것

- 새로 도착하는 프로세스의 실행시간 크기는 완료까지 남은 시간과 같으며, CPU를 할당받아 실행된 양만큼 남은 시간은 줄어들 것

- 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행시켜 주는 방식

- 실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우 현재 실행 중인 것을 중단하고 새 프로세스에 CPU 할당

- 완료까지 남은 실행시간의 계산, 잦은 문맥교환의 부담 존재

- 반환시간을 기준으로 했을 때 SPN보다 우수

 

- 위의 예제에 대입해보면

- P1 (0.5s) → P2 (0.5) → P3 (2) → P2 (4.5) → P1 (9.5) 의 순서로 CPU가 할당됨

- 평균 응답시간 = (17 + 7 + 2) / 3 = 8.67

- 평균 대기시간 = (7 + 2 + 0) / 3 = 3

 

- 이때 실제로는 SPN보다 더 많은 문맥교환이 요구되어 평균 응답시간이 조금 더 길어질 것임을 예상할 수 있음

- 만약 가까운 미래에 도착하게 될 프로세스의 정보를 알 수 있다면, 위의 예제에서 1초 뒤에 P3가 들어올 것을 알 수 있다면 P1을 할당하는 대신 1초를 기다렸다가 SPN을 적용하여 평균 응답시간을 줄일 수 있음 

→ 반복적인 시스템에서는 사용할 수 있겠지만 사실 어려움. idea 차원의 개념. Future-knowledge 스케줄링

 

- 잦은 문맥교환을 줄이는 방법

- SRT 스케줄링을 위한 임계값을 정해두고 두 프로세스의 남은 시간 차이가 임계값을 넘지 않을 경우에는 다음 프로세스의 실행시간이 더 짧더라도 선점되지 않도록 함

 

4) HRRN (Highest Response Ratio Next) 스케줄링

- 수행시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법

- 준비 큐에 있는 프로세스들 중에서 응답률이 가장 높은 우선순위를 줌

- 비선점 방식

- 응답률 = (대기시간 + CPU 요구량) / CPU 요구량

- 프로세스가 기다리는 시간이 길어질수록 우선순위가 높아지므로 곧 CPU 할당받을 수 있음

 

5) 라운드 로빈 (Round-Robin) 스케줄링

- FCFS 스케줄링을 기반으로 하여 CPU를 할당히되, 각 프로세스는 시간 할당량이 지나면 시간 종료 인터럽트에 의해 CPU 뺏기는 방식

- 선점 방식

- CPU를 반환한 프로세스는 다시 준비 큐의 끝에 들어가게 되고, 준비 큐의 맨 앞에 있는 프로세스가 CPU 선점

 

- ex)

프로세스	CPU 요구량 (ms)
P1	30
P2	8
P3	15
P4	10

- 위 프로세스들이 거의 동시에 도착했고, 시간 할당량이 10ms 일 때

- P1 (10) → P2 (8) → P3 (10) → P4 (10) → P1 (10) → P3 (5) → P1 (10) 순서로 CPU 할당 받음

- 평균 응답시간 = (63 + 18 + 53 + 38) / 4 = 43

- 평균 대기시간 = (33 + 10 + 38 + 28) / 4 = 27.25

 

- 한 프로세스가 CPU를 독점하는 단점을 방지할 수 있지만, CPU 선점에 따른 문맥교환의 오버헤드 감수해야 함

- 오버헤드: 문맥교환에 필요한 시간, 메모리 등

- 오버헤드에도 불구하고 이 기법은 대화식 시스템이나 시분할 시스템에 적합한 방식으로 알려져 있음

- 시간 할당량의 크기에 따라 시스템의 성능이 크게 달라질 수 있음

- 시간 할당량이 매우 크면 FCFS 방식과 같아지게 되며, 작을수록 문맥교환이 자주 발생하므로 문맥교환의 오버헤드가 커짐

- 일반적으로 시간 할당량은 10~100ms가 적당

 

- 연산 위주의 프로세스가 입출력 위주의 프로세스보다 우대받고 있음

- 입출력 위주 프로세스는 대부분 시간 할당량을 남긴 채 입출력을 발생시킨 다음 입출력이 완료되면 당시 남겨진 시간 할당량을 보상받지 못한 채 큐의 맨 뒤로 들어감 

→ 입출력을 마친 프로세스가 들어가는 준비 큐를 따로 하나 두고 우선순위는 더 높게 하되, 이 큐에서 CPU를 받을 때에는 이전 입출력을 발생시켰을 때 남긴 시간 할당량만큼만 주도록 하는 방식이 있음 : 가상 라운드 로빈 방식

 

- 프로세스가 생성될 때 부여된 우선순위가 완료 때까지 변하지 않는 값 → 정적 우선순위

- 시스템에 있는 동안 조정되도록 → 동적 우선순위

 

6) 다단계 큐 (Multi-level Queue) 스케줄링

- 정적 우선순위를 사용하는 선점 방식

- 우선순위의 개수만큼 큐 필요 → 같은 우선순위를 가지는 프로세스끼리 큐에 들어감

- 큐들 간에 프로세스 이동 불가능

- 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU 뺏김

 

7) 다단계 피드백 큐 (MFQ, Multi-level, Feedback Queue)

- 프로세스들의 CPU 요구량을 몰라도 짧은 프로세스들에게 유리하면서 입출력 프로세스를 우대할 수 있는 기법

- 입출력 프로세스 우대 → 짧은 연산 후 입출력 발생하면 CPU는 다른 프로세스에게 주어지고 입출력 작업과 병행되어 시스템 성능 향상

- 동적 우선순위를 기반으로 하는 선점 방식

 

- 우선순위 개수만큼 큐가 있으며 각 단계마다 서로 다른 CPU 시간 할당량을 가지도록 함

- 우선순위가 높은 단계의 큐일수록 시간 할당량 작도록 함

- 새로운 프로세스는 최상위 단계의 준비 큐에 들어간 후 FCFS의 순서로 CPU를 할당받아 실행되다가 그 큐의 시간 할당량이 끝나면 한 단계 아래의 준비 큐에 들어감으로써 우선순위가 한 단계 낮아짐

- 각 단계에서도 그 단계 큐의 시간 할당량을 다 사용할 때까지 계속 실행된다면 다음 단계의 큐로 들어감

- 마지막 단계에서는 라운드 로빈 방식으로 실행 (시간 할당량이 지나면 다음 프로세스에게 CPU 할당, 준비 큐 맨 뒤로 들어감)

 

- 어떤 단계에서든 시간 할당량이 끝나기 전에 입출력 등으로 CPU를 내놓게 되면 다시 준비 상태가 되었을 때 한 단계 위의 큐에 들어가도록 함으로써 우선순위를 높여줌

 

- 중간 단계의 맨 앞에 있는 프로세스는 상위 단계의 큐들이 비어있는 경우에만 CPU를 받을 수 있고, 시간 종료 인터럽트에 의해 선점되거나 입출력이 발생하지 않는 한 그 큐의 시간 할당량까지 쓸 수 있음

- 일단 CPU를 받은 프로세스는 실행 중 상위 단계의 프로세스에 의해 선점되지 않고 부여받은 시간 할당량까지는 보장됨

 

- 상대적으로 짧은 프로세스들이 하위 큐까지 내려가지 않도록함으로써 비교적 높은 우선순위를 유지할 수 있도록 함

- 입출력은 우선순위의 상향조정으로 이어져 우대받음을 알 수 있음

- Behavior Adaptive 스케줄링

 

- 변형)

- 각 단계에서 시간 할당량을 다 쓸 경우 그 단계의 큐에서 몇 번의 순환 후 다음 단계로 떨어뜨림

- 입출력의 완료 시 단계의 상승 폭을 더 크게 줌 

- 현재 큐에서 대기한 시간이 일정 시간을 넘기면 상위 큐로 이동시켜 줌

 

8) Fair-share 스케줄링

- 프로세스들의 특성이나 중요도에 따라 몇 개의 그룹으로 나누고, 각 그룹에 할애된 일정량의 CPU 시간은 그 그룹에만 영향을 미치도록 함

- ex)

- 1(A B) 2(C D) 3(E F)

- 1그룹에는 CPU 시간의 50%, 2그룹과 3그룹에는 각 25% 할당

- ACBEADBF의 순서대로 스케줄을 하거나, A에게 많은 시간을 주어야 할 경우 B를 줄이고 A를 늘리는 등 타 그룹에는 영향이 가지 않도록

 

4. 실시간 Realtime 스케줄링

- 실시간 시스템: 실행될 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템

- 경성 실시간 시스템

    - 작업이 마감시한 내에 완료되지 않으면 치명적인 결과를 초래하는 시스템 (시스템이 중지되는 등) 

    - 마감시한을 넘긴 후 완료되는 일은 아무 가치가 없음

    - 일반적으로 실시간 시스템은 경성 실시간 시스템을 말함

- 연성 실시간 시스템

    - 작업이 마감시한 내에 종료되지 않으면 데이터의 손실 등 피해가 발생하지만 시스템은 계속 운영 가능한 시스템

    - 마감시한을 넘긴 후부터는 완료의 가치가 점점 떨어짐

 

- 정적인 방법:  프로세스들의 특징과 개수를 알 수 있는 경우에 유용

- 동적인 방법: 프로세스의 생성 시간이나 특성을 알 수 없는 경우에 사용

- 실시간으로 운영되는 환경은 대부분 특수한 상황으로, 실행되어야 할 일들의 성격이나 개수를 사전에 알 수 있는 경우가 많음

 

1) RM (Rate Monotonic) 알고리즘

- 대표적인 정적 스케줄링 방식

- 크기와 개수가 알려진 프로세스들이 각자 주기적으로 발생되는 환경에서 사용

- 프로세스는 서로 독립적이고 주기적으로 수행되는 환경에서 각 프로세스의 마감시한은 각자의 주기와 같다고 가정

- 주기가 짧을수록 높은 우선순위 받음

- 낮은 우선순위의 프로세스가 더 높은 우선순위의 프로세스가 도착할 경우 CPU를 뺏기는 선점 방식

- 정적 환경에서 최적의 기법으로 알려져 있음

 

- n개로 구성된 프로세스 집합이 있을 때, 이 프로세스들에 의한 CPU 사용률 U는 아래와 같음

- U = U1 + U2 + ... Un = C1/P1 + C2/P2 + ... + Cn/Pn ≤ n(2^(1/n) - 1)

- 이 식이 만족되면 RM 기법으로 모든 프로세스의 마감시한을 맞출 수 있는 스케줄링이 가능하다는 것이 알려져 있음

- 1보다 작거나 같을 경우 될 수도 있고 안될 수도 있으며, 1보다 큰 경우엔 불가능함

- P는 주기, D는 마감시한, C는 크기(수행시간)

 

- 스케줄링 비용이 적게 드는 대신, 새로운 프로세스가 추가되는 환경에 바로 적응하지 못하고 전체 스케줄링을 다시 해야하는 단점

 

- ex) 

	주기	크기
T1	3	2
T2	6	2

- T1의 주기가 짧으므로 먼저 시작

- T1 (2) → T2 (1) // 3 → T1 (2) → T2 (1) // 6

- T1과 T2 모두 주기 내에서 일이 완료되었기 때문에 성공

- U = 2/3 + 2/6 = 1

 

2) EDF (Earliest Deadline First) 알고리즘

- 프로세스 마감시한이 가까울수록 우선순위 높게 부여하는 선점 방식의 동적 스케줄링

- 동적: 새로운 프로세스가 도착할 때 바로 대응할 수 있음

- 우선순위에 의해 실행 중 CPU 뺏길 수 있음

- 한 프로세스의 실행이 완료될 경우 마감시한이 가장 가까운 것을 찾아 스케줄

- 모든 프로세스가 주기적일 필요는 없으며, 주기가 있을 경우에는 마감시한을 주기로, 그렇지 않을 경우는 마감시한이 알려져야 함

 

- n개의 프로세스가 있을 때 아래와 같은 조건이 성립한다면 EDF 기법으로 가능한 스케줄이 존재

- C1/P1 + C2/P2 + ... + Cn/Pn ≤ 1

 

- 새로운 프로세스의 동적인 수용이 허용되나, 그럴 때마다 가능한 스케줄을 찾기 위한 계산을 해야하는 부담 존재

 

- ex)

프로세스	도착시간	CPU 요구량 (크기)	마감 시간
P1	0	8	25
P2	4	3	10
P3	5	10	20

- P1 (4) → P2 (3) → P3 (10) → P1 (4) //21

- P1이 수행되다가 4초 후에 마감 시간이 더 짧은 P2가 들어오면 P2가 CPU를 선점

- 1초 후에 P3가 들어오지만 여전히 P2의 마감 시간이 더 짧기 때문에 P2 수행 완료

- 그 다음 P3가 20초 내에 종료되어야 하기 때문에 P3 실행

- P3 종료 후 P1 마무리 → 성공