스케줄링 알고리즘(FCFS, RR, SJF, SRT, Priority, MLQ, MFQ)

FCFS(Frist Come First Served) 스케줄링

• FCFS 스케줄링은 준비 큐에 도착한 순서대로 CPU를 할당해준다.
• 비선점형 방식이다.
• 한 번 시작 되면 그 프로세스가 끝나야만 비로소 다음 프로세스를 실핼 할 수 있다.
• 작성이 간단하고 이해가 쉽다.
• 평균 대기 시간이 길어질 수 있어 Convoy Effect(호위효과)가 발생할 수 있다.
  • Convoy Effect란?
    : 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스를 차지하기 때문에 다른 프로세스들이 계속 기다려야 되는 현상. 효율성이 떨어진다.
• 응답 시간이 길어질 수 있다.
• 반환 시간에서는 유리하다.

FCFS 예시

P1,P2,P3가 모두 0초에 도착했다고 가정할 때 이렇게 결과가 나온다.
대기 시간 : P1 = 0, P2 = 24, P3 = 27
반환 시간 : P1 = 24, P2 = 27, P3 = 30
반응시간 : P1 = 0, P2 = 24, P3 = 27
평균 대기 시간 : (0+24+27)/3 = 17

Round Robin(RR) 스케줄링

• 각각의 프로세스에 동일한 CPU 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하도록 한다.
  (할당 시간이 지나면 프로세스를 빼앗고 다시 준비 큐에 제일 뒤에 줄을 서도록 한다. 선점형 방식)
• n개의 프로세스가 있을 때 할당 시간을 q로 설정하면, 어떤 프로세스도 (n-1)q 시간 이상을 기다리지 않아도 된다.
• 부여 시간을 너무 크게 잡으면 FCFS처럼 작동한다.
• 부여 시간을 너무 작게 잡으면 문맥교환에 대한 오버헤드가 커지게 된다.
• 응답 시간을 빠르게 할 수 있다.
• Convoy Effect 효과가 줄어든다.

Round Robin(RR) 예시

모두 0초에 도착했고 할당시간 q가 20초라는 가정하에 이렇게 결과가 나온다.
대기 시간 : P1 = 81, P2 = 20, P3 = 94, p4=97
반환 시간 : P1 = 77, P2 = 37, P3 = 162 ,P4 = 121
반응시간 : P1 = 0, P2 = 20 , P3 = 27 ,p4 = 57
평균 대기 시간 : (81+20+94+97)/4 = 73

SJF(Shortest-Job-First) 스케줄링 , SRT(Shortest Remaining Time) 스케줄링

• 다음 CPU burst time가 가장 작은 작업에 CPU를 할당한다.
  • CPU burst time란?
    : CPU 할당 후 입출력을 요구할 때까지의 시간
• 선점형과 비선점형으로 나누어진다.
• 비선점형에서는 실행 되고 있는 프로세스는 끝까지 실행한다.
• 선점형에서는 현재 실행되고 있는 프로세스의 남은 시간보다 도착한 프로세스가 더 빨리 끝날 수 있는 프로세스라면 다음 프로세스를 실행하도록 바꾸게 된다.
• 선점형 SJF의 경우 SRT(Shortest Remaining Time)이라고도 부른다.
• 평균 대기 시간을 줄일 수 있다.

SJF (비선점형) 예시

대기 시간 : P1 =0 , P2 = 6, P3 = 3, p4=7
반환 시간 : P1 = 7, P2 = 10, P3 = 4 ,P4 = 11
반응시간 : P1 = 0, P2 = 6 , P3 = 3 ,p4 = 7
평균 대기 시간 : (0+6+3+7)/4 = 4

SRT (선점형) 예시

대기 시간 : P1 =9 , P2 = 1, P3 = 0, p4=2
반환 시간 : P1 = 16, P2 = 5, P3 = 1 , P4 = 6
반응시간 : P1 = 0, P2 = 0 , P3 = 0 , p4 = 2
평균 대기 시간 : (9+1+0+2)/4 = 3

Priority 스케줄링

• 각각의 프로세스에 우선 순위 번호가 있다.
• 가장 높은 우선 순위의 프로세스에게 CPU를 할당한다.
• 선점형과 비선점형이 있다.
• 기아(Starvation)문제가 발생할 수 있다.
  • 기아문제란?
    : 우선 순위가 낮은 프로세스가 절대 실행 되지 않는 문제를 말한다.
• 기아 문제를 해결하기 위해 노화(aging)를 사용할 수 있다.
  • 노화(aging)
    : 프로세스가 기다리는 시간이 길어질수록 우선 순위를 높여 주는 것을 말한다.

Priority 예시

모두 0초에 도착했다고 가정했을 때 결과는 이렇다.
대기 시간 : P1 =6 , P2 = 0, P3 = 16, p4 = 18, P5 = 1
반환 시간 : P1 = 16, P2 = 1, P3 = 18 , P4 = 19, P5 = 6
반응시간 : P1 = 6, P2 = 0 , P3 = 16 , p4 = 18, P5 = 1
평균 대기 시간 : (6+0+16+18+1)/5 = 8.2

MLQ(Multilevel Queue)

• 앞 스케줄링 방법들이 큐를 하나도 가정했다면 멀티레벨큐는 레디 큐를 여러개 사용한다.
• 각각의 큐는 각자의 스케줄링 알고리즘을 가지고 있다.
• 기아(Starvation) 문제가 발생할 수 있다.
• 지정 된 큐를 벗어나지 못한다.(환경에 유연하게 적응 못한다.)

MFQ(Multi-level Feedback Queue)

• MLQ에서 지정 된 큐를 벗어나 우선 순위를 바꿀 수 있도록 허용한 스케줄링 방식이다.(환경 변화에 따라 유연하게 사용해야 될 때 유용하다.)
• 복잡하고 낮은 우선순위는 기아현상(Starvation)을 겪을 수 있다.
• 선점 스케줄링 방식으로 우선 순위가 바뀌거나 큐를 이동하면 프로세스를 빼앗거나 빼앗길 수 있다.
• 큐 간의 이동은 피드백을 통해 우선순위가 조정된다.(동적 우선순위)
  • 피드백
    :현재까지 프로세스의 사용 정보나 패턴들

🙇‍ 참고 사이트 🙇‍

https://code-lab1.tistory.com/45
https://kjhoon0330.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-2-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#3.%202.%20FCFS(First-Come%20First-Served)%20%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81
https://cocoon1787.tistory.com/123
https://rheem-hm.tistory.com/36