Re: Lahman, how ya doing?

Responding to Hansen...

class EventElement
{
private:
Object* recipient;
int event_id;
int tick_count;
public:
EventElement (Object* r, int e, int t)
   {recipient = r; event_id = e; tick_count = t;};
int getTickCount() {return tick_count;};
}

class Timer
{
private:
EventQueue* queueManager;
EventElement eventList[MAX_EVENT_COUNT];
int tick_count;
int next_event;
public:
Timer (EvetnQueue* e)
   {queueManager = e; next_event = 0; tick_count = 0;};
void add_event (Object* o, int e, int t);
void tick()
void reset() {tick_count = 0;};
}

void Timer::add_event (Object* o, int e, int t)
{
EventElement event = new [] (o, e, t);
eventList[next_event] = event;
next_event++;
if (next_event == MAX_EVENT_COUNT)
   // signal exception.
};

void Timer::tick()
{
tick_count++;
for (int i = 0; i < next_event; i++)
{
 int eventTickCount = eventList[i].getTickCount();
 if ((tick_count MOD eventTickCount) == 0)
    queueManager->push(&eventList[i]);
}
}


Here in Timer::tick() you're pushing pointers on to the queue from a pool of events held by Timer. Not relevant to my simulation, but generalizing to a case where any amount of time can pass between when an event is pushed on to the queue and when it is popped off and processed, it seems you can have two identical events going to the same object. I guess that still doesn't matter the way you've set it up, but if I'm passing data with an event (and you've opined on that practice!) I can imagine the content of the first being modified by preparing the second. So I'd want to make a copy for the queue, and destroy the copy at the end. Fire and forget, but somewhat different queue behavior, and all events must be processed that way if any of them are.

Actually, I wouldn't have the same event going to the same object on a given tick. I might send the same event to multiple objects on a tick, though. And I would certainly send the same events to the same objects on different ticks.


Remember here that I'm generalizing beyond the simulation, to a system that might have any kind of delay between the sending and receiving of an event. You wouldn't send two of the same event to the same object on a given tick, but you might send two of the same event to the same object on two different ticks before it receives the first event.

There are delays and there are delays. There are a couple of assumptions that the OOA/D developer needs to make about interacting object state machines to preserve sanity. The implementation must somehow ensure that those assumptions prevails.

One assumption is that self-directed events have priority over external events. This is necessary because the main reason one uses self-directed events is to get the state machine to some start /after/ some state variable has been updated. If the state variable lives in the state machine's object, it will probably be updated by a state machine action (e.g., counting acknowledgments to a broadcast event) so the condition prevails when the action completes and the state machine needs to get to the new state ASAP.

Another similar assumption is that multiple events between the same sender and receiver state machines will be consumed in the same order that they were generated. This assumption is necessary because handshaking protocols would be impossible without it. This assumption applies here. IOW, the delay is arbitrary only within limits.

[It is common to deal with this in the event queue manager. But the event packet needs to be more complicated because one needs the sender identifier and some sort of timestamp associated with the event. Since the receiver's events are all placed on the same queue, this will Just Work, even if the objects are distributed. Distributed interoperability infrastructures like CORBA orbs provide exactly this sort of thing under the hood using GMT timestamps so that sender and receiver can be in different time zones. Interoperability infrastructures are always event-based and they employ a queue on each side. The timestamp is used to ensure that the queues are popped in the same order as the other side was pushed.]

And if I don't pass data in the event, but data still needs to be passed, I don't know how to pass it. Using Timer as a specific example of the more generic question, it *could* be given an accessor function get_time(), a receiving object *could* get the time directly through that. But if it's to process event1 using time1 and then event2 using time2, and Timer has time3 by the time event1 hits the object and time4 by the time event2 hits it, I can't think of an easy alternative other than to stuff the data you need into the event so that it's all there.

You only need to pass data on an event if data integrity requires that when the event is consumed the value accessed be the value when the event was sent (as opposed to it current value). That's because the software must already support a means for the responding action to access the current value synchronously. That's because in the OOA/D paradigm one accesses knowledge synchronously on an as-needed basis. So one uses event data packets when one /doesn't/ want the current value.

I assume what you are angling for here is the issue in the other message: providing an absolute value of current time for computing a slope. If absolute time is measured in terms of number of ticks, then you could deal with the skip problem by having Timer increment a tick count for actual ticks processed. Whoever needs the absolute time could then ask Timer for the current value of that tick count.


That is what I was angling for, and I think I've resolved that in the other message. So, send data in an event when the value needed is what existed when the event was sent, and not when it is consumed. In my specific application, an event queue is hardly needed since the events are consumed immediately, so one way or the other is all good.

OK. I talked about this in the other message today, so I won't add anything here.

So what happens if the queue empties before...



Things are more complicated in a truly asynchronous system where the queue may have to wait for an external event. (Or for events generated by a real- or scaled-time timer.) But then the push just needs to restart the queue operation if the event count is exactly 1 after the push. Since you are using simulation ticks rather than scaling, this


Oh, okay. I suppose somewhere in the bowels of the queue it will be looping until it finds a quit event directed to queue?

Not exactly. There can be times when the queue is completely comatose.


But something must be looping or the program will hit the return 0 at the end of main(), and quit. 

As long as we are talking about generalities...  B-)

There is nothing that requires a program to execute instructions continuously (though stopping it may require explicitly inserting a HALT instruction). Events can be external to the application. For example, memory resident programs are designed to be dormant almost all of the time waiting for somebody to invoke a callback to push an event via RPC or whatever. That's precisely because one doesn't want a memory resident program to be constantly sucking down CPU cycles for a polling loop.

You've talked about the application actually running multiple simulations. Between those simulations you want the queue to be quiescent because you don't want a polling loop to be stealing cycles from the UI or whatever is being done between simulations. IOW, between simulations the event queue is just another object in the application that isn't being accessed. So the default behavior in a reusable queue should be that it doesn't do anything at all when it isn't needed -- which is no different than any other object in the application.

As a simplified version of an queue manager consider:

class EventQueue
{
private:
   int event_count;
   Event* next_pop_event;
   Event* nex_push_event;
   Event* (event_list[MAX_EVENTS]);
   void pop ()
   void start ()
public:
   void push (Event* e);
}

EventQueue::pop()
{
   // do processing to invoke responding action
   // I think I already went over this part in another message
   // This will essentially be a synchronous cal to the
   // responding state action that will return when the action
   // is complete.

   event_count = event_count - 1;

   // update next_pop_event for FIFO in event_list rung buffer
}

EventQueue::start()
{
   // launch thread for popping events around following code
   // so that start and push can return while queue is emptied
   while (event_count > 0)
       pop();
}

EventQueue::push(Event* e)
{
   // push e into event_list ring buffer

   event_count = event_count + 1;
   if (event_count == 1)
      start();
}

The point here is that when the events have been exhausted, the thread initiated from start terminates and the queue is completely idle until somebody pushes an event.

[Caveat. This is oversimplified because to be thread-safe in concurrent processing one would have to pause the pop thread, provide some temporary buffer for pushed events that pop checks, or provide some other means of synchronizing the update of event_count.]


But good enough for my immediate needs.

Alas, not necessarily. Remember that Timer pumps a bunch of events on the queue in a burst, essentially by table lookup & copy. If the first event consumed finishes before that burst is done you may have a race condition for updating event_count (e.g., the test in push may not "see" the same value that was incremented in the previous statement).

[One quick & dirty way around this (in C/C++) is to set/unset a semaphore around the event_count processing in push, declare the semaphore volatile, and insert a "while (semaphore) ;" just before the event_count update in pop. Since push will be at a higher priority than pop, the blocking won't be significant.]

doesn't matter because you just just need an event to Timer to trigger tick() when all the tick's processing is completed. In your case there are a couple of easy options: (1) have Timer put a self-directed event on the queue as the last event or (2) have the event queue manager call tick() when it is empty. (Tick() can generate an event for a graceful exit if, say, the maximum simulation ticks have executed to provide an exit.)


Hey, I just told you about (1)! Some of what you've been telling me is starting to make more sense in retrospect.

While (2) is valid, it has a problem. Once one gets the event queue manager right, one wants to reuse that effort across applications. If the event queue gets into the business of generating special events to particular application objects, it won't be reusable.


Well, I did see the results of a survey of programmers about the advantages of OOP, and code reuse was at the bottom. It was still an advantage to be included in a list, but it was the least of the advantages. Some shops that have tried to make generic and eminently reuseable libraries have found it so time-consuming that it was just abandoned.

So the programmers that were surveyed write their own String or Array classes for each application? Good luck. Everybody gets reuse of computing space objects through commercial libraries. That's because they are very narrowly defined data holders. So is an event queue; it's just a smart stack.

As far as object reuse in general is concerned, I agree it never lived up to the hubris of the '70s and early '80s. The problem is that one can provide quite different valid syntaxes for the same semantics. So when an object moves to a new reuse context the new client may be expecting to use a different access syntax (interface) than the one provided with the object for the original client. So even though client and service are very clear about the semantics of the service, they can't talk to one another.

Basically there are three solutions. One can modify the new client to use the access interface provided with the service rather than the one it wants to use. That means touching the implementation of the client, which is a major no-no in OO development. The second possibility is to add the interface that the new client wants to see to the service. That results in rapid increase in the complexity of the interface, much of which is redundant. That redundancy hurts if one uses the interface to "tailor" the object (e.g., provide a burdened cost from a base cost and burden rate) because it requires double edits if the tailoring changes, which is fragile.

The third solution is to provide "glue" code between the interface the reuse client wants and the interface the service object provides (e.g., a Facade pattern). At the object level that leads to overhead because of indirection and glue. Since object methods are usually small, that overhead can be quite significant. (John Lakos, in "Large Scale C++ Software Design", has measured three orders of magnitude hit doing similar things for OOP dependency management.)

Since none of these are very palatable at the object level, object reuse has pretty much gone by the wayside for problem space objects. However, the computing space objects are very narrowly defined and their behaviors are are defined mathematically so they are consistent across application contexts. That allows one to define a single interface that everyone can use. Hence we have lots of commercial class libraries for the nuts & bolts stuff.

BTW, the third solution is much less of a problem at larger scales, like subsystems. Generally at that level (if one is using disciplined event-based data transfer interfaces) the overhead is insignificant. So reuse is alive and well at the subsystem level. [My blog discusses this in the category on Application Partitioning. There is actually a formal model for two-way subsystem interfaces that allows one to provide local "glue" in complete isolation from the implementations of either subsystem.]


*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl@xxxxxxxxxxxxxxxxx
Pathfinder Solutions  -- Put MDA to Work
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
(888)OOA-PATH



.

Relevant Pages

  • Re: Lahman, how ya doing?
    ... Object* recipient; int event_id; ... Timer ... Not relevant to my simulation, but generalizing to a case where any amount of time can pass between when an event is pushed on to the queue and when it is popped off and processed, it seems you can have two identical events going to the same object. ... given tick. ...
    (comp.object)
  • Re: Lahman, how ya doing?
    ... >> A priority queue is an interesting idea. ... So Timer just enqueues the event on the right queue. ... >effectively starts at the same time on the current tick. ... >was triggered just gets time-sliced based on priority. ...
    (comp.object)
  • Re: Lahman, how ya doing?
    ... >> of events held by Timer. ... >> to make a copy for the queue, and destroy the copy at the end. ... I might send the same event to multiple objects on a tick, ... >software must already support a means for the responding action to ...
    (comp.object)
  • [PATCH] i386 No Idle HZ aka dynticks 051221
    ... All the tick skipping data is per cpu now, allowing each cpu to skip ticks ... best way to reprogram the timer, and selects the most reliable one. ... +static inline int account_timer ... +static inline void dyn_early_reprogram ...
    (Linux-Kernel)
  • Re: Lahman, how ya doing?
    ... Here in Timer::tickyou're pushing pointers on to the queue from a pool ... Using Timer as a specific example of the ... >>>current simulation tick is completed. ... It pops events until the queue is empty, ...
    (comp.object)