[Staff] [Ideas] Primitive Multithreading
Moderator: MaxCoderz Staff
- 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:
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?
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?
- KermMartian
- Calc Wizard
- Posts: 549
- Joined: Tue 05 Jul, 2005 11:28 pm
- Contact:
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
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.
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
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: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).
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 | /
+----------------+-'
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
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.
- Jim e
- Calc King
- Posts: 2457
- Joined: Sun 26 Dec, 2004 5:27 am
- Location: SXIOPO = Infinite lives for both players
- Contact:
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?
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?
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
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.
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.
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
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
Hmm, I recently had a class about primitive multithreading, and I was also pondering (as one does ) 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
*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
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
Re: [Staff] [Ideas] Primitive Multithreading
I hope it's not too late to resurrect this thread (and it's too late to stop me if it is ).
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:
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!
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 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
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
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.
avatar courtesy of driesguldolf.
Re: [Staff] [Ideas] Primitive Multithreading
That is awesome
I haven't been here for ages, but multithreading in z80 still triggers my attention
I haven't been here for ages, but multithreading in z80 still triggers my attention
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
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
Re: [Staff] [Ideas] Primitive Multithreading
Clever, though I can't help thinking it would be simpler to just disable interrupts during critical sections.
-
- Calc King
- Posts: 1513
- Joined: Sat 05 Aug, 2006 7:22 am
Re: [Staff] [Ideas] Primitive Multithreading
Well here's proof of that:
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)
Code: Select all
di
CS
ei
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)