MaxCoderz

for your 1 bit pleasure!

All times are UTC




Post new topic Reply to topic  [ 32 posts ]  Go to page 1, 2, 3  Next
Author Message
PostPosted: Thu 03 Aug, 2006 10:02 am 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 3064
Location: Croydon, England
I'm not really clued up on the way these new-fangled modern operating systems handle running multiple threads, so I apologise in advance if this isn't really proper multithreading.

Basically, I was pondering (as one does) whether it would be possible to run any number of threads on the TI-83 Plus. I daresay others have done this in the past, but not having access to the internet at the time to check I thought I'd do my own bit of experimentation.

The way I can see this working is to give each thread a small amount of time to run in (time slice). At the end of one thread running, I would save the calculator's state away, and load the state for the next thread. I would keep on swapping threads several times a second, giving each their own bit of time and preserving their state.

What I really needed to know was what needed to be preserved between executions. Really, there isn't a lot - just the registers. PC and SP clearly need to be preserved, so that when a thread is resumed it resumes running at the point it was left at. Keeping the other general-purpose registers (AF, BC, DE, HL, IX, IY) safe would be important as well.

Naturally, I'll need to also preserve the stack. Or rather, for each thread, I'll need to allocate some memory for a stack and point the new thread's SP register at the end of that new memory. To keep things simple, I'll just point my test thread's SP at $FFFF-200, as the TI is arranged to have 400 bytes of stack RAM, growing backwards from $FFFF.

To perform the swapping, I'll use a custom interrupt (run in IM 2). The timer hardware will trigger this interrupt many times a second, so it is ideal. At the end of my custom interrupt, I'll jump into the default handler provided by the TIOS so the TIOS functions that rely on it behave correctly.

The way I see it working is like this:

Quote:
-> Enter interrupt handler.

Pop value off stack. This will be the program counter of the last running thread. (->A)
Save current stack pointer. (->B)

Set stack pointer to area in RAM where I can preserve registers for this thread. (<-C)

Push IY, IX, HL, DE, BC, AF to the stack.
Push old stack pointer (<-B) to stack.
Push old program counter (<-A) to stack.

Find the address of the RAM where we have stored the registers for the next thread.
Load it into the stack pointer.

Pop value off stack, store it (will be PC) (->D)
Pop value off stack, store it (will be SP) (->E)

Pop AF, BC, DE, HL, IX, IY off stack.

Save current stack pointer (end of RAM area used to store registers for new thread) as address of last thread for next interrupt. (->C).

Load value into SP (<-E)
Push new thead's PC to stack (<-D)

Jump into TIOS interrupt handler ->


Effectively, all this does is take the pointer stored when the current thread was resumed, dump all the registers into the memory it points to, hunts the next thread, reloads the registers and saves the pointer for next interrupt.

Does it work?

Image

The above screenshot doesn't look too impressive, I'll give you that. There are only two threads running. The secondary thread is drawing all those random dots on the LCD. The other thread (which is the main program thread) just contains "bcall(_getkey)" - hence the 2nd/Alpha icons appearing,

I'll make the primary thread do something a bit more exotic - display random characters on the left side of the screen, the secondary work on the right side of the screen:

Image

The code for this is simply:

Code:
Main
   .include "Multithread/Multithread.asm"


   ; Kick things into action.
   call Multithread.Init
   
   ; For the moment, the secondary thread is hard-coded, and
   ; the 'multithreading' code ONLY switches back and forth between
   ; two hard-coded thread slots.
-

   halt ; Slow things down a bit here.

   ld b,8
   call ionRandom
   ld (curCol),a

   ld b,8
   call ionRandom
   ld (curRow),a

   ld b,0
   call ionRandom
   bcall(_PutMap)
   bcall(_getCSC)
   cp skClear
   jr nz,{-}
   
   call Multithread.End
   ret
   
; ---------------------------------------------------------
   
SecondaryThread
   
   di ; Don't want any other thread writing to the LCD!
         
   ld b,64
   call ionRandom
   add a,$80
   push af ; Save for later...
      out ($10),a
      
      ld b,48
      call ionRandom
      add a,48
      ld b,a
      srl a
      srl a
      srl a
      add a,$20
      out ($10),a
   
      ld a,b
      and 7
      ld c,%10000000
      jr z,{+}
      ld b,a
   -   srl c
      djnz {-}
   +
   
      in a,($11)
      call LcdBusy
      in a,($11)
      xor c
      ld c,a

      call LcdBusy

   pop af
   out ($10),a

   call LcdBusy
   ld a,c
   out ($11),a         
      
   ei
   
   jr SecondaryThread
   
LcdBusy
   push af
   inc hl
   dec hl
   pop af
   ret



As you can see, there are two discrete threads running there.

