如何用Java计算指数到达交替服务队列中Queue1与Queue2的等待时间？

Got it, let's work through how to calculate the waiting times for Queue1 and Queue2 in this alternating service system using Java. This is a classic discrete event simulation problem—here's a step-by-step implementation and explanation:

We'll use discrete event simulation to model the system. The key events we need to track are:

• Packet arrivals to Queue1/Queue2 (following exponential distribution with rate λ)
• Service completions for the current queue (service time follows exponential distribution with rate μ)

We'll use a priority queue to process events in chronological order, and track each packet's arrival time to calculate its waiting time (time from arriving at the queue to starting service).

1. Define Event Structure #

First, create an Event class to represent arrival and service completion events, sorted by timestamp:

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.LinkedList;

// Enum to distinguish event types
enum EventType {
    ARRIVAL, SERVICE_COMPLETION
}

// Event class: implements Comparable to prioritize by time
class Event implements Comparable<Event> {
    private final EventType type;
    private final double time;
    private final int queueId; // 0 = Queue1, 1 = Queue2

    public Event(EventType type, double time, int queueId) {
        this.type = type;
        this.time = time;
        this.queueId = queueId;
    }

    @Override
    public int compareTo(Event other) {
        return Double.compare(this.time, other.time);
    }

    // Getters for event properties
    public EventType getType() { return type; }
    public double getTime() { return time; }
    public int getQueueId() { return queueId; }
}

2. Simulation Core Logic #

Next, build the simulation class that manages queues, events, and server behavior:

class AlternatingQueueSimulation {
    private final double arrivalRate; // λ
    private final double serviceRate; // μ
    private final PriorityQueue<Event> eventQueue;
    private final Queue<Double> queue1; // Stores arrival times of packets in Queue1
    private final Queue<Double> queue2;
    private boolean serverBusy;
    private int nextServiceQueue; // Tracks which queue to serve next (0 = Q1, 1 = Q2)
    private double currentTime;
    private final double[] totalWaitingTime; // Cumulative waiting time per queue
    private final int[] processedPackets; // Count of packets processed per queue

    public AlternatingQueueSimulation(double lambda, double mu) {
        this.arrivalRate = lambda;
        this.serviceRate = mu;
        this.eventQueue = new PriorityQueue<>();
        this.queue1 = new LinkedList<>();
        this.queue2 = new LinkedList<>();
        this.serverBusy = false;
        this.nextServiceQueue = 0; // Start with Queue1 as per the problem statement
        this.currentTime = 0.0;
        this.totalWaitingTime = new double[2];
        this.processedPackets = new int[2];

        // Schedule initial arrival events for both queues
        scheduleNextArrival(0);
        scheduleNextArrival(1);
    }

    // Generate next arrival event using exponential distribution
    private void scheduleNextArrival(int queueId) {
        double interArrivalTime = -Math.log(Math.random()) / arrivalRate;
        double arrivalTime = currentTime + interArrivalTime;
        eventQueue.add(new Event(EventType.ARRIVAL, arrivalTime, queueId));
    }

    // Handle a packet arrival event
    private void handleArrival(int queueId, double arrivalTime) {
        // Add packet's arrival time to the corresponding queue
        if (queueId == 0) {
            queue1.add(arrivalTime);
        } else {
            queue2.add(arrivalTime);
        }

        // Schedule the next arrival for this queue
        scheduleNextArrival(queueId);

        // Start service immediately if server is idle
        if (!serverBusy) {
            startNextService();
        }
    }

    // Handle a service completion event
    private void handleServiceCompletion(int queueId, double completionTime) {
        serverBusy = false;
        currentTime = completionTime;

        // Switch to the other queue for next service (alternating rule)
        nextServiceQueue = 1 - nextServiceQueue;

        // Attempt to start serving the next queue
        startNextService();
    }

    // Start serving the next queue in the alternating sequence
    private void startNextService() {
        Queue<Double> targetQueue = (nextServiceQueue == 0) ? queue1 : queue2;
        int queueId = nextServiceQueue;

        if (!targetQueue.isEmpty()) {
            serverBusy = true;
            double packetArrivalTime = targetQueue.poll();

            // Calculate waiting time for this packet
            double waitingTime = currentTime - packetArrivalTime;
            totalWaitingTime[queueId] += waitingTime;
            processedPackets[queueId]++;

            // Schedule service completion event (exponential service time)
            double serviceTime = -Math.log(Math.random()) / serviceRate;
            double completionTime = currentTime + serviceTime;
            eventQueue.add(new Event(EventType.SERVICE_COMPLETION, completionTime, queueId));
        }
        // If target queue is empty, server remains idle until next event triggers service
    }

    // Run the simulation until we process a specified number of packets
    public void run(int totalPacketsToProcess) {
        while (processedPackets[0] + processedPackets[1] < totalPacketsToProcess) {
            if (eventQueue.isEmpty()) break;

            Event nextEvent = eventQueue.poll();
            currentTime = nextEvent.getTime();

            switch (nextEvent.getType()) {
                case ARRIVAL:
                    handleArrival(nextEvent.getQueueId(), nextEvent.getTime());
                    break;
                case SERVICE_COMPLETION:
                    handleServiceCompletion(nextEvent.getQueueId(), nextEvent.getTime());
                    break;
            }
        }

        // Output average waiting times
        System.out.println("Simulation Results:");
        System.out.printf("Queue 1 Average Waiting Time: %.4f (Packets Processed: %d)%n",
                totalWaitingTime[0] / processedPackets[0], processedPackets[0]);
        System.out.printf("Queue 2 Average Waiting Time: %.4f (Packets Processed: %d)%n",
                totalWaitingTime[1] / processedPackets[1], processedPackets[1]);
    }

    // Example usage
    public static void main(String[] args) {
        // Test with λ=0.5, μ=1.0, process 10,000 packets for stable results
        AlternatingQueueSimulation sim = new AlternatingQueueSimulation(0.5, 1.0);
        sim.run(10000);
    }
}

Key Details to Note #

• Exponential Distribution: We use -Math.log(Math.random()) / rate to generate exponential inter-arrival and service times—this is the standard inverse transform sampling method for exponential distributions.
• Alternating Service Rule: After each service completion, we switch the target queue (nextServiceQueue = 1 - nextServiceQueue). Even if the next queue is empty, the server won't jump to the other queue; it waits until the next event (arrival or service completion) triggers the next service attempt.
• Waiting Time Calculation: For each packet, waiting time is the difference between the time service starts and the time the packet arrived at the queue. We accumulate these values and divide by the number of processed packets to get the average.

Tips for Accuracy #

• Run the simulation with a large number of packets (10,000+) to minimize transient effects from the initial system state.
• Ensure system stability: The system is stable only if 2λ < μ—otherwise, queues will grow indefinitely and waiting times will explode.

内容的提问来源于stack exchange，提问作者김동현