[Staff] [Ideas] Primitive Multithreading

Here you can find side projects of the staff and great projects which we think should get extra support. (Note that featured projects are not projects by staff members of MaxCoderz)

Moderator: MaxCoderz Staff

User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

[Staff] [Ideas] Primitive Multithreading

Post by benryves »

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:
-> 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: Select all

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.
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

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
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Post by CoBB »

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
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

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.
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.
coelurus
Calc Wizard
Posts: 585
Joined: Sun 19 Dec, 2004 9:02 pm
Location: Sweden
Contact:

Post by coelurus »

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.
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

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
User avatar
qarnos
Maxcoderz Staff
Posts: 227
Joined: Thu 01 Dec, 2005 9:04 am
Location: Melbourne, Australia

Re: [Staff] [Ideas] Primitive Multithreading

Post by qarnos »

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.
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

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.
CompWiz
Calc King
Posts: 1950
Joined: Thu 13 Oct, 2005 1:54 pm
Location: UB

Post by CompWiz »

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
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

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.
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

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
User avatar
CDI
Maxcoderz Staff
Posts: 321
Joined: Tue 24 May, 2005 7:25 pm
Location: If I find out, you'll be first to know.
Contact:

Post by CDI »

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?
ImageImage
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

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?
User avatar
Jim e
Calc King
Posts: 2457
Joined: Sun 26 Dec, 2004 5:27 am
Location: SXIOPO = Infinite lives for both players
Contact:

Post by Jim e »

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
User avatar
KermMartian
Calc Wizard
Posts: 549
Joined: Tue 05 Jul, 2005 11:28 pm
Contact:

Post by KermMartian »

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
Post Reply