5.8 Algorithm Evaluation

 이제 특정 시스템에 맞는 스케줄링 알고리즘을 선정해야 할 것이다. 이 전에 다양한 알고리즘을 봤는데 우리가 운용하고 싶은 시스템에 적합한 알고리즘이 어떤 것이 있고 어떤 걸 사용해야 가장 최적인지를 봐야 한다. 우선 알고리즘 선택 기준은 다음과 같다.

1. 최대 응답 시간이 300ms라는 제약 조건 하에서 CPU 활용도 극대화
2. 처리 시간이 (평균) 총 실행 시간에 선형적으로 비례하도록 처리량 극대화

 알고리즘이 선택됐다면 실제 그 알고리즘을 써보고 평가해야 할 것이다. 평가 방법을 보자.

5.8.1 Deterministic Modeling

 Analytic Evaluation 은 주어진 알고리즘과 시스템 작업 부하를 사용하여 해당 작업 부하에 대한 알고리즘의 성능을 평가하기 위한 공식 또는 숫자를 생성한다.

 Deterministic Modeling은 Analytic Evaluation의 한 일종이며, 미리 결정된 경우들을 통해 작업 부하에 대한 각 알고리즘의 성능을 평가한다. 결정론적 모델링은 간단하고 빠르며 테스트 케이스를 통해 우리에게 정확한 숫자를 제공하여 알고리즘을 비교할 수 있다. 하지만 입력에 대한 정확한 숫자가 필요하다. 결정론적 모델링의 주요 용도는 스케줄링 알고리즘을 설명하고 예제를 제공하는 것으로 쓰이며, 같은 프로그램을 반복해서 실행하고 프로그램의 처리 요구 사항을 정확하게 측정할 수 있는 경우, 결정론적 모델링을 사용하여 스케줄링 알고리즘을 선택할 수 있다. 결정론적 모델링을 통해 일련의 예제에 대해 경향을 보여줄 수 있으며, 이후 별도로 분석하고 증명할 수 있다. 예를 들어, 설명된 환경(시간 0에서 모든 프로세스 및 시간이 사용 가능한 상태)에서 SJF 정책이 항상 최소 대기 시간을 유발함을 보여줄 수 있다.

 

5.8.2 Queueing Models

 보통 많은 시스템에서 실행되는 프로세스는 날마다 다양하기 때문에 결정론적 모델링에서 사용할 정적 프로세스 집합이 없다. 하지만 CPU 버스트 및 I/O 버스트의 분포는 결정될 수 있다. 이런 분포를 통해서 버스트 시간을 조금이라도 나마 정확히 예측 혹은 근사화할 수 있을 것이다. 일반적으로 이 CPU burst 시간은 지수 분포(exponential distribution)를 따르고, 또 시스템에 프로세스가 도착하는 시간 분포 또한 arrival-time distribution을 통해 설명할 수 있을 것이다. 두 분포를 통해서 알고리즘에 대한 평균 처리량, 이용률, 대기 시간 등을 계산할 수 있다.

 컴퓨터 시스템의 지연 시간 등을 설명을 서버 네트워크를 통해서 보자. CPU는 ready queue를 가진 서버이며, I/O 시스템은 장치 대기열을 갖는 서버라고 할 수 있다. 도착률과 서비스률을 알고 있다면 이를 통해 이용률, 평균 대기열 길이, 평균 대기 시간 등을 계산할 수 있고, 이를 queueing-network analysis 라고 한다.

