Re: Lahman, how ya doing?

Responding to Hansen...

A priority queue is an interesting idea. I suppose when that empties it goes to the normal queue. Some systems let your prioritize tasks on a scale of 0 to 7 or so, I wonder if they have eight queues.

Welcome to real-time. B-) I know R-T people dealing with hard R-T constraints who argued that WinCE was a unusable for R-T work because it only supported 32 priorities for threads.


I'm no R-T person, but... 32 ain't enough? Well, I'm sure they know what they're doing.

It's not so much about using all the threads as providing a broad range of priorities. Suppose one wanted one clump of processing to execute 50X as fast as another clump. To do that one wants it to get 50X more CPU cycles. If there are only 32 threads then one might only be able to get it to run 32X as fast. (That's an oversimplification, but it is the basic idea.)

However, there are situations where one needs lots of threads. Suppose you had 64 Thermometers and at run time you wanted to give priority to some of them dynamically (e.g., where the temperature gradient was greatest) because processing all 64 samples at once can't be done in a single "tick". The easy way to do that is to put each one in a thread and then manipulate the thread priorities as conditions changed.

For the hypothesized example, the event queues would be entirely separate object instances for the threads. Since computing the average is so rarely done one can be confident it will get done long before it should be triggered again. So Timer just enqueues the event on the right queue. The Timer events will get consumed (popped) immediately so everything effectively starts at the same time on the current tick. Hence there is no need to merge events back into a "normal" queue; the processing that was triggered just gets time-sliced based on priority.


But really, a lot of this just isn't much of a problem if timing information is passed to an object. E.g. in our real equipment we have some CAMAC counters that accumulate NIM pulses until they're stopped, read, and reset. And one channel is connected to a precision time standard. We're making a precision measurement, if the timing is off by 1/60 second that would be horrible. But for as long as the other channels count events from the charged particle detectors, the timing channel will be counting ticks from the time standard, and we can simply divide to find the counting rate to a precision that's limited by counting statistics but not by time resolution.

Unless there are gross timing errors that e.g. would cause the control system to go unstable or get too choppy to collect good data, I think just passing an elapsed time to the parts that need it is a simple and satisfactory solution.

Remember you already have a sort of priority in the order of event generation in Timer.

I assume that the CAMAC counters are pure hardware (i.e., the count is incremented in a hardware register.)


Yep, all hardware. All counters start counting at the same time when triggered, they all stop at the same time when stopped, and the values can be read at one's leisure.


At that point the simplest possible thing the driver would be to (1) write the stop register, (2) read the accumulator and save the value as an attribute in an existing object somewhere, and (3) write the reset register. That needs to happen /exactly/ on your 1/60th second tick no matter what else happens in the system.


The timing isn't crucial because there's a time standard feeding into one of the counters to tell us how much time has passed. The CAMAC crate is part of the measurement that I don't think I've told you about; they count events from charged particle detectors in a beam monitor that is to be calibrated. The calibration is done with the radiometer that measures the heat of reaction of the beam dumping into a target. That radiometric measurement is done by an HP voltmeter measuring voltage drops across the heater resistor and a precision shunt resistor that gives current I=V/R. The radiometric measurement depends on the heater current changing slowly in a period after it's been allowed to settle. E.g. two minutes to settle, average the power for the remaining eight minutes in a ten minute half-cycle.

So we get a count rate = counts/time, and if we're late in triggering the counters we get more counts, but we also get more timer ticks, it doesn't change the rate.

So that's the background I'm working with-- it's not crucial to get the timing exactly right, we just need to know what the timing is.


So I would put that <rather trivial> operation in the highest priority thread (i.e., put the relevant event queue manager in that thread).

That ensures that the count will be precise so long as the 1/60th event is consumed in a timely fashion. But you can get that for free from Timer by making that Timer event be the first one generated off the tick if it were a 1/60th tick.

The next problem is making sure the processing that needs that count get done accessing it before another 1/60th tick is processed. That may Just Work because the value in the attribute is quickly processed and converted to some other form or a history of values are stored until they are processed. I suspect one of these would be the case even if the rest of the feedback processing was pretty low priority.

However, if that isn't true there is a fallback position that is a variation on your proposal: pass the attribute value to subsequent processing rather than accessing it synchronously on an as-needed basis. This is a variation on the notion of "snapshot" data integrity. No matter how long the feedback loop processing takes, all you have to do is make sure that the first step extracts the value from the attribute and passes it to any subsequent processing via event data packets. Even at low priority that first step gets kicked off _on the same time tick_ so it should be able to access the attribute stored by the first event before the next tick no matter how low its priority is.