Well, that's two threads up and running. What's needed to extend this to any number of threads?
  • Thread management. Basically, the ability to add/remove threads at will, and have the handler be able to switch between as many threads as required.
  • Allocation of new stack space. New threads will need more stack space, so I shall need to add some mechanism to steadily allocate it.
  • Idle threads. One big problem is that as you add threads, each one gets progressively slower. If threads flag themselves as idle, they can be skipped so threads that do need CPU time get it. The easiest way to do this is to set a "sleep" counter which is checked when threads are switched around - if it's zero (when it runs out), the thread is given some time to run.

Off the top of my head, that's about it. There are some issues I have come across when working with this:
  • TIOS routines are not thread-safe. This speaks for itself, pretty much - if you have two threads, both of which are calling bcall(_putC) to display a character, they interfere with eachother (for example - incorrectly setting the value of curCol or curRow as one thread changes it as the other one is reading it) which causes crashes.
  • Variables can become an issue. Same reason as above - if two threads call a function which uses a set RAM location for a local variable, the variable can be changed half way through.


One possible way to get around thread-unsafety of functions is to disable interrupts before calling them and reenabling them afterwards, which prevents the thread switcher from swapping them. It's a pretty lousy workaround, though. ;)

Anyway, I don't know what you chaps think, but it seemed an interesting experiment. I'll see what I can do with regards to handling custom number of threads, then release the routines.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 10:12 am 
Offline
Maxcoderz Staff
User avatar

Joined: Wed 15 Dec, 2004 7:26 pm
Posts: 2735
Location: The Hague, Netherlands
Uhm. Maybe I oversee something, but wouldn't multiple threats destroy each other's data in the saferams? A true multithreading should also take care of that... shouldn't it? Which means it needs to manage the memory aswell.

Anyhow, it's really nice experiment, and I wonder how far you'll get. Any idea's for concrete use of this experiment? Or is just playing around?

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 10:22 am 
Offline
MCF Legend

Joined: Mon 20 Dec, 2004 8:45 am
Posts: 1601
Location: Budapest, Absurdistan
Threads operate on the same data. You're probably thinking of processes.

I've seen multithreading stuff at ticalc, but I don't know how mature it is:

http://www.ticalc.org/archives/files/fi ... 32995.html

_________________
The Independent Z80 Assembly Guide
Acelgoyobis
PindurTI


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 10:26 am 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 3064
Location: Croydon, England
kv83 wrote:
Uhm. Maybe I oversee something, but wouldn't multiple threats destroy each other's data in the saferams?
Yes, I mentioned it as a potential problem.
When someone creates a new thread, I'm thinking the best way to do this is to ask for a pointer to the entry point of the thread (something I can preload the stored PC with) and a size. It will then have to allocate the requested amount of memory and pass a pointer to that memory to the new thread, so the thread can store variables in it. This area of memory will also be used as the thread's stack storage.

Quote:
Anyhow, it's really nice experiment, and I wonder how far you'll get. Any idea's for concrete use of this experiment? Or is just playing around?
Mainly just playing around. :) I can see it might be useful for game AI, though.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 11:46 am 
Offline
Calc Wizard

Joined: Sun 19 Dec, 2004 9:02 pm
Posts: 585
Location: Sweden
Fun, but I don't see any _really_ practical applications. If you need concurrent programming on a calc, you probably should reconsider the program design :) Just think of all the overhead when switching threads.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 11:58 am 
Offline
Calc King
User avatar

Joined: Sun 26 Dec, 2004 5:27 am
Posts: 2457
Location: SXIOPO = Infinite lives for both players
coelurus wrote:
Fun, but I don't see any _really_ practical applications. If you need concurrent programming on a calc, you probably should reconsider the program design :) Just think of all the overhead when switching threads.
Yeah, i know. I always wanted to do multithreading especially for a graphics thread. But really i always found a simpler and better solution, but its just not as fun. :cry:

@ben: Planning on including thread priority if you do the manager?

_________________
Image


Top
 Profile  
Reply with quote  
PostPosted: Thu 03 Aug, 2006 11:58 am 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 01 Dec, 2005 9:04 am
Posts: 227
Location: Melbourne, Australia
I've often thought about this. It seems to me to be more of a "because we can" thing than something which would be overly useful, but it sure would be fun to write!

benryves wrote:
TIOS routines are not thread-safe. This speaks for itself, pretty much - if you have two threads, both of which are calling bcall(_putC) to display a character, they interfere with eachother (for example - incorrectly setting the value of curCol or curRow as one thread changes it as the other one is reading it) which causes crashes.


One possible solution, if you want to get tricky, would be to check if the thread address you popped off the stack is inside a TI-OS routine, and if it is, return control to the thread.

Obviously this could cause a delay in thread switching if the program calls _GetKey or something similar, or if you just get unlucky and keep catching the thread in a TI-OS routine by chance.

There's not much which can be done about the first one, but (getting even more tricky!) with the second one, you could swap the return address of the TI-OS routine with your own handler so you get control as soon as the routine completes. Of course, it could still be inside TI-OS code due to nested calls, so you would have to repeat the process until you're back in program RAM.

