spin lock
Krishna Myneni
I want to implement Forth code that does the following. One Forth word
is a signal handler, which executes periodically on a timer signal. A
second word, which is a normal Forth word, executes in the foreground.
Both words access a shared resource, an analog input card. Since both
words must configure the card (set up its input channel, gain, etc.),
there exists the possibility of data corruption. The solution is to
implement some mutual exclusion mechanism, possibly a spin lock, which
would work as follows:
variable DAQ_IN_USE
false DAQ_IN_USE !
: word1
DAQ_IN_USE spin-lock
:
\ setup card and read data
:
spin-unlock
;
: word2
DAQ_IN_USE spin-lock
:
\ setup card and read data
:
spin-unlock
;
where spin-lock and spin-unlock would be implemented in assembler to
avoid simultaneous access of the lock variable. The high-level
equivalents of these words are:
: spin-lock ( a -- )
BEGIN DUP @ 0= UNTIL
true SWAP ! ;
: spin-unlock ( a -- )
false SWAP ! ;
How have Forth programmer's typically handled this type of situation?
Although I gave an example of a signal handler, this situation would
apply equally to a multi-tasking Forth system, in which word1 and word2
are concurrent tasks (threads).
At this point, I'm not sure if a spin lock is the best solution for my
application. It may be that the handler word can safely EXIT if
DAQ_IN_USE is true, rather than wait for it to be unlocked. However, the
non-handler word must wait.
Krishna Myneni
Elizabeth D Rather
> I want to implement Forth code that does the following. One Forth word
> is a signal handler, which executes periodically on a timer signal. A
> second word, which is a normal Forth word, executes in the foreground.
> Both words access a shared resource, an analog input card. Since both
> words must configure the card (set up its input channel, gain, etc.),
> there exists the possibility of data corruption. The solution is to
> implement some mutual exclusion mechanism, possibly a spin lock, which
> would work as follows:
...
For many years (>30) FORTH, Inc. has used a resource management system
called GET/RELEASE. It uses a "facility variable" (a plain old VARIABLE
used for this purpose) plus the following words (in all cases, the addr
is returned by invoking the facility name):
GET ( addr — )
Obtain control of the facility variable at addr, having first made one
circuit of the SwiftOS round robin. If the facility is owned by another
task, the task executing GET will wait until the facility is available.
GRAB ( addr — )
Obtain control of the facility variable at addr. If the facility is
owned by another task, the task executing GRAB will wait until the
facility is available. GRAB does not PAUSE before attempting to obtain
control, so, in order to prevent deadlocks and avoid “resource hogging,”
it should be used only in circumstances in which it is known that no
other task could have the facility.
RELEASE ( addr — )
Relinquish the facility variable at addr. If the task executing RELEASE
did not previously own the facility, this operation is a no-op.
If the contents of the variable is zero, the facility is available. If
it is non-zero, it contains the handle of the owning task. If you
attempt to GET a facility you own, it's a no-op. If someone else owns
it, you wait. If you attempt to RELEASE a facility you don't own, it's
a no-op.
99% of the time, it's just GET and RELEASE, GRAB is for special
situations. All three words are very simple, 1 or 2 lines. They work
well with our multitasker concept, in which tasks always PAUSE during
I/O. If the facility being controlled is an interrupting device, the
interrupt usually clears the facility variable.
Example:
VARIABLE WIDGET
: RUN-WIDGET ( -- ) WIDGET GET ...(do stuff)... WIDGET RELEASE ;
It's been used for both hardware (e.g. disk, printers, other devices)
and shared software resources (e.g. sort with dedicated buffer;
non-reentrant code).
Cheers,
Elizabeth
--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310-491-3356
5155 W. Rosecrans Ave. #1018 Fax: +1 310-978-9454
Hawthorne, CA 90250
http://www.forth.com
"Forth-based products and Services for real-time
applications since 1973."
==================================================
Krishna Myneni
From your description, I gather that GRAB and RELEASE are equivalent to the spin
lock and unlock methods, while GET uses a scheduling scheme to grant access to
the resource and prevent one task from hogging the shared resource. It may be
that I have to implement something similar for my application as well.
When you say that tasks always PAUSE during I/O, is this the POSIX pause() function?
Krishna
Elizabeth D Rather
> Elizabeth D Rather wrote:
...
> From your description, I gather that GRAB and RELEASE are equivalent to the spin
> lock and unlock methods, while GET uses a scheduling scheme to grant access to
> the resource and prevent one task from hogging the shared resource. It may be
> that I have to implement something similar for my application as well.
>
> When you say that tasks always PAUSE during I/O, is this the POSIX pause() function?
No, unless they coincidentally do the same things ;-) The SwiftOS
multitasker (which technically is identical to the polyFORTH multitasker
and generations before that) runs standalone (multitasking under Windows
is quite different). It's basically a round-robin, with the rule that
whenever a task initiates I/O it relinquishes the CPU and remains
inactive (other tasks can run) until the I/O is complete. A task can
also voluntarily pause any other time, e.g. during a CPU-intensive
operation.
Elizabeth D Rather
> Krishna Myneni wrote:
>> Elizabeth D Rather wrote:
> ...
>> From your description, I gather that GRAB and RELEASE are equivalent
>> to the spin
>> lock and unlock methods, while GET uses a scheduling scheme to grant
>> access to
>> the resource and prevent one task from hogging the shared resource. It
>> may be
>> that I have to implement something similar for my application as well.
>>
>> When you say that tasks always PAUSE during I/O, is this the POSIX
>> pause() function?
>
> No, unless they coincidentally do the same things ;-) The SwiftOS
> multitasker (which technically is identical to the polyFORTH multitasker
> and generations before that) runs standalone (multitasking under Windows
> is quite different). It's basically a round-robin, with the rule that
> whenever a task initiates I/O it relinquishes the CPU and remains
> inactive (other tasks can run) until the I/O is complete. A task can
> also voluntarily pause any other time, e.g. during a CPU-intensive
> operation.
Ok, I looked up documentation for POSIX pause(). It's the same general
idea, except the SwiftOS multitasker is a lot simpler (and faster).
Anton Ertl
>When you say that tasks always PAUSE during I/O, is this the POSIX pause() function?
No, it's like the POSIX sched_yield() function.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2007: http://www.complang.tuwien.ac.at/anton/euroforth2007/
Bernd Paysan
> For many years (>30) FORTH, Inc. has used a resource management system
> called GET/RELEASE. It uses a "facility variable" (a plain old VARIABLE
> used for this purpose) plus the following words (in all cases, the addr
> is returned by invoking the facility name):
bigFORTH has something similar, with different names (LOCK/UNLOCK instead of
GET/RELEASE - no GRAB option). In principle, these two work with VARIABLEs,
but in practice, it turned out to be better to work with a special creator
word, which I called SEMA (short for semaphore). The reason was that when a
task dies, it (or rather the multitasker that kills the task) must unlock
all locks, and for that purpose, all SEMAs are linked together.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
Elizabeth D Rather
> Elizabeth D Rather wrote:
>> For many years (>30) FORTH, Inc. has used a resource management system
>> called GET/RELEASE. It uses a "facility variable" (a plain old VARIABLE
>> used for this purpose) plus the following words (in all cases, the addr
>> is returned by invoking the facility name):
>
> bigFORTH has something similar, with different names (LOCK/UNLOCK instead of
> GET/RELEASE - no GRAB option). In principle, these two work with VARIABLEs,
> but in practice, it turned out to be better to work with a special creator
> word, which I called SEMA (short for semaphore). The reason was that when a
> task dies, it (or rather the multitasker that kills the task) must unlock
> all locks, and for that purpose, all SEMAs are linked together.
That makes sense. Our systems do not make provision for tasks to "die",
which simplifies a lot of things (as well as improving overall
reliability, we think).
Krishna Myneni
> ...
> bigFORTH has something similar, with different names (LOCK/UNLOCK instead of
> GET/RELEASE - no GRAB option). In principle, these two work with VARIABLEs,
> but in practice, it turned out to be better to work with a special creator
> word, which I called SEMA (short for semaphore). The reason was that when a
> task dies, it (or rather the multitasker that kills the task) must unlock
> all locks, and for that purpose, all SEMAs are linked together.
>
What is the technique by which LOCK ensures there is no resource hogging by a
single task? I'd like to study it if you can point me to the proper source file
in bigFORTH (I have v 2.1.7).
For my application, neither "task" can terminate in an unorderly fashion, i.e.
without unlocking the resource, so I can get away with a simple VARIABLE for the
lock.
Krishna
Elizabeth D Rather
...
> What is the technique by which LOCK ensures there is no resource hogging by a
> single task? I'd like to study it if you can point me to the proper source file
> in bigFORTH (I have v 2.1.7).
In our systems, the important concept is that GET allows other tasks to
run before asking for the resource. This ensures that if someone else
has it they get a chance to release it. If the resource is held by
someone else, the task alternately PAUSEs and checks for it. Beyond
that, it's just a matter of good program design: put your GET and
RELEASE (or LOCK/UNLOCK, or whatever) around the smallest possible
section of code, so you hold the resource the shortest time possible,
and ensure that any error handling releases the resource. Remember, if
a task releases a resource that it doesn't currently own, it's a no-op,
so it's safe to put RELEASEs in any error recovery procedures.
> For my application, neither "task" can terminate in an unorderly fashion, i.e.
> without unlocking the resource, so I can get away with a simple VARIABLE for the
> lock.
Good.
Marcel Hendrix
> In our systems, the important concept is that GET allows other tasks to
> run before asking for the resource. This ensures that if someone else
> has it they get a chance to release it.
[..]
Wasn't there an *interrupt* involved in the OP's question?
What happens if a task has the lock/variable and interrupt code needs it?
The interrupt has to silently fail then? Or should the design be that it
can (almost) always run and wake a dedicated, pausable,TASK to further
handle the problem? (This postpones the problem until it becomes a real
error).
-marcel
Elizabeth D Rather
If a task is requesting service from a shared device, it should GET the
device before making the service request, then sleep. Interrupt code
can complete the time-critical part of the service, then RELEASE the
device and awaken the task to do further processing, if any.
It should never happen that a totally unexpected interrupt occurs for a
shared device. Some task should be expecting it, having done a GET. A
nice side-effect of this scheme is that the GET associates the task
handle with the facility, so the interrupt code knows who is expecting
the interrupt and hence whom to wake up.
Krishna Myneni
It's not quite as bad as a real interrupt --- it's a periodic signal, so the
signal handler can do one of three things:
a) check the lock, and if its in use, just EXIT and hope to get the lock on the
next period. The handler can miss a couple of periods (hmm... perhaps I should
rephrase that) on occasion, without causing a significant problem.
b) wait for the lock to be realeased, as with spin-lock. As long as the wait is
small, relative to the handler period, this should be ok.
c) use a combination of both, by waiting only a specified amount of time for the
lock. If the lock is not available within the time period, it can EXIT. If it
becomes available, go ahead and execute.
The only concern I have is to avoid the situation where the signal handler never
gets the lock.
Krishna
Marcel Hendrix
[..][..]
>> The interrupt has to silently fail then? Or should the design be that it
>> can (almost) always run and wake a dedicated, pausable,TASK to further
>> handle the problem? (This postpones the problem until it becomes a real
>> error).
> If a task is requesting service from a shared device, it should GET the
> device before making the service request, then sleep. Interrupt code
> can complete the time-critical part of the service, then RELEASE the
> device and awaken the task to do further processing, if any.
Neat. That would save an extra task, but if the interrupt for some reason
does not come because it is missing a period, the system might need to be
aborted.
> It should never happen that a totally unexpected interrupt occurs for a
> shared device. Some task should be expecting it, having done a GET. A
> nice side-effect of this scheme is that the GET associates the task
> handle with the facility, so the interrupt code knows who is expecting
> the interrupt and hence whom to wake up.
Wouldn't it be rather dangerous for the IRQ handler to do this? The task
could be in the (interrupted) process of being woken up because of a time
out, kill or something... Stopping the IRQ would kill the task, while
stopping the task might not prevent the IRQ from waking it inappropriately.
I see the SwiftForth reference manual has a good discussion on GET and
RELEASE.
-marcel
Elizabeth D Rather
> Elizabeth D Rather <erath...@forth.com> writes Re: spin lock
> [..]
>> Marcel Hendrix wrote:
>>> Elizabeth D Rather <erath...@forth.com> wrote Re: spin lock
> [..]
>>> What happens if a task has the lock/variable and interrupt code needs it?
>>> The interrupt has to silently fail then? Or should the design be that it
>>> can (almost) always run and wake a dedicated, pausable,TASK to further
>>> handle the problem? (This postpones the problem until it becomes a real
>>> error).
>
>> If a task is requesting service from a shared device, it should GET the
>> device before making the service request, then sleep. Interrupt code
>> can complete the time-critical part of the service, then RELEASE the
>> device and awaken the task to do further processing, if any.
>
> Neat. That would save an extra task, but if the interrupt for some reason
> does not come because it is missing a period, the system might need to be
> aborted.
I suppose some devices might need a time-out. That's not been my
experience, though.
>> It should never happen that a totally unexpected interrupt occurs for a
>> shared device. Some task should be expecting it, having done a GET. A
>> nice side-effect of this scheme is that the GET associates the task
>> handle with the facility, so the interrupt code knows who is expecting
>> the interrupt and hence whom to wake up.
>
> Wouldn't it be rather dangerous for the IRQ handler to do this? The task
> could be in the (interrupted) process of being woken up because of a time
> out, kill or something... Stopping the IRQ would kill the task, while
> stopping the task might not prevent the IRQ from waking it inappropriately.
"Waking up a task" from an IRQ merely involves setting a code in its
status cell. It's pretty non-violent, and if the task is already waking
up it's a no-op. And we don't kill tasks. We do have a word:
: NOD ( -- ) BEGIN STOP AGAIN ;
...which you can assign a task to do when it isn't doing anything else,
in case an interrupt it's associated with wakes it up inappropriately.
But normally the task wouldn't GET a facility unless it expected to do
something with it.
> I see the SwiftForth reference manual has a good discussion on GET and
> RELEASE.
Yeah, they work pretty much the same in SwiftForth, although the
multitasking is completely different. The SwiftOS multitasker is found
in SwiftX targets.
Elizabeth D Rather
> Marcel Hendrix wrote:
>> Elizabeth D Rather <erath...@forth.com> wrote Re: spin lock
>>
>>> In our systems, the important concept is that GET allows other tasks to
>>> run before asking for the resource. This ensures that if someone else
>>> has it they get a chance to release it.
>> [..]
>>
>> Wasn't there an *interrupt* involved in the OP's question?
>>
>> What happens if a task has the lock/variable and interrupt code needs it?
>> The interrupt has to silently fail then? Or should the design be that it
>> can (almost) always run and wake a dedicated, pausable,TASK to further
>> handle the problem? (This postpones the problem until it becomes a real
>> error).
>>
>> -marcel
>>
>
> It's not quite as bad as a real interrupt --- it's a periodic signal, so the
> signal handler can do one of three things:
>
> a) check the lock, and if its in use, just EXIT and hope to get the lock on the
> next period. The handler can miss a couple of periods (hmm... perhaps I should
> rephrase that) on occasion, without causing a significant problem.
This is a common situation with devices that are going to be tied up for
an extended period, like a printer. A facility VARIABLE contains zero
when the facility's available, so it's easy to check if it's non-zero,
and abort, ask the user for instructions, implement option c) or whatever.
> b) wait for the lock to be realeased, as with spin-lock. As long as the wait is
> small, relative to the handler period, this should be ok.
This is the common situation with disks and other devices that operate
in time frames of <1 sec. or so. That's actually what GET handles (with
no other logic). Situation a) requires actual code to test & abort.
> c) use a combination of both, by waiting only a specified amount of time for the
> lock. If the lock is not available within the time period, it can EXIT. If it
> becomes available, go ahead and execute.
That would be device-specific, but not hard to handle.
> The only concern I have is to avoid the situation where the signal handler never
> gets the lock.
That's called a bug, dear ;-) We all like to avoid those.
Bernd Paysan
> What is the technique by which LOCK ensures there is no resource hogging
> by a single task? I'd like to study it if you can point me to the proper
> source file in bigFORTH (I have v 2.1.7).
If a task unlocks a semaphore, it's given to the next task in the queue (the
information in the semaphore also contains all those tasks who attempted to
lock it), and the task in the queue is woken up with WAKE. That's in UNLOCK
(just do "view unlock"). The code for releasing all semaphors when a task
is killed is in UNLOCK-ALL.
Unloke Forth Inc's GET/RELEASE, tasks go to sleep if they can't get a lock.
I.e. it's not a spin-lock. But since going to sleep just involves two
pointers to change and a PAUSE, it's lightweight in bigFORTH, as well.
There is no prevention that a task which stays alive never unlocks a
semaphore. There's also no deadlock prevention. You can't prevent bugs, but
you can make sure there is fairness.
> For my application, neither "task" can terminate in an unorderly fashion,
> i.e. without unlocking the resource, so I can get away with a simple
> VARIABLE for the lock.
Should be a 2VARIABLE.
Elizabeth D Rather
> Krishna Myneni wrote:
...
> Unloke Forth Inc's GET/RELEASE, tasks go to sleep if they can't get a lock.
> I.e. it's not a spin-lock. But since going to sleep just involves two
> pointers to change and a PAUSE, it's lightweight in bigFORTH, as well.
On average, 2-3 machine instructions are actually executed before either
the task goes back to sleep if the facility is not available, or the GET
is successful. Mostly the task is PAUSEd (asleep but set to wake next
time around the round-robin). So it might be described as "sleeping
with one eye open".
> There is no prevention that a task which stays alive never unlocks a
> semaphore. There's also no deadlock prevention. You can't prevent bugs, but
> you can make sure there is fairness.
Right.
>> For my application, neither "task" can terminate in an unorderly fashion,
>> i.e. without unlocking the resource, so I can get away with a simple
>> VARIABLE for the lock.
>
> Should be a 2VARIABLE.
Not necessary in our system, since there's no separate queue for a
facility, just the main round-robin.
Krishna Myneni
> Krishna Myneni wrote:
> ...
>> handler never
>> gets the lock.
>
> That's called a bug, dear ;-) We all like to avoid those.
>
> Cheers,
> Elizabeth
>
It would certainly be poor design, at the least. But I should state the concern
more accurately. I want to ensure that the handler obtains a lock during at
least x% of its attempts, where in my application, x is around 50. The mutual
exclusion mechanism must guarantee that this will be the case.
Cheers,
Krishna
Elizabeth D Rather
Well, you need to estimate how many tasks will be competing for the
resource, and how long on average it will be held each time. Knowing
these two facts should clarify whether you have a problem or not.
If it does look like there's a problem, the first thing to do is think
about how to reduce the amount of time each task holds the resource,
maybe by re-designing its handler. For example, if you read data and
then analyze it, do not hold the resource during the analysis -- just
grab the data and release the resource.
If you have too many tasks needing the resource for too long, there's no
"mechanism" that will resolve the bottleneck. You either need to reduce
the demand or provide more resources.
Krishna Myneni
I believe I understand how to analyze the timing of my problem. I also stated at
the outset that the problem has only two "tasks" competing for a single
resource. What I'm looking for is an actual algorithm/code solution. If you can
provide such details, then that will be more useful than general answers.
Cheers,
Krishna
Krishna Myneni
> I want to implement Forth code that does the following. One Forth word
> is a signal handler, which executes periodically on a timer signal. A
> second word, which is a normal Forth word, executes in the foreground.
> Both words access a shared resource, an analog input card. Since both
> words must configure the card (set up its input channel, gain, etc.),
> there exists the possibility of data corruption. The solution is to
> implement some mutual exclusion mechanism, possibly a spin lock, which
> would work as follows:
Below is test code to illustrate a possible solution using spin-lock. It is
kForth specific, due to the signal handler implementation. The output is also
shown. The ratio of lock acquisitions for the handler and the foreground task
depends sensitively on the sleep time (variable SLEEP_TIME) for the method. The
method is very inefficient, wasting considerable time. Some queuing logic is
probably required.
Krishna
--
\ --------------------------------------------------------------
\ spinlock-ex.4th
\
\ Requires:
\ signal.4th
\ asm-x86.4th
\ Revisions:
\ 2007-08-25 created km
\
include signal.4th
include asm-x86.4th
VARIABLE DAQ_IN_USE ( the lock variable )
VARIABLE START_TIME
VARIABLE SLEEP_TIME ( sleep time in microseconds )
300000 SLEEP_TIME !
: elapsed ( -- u ) ms@ START_TIME @ - ;
\ : spin-lock ( a -- )
\ BEGIN DUP @ 0= UNTIL true SWAP ! ;
\ assembler spin-lock is different from Forth version above
CODE spin-lock ( a -- )
TRUE # eax mov,
Label: spin
0 [ebx] ecx mov,
eax 0 [ecx] xchg,
0<,
IF,
spin # jmp,
THEN,
0 # eax mov,
TCELL # ebx add,
END-CODE
\ : unlock ( a -- ) 0 SWAP ! ;
CODE unlock ( a -- )
0 [ebx] ecx mov,
0 # 0 [ecx] mov,
TCELL # ebx add,
END-CODE
: handler ( n -- )
DROP
DAQ_IN_USE spin-lock
CR elapsed 6 .r ." HANDLER has lock!"
100 MS ( time to process )
DAQ_IN_USE unlock
;
CR .( Use ESC to halt the test)
: test ( -- )
DAQ_IN_USE unlock \ for safety
['] handler SIGALRM forth-signal drop \ install the handler
1000 1000 SET-TIMER \ Send SIGALRM to kForth every 1000 ms
BEGIN
KEY? IF
KEY 27 = IF
SIG_IGN SIGALRM forth-signal DROP \ Stop sending SIGALRM
CR ." Exiting test "
EXIT
THEN
THEN
DAQ_IN_USE spin-lock
CR elapsed 6 .r ." test has lock."
100 MS ( time to process )
DAQ_IN_USE unlock
SLEEP_TIME @ usleep \ relinquish control to the system for a while
AGAIN
;
test
\ -----------------------------------------------------------------------
Here's the output:
-------------------------------------------------------------------------
krishna@ungee:~/kforth> kforth spinlock-ex
# is redefined
Use ESC to halt the test
76 test has lock.
478 test has lock.
883 test has lock.
1078 HANDLER has lock!
1179 test has lock.
1583 test has lock.
1987 test has lock.
2078 HANDLER has lock!
2483 test has lock.
2887 test has lock.
3078 HANDLER has lock!
3179 test has lock.
3583 test has lock.
3988 test has lock.
4079 HANDLER has lock!
Exiting test ok
500000 SLEEP_TIME !
ok
test
11843 test has lock.
12446 test has lock.
12847 HANDLER has lock!
12947 test has lock.
13551 test has lock.
13847 HANDLER has lock!
13947 test has lock.
14551 test has lock.
14843 HANDLER has lock!
14943 test has lock.
15547 test has lock.
15844 HANDLER has lock!
15944 test has lock.
16548 test has lock.
16844 HANDLER has lock!
16944 test has lock.
17548 test has lock.
17844 HANDLER has lock!
Exiting test ok
Krishna Myneni
> ...
> Below is test code to illustrate a possible solution using spin-lock. ...
The CODE defn of spin-lock has been cleaned up a bit, and some other minor
changes made to the file. It is available on the kForth Programming Examples
Page, as spinlock-ex.4th.
See http://ccreweb.org/software/kforth/kforth4.html
Krishna