[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
tr1p1ea
Maxcoderz Staff
Posts: 4141
Joined: Thu 16 Dec, 2004 10:06 pm
Location: I cant seem to get out of this cryogenic chamber!
Contact:

Post by tr1p1ea »

I have thought about multi-threading on calc a little, but never considered putting it into practice. This is a cool achievement ben, even if it is just for the sake of it :).

Perhaps you could tie a small amount of information to each thread, outlining any saferam areas it uses and how much, whether or not it uses TIOS romcalls, stack usage etc?
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."
Image
Image
User avatar
KermMartian
Calc Wizard
Posts: 549
Joined: Tue 05 Jul, 2005 11:28 pm
Contact:

Post by KermMartian »

Mmm, that's a good idea. 'Twould definitely help avoid conflicts between the threads.
Image Image Image
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

I haven't had much time (work!) to work on this project any more, but have extended it to add any number of threads and allocate memory for the register store and stack (in the form of programs named Thrd<random four-digit number>). You can't currently clean up threads, but I'm thinking the best way to do this would be to push data/VAT address of the temporary file to the new stack, and then an address of a cleanup routine.
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

Hm, here's a better idea for storing variables between threads - use the index registers!

That way, the memory allocated for the thread would be set up like this:

Code: Select all

+----------------+-. 
|                |  \      16 bytes
| Register store |   > (PC, SP, AF, BC,
|                |  /   DE, HL, IX, IY)
+----------------+-:
| Variable space |  \ 
|                |   IX points to the start
| |Grows  down|  |   of the variable space.
: v           v  :
:                :
: ^           ^  :
| | Grows  up |  |   SP points to the end
|                |   of the stack space.
|  Stack space   |  / 
+----------------+-'
Better would be to offset IX by 128 bytes, so you could use the full -128..127 range, but it's less confusing for users if it points to the start (and they can move it if they so wish).
User avatar
kv83
Maxcoderz Staff
Posts: 2735
Joined: Wed 15 Dec, 2004 7:26 pm
Location: The Hague, Netherlands
Contact:

Post by kv83 »

Hmmm... i'm to stupid to get that :P Could you explain in more detail :) :oops:
Image
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

Once the new thread has been created, some memory is allocated (it needs to be, for that thread's stack). If I also preload the new thread's IX register (as each thread is swapped, the registers are also swapped - so each thread has its own set of registers) to point at the block of memory allocated for the stack, you can also use that memory to store variables, using ix and an offset to point to different variables. This way, each thread can also have its own local variables.
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 »

ewww...Lose a register?? Never! Well wait, I guess it wouldn't be totaly gone, just if you are using it in a isolated routine that only uses memory that locked in like Plotsscreen.

So I imagine it could work ok, but its adding a level of abstraction to something that wasn't greatly needed. For practicality sake couldn't threads just be expected to get along?
Image
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

You can do whatever you like with IX. :) Much like SP, PC and IY, I'm talking about the preloaded state of the registers. Before a thread is allowed to start, IY (so the TIOS routines don't break), PC and SP are all set up and copied to the register store area in the freshly allocated thread memory.

All I'm saying is that for simplicity, when a new thread starts it has IX pointing to an area of memory it can use to store variables. Yes, this means that you can't use this and expect to be able to modify IX (that's the "losing a register" part), but there are ways around that. You could also easily make a thread only let itself run once by making the first instruction a NOP, and to set it to RET when it's run. That way, successive threads terminate instantly. When the thread exits, it would then need to set the first instruction back to NOP again.
Kalimero
Regular Member
Posts: 130
Joined: Fri 17 Dec, 2004 1:47 pm

Post by Kalimero »

...an area of memory it can use to store variables...
That would be Thread Local Storage (TLS) (just to give the child a name) and using one of the index registers is the most logical way to implement it imo.
User avatar
Timendus
Calc King
Posts: 1729
Joined: Sun 23 Jan, 2005 12:37 am
Location: Netherlands
Contact:

Post by Timendus »

Impressive little demo, Ben. Amazing. I too have been thinking about this, but never saw a need for it and didn't really know where to start... Respect :)
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
User avatar
Timendus
Calc King
Posts: 1729
Joined: Sun 23 Jan, 2005 12:37 am
Location: Netherlands
Contact:

Post by Timendus »

Hmm, I recently had a class about primitive multithreading, and I was also pondering (as one does :mrgreen:) whether it wouldn't be much easier to start with threads that are nice to each other by issuing a SLEEP once in a while which gives a scheduler the chance to make the context switch if it sees fit to do so. I'd expect such a system to be more efficient in many situations (you could use busy waits like waiting for a keypress for something useful), and easier to extend to more than two threads... Also it shouldn't require fidling with the interrupts, which would make things faster and easier to work with, and you wouldn't have to worry about locking critical sections and whatnot...

*Envisions himself trying to debug lock errors in assembly
*Screams and slaps himself back into reality

That's the one thing I'm extremely happy to have been able to avoid in my experiments with calculator networking ;)
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
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 hope it's not too late to resurrect this thread (and it's too late to stop me if it is :mrgreen:).

