4-4.[os] 스케줄링 알고리즘 (선점형)
라운드 로빈 스케줄링
- 순환 순서 방식
한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업하고, 작업을 다 끝내지 못하면 준비 큐의 맨 뒤에 삽입되어 자기 차례를 기다리는 방식
FCFS 와 비슷, 차이 -> 타임슬라이스
- 타임슬라이스: 프로세스가 CPU를 사용할 수 있는 최대 시간
- 우선순위가 적용되지 않는 가장 단순한 선점형 스케줄링 방식
라운드 로빈 스케줄링의 성능
성능 : 평균 대기시간 계산하기
대기시간
- P1 : 0초 + 19초 (29-10=19) + 8초 (47-39=8)
- P2: 7초 (10-3=7) + 19초 (39-20=19)
- P3: 14초 (20-6)
67/3 = 22.33
평균 대기 시간: 22.33초
- 콘베이 효과가 줄어들음
타임 슬라이스 크기와 문맥 교환
- 라운드 로빈 스케줄링과 FCFS 스케줄링의 평균 대기 시간이 같다면 라운드 로빈 스케 줄링이 더 비효율적
- 문맥 교환 시간이 추가
타임 슬라이스가 큰 경우
- 하나의 작업이 끝난 뒤 다음 작업이 시작됨
- FCFS랑 다를 게 없음
- 다른 프로세스를 기다려야해서 느려짐
타임 슬라이스가 작은 경우
- 여러 프로그램이 동시에 실행되는 것처럼 느낄 것
- 문맥 교환이 너무 자주 일어남 -> 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커짐 -> 실제 작업을 못 하는 문제
결론: 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 결정
유닉스 운영체제의 타임 슬라이스: 대략 100밀리초, 고정하지 않고 10〜 200밀리초 사이에서 조정
SRT 우선 스케줄링
- = Shortest Remaining Time
- SJF 스케줄링 + 라운드 로빈 스케줄링
- SJF 스케줄링의 선점형 버전
- SRT 스케줄링은 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택
- 라운드로빈 스케줄링이 큐에 있는 순서대로 CPU를 할당한다면, SRT 스케줄링은 남은 시간이 적은 프로세스에 CPU를 먼저 할당
SRT 스케줄링의 성능
성능 : 평균 대기시간 계산하기
대기시간
- P1 : 0초 + 19초 (29-10=19) + 27초 (37-10=27)
- P3: 4초 (10-6)
- P2: 16초 (19-3=16)
47/3 = 15.66
평균 대기 시간: 15.66초
- 평균 대기 시간이 짧다?
- 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산
- 남은 시간이 더 적은 프로세스와 문맥 교환을 해야함
- SJF와 마찬가지로 운영체제가 프로세스의 종료 시간 예측 불가
- 아사 현상
우선순위 스케줄링
- 우선순위를 반영한 스케줄링
어떤 기준으로 우선순위를 정하느냐에 따라 다름
예시) FCFS: 작업시간이 짧은 프로세스의 우선순위를 높게 설정할 경우:
- (비선점형 방식) SJF 스케줄링: 작업 시간이 짧은 프로세스에 높은 우선순위를 부여한다.
- (비선점형 방식) HRN 스케줄링: 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순 위를 부여한다.
(선점형 방식) SRT 스케줄링: 남은 시간이 짧은 프로세스에 높은 우선순위를부여한다.
고정 우선순위 알고리즘: 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정됨. 단순하게 구현 할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어진다.
변동 우선순위 알고리즘: 일정 시간마다 우선순위가 변한다. 일정 시간마다 우선순위를 새로 계산하고 이를 반영하기 때문에 시스템이 복잡하지만 시스템의 상황을 반영하여 효율적인 운영이 가능하다.
준비 큐에 있는 프로세스 순서를 무시
- 우선순위가 높은 프로세스에 먼저 CPU 할당
- 공평성 위배
- 아사 현상
- 프로세스의 우선순위를 매번 바꿔야하기 때문에 오버헤드 발생
시스템 효율 저하
시스템의 효율성이 아니라 프로세스의 중요도를 기준으로 결정
- 커널 프로세스 > 일반 프로세스
다딘계 큐 스케줄링
- = multilevel queue
- 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
- 각 큐는 라운드로빈 방식 (시간 정해놓고 돌려가면서 함)
- 큐마다 타임슬라이스 다르게 설정할 수 있음 (예시: 전면은 작게해서 반응속도 올리고, 후면은 크게해서 FCFS)
- 고정형 우선순위 (도중에 우선순위가 바뀌지 않음)
- 상단 큐의 작업이 다 끝나야 다음 우선순위 큐 작업함 (하단은 계속 연기됨)
- 각 단계의 큐에 라운드 로빈 방식을 사용하고 우선순위에는 변화가 없다!
다단계 피드백 큐 스케줄링
- = multilevel feedback queue
- 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식
- CPU를 사용하고 난 프로세스의 우선순위가 낮아진다
- CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤
- 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다 (커널 프로세스는 예외)
- 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화
- 우선순위에 따라 타임 슬라이스의 크기가 다르다
- 우선순위↓ 타임 슬라이스↑
- (우선순위가 낮은 프로세스가 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 우선순위가 낮은 큐의 타임 슬라이스를 크게 설정)
- 마지막 큐는 결국 FCFS (타임슬라이스 크기: 무한대)
- 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식
- 유닉스 운영체제: 타임 슬라이스를 고정하지 않고 10〜 200밀리초 사이에서 조정할 수 있도록 한 이유 -> 바로 다단계 피드백 큐 스케줄링