Semaphores

Semaphores

• Semaphore is described by Dijkstra. Semaphore is a nonnegative integer variable that is used as a flag. Semaphore is an operating system abstract data type. It takes only integer value. Its used to solve critical section problem.

• Dijkstra introduced two operations (P and V) to operate on semaphore to solve process synchronization problem. A process calls the P operation when it wants to enter its critical section and calls V operation when it wants to exit its critical section. The P operation is called as wait operation and V operation is called as signal operation.

• A wait operation on a semaphore decease its value by one.

Waits: while S < 0

do loops;

S:= S-1;

• A signal operation increments its value:

signal:

S:= S+ 1;

• A proper semaphore implementation requires that P and V be indivisible operations. A semaphore operation is atomic. This may be possible by taking hardware support. The operation P and V are executed by the operating system in response to calls issued by any one process naming a semaphore as parameter.

• There is no guarantee that no two processes can execute wait and signal operations on the same semaphore at the same time.

Properties of semaphore:

1. Semaphores are machine independent.

2. Semaphores are simple to implement.

3. Correctness is easy to determine.

4. Semaphore acquire many resources simultaneously.

5. Can have many different critical sections with different semaphores.

Binary Semaphore

• Binary semaphore is also known as mutex locks. It deals with the critical section for multiple processes.

• Binary semaphore value is only between 0 and 1.

Counting semaphore

• Used with that resource which has a finite number of instances.

• It works over unrestricted domain.

• Nonbinary semaphore often referred to as either a counting semaphore or a general semaphore.

• Process waiting for semaphore is stored in the queue for binary and counting semaphore. Queue uses first in first out policy.

• A semaphore that does not specify the order in which processes are removed from the queue is called as weak semaphore. The process that has been blocked the longest is released from the queue first is called a strong semaphore.

• Semaphore can be implemented in user applications and in the kernel. Both operations can be implemented in the kernel by blocking waiting process to avoid busy waiting.

Busy Waiting

• Busy waiting is a situation in which a process is blocked on a resource but does not yield the processor. A busy wait keeps the CPU busy in executing a process even as the process does nothing.

• Busy waiting is also called as spin waiting.

Busy waiting waste CPU cycles that some other process might be able to use productively.

• To avoid busy waiting, a process waiting for critical section, they put into the blocked state. When process allowed entering into critical section, then process is kept in ready state.

• To overcome the need for bust waiting:

In wait() operation :

a. When process reads semaphore value and it is not positive value then process blocked itself for some time.

b. Semaphore keeps all blocked process in the waiting queue so process is kept in this queue,

c. CPU scheduler selects another process for execution.

In signal () operation :

a. The wakup () operation is used for restating the blocked processes. When any other process executes signal () operation, then blocked process state changed from blocked state to ready state.

b. This process is kept in the ready queue.

Drawbacks of Semaphore

1. They are essentially shared global variables.

2. Access to semaphores can come from anywhere in a program.

3. There is no control or guarantee of proper usage.

4. There is no linguistic connection between the semaphore and the data to which most have the semaphore controls access.

5. They serve two purposes, mutual exclusion and scheduling constraints.

Semaphore Programming

1. Semget( )

• To create a semaphore or gain access to one that exists, the semget system call is used.

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/sem.h>

int semget (key t key,intnsems, int semflg);

• The semget system call takes three arguments :

  a. The first argument, key, is used by the system to generate a unique semaphore identifier.

  b. The second argument, nsems, is the number of semaphores in the set.

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

• When a semaphore is first created, the kernel assigns to it an associated :

a. Semaphore Control Block (SCB),

b. A unique ID,

c. A value (binary or a count), and

d. A task waiting list

• A Kernel can support many different types of semaphores, including binary, counting, and mutual-exclusion (mutex) semaphores.

2. semctl () function

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

• The function prototype is as follows:

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/sem.h>

int semctl(int semid, int semnum, int cmd, union semunarg);

• The semctl system call takes four arguments :

1. The first argument, semid is a valid semaphore identifier that was returned by a previous semget system call.

2. The second argument, semnum, is the number of semaphores in the semaphore set (array), 0 means this number (index) is not relevant.

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

4. The fourth argument to semctl, arg, is a union of type semun. Given the action specified by the preceding cmd argument, the data in arg can be one of of any the following four values:

a. An integer already was set in the val member of sem_union that used with SETVAL to indicate a change of specific value for a particular semaphore within the semaphore set.

b. A reference to a semid_ds structure where information is returned when IPC_STAT or IPC_SET is specified.

c. A reference to an array of type unsigned short integers; the array is used either to initialize the semaphore set or as a return location when specifying GETALL.

d. A reference to a seminfo structure when IPC_INFO is requested.

• If semctl fails, it returns a value of 1 and sets errno to indicate the specific error.

3. semop() function

Additional operations on individual semaphores are accomplished by using the semop system call. Its syntax is :

#include <sys/types.h> 

#include <sys/ipc.h>

#include <sys/sem.h>

int semop(int semid, struct sembuf *sops, unsigned nsops); for.

• The semop system call takes three arguments

a .The first argument, semid, is a valid semaphore identifier that was returned by a previous successful semget system call.

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

c. The third argument, nsops, is the number of elements in the array of semaphore operations.

• If semop fails, it returns a value of - 1 and sets errno to indicate the specific error. • If a semop call must block after completing some of its component operations, the kernel rewinds the operation to the beginning to ensure atomicity of the entire call.

• 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 a semaphore value is to be modified, the accessing process must have altered permission for the semaphore set.

• When the sem_op value is positive, the process is adding to the semaphore value. Os The addition is used to record the return (release) of the resource affiliated with the semaphore.

• Again, when a semaphore value is to be modified, the accessing process must have alter permission for the semaphore set.

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

4. sem_post()

Syntax :

#include <semaphore.h>

int sem_post(sem_t *sem);

• The sem_post() function unlocks the specified semaphore by performing a semaphore unlock operation on that semaphore. When this operation results in a positive semaphore value, no threads were blocked waiting for the semaphore to be unlocked; the semaphore value is simply incremented.

• When this operation results in a semaphore value of zero, one of the threads waiting for the semaphore is allowed to return successfully from its invocation of the sem_wait() function. The sem_post() interface is reentrant with respect to signals and may be invoked from a signal-catching function.

5. sem_init()

Syntax :

#include <semaphore.h>

• int sem_init(sem_t *sem, int pshared, unsigned int value);

The sem_init() function is used to initialize the semaphore's value. The pshared argument must be 0 for semaphores local to a process. The value argument specifies the initial value for the semaphore.

• The pshared argument indicates whether this semaphore is to be shared between the threads of a process, or between processes.

• If pshared has the value 0, then the semaphore is shared between the threads of a process, and should be located at some address that is visible to all threads.

• If pshared is nonzero, then the semaphore is shared between processes, and should be located in a region of shared memory.