<쉽게 배우는 운영체제> 교재를 참고하였습니다.
스케줄링 알고리즘의 선택 기준

-
비선점형 알고리즘은 작업을 종료할 때가지 CPU를 놓지 않기 때문에 효율 저하로 현재는 거의 사용하지 않음
-
선점형 알고리즘은 시분할 시스템을 고려해서 개발된 기술로, 어떤 프로세스가 CPU를 할당 받아 실행 중이라도 OS가 CPU를 강제로 빼앗을 수 있음
스케줄링 알고리즘의 평가 기준
- CPU 사용률
-
전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
-
가장 이상적인 수치는 100%이지만 실제로는 여러 가지 이유로 90%에도 못 미침
-
- 처리량
- 단위 시간당 작업을 마친 프로세스의 수
- 이 수치가 클 수록 좋은 알고리즘임

-
대기 시간 : 프로세스가 생성된 후 실행되기 전까지 대기하는 시간.
-
응답 시간 : 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기까지의 시간
-
실행 시간 : 프로세스 작업이 시작된 후 종료되기까지의 시간
-
반환 시간 : 대기 시간을 포함하여 실행이 종료될 때까지의 시간
스케줄링 알고리즘 선택 (평가) 기준
-
대기시간: 작업을 요청해도 실제작업이 이루어지기 전까지 대기시간이 필요함. 이 시간은 짧을수록 좋음
-
응답시간: 대화형 시스템에서 사용자의 요구에 얼마나 빠른 시간 내에 반응하는지 중요함. 응답시간은 프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 소요시간임
-
반환시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데 소요되는 시간. 반환시간은 대기시간과 실행시간의 합
CPU 알고리즘의 효율성을 평가할 때 사용률과 처리량은 계산이 복잡하기 때문에 일반적으로 대기시간, 응답 시간, 반환 시간을 계산함.
스케줄링 알고리즘의 성능을 비교할 때 주로 평균 대기 시간을 평가함.
평균 대기 시간
- 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값

FCFS 스케줄링
FCFS 스케줄링의 동작 방식
-
준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식 (선입선출)
-
한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있음
- 모든 프로세스는 우선순위가 동일

FCFS 스케줄링의 성능


FCFS 스케줄링의 성능
- FCFS 스케줄링의 성능 : 평균대기시간을 적용해서 평가함
- 작업이 시작할 때까지 전체 프로세스가 대기한 시간의 평균값
- 평균 대기 시간 : (0+27+42)÷3=23밀리초
FCFS 스케줄링의 평가
-
처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어짐
-
특히 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어짐
-
시분할 시스템에서는 입출력을 요청한 프로세스를 대기상태로 보내서 처리할 수 있지만, 일괄처리 시스템에서는 프로세스의 상태 변화가 없기 때문에 작업효율이 저하됨

SJF(Shortest job first) 스케줄링
SJF 스케줄링의 동작 방식
-
준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
- 최단 작업 우선 스케줄링이라고도 함.
-
콘보이 효과를 완화하여 시스템의 효율성을 높임
- SJF 스케줄링은 프로세스에 CPU를 할당할 때 시간이 오래 소요되는 작업이 앞에 있고 간단한 작업이 뒤에 있으면 순서를 교체해서 실행

SJF 스케줄링의 성능


