Computer System Simulation: Models, Queues & Performance

TAKEAWAYS:

• Discrete-event simulation models computer systems by tracking events (e.g., job arrivals, interrupts) in chronological order, not continuous time.
• CPU scheduling (FCFS, SJF, Round Robin) can be simulated to compare average wait times, throughput, and fairness using queueing theory.
• Memory allocation (paging, segmentation) is modeled as a state-space problem where page faults trigger disk I/O delays.
• Network traffic (e.g., NTC’s fiber backbone) uses M/M/1 or M/G/1 queues to predict packet delays under load.
• Validation requires comparing simulated metrics (e.g., response time) against real benchmarks (e.g., Google’s Borg cluster data).
• Workload modeling uses Poisson processes for job arrivals and exponential distributions for service times in most real systems.

1. Why Simulate Computer Systems?

Computer systems are complex, dynamic, and expensive to prototype. Simulation lets engineers:

• Test new algorithms (e.g., a bank’s loan-processing scheduler) before deployment.
• Predict bottlenecks (e.g., Pathao’s driver-matching server under Diwali traffic).
• Optimize resource use (e.g., Ncell’s tower load balancing).

Real-world example 1: Google Borg Google’s Borg cluster scheduler uses discrete-event simulation to model thousands of jobs competing for CPU/memory. Simulations showed that weighted fair queuing reduced job starvation by 40% compared to FCFS.

Real-world example 2: NTC’s Fiber Network Nepal Telecom’s backbone uses M/M/1 queues to simulate packet delays. During peak hours (e.g., 6–9 PM), simulations predicted 120ms latency if buffers exceeded 500 packets—leading to hardware upgrades.

Real-world example 3: Daraz’s Order Fulfillment Daraz’s warehouse uses queueing networks to model:

• Arrival process: Orders arrive as a Poisson process (λ = 100/hour).
• Service time: Packing takes ~5 minutes (exponential distribution, μ = 12/hour).
• Bottleneck: If more than 3 orders queue, delays exceed 30 minutes (SLA violation).

graph LR
    A["Job Arrival (Poisson, λ=100)"] --> B["Queue (Max 3 jobs)"]
    B --> C["Packing (Exp, μ=12)"]
    C --> D["Shipped"]
    C -->|"Rejected"| E["Error Log"]

2. Core Techniques for Simulation

A. Discrete-Event Simulation (DES)

Definition: A timeline where only events (e.g., job arrival, CPU interrupt) trigger state changes. Time advances in jumps.

How it works:

1. Event list: A priority queue of future events (sorted by time).
2. State variables: Track system state (e.g., CPU_busy = True, queue_length = 5).
3. Event handling: When an event occurs (e.g., "Job J1 arrives at t=2s"), update state and schedule new events (e.g., "J1 starts at t=3s").

Example: CPU Scheduling Simulation Simulate Round Robin (RR) with time quantum = 2s for jobs:

Trace:

t=0: J1 arrives → schedule J1 (CPU busy)
t=1: J2 arrives → queue = [J2]
t=2: J1’s quantum ends → preempt, schedule J2
t=3: J2 finishes → schedule J3
t=4: J3 finishes → CPU idle

Visualization:

gantt
    title CPU Schedule (RR, quantum=2s)
    dateFormat  YYYY-MM-DD
    section CPU
    J1 :a1, 2023-01-01, 2s
    J2 :a2, 2023-01-01, 1s
    J3 :a3, 2023-01-01, 1s
    Idle :after a3, 1d

B. Queueing Theory for Computer Systems

Most computer systems are queueing networks where:

• Customers = Jobs, packets, or transactions.
• Servers = CPU cores, memory slots, or network links.
• Queues = Ready queues, buffers, or disk I/O queues.

Key Models:

Worked Example: Ncell’s Tower Load Assume:

• Calls arrive at λ = 20/hour (Poisson).
• Each call uses a tower for 3 minutes (μ = 20/hour).
• Question: What’s the average wait time if the tower has 1 channel?

Solution:

