FCFS & SJF & Priority & Round Robin

First-Come, First-Served(FCFS)

• 먼저 온 순서대로 차례대로 CPU를 할당
• 가장 간단하고 공평한 방법
• Non-preemptive scheduling

위 FCFS를 하나의 예시를 들어 살펴보도록 합시다

프로세스가 P1, P2, P3가 ReadyQueue에 순서대로 대기하고 있고, 각각의 프로세스들은 실행시간이 10초, 5초, 3초가 걸린다고 가정합니다

그렇다면 위 그림처럼 각각의 프로세스들은 종료될때까지 10초, 15초, 18초가 걸리게 됩니다.

평균 대기시간 : $0 + 10 + 15 / 3 = 약 8.3초$ 가 걸리는걸 확인할 수 있습니다.

이렇게 되면 P3는 실행까지 3초밖에 안걸리는데 조금 늦게 왔다는 이유로 15초나 기다려야하는 문제가 발생합니다.

위 문제를 해결하기 위해 다른 스케줄링 알고리즘을 알아보도록 합시다.

Shortest-Job-First(SJF)

• 실행시간이 짧은 작업 순서대로 처리하기
• 비현실적
• 프로세스 실행 시간에 대한 예측이 필요
• Preemptive 또는 Non-preemptive로 설정 가능

FCFS에서 살펴 보았듯이 평균 대기 시간이 오래 걸리기 때문에 실행 시간이 빠른 순서로 한다고 가정해 봅시다.

위 그림처럼 프로세스 실행 순서를 바꾼다면 평균 대기시간은 : $0 + 3 + 8 / 3 = 약 3.6초$ 가 걸리는것을 알 수 있습니다.

FCFS와 SJF를 비교해 보았을때 SJF가 평균대기시간(이하 AWT)이 더 짧게 걸립니다.

하지만 SJF 경우에는 하나의 프로세스의 실행시간이 얼마나 걸릴지 정확하게 모르기 때문에 비현실적이라는 문제점이 있습니다.

Non-preemptive SJF

• 비 선점형 SJF
• 프로세스가 Ready Queue에 도착하고 실행 중인 프로세스가 없으면 바로 실행
• 실행중인 프로세스가 있으면 Ready Queue에서 대기
• 하나의 프로세스가 실행 종료되면 Ready Queue에서 Burst Time이 가장 짧은 프로세스를 꺼내서 실행

Preemptive SJF

• 선점형 SJF
• 프로세스가 Ready Queue에 도착하고 실행 중인 프로세스가 없으면 바로 실행
• 프로세스가 실행 중일 때, 새로운 프로세스가 도착하면 실행중인 프로세스와 Ready Queue에 대기중인 프로세스의 BT를 비교해서 가장 짧은 BT를 가진 프로세스가 선점하여 실행

Priority Scheduling

• 프로세스별로 우선순위를 부여
• 부여된 우선순위를 기준으로 하여 우선순위가 높은 프로세스를 먼저 실행
• 여기서 말하는 우선순위는?
  • 내부적인 요소
    • 짧은 실행 시간
    • 메모리를 작게 차지하는 프로세스
    • I/O 사용시간이 길고 CPU 사용시간이 짧은 프로세스
  • 외부적인 요소
    • 지불하는 비용
    • 다른 외부적인 기준
• Preemptive 또는 Non-preemptive 가능
• 문제점
  • Starvation : 우선순위가 낮아서 대기하고 있는데 새로 들어온 프로세스가 우선순위가 높다면 계~~속 기다려야 한다
  • Starvation을 해결하기 위해서 Aging 기법을 사용한다.
  • Aging : 프로세스의 Ready Queue 도착 시간을 기준으로 하여 대기 시간에 따라 우선순위를 높여준다

Round-Robin(RR)

• Time-sharing System(시분할 / 시공유 시스템)에서 자주 사용
• Time Quantum을 기준으로 하여 CPU 할당
• Time Quantum동안 프로세스를 실행하고 다른 프로세스로 넘어가서 다시 TimeQuantum동안 실행
  • 위 과정을 반복해서 모든 프로세스들을 처리한다
• Preemptive
• Time Quantum을 얼마로 기준하느냐에 따라 성능이 좌우된다.
  • Time Quantum = 10000000000000 이라면
    • 거의 FCFS와 동일하게 동작가능
  • Time Quantum 이 0에 수렴하는 값이라면
    • 여러개의 프로세스를 바로바로 돌려가면서 실행하기 때문에 거의 동시에 실행하는것처럼 느껴짐 => Process Sharing
    • 하지만 Context Switching Overhead가 매우 커진다