MaxCoderz

for your 1 bit pleasure!

All times are UTC




Post new topic Reply to topic  [ 32 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
 Post subject:
PostPosted: Sun 06 Aug, 2006 2:05 am 
Offline
Maxcoderz Staff
User avatar

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


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sun 06 Aug, 2006 12:47 pm 
Offline
Calc Wizard
User avatar

Joined: Tue 05 Jul, 2005 11:28 pm
Posts: 549
Mmm, that's a good idea. 'Twould definitely help avoid conflicts between the threads.

_________________
Image Image Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Mon 07 Aug, 2006 10:01 am 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 3064
Location: Croydon, England
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.


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

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 3064
Location: Croydon, England
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:
+----------------+-.
|                |  \      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).


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 10 Aug, 2006 4:15 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Wed 15 Dec, 2004 7:26 pm
Posts: 2735
Location: The Hague, Netherlands
Hmmm... i'm to stupid to get that :P Could you explain in more detail :) :oops:

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 10 Aug, 2006 4:32 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 3064
Location: Croydon, England
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.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 10 Aug, 2006 4:45 pm 
Offline
Calc King
User avatar

Joined: Sun 26 Dec, 2004 5:27 am
Posts: 2457
Location: SXIOPO = Infinite lives for both players
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


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 10 Aug, 2006 4:54 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 3064
Location: Croydon, England
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.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Fri 11 Aug, 2006 1:52 pm 
Offline
Regular Member

Joined: Fri 17 Dec, 2004 1:47 pm
Posts: 130
Quote:
...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.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Mon 02 Oct, 2006 8:45 pm 
Offline
Calc King
User avatar

Joined: Sun 23 Jan, 2005 12:37 am
Posts: 1727
Location: Netherlands
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


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Thu 05 Apr, 2007 11:51 pm 
Offline
Calc King
User avatar

Joined: Sun 23 Jan, 2005 12:37 am
Posts: 1727
Location: Netherlands
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


Top
 Profile  
Reply with quote  
PostPosted: Wed 20 May, 2009 9:19 am 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 01 Dec, 2005 9:04 am
Posts: 227
Location: Melbourne, Australia
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:
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:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; 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.


Top
 Profile  
Reply with quote  
PostPosted: Wed 20 May, 2009 11:56 am 
Offline
Calc King
User avatar

Joined: Sun 23 Jan, 2005 12:37 am
Posts: 1727
Location: Netherlands
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


Top
 Profile  
Reply with quote  
PostPosted: Wed 20 May, 2009 6:49 pm 
Offline
Maxcoderz Staff
User avatar

Joined: Thu 16 Dec, 2004 10:06 pm
Posts: 3064
Location: Croydon, England
Clever, though I can't help thinking it would be simpler to just disable interrupts during critical sections. :)


Top
 Profile  
Reply with quote  
PostPosted: Fri 22 May, 2009 10:45 am 
Offline
Calc King

Joined: Sat 05 Aug, 2006 7:22 am
Posts: 1513
Well here's proof of that:
Code:
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)


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

All times are UTC


Who is online

Users browsing this forum: No registered users and 5 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