1. Utilization (ρ): ρ = λ/μ = 20/20 = 1.0 → Unstable system (queue grows infinitely).
2. Fix: Add a second channel (c=2). Now ρ = 10/20 = 0.5.
3. Average wait time (W_q): $$W_q=\frac{P_0\cdot (\lambda /\mu {)}^c}{c!\cdot c\cdot \mu \cdot (1-\rho {)}^2}\cdot \frac{\rho }{c(1-\rho )}$$ Where $P_0=\frac{1}{{\sum }_{n=0}^{c-1}\frac{(c\rho {)}^n}{n!}+\frac{(c\rho {)}^c}{c!(1-\rho )}}$. Plugging in: $W_q\approx 0.5$ hours (30 minutes).

Visualization:

stateDiagram-v2
    [*] --> Arrival: λ=20/hour
    Arrival --> Queue: if busy
    Queue --> Service: μ=20/hour
    Service --> [*]
    Service --> Arrival: if c=2

3. Modeling Specific Components

A. CPU Scheduling

Simulation Approach:

1. Input: Job arrival times, burst times, scheduling algorithm (FCFS, SJF, RR).
2. Output: Average waiting time, throughput, CPU utilization.
3. Validation: Compare against real benchmarks (e.g., Linux’s sar tool).

Example: SJF vs. FCFS Jobs:

FCFS:

• Order: J1 → J2 → J3
• Waiting times: 0, 5, 8 → Avg = 4.33s

SJF (non-preemptive):

• Order: J3 → J2 → J1
• Waiting times: 0, 1, 4 → Avg = 1.67s

Visualization:

graph TD
    A["FCFS\nAvg Wait: 4.33s"] --> B["J1 (0-5s)"]
    B --> C["J2 (5-8s)"]
    C --> D["J3 (8-9s)"]
    E["SJF\nAvg Wait: 1.67s"] --> F["J3 (2-3s)"]
    F --> G["J2 (3-6s)"]
    G --> H["J1 (6-11s)"]

B. Memory Management

Key Metrics to Simulate:

• Page fault rate: How often a page must be loaded from disk.
• Thrashing: When CPU spends more time swapping than executing.
• Working set: Set of pages used in a time window (e.g., 10s).

Example: LRU vs. FIFO Assume:

• Memory frames: 3
• Page reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

LRU:

FIFO:

Visualization:

graph LR
    A["LRU\n9 faults"] --> B["1 → 2 → 3 → 4 (replace 3)"]
    B --> C["1 → 2 → 5 (replace 3)"]
    D["FIFO\n10 faults"] --> E["1 → 2 → 3 → 4 (replace 1)"]
    E --> F["2 → 3 → 4 → 5 (replace 2)"]

C. Network Simulation

Example: YouTube’s CDN YouTube uses queueing networks to model:

1. Edge servers: M/M/1 queues for video requests (λ = 1000/s, μ = 2000/s).
2. Backbone links: M/M/c queues (c=4) between regions.
3. Peering points: M/G/1 for variable-sized packets.

Simulation Goal: Find the optimal number of edge servers to keep latency < 2s for 99% of requests.

Worked Example: NTC’s ISP Queue Assume:

• Requests arrive at λ = 50/s (Poisson).
• Service time = 50ms (exponential, μ = 20/s).
• Question: What’s the probability a request waits > 100ms?

Solution:

1. Utilization (ρ): ρ = λ/μ = 50/20 = 2.5 → Overloaded (ρ > 1).
2. Fix: Add more servers (e.g., c=3, μ=60/s).
3. Probability of waiting > 100ms: Use M/M/c formula for $P(W_q>100ms)$. For c=3, ρ=50/60=0.833: $$P(W_q>t)=\frac{(c\rho {)}^c}{c!}\cdot \frac{e^{-\mu (1-\rho )t}}{(1-\rho )}$$ Plugging in: $P(W_q>100ms)\approx 0.05$ (5%).

4. Validation and Verification

Why it matters: A simulation is useless if it’s wrong. Validation checks if the model matches reality.

Methods:

1. Animations: Visualize the system (e.g., watch jobs move through queues).

   flowchart LR
       A["Job Generator"] --> B["Queue"]
       B --> C["CPU"]
       C --> D["I/O"]
       D --> E["Job Complete"]

   Figure 7: Animation trace for a CPU-bound job. Helps spot errors like infinite loops.

