728x90
728x90
프로세스 스케줄링 알고리즘
운영체제는 프로세스 스케줄링을 통해 어떤 프로세스에 CPU를 할당할 것인지를 결정한다.
Preemptive vs Non-preemptive
- Preemptive 방식
- CPU 점유를 빼앗을 수 있는 방식이다.
- 프로세스 P1이 CPU를 할당받아 실행중일 때 우선순위가 높은 프로세스 P2가 등장하여 CPU를 요청하면 P1의 CPU를 뺏어서 P2에게 할당하는 방식이다.
- Non-preemptive 방식
- CPU 점유를 빼앗을 수 없는 방식이다.
- 프로세스가 한번 CPU를 할당 받아 실행하면 실행이 끝날 때 까지 다른 프로세스에게 CPU를 넘겨주지 않는 방식이다.
- 스스로의 할당 해제(I/O 작업 등)의 경우에만 CPU 할당 해제가 발생한다.
- 이후 언급될 스케줄링 기법들을 Turn-around Time(Waiting Time + Burst Time)을 기준으로 분석하였다.
각 Process의 정보는 아래 표와 같다.
FCFS(First Come First Served) 스케줄링
Ready Queue에 도착한 순서대로 CPU를 할당하는 방식
- Non-preemptive(비선점) 스케줄링이다.
Average Turn-around Time : ((0+3)+(1+6)+(5+4)+(7+5)+(10+2))/5 = 43/5
장점
- Starvation 이 발생하지 않는다.
단점
- 평균 대기시간(Average Waiting Time)이 길어질 수 있다.
- 응답 시간(Response Time)이 길어질 수 있다.
- convoy effect : 시간이 많이 필요한 작업이 먼저 수행되어서 나중에 도착한 시간이 빨리 끝나는 작업이 수행되지 못하는 것
Round Robin(RR) 스케줄링
각 프로세스에 동일한 CPU 할당 시간(time quantum)을 부여하고, 할당 시간이 경과되면 CPU를 회수해 Ready Queue에 있는 다음 프로세스에게 CPU를 할당하는 방식
- preemptive(선점) 방식이다.
Average Turn-around Time : ((1+3)+(10+6)+(9+4)+(9+5)+(5+2))/5 = 54/5
장점
- Response Time 이 빠르다.
단점
- time quantum 이 너무 짧으면 Context Switching이 자주 발생해 Overhead가 증가한다.
- time quantum 이 너무 길면 FCFS 와 같은 결과를 얻게 된다.
SJF(Shortest Job First) 스케줄링
burst time(남은 실행 시간, 예측된 값)이 짧은 프로세스부터 먼저 CPU를 할당하는 방식
- preemptive / non-preemptive 방식으로 나누어진다.
SPN(Shortest Process Next) 스케줄링
burst time 이 더 짧은 프로세스가 등장해도 실행하던 프로세스는 CPU를 반납하지 않는다.
- SJF의 Non-preemptive 방식이다.
Average Turn-around Time : ((0+3)+(1+6)+(7+4)+(9+5)+(1+2))/5 = 38/5
SRTF(Shortest Remaining Time First 또는 SRT) 스케줄링
burst time이 더 짧은 프로세스로 교체한다.
- SJF의 preemptive 방식이다.
Average Turn-around Time : ((0+3)+(7+6)+(0+4)+(9+5)+(0+2))/5 = 36/5
장점
- Optimal(최적)의 알고리즘이다.
- 더 짧은 Turn-around Time 은 불가능하다.
단점
- 비현실적이다.
- burst time을 정확하게 예측하는 것은 불가능하다.
- 예측하는 과정에서 overhead가 발생한다.
- starvation(기아 현상) 이 발생할 수 있다.
- 최악의 경우에 burst time 이 긴 프로세스는 Ready Queue 에서 영원히 기다리게 된다.
HRRN(Highest Response Ratio Next) 스케줄링
프로세스가 끝나면 Ratio 값을 계산하고, Ratio 값이 큰 프로세스를 실행하는 방식이다.
Ratio : Burst time 대비 얼마나 기다렸는 지를 나타낸다.
- Non-preemptive 방식이다.
Average Turn-around Time : ((0+3)+(1+6)+(5+4)+(9+5)+(5+2))/5 = 40/5
장점
- Starvation이 발생하지 않는다. - Aging 기법 사용
- Aging 기법 : 프로세스의 대기 시간이 길수록 우선순위를 높여주는 방식
단점
- burst time을 정확하게 예측할 수 없다.
- 예측하는 과정에서 Overhead가 발생한다.
- 최고의 성능을 보장하지 않는다.
MFQ(Multilevel Feedback QueueMFQ) 스케줄링
실행시간을 예측하지 않고, 실행시간이 짧은 것에 우선순위를 주는 방식이다.
- 실행시간이 긴 process에게 패널티를 주어 예측하지 않고 우선순위를 부여할 수 있다.
- preemptive 방식이다.
작동 방식
- N 개의 Ready Queue가 존재한다.
- 새로운 Process는 0번 Ready Queue에 추가된다.
- 0번 부터 작업을 시작하고, n번 큐까지 비어있을 때 N+1 번 큐의 작업을 시작한다.
- time quantum을 모두 사용한 Process는 다음 Ready Queue(N+1 번 큐) 로 넘어가게 된다.
- time quantum q는 해당 큐의 순위에 따라 다르다.(ex. n 번째 큐 : q = 2^N )
time quantum을 다르게 설정한 이유?
- 아래 큐로 밀려날수록 CPU를 점유할 확률이 낮다.
- 따라서, 긴 time quantum을 주어 한번 CPU를 점유 할 시 최대한 완료할 수 있게 구성한다.
장점
- burst time을 예측하지 않고 비슷한 효과를 낼 수 있다.
- 예측에 필요한 overhead를 절약할 수 있다.
단점
- 설계 및 구현 과정에서 overhead가 발생한다.
- 여전히 starvation을 완벽하게 해결하지 못한다.
추가 질문
Q. RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.
더보기
- time quantum 이 너무 짧으면 Context Switching이 자주 발생해 Overhead가 증가한다.
- time quantum 이 너무 길면 response time 이 길어진다.
Q. 동시성과 병렬성의 차이에 대해 설명해 주세요.
더보기
동시성
- 하나의 코어로 빠르게 전환하며 여러 작업을 수행하는 것
- 여러 작업이 동시에 실행되는 것처럼 보인다.
병렬성
- 실제로 여러 코어로 여러 작업을 동시에 수행하는 것
728x90
728x90
'Computer Science > Operating System' 카테고리의 다른 글
Deadlock(데드락) (0) | 2023.03.08 |
---|---|
Mutex(뮤텍스) & Semaphore(세마포어) (0) | 2023.03.07 |
Context Switching(컨텍스트 스위칭) (0) | 2023.03.07 |
단기 스케줄러, 중기 스케줄러, 단기 스케줄러 (0) | 2023.03.07 |
Process Address Space(프로세스 주소 공간) (0) | 2023.03.07 |