Thread View: net.micro.16k
3 messages
3 total messages
Started by Dave Mason
Tue, 17 Dec 1985 23:33
Need word version of test-and-set
Author: Dave Mason
Date: Tue, 17 Dec 1985 23:33
Date: Tue, 17 Dec 1985 23:33
44 lines
2651 bytes
2651 bytes
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.BITNET
Re: Need word version of test-and-set
Author: Steve Villee
Date: Thu, 26 Dec 1985 19:43
Date: Thu, 26 Dec 1985 19:43
57 lines
2866 bytes
2866 bytes
> 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
Re: Need word version of test-and-set
Author: Dave Mason
Date: Sun, 29 Dec 1985 00:18
Date: Sun, 29 Dec 1985 00:18
29 lines
2297 bytes
2297 bytes
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
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads