I've looked at Garth's IRQ system and might be able to fold that in here somehow. I'm also not entirely convinced yet he was wrong about what he said regarding PETT IL implementing D. Wheeler's split stack idea vs. the more traditional plain old cells sliding up and down the zero page. I will eventually benchmark both approaches and report the results here. On to the situation at hand...

I have a need, for a game I'm writing on top of PETTIL, to animate several things on the display such that they appear to occur simultaneously. There's an easy enough way to intercept the Jiffy clock IRQ (every 1/60th of a second) and do whatever I want to do. The approach I'm considering is to have the IRQ run through a (sorted) "timeout" list (contains 3-byte expiration times corresponding to some future jiffy clock value at $8d-$8f), and when the jiffy clock is greater than the timeout value, a corresponding execution token gets added to the "triggered" list (a FIFO queue that contains only execution tokens). While each individual event is unlikely to clobber the next interrupt (by taking longer than a jiffy), several events triggered simultaneously just might.

The main loop will run through the event list of already triggered events and execute the first word on that list, discarding it. A simple FIFO queue. If there are no events, it will busy-wait on the next event.

it could look something like this:

in 5 seconds, the eyes close. 1/2 a second later, the eyes open.

Not sure what word to use for repeated-event ( every )? or if event is a good choice. Naming the words properly is 50% of the job, after all. I like Java's threading and synchronize stuff, and have done 6502 IRQ handlers in games before but not like this. What's a good design? What's good and bad about this design?

This is exactly what one of the parts of an article is about that I will soon be posting on my website (although the article will not be Forth-specific), about simple methods to effectively get multitasking without a multitasking OS. [Edit, 5/15/14: It's up, at http://wilsonminesco.com/multitask/index.html.] Here's a (very cropped) piece of it:

You could have a hardware timer that has a comparator that watches for a match and causes an interrupt; but what I've always done is to use the software real-time clock (which runs on interrupts from a 65c22 VIA's T1), adding a portion of code to do the comparison and act if there's a match. It adds very little execution time to the real-time clock ISR, for two reasons:

1. The alarms are sorted by chronological order, so the RTC ISR only has to watch for the first one in line. There is no need to check all the pending alarms for a match.
   
2. When checking for a match, the first byte (the low byte) will usually fail the test, so you jump out of the routine quickly without wasting much time.

Your alarm-management software can of course keep, install, delete, and sort (by due times) many alarms, and any given alarm's routine might also set an alarm for the next time it's supposed to run. It might be to collect new data every second, every minute, every fifteen minutes, or whatever. What I have set up has 0.010 second (10ms) resolution, meaning I could conceivably have as many as 100 alarms per second, up to something being scheduled out 2^32 centiseconds which is over 16 months out.

If there's a risk of having multiple alarms with the exact same time due time, a few possible ways to deal with it are:

• Have the real-time clock ISR check for more possibly due alarms after executing the first one.
  
• Have the real-time clock ISR watch for the next alarm being slightly past due, not just an exact match.
  
• For less runtime overhead, it might be better to have the alarm installation routine see if there's already an alarm with the same due time, and if so, increment the next one by a tick, or even more if there's any risk that a single tick won't give the last previous alarm time to finish executing first.

If there's no alarm pending, the RTC NMI ISR will usually take 8 [assembly-language] instructions, including the RTI. If there is at least one alarm pending, it will usually take three more. Comparison is done on the low byte first and high byte last to save time, since the high bytes are more likely to be the same. Where my set goes over 16 months, if my alarms are typically for the same day, the high byte will usually match, requiring more byte comparisons in order to see that we're not there yet; so that's not the place to start the comparison.

The alarm array might look something like:

Code:

ALM_LIST:     DFS  8*6         ; DFS ("DeFine Storage") in the C32 assembler makes a
ALM_cs_32:    EQU  ALM_LIST    ; variable space of that many bytes.  Here we're leaving
ALM_XEQ_ADR:  EQU  ALM_LIST+4  ; room for an 8-alarm queue, each having 4 bytes for the
                               ; cs-32-matching time and 2 for the alarm-execute address.
                               ; ALM_cs_32 and ALM_XEQ_ADR are for the first one in line.

In my 6502 Forth system, the alarms essentially activate a Forth ISR, which, as shown in the article on that subject, really has no overhead. As you might imagine, there are many ways to carry out alarm methods. You might have routines to:

• set an alarm with an absolute time
  
• another to set an alarm with a time relative to right now
  
• sort alarms by chronological order (which would be used by the two above) and leave the next-due one at the head of the queue
  
• delete an alarm, using its execute address to find the right one, and close up the gap in the alarm list
  
• delete the alarm at the head of the queue (used especially by that alarm when it executes)
  
• find out how long before the next alarm is due
  