예를 들어, 𝑛을 평균 장기 대기열 길이(서비스 중인 프로세스를 제외), 𝑊를 대기열의 평균 대기 시간, 𝜆를 대기열에 새로운 프로세스의 평균 도착률( ~ 개/sec )로 정의해보자. 프로세스가 대기하는 동안 𝑊시간 동안 예상되는 𝜆×𝑊 개의 새로운 프로세스가 대기열에 도착할 것으로 예상된다고 할 수 있다. 시스템이 안정 상태에 있다면, 대기열을 떠나는 프로세스 수는 도착하는 프로세스 수와 같아야 한다. 따라서, 𝑛 = 𝜆×𝑊 이며, 이 방정식을 Little's formula 라고 부른다, 모든 스케줄링 알고리즘과 도착 분포에 대해 쓸 수 있다.

 리틀의 정리를 사용하여 세 변수 중 두 변수만 알고 있다면 다른 하나 변수를 계산할 수 있다. 예를 들어, 평균적으로 매 초 7개의 프로세스가 도착( 7 개/sec )하고 대기열에는 보통 14개의 프로세스( 14 개 )가 있을 때, 각 프로세스의 평균 대기 시간을 2초로 계산할 수 있다.

 대기열 분석은 스케줄링 알고리즘을 비교하는 데 유용할 수 있지만, 현재로서는 다룰 수 있는 알고리즘과 분포의 클래스가 상당히 제한적이고, 복잡한 알고리즘 및 분포의 수학적인 작업은 어려울 수 있다. 따라서 도착 및 서비스 분포는 수학적으로 처리 가능하지만 현실적이지 않은 방식으로 정의될 수 있고, 일련의 독립적인 가정을 필요로 하기 때문에 이는 정확하지 않을 수 있다. 이런 한계로 인해 대기열 모델은 종종 실제 시스템의 근사값에 불과하며, 계산 결과의 정확성이 떨어질 수 있다.

 

5.8.3 Simulation

 위의 확률에서 더 나아가 다양한 평가를 얻을 수 있는 시뮬레이션 실행이 있다. 시뮬레이션을 하기 위해서는 시뮬레이터라고 컴퓨터 시스템의 모델을 프로그래밍하고, 시뮬레이터는 시계를 가지고 있기 때문에 이 시간을 나타내는 변수의 값이 증가함에 따라 장치, 프로세스 및 스케줄러의 활동을 반영하기 위해 시스템 상태를 수정하게 되며, 시뮬레이터는 시뮬레이션이 실행되는 동안 알고리즘 성능을 나타내는 통계를 수집하고 결과를 출력하게 된다.

 시뮬레이션을 구동하기 위한 데이터는 여러 가지 방법으로 생성할 수 있다. 가장 일반적인 방법은 확률 분포에 따라 프로세스, CPU 버스트 시간, 도착, 출발 등을 생성하기 위해 프로그래밍된 난수 생성기를 사용하는 것이며, 분포는 위에서도 봤다시피 수학적으로 정의될 수 있고(균일, 지수, 포아송) 또는 경험적(디렉-델타, 딥러닝 모델)으로 정의될 수도 있다. 분포가 경험적으로 정의되어야 하는 경우, 연구 중인 실제 시스템의 측정 값을 사용하며, 결과는 실제 시스템의 사건 분포를 정의하며, 이 분포를 시뮬레이션에 이용한다.

 분포에 기반한 시뮬레이션은 실제 시스템의 연속적인 사건 간의 관계 때문에 정확하지 않을 수 있다(어떤 사건들이 다른 사건에 영향을 많이 끼칠 수 있는 컴퓨터 시스템에서 사건 각각이 독립인 분포에서 생성한 난수들과 맞지 않을 수 있다는 것임). 빈도 분포는 각 사건이 얼마나 자주 발생하는지만 나타내며, 발생 순서에 대한 정보를 포함하지 않는다. 이 문제를 해결하기 위해 추적 파일을 사용할 수 있다. 실제 시스템을 모니터링하고 실제 사건의 순서를 기록하여 추적을 생성하며, 그런 다음 이 시퀀스, 시나리오를 사용하여 시뮬레이션을 구동한다. 추적 파일은 두 알고리즘을 정확히 동일한 실제 입력 집합에서 비교하는데 적합하다. 이 방법은 입력 값에 대해 정확한 결과를 얻을 수 있게 된다.

 시뮬레이션은 비용이 많이 들지만 그만큼 정확하게 알고리즘을 평가할 수 있도록 한다.