mm1.txt

One-channel queuing system simulator (M/M/1) * Arrival and service times are random and distributed

/* Author: Vadim Kyrylov.  Date: 26-Feb-2002
*
* One-channel queuing system simulator (M/M/1)
* Arrival and service times are random and distributed exponetially. 
*
* The simulator is time-slice-driven, i.e. the system model is being  
* run at discrete time points, with constant increments deltaT.
* At each such time moment, program checks if a new item arrival or 
* release has occurred during previus deltaT.
*
* This control structure is more suitable for continuos-time simulation, but    
* our system has a discrete nature. (However, this is somewhat helpful 
* for drawing diagrams, since increments along X-axis are constant.) 
*
*/
import java.applet.Applet;
import java.awt.*;
import java.lang.*;
import java.awt.event.*;
import java.util.*;


// applet driver
public class SimApplet extends Applet {	
	
	int myArrival = 80, myService = 40; // mean time between arrivals and mean service time
	
	// Slider Parameters: LabelText, DefaultValue, VisiblePart, Min, Max+VisibePart
	Slider arrivSlider = new Slider("Mean Time Between Arrivals:", myArrival, 5, 1, 120+5); 
	Slider servSlider = new Slider("System Mean Service Time:", myService, 5, 1, 120+5);
	
	CvQueue myObj;
	Panel topPanel    = new Panel();
	Panel bottomPanel = new Panel();
	Panel cenralPanel = new Panel();		
	Button buttonStep  	= new Button(" Step");
	Button buttonRun   	= new Button("R u n");
	Button buttonReset  = new Button("Reset");
	
	public static boolean oneStep = true;
	
	public void init()  {
	
		setBackground(Color.white);
		setLayout(new BorderLayout() );	// Layout Manager for the applet window
		
		// a panel with the main object 
      	myObj = new CvQueue(myArrival,myService);
      	// make the panel size fitting the canvas
	    Dimension dim = getToolkit().getScreenSize();
	    myObj.setSize(dim.width/2, dim.height/2);
      	topPanel.add("North", myObj);	
		add("North", topPanel);
		
		// a panel with sliders and control buttons
		bottomPanel.setLayout(new BorderLayout() );
		bottomPanel.setBackground(Color.cyan);
		bottomPanel.add("West", arrivSlider);
		cenralPanel.add(buttonStep);
		cenralPanel.add(buttonRun);
		cenralPanel.add(buttonReset);
		bottomPanel.add("Center", cenralPanel);
		bottomPanel.add("East", servSlider);
		
		add("South", bottomPanel);	
      	
      	setSize(getPreferredSize());
      		
		arrivSlider.addAdjustmentListener(new myAdjustmentListener());
		servSlider.addAdjustmentListener(new myAdjustmentListener());
	}
	
		// update the drawing panel in accordance with user action
	public boolean action(Event e, Object arg)  {
		if (e.target == buttonStep) {
			// run one step at a time
			oneStep = true;
			Graphics g = getGraphics();
			g.setColor(Color.red);
			Color myClr = g.getColor();
			myObj.runOneStep(myObj.sysTime, myClr);
			if (myObj.sysTime>myObj.Tmax) myObj.resetVars();
		} else if (e.target == buttonRun) {
			// run one sequence in new color without erasing previous results 
			oneStep = false;
			myObj.runSequence(true);
		} else if (e.target == buttonReset) {
			drawMyObj(myArrival, myService);
		}
		return false;
	}  // action
	
	
	public void drawMyObj(int Arriv, int Serv) {
		// create a new object and put it on the top panel
      	topPanel.remove(myObj);
      	myObj = new CvQueue(Arriv, Serv);
	    Dimension dim = getToolkit().getScreenSize();
	    myObj.setSize(dim.width/2, dim.height/2);
      	topPanel.add("North", myObj);	
	} 
	
	class myAdjustmentListener implements AdjustmentListener {
		public void adjustmentValueChanged(AdjustmentEvent event) {
			topPanel.remove(myObj);				
			myArrival = arrivSlider.getValue();
			myService = servSlider.getValue();
			drawMyObj(myArrival, myService); 
		}
	}
}// SimApplet


// the simulator
class CvQueue extends Canvas {	

	public int sysTime;
	
	Random numberGenerator = new Random();
	Dimension d;
	int maxX, maxY;
	int Tmax; // simulation time interval in some units (e.g. seconds)
	int deltaT=1; // simulation time step
	int deltaY=20;
	float meanArrival, meanService;
	int x1, y1, x2, y2, x0=25, y0 = 250;
	float lambda, mu; // arrival and service intensity parameters (1/sec)
	float tNextArrive;	// time of the item's arrival	
	boolean itemArrived = false;
	boolean serviceDone = false;
	float tNextOut;		// time of the item's out of the system 
	int numInQueue=0; 	// number of items in the waiting line
	Color myColor;
	
