Computer System Simulation: Queues, Schedulers & Performance

Core Concepts

1. Why Simulate Computer Systems?

Computer systems (CPUs, networks, databases) are complex, dynamic, and probabilistic. Simulation lets us:

• Predict bottlenecks (e.g., Ncell’s call drops during peak hours).
• Test new algorithms (e.g., Google’s load balancers) without real-world risks.
• Optimize resource use (e.g., Daraz’s server farms during sales).

Real-world tie:

• WhatsApp’s message routing: Uses priority queues to prioritize urgent messages (e.g., OTPs) over regular chats. Simulation helps balance server load across regions.
• Nepal Rastra Bank’s core banking: Models transaction queues to avoid crashes during Diwali season.
• Pathao’s driver dispatch: Simulates geospatial queues to match riders to nearest drivers faster.

2. Key Components of Computer System Simulation

A. Discrete-Event Simulation (DES) for IT Systems

DES models events like:

• Job arrival (e.g., a user submitting a request to eSewa).
• CPU scheduling (e.g., switching between tasks in a virtual machine).
• Network packet arrival (e.g., data packets in NTC’s fiber-optic backbone).

How it works:

1. Event list: A priority queue of pending events (e.g., [Task1 arrives at t=2s, Task2 completes at t=5s]).
2. Simulation clock: Advances only when an event occurs (no wasted computation).
3. State updates: Modify system state (e.g., CPU switches from Task1 to Task2).

flowchart LR
    A["Event List (Priority Queue)"] -->|"Process Next Event"| B["Simulation Clock"]
    B --> C["Update System State"]
    C --> D["Schedule Next Event"]
    D --> A

Worked Example: CPU Scheduling Simulation Assume a single-core CPU with these tasks:

Simulation Steps:

1. t=0ms: T1 arrives → CPU starts T1. Event: T1 completes at t=5ms.
2. t=1ms: T2 arrives → CPU is busy (T1 running). Event: T2 completes at t=4ms (1ms wait + 3ms burst).
3. t=2ms: T3 arrives → CPU still busy. Event: T3 completes at t=6ms (4ms wait + 2ms burst).
4. t=4ms: T2 completes → CPU switches to T3.
5. t=5ms: T1 completes → CPU idle (all tasks done).

Visualization of CPU State Over Time:

Time (ms) | CPU State       | Queue
----------|-----------------|-----------------------
0         | Running T1      | [T2, T3]
1         | Running T1      | [T2, T3]
2         | Running T1      | [T2, T3]
3         | Running T1      | [T2, T3]
4         | Running T2      | [T3]
5         | Idle            | []
6         | Done            | []

B. Queueing Models for IT Systems

Most computer systems involve queues:

• CPU scheduling queues (Ready, Blocked, I/O).
• Network buffers (e.g., NTC’s packet queues).
• Database transaction logs (e.g., NEPSE’s order matching).

Common Queue Types in IT:

Worked Example: Network Router Queue A router has a buffer of size 3 packets. Packets arrive with random inter-arrival times (exponential distribution, λ=2 packets/sec). Service time is constant (100ms per packet).

Simulation Trace:

Visualization of Packet Queue:

graph LR
    A["Packet 1"] -->|"Transmitted"| B["Packet 2"]
    B --> C["Packet 3"]
    C --> D["Packet 4 (Dropped)"]

Key Metrics:

• Throughput: Packets/sec successfully transmitted = 2/3 ≈ 0.67 packets/sec.
• Drop Rate: 2/4 = 50% (high! Need a larger buffer or faster CPU).

C. Probabilistic Workloads

Real-world IT systems have random arrival/service times. Common distributions:

1. Exponential: Models unpredictable events (e.g., user clicks on Daraz).
   • Mean inter-arrival time = $1/\lambda$ (λ = arrival rate).
2. Uniform: Fixed range (e.g., CPU burst time between 1–5ms).
3. Normal: Clustered around a mean (e.g., Ncell call durations).

Worked Example: eSewa Transaction Processing Assume:

• Transactions arrive exponentially (λ=5 transactions/min).
• Service time is uniform (1–3 seconds).

Simulation for 10 minutes:

1. Generate 50 arrival times using exponential distribution.
2. Generate 50 service times using uniform distribution.
3. Simulate a queue with a single server (e.g., eSewa’s payment processor).

Sample Output:

Visualization of eSewa Queue:

gantt
    title eSewa Transaction Queue (10s Window)
    dateFormat  HH:mm:ss
    section Server
    T1 :a1, 0, 2s
    T2 :a2, 2s, 2s
    T3 :a3, 4s, 3s
    section Queue
    T2 :crit, 0s, 2s
    T3 :crit, 2s, 2s

Key Insight:

• Average wait time = (1.6 + 2.7 + ...) / 50 ≈ 1.2 seconds.
• Server utilization = Total busy time / Total time ≈ 75%.

3. Simulation Tools for Computer Systems

4. Validation and Verification

Simulation results must be realistic. Methods:

1. Tracing: Compare simulation logs to real system traces (e.g., Ncell’s call logs).
2. Analytical Models: Use queueing theory (e.g., M/M/1 for CPU scheduling).
3. Benchmarking: Test against known workloads (e.g., TPC-C for databases).

Worked Example: Validating a Web Server Simulation

• Real Data: Google’s web server handles 1000 requests/sec with 95% <200ms latency.
• Simulation: Your model shows 900 requests/sec with 90% <200ms.
• Action: Increase buffer size or optimize CPU scheduling.

5. Applications in Nepal’s IT Sector

Exam Tip

1. Focus on queueing theory: Know M/M/1, M/G/1, and G/G/1 notations for CPU/network models.
2. Draw timelines: For CPU scheduling, always show a Gantt chart.
3. Calculate metrics: Expect questions on throughput, utilization, and wait time.
4. Compare algorithms: Contrast FCFS, Round Robin, and Priority Scheduling in terms of fairness and efficiency.
5. Real-world mapping: Relate simulations to Ncell’s call drops, eSewa’s transaction limits, or Daraz’s server crashes.

Key Formula Cheat Sheet:

Visual Summary of CPU Scheduling Algorithms:

mindmap
  root((CPU Scheduling))
    FCFS
      Pros: Simple
      Cons: Convoy effect
    Round Robin
      Pros: Fair
      Cons: Overhead
    Priority
      Pros: Urgent tasks first
      Cons: Starvation
    SJF
      Pros: Optimal for short jobs
      Cons: Hard to predict burst time