Gui application for embedded system

On 23/07/14 05:40, Randy Yates wrote:
> George Neuner <gneuner2@comcast.net> writes:
> 
> ...<a lot of stuff about synchronization>...
> 
> Can someone PLEASE explain to me, REALLY, the difference between a mutex
> and a binary semaphore? In the FreeRTOS implementation, the only
> difference I can see is the potential "priority elevation" thingie.
> 

The key issue is that a mutex has an owner, while a semaphore is just a
counter (usually with a limit - binary semaphores have a limit of 1).

Having an owner means more overhead and higher costs, but also more
flexibility - such as for priority elevation, and ensuring that only the
owner can release the mutex.  Semaphores are simpler, and can often be
implemented by single atomic operations or by a short section with
disabled interrupts (depending on the hardware).  It is common to use
semaphores to implement higher-level structures such as mutexes or queues.

> Also, the difference is in how it is used. A semaphore starts out
> unposted and blocks until a post event occurs. A mutex starts out
> "available," then some task takes the token (making it unavailable),
> does its thing, and then returns the token (making it available again).
> 
> So usage of a semaphore requires one access per event, while usage of a
> mutex requires two accesses per <protected resource usage>.
> 
> Is this right?
> 
> So is that it??!?
> 

On 7/22/14, 11:40 PM, Randy Yates wrote:
> George Neuner <gneuner2@comcast.net> writes:
>
> ...<a lot of stuff about synchronization>...
>
> Can someone PLEASE explain to me, REALLY, the difference between a mutex
> and a binary semaphore? In the FreeRTOS implementation, the only
> difference I can see is the potential "priority elevation" thingie.
>
> Also, the difference is in how it is used. A semaphore starts out
> unposted and blocks until a post event occurs. A mutex starts out
> "available," then some task takes the token (making it unavailable),
> does its thing, and then returns the token (making it available again).
>
> So usage of a semaphore requires one access per event, while usage of a
> mutex requires two accesses per <protected resource usage>.
>
> Is this right?
>
> So is that it??!?
>

A mutex is very much a specialized kind of semaphore, and due to that 
specialization works a bit different. This specialization is for 
protecting something from access by two tasks.

A Mutex's state is either it is owned by a particular task (which then 
has the right to access the thing being protected), or is free. A mutex 
will generally start in the "free" state, will be acquired by a task 
needing to access the resource, and then when the access is done, will 
be released by the task going back into the free state. Due to the fact 
that Mutex can know who "owns" it, it is possible that when a higher 
priority task tries to get a Mutex that is currently owned by a lower 
priority task, that the system can take action (like raise the priority 
of the owning task) to get the Mutex to the higher priority task 
quicker. Note also that only the task that "owns" the Mutex is supposed 
to give it back, and sometimes this will be enforced.

A Semaphore on the other hand is a more general type of primitive. In 
general, it it counts how many times it has been "Given", and allows 
that many "Takes" to occur. Sometimes blocking if too many gives have 
been done, and generally blocking if you try to take when there hasn't 
been a matching give already. A Binary Semaphore, is basically just a 
special case of the "Counting" Semaphore with an upper limit of 1. Note 
that for a semaphore, the giver and taker do not need to be the same 
task, and in fact generally aren't. The givers being the "Producer" of 
something and the takers being the "Consumers", and the semaphore being 
a control over the availability of the thing.

A Semaphore CAN act mostly like a Mutex if used in a similar way, the 
semaphore initialized to say there is a single resource available, and a 
task wanting exclusive access will "consume" that resource, work with 
it, then "produce" it back to the semaphore so someone else can use it. 
(this is why binary semaphores are sometimes initialized as "full", 
while more generic counting semaphores tend to start "empty"). The major 
limitation of this over a Mutex is that since semaphores aren't "owned" 
by their consumer, you don't get the ability to do something special 
like priority inheritance if a higher priority task tries to take the 
semaphore when it is already empty.