• do conversions from H:MM:SS to centiseconds (or milliseconds, or whatever you use) and back

How complex you want to get is up to you of course. These are merely suggestions, based on what I have running in Forth (not assembly).

Certain things in your tasks may be inappropriate to time with alarms though. For example, if you have a key-scanning routine and it sees that you've pressed a key, and, for debouncing, it waits to see if it finds it pressed for 50ms in a row before submitting it to the other routines as a valid keypress, you don't set an alarm for 50ms later. The task needs to be run many times in that amount of time, making sure the key remains pressed for 50ms in a row, and it should re-start the count every time it sees the key up and then down again. There is no need to do this constant re-checking on any particular schedule though. There's little difference between getting to it every 100 microseconds versus every 2 milliseconds, while taking care of other tasks in between. That's one of countless senarios that are better taken care of with the cyclic executive method below. <truncated>

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

design bug: my approach needs to take into account that the jiffy clock resets to 0,0,0 at midnight

I actually have two sets of bytes, one for time of day (HMS) and calendar and one for ongoing centiseconds, to prevent having to convert back and forth so much. The alarms go by centiseconds, and their application means that the conversion is seldom needed. I could almost get rid of the HMS & calendar bytes and their incrementing because I use them so seldom. For the 32-bit centiseconds count though, you never need to reset it, and it doesn't matter when you have it cross through zero.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

By my calculation, it would take about 76 years of up-time for a 32-bit centi-second counter to wrap.

Mike

[Edit: Oops ... looks like I was off by a factor of 60! Thanks, Garth!]

100 centiseconds = 1 second
256 centiseconds (ie, the rate the second byte increments) = 2.56 seconds
65,536 centiseconds (ie, the rate the third byte increments) = 655.36 seconds, or a little under 11 minutes
16,777,216 centiseconds (ie, the rate the fourth byte increments) is about 46 hours, 36 minutes, 12 seconds
4,294,967,296 centiseconds (ie, the rate the fourth byte rolls over) is a little over 497 days, or 16½ months.

That's more than adequate for my applications, but 24 bits might not be.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

The uptime counter in POC has 40 bits. Of the five bytes, the least significant one increments at 10 millisecond intervals due to the 100 Hz jiffy IRQ that is generated by the watchdog timer in the real-time clock (RTC). When that byte hits 100 it is returned to zero and the next byte is incremented (seconds × 1). When the seconds × 1 byte wraps to zero, the next byte is incremented (seconds × 256), and so on. Therefore, the uptime counter is good for 49710 days (or 136 years), 6 hours, 28 minutes, 16.99 seconds.

The jiffy IRQ also drives a 24 bit down counter that is used to generate time delays, with the most significant 16 bits representing the time delay in seconds. I don't maintain the calendar date or time-of-day in software because I can get it from the RTC as needed. The RTC also has an alarm that can be set up to interrupt with various degrees of resolution, such as once per second, once per day, at specific times, etc.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

I'm working on this part now, a general-purpose interrupt handler to time all the different events in my game. I piggybacked it on top of the PET's 1/60th of a second "jiffy" interrupt. There are three unsorted lists. The "add" list is where things are queued up to be added to the "timer" list. The IRQ handler decrements each 8-bit timer-counter on the timer list, and when the countdown to zero is reached, the associated 16-bit CFA gets added to the third list, which I'm calling the "execute" list. The execute list is a FIFO queue with a foreground handler that runs each word (in the order it was added) and removes it.

So the IRQ handler has to:

• count down all the timers on the timer list
• remove any expired timers from the timer list and enqueue their associated CFAs to the "execute" list
  This is accomplished by replacing the expired entry with the last entry and decrementing the timer list size
• copy/remove each item from the "add" list to the timer list until a zero-length duration is reached indicating the end of the add list
• chain the PET's main interrupt handler at $E455

When queuing multiple events on the add list, just make sure to write the duration byte of the zeroth element at the very end. Putting something on the "add" list is equivalent to saying 'execute the Forth word at the specified CFA after `duration` jiffies

Be sure to see my article on simple multitasking methods. Rather than counting down all the timers on the timer list, let me recommend having just one timer variable (which could be multiple bytes if one byte does not give enough resolution), and let the ISR stop with just this one, not do a list of them. Keep the ISR as simple as you can. Having the one real-time clock works out fine if you work it like a room full of people all watching the same clock on the wall to time their individual tasks. None interfere with any of the others. All tasks should watch the same real-time clock counter bytes, and add the desired offsets to get the target times to watch for, and keep those target times in their own variables. When they're watching for the target time, they just take the current time on the clock and subtract the target time in the variable. If the answer is negative, you have not arrived at the target time yet, so just give control back so something else can run. The number of clock cycles spent on a task that doesn't need to do anything yet is very minimal.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

