4-4.[os] 스케줄링 알고리즘 (비선점형)
스케줄링 알고리즘 = 선점형 알고리즘(빼앗을 수 있음) + 비선점형 알고리즘(빼앗을 수 없음)
스케줄링 알고리즘 선택 기준
CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법. 보통 90%도 안됨.
처리량: 처리량은 단위 시간당 작업을 마친 프로세스의 수. 처리량이 클수록 좋은 알고리즘.
대기 시간: 작업을 요청하더라도 실제 작업이 이루어지기 전까지는 대기 시간이 필요하다.
응답 시간: 대화형 시스템에서는 사용자의 요구에 얼마만에 반응하는지가 중요하다. 프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간.
반환 시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간. 반환 시간 = 대기 시간 + 실행시간
- 사용률과 처리량은 계산하기 어려움
- 대기 시간, 응답 시간, 반환시간을 계산
- 대기 시간: 프로세스가 생성된 후 실행되기 전까지 대기하는 시간
- 응답 시간: 첫 작업을 시작한 후 첫 번 째 출력(반응)이 나오기까지의 시간
- 실행 시간: 프로세스 작업이 시작된 후 종료되기까지의 시간
- 반환 시간: 대기 시간을 포함하여 실행이 종료될 때까지의 시간
- 성능: 평균 대기 시간 = 모든 대기시간 / 프로세스 수
FCFS 스케줄링
- 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식
- = 선입선출 스케줄링
성능 : 평균 대기시간 계산하기
대기시간
- P1 : 0초
- P2: 27초 (30-3=27)
P3: 42초 (30+18-6)
(0+27+42)/3 = 23
평균 대기 시간: 23초
특징:
- 단순하고 공정함
- 처리 시간이 긴 프로세스가 CPU를 차지하면 나머지는 하염없이 기다림 → 효율성↓
- 콘보이 효과(convoy effect, 호송 효과): 트럭이 한줄로 늘어서 있을 때 앞의 배달이 막히면 뒤의 배달이 지연되는 현상
SJF 스케줄링
- SJF(Short Job First)
- 최단 프로세스 우선 스케줄링
- 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
- 작은 작업을 먼저 실행하기 때문에 시스템의 효율성이 좋아진다
- 실행 시간이 판단 기준이기 때문에 항상 적은 시간을 사용하는 프로세스에 우선권이 주어짐
성능 : 평균 대기시간 계산하기
- 시작 시점에는 프로세스 P1 뿐이므로 P1은 대기하지 않고 바로 실행된다
- P1: 0초
- P3: 24초 (30-6)
P2: 36초 (30+9-3)
(0+24+36)/3 = 20
평균 대기 시간: 20초
단점:
운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
- 현대의 프로세스는 사용자와의 상호작용이 빈번히 발생하기 때문에 프로그램 종료 시간을 파악하기 어려움. 과거엔 일괄 작업 프로세스였어서 예측이 가능했음.
공평하지 못하다
- 아사현상(starvation), 무한 봉쇄 현상(infinite blocking): 작업 시간이 길다는 이유로 계속 뒤로 밀려서 공평성↓
해결 방안:
에이징
- 프로세스가 양보할 수 있는 상한선을 정하는 방식
- 프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지 양보하도록 규정
-> 결론: SJF 스케줄링은 프로세스의 종료 시간을 파악하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않음
HRN 스케줄링
- HRN(Highest Response Ratio Next)
- 최고 응답률 우선 스케줄링
- SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘
- 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링
- 우선순위를 정할 때 대기 시간을 고려함으로써 아사 현상을 완화 -> 스케줄링 방식에 에이징 구현
성능 : 평균 대기시간 계산하기
우선순위
- P1이 우선 실행
- P2 우선순위: ((30-3)+ 18))/18 =2.5
- P3 우선순위: ((30-6) + 9))/9 = 3.67
- P3>P2 → P3가 먼저 실행
대기 시간
- P1: 0초
- P3: 24초 (30-6)
P2: 36초 (30+9-3)
(0+24+36)/3 = 20
평균 대기 시간: 20초
장점:
- 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상을 완화 단점:
- 공평성에 위배됨