I just had a thought today about implementing mutual exclusions (mutexes) in Z80 code. Mutexes are usually implemented using an atomic test-and-set instruction, which the Z80 lacks, but we can do an implicit test-and-set using SMC.

The idea is to create the mutex using an instruction that overwrites itself with something else. Obviously, the original instruction will be an LD, and we want to replace it with something useful. The caveat is that the new instruction must only be one byte, since we need to do this in one instruction. We could use two-bytes if you use an immediate address (like ld (xxxx), hl), but then the mutexes must be hard-coded.

The (or A) solution is to use a RET instruction ($c9). A mutex then consists of 4 bytes:

Code: Select all

mutex:
        ld      (hl), $c9   ; overwrite self with "ret" insn.
        scf
        ret
The caller of the mutex loads HL with the mutex address and resets the carry flag before calling. If the carry flag is set on return, the mutex has been acquired.

I've written 3 high-level routines (acquire_mutex, timeout_mutex and release_mutex) to manipulate the mutexes. They seem to work fine in PTI, though I haven't had a chance to test them in multi-threaded code, since I don't have any!


Code: Select all

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; acquire_mutex:
;;
;;  This routine will block until the mutex is acquired.
;;
;; INPUTS:
;;
;;  REGISTERS
;;
;;  * HL    - address of mutex to acquire.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
acquire_mutex:
        or      a
        call    $ + $0006               ; indirect call to hl (see below)
        jr      nc, acquire_mutex
        ret
        jp      (hl)
        

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; timeout_mutex:
;;
;;  This routine will block until the mutex is acquired or the timeout
;;  period elapses.
;;
;; INPUTS:
;;
;;  REGISTERS
;;
;;  * A     - timeout value (0 == 256).
;;  * HL    - address of mutex to acquire.
;;
;; OUTPUTS:
;;
;;  REGISTERS
;;
;;  * F     - carry flag set if mutex was acquired.
;;          - carry flag clear if timeout elapsed.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
timeout_mutex:
        or      a
        call    $ + $0008           ; indirect call to hl (see below)
        ret     c
        dec     a
        jr      nz, timeout_mutex
        ret
        jp      (hl)
        

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; release_mutex:
;;
;;  Releases an acquired mutex.
;;
;; INPUTS:
;;
;;  REGISTERS
;;
;;  * HL    - address of mutex to release.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
release_mutex:
        ld      (hl), $36   ; overwrite mutex with LD (hl), $c9
        ret
I guess you could also write an init_mutex routine to create mutexes on-the-fly. Just load the target address with the byte sequence: $36, $c9, $37, $c9.

Another variation (which I trialled before settling on this) is to use immediate addressing as described above to write a two-byte instruction. $fe18 would give you a nice succinct infinite loop (JR pc-2), but makes implementing timeouts somewhat impossible. On the other hand, it would allow the scheduler to check for blocked threads (just check for $fe18 and the PC before executing the thread) and not waste run-time on them.
"I don't know why a refrigerator is now involved, but put that aside for now". - Jim e on unitedti.org

avatar courtesy of driesguldolf.
User avatar
Timendus
Calc King
Posts: 1729
Joined: Sun 23 Jan, 2005 12:37 am
Location: Netherlands
Contact:

Re: [Staff] [Ideas] Primitive Multithreading

Post by Timendus »

That is awesome :)
I haven't been here for ages, but multithreading in z80 still triggers my attention :mrgreen:
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Re: [Staff] [Ideas] Primitive Multithreading

Post by benryves »

Clever, though I can't help thinking it would be simpler to just disable interrupts during critical sections. :)
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: [Staff] [Ideas] Primitive Multithreading

Post by King Harold »

Well here's proof of that:

Code: Select all

di
CS
ei
And that's it.

But it has a nasty downside compared to many other ways of implementing critical sections, you would disable all threads - also threads that have nothing to do with it and aren't even trying to enter a critical section at all (or a different section)
Post Reply