COCS3308 Program-5 (FORTRAN-2)
Single-Server Simulation due: 10/25/2006
A. Objectives
1. Linked-List (of simulation events) processing
2. Implementing a single-server queuing system for obtaining
some performance measures such as
Steady-State average delay (Average queue waiting time)
Steady-State average waiting time (Average queue waiting time + average service time)
Steady-State time-average number in queue (Average queue size)
Utilization factor.
Expected conservation equation:
Q = D*U/S = D/E = D*A
where Q is Average queue size
U is the Utilization factor
D is the average queue waiting time
S is the average service time
E is the mean interarrival time and
A is Arrival Rate, number of arrivals per time unit
which is the reciprocal of the Mean interarrival time..
B. Assumptions
1. Simulation time: 500,000 Units
2. Customer interarrival time:
Uniform distribution between 0 and an input MAX value.
3. Service Time: Uniform distribution between 10 and an input MAX.
4. Queue-Waiting jobs classified into two types:
LOW-Queue Jobs: requested service time > 20% of the service time
range (the difference between the min service time expected and
the max service time expected).
HIGH-Queue Jobs: Other jobs (with relatively short service time)
5. A Low-Queue job will be picked up for service only if
a. there is NO job in the HIGH-Queue or
b. a Low-Queue job has been waiting more than 5,000 time units
longer than any HIGH-Queue job.
C. Required outputs
For each input parameter set (of Max interarrival time and Max
service time),
1. Utilization Factor (Expected to be the mean Service time divided by the expected mean
Inter-arrival time)
2. For each waiting queue and two queues combined:
2a. # of jobs processed
2b. Average queue size
2c. Average queue waiting time
2d. Max waiting time.
D. Use following inputs:
500 300
500 400
500 510
E. Your task:
Now, you only may have to fill in three routines
that have been left out in the following partial solution:
They are
Subroutine InsertEvent (Node, Head, Tail)
Subroutine QDelete(Q)
Subroutine finishing
******************PARTIAL SOLUTION********************
! Single-server queueing system simulation.
!
Module events
Implicit None
Type Event
Integer:: EType
Integer:: OccurTime
Type(Event), Pointer:: Next
End Type Event
Contains
Subroutine Initialize (Head,Tail)
Type(Event), Pointer :: Head, Tail
Nullify (Head,Tail)
Return
End Subroutine Initialize
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Recursive Subroutine InsertEvent (Node, Head, Tail)
! Inserts the given event-node into the list
! in ascending order of occurrence time of scheduled events
Type(Event), pointer :: Head, Tail
Type(Event), pointer :: Node, NewHead
! Rest is left out for you to fill in
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Subroutine DeleteEvent (H,T,Delete)
! This subroutine simply removes the first event from
! the event-queue and returns it
Type(Event), pointer :: H,T
Type(Event), pointer :: Delete
if (.NOT.Associated(H)) then ! queue-empty and an error
Print *, "ERROR:::EVENT-QUEUE IS ALREADY EMPTY"
Return
end if
Delete => H
H => H%Next
! If this new head is empty, Tail must become empty as well
if (.NOT. Associated(H)) Nullify(T)
return
End Subroutine DeleteEvent
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
End Module Events
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Program SingleServer
Use Events
Implicit None
Integer, parameter :: Hq=2000, Lq=4000
LOGICAL IDLE
Integer HIGHQ(Hq,2), LOWQ(Lq,2), TOTAL(2), & !CUMULATIVE QUEUE SIZES
QSIZE(2), QMAX(2), FRONT(2), JOBS(2), &
WAIT(2), & !CUMULATIVE WAITING TIMES IN EACH QUE
LASTCH(2), & !LAST QUEUE SIZE CHANGE TIME
TIME, & ! CURRENT SIMULATION TIME
LASTIDLE, & !LAST server IDLE TIME
IDLETIME, & !CUMULATIVE server IDLE TIMES
OFTEN, & ! INTERARRIVAL TIME UpperBound
ServHigh, & !Service time upperbound
TotalTime, Inputs, K
Logical More
Type(Event), Pointer :: Head, Tail, Node, Current
Integer testing /0/
! INITIALIZATIONS
Qmax = (/Hq, Lq/)
totaltime=500000
Inputs=0
More = .true.
Do while(More)
Print *, "--------------------------------"
Print *, 'Type in'
Print *, "The InterArrival Time Upperbound"
Print *, 'And Service Time Upperbound!'
Read(5,*,End=9999) Often, ServHigh
print *, '------------------------------------------'
PRINT 999, 'UPPER BOUND FOR INTERARRIVAL TIME :::', OFTEN
Print 999, 'UPPER BOUND FOR SERVICE TIME:::::::::', ServHigh
999 Format (1X, A, I5)
Inputs = Inputs+1
LASTIDLE=0
TIME=0
IdleTime=0
IDLE= .TRUE.
DO K=1,2
QSIZE(K)=0
TOTAL(K)=0
LASTCH(K)=0
JOBS(K)=0
WAIT(K)=0
FRONT(K)=0
end do
!
Call Initialize (Head,Tail)
Call MakeNode(1,0,Node)
CALL InsertEvent (Node,Head,Tail) !FIRST ARRIVAL EVENT SCHEDULED
Call MakeNode(2,0,Node)
CALL InsertEvent (Node,Head,Tail) !FIRST FINISHING EVENT SCHEDULED
Call MakeNode(3,TotalTime,Node)
CALL InsertEvent (Node,Head,Tail) !SIMULATION TERMINATION
!
! LOOP TO CONTINUE THE SIMULATION BY PICKING UP AN EVENT
! after another until simulation total time comes up.
TIME=Head%OccurTime
DO WHILE (TIME .LT. totaltime)
Select Case (Head%EType)
100 Case(1) ! NEW ARRIVAL
CALL ARRIVAL
IF (IDLE) CALL FINISHING
200 Case(2) ! FINISHING EVENT
CALL FINISHING
Case(3) ! Termination Event
Call Finishing ! Just update statistics
Call Qdelete(1)
Call Qdelete(2)
Exit
Case Default ! Safety measure
Print *, "ERROR: ILLEGAL EVENT TYPE IN EVENT-QUEUE:"
End Select
Call DeleteEvent (Head,Tail,Current)
Time=Head%OccurTime ! Advance the simulation time in all cases
! unless it is over
END DO !END OF ONE SIMULATION RUN
!
! END OF ONE SIMULATION RUN!!!!!
!
Print *, '-------------------------------'
Print *, " SIMULATION STATISTICS"
Print *, "-------------------------------"
Print *, " High-Q: Low_Q: Total:"
PRINT 777, 'JOBS PROCESSED: ', JOBS, jobs(1)+jobs(2)
777 Format (1X, A, 3I8)
PRINT 788, 'AVERAGE QUEUE SIZES: ', &
1.0*TOTAL(1)/totaltime, &
1.0*TOTAL(2)/totaltime, &
0.5*(Total(1)+Total(2))/TotalTime
788 format (1X, A, 3F8.2)
PRINT 788, 'AVERAGE WAITING TIMES:', &
1.0*WAIT(1)/JOBS(1), &
1.0*WAIT(2)/JOBS(2), &
1.0*(wait(1)+wait(2))/(jobs(1)+Jobs(2))
PRINT 888, 'TOTAL IDLE TIME PERCENTS:::', 100.0*IDLETIME/TotalTime
888 format (1X, A, F10.2, "%")
END DO !!!END OF ALL SIMULATION RUNS
9999 Print *
Print *, "SIMULATION OVER AFTER PROCESSING", Inputs, "INPUTS."
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Stop ! Just in case.
Contains
Subroutine MakeNode (EventType, EventTime, Item)
Type(Event), pointer :: Item
Integer EventType, EventTime, Err
Allocate (Item, Stat=Err)
if (Err /= 0) then
Print *, "MEMORY ALLOCATION FAILURE:::"
Stop
end if
Item%EType = EventType
Item%OccurTime = EventTime
Nullify (Item%Next)
return
End Subroutine ! Mandatory
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
SUBROUTINE QINSERT(Q,REQUEST)
Integer Q, Loc, Request
IF (QSIZE(Q) .GE. QMAX(Q)) THEN !QUEUE IS FULL
PRINT*, 'ERROR::: QUEUE IS FULL::::', Q
RETURN
END IF
QSIZE(Q)=QSIZE(Q)+1
LOC=FRONT(Q)+QSIZE(Q)
IF (LOC .GT. QMAX(Q)) LOC=LOC-QMAX(Q)
IF (Q .EQ. 1) THEN !!HIGHQ!!!
HIGHQ(LOC,1)=TIME !ARRIVAL TIME!!!
HIGHQ(LOC,2)=REQUEST !Service REQUEST TIME!!!
ELSE
LOWQ(LOC,1)=TIME
LOWQ(LOC,2)=REQUEST
END IF
! UPDATE CUMULATIVE QUEUE SIZE
TOTAL(Q)=TOTAL(Q)+ (TIME-LASTCH(Q))*(QSIZE(Q)-1)
LASTCH(Q)=TIME
RETURN
END Subroutine
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
SUBROUTINE QDELETE(Q)
! This subroutine does the following:
1. Check to see If the given queue is empty.
If it is then an ERROR-CASE and return.
2. Else
2.a update Front and Qsize of the queue to get the request
time to schedule a FINISHING event by:
Call MakeNode(2, Time+Request, Node)
CALL InsertEvent(Node, Head, Tail)
2.b Update
Total(Q)
JOBS(Q)
WAIT(Q)
LastCh(Q)
if (Qsize(Q) == 0) Front(Q) = 0
END Subroutine
!*********************************************
! SUBROUTINE ARRIVAL
!*********************************************
SUBROUTINE ARRIVAL
Integer Request, After, Type
REQUEST=KRAND(ServHigh-10)+10
TYPE=1
IF (REQUEST .GT. 0.2*(ServHigh-10)+10.001) TYPE=2
CALL QINSERT(TYPE,REQUEST)
AFTER=KRAND(OFTEN)! It is between 0 and OFTEN
Call MakeNode(1,Time+After,Node)
CALL InsertEvent(Node,Head,Tail)
RETURN
END Subroutine
!********************************************
! FUNCTION KRAND(MAX)
!********************************************
Integer FUNCTION KRAND(MAX)
! Computes and returns an integer between
! 0 and the given MAX
Integer Max
Integer SEED/9753135/
Krand = Ran(Seed) * Max + 0.0001
RETURN
END Function
!*********************************************
! SUBROUTINE FINISHING
!*********************************************
SUBROUTINE FINISHING
Integer front1, front2
! THIS SUBROUTINE IS CALLED WHENEVER A JOB HAS BEEN FINISHED,
! OR THE SIMULATION IS OVER.
! HENCE, IT DOES:
! 1. IF server HAS BEEN IDLE, UPDATE CUMULATIVE IDLE TIME
! AND RESET THE LAST IDLE TIME.
! 2. IF BOTH QUEUES ARE EMPTY, RESET IDLE AND LASTIDLE,
! AND RETURN.
! 3. ELSE, IF THE LOWQUE IS EMPTY, THEN DELETE THE HIGHQUE
! 4. ELSE, IF THE HIGHQUE IS EMPTY, DELETE THE LOWQUE.
! 5. ELSE, (BOTH QUEUES ARE NON-EMPTY) SO DECIDE WHICH
! QUEUE HAS TO BE DELETED. AND DELETE THAT QUEUE AND
! RESET IDLE INDICATOR.
! In all, this subroutine deletes a queue if both are not empty
by calling Qdelete(Q) and updates if necessary
IdleTime
LastIdle and
Idle