discrete event simulation question

[jack]

Hi guys,


I am working on a project which requires an implementation of discrete
event simulation in C using linked lists. I would greatly appreciate if
someone could provide with some sources on how to approach DES. Please
help me out.

Thanks,
Jack

 

[Eric Sosman]

Hi guys,


I am working on a project which requires an implementation of discrete
event simulation in C using linked lists. I would greatly appreciate if
someone could provide with some sources on how to approach DES. Please
help me out.

You don't have a C question (yet -- once you start on
the implementation, you may have C questions), but a question
about algorithms and/or data structures.

<off-topic>

The fundamental form of a discrete-event simulation is that
there's a queue of events scheduled for various times in the
simulated future. You remove the earliest of those events from
the queue, advance the global "clock" to the scheduled time
of that event, and do whatever event-specific processing the
event requires. This processing may add new events to the
queue (scheduled for times no earlier than the clock, of
course), may cancel scheduled events that have not yet happened,
and may change the scheduled time of some future events (which
can be regarded as a cancellation plus adding a new event, if
that's convenient). The event processing also modifies the
state of the simulated system in whatever ways are appropriate,
and may even cause the simulation to terminate.

So: The central data structure for the simulation framework
is a priority queue, ordered by the events' scheduled times.
Other data structures are usually problem-specific, keeping
track of the automobiles or mesons or whatever knick-knacks
circulate in the simulated system. There are *many* data
structures that implement such things; you need to choose a
few and then (if puzzled) come back here with the problems
you've encountered in writing the code for them.

(In my brief and inglorious career as "Lecturer in
Mathematics," I used to teach this stuff. At the time, it
went for 0.5 semester-hours' credit; nowadays, I understand
that merely learning a programming language or learning how
to operate a spreadsheet earns more. O tempora! O mores!)

</off-topic>

 

[jack]

Thanks a lot Eric for your effort. I shall start working on the
algorithm and get back to you with some C questions.

Jack

 

[jack]

Hi,

I've been working on an Discrete event simulation problem using linked
lists(LL). The algorithm looks as follows:

struct linkedlist
{
int event;
int queue; //FIFO on which the event acts
double timer; // time value embedded in each node in the LL on
which the LL is sorted.
};

The timer field has the time based on which, the time for a particular
node is set. The timer value for a node indicates when the node is to
be read and the corresponding event executed. The event loop looks
something like this:

struct linkedlist *ptr;
ptr = (struct linkedlist *)head; (points to the beginning of LL)
while(1)
{
ptr = ptr->next ( advance the linked list)
execute ptr->event on ptr->queue
get time from gettimeval (global_time)
add the time taken for execution of one event to the global time
create new node with another event, the queue on which the event
acts and the time value.
Add the new node to the linked list based on time (The list is
ordered based on increasing time)
get time from gettimeval (global_time)
sleep(ptr->time - global_time)
}

Now, is this the way we schedule time in a event scheduling algorithm?
If not how do we do it? I would be more than glad if you can provide me
with some documentation.....on this stuff i.e., time scheduling..I am
asking this coz...I am getting -ve vlaues of (ptr->time - global_time)
.. This means that the event is taking more time than its required to
take. But, then..how do we set the time for that event before hand and
store it in the node? Any info on this...is welcome.

Jack

 

[osmium]

I've been working on an Discrete event simulation problem using linked
lists(LL). The algorithm looks as follows:

I think this is too complicated a problem to be of much help without a
blackboard. There are likely terminology problems and simple
misunderstandings of what is meant. But I will give it a brief try. First
of all, this may be helpful;

http://www.cis.temple.edu/~ingargio/old/cis307s95/homeworks/hints1.html

struct linkedlist
{
int event;
int queue; //FIFO on which the event acts
double timer; // time value embedded in each node in the LL on
which the LL is sorted.
};

The timer field has the time based on which, the time for a particular
node is set. The timer value for a node indicates when the node is to
be read and the corresponding event executed. The event loop looks
something like this:

struct linkedlist *ptr;
ptr = (struct linkedlist *)head; (points to the beginning of LL)
while(1)
{
ptr = ptr->next ( advance the linked list)
execute ptr->event on ptr->queue
get time from gettimeval (global_time)
add the time taken for execution of one event to the global time

No. Global time should only be advanced as needed to accommodate the due
time of the next item. But my guess is you probably did not mean what I
understood you to say. The change in state of the 'gadget' takes place in,
conceptually, zero time.

create new node with another event, the queue on which the event
acts and the time value.
Add the new node to the linked list based on time (The list is
ordered based on increasing time)
get time from gettimeval (global_time)
sleep(ptr->time - global_time)
}

Now, is this the way we schedule time in a event scheduling algorithm?
If not how do we do it?

Before an event releases control back to the main program, it computes the
time during which the event will be dormant. IOW, it says "Reactivate me at
time x" ( or time now + y).

I would be more than glad if you can provide me

 

[jack]

Osmium,

Thanks for your answer. The link which you provide partly
explained/addressed my problem . But ,I still dont get a picture of
what I should do. As I mentioned above:

I am alloting the 'due time' for each event in the following manner

due_time = global_time + (time one_data_transfer (That's the event
here) requires ) ------ 1

Now, I place the node in the linked list sorted on the order of
increasing due_time. And once I start to execute the event, If I happen
to finish the event before the designated due_time for that event, I
sleep for the remaining time. But THE MAIN PROBLEM is the time taken
for one event is exceeding the due_time sometimes(which it
shouldn't??)(I guess this is because,with equation---1, often it's so
happening that the difference between the due_times of two consecutive
nodes is less than the time one _data_transfer requires).

so I begun to question my the basic allocation of due_time which I did
in equation--1. Is that correct?

Jack

 

[osmium]

Osmium,

Thanks for your answer. The link which you provide partly
explained/addressed my problem . But ,I still dont get a picture of
what I should do. As I mentioned above:

I am alloting the 'due time' for each event in the following manner

due_time = global_time + (time one_data_transfer (That's the event
here) requires ) ------ 1

Now, I place the node in the linked list sorted on the order of
increasing due_time. And once I start to execute the event, If I happen
to finish the event before the designated due_time for that event, I
sleep for the remaining time. But THE MAIN PROBLEM is the time taken
for one event is exceeding the due_time sometimes(which it
shouldn't??)

When the event is scheduled to be finished it damn well *has* to be
finished. There is no looking back, you can only look forward. For
example, if a read might result in error handling, the first estimate is the
scheduled time with no error, if an error occurs this is a new job, so to
speak. If necessary, change the initial estimate to the minimum time, when
it expires see what the situation is and reschedule another event if needed.

..

 

[jack]

You remove the earliest of those events from
the queue, advance the global "clock" to the scheduled time
of that event, and do whatever event-specific processing the
event requires. This processing may add new events to the
queue (scheduled for times no earlier than the clock, of
course), may cancel scheduled events that have not yet happened,
and may change the scheduled time of some future events (which
can be regarded as a cancellation plus adding a new event, if
that's convenient). The event processing also modifies the
state of the simulated system in whatever ways are appropriate,
and may even cause the simulation to terminate.


What exactly do you mean by global "clock" here? Is it the system
clock? If its system clock, how do we use it to set the due_time in
each node? If its not system clock , then how exactly do we manage the
global time?

The reason why I ask this is I am using system clock as the global time
and assigning the due_time to each node in the Linkedlist based on the
following value:

due_time_for_event => current_system_clock_time +
time_taken_for_one_event.

( In my case, the event is consumption of data by a FIFO. Hence the
time_taken_for_one_event i.e., consumption would be
(1/Consumption_rate_of_FIFO)).

But, because of this, some times(infact many times) its so happening
that the due_times of 2 adjacent nodes are overlapping. Because of this
, the event's execution is still going on when the next event's
due_time has already elapsed and its due. How do I deal with this in a
sequential program? How do I maintain global time? What is its relation
to system clock time? How to I use to set the due_time in each node so
that each event gets its due_time as atleast greater than the previous
event's due_time by "time_taken_for_one_event"?

Thanks,
Jack

 

[Al Balmer]

You remove the earliest of those events from
the queue, advance the global "clock" to the scheduled time

I think it's time to repeat Eric's original reply:

" You don't have a C question (yet -- once you start on
the implementation, you may have C questions), but a question
about algorithms and/or data structures."

You'd probably get more and better answers in comp.programming or some
other group where this is on-topic.

 

[jack]

I think it's time to repeat Eric's original reply:

" You don't have a C question (yet -- once you start on
the implementation, you may have C questions), but a question
about algorithms and/or data structures."

You'd probably get more and better answers in comp.programming or some
other group where this is on-topic.

Thanks Al.

 

[Chris McDonald]

I think it's time to repeat Eric's original reply:

" You don't have a C question (yet -- once you start on
the implementation, you may have C questions), but a question
about algorithms and/or data structures."

You'd probably get more and better answers in comp.programming or some
other group where this is on-topic.

Agreed, and the folks in comp.simulation are very friendly, too.