	// accumulators
	long stepCount;
	long arrCount;
	float avgQueueLen;
	long maxQueueLen;
	float varQueueLen;
	
	
	// constructor 
	CvQueue(int Arriv, int Serv) {
		meanArrival = (float)Arriv;
		meanService = (float)Serv;
	}
	
	
	// intialize variables and draw static elements on the canvas
	public void paint(Graphics g) {  
		
		d = getSize();
		maxX = d.width - 1;
		maxY = d.height - 1;
		Tmax = (maxX-x0)*deltaT;
    	mu = 1/meanService; 
    	lambda = 1/meanArrival;
    	tNextArrive = -1;
    	tNextOut = -1;	 
    	
    	g.setColor(Color.black);
    	
    	// draw X-axis
    	g.drawLine(x0, y0, maxX, y0);
    	g.drawLine(x0, y0+1, maxX, y0+1);
    	for (int t=x0; t<maxX-40; t=t+60) {
    		g.drawLine(t, y0, t, y0+4);
    		g.drawString((t-x0)*deltaT + "", t-5, y0+15);
    		g.drawString("Time, s", maxX-40, y0+15);
    	} 
    	
    	// draw event indicator   	
    	g.drawLine(x0, y0+55, maxX, y0+55);
    	g.drawString(" IN", 0, y0+50); // arrival - dash up
    	g.drawString("OUT", 0, y0+70); // service complete - dash down
    	
    	// draw Y-axis
    	g.drawLine(x0, y0, x0, 25);
    	g.drawLine(x0+1, y0, x0+1, 25);
    	g.drawString("Queue", 0, 10);
    	g.drawString("Length", 0, 20);
    	int nMax = y0/deltaY;
    	for (int i=0; i<nMax-1; i++) {
    		g.drawLine(x0, y0-deltaY*i, x0-4, y0-deltaY*i);
    		g.drawString(i+"", x0-16, y0-deltaY*i+5);
    	}
    	
    	x1 = x0; 
		y1 = y0;
		
		// the accumulators
		stepCount = 0;
		arrCount = 0;
		avgQueueLen = 0;
		maxQueueLen = 0;
		varQueueLen = 0;

	}

	
	// run the simulation and plot the diagram; sysTime is the simulation time
	void runSequence(boolean changeColor) {
			
		Graphics g = getGraphics();
		if (changeColor)  {
			// create new random color for each sequence
			myColor = new Color((int)(255.0 * numberGenerator.nextFloat()),
								(int)(255.0 * numberGenerator.nextFloat()),
								(int)(255.0 * numberGenerator.nextFloat()));
			g.setColor(myColor);
		} else  g.setColor(Color.red);
		
		Color myColor = g.getColor(); 
		
		//***  main loop  ***
		for (sysTime=0; sysTime < Tmax; ) {
			// simulate the Server state at current time sysTime
			runOneStep(sysTime, myColor);
		}
		
		displayStat(g);
		resetVars(); // ensure continuity for the next run
	}
	
	
	void resetVars() {
		tNextArrive = tNextArrive - Tmax;
		tNextOut = tNextOut - Tmax;
		sysTime = 0;
    	x1 = x0; 
		y1 = y0 - numInQueue * deltaY;
	}
	
	
	// simulate the Server and display results for current system time
	void runOneStep(int t, Color clr) {
		runServer(t);
		paintResults(clr); 
		updateStats();
		sysTime = sysTime + deltaT;
	}
	
	
	// accumulate statistics
	void updateStats() {
		stepCount++;
		avgQueueLen = avgQueueLen + numInQueue;
		if (maxQueueLen < numInQueue) maxQueueLen = numInQueue;
		varQueueLen = varQueueLen + numInQueue*numInQueue;
	}
	
	
	// update state/event variables for current time
	// (numInQueue, itemArrived, tNextArrive, serviceDone, tNextOut, arrCount)
	void runServer(int time) {
   		
		if (time > tNextArrive) {
			// an item has arrived...
			itemArrived = true;
			arrCount++;
			if (numInQueue == 0) tNextOut = time  + expRandom(mu);
			numInQueue++; // add it to the queue 
			// calculate the next arrival time
			tNextArrive = tNextArrive + expRandom(lambda);
		} else itemArrived = false;
		
		
		serviceDone = false;
		
		if (time > tNextOut) {
			if (numInQueue > 0) {
				// the item has left the system...
				serviceDone = true;
				if (SimApplet.oneStep) Toolkit.getDefaultToolkit().beep();
				numInQueue--; // remove it from the queue
				// calculate the next out time
				tNextOut = tNextOut  + expRandom(mu);
			}
		} 
				
   }
   

