Very Computer

Since there was no answer to this msg in comp.os.linux.developer.app I just
try it in here.

Hi, I have a few questions about semaphores.

First question: I want to know what layout the structs 'sem', 'sem_queue'
and 'sem_undo' have, but I can't them in any .h-file (/usr/include/*) and
what's the function of struct 'sem_queue'?

Second question: about the semop() call; the 2nd parameter is a pointer to
an array of 'sembuf'-s, while the last parameter is an int. Am I correct in
saying that the last param. selects a 'sembuf' out of the array and that
each 'sembuf' contains some sort of presetting operation?

Third question: maybe simple, but I have to know for sure; it's about the
semctl() call. If you use the command GETALL or SETALL, then the last
argument of this call is a pointer to an array which contains or will
contain the values of the semaphores. I assume this array must be as large
as there are semaphores in the set. So 2 semaphores in a set, means an array
of 2 elements. Correct?

Fourth and most important question: in my study book of IPC the following
pseudo code for p- and v-operations is mentioned:

p(sem)
{
        if (sem != 0)
                decrement sem by one
        else
                wait until sem becomes non-zero

Quote:}

Quote:}

Greetz, Arthur

[snipped]

Quote:> First question: I want to know what layout the structs 'sem', 'sem_queue'
> and 'sem_undo' have, but I can't them in any .h-file (/usr/include/*) and
> what's the function of struct 'sem_queue'?

Quote:

> Second question: about the semop() call; the 2nd parameter is a pointer to
> an array of 'sembuf'-s, while the last parameter is an int. Am I correct in
> saying that the last param. selects a 'sembuf' out of the array and that
> each 'sembuf' contains some sort of presetting operation?

Quote:

> Third question: maybe simple, but I have to know for sure; it's about the
> semctl() call. If you use the command GETALL or SETALL, then the last
> argument of this call is a pointer to an array which contains or will
> contain the values of the semaphores. I assume this array must be as large
> as there are semaphores in the set. So 2 semaphores in a set, means an array
> of 2 elements. Correct?

Quote:

> Fourth and most important question: in my study book of IPC the following
> pseudo code for p- and v-operations is mentioned:

I think the value that gets decremented is semncnt which is the number
of processes waiting on the semaphore, NOT the value of the semaphore.

Quote:> And what's the goal of waiting until the semaphore becomes 0 with semop(). I
> mean, if p-operations decrement the semaphore it may get smaller than 0.  If
> not all v-operations compensate/increment the semaphore, the semaphore could
> grow more negative and testing for 0 will always fail.

Quote:

> Greetz, Arthur

 Arthur> Since there was no answer to this msg in
 Arthur> comp.os.linux.developer.app I just try it in here.

 Arthur> Hi, I have a few questions about semaphores.