SJF 스케줄링의 성능
- 평균 대기 시간: (0+24+36)÷3=20밀리초
- 시작 시점에서 프로세스는 P1 뿐이므로 P1은 바로 실행, P1이 30밀리초동안 작업을 하면 큐에 프로세스 P2와P3이 기다림. 두 프로세스 중 P3 작업이 짧기 때문에 먼저실행. 마지막에 P2가 36밀리초를 기다린 후 실행됨
SJF 스케줄링의 평가
-
운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움
-
작업 시간이 길다는 이유만으로 계속 뒤로 밀려 공평성이 현저히 떨어짐. 이를 아사(starvation) 현상이라 부름
SJF 스케줄링의 평가
-
SJF 스케줄링 방법은 먼저 도착한 큰 작업으로 인해 작은 작업이 지연되는 FCFS 스케줄링보다 평균대기 시간이 단축됨
-
현대 프로세스는 사용자와 상호작용이 자주 발생하기 때문에 프로그램 종료시간 파악이 어려움. 예를 들면 워드프로세서를 사용할 때 몇 분 안에 종료되는 경우도 있고, 몇시간 동안 작업하는 경우도 있음. 이렇게 프로세스 작업의 길이를 추정하는 것이 불가능함.
- 아사(starvation) 현상(만약 p3 같은 작은 작업이 계속 준비 큐에 진입하면 프로세스 p2의 작업이 계속 연기됨)
에이징 (나이 먹기)
- 아사 현상의 완화 방법
- 프로세스가 양보할 수 있는 상한선을 정하는 방식
- 프로세스가 자신의 순서를 양보할 대마다 나이를 한살씩 먹어 최대 몇 살까지 양보하도록 규정하는 것
HRN 스케줄링
HRN(Highest Response ratio Next) 스케줄링의 동작 방식
- SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘
- 최고 응답률 우선 스케줄링이라고도 함
- 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식
- 대기 시간을 고려함으로 아사현상 완화

HRN 스케줄링의 성능


HRN 스케줄링의 성능
- P1 도착과 동시에 실행. 이때 준비 큐에 있는 P2와 P3 우선순위 계산
- P2 = (27 대기시간 + 18CPU 사용시간) / 18CPU사용시간 = 2.5
- P3 = (24 + 9)/9 = 3.67 임. 따라서 HRN 스케줄링에서는 숫자가 큰 P3가 먼저 실행됨.
- 프로세스의 실행 순서는 SJF와 동일해서 평균 대기 시간은 20 밀리초임.
HRN 스케줄링의 평가
-
실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상을 완화
-
대기 시간이 긴 프로세스의 우선순위를 높임으로써 CPU를 할당 받을 확률을 높임
-
여전히 공평성이 위배되어 많이 사용되지 않음
라운드 로빈(Round Robin) 스케줄링
라운드 로빈 스케줄링의 동작 방식
-
한 프로세스가 할당 받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
-
선점형 알고리즘 중 가장 단순(간단)하고 대표적인 방식
-
프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행
- RR 스케줄링 방법은 FCFS 스케줄링 방법과 유사하지만, 각 프로세스에 CPU를 사용할 수 있는 최대 시간(타임 슬라이스) 이 있음
-
프로세스는 자신에게 주어진 시간만큼만 작업할 수 있으며 작업이 종료되지 않으면 뒤쪽에 삽입됨
- RR 스케줄링은 우선순위가 적용되지 않은 가장 단순한 선점형 스케줄링 방식

라운드 로빈 스케줄링의 성능


라운드 로빈 스케줄링의 성능
- 타임 슬라이스가 10밀리초인 시스템에서 표와 같이 프로세스가 실행될 때 RR 스케줄링의 평균대기 시간을 계산
- 프로세스 P1 은 도착하면서 실행, 대기시간 0, P1 은 주어진 작업시간 10ms 동안 실행된 후 큐의 맨 뒤로 이동함
- 프로세스 P2 는 3ms 후에 도착해서 7ms 를 기다리고, 10ms 동안 실행되고, 큐의 맨 뒤로 이동함
- 프로세스 P3 은 6 ms 후에 도착해, 14 ms 를 대기한 후 9ms 동안 실행되고 작업을 마침
- 프로세스 P1 은 29ms 후에 작업을 다시 시작함. 앞선 작업에서 10ms 동안 실행되었기 때문에 실제 대기시간은 19ms
- 프로세스 P1 이 10ms 동안 실행된 후 큐의 맨 뒤로 이동하면 P2가 8 ms 동안 실행되고 작업을 마침
- P1 마지막 작업이 실행되고 모든 작업이 종료됨
- 총 대기 시간 : 0(P1)+7(P2)+14(P3)+19(P1)+19(P2)+8(P1)=67밀리초
- 평균 대기 시간 : 67÷3=22.33 밀리초
타임 슬라이스의 크기와 문맥 교환
-
FCFS의 평균대기시간=23 ms, RR= 평균대기시간=22.33ms
-
라운드 로빈 스케줄링이 효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 함
타임 슬라이스가 큰 경우
- 타임 슬라이스가 너무 크면 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보여 FCFS 스케줄링과 다를 게 없음
-
예) 타임 슬라이스 1초인 시스템에서 비디오 플레이어와 워드 프로세서 동시실행
-
비디오 플레이어와 워드프로세스가 동시에 실행되면, 두 프로세스에 문제가 생김(비디오 끊김 현상 및 반응속도가 매우 느림)
타임 슬라이스가 작은 경우
-
타임 슬라이스를 1밀리초와 같이 매우 작은 값으로 설정하면, 사용자는 여러 프로그램이 동시에 실행되는 것처럼 느낌
-
그러나 타임 슬라이스를 너무 작게 설정하면 시스템의 전반적인 성능 저하
-
문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생
-
결론 : 타임 슬라이스를 작게 설정하되 문맥 교환에 소요되는 시간을 고려하여 적절한 크기로 설정.
-
참고: 유닉스 타임슬라이스 대략 100 ms, (100-200밀리초 조절가능)
정리
-
타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요
-
유닉스 운영체제에서는 타임 슬라이스가 대략 100 밀리초

