6502.org Forum  Projects  Code  Documents  Tools  Forum
It is currently Sat Nov 16, 2024 11:37 pm

All times are UTC




Post new topic Reply to topic  [ 22 posts ]  Go to page Previous  1, 2
Author Message
PostPosted: Sat Mar 24, 2018 1:16 am 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8493
Location: Midwestern USA
Alarm Siren wrote:
Specifically, I want to ensure that TSB is always atomic, because I intend to use it as the basic operation for locking semaphores in software, see this page for explanation. This method only works if TSB is guarenteed to be atomic.

TSB and TRB are atomic if correctly used. Also, the 65C02 does tell you when atomic access to RAM is needed during a R-M-W instruction. Your glue logic should be able to handle that.

That said, I surmise your problem has nothing to do with the atomicity of R-M-W instructions and everything to do with proper task-switching timing. Task-switching timing is going to take careful analysis and programming—for example, if a task is about to set a semaphore you have to inhibit task switching for the duration of the operation so conflict doesn't arise. You'd also need to account for what could happen if the semaphore was already being manipulated when your task tries to manipulate it. That can get tricky and result in deadlock if not carefully handled.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Top
 Profile  
Reply with quote  
PostPosted: Sat Mar 24, 2018 1:35 am 
Offline
User avatar

Joined: Tue Oct 25, 2016 8:56 pm
Posts: 362
BigDumbDinosaur wrote:
the 65C02 does tell you when atomic access to RAM is needed during a R-M-W instruction. Your glue logic should be able to handle that.
Yes, via the ML pin, and the glue logic that relates to that is what I'm trying to figure out.

BigDumbDinosaur wrote:
That said, I surmise your problem has nothing to do with the atomicity of R-M-W instructions and everything to do with proper task-switching timing. Task-switching timing is going to take careful analysis and programming—for example, if a task is about to set a semaphore you have to inhibit task switching for the duration of the operation so conflict doesn't arise. You'd also need to account for what could happen if the semaphore was already being manipulated when your task tries to manipulate it. That can get tricky and result in deadlock if not carefully handled.


I... don't really see how. There isn't any task-switching. There are two separate processors that have access to a shared RAM, but each processors is single-threaded and running constantly, so there's no task-switcing per se. Just two tasks running in parallel. The beautiful thing about Test-and-Set as a semaphore primitive is that, provided the instruction itself is atomic, it guarentees mutual exclusion for two competing processes.

CPU A and CPU B both execute on the same semaphore memory location; CPU A arbitrarily gets in a fraction sooner and the bus arbiter holds CPU B. CPU A reads a zero, so Z is set, then it writes back a '1', all within one atomic instruction. It has acquired the lock and can proceed on its merry way. Now, CPU B is released by the bus arbiter. It reads the '1' left behind by the previous instruction, so Z=false. It also writes a '1', but that's not a problem because that's what it was already. The TSB instruction is followed by a BNE spinlock, so it just keeps looping back and trying to do that TSB over and over until CPU A clears the byte, so it reads a zero, acquires the lock, etc.

The key thing is that only works if TSB is guarenteed to be atomic, i.e. that CPU B won't be able to read a '0' out of the semaphore before CPU A has had a chance to change it to a '1'. Therefore to make this scheme work, I need to use ML to guarentee the atomicity of TSB (and by extension all R-M-W instructions). I guess what I'm getting at is I'm fully aware that higher level software will require semaphores to synchronise access to shared RAM. My intended solution is the Test-and-Set, which requires the TSB instruction itself be guarenteed atomic, so I need to make it atomic at the hardware level - software semaphores won't work because bus arbitration happens on a cycle-by-cycle basis, not instruction-by-instruction, so there's no way for the software to "know" in time.

Code:
    db      semaphore
spinlock:
    LDA     #1
    TSB     semaphore       ; Acquire lock if available
    BNE     spinlock        ; If not, keep trying
    ; do some work on the shared resource
    STZ     semaphore       ; Clear the lock


Incidentally, perhaps a moderator would be kind enough to split this topic? It has now significantly diverged and the topic title is therefore misleading.

_________________
Want to design a PCB for your project? I strongly recommend KiCad. Its free, its multiplatform, and its easy to learn!
Also, I maintain KiCad libraries of Retro Computing and Arduino components you might find useful.


Top
 Profile  
Reply with quote  
PostPosted: Sat Mar 24, 2018 2:27 am 
Offline
User avatar