SysV semaphores I presume.

 Arthur> First question: I want to know what layout the structs 'sem',
 Arthur> 'sem_queue' and 'sem_undo' have, but I can't them in any
 Arthur> .h-file (/usr/include/*) and what's the function of struct
 Arthur> 'sem_queue'?

Those structures are part of the internal implementation; they are not
necessarily visible or useful from user-space. If they aren't defined
in /usr/include/sys/*, then look in your kernel sources.

 Arthur> Second question: about the semop() call; the 2nd parameter is
 Arthur> a pointer to an array of 'sembuf'-s, while the last parameter
 Arthur> is an int. Am I correct in saying that the last
 Arthur> param. selects a 'sembuf' out of the array and that each
 Arthur> 'sembuf' contains some sort of presetting operation?

You are incorrect.

The second parameter is indeed a pointer to an array of sembufs, each
defining an operation to perform. The third parameter is the number of
sembufs in the array.

The call to semop() attempts to perform *all* the specified
operations, atomically. (i.e. if it blocks, it will do so in a state
where *none* of the operations have yet been performed, and it will
either return success with all operations carried out, or failure with
none of them performed.)

 Arthur> Third question: maybe simple, but I have to know for sure;
 Arthur> it's about the semctl() call. If you use the command GETALL
 Arthur> or SETALL, then the last argument of this call is a pointer
 Arthur> to an array which contains or will contain the values of the
 Arthur> semaphores. I assume this array must be as large as there are
 Arthur> semaphores in the set. So 2 semaphores in a set, means an
 Arthur> array of 2 elements. Correct?

Yes.

 Arthur> Fourth and most important question: in my study book of IPC
 Arthur> the following pseudo code for p- and v-operations is
 Arthur> mentioned:

 Arthur> p(sem)
 Arthur> {
 Arthur>     if (sem != 0)
 Arthur>             decrement sem by one
 Arthur>     else
 Arthur>             wait until sem becomes non-zero
 Arthur> }

This description is incomplete

 Arthur> v(sem)
 Arthur> {
 Arthur>     if(queue of waiting processes not empty)
 Arthur>             restart first process in wait queue
 Arthur>     else
 Arthur>             increment sem by one
 Arthur> }

as is this; if p() is going to "wait until sem becomes non-zero", then
v() must increment the value before waking up the waiting process (else
the value will still be 0), and p() must decrement the value again after
waking up.

The alternative implementation is for p() to "wait until restarted by v()",
in which case the transfer of ownership, so to speak, can be performed
without actually incrementing and decrementing the value.

 Arthur> And what's the goal of waiting until the semaphore becomes 0
 Arthur> with semop().

Never found a use for that, personally.

 Arthur> I mean, if p-operations decrement the semaphore it may get
 Arthur> smaller than 0.

No. Not possible. Any attempt to decrement the value below 0 will block.

 Arthur> If not all v-operations compensate/increment the semaphore,
 Arthur> the semaphore could grow more negative and testing for 0 will
 Arthur> always fail.

With SysV semaphores, then the implementation of P() is a single semop
call to decrement the semaphore value. The implementation of V() is a
corresponding call to increment it. The behaviour of semop provides the
wait/restart behaviour (note that many implementations do not attempt to
queue processes waiting on a semaphore; there is usually no mechanism to
prevent starvation).

--
Andrew.

comp.unix.programmer FAQ: see <URL: http://www.erlenstar.demon.co.uk/unix/>
                           or <URL: http://www.whitefang.com/unix/>

Quote:>And what's the goal of waiting until the semaphore becomes 0 with semop().

Avoiding the race with a general purpose semaphore requires the caller to first
acquire a binary semaphore built as above.

--
John D. Hickin      Nortel Technology, Montreal, Quebec

Quote:>And what's the goal of waiting until the semaphore becomes 0 with semop().

Avoiding the race with a general purpose semaphore requires the caller to first
acquire a binary semaphore built as above.

--
John D. Hickin      Nortel Technology, Montreal, Quebec

 >> And what's the goal of waiting until the semaphore becomes 0 with
 >> semop().

 John> There is a race between creating a semaphore and initializing
 John> it to some positive number.

No.

With SysV semaphores, there's a race between creating the semaphore
and initialising it with *ANY* value -- the state of a newly-created
SysV semaphore is *not defined*.

 John> If all you need is a binary semaphore, however, you can avoid
 John> the race through the simple expedient of associating the 0
 John> value with available and the 1 value with busy. To acquire such
 John> a semaphore you must wait until its value is 0 and then claim
 John> it with a SEM_UNDO.

You should not do this. The correct implementation of a binary semaphore
using SysV semaphores is to regard 0 as "busy" and 1 as "available". To
acquire, decrement the semaphore (with SEM_UNDO if you wish it to be
released automatically on process termination). To release, increment it.

 John> Avoiding the race with a general purpose semaphore requires the
 John> caller to first acquire a binary semaphore built as above.

Not so, because there is no guarantee that any SysV semaphore will be
initialised to 0.

There are two good solutions to this problem that I know of:

  - ensure that creation and initialisation of the semaphore(s) is
    performed by a specific process, and that other processes do not
    access the semaphores until they have been initialised. This is the
    method I've tended to use in the past.

  - (a method I got from Rich Stevens) use the sem_otime value to detect
    uninitialised semaphores.

--
Andrew.

comp.unix.programmer FAQ: see <URL: http://www.erlenstar.demon.co.uk/unix/>
                           or <URL: http://www.whitefang.com/unix/>

Ouch! I have to agree.

I'm interested in Stevens' method; could you please elaborate? Is there not
still a race in any test of the sem_otime value?

--
John D. Hickin      Nortel Technology, Montreal, Quebec

Quote:> I'm interested in Stevens' method; could you please elaborate? Is there not
> still a race in any test of the sem_otime value?

        The variable sem_otime is set equal to 0 and sem_ctime is set
        equal to the current time.

        The data structure associated with each semaphore in the set is
        not initialized.  The semctl() function with the command SETVAL
        or SETALL can be used to initialize each semaphore.

So if you have a scenario where multiple processes can create the same
semaphore at about the same time, specify IPC_CREAT | IPC_EXCL and the
first one that succeeds in the creation does the SETVAL followed by a
semop().  You are guaranteed that the CREAT | EXCL test is atomic and
that semop() will set sem_otime nonzero.  The processes that get EEXIST
call semget() again without IPC_CREAT | IPC_EXCL (since they know it
already exists) and then call semctl() in a loop, waiting for sem_otime
to be nonzero.  If it's still 0, just sleep for some small amount of
time, waiting for the single creator to finish its semop().

This is documented in detail in the forthcoming "Unix Network Programming,
Volume 2, IPC: Interprocess Communication" (available around July).

        Rich Stevens

Quote:>> First question: I want to know what layout the structs 'sem', 'sem_queue'
>> and 'sem_undo' have, but I can't them in any .h-file (/usr/include/*) and
>> what's the function of struct 'sem_queue'?

>Did you look in /usr/include/sys/sem.h for struct sem and struct
>sem_undo?

Quote:>> Second question: about the semop() call; the 2nd parameter is a pointer to
>> an array of 'sembuf'-s, while the last parameter is an int. Am I correct in
>> saying that the last param. selects a 'sembuf' out of the array and that
>> each 'sembuf' contains some sort of presetting operation?

>Don't think so.  The last param indicates the number of elements in the
>array of struct sembufs.  Since we didn't mark the end of the array, we
>have to tell semop where the end is lest we walk off the end of the
>array.  sembuf contains the semaphore number, the operation and the
>NOWAIT/UNDO flag.

Quote:>> Fourth and most important question: in my study book of IPC the following
>> pseudo code for p- and v-operations is mentioned:
>[snipped]

>I think the value that gets decremented is semncnt which is the number
>of processes waiting on the semaphore, NOT the value of the semaphore.

Quote:>> And what's the goal of waiting until the semaphore becomes 0 with semop(). I
>> mean, if p-operations decrement the semaphore it may get smaller than 0.  If
>> not all v-operations compensate/increment the semaphore, the semaphore could
>> grow more negative and testing for 0 will always fail.

>The idea behind the value of a semaphore is that you gain control by
>decrementing the value and you give up the resource by incrementing.
>The value can never go below zero (when you find struct sem you'll
>notice that semval is an unsigned short).  If you want to gain the

Quote:>resource, you set sem_op in struct sembuf to a negative value.  If there
>are no resources available (value is zero or less than the absolute
>value of sem_op) you either wait or don't.  If you wait, when the value
>of the semaphore rises such that the value can be decremented without
>going negative, your process continues.

grtz, arthur

Quote:> Arthur> Hi, I have a few questions about semaphores.

>SysV semaphores I presume.

Quote:> Arthur> First question: I want to know what layout the structs 'sem',
> Arthur> 'sem_queue' and 'sem_undo' have, but I can't them in any
> Arthur> .h-file (/usr/include/*) and what's the function of struct
> Arthur> 'sem_queue'?

>Those structures are part of the internal implementation; they are not
>necessarily visible or useful from user-space. If they aren't defined
>in /usr/include/sys/*, then look in your kernel sources.

Quote:>The call to semop() attempts to perform *all* the specified
>operations, atomically. (i.e. if it blocks, it will do so in a state
>where *none* of the operations have yet been performed, and it will
>either return success with all operations carried out, or failure with
>none of them performed.)

Quote:> Arthur> p(sem)
> Arthur> {
> Arthur>         if (sem != 0)
> Arthur>                 decrement sem by one
> Arthur>         else
> Arthur>                 wait until sem becomes non-zero
> Arthur> }

>This description is incomplete

> Arthur> v(sem)
> Arthur> {
> Arthur>         if(queue of waiting processes not empty)
> Arthur>                 restart first process in wait queue
> Arthur>         else
> Arthur>                 increment sem by one
> Arthur> }

>The alternative implementation is for p() to "wait until restarted by v()",
>in which case the transfer of ownership, so to speak, can be performed
>without actually incrementing and decrementing the value.

grtz, arthur

+ Ouch! I have to agree.
+
+ I'm interested in Stevens' method; could you please elaborate? Is there not
+ still a race in any test of the sem_otime value?

I know of two methods, both from Stevens.

Newer Unixes are supposed to create brand new semaphores with a sem_otime of
zero.  If the creating process (specifying exclusive create in semget(2))
gets a good result, then it does the setup.  Any other process doing an
exclusive create will get an error; those then wait for sem_otime to be
something other than zero.  But I don't know how many existing, popular Unix
implementations actually do that.

The one I use is from Stevens' APUE, where a semaphore set of N semaphores
is actually a set of N+2 semaphores.  The two extra ones are a counting
semaphore and an internal-use-only mutex on the counter.  There can still be
a race condition under an interesting set of circumstances, but it's easy to
detect and fix (Stevens details all of this).  I wrote this method into a
set of C++ semaphore wrapper-ish classes (credit given, of course) and it
works well.

Luck++;
/dev/phil

=> If you post a followup, PLEASE don't email a copy to me.  I read news
    often enough that replying to things twice is annoying.  But thanks.

Quote:> Newer Unixes are supposed to create brand new semaphores with a sem_otime of
> zero.  If the creating process (specifying exclusive create in semget(2))
> gets a good result, then it does the setup.  Any other process doing an
> exclusive create will get an error; those then wait for sem_otime to be
> something other than zero.  But I don't know how many existing, popular Unix
> implementations actually do that.

        Rich Stevens