Semaphore Definition: Starvation

SEMAPHORES
Semaphore Definition
A semaphore is a data structure that is shared
by several processes. Semaphores are most
often used to synchronize operations (to avoid
race conditions) when multiple processes
access a common, non-shareable resource.
By using semaphores, we attempt to avoid other
multi-programming problems such as:
Starvation
Occurs when a process is habitually denied access to
a resource it needs.
Deadlock
Occurs when two or more processes each hold a
resource that the other needs while waiting for the
other process to release its resource.
1
SEMAPHORES
To indicate a process has gained access to the
resource, the process decrements the
semaphore.
For events to progress correctly, the test and
decrement operation on the semaphore must be
atomic (i.e., noninterruptible/indivisible).
There are two kinds of Semaphores:
Binary semaphores
Control access to a single resource, taking the value
of 0 (resource is in use) or 1 (resource is available).
Counting semaphores
Control access to multiple resources, thus assuming
a range of nonnegative values.
2
SEMAPHORES
Semaphore is a nonnegative integer that is
stored in the kernel.
Access to the semaphore is provided by a
series of semaphore system calls.
SEMAPHORES
Creating and Accessing

Semaphore Sets
Before a semaphore set can be used, it must be

created.
The creation of the semaphore set generates a
unique data structure that the system uses to
identify and manipulate the semaphores.
A conceptual arrangement of a system
semaphore structure for a newly allocated set of
three semaphores is shown in Figure.
UNIX kernel structures

struct sem
semval
sempid
semncnt
semznt
current value of the semaphore counter

pid of the most recent task to access it
counts tasks awaiting semval >= current
counts tasks awaiting semval == 0
A semaphore set
descriptor
struct sem array[ ]
nsems = 3
struct semid_ds
sem_perm
*sem_base
sem_nsems
sem_otime
sem_ctime
SEMAPHORES

Semaphore Sets
Figure 7.1. Data structures for a set of three semaphores.
SEMAPHORES

Semaphore Sets
To create a semaphore or gain access to one

that exists, the semget system call is used.
(Table 7.1)
SEMAPHORES

Semaphore Sets
2
Manual Section
sys/typ es.h > Include

<
File(s)
<sys/ip c.h >
<sys/sem .h >
int semget (key_t key, int nsems, int semflg);
Summary
Return
Sets errno
Failure
Success
Yes
1-
The semaphore identifier
Table 7.1. Summary of the semget System Call

9
SEMAPHORES

Semaphore Sets
The semget system call takes three arguments:

The first argument, key, is used by the system to
generate a unique semaphore identifier.
The second argument, nsems, is the number of
semaphores in the set.
The third argument, semflg, is used to specify
access permission and/or special creation
conditions.
If the semget system call fails, it returns a 1 and
sets the value stored in errno.
10
SEMAPHORES
Semaphore Control
The semctl system call allows the user to
perform a variety of generalized control
operations on the system semaphore structure,
on the semaphores as a set, and on individual
semaphores.
(Table 7.3)
11
SEMAPHORES
Semaphore Control
2
Manual Section

<
File(s)
<sys/ip c.h >
<sys/sem .h >
int semctl(int semid, int semnum, int cmd,
Summary
union semun arg);
Return
Sets errno
Failure
Success
Yes
1-
0 or the value requested
Table 7.3. Summary of the semctl System Call

12
SEMAPHORES
Semaphore Control
The semctl system call takes four arguments:
The first argument, semid, is a valid semaphore
identifier that was returned by a previous semget
system call.
The second argument, semnum, is the number of
semaphores in the semaphore set.
The third argument to semctl, cmd, is an integer
command value. the cmd value directs semctl to
take one of several control actions. Each action
requires specific access permissions to the
semaphore control structure.
13
SEMAPHORES
Semaphore Control
The fourth argument to semctl, arg, is a union of
type semun.
The last set of semctl cmd values acts upon

individual semaphores or upon specific
members in the semid_ds structure. All of these
commands require read permission except for
SETVAL, which requires alter permission:
GETVAL
Return the current value of the individual semaphore
referenced by the value of the semnum argument.
SETVAL
Set the value of the individual semaphore referenced
by the semnum argument to the value specified by
the fourth argument to semctl.
14
SEMAPHORES
Semaphore Control Details

The definition of union semnum is
union semun
{
int val;
ushort *array;
struct semid_ds *buf
};
15
SEMAPHORES
Semaphore Operations
Additional operations on individual semaphores
are accomplished by using the semop system
call.
(Table 7.5.)
16
SEMAPHORES
2
Manual Section

<
File(s)
<sys/ip c.h >
<sys/sem .h >
int semop(int semid, struct sembuf *sops,
Summary
unsigned nsops);
Return
Sets errno
Failure
Success
Yes
1-
Table 7.5. Summary of the semop System Call

17
SEMAPHORES
The semop system call takes three arguments:
The first argument, semid, is a valid semaphore
identifier that was returned by a previous
successful semget system call.
The second argument, sops, is a reference to the
base address of an array of semaphore
operations that will be performed on the
semaphore set associated with by the semid
value.
The third argument, nsops, is the number of
elements in the array of semaphore operations.
18
SEMAPHORES
If semop fails, it returns a value of 1 and sets
errno to indicate the specific error.
array of semaphore operations
struct sembuf
{
unsignedshort sem_num;//which semaphore (0 ..
nsems-1)
short sem_op;
short sem_flg;
}
19
SEMAPHORES
Semaphore Operation Details

When the sem_op value is negative, the process
specifying the operation is attempting to
decrement the semaphore.
The decrement of the semaphore is used to
record the acquisition of the resource affiliated
with the semaphore.
When the sem_op value is positive, the process is
adding to the semaphore value. The addition is used to
record the return (release) of the resource affiliated with
the semaphore.
20
SEMAPHORES
Semaphore Operation Details

When the sem_op value is zero, the process is
testing the semaphore to determine if it is at 0.
When a semaphore is at 0, the testing process
can assume that all the resources affiliated with
the semaphore are currently allocated (in use).
21

Semaphore Definition: Starvation

Uploaded by

Copyright:

Available Formats

Semaphore Definition: Starvation

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Semaphore Definition: Starvation

Uploaded by

Copyright:

Available Formats

SEMAPHORES

Creating and Accessing

Before a semaphore set can be used, it must be

UNIX kernel structures

current value of the semaphore counter

Creating and Accessing

Figure 7.1. Data structures for a set of three semaphores.

Creating and Accessing

To create a semaphore or gain access to one

Creating and Accessing

sys/typ es.h > Include

The semaphore identifier

Table 7.1. Summary of the semget System Call

Creating and Accessing

The semget system call takes three arguments:

sys/typ es.h > Include

0 or the value requested

Table 7.3. Summary of the semctl System Call

The last set of semctl cmd values acts upon

Semaphore Control Details

sys/typ es.h > Include

Table 7.5. Summary of the semop System Call

Semaphore Operation Details

Semaphore Operation Details

You might also like