	// paint the results of current step
	void paintResults(Color clr) {
		
		Graphics g = getGraphics();
		g.setColor(clr);
		
		if (itemArrived) {
			// draw vertical dash upwards
			g.drawLine(x1, y0+55, x1, y0+45);		
		}
		
		if (serviceDone) {
			// draw vertical dash downwards
			g.drawLine(x1, y0+55, x1, y0+65);
		}
		
		// plot the diagram for current numInQueue
		x2 = x1 + 1;
		y2 = y0 - numInQueue * deltaY;
		g.drawLine(x1, y1, x2, y2);
		g.drawLine(x1+1, y1+1, x2+1, y2+1);
		x1 = x2;
		y1 = y2;			
	
	} 
	
	
	// display satistics
	void displayStat(Graphics g) {
	
		int xx = 2*maxX/3; // horizontal offset
		int xstart = 150;
		
		g.setColor(Color.lightGray);
		g.fillRect(xstart-100, y0+75, xx+50, 55);
		
		g.setColor(Color.cyan);
		g.fillRect(xstart-10, y0+96, 50, 14); // clear old value
		g.setColor(Color.blue);
		g.drawString("Total arrivals", xstart-90, y0+108);
		g.drawString("= "+arrCount, xstart, y0+108);
		
		
		g.setColor(Color.cyan);
		g.fillRect(xx-10, y0+78, 100, 14); // clear old value
		g.setColor(Color.blue);
		g.drawString("Avg queue length", xx-120, y0+90);
		float aqLength = avgQueueLen/stepCount;
		g.drawString("= "+(float)(aqLength), xx, y0+90);
		
		g.setColor(Color.cyan);
		g.fillRect(xx-10, y0+96, 100, 14); // clear old value
		g.setColor(Color.blue);
		g.drawString("      Std deviation", xx-120, y0+108);
		g.drawString("= "+(float)Math.sqrt((float)(varQueueLen - aqLength*aqLength)/stepCount), xx, y0+108);

		g.setColor(Color.cyan);
		g.fillRect(xx-10, y0+113, 100, 14); // clear old value
		g.setColor(Color.blue);
		g.drawString("Max queue length", xx-120, y0+124);
		g.drawString("= "+maxQueueLen, xx, y0+124);
		
		//g.drawRect(xstart-100, y0+75, xx+50, 55);
	
	}
	

	// returns exponetially distributed random variable
	float expRandom (float gamma) {
		float myRandom = (float) (-Math.log(numberGenerator.nextFloat())/gamma );	
		return myRandom;
	
	}
  
   
} // CvQueue



//==========================================================
// The classes below added just for the convenience of keeping 
// all the stuff in a single file.
//===========================================================
// From Graphic Java by D.Geary, p. 542-543, with minor modifications 

public class BorderedPanel extends Panel {
	public Insets getInsets() {
		return new Insets(2,2,2,2);
	}
	public void paint(Graphics g) { 
		Dimension size = getSize();
		this.setBackground(Color.white);
		g.setColor(Color.black);
		g.drawRect(0,0,size.width-1,size.height-1);

		g.setColor(Color.lightGray);
		g.draw3DRect(1,1,size.width-3,size.height-3,true);
	}
}//BorderedPanel


public class Slider extends BorderedPanel implements Adjustable {
	Scrollbar scrollbar;
	Label     valueLabel; 
	String labelText = "dummy";

	public Slider(String mylabelText, int initialValue, int visible, 
	              int min, int max) {
	    labelText = mylabelText;          
		String initialValueStr = labelText + " " + Integer.toString(initialValue);

		valueLabel = new Label(initialValueStr, Label.CENTER);
 		scrollbar  = new Scrollbar(Scrollbar.HORIZONTAL, initialValue, visible, min, max);
 		//scrollbar  = new Scrollbar(Scrollbar.VERTICAL, initialValue, visible, min, max);	// NEW

		setLayout(new BorderLayout());
		add(valueLabel, "North");
		add(scrollbar, "Center");

		scrollbar.addAdjustmentListener(new AdjustmentListener() {
			public void adjustmentValueChanged(AdjustmentEvent e) {
				valueLabel.setText(labelText + " " + Integer.toString(scrollbar.getValue()));
			}
		});
	}
	
	public void addAdjustmentListener(AdjustmentListener l) {
		scrollbar.addAdjustmentListener(l);
	}
	public void removeAdjustmentListener(AdjustmentListener l) {
		scrollbar.removeAdjustmentListener(l);
	}
	public int getOrientation() {
		return scrollbar.getOrientation();	
	}
	public void setOrientation(int orient) {
		scrollbar.setOrientation(orient);	
	}
	public int getValue() {
		return scrollbar.getValue();
	}
	public int getVisibleAmount() {
		return scrollbar.getVisibleAmount();
	}
	public int getMinimum() {
		return scrollbar.getMinimum();
	}
	public int getMaximum() {
		return scrollbar.getMaximum();
	}
	public int getUnitIncrement() {
		return scrollbar.getUnitIncrement();
	}
	public int getBlockIncrement() {
		return scrollbar.getBlockIncrement();
	}
	public void setValue(int value) {
		scrollbar.setValue(value);
		valueLabel.setText(Integer.toString(value));
	}
	public void setVisibleAmount(int value) {
		scrollbar.setVisibleAmount(value);
	}
	public void setMinimum(int min) {
		scrollbar.setMinimum(min);
	}
	public void setMaximum(int max) {
		scrollbar.setMaximum(max);
	}
	public void setUnitIncrement(int inc) {
		scrollbar.setUnitIncrement(inc);
	}
	public void setBlockIncrement(int inc) {
		scrollbar.setBlockIncrement(inc);
	}
}//Slider