Joined: Tue Oct 25, 2016 8:56 pm
Posts: 362
How about this circuit?

Note that the two controlled buffers are not "part of the circuit", they're just there because logisim cannot directly emulate open-drain pins. Also note that Busy to X input and ML inputs are inverted (that is, active HIGH) on this diagram; hence that inverter is also not a part of the circuit.

Anyway, what happens is normally ~BUSY is passed to RDY unchanged. ~BUSY is normally asserted by the bus arbiter if both processors try to access the same RAM location at the same time. However, if ~BUSY and ~ML are asserted simultaniously, then that gets saved into the D Flip Flop, causing RDY to continue to be held low - even though ~BUSY would normally be released during PHI2 low because of the way the bus arbiter works. RDY will not be released until ~ML is released, which based on the infamous Table 5-7 in the 65C816 datasheet, should not happen until the part of the R-M-W instruction that needs to remain atomic has completed.

Thoughts?


Attachments:
Schematic v2.png
Schematic v2.png [ 10.05 KiB | Viewed 3270 times ]

_________________
Want to design a PCB for your project? I strongly recommend KiCad. Its free, its multiplatform, and its easy to learn!
Also, I maintain KiCad libraries of Retro Computing and Arduino components you might find useful.
Top
 Profile  
Reply with quote  
PostPosted: Sat Mar 24, 2018 2:59 am 
Offline
User avatar

Joined: Tue Oct 25, 2016 8:56 pm
Posts: 362
Here's the same circuit again, but with the signals active low as they are in the real deal, and annotated to show how it might be built out of actual glue logic.


Attachments:
Schematic v3.png
Schematic v3.png [ 13.89 KiB | Viewed 3262 times ]

_________________
Want to design a PCB for your project? I strongly recommend KiCad. Its free, its multiplatform, and its easy to learn!
Also, I maintain KiCad libraries of Retro Computing and Arduino components you might find useful.
Top
 Profile  
Reply with quote  
PostPosted: Fri Mar 30, 2018 12:46 am 
Offline
User avatar

Joined: Wed Mar 01, 2017 8:54 pm
Posts: 660
Location: North-Germany
If you TSB an individual bit (1 for up to 8 CPUs) and then CMP that semaphore byte it should work. If the CMP doesn't match some other CPU did the same, so you should TRB then wait a while (ideally this delay should vary) and then retry.

Somehow a similar strategy was chosen when ethernet busses where really busses (not switched point to point connections). When the bus seems free they issued their packet, detect the collision and retry with individual delays. It worked :)

Of course, your HW solution is faster.


my 1/2 cent


Top
 Profile  
Reply with quote  
PostPosted: Fri Mar 30, 2018 5:51 am 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8493
Location: Midwestern USA
GaBuZoMeu wrote:
Somehow a similar strategy was chosen when ethernet busses where really busses (not switched point to point connections). When the bus seems free they issued their packet, detect the collision and retry with individual delays. It worked :)

UTP networks using hubs experience frequent collisions and hence require the random delay. It's still part of the Ethernet specification, although in practice collisions are not likely to occur on modern switched networks.

I recall a client (a busy insurance office) using a 3Com hub that had a collision detection indicator on it. That indicator was on most of the time. I finally convinced him to invest in an Ethernet switch, at a time when a switch was a costly piece of hardware. He was skeptical that the investment was worth it but quickly changed his tune when he saw a significant performance increase on his network.

Back in the days when I wrote software for the Xetec Lt. Kernal hard drive subsystem I used the random delay technique to arbitrate file and record locking. I got the idea from Ethernet.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Top
 Profile  
Reply with quote  
PostPosted: Sat Mar 31, 2018 9:44 pm 
Offline
User avatar

Joined: Tue Oct 25, 2016 8:56 pm
Posts: 362
Just complete to the discussion, I figured out that you need a diode, pointing left on the diagram above, with pull-ups on both sides, otherwise there is a rare circumstance involving WAI where the system could become deadlocked.

Your TSB/CMP solution is interesting, though I prefer the speed of the hardware solution. I'd probably have to use the TSB/CMP method if more than two devices were sharing the same RAM, luckily the architecture I have is each slave has its own shared RAM - so slaves are not aware of eachother, only the master.

_________________
Want to design a PCB for your project? I strongly recommend KiCad. Its free, its multiplatform, and its easy to learn!
Also, I maintain KiCad libraries of Retro Computing and Arduino components you might find useful.


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

All times are UTC


Who is online

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