With regards to "sleep" mode, I'm not sure I fully understood. You are planning of giving sleeping threads some time, aren't you? Otherwise they can't clear the sleep flag. I think you were but I wasn't sure.

You could also implement critical sections - so threads don't get disturbed when running thead-unsafe code (although there would be a lot of them!).

EDIT: Oops! That'll teach me for not reading properly. DI is a nice easy way of doing it! :D

And there is also the option of co-operative multitasking (think Windows 3.x), where a "thread" will call a yeild routine occasionally when it is safe to do so. That would be by far the easiest approach on the calcs.

Modern CPUs are designed for multi-threading with lots of handy stuff we can only wish for on the Z80.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 3:31 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 3064
Location: Croydon, England
As you can probably tell, this isn't an especially serious project - mainly just "doing it because we can". ;)

I'm not really sure how I'd manage a priority system. The simplest way that I can think of would be to give each thread a priority counter, and when that thread is running that counter is decremented. The next thread is not switched to until that counter runs out - so a thread with a 10 priority will be left running for the duration of 10 interrupts, whereas a thread with a 1 priority would only run for a single interrupt.

(When I say they run for x interrupts, one "interrupt" refers to the thread switcher running once, and one potential switch to the next thread).

The idea of sleeping threads is that they can, for example, ask to sleep for 100ms in their main loop. This means that when the thread switcher goes to try to swap them back in, if their sleep timer is still waiting that thread is skipped over. The thread switcher (in the interrupt) would have to manage decrementing these timers itself.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 5:23 pm 
Offline
Calc King

Joined: Thu 13 Oct, 2005 1:54 pm
Posts: 1950
Location: UB
I think I saw a program on Ticalc.org a while ago that does multitasking. It displays a large grey pi symbol in the background while allowing you to do normal homescreen math stuff. It looked pretty good, I think. It has been a while since I used it though.

_________________
In Memory of the Maxcoderz Trophy Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 5:26 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 3064
Location: Croydon, England
I wrote that ;)
It doesn't properly handle threads, it just draws a pi symbol in a custom interrupt handler that's left loaded.
I asked for it to be removed from ticalc.org as it had a habit of writing over RAM that the OS used, causing crashes.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 5:27 pm 
Offline
Calc King
User avatar

Joined: Sun 26 Dec, 2004 5:27 am
Posts: 2457
Location: SXIOPO = Infinite lives for both players
Well, in the case of priority. You could add up all the priority numbers given, use that to divide the number of switches to occur in a unit of time(incase 1 second is to long). Then multiply that by every Priority number. The final vaule woud be used as a count down vaule. Oh and ofcouse make sure to handle zero.

ohhh...You could also toss in hardware only tasks. ON, link, and all that SE funness.

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 5:27 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Tue 24 May, 2005 7:25 pm
Posts: 317
Location: If I find out, you'll be first to know.
This is a very neat idea, maybe you could bar it down to say 4 or 5 threads. And in order to keep the registers from clearing (and any other vars you may have) into an appvar? Or would that kill the speed?

_________________
Image
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 5:56 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 3064
Location: Croydon, England
The registers for each thread (well, PC, SP, AF, BC, DE, HL, IX and IY) are already backed up. The problem is more stack space for new threads, as that's variable.

As for where to store that, I was thinking of making the "new thread" function take two arguments - thread start (to preload the PC) and stack size. A new program (or, as you said, AppVar) would be created for the thread and the SP set to point to the end of it, and it could use that stack space for, well, anything it chose (calling subroutines or storing local variables - whatever you felt like).

@Jim E: I see (sort of). It seems that that would add a lot of overhead, though?

As for hardware-only tasks, what do you mean by those?


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 03 Aug, 2006 6:55 pm 
Offline
Calc King
User avatar

Joined: Sun 26 Dec, 2004 5:27 am
Posts: 2457
Location: SXIOPO = Infinite lives for both players
Not much, unless you count a call to set a new prioty level overhead. Once everything is in place. The actual interrupt would only decrease a priority count every interrupt, if its zero switch to next thread and start over with that threads info. The benefit there is that you wouldn't be forced to switch tasks every interrupt.

By hardware only I meant tasks that are triggered by specific hardware interrupts. ON button and link come to mind. Basically I suggested you expand to an all out interrupt package.

hehe...run grey in the of the threads, I bet it won't look bad.

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat 05 Aug, 2006 10:45 pm 
Offline
Calc Wizard
User avatar

Joined: Tue 05 Jul, 2005 11:28 pm
Posts: 549
Yeah, I've been thinking of adding a system like this to Doors CS 7.0, just for kicks, when I get around to releasing 6 and finishing up some other stuff like SourceCoder. I'd probably allocate areas of userram in a custom appvar for use by the threads.

_________________
Image Image Image


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 32 posts ]  Go to page 1, 2, 3  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB ® Forum Software © phpBB Group | DVGFX2 by: Matt