4dsdev
Views: 614,161 Main | Rules/FAQ | Memberlist | Active users | Last posts | Calendar | Stats | Online users | Search 11-24-17 09:46 AM
Guest:

0 users reading blargSNES: event scheduler design | 1 bot

Main - Homebrew projects - blargSNES: event scheduler design New reply


StapleButter
Posted on 11-09-15 12:49 PM (rev. 2 of 11-09-15 12:59 PM) Link | #694
at some point we'll need a proper event scheduler for it, it's a mess right now


* event timestamps: cycles from previous event

* CPU execution: take next event's timestamp, run instructions for that amount of cycles
* just skip straight to the event if: 1) WAI opcode 2) speedhacking around an IRQ wait loop 3) DMA transfer

* insert event: knowing the amount of cycles to wait
-- for each stored event, if the stored event's timestamp is greater, move further into the queue
-- if the stored event's timestamp is less or equal, store event there
-- linked list structure?
-- give event a unique ID (or just use a pointer to it?)
-- fix timestamp for event right after it

* remove event (if for example a IRQ was enabled then disabled before firing):
-- find event with matching uniqueID/pointer, remove
-- yep, double-linked list would definitely be a bonus there
-- fix timestamp for event right after it




can be subject to changes

____________________
blargSNES -- SNES emu for 3DS
More cool stuff

profi200
Posted on 11-09-15 12:53 PM Link | #695
You might want to use light locks or maybe the coming light events. That's a lot better than using sys calls every time.

StapleButter
Posted on 11-09-15 01:00 PM Link | #696
I'm referring to events in SNES emulation, not the 3DS ones.


The light events could be interesting for things like the DSP sync though.

____________________
blargSNES -- SNES emu for 3DS
More cool stuff

plutoo
Posted on 11-09-15 01:05 PM (rev. 2 of 11-09-15 01:12 PM) Link | #697
I'd just use a priority queue (or a sorted singly linked list), and I would never ever "remove" events. In the case of an irq that gets disabled, I would simply check whether the irq is enabled or not when "popping" that event (and ignore it if it has been disabled).

When any event is added to the front of the queue, I'd interrupt the CPU execution, and recalculate the number of cycles left before next event occurs.

This is the simplest and cleanest way of doing things.

Edit: I should elaborate why removing an event is a really bad idea. What would happen if the program disabled interrupts, then enables them again? Then that event would be removed, and never added again.

Also for the timestamp you'd want an absolute value. This way, you don't need to loop and update all events each time you handle them. Of course you will need to handle integer overflow, but that's no problem since the list is ordered.

StapleButter
Posted on 11-09-15 02:57 PM Link | #698
The issue in this case is that the SNES supports an IRQ that can be programmed to fire at any screen position. Not only can it be disabled before firing, but it could also be changed to occur later or earlier.


The idea for timestamps would be that an event's timestamps is how many cycles away it is from the event before it. Each event would be relative to the one before itself, which would minimize overhead in updating (only one event to update really) and completely avoid integer overflow.

____________________
blargSNES -- SNES emu for 3DS
More cool stuff

coto
Posted on 11-09-15 04:39 PM Link | #699
About the IRQ that may trigger an event after set, and then would be unset right before the IRQ cycle count IRQ says it would be triggered:

spinlock_sched() runs on any hardware IRQ (for example vblank) handler. (or at least in a process that runs separately from the cycle counter thread)

process_id = you assign one up to 10 or any other number
u8 status = 0/1 (enabled/disabled)
callback = (u32)&handler pointer
spinlock_createproc(u8 process_id,u8 status,u32cback_ptr new_callback) //allocate a process

spinlock_modifyproc and spinlock_deleteproc should speak for themselves

-

//if set to 0 it will run the handler registered / 1 it wont
spinlock_perm(u8 process_id,u8 status)


-

SPINLOCK.H
http://pastebin.com/Hzg5FAuf

SPINLOCK.C
http://pastebin.com/Jqeam9kX

Very basic I know, but it really works.

For example if you want to run process #0 registered Only on scanline # 100 and #110
currentscanline_thread(){

if((scanline == 110) || (scanline == 100)){
spinlock_perm(0,0);
}

}

//then later on scanline end
nextscanline_thread(){
spinlock_perm(0,1);
scanline++;
}

yuriks
Posted on 11-26-15 09:09 PM Link | #777
I'd do this with a simple sorted array. Your number of outstanding events at any given time is likely to be a small number. Simply give each event entry an auto-incrementing unique id, and insert it into the array mantaining a sorted order. For removing events iterate until you find a matching id.

Since the number of events is small, a linked list or other more complex structure will probably not give you any significant advantage (and could even be slower with a naive implementation.)

To optimize for the common case, you could sort the array in reverse order, so that popping the next event just requires decrementing the size. Another option is to use a circular array instead, though the implementation there is slightly more complicated.

gudenau
Posted on 11-26-15 09:10 PM Link | #778
Posted by yuriks
I'd do this with a simple sorted array. Your number of outstanding events at any given time is likely to be a small number. Simply give each event entry an auto-incrementing unique id, and insert it into the array mantaining a sorted order. For removing events iterate until you find a matching id.

Since the number of events is small, a linked list or other more complex structure will probably not give you any significant advantage (and could even be slower with a naive implementation.)

To optimize for the common case, you could sort the array in reverse order, so that popping the next event just requires decrementing the size. Another option is to use a circular array instead, though the implementation there is slightly more complicated.

You might be able to abuse memory mapping to make a ring buffer; that could be fun.

yuriks
Posted on 11-26-15 09:11 PM Link | #779
That's not particularly helpful here, since it's only useful if you need to have a pointer to a window in the buffer that appears contiguous, which isn't the case here.

plutoo
Posted on 11-26-15 09:19 PM Link | #780
I kinda agree, if you can live with a hard limit on the number of events then a circular array would be optimal. But removals in the "middle" of the array can be painful to implement. :P

gudenau
Posted on 11-28-15 11:05 PM Link | #793
Posted by plutoo
I kinda agree, if you can live with a hard limit on the number of events then a circular array would be optimal. But removals in the "middle" of the array can be painful to implement. :P

Check for nulls and skip them, keep the holes in mind while updating the pointer? Given an array that is a little oversized and smart coding, that should not be to big of a preformance hit.


Main - Homebrew projects - blargSNES: event scheduler design New reply

Page rendered in 0.018 seconds. (2048KB of memory used)
MySQL - queries: 28, rows: 85/85, time: 0.012 seconds.
[powered by Acmlm] Acmlmboard 2.064 (2017-11-20)
© 2005-2008 Acmlm, Xkeeper, blackhole89 et al.