SRT 우선 스케줄링
SRT (Shortest Remaining Time) 스케줄링의 동작 방식
-
SJF와 RR을 혼합한 방법으로 최소 잔류시간 우선 스케줄링이라고 함. SJF의 선점형 버전이라고 말할 수 있음
-
기본적으로 라운드 로빈 스케줄링 (RR) 을 사용하지만, CPU를 할당받을 (배정받을) 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택
-
RR 스케줄링이 큐에 있는 순서대로 CPU를 할당하는 것이라면, SRT는 남은 작업시간이 작은 순으로 처리됨

SRT 스케줄링의 성능


SRT 스케줄링의 성능
- 타임 슬라이스 10 ms 인 시스템에서 다음 같은 프로세스가 실행될 때 SRT 방법으로 계산
- P1 도착후 바로 실행(대기시간 0), P1은 자신에게 주어진 작업시간인 10ms동안 실행 후 큐의 맨 뒤쪽으로 이동
- P2는 3ms 후에 도착, P3은 6ms 후에 도착하는데, P3의 작업이 짧기 때문에 P3 가 먼저실행 9ms 후에 작업종료.
- 나머지 P1의 남은 작업과 P2의 작업 시간 중 P2의 작업시간이 짧기 때문에 P2 연속 두 번 실행, 그 다음 P1의 남아있는 작업을 실행함
- 총 대기시간 : 0(P1)+4(P3)+16(P2)+27(P1)=47밀리초
- 평균 대기 시간 : 47÷3=15.66 밀리초
SRT 스케줄링의 평가
- SJF 방법과 SRT 방법의 평균대기시간을 비교해 보면 SRT 방법이 짧은 평균대기시간을 나타내지만 SRT 방법은 좋은 알고리즘이 아님
- 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가됨
-
운영체제가 프로세스의 종료 시간을 예측하기 어렵고, 아사 현상이 일어나기 때문에 잘 사용하지 않음
우선순위 스케줄링
우선순위 스케줄링의 동작 방식
-
프로세스의 중요도에 따른 우선순위를 반영한 스케줄링 알고리즘
-
[표4-5]와 같이 작업시간이 짧은 프로세스의 우선순위를 높게 설정했다고 가정