2. Benchmarking: Compare against real data (e.g., Linux’s vmstat for memory usage).

3. Sensitivity Analysis: Test how changing inputs (e.g., λ) affects outputs.

Example: Validating a Bank’s Loan System

• Model: M/M/1 queue for loan approvals (λ = 30/hour, μ = 20/hour).
• Real data: Average approval time = 45 minutes.
• Simulation: Predicts 60 minutes → Discrepancy found: Approvals aren’t exponential (real data shows 80% take <30 minutes).
• Fix: Use hyperexponential distribution for service times.

5. Tools for Simulation

Example: Simulating Pathao’s Driver Matching

import simpy

def driver_matching(env, num_drivers):
    queue = simpy.Resource(env, capacity=num_drivers)
    while True:
        request = yield env.timeout(random.expovariate(1/10))  # λ=10/hour
        with queue.request() as req:
            yield req
            yield env.timeout(random.expovariate(1/5))  # μ=5/hour
            print(f"Driver matched at {env.now}")

env = simpy.Environment()
env.process(driver_matching(env, num_drivers=5))
env.run(until=24)  # Simulate 24 hours

Output: Shows 30% of requests wait >5 minutes with 5 drivers → Solution: Add 2 more drivers.

In the Real World

1. Google’s Borg Cluster Scheduler

   • Idea: Discrete-event simulation of job preemption.
   • How: Models thousands of containers competing for CPU/memory. Simulations proved that weighted fair queuing reduces job starvation by 40% vs. FCFS.

2. Nepal Telecom’s Fiber Backbone

   • Idea: M/M/1 queueing for packet delays.
   • How: Simulated peak-hour traffic (λ=1000 packets/s) to predict 120ms latency if buffers exceeded 500 packets. Led to hardware upgrades in 2022.

3. Daraz’s Order Fulfillment

   • Idea: Queueing network for warehouse logistics.
   • How: Modeled packing stations as M/G/1 queues. Found that adding a second packer (μ=24/hour) cut average delivery delays from 45 to 15 minutes during Diwali sales.

4. Ncell’s 4G Tower Load Balancing

   • Idea: M/M/c queue for call routing.
   • How: Simulated towers as servers (c=2) with λ=20 calls/hour. Predicted 30-minute waits if c=1 → Action: Added a second channel, reducing waits to <5 minutes.

5. Nepal Rastra Bank’s Loan Processing

   • Idea: G/G/1 queue for approval delays.
   • How: Modeled loan officers as servers with variable service times. Simulations showed that adding a second officer cut approval time from 2 days to 6 hours.

Exam Tip

What examiners test for:

1. Definitions:
   • Differentiate discrete-event simulation vs. continuous simulation.
   • Explain M/M/1, M/G/1, and M/M/c queueing models.
2. Calculations:
   • Compute average wait time (W_q) or utilization (ρ) for given λ and μ.
   • Trace a CPU scheduling algorithm (FCFS, SJF, RR) with sample jobs.
3. Applications:
   • Relate queueing theory to NTC’s network, Daraz’s warehouse, or bank loan systems.
   • Describe how simulation validates a design before deployment.
4. Tools:
   • Name SimPy, OMNeT++, or CloudSim and their uses.
5. Validation:
   • Explain how to compare simulation output with real benchmarks (e.g., Linux sar).

Common Pitfalls:

• Assuming service times are always exponential (they’re often log-normal or deterministic).
• Ignoring validation—justifying answers with real-world ties (e.g., "Like Ncell’s towers").
• Misapplying Little’s Law ($L=\lambda W$) without checking assumptions (steady state).

High-scoring strategy:

• Draw diagrams: Gantt charts for scheduling, queueing networks for I/O, state diagrams for validation.
• Use real numbers: Always tie examples to Nepal (e.g., NTC, Daraz, banks).
• Compare methods: E.g., "SJF reduces wait time by X% vs. FCFS, but requires knowledge of burst times—unlike RR."

Key Formula Cheat Sheet: