3월 1주차 운영체제 - 3.4 CPU 스케줄링 알고리즘

[Mins00oo]

3.4 CPU 스케줄링 알고리즘

비선점형 방식

💡 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다.

프로세스   실행시간 도착시간

P1              30 0

P2              18 3

P3              9 6

FCFS

• 평균 대기시간: (0 + 27 + 42) / 3 = 23
• FIFO와 비슷한 개념으로, 먼저 온 것을 먼저 처리한다
• 단점으로는, 작업 시간이 긴 프로세스가 앞에 있다면 뒤쪽의 프로세스는 계속해서 기다려야 한다.
• 이를, 콘베이 효과(convey effect)라고 한다.

SJF

• 평균 대기시간: (0 + 24 + 36) / 3 = 20
• 프로세스들의 작업 시간이 짧은 순으로 먼저 실행한다
• 단점으로는, 형평성에 어긋난다는 문제가 있다. → 아사현상
• 프로세스의 실행 시간을 실제로는 알 수 없다는 점에 과거의 실행 시간을 토대로 사용한다.

우선순위 → HRN 스케줄링

• P2의 우선순위: (27 + 18) / 18 = 2.5 , P3의 우선순위: (24 + 9) / 9= 3.67
• 우선순위 = (대기 시간 + 사용 시간) / 사용 시간
• SJF 알고리즘의 단점을 보완하기 위한 알고리즘
• SJF방식은 작업시간만 고려했다면, 대기시간도 같이 고려해서 우선순위를 구한다
• 나오는 우선순위가 높을 수록, 먼저 실행된다.
• 이것도 마찬가지로, 공평성이 위배되어 많이 사용되지 않는다.

선점형 방식

💡 실행중인 프로세스를 알고리즘에 의해 중단시키고 다른 프로세스에 CPU 소유권을 할당시키는 방식

라운드 로빈

• 평균 대기시간: 0(P1) + 7(P2) + 14(P3) + 19(P1) + 19(P2) + 8(P1) / 3 → 67 / 3 = 22.33
• 현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링의 일종
• 각 프로세스에 동일한 할당 시간이 주어진 후, 할당 시간만큼 작업을 한다.
• 작업을 끝내지 못했다면, 맨 뒤로 가서 프로세스는 대기한다.
• 할당시간이 너무 크게 주어지면, FCFS가 된다. → 사실상 RR은 FCFS와 비슷한데 할당시간이 주어진다는 점이 다르다.
• 할당시간이 너무 짧으면, 컨텍스트 스위칭이 잦아져서 많은 시간을 낭비하게 된다.

SRT

• 평균 대기시간: 0 + 4 + 16 + 27 / 3 → 47 / 3 = 15.66
• SJF와는 다르게 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 실행
• 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 컨텍스트 스위칭이 일어나서 작업이 추가된다.
• SJF와 마찬가지로 프로세스의 종료 시간을 예측하기 어렵다.

다단계 큐

• 우선순위에 따라 여러개의 준비 큐를 생성한다.
• 큐마다 다르게 스케줄링 알고리즘을 적용한다.
• 스케줄링 부담은 적지만, 유연성이 떨어진다.