Subject:
|
Re: NQC 2.0 and some math questions
|
Newsgroups:
|
lugnet.robotics.rcx.nqc
|
Date:
|
Sat, 2 Oct 1999 06:24:04 GMT
|
Viewed:
|
2556 times
|
| |
|
|
Your proposed solution is susceptible to the "lockstep starvation" problem.
Lockstep starvation happens when two tasks try to get the lock at the same time
and execute the same code in lock step, like so:
task 1: lock |= 2;
task 2: lock |= 4;
task 1: if (lock == 2)
task 2: if (lock == 4)
task 1: lock &= ~2;
task 2: lock &= ~4;
task 1: while(lock);
task 2: while(lock);
task 1: lock |= 2;
task 2: lock |= 4;
task 1: if (lock == 2)
(etc...)
The official solution to the problem is to use a test-and-set primitive, but
the "practical workaround" I was taught was to insert a random delay somewhere
in the loop. You can also effectively solve the problem by having each task
delay a different, fixed amount of time. I'll show that method here.
Dave Baum's code, modified to fix lockstep starvation problem:
int lock;
#define TASK_BIT(task_num) (1 << task_num)
void acquire_lock(int task_num)
{
while(1)
{
// wait for lock to be clear
while(lock);
// try to own it
lock |= TASK_BIT(task_num);
// see if we own it
if (lock == TASK_BIT(task_num)) {
return;
} else {
lock &= ~TASK_BIT(task_num);
Sleep(task_num);
}
}
}
- Robert Munafo http://www.mrob.com/
LEGO: TC+++(8480) SW++ #+ S-- LS++ Hsp M+ A@ LM++ YB64m IC13
|
|
Message has 1 Reply:
 | | Re: NQC 2.0 and some math questions
|
| (...) You're right - I forgot the delay (that's what I get for typing code from memory). Yeah, 'test and set' is the best solution, but unfortunately the RCX doesn't have one. The bitflag stuff is a little ugly for my tastes, which is why NQC does (...) (25 years ago, 2-Oct-99, to lugnet.robotics.rcx.nqc)
|
Message is in Reply To:
| | Re: NQC 2.0 and some math questions
|
| (...) I'm going from memory here, so I may miss a detail... int lock; #define TASK_BIT(task_num) (1 << task_num) void acquire_lock(int task_num) { while(1) { // wait for lock to be clear while(lock); // try to own it lock |= TASK_BIT(task_num); // (...) (25 years ago, 2-Oct-99, to lugnet.robotics.rcx.nqc)
|
16 Messages in This Thread:
  
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