On 2014-07-23, Paul Rubin <no.email@nospam.invalid> wrote:
> Randy Yates <yates@digitalsignallabs.com> writes:
>> Can someone PLEASE explain to me, REALLY, the difference between a mutex
>> and a binary semaphore? In the FreeRTOS implementation, the only
>> difference I can see is the potential "priority elevation" thingie.
>
> Usually a mutex is in one of two states: either owned by some process
> (therefore locked), or else unlocked (so any proces can acquire it).  In
> other words it's a one-bit value indicating whether you have ownership
> of a resource.
>
> A semaphore on the other hand contains an integer rather than a bit,

If it's a counting semaphore (the kind Dijkstra talked about).  There
are also binary semaphores.

-- 
Grant Edwards               grant.b.edwards        Yow! ... bleakness
                                  at               ... desolation ... plastic
                              gmail.com            forks ...

Randy Yates wrote:
> Can someone PLEASE explain to me, REALLY, the difference between a mutex
> and a binary semaphore? In the FreeRTOS implementation, the only
> difference I can see is the potential "priority elevation" thingie.
> 
> Also, the difference is in how it is used. A semaphore starts out
> unposted and blocks until a post event occurs. A mutex starts out
> "available," then some task takes the token (making it unavailable),
> does its thing, and then returns the token (making it available again).

There isn't necessarily a difference between a mutex and a binary
semaphore. In INTEGRITY, the binary semaphore *is* what everyone calls a
mutex.

To me, key properties of a mutex are:
- it starts "available"
- someone can take it, and later bring it back.
- you cannot bring back a mutex you do not own.
- bonus points for being recursive (i.e. if I already have it, I can
  take it again, and must the bring it back twice).
- bonus points for priority inheritance.
- ideal for implementing critical sections.

Key properties of a semaphore are:
- it's a counter starting at an arbitrary value.
- anyone can count it up, anyone can count it down. Counting below
  zero makes you block.
- ideal for managing queues.

Some people (namely the INTEGRITY guys) define a binary semaphore as a
recursive, priority-inheriting mutex.

Some other people define a binary semaphore as a simple semaphore that
just cannot count farther up than one. Such a semaphore can be used to
build a non-recursive, non-priority-inheriting mutex, or it can be used
to implement a wakeup event (where multiple signals should result in
only one actual wakeup).


  Stefan

Richard Damon <Richard@Damon-Family.org> writes:

> On 7/22/14, 11:40 PM, Randy Yates wrote:
>> George Neuner <gneuner2@comcast.net> writes:
>>
>> ...<a lot of stuff about synchronization>...
>>
>> Can someone PLEASE explain to me, REALLY, the difference between a mutex
>> and a binary semaphore? In the FreeRTOS implementation, the only
>> difference I can see is the potential "priority elevation" thingie.
>>
>> Also, the difference is in how it is used. A semaphore starts out
>> unposted and blocks until a post event occurs. A mutex starts out
>> "available," then some task takes the token (making it unavailable),
>> does its thing, and then returns the token (making it available again).
>>
>> So usage of a semaphore requires one access per event, while usage of a
>> mutex requires two accesses per <protected resource usage>.
>>
>> Is this right?
>>
>> So is that it??!?
>>
>
> A mutex is very much a specialized kind of semaphore, and due to that
> specialization works a bit different. This specialization is for
> protecting something from access by two tasks.
>
> A Mutex's state is either it is owned by a particular task (which then
> has the right to access the thing being protected), or is free. A
> mutex will generally start in the "free" state, will be acquired by a
> task needing to access the resource, and then when the access is done,
> will be released by the task going back into the free state. Due to
> the fact that Mutex can know who "owns" it, it is possible that when a
> higher priority task tries to get a Mutex that is currently owned by a
> lower priority task, that the system can take action (like raise the
> priority of the owning task) to get the Mutex to the higher priority
> task quicker. Note also that only the task that "owns" the Mutex is
> supposed to give it back, and sometimes this will be enforced.
>
> A Semaphore on the other hand is a more general type of primitive. In
> general, it it counts how many times it has been "Given", and allows
> that many "Takes" to occur. Sometimes blocking if too many gives have
> been done, and generally blocking if you try to take when there hasn't
> been a matching give already. A Binary Semaphore, is basically just a
> special case of the "Counting" Semaphore with an upper limit of 1.
> Note that for a semaphore, the giver and taker do not need to be the
> same task, and in fact generally aren't. The givers being the
> "Producer" of something and the takers being the "Consumers", and the
> semaphore being a control over the availability of the thing.
>
> A Semaphore CAN act mostly like a Mutex if used in a similar way, the
> semaphore initialized to say there is a single resource available, and
> a task wanting exclusive access will "consume" that resource, work
> with it, then "produce" it back to the semaphore so someone else can
> use it. (this is why binary semaphores are sometimes initialized as
> "full", while more generic counting semaphores tend to start "empty").
> The major limitation of this over a Mutex is that since semaphores
> aren't "owned" by their consumer, you don't get the ability to do
> something special like priority inheritance if a higher priority task
> tries to take the semaphore when it is already empty.

