semaphores (2)

semaphores (2)

Post by Arthur Rink » Tue, 12 May 1998 04:00:00



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:}

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

Quote:}

I thought that if every process handles the p- and v-operation correctly
(i.e. calling them), the semaphore value will eventually returns to its
initial value. So if the initial value was 2 and a few processes do some p-
and v-operations, the semaphore will at the end be 2 again. But, reading
further in the book I started to doubt if that was true. I found that when a
process makes a p-operation and ends up in the waiting queue, it decrements
the semaphore when it comes out the queue. Why it that?
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.

Greetz, Arthur

 
 
 

semaphores (2)

Post by Glenn Wes » Tue, 12 May 1998 04:00:00


[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'?

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:

> 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?

Sounds good to me.

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
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.
Quote:

> Greetz, Arthur


 
 
 

semaphores (2)

Post by Andrew Giert » Tue, 12 May 1998 04:00:00


 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/>

 
 
 

semaphores (2)

Post by John Hicki » Tue, 12 May 1998 04:00:00


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

There is a race between creating a semaphore and initializing it to some
positive number. If all you need is a binary semaphore, however, you can avoid
the race through the simple expedient of associating the 0 value with available
and the 1 value with busy. To acquire such a semaphore you must wait until its
value is 0 and then claim it with a SEM_UNDO.

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

 
 
 

semaphores (2)

Post by John Hicki » Tue, 12 May 1998 04:00:00


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

There is a race between creating a semaphore and initializing it to some
positive number. If all you need is a binary semaphore, however, you can avoid
the race through the simple expedient of associating the 0 value with available
and the 1 value with busy. To acquire such a semaphore you must wait until its
value is 0 and then claim it with a SEM_UNDO.

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

 
 
 

semaphores (2)

Post by Andrew Giert » Tue, 12 May 1998 04:00:00


 >> 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/>

 
 
 

semaphores (2)

Post by John Hicki » Tue, 12 May 1998 04:00:00


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

 
 
 

semaphores (2)

Post by W. Richard Steve » Tue, 12 May 1998 04:00:00


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?

When you create a new System V semaphore there is no guarantee whatsoever
as to the initial values of the actual semaphores themselves.  The Unix 98
(http://www.rdg.opengroup.org) spec says:

        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

 
 
 

semaphores (2)

Post by Arthur Rink » Wed, 13 May 1998 04:00:00




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?

yes, sem.h contains some definitions and includes sem_buf.h if i'm not
mistaken. b.t.w. i'm actually using linux so that could be somewhat
different. I didn't checked every file in the dir, but I used grep to check
the files. it didn't find what i was looking for.

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.

are you sure? if the array contains serveral structs and that last param
indicates the total number of structs in that array, then how do you
indicate an arbitrary struct of that array?
for example: the array contains 10 structs, so the last param is 10. how to
address struct number 5?

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.

Why do you say that? my book here talks about decrementing 'semval' by the
absolute value op 'sem_op', so i think they mean 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

smart to check the data type of semval...my book also says semval is always
positive...should have seen that :-(

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.

so if a process calls a v-operation a process in the waiting queue is
restarted AND the value of the semaphores is incremented?
So it's not (a) restarting a waiting proces or (b) incrementing the
semaphore?

grtz, arthur

 
 
 

semaphores (2)

Post by Arthur Rink » Wed, 13 May 1998 04:00:00




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

>SysV semaphores I presume.

yep.

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.

and there they were.

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.)

So after the semop() call all the operations defined in the sembuf struct
are "executed" on the appropriate semaphores? if so, is that used often?

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.

and only if there're no processes left in the queue, you have to increment?

grtz, arthur

 
 
 

semaphores (2)

Post by Phil Edwar » Wed, 13 May 1998 04:00:00



+ 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.

 
 
 

semaphores (2)

Post by W. Richard Steve » Wed, 13 May 1998 04:00:00


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.

Should be all.  Every "official" man page that I've found (X/Open, SVID,
etc.) says that sem_otime is initialized to 0.  I've also *never* found
a man page that explicitly says that the semaphore values are initialized
to anything when created.  I think some init the values to 0, but I sure
wouldn't count on that.

        Rich Stevens