I think I can connect to this by way of the CAMAC counters-- the counters hold the snapshot. As long as it stops and starts counting the particle detectors and the clock at the same time it doesn't matter, to a first approximation, how long it takes to get the data out and process it.

I was assuming the counters (plural) needed to be synchronized (i.e., they all counted over roughly the same time slice). That implies someone is starting them (i.e., an event goes to each CAMAC) at the same time and someone else is reading them (i.e., the event goes to the reader) at the same time. If that isn't the case, I was addressing a different problem.

computation. Then my code in Timer.tick for the event generation loop might look something like:

    int eventTickCount = eventList[i].getTickCount();
    bool isReady = eventList[i].getRecipient()->isReady();
    if ((tick_count MOD eventTickCount) == 0)
    {
       if (isReady())
          queueManager->push(&eventList[i]);
       else
          deferredBitmap |= (1 << i);  // set deferral of event


Woah, what are you doing to deferredBitmap there? Looks kinky.

Again, my R-T/E background is showing. One gets used to bit-wise processing because hardware real estate is usually precious to the Hardware Guys and they cram multiple fields into a single register. So masking, shifting, and bitwise AND, OR, and XOR operations are a Way Of Life. A logical extension of that is that bitmaps become very natural to use. (I've used bitmaps that were megabytes in length to save memory.)


That must be micocontrollers, because any computer you can get at Best Buy has a lot of room for sloppy software.

In your simulation that's true because you don't actually read the hardware to get the temperature. But I can't recall a case where in an actual instrument the value to be read was conveniently in one register and filled all the available bits. (In fact, one will probably have to read another register value just to determine how to scale the value once it is extracted.) So the real controller is almost certainly going to have to deal with things like split registers and multiple fields per register. That means bitwise operations become a Way Of Life.

However, bitmaps are very handy things for saving space and they can be more efficient when one has to deal with multiple boolean values. (More efficient because one gets to effectively load multiple values into a single ALU register to be processed by several instructions and one is <slightly> less subject to page faults.) Once one gets used to using them, one tends to find places where problem solutions can be cast in terms of bitmaps regardless of subject matter.

The case above is a classic example of a list where all one needs is a boolean value (i.e., the event deferred or not). That sort of thing is fairly common in any sort of software. [As an ex-R-T/E guy, when I wrote that code I am pretty sure I never even thought of using something like an array of char. B-)]

This code is just setting a bit for an event. The bit position in the bitmap is the index of the 1-bit boolean (true = set; false = reset or 0) for whether the event is deferred or not. I used the index of the event in eventList as the identity of the event in the bitmap. Alas, what isn't shown is an assumption in the declaration of deferredBitmap that the total number of events does not exceed the number of bits in the int or long associated with deferredBitmap. (If one needs more bits in the bitmap, then one needs macros for getting to the right bit and I was trying to keep it simple.)

[BTW, apropos of the point previously, I wasn't sure what you thought was kinky. So I addressed both the bitmap processing basics via indexed OR mask and the deferredBitmap variable assumption about bit count. That sort of coverage gets wordy too. B-)]


That |= symbol, mainly. I didn't even recognize it.

In C/C++ it is the bitwise OR operator. The dual "|=" operation is essentially a shorthand equivalent to

deferredBitmap = deferredBitmap | (1 << i);

[C was designed to be used on small machines (PDP8s) with limited, segmented memory so saving keystrokes was a major design goal for the compiler to allow more source code in memory at the same time during parsing.]

Finally, I thought you indicated that the "block" had the responsibility to decide whether its processing should be skipped for the current tick. If so, then I think that is a substantial dependency since Thermometer necessarily needs to understand /how/ Timer does its scheduling just to make that decision.


No, I was just assuming that it would be told an elapsed time when it's triggered. I had Timer taking care of all the timing functionality, including determining the elapsed time and passing it.

Right, but it is still making a decision based on that elapsed time. The fact that it /is/ an elapsed time is what is bleeding cohesion -- the "block" needs to understand something about scheduling semantics in general and the specific design context in particular. Avoiding that was why I belabored the difference between passing time vs. passing just the data to be processed (i.e., passing the data at the right time).

The first, though, that behavior messages very rarely carry data, that one accesses it directly from the source when it is needed, I need more on that. For starters, I thought behavior messages *do* carry data, or that they can. E.g. when a mouse down event is generated, you're going to want to know where it went down. But in the case we're discussing, I get the idea that if Controller needs to know an elapsed time it should ask Timer for the time, keep its own record of the previous time, and do its own calculation of elapsed time. Which is easily done. But then that requires that Controller knows that Timer exists, which I thought was something we're trying to avoid. 
<snip>

For the second part, I would try to find a way so that the object does not need to deal with a notion of elapsed time. That is inherently a scheduling issue and it would be bleeding cohesion from Timer for the object to deal with that. One way to do that in the overall context is the way I suggested above: pass the data itself. Now we are using the snapshot approach because the synchronization rules and our basic sequencing design may not provide timely data if we use synchronous access. Note that no /additional/ information or decisions are required; we just use the data passing mechanism rather than synchronous access to ensure DbC on data integrity is satisfied.


Remember that 8 pound sledge hammer? In my case, I've decided not to use an event queue because the strategy of the program has Timer as the sole passer of messages. There's no event that can be passed which can't be processed immediately. I've also changed the message passing to be closer to the example that you gave, and simplified it a little since it's a simulation and not R-T and so everything is carefully controlled. And I also load an elapsed time in the events before I send them off, which wouldn't be necessary if I'd used ticks as the time unit as you did, but I've decided to stay with seconds because it's closer to the real world, it's easier to change the time resolution, and because I don't really expect the processing time to become onerously long because of it. And what the heck is the difference between an event and a pure data transfer interface?

If Timer /does/ provide all the coordination, that's fine. But recently you indicated a possible problem with "witching" ticks where multiple activities can be triggered. That resulted in some processing not being done on some ticks in the real controller. If you want to simulate that, then using a separate, lower priority thread for the processing that isn't critical to the timing will give you those skips -- if the processing is event-based AND you daisy-chain the non-critical processing using peer-to-peer events (as we talked about) rather than events generated from Timer.

I would also argue that defining the sequencing by registering events with Timer is a very elegant way of describing a very critical part of the design. You can still use Timer.add_event for that initialization and then generate "events" synchronously, but it seems sort of inconsistent not to go the extra six inches and use an event queue when the design is effectively event-based.

[The event queue infrastructure is a one-time creation because it can be reused across applications. One just has to take a couple of moments to come up with an event identity scheme that will be both efficient and generic. So suppose you already had the infrastructure in a library. Wouldn't you make use of that reuse here?]

As to the question, an event represents the asynchronous form of a pure data transfer interface because one assumes an arbitrary delay between when the message is generated and when it is consumed. In a direct method call implementation the message response is synchronous with sending the message. In both cases, though one has a basic pure message-based data transfer interface: {message ID (event or method), <by-value data packet>}.

However, in any other situation where one could access consistent data synchronously, I would opt for asking Timer for any knowledge one needed.

[Caveat. This is the OOA view. When addressing nonfunctional requirements during OOP one may have to sacrifice pristine decoupling for practical optimization. Just as one might implement OOA state


I'm glad you brought that up, because I've found reasons to want to tell one class to get data from another class sometimes through one accessor function, and sometimes through another accessor function. Like the two sides of a thermal link-- the direction of heat flow depends on which thermal mass has the higher temperature, and it would be convenient to specify, say,

  heatsink.connect(&(link.side1));
  target.connect(&(link.side2));

Which would conveniently make the thermal link just another source (or sink) of heat that can be thrown into a list with the controller, the beam, noise, etc., and dealt with in a uniform way with no decision making, no need to pass a temperature only to thermal link sources of heat, etc. Or record different aspects of a block, like

  ChartRecorder chart1(&(controller.power));
  ChartRecorder chart2(&(controller.gain_term));

It is hard to tell without knowing what is going on in the innards, but these examples appear to simply be forms of relationship instantiation. In both cases I could easily envision the implementation just assigning to a particular pointer private variable that would subsequently be navigated during collaborations so that the message always got to the Right Place.


And I like the sort-of self-documenting nature of that compared with my original thought to give each class a generic output() member that outputs whatever that block is supposed to put out. But it turns out that in C++ pointers to member functions are a tricky thing. The advice I've found involves static wrapper functions, but you still have to specify which wrapper function, and that doesn't help if I want to select from several potential member functions in the same instantiation of a class. (Although there may just be a solution I don't see.)

This is getting dangerously close to OOP and, as a translationist, I try to never go there. B-) This sort of thing is very OOPL-dependent.


That's easily done with public variables, as in

class Class {
public:
  float power;
  float gain_term;
};

And that could be used with the above code as it is. But we're not supposed to make variables publicly accessible in C++. We're supposed to write

class Class {
private:
  float power;
  float gain_term;
public:
  float get_power() {return power;}
  float get_gain_term() {return gain_term;}
};

Which is fine as long as you don't need a pointer to the data. As far as I can see, that makes my scheme, if not unworkable, at least not worth the effort versus the brute force way of passing a parameter to indicate which number to get back, and using a switch statement to get the right value from a member function to return. 

You could do:

class AClass {
private:
    float* power;
    float* gain_term;
public:
    AClass (float* p, float* g) {power = p; gain_term = g;};
    float get_power() {return *power;};
    float get_gain_term() {return *gain_term;};
}

However, as a reviewer I would be all over you for another reason. Power and gain_term are at the knowledge attribute level and they must exist in some other object to be referenced. The client of get_power and get_gain_term should, therefore, be talking to that object rather than AClass. The proper OOA/D way to do this would be:

class DataHolder {
private:
    float power;
    float gain_term;
public:
    float get_power() {return power;};
    float get_gain_term() {return gain_term;};
}

class AClass {
private:
    DataHolder* myDataHolder;
public:
    DataHolder* getACLassDataHolder() {return myDataHolder;};
}

class Client {
private:
    AClass* myAClass;
public:
    void doIt();
}

Client::doIt() {
    DataHolder* myDataHolder = myAClass->getAClassDataHolder();
    ...
    tmp1 = myDataHolder->getPower();
    ...
    tmp2 = myDataHolder->getGainTerm();
    ...
}

The number of indirections is exactly the same. Depending on the compiler implementation and platform there could be small differences in performance but it is unlikely that that sort of overhead is going to sink the performance ship. If worse comes to worse, one might have to use your form. But there should be a clear, demonstrated need to do so because it really opens up a nasty door to foot shooting because semantically both AClass and DataHolder own the data.

To see the problem envision some maintenance where things change and the Client in this case needs (gain_term * 1.5). One way to fix that is in Aclass::get_gain_term() as {return *power * 5;}. Now someone else comes along in the next round of maintenance and needs to access the raw value of gain_term (i.e., without the 1.5 multiplier). They should use DataHolder::get_gain_term rather than AClass::get_gain_term. But semantically both classes seem to provide the same gain_term and it would be an easy mistake to cut & paste an access to ACLass::get_gain_term thinking one was getting the right value.

As I keep harping, the reason one uses OO development in the first place is to have more maintainable software. A big piece of that is /preventing/ exactly this sort of inadvertent foot-shooting. It is a little bit more round-about to navigate two relationship pointers to get to the data, but in doing so one is getting to the one and only true owner of the data. [Just getting there for the first round of maintenance should raise the issue of get_gain_term meaning two different things depending on who the client is! The maintainer would be almost forced provide a second, different accessor for the 50% increase semantics. If not, then on the second round it should be obvious that one needs a different accessor. So one has two opportunities where one is nudged to get it right.]

Another factor is that I understand my way, and I'm not sure I understand what you're talking about. I mean, relating to my special interface above, would I declare, for instance,

  heatsink.connect(&(link.new_side1));
  target.connect(&(link.old_side2));

For me to contrast things you will have to explain what heatsink, target, and link are and what the methods actually do in your implementation. As I indicated above, this might well be just a form of relationship instantiation that I am advocating.


*************
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?
    ... >> 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: cooperative multitasking scheme
    ... >> equal priority or where priorities aren't specifically used. ... where I choose not to use preemption at ... the action of the timing event is to move the process from the sleep queue ... I very much appreciate having a sleep queue. ...
    (comp.arch.embedded)
  • Re: Best way to design multithreading application
    ... The data acquisition is more important than UI updates, ... adding it to a Queue 1 as it acquires more. ... B, which is medium-to-high priority, loops over and over, and when it ... But when the threads involved are dependent on each other, as they are here, it makes little sense to make one thread higher priority than another, and for the reason you note: you really do need each of these threads to, at least on average, process the data at the same rate, otherwise you will eventually consume all your resources (memory in this case, though having the UI lag behind the actual processing is probably not desirable either). ...
    (microsoft.public.dotnet.framework)
  • Re: output.c error in multithreaded program
    ... >please see further below about a couple of semaphore questions). ... just modify your queue insertion routine to put the request in the ... scheduling priorities give you control over priority of how things are done). ... Why have an array of handles and an array of counts when the natural ...
    (microsoft.public.vc.mfc)
  • Re: So... What are the alternatives? Was: I dont use an RTOS because...
    ... This configuration parameter decides whether or not preemption is allowed. ... queue will be treated as though they have equal priority. ... The real-time clock serves two primary purposes in my O/S. ...
    (comp.arch.embedded)