개요
워크로드에 대한 가정
일련의 프로세스들이 실행되는 상황 (워크로드) 가정
- 모든 작업은 같은 시간 동안 실행됨
- 모든 작업은 동시에 도착함
- 각 작업은 시작되면 완료될 때까지 실행
- 모든 작업은 CPU만 사용 (＝ I/O 수행 X)
- 각 작업의 실행 시간은 사전에 알려짐
스케줄링 평가 항목 (scheduling metric)
- 반환 시간 (turnaround time)
작업이 `완료`된 시각에서 작업이 시스템에 `도착`한 시간을 뺀 시간으로 정의
위 가정에서 모든 작업은 동시에 도착한다고 가정했으므로, `arrival = 0`
∴ 작업 반환 시간 = 작업 완료 시각
📌 반환 시간은 성능 측면에서의 평가 기준
다른 평가 기준으로는 `공정성`(Fairness)이 있음.
성능과 공정성은 스케줄링에서 상충되는 목표임
성능 vs 공정성
CPU 스케줄링에서 성능과 공정성은 시스템 성능을 평가하는 두 가지 핵심 지표
각각 효율성과 공정성 측면에서 상호 보완적 역할을 함
Jain's Fariness Index : 자원 할당의 공정성을 측정하기 위해 널리 사용되는 지표
| 항목 | 반환 시간 | Jain's Fairness Index |
| 측정 대상 | 개별 프로세스의 실행 시간 | 전체 시스템의 자원 분배 패턴 |
| 민감도 | 대기 시간, 실행 시간 변화에 민감 | 극단적 불공정 사례에 덜 민감 |
| 사용 사례 | 실시간 시스템, 배치 처리 | 클라우드 자원 관리, QoS 보장 |
- `TAT`: 프로세스 제출부터 완료까지의 총 시간
- `JFI`: 모든 프로세스가 받은 CPU 시간의 균등성을 0~1 범위로 정량화 (1에 가까울 수록 공정)
극단적 불공정 사례에 둔감 ❓
한 프로세스를 제외한 나머지 프로세스들이 균등하게 자원을 받으면 = JFI는 높게 나옴
CPU 스케줄링 알고리즘
CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당
프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정
목표: `CPU 이용률 ↑`, `주어진 시간에 多일`, `준비 큐 프로세스는 少`, `응답시간↓`
비 선점형 방식
비 선점형 (non-preemptive) 은 프로세스가 스스로 CPU를 포기하는 방식
강제로 프로세스 중지하지 않음
∴ 컨텍스트 스위칭으로 인한 부하 적음
1) 선입 선출 (First In First Out, FIFO)
가장 먼저 온 것을 가장 먼저 처리하는 알고리즘
길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상 (convoy effect)이 발생
- 간발의 차이로 A, B, C 순서대로 도착했다고 가정 (도착 시간 = 0)
- 각 작업들은 10초 동안 실행
∴ 평균 반환 시간 = `(10+20+30)/ 3 = 20`
실행 시간이 모두 같지 않을때 위 그림의 평균 반환 시간은 `(100+110+120)/3 =110`
짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동한 사용하는 프로세스의 종료를 기다리는 현상인
👉 Convoy effect 발생
그렇다면, 작업 실행 시간이 다른 경우 좋은 알고리즘은 ?
2) 최단 작업 우선 (Shortest Job First, SJF)
실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘
- 긴 시간을 가진 프로세스가 실행되지 않는 현상 (starvation) 발생
- 평균 대기 시간이 가장 짧음
- 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행 시간을 토대로 추측
처음 실행되는 프로세스인 경우 예측은 어떻게 할까 ❓
1. `기본값` 할당: 운영체제가 사전에 설정한 고정값 (ex: 10ms) 사용
2. `부모 프로세스`의 실행 시간 상속: 부모 프로세스의 평균 실행 시간을 초기 값으로 사용
3. `동적 평균값`활용: 현재 시스템에서 실행된 모든 프로셋의 평균 실행 시간을 초기 추정치로 사용
모든 작업이 동시에 도착하는 경우, SJF는 최적의 스케줄링 알고리즘임
평균 반환 시간 = (10+20+120)/3 =50
모든 작업이 동시에 도착하지 않으므로 임의의 시간에 도착한다면? (가정 2 완화)
- A: t=0 시간에 도착
- B,C: t=10 시간에 도착
도착시간이 다르다면, 위그림과 같이 A가 끝날 때까지 B, C는 기다릴 수밖에 없음
이전의 FIFO 알고리즘에서 확인한 `Convoy` 문제 발생
평균 반환 시간 = (100+ (110-10)+(120-10)) /3 = 103.33
우선순위
SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상 발생.
오래된 작업일수록 우선순위를 높이는 방법을 통해 단점 보완한 알고리즘
선점형 방식
선전형(preemptive) 방식은 현대 운영체제가 쓰는 방식
현재 사용하고 있는 프로세스를 알고리즘에 의해 중단시키고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식
📌 즉, 스케줄러는 컨텍스트 스위칭을 수행하고, 실행 중인 프로세스 중단 & 다른 프로세스 실행 및 재개 가능
1) 최소 잔여시간 우선 (Shortest Remaining First, SRF)
중간에 실행시간이 더 짧은 작업이 들어와도 기존 작업을 모두 수행하고 다음 작업을 실행하는 SJF에 `선점형` 기능 추가
- 새로운 작업이 시스템에 들어옴
- 스케줄러는 남아 있는 작업과 새로운 작업의 잔여 실행 시간 계산
- 가장 적은 잔여 실행 시간을 가진 작업 스케줄
새로운 가정(작업마다 임의의 시간에 도착함) 하에서, SRF가 최적의 알고리즘
∵ 모든 작업들이 동시에 도착할 경우 SFJ가 최적의 결과를 도출
새로운 평가 기준 - 응답 시간
작업의 실행 시간을 미리 알고 있고, 작업이 오직 CPU만 활용하면서 평가 기준이 반환 시간만 존재하는 경우,
SRF는 최고의 알고리즘임
시분할 시스템의 등장으로 사용자는 터미널에서 작업하게 되어 시스템에게 상호작용을 원활히 하기 위한 성능 요구
시분할 시스템❓
한 대의 컴퓨터를 여러 사용자가 동시에 사용할 수 있도록 설계된 시스템
- 다중 사용자 환경: 각 사용자는 자신의 프로그램 실해 & 다른 사용자와 독립적 작업
- 시간 슬라이싱: CPU 처리 시간을 작은 단위로 나누어 사용자에게 순차적 할당
- 실시간 상호작용: 사용자는 터미널을 통해 명령 입력 & 즉각 응답
응답 시간 (reponse time)이라는 새로운 평가 기준 생김
`응답 시간`: 작업이 도찰할 때부터 처음 스케줄 될 때까지의 시간
이전의 알고리즘은 응답 시간과 상호작용 측면에서는 나쁜 방법임
그렇다면, 응답 시간에 민감한 스케줄러는 어떻게 만들까?
2) 라운드 로빈 (Round Robin, RR)
각 프로세스는 동일한 일정 시간을 주고, 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 이동하는 알고리즘
- 현대 컴퓨터가 쓰는 스케줄링
- 우선순위 스케줄링의 일종
- 일정 시간 = 타임 슬라이스 = 스케줄링 퀀텀
- 로드밸런서에서 트래픽 분산 알고리즘으로 사용
타임 슬라이스의 길이는 RR에서 매우 중요
짧을 수록 응답 시간 기준으로 RR 성능은 좋아지지만, 너무 짧게 지정하면 컨텍스트 스위칭 비용이 전체 성능에 영향O
3) 다단계 큐
- 우선순위에 따른 준비 큐를 여러 개 사용
- 큐마다 RR이나 FIFO 등 다른 스케줄링 알고리즘을 적용
- 큐 간의 프로세스 이동X
기아 문제: 낮은 우선순위 큐에 있는 프로세스가 높은 우선순위 프로세스들로 인해 실행 x
유연성 부족: 한 번 할당된 큐 변경x, 동적 환경에서 적응력 떨어짐
4) 다단계 피드백 큐 (Multi-Level Feedback Queue, MLFQ)
다단계 큐의 확장 형태, 프로세스가 큐 간에 이동할 수 있는 기능 추가
- 처음에는 높은 우선순위 큐에서 실행
- 실행 시간이 길어지면 낮은 우선순위 큐로 이동
- 짧은 작업은 빠르게 끝내고, 긴 작업은 낮은 우선순위에서 실행
- 현대 운영체제에서 가장 많이 사용하는 스케줄링 방식 中 하나
