CPU 스케줄링 기법들의 구현 및 벤치마킹 프로그램을 통한 모의실험

프로젝트의 목적

ㆍ 다양한 스케줄링 알고리즘을 직접 구현해 봄으로써 각 스케줄링 기법의 동작 과정을 이해한다.

ㆍ 각 스케줄링 알고리즘의 간트차트를 분석하여 특성을 파악한다.

ㆍ 구현한 프로그램을 통해 모의실험을 함으로써 각 스케줄링 알고리즘을 평가해 본다.

---

프로젝트의 내용

ㆍ 여러 가지 스케줄링 기법에 대응하는 벤치마킹 프로그램을 구현한다.

ㆍ 구현한 벤치마킹 프로그램을 이용해 모의실험을 진행한다.

ㆍ 모의실험을 통해 각각의 스케줄링 기법을 평가한다.

---

스케줄링 알고리즘의 테스트

ㆍ 각 스케줄링 알고리즘을 공평하게 평가하기 위하여 위 표와 같은 입력 예제를 각 스케줄링 알고리즘에게 동일하게 주어 테스트를 진행하였다.
ㆍ 도착시간을 고려하지 않고 구현한 Round Robin 스케줄링은 형평성을 위해 테스트 과정에서 제외하였다.
ㆍ 각 스케줄링 알고리즘은 평균 대기시간, 평균 반환시간으로 평가를 하였다.

 

 

ㆍ 4가지 입력 예제에 대해 각 스케줄링 기법의 벤치마킹 프로그램으로 평균 대기시간을 구하고 표로 작성하였다.

 

 

ㆍ 4가지 입력 예제에 대해 각 스케줄링 기법의 벤치마킹 프로그램으로 평균 반환시간을 구하고 표로 작성하였다.

---

테스트 결과 분석

ㆍ 4가지 입력 예제에 대한 각 스케줄링 알고리즘의 평균 대기시간을 막대그래프로 표현해 보았다.
ㆍ 그래프에서 보이는 것처럼 4가지 입력 예제에 대해 FCFS, Non-Preemptive SJF, Preemptive SJF 순으로 평균 대기시간이 짧아지고 있다는 것을 확인할 수 있다.
ㆍ 대기시간이 스케줄링 알고리즘에 실질적으로 영향받는 요소임을 고려한다면 FCFS, Non-Preemptive SJF, Preemptive SJF 순으로 성능이 좋아지고 있다는 것을 확인할 수가 있다.

 

 

ㆍ 4가지 입력 예제에 대해 각 스케줄링 알고리즘의 실제 평균 반환시간을 막대그래프로 표현해 보았다.
ㆍ 그래프에서 보이는 것처럼 4가지 입력 예제에 대해 FCFS, Non-Preemptive SJF, Preemptive SJF 순으로 평균 반환시간이 짧아지고 있다는 것을 확인할 수 있다.
ㆍ 평균 반환시간을 기준으로 각각의 스케줄링 알고리즘을 평가해본다면 FCFS, Non-Preemptive SJF, Preemptive SJF 순으로 성능이 좋아지고 있다는 것을 확인할 수가 있다.

---

스케줄링 알고리즘의 분석과 평가

FCFS 스케줄링

ㆍ 각 프로세스는 도착시간에 따라 CPU에 할당되며, 비선점형 방식이기 때문에 CPU의 활용도가 떨어진다는 특성이 있다.
ㆍ 소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹는 부정적인 현상에 주의해야 한다.
ㆍ 가장 단순한 방식이며, 구현하기가 가장 수월했던 스케줄링 기법이다.

 

Non-Preemptive SJF 스케줄링

ㆍ 버스트 시간이 짧은 프로세스에게 CPU를 먼저 할당하는 방식이다.
ㆍ FCFS 스케줄링과 마찬가지로 비선점형 방식이기 때문에 여전히 CPU의 활용도가 떨어진다는 특성을 가지고 있다.
ㆍ FCFS 스케줄링과 비교하여 비교적 빠른 대기시간과 반환시간을 가지고 있다.

Preemptive SJF 스케줄링

ㆍ 현재 수행 중인 프로세스의 남은 버스트 시간보다 더 짧은 버스트 시간을 가진 프로세스가 도착하게 된다면, 현재 수행 중인 프로세스에게서 CPU를 빼앗아 새로 도착한 프로세스에게 CPU를 할당하는 방식의 기법이다.
ㆍ 선점형 방식이기 때문에 CPU 활용도가 좋으며, 앞서 설명한 두 가지 스케줄링 기법에 비해 최소한의 평균 대기시간을 제공해주고 있다.
ㆍ 프로세스의 선점과 같은 여러 상황을 고려해야 하기 때문에 구현하기가 가장 까다로웠던 스케줄링 기법이었다.

Round Robin Scheduling

ㆍ 각 프로세스가 Time Quantum이라 불리는 시간의 양에 의해 제한되어 실행된다는 특성을 가진 스케줄링 기법이다.
ㆍ Time Quantum의 크기가 너무 작으면 실행시간에 차지하는 오버헤드가 많아져서 전체 실행시간이 느려지는 현상이 발생 가능하다. 이 같은 상황을 고려해 적절한 Time Quantum이 필요하다.
ㆍ 도착시간을 고려하지 않고 구현을 하였기 때문에 구현상 큰 어려움이 없었다. 만약 도착시간을 고려하고 프로그램을 작성하였다면, 큰 어려움이 있었을 꺼라 생각한다.

---

GitHub - qlsdud0604/cpu-scheduler: 여러가지 CPU 스케줄링 기법들의 구현 및 벤치마킹 프로그램을 통한 모