Locking from primitives
Xllo
A friend was asked a question in an interview.
Given atomic increment & decrement operations
how would one implement locking functions?
I tried various ways, but can't arrive at a working
solution.
Is this problem solvable? Are there any extra
operations one would need?
If not, can some one give me a solution or hints
about the direction in which I can attack the problem.
osmium
See what you can find on "deadly embrace" combined with other restrictive
words on google.
Ben Bacarisse
> Am a Beginner, so excuse if something is silly.
>
> A friend was asked a question in an interview.
> Given atomic increment & decrement operations
> how would one implement locking functions?
>
> I tried various ways, but can't arrive at a working
> solution.
>
> Is this problem solvable? Are there any extra
> operations one would need?
No other operations are needed.
In some sense questions like this are odd because there are famous
solutions[1] that require only atomic loads and stores, so such
questions are really: "In what way can atomic operation X simplify
the implementation of locking (particularly with N > 2 processes)?".
> If not, can some one give me a solution or hints
> about the direction in which I can attack the problem.
I am not good at hinting, but it may help to imagine you have atomic
functions:
int inc(int &var)
{
var = var + 1;
return var;
}
int dec(int &var)
{
var = var - 1;
return var;
}
and you are looking for a solution of this shape:
declare shared variables;
process P(int n)
{
while (1) {
code that allows only one instance of P to proceed;
/* critical section */
code that releases at most one waiting instance of P;
/* non-critical section */
}
}
for (int i = 0; i < N; i++)
start process P(i);
[1] Dekker, Perterson and Lamport are the three best known.
http://en.wikipedia.org/wiki/Mutual_exclusion has links to all three.
--
Ben.
Joe Seigh
http://groups.google.com/group/comp.programming/msg/9e1c24e9d891dcd4?hl=en&
or here in slightly different form
http://groups.google.com/group/comp.unix.programmer/msg/212c43216ba3e2b4?hl=en&
You don't need a decrement operation. If you just need
mutual exclusion it's trivial and a lot simpler. Just
your basic bakery algorithm, you know the "take a number
and wait".
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
MM
> Xllo wrote:
>> Am a Beginner, so excuse if something is silly.
>>
>> A friend was asked a question in an interview.
>> Given atomic increment & decrement operations
>> how would one implement locking functions?
>>
>> I tried various ways, but can't arrive at a working
>> solution.
>>
>> Is this problem solvable? Are there any extra
>> operations one would need?
>>
>> If not, can some one give me a solution or hints
>> about the direction in which I can attack the problem.
>>
>>
> Try the fetch and increment version from here
> http://groups.google.com/group/comp.programming/msg/9e1c24e9d891dcd4?hl=en&
What are the functions fa & fi in the program?
CBFalconer
You need an increment/decrement that returns a condition code based
on the original (not the final) value.
if (increment(lock) was zero) gotit;
else {
decrement(lock); /* restore it */
/* dosomethingelse such as try again */;
}
This will usually require assembly code.
--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
Joe Seigh
> Joe Seigh wrote:
>>
>>Try the fetch and increment version from here
>>http://groups.google.com/group/comp.programming/msg/9e1c24e9d891dcd4?hl=en&
>
>
> What are the functions fa & fi in the program?
>
>
>>or here in slightly different form
>>http://groups.google.com/group/comp.unix.programmer/msg/212c43216ba3e2b4?hl=en&
>>
>>You don't need a decrement operation. If you just need
>>mutual exclusion it's trivial and a lot simpler. Just
>>your basic bakery algorithm, you know the "take a number
>>and wait".
>
fetch and add and fetch and increment. Atomically adds or increments
the target and returns the previous value.
int fi(int *x) { return *x++; } // atomic
If the atomic increment only returns the sign of the
result, you need to use a different algorithm involving
trying to sucessfully decrement an integer from 1 to 0.
If you succeed, you have the lock, otherwise increment
the integer and retry. To release the lock, increment
the integer. The integer (lock) is initialized to 1.
Or something like that.
Ben Bacarisse
> Xllo wrote:
>>
>> Am a Beginner, so excuse if something is silly.
>>
>> A friend was asked a question in an interview.
>> Given atomic increment & decrement operations
>> how would one implement locking functions?
>>
>> I tried various ways, but can't arrive at a working
>> solution.
>>
>> Is this problem solvable? Are there any extra
>> operations one would need?
>>
>> If not, can some one give me a solution or hints
>> about the direction in which I can attack the problem.
>
> You need an increment/decrement that returns a condition code based
> on the original (not the final) value.
Since the operation is atomic the final value is just as good. You
can infer the original value, with certainty, from the final one.
--
Ben.
CBFalconer
True enough. You can then have a lock with:
volatile int lock = 1;
....
/* returns non zero for success */
int acquire(volatile int *lock) {
int oldvalue;
if (0 < (oldvalue = *lock--)) *lock++;
return oldvalue;
}
/* probably needs a guard against misuse */
/* i.e. releasing an unacquired lock. */
void release(volatile int *lock) {
*lock++;
}
Assuming reasonable code generation. And there's the rub.
Volatile doesn't ensure that. Thus OSs or libraries usually supply
a suitable primitive written in assembly.
Arthur J. O'Dwyer
On Sun, 7 Jan 2007, CBFalconer wrote:
> Ben Bacarisse wrote:
>> CBFalconer <cbfal...@yahoo.com> writes:
>>> Xllo wrote:
>>>>
>>>> Am a Beginner, so excuse if something is silly.
>>>>
>>>> A friend was asked a question in an interview.
>>>> Given atomic increment & decrement operations
>>>> how would one implement locking functions?
>>>>
>>>> I tried various ways, but can't arrive at a working
>>>> solution.
>> Since the operation is atomic the final value is just as good.
>> You can infer the original value, with certainty, from the final
>> one.
>
> True enough. You can then have a lock with:
>
> volatile int lock = 1;
>
> ....
>
> /* returns non zero for success */
> int acquire(volatile int *lock) {
> int oldvalue;
>
> if (0 < (oldvalue = *lock--)) *lock++;
> return oldvalue;
> }
>
> /* probably needs a guard against misuse */
> /* i.e. releasing an unacquired lock. */
> void release(volatile int *lock) {
> *lock++;
> }
:( <-- disappointed smiley
You should know better than that, CBFalconer! Not only is the precedence
of your -- and * operators wrong, your code doesn't do anything like a
lock (i.e. --- I assume --- mutex). Your "acquire" function doesn't have
any way to block, so it can't possibly be implementing the "wait until
the lock is available" semantics the OP wants.
As someone else mentioned already, so I don't feel bad spoiling it,
the OP's problem could be solved with the "bakery algorithm":
volatile int take_a_number = 0;
volatile int now_serving = 0;
int acquire_lock() {
int my_number = take_a_number++;
while (my_number != now_serving) /* busy-wait */ ;
return;
}
int release_lock() {
now_serving++;
}
In a real mutex library, of course, you wouldn't necessarily busy-wait;
you'd use the current value of now_serving to figure out who has the lock,
and then yield to that thread. (Or something clever like that.)
HTH,
-Arthur
Ben Bacarisse
This example has the same idea behind it but I would be wary of
calling it "the" bakery algorithm. Lamport's original BA does not
require atomic increment -- in fact it is remarkable in that it does
not require *any* atomic operations. It is the only mutex algorithm I
know of that works when reads and writes can fail in truly spectacular
fashion[1]. Of course, the down side is that it is also much more
complex than the above.
Because of the problem of integer overflow, I suspect the OP's tutor
is expecting something more like:
Spoiler: scroll only if you want to...
int lock = 0;
void acquire_lock() {
while (inc(lock) != 1) dec(lock);
}
int release_lock() {
dec(lock);
}
such a solution will work even if the inc and dec operations only work
on quite narrow integer variables.
[1] As a result he (Lamport) would say that it is the first true
mutual exclusion algorithm.
--
Ben.
Joe Seigh
> This example has the same idea behind it but I would be wary of
> calling it "the" bakery algorithm. Lamport's original BA does not
> require atomic increment -- in fact it is remarkable in that it does
> not require *any* atomic operations. It is the only mutex algorithm I
> know of that works when reads and writes can fail in truly spectacular
> fashion[1]. Of course, the down side is that it is also much more
> complex than the above.
Bakeries were around and using the algorithm long before Lamport
was. Anyway Lamport's bakery algorihm, as it's called, is a distributed
algorithm and the OP specifically mentioned atomic increment and decrement
which makes it not a distributed algorithm problem.
>
> Because of the problem of integer overflow, I suspect the OP's tutor
> is expecting something more like:
>
Bakeries solved the problem of integer overflow also. It's a no
brainer if you ever went to a real bakery or delicatessen. All
the bakery algorithms I've done handle integer overflow (integer wrap
actually) as long as the number of waiters is less than the
integer range.
Ben Bacarisse
> Ben Bacarisse wrote:
>> This example has the same idea behind it but I would be wary of
>> calling it "the" bakery algorithm. Lamport's original BA does not
>> require atomic increment -- in fact it is remarkable in that it does
>> not require *any* atomic operations. It is the only mutex algorithm I
>> know of that works when reads and writes can fail in truly spectacular
>> fashion[1]. Of course, the down side is that it is also much more
>> complex than the above.
>
> Bakeries were around and using the algorithm long before Lamport
> was.
This strikes me as an odd remark to make. Tie-breakers were around
before Peterson and heaps pre-date Heap Sort. Algorithms are often
named after things they resemble. Are you suggesting that Lamport's
algorithm is trivial and/or obvious?
> Anyway Lamport's bakery algorihm, as it's called, is a distributed
> algorithm and the OP specifically mentioned atomic increment and decrement
> which makes it not a distributed algorithm problem.
Absolutely. That's why I was not suggesting it and, indeed, gently
arguing *against* using similarly inspired techniques.
Incidentally, Lamport did not invent the algorithm to solve a
distributed problem and his writings suggest that he became aware of
its more general application somewhat later.
>> Because of the problem of integer overflow, I suspect the OP's tutor
>> is expecting something more like:
>>
> Bakeries solved the problem of integer overflow also. It's a no
> brainer if you ever went to a real bakery or delicatessen. All
> the bakery algorithms I've done handle integer overflow (integer wrap
> actually) as long as the number of waiters is less than the
> integer range.
Since you call it a "no brainer" I suspect you are referring to some
method that is not the same as Lamport's or one that assumes some
higher-level atomic operations. Otherwise you'd refer readers to your
published paper!
--
Ben.
Joe Seigh
> Joe Seigh <jsei...@xemaps.com> writes:
>>Bakeries were around and using the algorithm long before Lamport
>>was.
>
>
> This strikes me as an odd remark to make. Tie-breakers were around
> before Peterson and heaps pre-date Heap Sort. Algorithms are often
> named after things they resemble. Are you suggesting that Lamport's
> algorithm is trivial and/or obvious?
You have an issue with using the term bakery algorithm to refer
to anything other than Lamport's bakery algorithm. How would
you characterize algorithms that use the same technique that
bakeries use to arbitrate service order? And why do you
persist in making the problem a distributed algorithms problem
when the OP clearly indicates it is not?
Joe Seigh
>
> If the atomic increment only returns the sign of the
> result, you need to use a different algorithm involving
> trying to sucessfully decrement an integer from 1 to 0.
> If you succeed, you have the lock, otherwise increment
> the integer and retry. To release the lock, increment
> the integer. The integer (lock) is initialized to 1.
> Or something like that.
>
void acquirelock(int *lock) {
do {
while (*lock != 1); // atomic
}
while (dec(lock) != 0);
}
void releaselock(int *lock) {
*lock = 1; // atomic
Ben Bacarisse
> Ben Bacarisse wrote:
>> Joe Seigh <jsei...@xemaps.com> writes:
>>>Bakeries were around and using the algorithm long before Lamport
>>>was.
>> This strikes me as an odd remark to make. Tie-breakers were around
>> before Peterson and heaps pre-date Heap Sort. Algorithms are often
>> named after things they resemble. Are you suggesting that Lamport's
>> algorithm is trivial and/or obvious?
>
> You have an issue with using the term bakery algorithm to refer
> to anything other than Lamport's bakery algorithm. How would
> you characterize algorithms that use the same technique that
> bakeries use to arbitrate service order?
I call them ticket algorithms, but that term is not universal. You
can call them whatever you like.
> And why do you
> persist in making the problem a distributed algorithms problem
> when the OP clearly indicates it is not?
I don't, and I cant see why you think I do. But no matter: I don't
think the OP needs or wants a distributed algorithm. I don't think
Lamport's Bakery Algorithm is the correct solution for the OP. Other
algorithms that use some form of numbered tickets might well be good
solutions for the OP.
I can't see how to make it any clearer. I even posted my proposed
solution which was not in the least suitable for a distributed system.
--
Ben.
Arthur J. O'Dwyer
On Sun, 7 Jan 2007, Ben Bacarisse wrote:
> "Arthur J. O'Dwyer" <ajon...@andrew.cmu.edu> writes:
>>
>> As someone else mentioned already, so I don't feel bad spoiling it,
>> the OP's problem could be solved with the "bakery algorithm":
>>
>> volatile int take_a_number = 0;
>> volatile int now_serving = 0;
>>
>> int acquire_lock() {
>> int my_number = take_a_number++;
>> while (my_number != now_serving) /* busy-wait */ ;
>> return;
>> }
>>
>> int release_lock() {
>> now_serving++;
>> }
>
> This example has the same idea behind it but I would be wary of
> calling it "the" bakery algorithm.
It's definitely "the" bakery algorithm. I didn't say it was "the"
bakery implementation. :) (There are plenty of other ways to implement
"take-a-number-and-wait", but "take-a-number-and-wait" is /the/ bakery
algorithm, AFAIC.)
> Because of the problem of integer overflow, I suspect the OP's tutor
> is expecting something more like:
[snip spoiler space]
>
> int lock = 0;
>
> void acquire_lock() {
> while (inc(lock) != 1) dec(lock);
> }
>
> int release_lock() {
> dec(lock);
> }
Here you're assuming an atomic "increment-and-test" instruction, which
the OP didn't specify. I think my implementation works even if all you
have is an atomic increment instruction. OTOH, yours fails if the sequence
of execution is
Thread A Thread B
lock=0
lock++ (lock=1)
lock++ (lock=2)
if (lock==1) (fails)
if (lock==1) (fails)
lock-- (lock=1)
lock-- (lock=0)
lock++ (lock=1)
lock++ (lock=2)
if (lock==1) (fails)
if (lock==1) (fails)
lock-- (lock=1)
lock-- (lock=0)
...
The problem with your algorithm is that it doesn't impose any order on
the contending threads. Whereas the bakery algorithm is
Take a number.
Wait until your number is called.
Be served.
the algorithm above is more like
Enter the bakery.
If you are the only person in the bakery, be served.
Otherwise, exit the bakery and return to step 1.
HTH,
-Arthur
Ben Bacarisse
> On Sun, 7 Jan 2007, Ben Bacarisse wrote:
>> "Arthur J. O'Dwyer" <ajon...@andrew.cmu.edu> writes:
>>>
>>> As someone else mentioned already, so I don't feel bad spoiling it,
>>> the OP's problem could be solved with the "bakery algorithm":
>>>
>>> volatile int take_a_number = 0;
>>> volatile int now_serving = 0;
>>>
>>> int acquire_lock() {
>>> int my_number = take_a_number++;
>>> while (my_number != now_serving) /* busy-wait */ ;
>>> return;
>>> }
>>>
>>> int release_lock() {
>>> now_serving++;
>>> }
>>
>> This example has the same idea behind it but I would be wary of
>> calling it "the" bakery algorithm.
>
> It's definitely "the" bakery algorithm. I didn't say it was "the"
> bakery implementation. :) (There are plenty of other ways to implement
> "take-a-number-and-wait", but "take-a-number-and-wait" is /the/ bakery
> algorithm, AFAIC.)
I don't want a name war. Use whatever terms you like (now that I know
how you are using them). I think Lamport would rather the term was
used only for his solution since it has properties not possessed by
other versions, but he is not here and I don't want to argue about
words.
>> Because of the problem of integer overflow, I suspect the OP's tutor
>> is expecting something more like:
> [snip spoiler space]
>>
>> int lock = 0;
>>
>> void acquire_lock() {
>> while (inc(lock) != 1) dec(lock);
>> }
>>
>> int release_lock() {
>> dec(lock);
>> }
>
> Here you're assuming an atomic "increment-and-test" instruction, which
> the OP didn't specify.
Yes. I though it likely that that was what was being asked. It was
just a guess from my experience of such questions (and the suggestive
inclusion of a decrement operation).
> I think my implementation works even if all you
> have is an atomic increment instruction.
It does indeed.
> OTOH, yours fails if the sequence
> of execution is
I take it you mean my code, modified to test lock separately -- when
there is no test included, just an increment instruction? I suggested
a solution based on an assumption that may have been unwarranted, but
it seems rather unfair to criticise code I did not write!
> Thread A Thread B
> lock=0
> lock++ (lock=1)
> lock++ (lock=2)
> if (lock==1) (fails)
> if (lock==1) (fails)
> lock-- (lock=1)
> lock-- (lock=0)
> lock++ (lock=1)
> lock++ (lock=2)
> if (lock==1) (fails)
> if (lock==1) (fails)
> lock-- (lock=1)
> lock-- (lock=0)
> ...
This sequence is not possible for the code I posted, but to cut a long
sequence of posts short, we won't know how to evaluate any proposed
solution unless the OP posts more details of the homework. Are
solution that require unbounded state OK? What are the "fairness"
requirements for the solution? Are probabilistic solutions allowed
(provided they are correct)?
BTW, I like ticket-based soltions like yours better than
endless-backoff ones like mine. I probably came over as too negative
in my post.
--
Ben.