Chapter 2 Modeling Complex Systems Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 1 of 38 CONTENTS 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 Introduction List Processing in Simulation A Simple Simulation Language simlib Single Server Queueing System with simlib Time Shared Computer Model Multiteller Bank with Jockeying Job Shop Model Efficient Event List Manipulation Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 2 of 38 2 1 INTRODUCTION Complex systems usually require complex models difficult to code from scratch in general purpose language Need some help more simulation oriented software In this chapter will discuss list processing a central activity in most simulations and high level simulation software Develop and illustrate a set of support routines simlib that does several routine simulation tasks List processing event list management random number and variate generation statistics collection output reporting Will do this in C FORTRAN codes available on book s website simlib is not a real real simulation language Doing it here to illustrate what s behind commercial simulation software enable modeling of more complex systems Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 3 of 38 2 2 LIST PROCESSING IN SIMULATION Most simulations involve lists Queues event list others A list is composed of records Record Usually corresponds to an object in the list By convention a record is represented as a row in a twodimensional array matrix representing the list A person in a queue list an event in the event list A record is composed of one or more attributes Attribute A data field of each record By convention attributes are in columns Examples of records lines of attributes columns Queue list time of arrival customer type service requirement priority Event list event time event type possibly other attributes of the event Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 4 of 38 2 2 1 Approaches to Storing Lists in a Computer Sequential allocation approach used in Chap 1 Records are in physically adjacent storage locations in the list one record after another Logical position physical position Linked allocation Logical location need not be the same as physical location Each record contains its usual attributes plus pointers or links Successor link or front pointer physical location row number of the record that s logically next in the list Predecessor link or back pointer physical location of the record that s logically before this one in the list Each list has head pointer tail pointer giving physical location of logically first and last records Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 5 of 38 2 2 1 Approaches to Storing Lists in a Computer cont d Advantages of linked over sequential allocation Adding deleting inserting moving records involves far fewer operations so is much faster critical for event list management Sequential allocation have to move records around physically copying all the attributes Linked allocation just readjust a few pointers leave the record and attribute data physically where they are Reduce memory requirements without increasing chance of list overflow Multiple lists can occupy the same physical storage area can grow and shrink more flexibly than if they have their own storage area Provides a general modeling framework for list processing which composes a lot of the modeling computing in many simulations Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 6 of 38 2 2 2 Linked Storage Allocation Will treat doubly linked lists could define singly linked Physical storage area for all lists max of say 25 lists Array with say 15 rows 4 columns for attributes a column for back pointers a column for forward pointers Also need array with 25 rows 2 columns for head and tail pointers of each list Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 7 of 38 2 2 2 Linked Storage Allocation cont d Example Two queues FIFO Shortest Job First event list see text for different examples FIFO queue attrib1 time of arrival SJF queue attrib1 time of arrival attrib2 service requirement insert new records customers to keep list ranked in increasing order on attrib2 remove next customer to serve off top of list Event list attrib1 future event time attrib2 event type Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 8 of 38 2 2 2 Linked Storage Allocation cont d Need Utility code to manage all this Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 9 of 38 2 3 A SIMPLE SIMULATION LANGUAGE simlib Some C functions rudimentary simulation language Source code in Appendix 2A and on book s website Also available in legacy FORTRAN on book s website Capabilities List processing pointers file a record remove a record Processes event list Tallies statistical counters Generate random numbers variates from some distributions Provide standard output optional Not a real simulation language incomplete inefficient But illustrates what s in real simulation software how it works Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 10 of 38 2 3 A Simple Simulation Language simlib cont d Heart of simlib is a collection of doubly linked lists All live together in dynamic memory space allocated as new records are filed in lists freed when records are removed from lists Maximum of 25 lists Records in lists can have a maximum of 10 attributes Data are stored as type float Uses dynamic storage allocation so total number of records in all lists is limited only by hardware List 25 always reserved for event list Always attribute 1 future event time attribute 2 event type attributes 3 10 can be used for other event attributes Kept sorted in increasing order on event time next event is always on top User must include simlib h for required declarations definitions simlib h in turn includes simlibdefs h Simulation Modeling and Analysis Chapter 2 Modeling Complex Systems Slide 11 of 38 2 3 A Simple Simulation Language simlib cont d Key simlib variables and constants sim time simulation clock updated by simlib next event type type of next event determined by simlib transfer i float array indexed on i 1 2 10 for transferring attributes of records into and out of lists maxatr max number of attributes in any list defaults to 10 but user can initialize to 10 for improved efficiency cannot