I read this page when I was doing the design, and in this circumstance I disagree with your recommendation.

Here's how i look at it -- On the PET/VIC/C=64, the mechanism is to hook the IRQ vector, do your own IRQ service thing, then chain the ROM IRQ handler. At 1mhz, there are 16,667 clocks in each 1/60th of a second. Some of these clocks are sensitive to IRQ (anything that reads or writes the timer list) and the rest of them (hopefully a vast majority) are not, and will be used for mainline processing. Within each jiffy, there have to be enough clocks to finish all IRQ service without clobbering the next one.

Some of the "work" being done by the game will take more than 1/60th of a second to complete. This is foreground code running during "the rest of the clocks" mentioned in the previous paragraph. My goal is to reduce code size, have a simple design, and reduce the combined total number of clocks required for the IRQ and mainline code. There should never be more than a dozen balls in the air at once, and decrementing and testing (BEQ) up to a dozen 8-bit timers during the IRQ servicing with a DEY loop is fast and simple. All SEI-sensitive code runs at the start of the jiffy. Something like (untested)Doing a lot of addition, subtraction, list searches/insertions/deletions would be more expensive, in toto, and would probably need to have IRQ disabled, which risks clobbering the next IRQ

Edit: On the 4.0 PET, the ROM IRQ processing routine takes up 641 to 729 cycles, determined by setting a breakpoint at the entry (PHA) and exit (RTI) instructions and subtracting cycle counts in VICE, which is approximately 3.85% of the available CPU time

You definitely know the PET/VIC/C64 better than I, and your game application too, so I defer to you there.

The best way will depend partly on how often the IRQ hits compared to how often, on average, you switch tasks. Your ISR apparently runs seldom enough that there would be no problem giving it more work to do. I'm used to tens of thousands of interrupts per second, while still leaving plenty of time for non-IRQ work to be done in between, and task switching at 10,000+ times per second (where tasks usually are waiting for a time or condition or event that has not arrived yet, so they give control back in only a few cycles, since there's nothing for them this time). (For 1MHz, translate that to 2,000 interrupts per second, and a minimum of 500 task switches per second.) Incrementing the one timer takes very few cycles. If all the ISR does is increment a timer variable, it could be as simple as:

or for three bytes,

Since no registers get clobbered, there's no need to save and restore them. The IRQ and RTS already save and restore the status. Some applications will need up to four bytes or even more for the timer variable, for intervals ranging from a fraction of a millisecond out to months or years. Some tasks may use only the lowest byte(s), while other ones use the middle two bytes, and slow-cycling ones use only the highest ones. Most tasks' needed intervals will be unrelated to the rollover rate of any given timer variable byte. Having several timer variables for the ISR to increment then requires also that the ISR pay attention to how many bytes in each set, or just run all of them with the maximum number of bytes even if some tasks don't need that many.

If a task is watching only a single byte, it won't ever read it wrong. But if it's watching two bytes and interrupts must not be disabled (because the ISR does other necessary stuff too), you would do something like (Forth equivalent):
since an interrupt could increment it between when you read the low byte and when you read the high byte. If you do it in assembly, you only need to compare one of the bytes. In most cases the loop will drop through on first try.

Even if each task had its own timer variable, reading such a multi-byte variable still requires the comparison, unless you disable interrupts while reading it.

Checking to see if it's time for a task to do something involves:
which exits the task if the time it's watching for has not come yet. If the target time itself is getting decremented, and again used more than one byte, you'd have something like:

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

FYI Jeelabs has a little article about multitasking with Mecrisp with a link to the Forth source code at http://jeelabs.org/article/1621b/ .

Blazin' Forth called it JIFFIES.

Wait n jiffies.

If you have multitasking, you could improve JIFFIES by placing PAUSE in the wait loop. The task switcher, not Blazin' Forth's PAUSE.

Another way to improve JIFFIES is to make it work more like DOWN-COUNTER from Tim Hendtlass' book "Real Time Forth".

I prefer cooperative multitasking, but I've got this idea I'd like to play with on how to have preemptive multitasking where all primitives are 'atomic'.
It involves building a kernel with support for Garth's zero overhead high level interrupts and making the high level interrupt call PAUSE. On the C64 the interrupt occurs sixty times a second so the timing should be about right for a few background tasks.

If task switching every 1/60th of a second is not often enough, PAUSE can still be included in I/O routines and in the loops of background tasks. Since PAUSE manipulates the stack pointers, including the return stack pointer, it is a code definition ( at least it should be ) . When multitasking is disabled, PAUSE is set to execute NOOP , a no-op. In Fleet Forth, both NOOP and (PAUSE) , the word that does the actual task switching, are code and therefore 'atomic' as far as high level interrupts are concerned.
NOOP is nothing more than a word with a code field that points to NEXT . It has no body.