[운영체제] CPU 스케줄링: 알고리즘의 평가 - (1)

 

알고리즘의 평가(Algorithm Evaluation)

---

 

- 시스템에 맞는 CPU 스케줄링 알고리즘을 선택하는 방법

 

1. 알고리즘을 선택하는 데 사용할 기준을 정의한다.

 

2. 선택 기준이 정의되면, 선택 기준에 따라 알고리즘들을 평가한다.

 

 

 

 

 

 

결정론적 모델링(Deterministic Modeling)

---

 

평가 방법 중 중요한 부류 중 하나가 분석적 평가(analytic evaluation)이다.

 

분석적 평가는 알고리즘 성능 평가하는 공식이나 값을 생성하기 위해 주어진 알고리즘과 시스템 부하를 이용한다.

 

 

결정론적 모델링(deterministic modeling)은 분석적 평가의 한 가지 유형이다.

 

이는 미리 정의된 특정 작업 부하를 이용하여 각 알고리즘의 성능을 정의한다.

 

 

결정론적 모델링의 장점은 단순하고 빠르고, 알고리즘 비교를 위한 정확한 값을 제공한다는 것이다.

 

결정론적 모델링의 단점은 입력으로 정확한 숫자를 요구하고, 결과 또한 입력된 경우에 대해서만 적용된다는 것이다.

 

 

결정론적 모델링은 주로 스케줄링 알고리즘을 설명하고, 예시를 제공할 때 사용된다.

 

또한 동일한 프로그램을 반복해 여러 번 실행하고, 프로그램의 처리 요구 사항들을 정확하게 측정할 수 있는 경우, 스케줄링 알고리즘을 선택하기 위해 결정론적 모델을 사용할 수도 있다.

 

 

 

https://www.freepik.com/vectors/illustrations - www.freepik.com

 

 

 

 

 

 

큐잉 모델(Queueing Models)

---

 

대부분의 시스템에서 실행되는 프로세스는 매일 달라진다.

 

따라서 결정론적 모델링을 사용할 수 있는 정적 프로세스 집합이 없다.

 

 

다음 두 분포로부터 대부분의 알고리즘에 대한 여러 값들을 계산할 수 있다.

 

1. CPU와 I/O bust의 분포

2. arrival-time 분포

 

 

도착률(arrival rate)과 서비스율(service rate)을 통해서 이용률(utilization), 평균 큐 길이, 평균 대기 시간 등을 계산할 수 있다.

 

이러한 분석을 큐잉 네트워크 분석(queueing-network analysis)이라고 한다.

 

 

- Little's formula

 

n을 평균 큐 길이라 하고, W를 큐에서의 평균 대기 시간이라 하고, $\lambda$를 새로운 프로세스들이 도착하는 평균 도착률이라고 하면,

 

$n = \lambda \times W$을 만족한다.

 

 

- 큐잉 모델의 한계

 

처리 가능한 알고리즘과 분포가 제한적이다.

 

복잡한 알고리즘과 분포의 수학적 분석이 어렵다.

 

실제 시스템의 근사치이므로, 계산 결과의 정확성에 의심의 여지가 있다.

 

 

 

 

 

 

모의실험(Simulation)

---

 

모의실험은 컴퓨터 시스템에 대한 모델을 프로그래밍하는 것을 포함한다.

 

 

- 모의실험을 위한 데이터 생성 방법

 

1. 난수 발생기(ramdom-number generator) 사용

 

2. 추적 파일(trace file) 사용

추척 파일은 실제 시스템을 모니터 해서 이벤트의 순서를 기록해놓은 파일이다.

 

 

- 모의 실험의 단점

 

컴퓨터를 오래 사용해야 하므로 큰 비용이 발생할 수 있다.

 

추적 파일은 대량의 저장 공간을 요구할 수 있다.

 

 

 

 

 

 

구현(Implementation)

---

 

실제 코드로 작성해 os에 넣고 실행해 보는 방법으로 알고리즘을 평가하는 유일하게 정확한 방법이다.

 

 

- 구현의 단점

 

비용이 많이 든다.

 

알고리즘 적용 환경이 바뀔 수 있다.