gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

C/C++ > Interrupt-Safe Data Structures

#174963 - shotgunninja - Tue Aug 10, 2010 5:43 pm

Hello, my name is Nick Iannone, and I've recently started working on an engine for the Nintendo DS, using libnds. I'm posting this here, because (1) it's more about C++ than anything else, and (2) because it applies to both GBA and NDS development.

I'm currently working on a set of basic, interrupt-safe nonblocking data structures for GBA/DS development. They are based loosely on the works of Timothy Harris, et al. of the University of Cambridge. The purpose and use of these data structures is to allow safe, nonblocking data structure access from both the main program and from interrupt service routines, without disturbing the natural flow of the program.

Since there is no atomic Compare-and-Store instruction on the ARM9 (that I know of), I use a Monitor-Object-like dummy-lock system which stores the future value of a property in the lock, does what it has to, then overwrites the property and clears the lock. If a method is called in the interrupt while the lock is active in the main program, it uses the states of the lock and the property to determine the stage of the method in the main program, and adjust the stored values as necessary.

Since all values are sampled and tested as conditions for the lock, there is a small risk that (if the interrupt occurs between the load and compare operations) this value will be invalid, but since this is interrupt-based, not thread-based, the operation will complete and unlock in the interrupt before this becomes an issue in the main program.

I have yet to do some testing on some situations, but I have completed initial coding of the Interrupt-Safe Stack, and I will post code for it shortly. Please let me know what you think, and if there is any way to improve upon this.

#174965 - keldon - Tue Aug 10, 2010 6:46 pm

A mutex system would be good, basic thread support and message passing would be pretty useful. Can't wait!

#175052 - shotgunninja - Fri Aug 27, 2010 2:52 pm

@keldon, I can't make the GBA/DS support threading if the hardware isn't designed for threads, and since the libnds software does a lot on its own already, making an arbitrary multithreading system would cause some issues with how the code runs with libnds. I'm just designing these to allow data structures to be used both inside and outside interrupt routines without data loss.

#175113 - Dirbaio - Thu Sep 09, 2010 6:40 pm

It IS possible to make threads on the NDS...
Commercial games use threads.

#175121 - Miked0801 - Fri Sep 10, 2010 3:35 pm

What does hardware support have to do with threads? A thread is a software construct, independant of the hardware.

#175123 - Dwedit - Fri Sep 10, 2010 3:55 pm

Without IRQs or timers, you can't do much threading, unless you have some kind of voluntary yield function.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."

#175124 - elwing - Fri Sep 10, 2010 5:05 pm

Dwedit wrote:
Without IRQs or timers, you can't do much threading, unless you have some kind of voluntary yield function.

yep, you need a bit of hardware to make a threading system, however the gba hardware as all the required thing to create a threading system, on most system there are no "magical" hardware part that provide thread. all the "task switching", time slice and priority ordonancer are implemented in software, it represent quite some overhead and memory space, it isn't really required when doing a game for a system like a gba...

and in most case for your game logic you can use some trick like protothread to implement time decoupled logic

#175176 - keldon - Tue Sep 21, 2010 12:47 pm

There are threading systems for the DMG, and I'm not even talking about an elaborate system with any time management system, just the initial ability to have threads that you can [somehow] switch between safely and have a method to pass a simple message to another thread.

You can then incorporate some basic thread mechanics into the message passing methods with some basic thread control methods - there's not even any need for time sharing here.

Sitting somewhere between single threaded and typical threading systems I'm sure it could be useful. And I'm 100% certain it can be done, but I'm only mentioning it in passing.