tradeoffs between taskLock and using a semaphore?
Todd Hoff
be too heavy weight. Someone suggested using taskLock/taskUnlock as
a form of mutual exclusion.
Is this a good idea? What are the tradeoffs? Is the performance better?
Thanx
Jeff Hill
vxTas() would be less intrusive?
Jeff
Stan Schneider
>> Submitted-by: th...@netxwest.com (Todd Hoff)
>>
>> We have a situtation where using a semaphore for mutual exclusion might
>> be too heavy weight. Someone suggested using taskLock/taskUnlock as
>> a form of mutual exclusion.
>>
>> Is this a good idea? What are the tradeoffs? Is the performance better?
>>
Well, I happened to have a little test program lying around (appended).
The test is really crude; someone out there is likely to tear it to shreds. It
assumes the common case: no exclusion is required (usually a good
assumption).
Bottom line: Since taskUnlock reschedules, taskLock/Unlock isn't much faster
than semGive/take, and it raises your scheduling latency. intUnlock is the
fastest, but it raises your interrupt latency. If you don't care about
latency, intLock's hard to beat. vxTas is somewhere in between.
They're all pretty damn fast in the common "do nothing" case.
->lockTest 1000000
Sem test took = 4.48 secs
taskLock test took = 3.95 secs
intLock test took = 1.85 secs
vxTas test took = 3.20 secs
-- Stan
===============================================================================
= = =
= Stan Schneider = email: st...@rti.com =
= Real-Time Innovations, Inc. = Phone: (408) 720-8312 =
= 954 Aster, Sunnyvale, CA 94086 = Fax: (408) 720-8419 =
= = =
===============================================================================
#include "stdio.h"
#include "tickLib.h"
#include "semLib.h"
#include "taskLib.h"
#include "intLib.h"
#include "vxLib.h"
#include "sysLib.h"
void lockTest(int nloops)
{
int i;
int start;
int key;
int tasLock;
SEM_ID sem = semBCreate(SEM_Q_PRIORITY, SEM_FULL);
start = tickGet();
for (i=0; i<nloops; i++) {
semTake(sem, WAIT_FOREVER);
semGive(sem);
}
printf("Sem test took = %.2f secs\n",
(float) (tickGet()-start)/sysClkRateGet());
start = tickGet();
for (i=0; i<nloops; i++) {
taskLock();
taskUnlock();
}
printf("taskLock test took = %.2f secs\n",
(float) (tickGet()-start)/sysClkRateGet());
start = tickGet();
for (i=0; i<nloops; i++) {
key = intLock();
intUnlock(key); /* Hardware latch => we won't miss ticks. */
}
printf("intLock test took = %.2f secs\n",
(float) (tickGet()-start)/sysClkRateGet());
start = tickGet();
tasLock = 0;
for (i=0; i<nloops; i++) {
while (!vxTas(&tasLock)) {}
tasLock = 0;
}
printf("vxTas test took = %.2f secs\n",
(float) (tickGet()-start)/sysClkRateGet());
}
Roeber
> Bottom line: Since taskUnlock reschedules, taskLock/Unlock isn't much faster
> than semGive/take, and it raises your scheduling latency. intUnlock is the
> fastest, but it raises your interrupt latency. If you don't care about
> latency, intLock's hard to beat. vxTas is somewhere in between.
>
> They're all pretty damn fast in the common "do nothing" case.
Stan answered the question well with a little benchmark program.
There is one thing that needs correction though. Both Stan and Jeff Hill
indicated that you could use vxTas to protect a critical section. I'm not
sure where they are coming from. vxTas (a test and set mechanism) is used
at the heart of any spin lock strategy for protecting critical sections
in a multiprocessor system. It is useless for uniprocessor synchronization
since you have to account for the case where someone else has the lock and gets
suspended, allowing another task to run. If that new task tries to acquire the
same lock your dead, classic deadlock situation. There has recently been some
very good work out of DEC research on using adaptive spin locking strategies
to handle this case but the issues are beyond what I think people want to deal
with for an embedded system. To avoid this problem, in our multiprocessor
version of VxWorks, we always make sure interrupts are locked (using intLock)
while a lock is held as acquired through vxTas (this is the same thing WRS
does in the backplane driver where they use vxTas for multiprocessor synchron-
ization).
The bottom line is that vxTas isn't much use for uniprocessor critical
section protection. The method of choice is intLock/intUnlock but you have
to really make sure not to abuse it since it does increase interrupt latency.
We have actually updated intLib.h to contain intLock/intUnlock as inline
routines. The inline assembler versions drop the overhead to just a few
instructions. I haven't seen VxWorks 5.1 yet so I don't know if WRS has
taken our suggestion and done the same thing. Fred
Stan Schneider
>> Both Stan and Jeff Hill indicated that you could use vxTas to protect a
>> for uniprocessor
And the survey says... BANNH.
Sorry about that. I threw the tas in at the last minute without thinking. I
stand sheepishly corrected.
Jeff Hill
Fred Roeber writes:
> It is useless for uniprocessor synchronization
> since you have to account for the case where someone else has the lock and gets
> suspended, allowing another task to run. If that new task tries to acquire the
> same lock your dead, classic deadlock situation.
Which leads to the question:
If a thread bombs with a lock on and has potentially left the
resource inconsistent do you want the OS to unlock (and allow
other threads to use the inconsistent resource)?
Take for example a doubly linked list:
Thread one takes the lock for the list.
Thread two asks for the lock and pends for it.
Thread one bombs while in the middle of deleting a node
from the list and with the lock on.
The list is left with inconsistent forward and backward
pointers.
The OS allows thread two to take the lock.
Thread two traverses the list and bombs because the
list is inconsistent.
Jeff
Steven King
And then there is the polling for a global flag method.
If you need mutex between two cooperating tasks (or an interrupt routine
and a task), then you can have them agree upon a protocol. This protocol
is basically:
Task1 (or interrupt routine)
----------------------------
o Write into a global variable when you need mutex
o Perform the necessary activity
o Write some other value (presumably zero) into the global variable to
indicate completion
Task2
-----
o Check the global flag for zero
o If not zero, call taskDelay(somePeriodOfTime)
o Check to see if you're sick and tired of checking the flag
If so, break out of the loop (or some appropriate action, like a timeout)
o Loop back and check the flag again
Note that this does not work for 3 or more participants. It also does not
work for anything but a steady stream of events. Task2 must always come
back and wait for Task1 to do something first. Task1 must have the
resources (message queue space, shared memory buffers, etc.) to perform
the necessary actions.
In the case where a task is being fed by an interrupt routine, I have seen
where this method is faster than semTake/semGive. In my case, the overhead
was 2 uSec vs. the 15 uSec of semTake/semGive. It is NOT general purpose,
and if the timing of the events change then you're hosed.
Stan's timings cover all of the other cases.
Steven (s...@strl.labs.tek.com)
"Sometimes if you have a cappuccino and then try again it will work OK."
(Dr. Brian Reid) "Sometimes one cappuccino isn't enough." (Marcus Ranum)
"A double vanilla latte always works." (Me)
P.Owens,C20,3492
>th...@netxwest.com (Todd Hoff) writes:
>|> We have a situtation where using a semaphore for mutual exclusion might
>|> be too heavy weight. Someone suggested using taskLock/taskUnlock as
>|> a form of mutual exclusion.
>|>
>|> Is this a good idea? What are the tradeoffs? Is the performance better?
>
>And then there is the polling for a global flag method.
>
>If you need mutex between two cooperating tasks (or an interrupt routine
>and a task), then you can have them agree upon a protocol. This protocol
>is basically:
>
>Task1 (or interrupt routine)
>----------------------------
>
>o Write into a global variable when you need mutex
>o Perform the necessary activity
>o Write some other value (presumably zero) into the global variable to
> indicate completion
>
>Task2
>-----
>
>o Check the global flag for zero
>o If not zero, call taskDelay(somePeriodOfTime)
>o Check to see if you're sick and tired of checking the flag
> If so, break out of the loop (or some appropriate action, like a timeout)
>o Loop back and check the flag again
>
Think what will happen if :-
o Task2 reads the flag and finds it to be zero
o Task2 starts using the resource
o Task1 preempts, sets the flag and does its bit
o Task2 continues using the corrupted resourse
---
Pete Owens
P.O...@daresbury.ac.uk
Rajeev Chawla
> It is useless for uniprocessor synchronization
> since you have to account for the case where someone else has the lock and gets
> suspended, allowing another task to run. If that new task tries to acquire the
> same lock your dead, classic deadlock situation.
Deadlock will result only if the other task did a busy wait on the lock.
To avoid deadlocks, Test and Set (TAS) mechanism loop could be modified to
include timeouts. When a task fails to acquire (using TAS) the lock, it times
out allowing other tasks to run in that timeout period. When the timeout
interval is over, this task restarts the TAS loop.
This can lead to starvation which is, as a matter of fact, built in TAS.
Rajeev
--
----------------------------------------------------------------------------
- __
-- ~( @\ \ /-=-=-=-=-=-=-=-=-=-=-=---=-=-=-
--- _________]_[__/_>________ ______------ Rajeev Chawla
/ ____ \ <> | ____ \ ______ Integrated Systems
=\_/ __ \_\_______|_/ __ \__D ------ 408-980-1500 raj...@isi.com
________(__)_____________(__)____ \-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
You can drive as fast as you want in any direction you want.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=