mason@utcsri.UUCP (Dave Mason) (12/18/85)
I am looking for a fast way to exit a critical section and see if anyone
else was waiting to get in. This is relatively easy (if rather obscure) to
do on other processors (like PDP-11, S/370, VAX, MC68000). Despite being
a NS32000 booster, I can't think of a way to do this on the NS32000.
I would appreciate help particularly from the friendly people at nsc.
Here is how I would do it on the PDP-11:
flag: .word 1 ; section initially free
; enter critical section
decb flag+1 ;say we want in
asrb flag ; try & enter
bcs wegotit
;do it the slow way...put us in a queue etc. (don't worry about details
wegotit: ;critical section
...
;exit critical section
add $0x0101,flag ; say it's free & check for anyone waiting
bgt weregone ; no-one was...fast exit
;do it the slow way, check the queue etc. (more messy details)
(sorry for any non-unix syntax, I've never used unix assemblers)
(I did warn you it was obscure...pretty kludgey too...much cleaner & clearer
with Compare-and-Swap ala S/370)
(Note: the foregoing depends on the read-modify-write cycle for the asrb and
the add to be indivisible across processors)
(Note: test-and-set won't do the trick (at least not anyway I can see it),
because we have to do 2 things: exit the critical section; check for others,
in an indivisible way. A 2 bit test & set would do, but compare&swap is the
more general solution.)
The reason I'm interested in this is that the slow way is 2-3 decimal orders
of magnitude slower (for other reasons), and I want this to be a cheap,
therefore useful, facility.
If the people at National can't come up with something, could I interest
you in a nice Compare-and-swap instruction?
--
Usenet: {dalcs dciem garfield musocs qucis sask titan trigraph ubc-vision
utzoo watmath allegra cornell decvax decwrl ihnp4 uw-beaver}
!utcsri!mason Dave Mason, U. Toronto CSRI/ Ryerson Polytech
CSNET: mason@Toronto
ARPA: mason%Toronto@CSNet-Relay
BITNET: FCTY7053@RYERSON.BITNETsteve@anasazi.UUCP (Steve Villee) (12/26/85)
> I am looking for a fast way to exit a critical section and see if anyone > else was waiting to get in. This is relatively easy (if rather obscure) to > do on other processors (like PDP-11, S/370, VAX, MC68000). Despite being > a NS32000 booster, I can't think of a way to do this on the NS32000. There is a way to do this on any processor that has a test-and-set primitive. The basic idea is to have a counter which is -1 if the resource is free, and otherwise the number of processes waiting to use the resource. This counter is updated using ordinary (non-atomic) instructions, but access to it is gated via an outer gate using the test-and-set primitive. You just spin on the outer gate until you get in, quickly examine and update the counter, and then open the outer gate. If done properly, contention for the outer gate should be minimal, and there should be very little actual "spinning" on it. My National code is a little rusty, but here goes: counter: .word -1 outer_gate: .byte 0 ; ... Seize_resource: sbitib 0,outer_gate ; Try to shut the outer gate. bfs Seize_resource ; Already shut - loop. addqw 1,counter ; Update the counter. cmpqw 0,counter ; See if resource was free. (Ugh!) movqb 0,outer_gate ; Open gate in any case. beq label_a ; Yes - the resource is ours now. ; (Perform a P-op on the semaphore associated with the resource.) label_a: ; We now have the resource. ; ... Release_resource: sbitib 0,outer_gate ; Try to shut the outer gate. bfs Release_resource ; Already shut - loop. addqw -1,counter ; Update the counter. movqb 0,outer_gate ; Open gate. bcc label_b ; It went to -1, so nobody waiting. ; (Perform a V-op on the semaphore associated with the resource.) label_b: ; We no longer have the resource. By the way, I don't think this is any easier on the Motorola 68000. As far as I know, its only atomic instruction is tas. The 68020 brings in a compare and swap. Did you have another idea for the 68000? --- Steve Villee (ihnp4!terak!anasazi!steve) International Anasazi, Inc. 7500 North Dreamy Draw Drive, Suite 120 Phoenix, Arizona 85020 (602) 870-3330
mason@utcsri.UUCP (Dave Mason) (12/29/85)
In article <450@anasazi.UUCP> steve@anasazi.UUCP (Steve Villee) writes: >> I am looking for a fast way to exit a critical section and see if anyone >> else was waiting to get in. > >There is a way to do this on any processor that has a test-and-set primitive. >The basic idea is to have a counter which is -1 if the resource is free, and >otherwise the number of processes waiting to use the resource. This counter >is updated using ordinary (non-atomic) instructions, but access to it is gated >via an outer gate using the test-and-set primitive. You just spin on the outer >gate until you get in, quickly examine and update the counter, and then open >the outer gate. If done properly, contention for the outer gate should be >minimal, and there should be very little actual "spinning" on it. > The only problem is that I wanted to avoid spin-locks as the processes are actually user-level timeshared processes, and if the holder of the lock were to get swapped out, a lot of CPU time could be burned before it got brought back in. It appears that there isn't any way around it though, at some level you've got to spin-lock, so I will do a system call if I don't get the original lock (& do the spin-lock in the system where it's cheaper) (I was going to have a system call to handle the queue anyway, it just has to be a little more complicated than I had hoped.) Thanks -- Usenet: {dalcs dciem garfield musocs qucis sask titan trigraph ubc-vision utzoo watmath allegra cornell decvax decwrl ihnp4 uw-beaver} !utcsri!mason Dave Mason, U. Toronto CSRI/ Ryerson Polytech CSNET: mason@Toronto ARPA: mason%Toronto@CSNet-Relay BITNET: FCTY7053@RYERSON.BITNET