알고리즘 평가
결정론적 모델링
평가 방법의 주요 범주 중 하나는 **분석적 평가(analytic evaluation)**입니다. 분석적 평가는 주어진 알고리즘과 시스템 워크로드를 사용하여 해당 워크로드에 대한 알고리즘의 성능을 평가하는 공식이나 숫자를 도출합니다.
**결정론적 모델링(deterministic modeling)**은 분석적 평가의 한 유형입니다. 이 방법은 특정 미리 정해진 워크로드를 사용하고 해당 워크로드에 대한 각 알고리즘의 성능을 정의합니다. 예를 들어, CPU 버스트 시간이 밀리초 단위로 주어진 프로세스 집합이 있다고 가정할 수 있습니다. 각 스케줄링 알고리즘(FCFS, SJF, RR 등)을 이 프로세스 집합에 적용하여 평균 대기 시간을 계산하고 비교할 수 있습니다.
결정론적 모델링은 간단하고 빠릅니다. 이는 정확한 숫자를 제공하여 알고리즘을 비교할 수 있게 합니다. 그러나 입력에 정확한 숫자가 필요하며, 그 결과는 해당 경우에만 적용됩니다. 결정론적 모델링의 주요 용도는 스케줄링 알고리즘을 설명하고 예시를 제공하는 것입니다. 동일한 프로그램을 반복해서 실행하고 프로그램의 처리 요구 사항을 정확하게 측정할 수 있는 경우, 결정론적 모델링을 사용하여 스케줄링 알고리즘을 선택할 수 있습니다. 또한, 여러 예시를 통해 결정론적 모델링은 추세를 나타낼 수 있으며, 이는 나중에 분석되고 개별적으로 증명될 수 있습니다.
큐잉 모델
많은 시스템에서 실행되는 프로세스는 매일 다르므로, 결정론적 모델링에 사용할 정적 프로세스 집합이나 시간이 없습니다. 그러나 CPU 및 I/O 버스트 분포는 결정할 수 있습니다. 이러한 분포는 측정된 다음 근사하거나 단순히 추정할 수 있습니다. 결과는 특정 CPU 버스트의 확률을 설명하는 수학적 공식입니다. 일반적으로 이 분포는 지수적이며 그 평균으로 설명됩니다. 마찬가지로, 프로세스가 시스템에 도착하는 시간의 분포(도착 시간 분포)를 설명할 수 있습니다. 이 두 분포로부터 대부분의 알고리즘에 대한 평균 처리량, 활용률, 대기 시간 등을 계산할 수 있습니다.
컴퓨터 시스템은 서버 네트워크로 설명됩니다. 각 서버에는 대기 중인 프로세스 큐가 있습니다. CPU는 준비 큐를 가진 서버이며, I/O 시스템도 장치 큐를 가집니다. 도착률과 서비스율을 알면 활용률, 평균 큐 길이, 평균 대기 시간 등을 계산할 수 있습니다. 이 연구 분야를 **큐잉 네트워크 분석(queueing-network analysis)**이라고 합니다.
**리틀 공식(Little’s formula)**은 n = λ × W로 정의되며, n은 평균 장기 큐 길이(서비스 중인 프로세스 제외), W는 큐에서의 평균 대기 시간, λ는 큐에 새로운 프로세스가 도착하는 평균 도착률입니다. 이 방정식은 모든 스케줄링 알고리즘 및 도착 분포에 대해 유효하므로 특히 유용합니다.
큐잉 분석은 스케줄링 알고리즘을 비교하는 데 유용하지만 한계도 있습니다. 현재 처리할 수 있는 알고리즘 및 분포 클래스는 상당히 제한적입니다. 복잡한 알고리즘 및 분포의 수학은 다루기 어려울 수 있습니다. 따라서 도착 및 서비스 분포는 종종 수학적으로 다루기 쉬운 (그러나 비현실적인) 방식으로 정의됩니다. 또한, 정확하지 않을 수 있는 여러 독립적인 가정을 할 필요가 있습니다. 이러한 어려움 때문에 큐잉 모델은 종종 실제 시스템의 근사치일 뿐이며, 계산된 결과의 정확성은 의심스러울 수 있습니다.
시뮬레이션
스케줄링 알고리즘에 대한 더 정확한 평가를 얻기 위해 **시뮬레이션(simulations)**을 사용할 수 있습니다. 시뮬레이션을 실행하는 것은 컴퓨터 시스템 모델을 프로그래밍하는 것을 포함합니다. 소프트웨어 데이터 구조는 시스템의 주요 구성 요소를 나타냅니다. 시뮬레이터에는 시계를 나타내는 변수가 있습니다. 이 변수의 값이 증가함에 따라 시뮬레이터는 시스템 상태를 수정하여 장치, 프로세스 및 스케줄러의 활동을 반영합니다. 시뮬레이션이 실행됨에 따라 알고리즘 성능을 나타내는 통계가 수집되어 인쇄됩니다.
시뮬레이션을 구동하는 데이터는 여러 가지 방법으로 생성될 수 있습니다. 가장 일반적인 방법은 확률 분포에 따라 프로세스, CPU 버스트 시간, 도착, 출발 등을 생성하도록 프로그래밍된 난수 생성기를 사용하는 것입니다. 분포는 수학적으로 정의되거나 경험적으로 정의될 수 있습니다.
그러나 분포 기반 시뮬레이션은 실제 시스템에서 연속적인 이벤트 간의 관계로 인해 정확하지 않을 수 있습니다. 빈도 분포는 각 이벤트가 몇 번 발생하는지만 나타내며, 발생 순서에 대해서는 아무것도 나타내지 않습니다. 이 문제를 해결하기 위해 **트레이스 파일(trace files)**을 사용할 수 있습니다. 트레이스 파일은 실제 시스템을 모니터링하고 실제 이벤트 시퀀스를 기록하여 생성됩니다. 그런 다음 이 시퀀스를 사용하여 시뮬레이션을 구동합니다. 트레이스 파일은 동일한 실제 입력 세트에서 두 알고리즘을 비교하는 훌륭한 방법을 제공합니다. 이 방법은 해당 입력에 대해 정확한 결과를 산출할 수 있습니다.
시뮬레이션은 비용이 많이 들 수 있으며, 종종 몇 시간의 컴퓨터 시간이 필요합니다. 더 자세한 시뮬레이션은 더 정확한 결과를 제공하지만, 더 많은 컴퓨터 시간도 소요됩니다. 또한, 시뮬레이터의 설계, 코딩 및 디버깅은 주요 작업이 될 수 있습니다.
구현
시뮬레이션조차도 정확도가 제한적입니다. 스케줄링 알고리즘을 평가하는 유일하게 완전히 정확한 방법은 알고리즘을 코딩하고 운영체제에 넣어 어떻게 작동하는지 확인하는 것입니다. 이 접근 방식은 실제 운영 조건에서 평가하기 위해 실제 시스템에 실제 알고리즘을 적용합니다.
이 방법에는 비용이 수반됩니다. 알고리즘을 코딩하고 운영체제를 수정하여 이를 지원하는 데 비용이 발생합니다. 또한 변경 사항을 테스트하는 데도 비용이 발생합니다.
또한, 알고리즘이 사용되는 환경이 변경될 수 있습니다. 환경은 새로운 프로그램이 작성되고 문제 유형이 변경되는 일반적인 방식뿐만 아니라 스케줄러의 성능 결과로도 변경됩니다. 이 문제는 일반적으로 완전한 작업 세트를 캡슐화하는 도구 또는 스크립트를 사용하고, 이러한 도구를 반복적으로 사용하며, 결과를 측정하면서 이러한 도구를 사용하는 방식으로 해결됩니다.
일반적으로 가장 유연한 스케줄링 알고리즘은 시스템 관리자나 사용자가 특정 애플리케이션 또는 애플리케이션 세트에 맞게 조정할 수 있는 알고리즘입니다. 다른 접근 방식은 프로세스 또는 스레드의 우선순위를 변경할 수 있는 API를 사용하는 것입니다. 이 접근 방식의 단점은 시스템 또는 애플리케이션 성능 조정이 일반적으로 더 일반적인 상황에서 성능 향상을 가져오지 않는다는 것입니다.
Last updated