운영체제에서 CPU Scheduling은 ready 상태에 있는 여러 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정하는 과정이다. 멀티프로그래밍 환경에서는 여러 프로세스가 번갈아 실행되기 때문에 CPU를 어떤 기준으로 누구에게 줄지 정하는 스케줄링이 중요하며, 보는 관점에 따라 job scheduling 이라고도 한다.
Basic Concepts
CPU utilization과 multiprogramming
운영체제의 중요한 목표 중 하나는 CPU를 쉬게하지 않고 최대한 바쁘게 유지하는 것이다. CPU가 놀고 있으면 시스템 자원이 낭비되므로 CPU utilization을 높이는 게 중요하다.
이를 위해 사용하는 방식이 multiprogramming이다. 여러 프로세스를 메모리에 올려 두고, 어떤 프로세스가 I/O를 기다리는 동안 CPU가 다른 프로세스를 실행할 수 있게 한다. 한 프로세스가 멈춰 있어도 CPU는 다른 일을 계속 한다. 즉 이런 multiprogramming 환경에서는 CPU가 프로세스를 선택해야한다. 이게 scheduling이다.
CPU–I/O Burst Cycle
위 그림을 살펴보면, 프로세스의 실행은 CPU-burst와 I/O-burst가 반복되는 cycle을 가진다.
I/O작업은 상대적으로 느리기 때문에 CPU는 I/O작업 완료까지 기다리지 않고, scheduling으로 다른 프로세스를 잡아 실행하기 때문이다.
- CPU-burst: 프로세스가 CPU를 점유해서 실제로 연산을 수행하는 시간
- I/O-burst: 프로세스가 CPU를 사용하지 않고, I/O 작업 완료를 기다리는 시간
프로세스는 실행 내내 CPU만 사용하는 게 아니다. 보통 이런 흐름을 반복한다.
- CPU에서 명령 수행
- I/O 요청 발생
- I/O 완료를 기다림
- 다시 CPU에서 실행
CPU burst distribution
위 CPU burst time의 분포를 보면 짧은 CPU burst는 많고 긴 CPU burst는 적다는 특징이 있다. 즉 대부분의 프로세스는 짧은 CPU burst를 가진다.
CPU Scheduler와 Dispatcher
CPU Scheduler
CPU Scheduler는 메모리에 있는 프로세스들 중 ready 상태에 있는 프로세스들 중 하나를 골라 CPU를 할당하는 역할을 한다.
CPU 스케줄링 결정은 보통 다음 네 가지 시점에 발생한다.
- running → waiting — 실행 중이던 프로세스가 I/O 요청 등으로 기다리게 되는 경우
- running → ready — 실행 중이던 프로세스가 선점되어 준비 상태로 돌아가는 경우
- waiting → ready — I/O가 끝나서 다시 실행 준비 상태가 되는 경우
- terminates — 프로세스가 종료되는 경우
Nonpreemptive vs Preemptive
스케줄링은 크게 두 가지로 나뉜다.
Nonpreemptive scheduling은 CPU를 한 번 할당받은 프로세스가 스스로 CPU를 놓을 때까지 계속 실행되는 방식이다. 앞서 본 네 가지 시점 중 1번과 4번에 해당하는 경우는 nonpreemptive scheduling인데, 1번은 프로세스가 스스로 CPU를 놓는 경우이고, 4번은 프로세스가 끝났으니 당연히 넘겨야하기 때문이다.
Preemptive scheduling은 운영체제가 현재 실행 중인 프로세스로부터 CPU를 강제로 빼앗아 다른 프로세스에 할당할 수 있는 방식이다. running → ready나 waiting → ready 상황에서 preemptive scheduling이 가능하다.
즉 직관적으로 말하자면 Nonpreemptive는 뺏지 않고, Preemptive는 중간에 뺏을 수 있다는 느낌으로 이해하면 좋을것같다.
Dispatcher
CPU scheduler가 "누가 실행될지" 결정하면, Dispatcher는 실제로 CPU를 그 프로세스에게 넘겨주는 역할을 한다.
Dispatcher가 수행하는 작업은 context switching, user mode로 전환, 선택된 프로세스의 적절한 위치로 점프하여 실행 재개다. 단순히 "다음은 이 프로세스"라고 고르는 것만이 아니라, 실제로 그 프로세스가 이어서 실행될 수 있도록 상태를 복구해 주는 역할까지 한다.
- Dispatch latency: 한 프로세스를 멈추고 다른 프로세스를 실행하기 시작할 때까지 걸리는 시간
Scheduling Criteria
CPU 스케줄링 알고리즘은 다음과 같은 여러 기준으로 평가된다.
- CPU utilization — CPU 이용률. 최대화가 목표.
- Throughput — 단위 시간당 완료된 프로세스 수. 최대화가 목표.
- Turnaround time — 프로세스가 도착해서 완전히 끝날 때까지 걸린 전체 시간. ready queue 대기 시간, CPU 실행 시간, I/O 대기 시간이 모두 포함. 최소화가 목표.
- Waiting time — 프로세스가 ready queue에서 기다린 시간. 최소화가 목표.
- Response time — 요청이 들어온 뒤 첫 번째 응답이 나오기까지 걸리는 시간. 전체 작업이 끝날 때까지의 시간이 아니라 처음 반응이 나올 때까지의 시간. 최소화가 목표.
이제부터는 scheduling algorithms에 대해 살펴볼 것이다.
FCFS Scheduling
FCFS(First-Come, First-Served)는 이름 그대로 먼저 도착한 프로세스를 먼저 실행하는 방식이다. 즉 queue 자료구조처럼 먼저 들어온 프로세스에 CPU를 할당하고, 실행이 끝나면 다음 프로세스를 실행한다.
도착 순서가 P1 → P2 → P3일 때, 간트차트를 그려보면 위와 같다. 위 예시의 경우 average waiting time이 17임을 알 수 있다.
반면 도착순서가 P2 → P3 → P1인 경우, average waiting time이 3이 된다.
즉, 같은 burst time을 가진 프로세스들이더라도 도착 순서가 달라지면 평균 waiting time이 크게 달라질 수 있다.
Convoy effect
FCFS의 대표적인 단점은 Convoy effect다. 짧은 프로세스들이 긴 프로세스 뒤에서 줄줄이 기다리는 현상이다. 덩치가 큰 놈이 먼저 들어오고 작은 놈들이 그 이후에 들어오면 덩치가 큰 놈을 먼저 처리하느라 다른 놈들의 waiting time이 너무 길어진다. 즉 FCFS는 단순하지만 average waiting time 측면에서 비효율적일 수 있다.
SJF Scheduling
개념
SJF(Shortest-Job-First)는 각 프로세스의 다음 CPU burst 길이를 기준으로 가장 짧은 작업을 먼저 실행하는 방식이다. FCFS의 convoy effect를 보완한 방식이라고 할 수 있겠다.
두 가지 방식이 있다.
- Nonpreemptive SJF — 한 번 CPU를 할당받은 프로세스는 자신의 CPU burst가 끝날 때까지 실행된다. 즉 이미 CPU한테 넘어간 작업은 건들지 않는다.
- Preemptive SJF(SRTF) — 현재 실행 중인 프로세스보다 더 짧은 burst를 가진 프로세스가 새로 도착하면 선점한다. SRTF(Shortest-Remaining-Time-First)라고도 부른다.
즉 SJF는 average waiting time을 최소화하는 알고리즘이다.
Non-Preemptive SJF 예시
t0에는 P1만 있으므로 P1 실행. Nonpreemptive이므로 P1은 끝날 때까지 계속 실행된다. P1이 끝난 뒤 ready queue에서 가장 짧은 burst를 가진 P3부터 실행된다.
Preemptive SJF(SRTF) 예시
같은 프로세스 집합에 SRTF를 적용하면 이렇게 진행된다.
- 0~2 — P1만 있으므로 P1 실행. P1 남은 시간 = 5
- t2 — P2 도착(burst 4). P1 남은 시간 5 > 4이므로 P2가 선점
- 2~4 — P2 실행. P2 남은 시간 = 2
- t4 — P3 도착(burst 1). P2 남은 시간 2 > 1이므로 P3가 선점
- 4~5 — P3 실행 후 종료
- 시간 5 — P4 도착(burst 4). ready queue: P1(5), P2(2), P4(4). 가장 짧은 P2 실행
- 5~7 — P2 종료. 남은 P1(5), P4(4). P4 실행
- 7~11 — P4 종료. P1 실행
- 11~16 — P1 종료
이 경우 average waiting time이 nonpreemptive SJF다 더 작은 반면, context switch overhead는 늘어난 것을 확인할 수 있다.
Determining length of next CPU burst
SJF는 다음에 들어오는 프로세스의 CPU burst 길이를 정확히 알 수 없다는 문제가 있다. 그래서 운영체제는 이전 CPU burst를 이용해 다음 burst를 예측한다. -> Exponential averaging
t(n)— 실제 n번째 CPU burst 길이τ(n+1)— 다음 CPU burst의 예측값α— 가중치 (0 ≤ α ≤ 1)
즉 공식을 보면 알 수 있듯 다음 예측값은 가장 최근의 실제값과 이전까지의 예측값을 섞어 최근 기록도 반영하고 과거 추세도 반영하는 형태이다.
α = 0이면 τ(n+1) = τ(n) — 최근 실제 burst는 전혀 반영되지 않고 과거 예측만 유지된다.
α = 1이면 τ(n+1) = t(n) — 오직 마지막 실제 burst만 반영되고 과거 정보는 무시된다.
공식을 전개하면 오래된 과거일수록 가중치가 점점 작아진다. 최근 CPU burst는 더 크게 반영되고 오래된 burst는 덜 반영된다. burst 길이가 변하더라도 예측값이 너무 급격히 흔들리지 않으면서 최근 경향도 반영할 수 있다.
Priority Scheduling
Priority Scheduling은 각 프로세스에 우선순위 번호를 부여하고, 가장 높은 우선순위의 프로세스에게 CPU를 할당하는 방식이다. 일반적으로 숫자가 작을수록 높은 우선순위로 정의하나, 경우에 따라 달라질 수 있다.
Preemptive 방식에서는 더 높은 우선순위의 프로세스가 ready queue에 들어오면 현재 실행 중인 프로세스를 선점한다. Nonpreemptive 방식에서는 한 번 시작한 프로세스는 끝날 때까지 CPU를 유지한다.
SJF는 사실 priority scheduling의 한 형태로 볼 수 있다. CPU burst 길이를 우선순위처럼 사용하기 때문이다. burst가 짧을수록 우선순위가 높다고 볼 수 있다.
Starvation과 Aging
Priority scheduling의 대표적인 문제는 Starvation이다. 우선순위가 낮은 프로세스는 계속 더 높은 우선순위 프로세스들에게 밀려서 영원히 실행되지 못할 수 있다.
이를 해결하는 대표적인 방법이 Aging이다. 기다리는 시간이 길어질수록 프로세스의 우선순위를 점점 높여 준다. 그러다보면 언젠가는 처음에 우선순위가 낮았던 프로세스들도 결국 실행될 것이다.
Round Robin Scheduling
Round Robin(RR)은 모든 프로그램이 공평하게 정해진 시간(time quantum)만큼 돌아가며 CPU를 사용하고, 시간이 끝나면 ready queue의 맨 뒤로 가서 다시 줄을 서는 방식이다.
즉 이 time quantum 값이 크면 클수록 FIFO처럼 동작하고, 작으면 작을수록 context switch overhead가 증가한다.
time quantum이 20일때의 예시를 살펴보자.
P1, P2, P3, P4 순서로 들어온다고 했을때, P1은 53 중 time quantum인 20만큼만 쓰고 남은 33은 남겨둔 채 CPU는 P2에게 할당되고, P1은 다시 ready queue의 맨 뒤로 가서 줄을 선다. P2는 burst time이 time quantum보다 작으므로 17만에 한번에 실행이 끝난다.
RR은 일반적으로 SJF보다 평균 turnaround time은 크다. 하지만 response time은 더 좋다. 모든 프로세스가 오래 기다리지 않고 빠르게 한 번씩 CPU를 받기 때문이다. 평균 완료 시간만 보면 SJF가 유리하고, 처음 반응 속도는 RR이 유리하다.
Time Quantum과 Turnaround Time
RR에서 time quantum의 크기는 매우 중요하다.
Quantum이 큰 경우
프로세스의 실행 시간이 10인데 quantum이 12라면 그 프로세스는 한 번의 quantum 안에 끝난다. context switch가 거의 발생하지 않아서 동작이 FCFS와 비슷해진다. quantum이 너무 크면 RR의 특성이 약해지고 FIFO처럼 동작한다.
Quantum이 작은 경우
quantum이 1이라면 프로세스는 1 단위로 아주 잘게 나뉘어 실행된다. context switch가 매우 자주 발생한다. response는 좋아질 수 있지만 context switch overhead가 너무 커진다. CPU가 실제 작업보다 전환 작업에 시간을 더 많이 쓸 수도 있다.
Turnaround time과 quantum의 관계
RR에서 turnaround time은 time quantum 값에 따라 달라진다. quantum이 작아지면 응답성은 좋아질 수 있지만 context switch가 증가해서 전체 완료 시간에 악영향을 줄 수 있다. quantum이 너무 크면 context switch는 줄지만 뒤에 있는 프로세스들이 첫 실행 기회를 늦게 받는다. turnaround time은 단순히 quantum이 크다고 무조건 좋아지지도 않고, 작다고 무조건 좋아지지도 않는다.
Rule of Thumb
Time quantum should be large enough so that 90% of jobs finish in one time quantum.
즉 q를 너무 작게 잡지말고 전체 작업의 90% 정도는 한번의 quantum 안에서 끝날 수 있을만큼 충분히 크게 잡아야한다는 말이다. 앞선 예시에서 P2처럼 한번에 끝날 수 있는 작업이 전체 프로세스 집합 중 90% 정도가 되어야 한다는 의미이다.
앞서 학습했던 기본 스케줄링 알고리즘들은 보통 하나의 ready queue를 전제로 설명된다. 하지만 하나의 ready queue만으로는 다양한 성격의 프로세스를 처리하기 어렵다는 문제가 생긴다. 그래서 ready queue를 성격에 따라 여러 개로 나눠 운영하는 CPU scheduling 기법이 등장한다.
Multilevel Queue
Multilevel Queue에서는 ready queue를 여러 개로 나눈다.
- foreground (interactive)
- background (batch)
그리고 각 queue마다 서로 다른 스케줄링 알고리즘을 적용할 수 있다.
- foreground: RR — 대화형(Interactive) 작업이 모이는 foreground queue에는 response time을 줄이기 위해 RR을 적용한다.
- background: FCFS — 일괄처리(Batch) 작업이 모이는 background queue에는 FCFS를 적용한다.
즉 프로세스의 성격에 따라 아예 다른 방식으로 CPU를 스케줄링하는 것이다.
Queue들 사이의 스케줄링
이렇게 queue를 여러 개로 나누면, queue에 있는 프로세스들 사이에서의 스케줄링뿐만 아니라 queue들 사이의 스케줄링도 필요해진다. 방식은 크게 두 가지다.
1) Fixed Priority Scheduling
우선순위가 높은 queue를 먼저 모두 처리하고, 그 다음 낮은 queue를 처리하는 방식이다. 예를 들어 foreground 큐가 background 큐보다 우선이면, foreground에 작업이 계속 들어오는 동안 background는 계속 실행되지 못할 수 있다. 즉 starvation 문제가 발생할 수 있다.
2) Time Slice 방식
각 queue별로 일정 비율의 CPU 시간을 할당해주는 방식이다.
foreground: 80%
background: 20%이렇게 하면 높은 우선순위 queue를 더 우대하면서도, 낮은 queue가 완전히 굶는 문제를 줄일 수 있다.
Multilevel Feedback Queue
기본적인 multilevel queue 환경에서는 우선순위가 낮은 queue에 있는 작업의 starvation 문제가 발생할 수 있다. 따라서 이를 보완하기 위해 프로세스가 위아래 queue를 왔다갔다 이동(feedback)할 수 있게 만든 Multilevel Feedback Queue가 등장한다.
각 queue마다 위쪽 queue로 향하는 path를 통해 multilevel feedback queue를 구현한다. 위쪽 queue로 이동할 때마다 aging을 적용해서 starvation 문제를 해결한다.
MLFQ를 구현하기 위한 고려사항들
- queue를 몇 개 둘 것인지
- 각 queue 안에서는 어떤 스케줄링 알고리즘을 쓸지
- 언제 더 낮은 queue로 내릴 것인지
- 언제 더 높은 queue로 올릴 것인지
- 새 프로세스나 인터럽트 또는 I/O 작업이 끝나고 온 프로세스를 어느 queue로 넣을 것인지
MLFQ 예시
Q0: RR, time quantum = 8ms
Q1: RR, time quantum = 16ms
Q2: FCFS동작 과정은 이렇다.
1) 새 작업은 Q0에 들어간다 — 가장 높은 우선순위 queue에서 먼저 실행 기회를 준다.
2) 8ms 안에 끝나지 않으면 Q1로 내려간다 — 짧은 작업은 위에서 빨리 끝나고, 오래 걸리는 작업은 아래로 내려간다.
3) Q1에서도 16ms 안에 끝나지 않으면 Q2로 내려간다 — Q2에서는 FCFS로 처리된다.
즉 가장 위의 queue의 time quantum값이 8이므로, q=8 이내에 작업이 안 끝나면 밑의 queue로 가고, 여기서 q=16 이내에 작업이 안 끝나면 밑의 queue로 가는 구조다.
이 예시는 SJF 알고리즘이라고 할 수 있다. 우선순위의 기준을 작업량이 작은 것으로 본다면 Priority Algorithm이라고도 할 수 있다.
Multiple-Processor Scheduling
지금까지는 CPU가 하나인 경우를 기준으로 스케줄링을 봤으나 실제 시스템은 CPU가 여러 개일 수 있으므로 multiprocessor 환경에서 스케줄링이 어떻게 달라지는지도 봐야 한다.
Asymmetric Multiprocessing
- 프로세서들 간에 master와 slave 관계가 존재
- 오직 한 master 프로세서만 전체 데이터 구조에 접근해 모든 스케줄링 전담 가능
- 나머지 slave 프로세서들은 master가 던져주는 작업만 처리
Symmetric Multiprocessing (SMP)
- 모든 프로세서가 동질적(Homogeneous)이며 master-slave 구분이 없음
- 각 CPU가 자신의 작업이 끝나면 전체 queue를 직접 확인하고, 스스로 스케줄링을 수행해 일감을 가져옴
Load Sharing
여러 CPU들에게 작업을 할당하는 방식은 두 가지가 있다.
- Push migration — 비대칭적 구조에서 master CPU가 slave CPU들한테 일감을 밀어넣어주는 방식
- Pull migration — 대칭적 구조에서 작업이 끝난 CPU가 전체 queue에 쌓여있는 일감들을 직접 들여다보고 스케줄링해 끌어오는 방식
Processor Affinity
가능하면 한 프로세스를 같은 CPU에서 계속 실행시키자는 개념이다.
모든 CPU는 자신만의 독립적인 캐시를 갖고 있는데, 만약 1번 프로세스가 1번 CPU에서 처리되고 있었다면 1번 CPU의 캐시에는 해당 프로세스의 실행과 관련된 유용한 데이터들이 많이 저장돼있게 된다. 따라서 1번 프로세스가 I/O 작업 등으로 잠시 중단됐다가 다시 실행될 때, 이전에 실행됐던 1번 CPU에 다시 할당받게 되면 Cache Hit Ratio가 높아지고 처리속도가 빨라지고 효율이 높아진다.
즉 cache hit ratio를 높이기 위한 전략이다.
Cache Hit Ratio: 특정 프로세스를 실행할 때 필요한 유용한 데이터가 해당 CPU의 로컬 캐시 메모리 안에 이미 존재할 확률
Processor affinity를 구현하는 방식은 두 가지가 있다.
- Hard affinity — 반드시 이전에 실행됐던 해당 CPU에 다시 할당되도록 보장해주는 방식
- Soft affinity — 이전 CPU에 다시 할당해주기 위한 노력은 하지만, 상황에 따라 보장까지는 해주지 못하는 방식
Thread Scheduling
CPU는 스케줄링 시 kernel thread만 본다. user thread는 직접 보지 못한다. 그래서 user thread가 실행되려면 LWP(Lightweight Process)와 매핑되어야 한다.
Local Scheduling
user level에서 발생하는 스케줄링이다. 여러 user level thread들은 CPU 작업을 수행하기 위해 먼저 LWP를 할당받기 위한 경합을 거치게 되며, 특정 user thread가 LWP를 차지하도록 선택하는 과정이 local scheduling이다.
Global Scheduling
kernel level에서 발생하는 스케줄링이다. 특정 user level thread가 local scheduling을 통해 LWP에 할당되고 나면, 해당 LWP는 밑에 있는 kernel level thread랑 1:1로 매핑돼 작업이 커널로 전달된다. CPU 입장에서는 이제 여러 개의 kernel level thread들이 존재하는 상태가 되는데, 이들 중 어떤 thread를 잡아당겨 실제 일감을 처리해줄 것인지 스케줄링하는 과정이 global scheduling이다.
Real-Time Scheduling
실시간 스케줄링이라고도 불리며, 특정 작업이 일정한 시간 제약 내 처리되어야 하는 환경에서 사용된다. 그 제약을 얼마나 엄격하게 지켜야 하는지에 따라 두 가지로 나뉜다.
- Hard Real-Time — 주어진 정해진 시간 내 작업이 반드시 끝난다는 걸 완벽히 보장해주는 시스템이다.
- Soft Real-Time — 실시간 작업에 가장 높은 우선순위를 부여해 최대한 빠르게 처리해주려고 노력하지만, 정해진 시간 내에 끝난다고 확실하게 보장해주지는 않는 시스템이다.
Operating System Examples
이제 이론적 내용이 아니라 실제 운영체제가 이를 어떻게 구현하는지 사례를 살펴보자. 예시로 나오는 운영체제는 Solaris, Windows XP, Linux다.
Solaris2 Scheduling
Solaris는 클래스별로 queue를 분리하며, 우선순위에 따라 크게 3가지 클래스로 나눈다.
- real time
- system
- interactive & time sharing
Solaris에는 Dispatch Table이라는 스케줄링 지침서가 있다. 프로세스의 현재 상황에 맞춰 우선순위와 time quantum을 어떻게 변경하고 조정할 것인지 세밀하게 규정해놓은 테이블이다.
Solaris에서는 priority 숫자가 높을수록 우선순위가 높다. 반면 time quantum은 작을수록 우선순위가 높다. 즉 우선순위가 높은 작업에는 짧은 time quantum을, 우선순위가 낮은 작업에는 긴 time quantum을 할당하는 반비례 정책을 사용한다.
또한 I/O 작업이 끝난 프로세스에는 우선순위를 상대적으로 매우 높게 다시 부여해 CPU를 즉시 할당받을 수 있게 해준다.
Windows XP Priorities
Windows XP는 우선순위를 단일 숫자 하나로만 다루지 않고 Priority Class + Relative Priority 구조로 관리한다. 6개의 우선순위 클래스로 나누고, 한 클래스 내에서도 thread별로 7단계로 구분한다.
Linux Scheduling
Linux는 Time-sharing 환경과 Real-time 환경을 구분해 각기 다른 algorithm을 적용한다.
Time-sharing
신용도 기반 알고리즘을 적용한다. 프로세스의 신용도가 높을수록 우선순위가 높게 배정된다. CPU를 사용할 때마다 신용도가 점차 차감되며, 0이 되면 다른 프로세스에게 CPU가 넘어간다. 모든 프로세스의 신용도가 0이 되면 우선순위와 이전 사용기록을 반영해 신용도를 재할당한다.
Real-time
soft real-time 프로세스만 지원하며, FCFS와 RR 방식을 사용한다.
Linux는 Solaris와 반대로 숫자가 작을수록 우선순위가 높다. 우선순위에 따라 최대 140단계의 queue가 존재하며, active array에서 할당받은 time quantum 내에 작업을 다 끝내지 못한 프로세스는 expired array로 넘어가 같은 priority number에 줄을 서게 된다.
Algorithm Evaluation
어떤 스케줄링 알고리즘이 좋은지 평가하는 방법 세 가지를 알아보자.
1) Deterministic Modeling
이번 챕터에서 계속 사용한 방식으로, 주어진 프로세스들의 arrival time, CPU burst time, time quantum 등 사전에 정의된 정확한 데이터 값을 바탕으로 간트차트를 그려 성능을 평가하는 방식이다.
2) Queuing Model
수학적 공식을 기반으로 ready queue에서 프로세스들이 대기하는 상황을 분석하는 모델이다.
대표 식:
n = λ × W
n : 평균 ready queue 길이
λ : 평균 도착률 (일감들이 ready queue 안으로 들어오는 비율)
W : 평균 대기 시간
따라서 λ = n / W 로도 표현할 수 있다.실제 개별 프로세스를 하나하나 시뮬레이션하지 않고 시스템을 수학적으로 모델링해서 평균적 성능을 추정하는 방식이다.
3) Simulation Model
실제 작업 데이터를 기반으로 시뮬레이션을 하는 방식이다.
흐름은 이렇다. 실제 컴퓨터에서 프로세스를 실행시키고, 그 과정에서 발생하는 모든 측정 기록을 담아 trace tape라는 방대한 실제 데이터 세트를 생성한다. 이후 특정 알고리즘을 구현한 소프트웨어 시뮬레이터에 이 trace 데이터를 직접 넣어 구동시킨다. 실제 작업 데이터를 기반으로 한 시뮬레이션이 끝난 뒤, average waiting time이나 response time 등 해당 알고리즘의 구체적인 성능 통계치를 도출하고 분석한다.