우선순위 스케줄링의 동작 방식
- 우선순위 스케줄링의 동작 방법 : 프로세스 우선순위를 반영한 알고리즘
- P1은 바로 실행, P1이 작업을 종료하면, 준비 큐에 있는 P2와P3 중에 P3가 우선순위가 높아 먼저 실행되고, 다음 P2 실행됨.
- 이 경우 총 대기시간과 평균 대기 시간이 SJF와 같음
우선순위 적용
-
우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있음
-
(비선점형 방식) SJF 스케줄링 : 작업 시간이 짧은 프로세스에 높은 우선순위를 부여
-
(비선점형 방식) HRN 스케줄링 : 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위를 부여
-
(선점형 방식) SRT 스케줄링 : 남은 시간이 짧은 프로세스에 높은 우선순위를 부여
-
고정 우선순위 알고리즘
-
한 번 우선순위를 부여 받으면 종료될 때까지 우선순위가 고정
-
단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어짐
변동 우선순위 알고리즘
-
일정 시간마다 우선순위가 변하여 일정 시간마다 우선순위를 새로 계산하고 이를 반영
-
복잡하지만 시스템의 상황을 반영하여 효율적인 운영 가능
우선순위 스케줄링의 평가
-
준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하므로 공평성을 위배하고 아사 현상을 일으킴
-
준비 큐에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성을 떨어뜨림
-
이런 단점도 있지만, 프로세스의 우선순위는 시스템의 효율성이 아니라 중요도를 기준으로 결정됨
- 예) 커널 프로세스
다단계 큐 스케줄링
다단계 큐 (multilevel queue) 스케줄링의 동작 방식
-
우선순위에 따라 준비 큐를 여러 개 사용하는 방식
-
프로세스는 운영체제로부터 부여 받은 우선순위에 따라 해당 우선순위의 큐에 삽입
-
라운드 로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 나뉘어 프로세스가 큐에 삽입되는 것으로 우선순위가 결정
-
우선순위는 고정형 우선순위를 사용
-
상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작됨
-
다단계 큐 스케줄링은 우선순위에 따라 다양한 방법이 가능한 선점형 알고리즘임
-
우선순위가 높은 프로세스가 낮은 프로세스보다 먼저 작동하며 우선순위에 따라 타임 슬라이스를 조절하여 작업의 효율을 높일 수 있음
-
예) 전면 프로세스는(인터넷 브라우저)는 반응속도를 높이기 위해 타임슬라이스를 작게하고, 후면프로세스는(워드프로세서) 사용자와 상호작용이 작기 때문에 FCFS 방식으로 처리함
-
즉, 프로세스의 우선순위를 작업형태에 따라 결정할 수 있음
-
우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기되는데, 이런 문제를 해결하기 위해 제안된 방법이 다단계 피드백 큐임

다단계 피드백 큐 스케줄링
다단계 피드백 큐 스케줄링의 동작 방식
-
프로세스가 CPU를 한 번씩 할당 받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화
-
우선순위가 낮아진다고 할지라도 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않음
-
우선순위에 따라 타임 슬라이스의 크기가 다름
-
우선순위가 낮아질수록 CPU를 얻을 확률이 적어짐. 따라서 한번 CPU를 잡을 때 많이 작업하라고 낮은 우선순위의 타임 슬라이스를 크게 함.
-
마지막 큐에 있는(우선순위가 가장 낮은) 프로세스는 무한대의 타임 슬라이스를 얻음
-
마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작
-
다단계 피드백 큐 알고리즘은 오늘날의 OS가 CPU 스케줄링을 위해 일반적으로 사용하는 방법임, 변동우선순위 알고리즘의 전형적인 방법
-
유닉스 운영체제에서 타임 슬라이스를 고정하지 않고 10-200 ms 사이를 조정할 수 있도록 한 이유는 바로 다단계 피드백 큐 방법을 사용하기 때문임

다단계 피드백 큐 스케줄링의 동작 방식
- 다단계 피드백 큐 방법은 우선순위가 낮은 프로세스에 불리한 다단계 큐 방법의 문제점을 보완함.
- 다단계 큐의 경우 각 단계의 큐에 라운드 로빈 방식을 사용하고, 우선순위에는 변화가 없는데 반해 다단계 피드백 큐 스케줄링은 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화함.
'전공 > 운영체제' 카테고리의 다른 글
Ch05. 프로세스 동기화_01) 프로세스 간 통신 (0) | 2023.04.18 |
---|---|
[심화]Ch04. CPU 스케줄링 _05)인터럽트 처리 (0) | 2023.04.04 |
Ch04. CPU 스케줄링 _03) 다중 큐 (0) | 2023.04.02 |
Ch04. CPU 스케줄링 _02) 스케줄링 시 고려 사항 (0) | 2023.03.29 |
Ch04. CPU 스케줄링 _01) 스케줄링의 개요 (0) | 2023.03.29 |
댓글