Thank you all for your input - very educational! Richard, I especially
appreciately your response.
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

Randy Yates <yates@digitalsignallabs.com> writes:
> [...]
> Richard, I especially appreciately ...

??? _appreciated_
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

Randy Yates wrote:
> George Neuner <gneuner2@comcast.net> writes:
>
> ...<a lot of stuff about synchronization>...
>
> Can someone PLEASE explain to me, REALLY, the difference between a mutex
> and a binary semaphore? In the FreeRTOS implementation, the only
> difference I can see is the potential "priority elevation" thingie.
>

It'll vary. The canonical { P(),V() } as per Knuth is the mutex/binary 
semaphore.

There are several heresies on this theme.

> Also, the difference is in how it is used. A semaphore starts out
> unposted and blocks until a post event occurs. A mutex starts out
> "available," then some task takes the token (making it unavailable),
> does its thing, and then returns the token (making it available again).
>

I would not be surprised if you could initialize either either way. 
VxWorks has a sempahore object that you can initialize to a value
so that <n> threads can do their initialization, then block on it.



> So usage of a semaphore requires one access per event, while usage of a
> mutex requires two accesses per <protected resource usage>.
>
> Is this right?
>

It is whatever the implementers say is right.

> So is that it??!?
>

-- 
Les Cargill

Les Cargill wrote:
<snip>
> It'll vary. The canonical { P(),V() } as per Knuth is the mutex/binary
> semaphore.
Edit: It was Djikstra and the default was counting semaphores.

-- 
Les Cargill

Hi Randy,

On Tue, 22 Jul 2014 23:40:07 -0400, Randy Yates
<yates@digitalsignallabs.com> wrote:

>Can someone PLEASE explain to me, REALLY, the difference between a mutex
>and a binary semaphore? 

When you are speaking strictly about _binary_ semaphores, the
difference essentially is the use case.  

A general semaphore *conceptually* is simply a pairing of a binary
semaphore with a counter.


The "environment awareness" properties that people often associate
with synchronization primitives really are tangential to their basic
function of resource locking.

E.g., the notion that a "mutex" has an owner fell out of early
algorithmic locking schemes which had to work without the aid of
atomic RMW instructions [e.g., compare/swap, test/set, interlocked
inc/dec, etc.] that commonly are found on modern CPUs.  
See:
  https://en.wikipedia.org/wiki/Dekker%27s_algorithm
  https://en.wikipedia.org/wiki/Peterson%27s_algorithm
  https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm

In use, it isn't necessary for a mutex to have an explicit owner: the
owner is implicit in the states of the competing tasks.  If you look
at the algorithms above, you'll see that, at least as written, the
identity of the current "owner" is known only implicitly by the
participants.  
[Obviously, an external observer or a participant in busy-wait could,
in principle, examine the shared state and identify the owner, but
that is extraneous to the algorithm(s).]

However, external identification of the owner enables other useful
concepts such as priority awareness, deadlock detection, etc. to be
layered on top of the basic synchronization.


It has been proven that all so-far discovered synchronization
"primitives" are equivalent and that they all can be implemented in
terms of one other.  

Hope this helps,
George

George Neuner wrote:
> Hi Randy,
<snip>
>
> It has been proven that all so-far discovered synchronization
> "primitives" are equivalent and that they all can be implemented in
> terms of one other.
>

Well said - which is one reason I don't even try to remember the fine 
points of them any more. Next time is always different.

> Hope this helps,
> George
>

-- 
Les Cargill