우봉수
2023. 4. 18. 01:38
2023. 4. 18. 01:38
선입 선처리 스케줄링(FCFS)
- First Gome, First-Served Scheduling
- 프로세스가 도착한 순서 차례대로 작업을 하는 것
- 평균 대기 시간: (0<p1>+24<p2>+27<p3>)/3 = 17
만약 프로세스의 도착순서가 바뀐다면?
- 평균 대기 시간: (0<p2>+3<p3>+6<p1>)/3 = 3
- 위의 경우 보다 대기 시간이 훨씬 줄어들었다.(성능 향상)
- 호위 효과(Convoy effect): 긴 프로세스 다음에 존재하는 짧은 프로세스들이 겪는 효과
최단 작업 우선 스케줄링(SJF)
- Shortest-Job-First Scheduling
- 예상 실행시간이 적은 작업 부터 우선 스케줄링 하는 기법
- 단 예상이 틀릴 경우가 존재 할 수 있으므로 그러한 프로세스 들에게는 패널티를 주어야 한다.
- 평균 대기 시간: (0<p4>+3<p4>+9<p3>+16<p2>)/4 = 7
- CPU 버스트 길이의 근사 값을 계산해 가장 짧으 예상 CPU 버스트를 가진 스로세스를 선택한다.
- 지수 평균을 이용하여 CPU 버스트의 길이를 예상한다.
- 선점형, 비선점형으로 존재
최소 잔여 시간 우선 스케줄링(SRT)
- 선점형 SJF 알고리즘을 사용한 스케줄링 방법
- Shortest-Remaining Time First
- 평균 대기 시간: (10-1<P1>+1-1<P2>+17-2<P3>+5-3<P4>)/4 = 26/4 = 6.5
- 프로세스 대기시간: 총 대기시간 - (도착시간 + 이미 진행된 시간)
우선순위 스케줄링
- 숫자가 작을 수록 우선순위를 높게 설정
- 선점형과 비선점형으로 나누어진다.
- SJF는 일종의 우선순위 스케줄링
- 문제점: 낮은 우선순위의 프로세스는 실행되지 않는 기아 문제
- 해결책: (노화) 시간이 흘러갈수록 프로세스의 우선순위를 증가시킨다.
- 평균 대기 시간: (0<P2>+1<P5>+6<P1>+16<P3>+18<P4>)/5 = 8.2
Round Robin (RR)
- 각 프로세스마다 일정 시간(time quantum) 동안만 CPU를 할당받고 해당 시간이 끝나면 다시 맨 뒤로 줄을 서는 방식(큐)
- 준비 완료 큐에 n개의 프로세스가 있고 시간 할당량이 q이면 각 프로세스는 최대 q 시간 단위의 덩어리로 CPU 시간의 1/n 을 얻는다.
- 각 프로세스는 자신의 다음 시간 할당량이 할당 될 때까지 (n-1)q 시간 이상을 대기하지 않는다.
- 시간 할당량이 경과될 때마다 인터럽트를 발생시킨다.
- 성능
- q가 커진다면 → FIFO에 가까워짐
- q가 적어질수록 → q는 문맥 교환 시간에 비해 충분히 커야 한다 그렇지 않으면 오버헤드가 너무 크기 때문에 비효율 적이기 때문이다.
- SJF보다 총처리시간은 크지만 응답시간은 더 좋다.
다단계 큐
- 준비 큐는 별개의 큐로 분할된다
- foreground (RR)
- background (FCFS)
- 큐와 큐 사이의 스케줄링도 정해야 한다.
- 고정 우선순위 스케줄링: 기아가 발생 할 수 있음
- 시간 할당(RR): 각 큐는 일정량의 비율의 CPU 시간을 할당 받는다.
다단계 큐 스케줄링(MQS)
- 각 큐마다 우선순위가 다르다는 것을 이용해 스케쥴링하는 것
다단계 피드백 큐(MFQS)
- 프로세스가 우선순위가 바뀜에 따라 여러 큐로 이동하는 것
- 노화를 이런 방식으로 구현할 수 있다.
- 매개변수
- 큐의 개수
- 각 큐에서 사용하는 스케줄링 알고리즘
- 프로세스 업그레이드 시기를 결정하는 데 사용되는 방법
- 프로세스를 강등시키는 시기를 결정하는 데 사용되는 방법
- 프로세스가 서비스를 받기 위해 들어갈 큐를 결정하는 데 사용되는 방법
- 우선순위가 높은 큐일 수록 time quantum의 크기를 작게 한다.
- 마지막 큐일 경우에는 작업이 끝날 때 까지 계속한다.