Motivation for ‘and’ Syncronization‘and’ Syncronization‘and’ Syncronization ImplementationWhy Wake All Processes on Signal?POSIX:XSI SemaphoresPOSIX:SEM vs POSIX:XSI SemaphoresSemaphore SetsSemaphore Sets (Cont)Semaphore CreationIPC_PRIVATERandom KeyGenerate Key from ftoksemopstruct sembufsem_opset_sembuf_structSemaphore – Example 1struct sembuf – Example 1Semaphore – Ex 2 (Top)Semaphore – Ex 2 (Upper Middle)Semaphore – Ex 2 (Lower Middle)Semaphore – Ex 2 (Bottom)Semaphore – Example 3Slide 24semctlImportant Commandssemnum Paramaterinitialize _sem_elementremove_semaphoreCommand Prompt Semaphore Opssemop_restartsem_wait_restartMotivation for ‘and’ Syncronization*A = 1; *B = 1;Process 1 Process 2 Process 3wait(&A); wait(&A); wait(&B);<use resource A> wait(&B); <use resource B>signal(&A); <use resources A and B> signal(&B);signal(&B);signal(&A);‘and’ Syncronization*A = 1; *B = 1;Process 1 Process 2 Process 3wait(&A); wait(&A, &B); wait(&B);<use resource A> <use resources A and B> <use resource B>signal(&A); signal(&A, &B); signal(&B);wait(&A, &B) denotes simultaneous wait on A and B. The semaphores A and B are decremented only if both of them can decremented without blocking‘and’ Syncronization Implementationwait – if ((ap->value > 0) && (bp->value > 0)) { (ap->value)--; (bp->value)--; }else if (ap->value <= 0) <add current process to ap->list> else <add current process to bp->list> <block process and reset pc to beginning of wait>signal – ap->value++; <move all processes on ap->list to ready queue> bp->value++; <move all processes on bp->list to ready queue>Why Wake All Processes on Signal?Process 1 Process 2 Process 3a1: wait(&A,&B); a2: wait(&B,&C); a3: signal(&B,&C);b1: <critical section> b2: <critical section> c1: signal(&A,&B); c2: signal(&B,&C);Assume a1 is executed followed by a2, the semaphore queues are:A: process 1B: process 1, process 2C: process 2Then, if a3 is executed and the signal only wakes up the first process in each queue, the semaphore queues are:A: process 1B: process 2C:Now process 1 holds B while blocking on A. Process 2 cannot proceed until process 1 gets A. This defeats the purpose of ‘and’ synchronizationPOSIX:XSI Semaphores•POSIX:XSI semaphores are part of the general POSIX:XSI interprocess communication facility•A POSIX:XSI semaphore is created by executing a semget system call•The semget creats a semaphore data structure in the kernel and returns an integer handle to the semaphore•Processes cannot access semaphore data structures directly – only through system calls•Semaphore ids or handles are analogous to file descriptorsPOSIX:SEM vs POSIX:XSI Semaphores•POSIX:XSI data structures are created and kept in the kernel and are referenced through integer handles•In POSIX:SEM, a program declares a variable of type sem_t and passes a pointer to that variableSemaphore Sets•A semaphore set is an array of semaphore elements•A process can perform operations on the entire set in a single system call•The internal representation of semaphore sets and semaphore elements is not directly accessible•Each semaphore includes at least the following:–A nonnegative integer representing semaphore value–Process ID of the last process to manipulate the semaphore element–Number of processes waiting for the semaphore element to increase–Number of processes waiting for the semaphore element value to equal 0Semaphore Sets (Cont)•Semaphore operations allow a process to block until a semaphore element value is 0 or until it becomes positive•Each element has two queues associated with it – a queue of processes waiting for the semaphore element value to increase and a queue of processes waiting for the value to equal 0Semaphore CreationSYNOPSIS#include <sys/types.h>#include <sys/ipc.h>#include <sys/sem.h>int semget (key_t key, int nsems, int semflg);POSIX:XSIIPC_PRIVATE#include <stdio.h>#include <sys/stat.h>#include <sys/types.h>#include <sys/ipc.h>#include <sys/sem.h>#define PERMS S_IRUSR|S_IWUSR#define SET_SIZE 3int semid;void main(void){ int seimid; if ((semid = semget(IPC_PRIVATE, SET_SIZE, PERMS)) < 0) perror("Could not create new private semaphore"); else printf("Semaphore created with ID %d\n",semid);}#include <stdio.h>#include <sys/stat.h>#include <sys/ipc.h>#include <sys/sem.h>#include <string.h>#include <errno.h>#define PERMS S_IRUSR|S_IWUSR|S_IRGRP|S_IWGRP|S_IROTH|S_IWOTH#define SET_SIZE 1#define KEY ((key_t)99887)void main(void){ int semid; if ((semid = semget(KEY, SET_SIZE, PERMS | IPC_CREAT)) < 0) fprintf(stderr, "Error creating semaphore with key %d: %s\n", (int)KEY, strerror(errno)); else printf("Semaphore with ID %d created for key %d\n",semid,(int)KEY);}Random KeyGenerate Key from ftok int semid; key_t mykey; if (argc != 3) { fprintf(stderr, "Usage: %s filename id\n", argv[0]); exit(1); } if ((mykey = ftok(argv[1], atoi(argv[2]))) == (key_t) -1) { fprintf(stderr, "Could not derive key from filename %s: %s\n", argv[1], strerror(errno)); exit(1); } else if ((semid = semget(mykey, SET_SIZE, PERMS | IPC_CREAT)) < 0) { fprintf(stderr, "Error creating semaphore with key %d: %s\n", (int)mykey, strerror(errno)); exit(1);semopSYNOPSIS#include <sys/types.h>#include <sys/ipc.h>#include <sys/sem.h>int semop(int semid, struct sembuf *sops, int nsops);POSIX:XSI•A process can increment, decrement or test individual semaphore elements with the semop system call•semid is handle returned by semget•sops points to an array of element operations•nsops specifies the number of element operations in the sops array•semop returns –1 and sets errno on errorstruct sembufstruct sembuf has the following three fields•short sem_num: The number of the semaphore element•short sem_op: The particular operation to be performed on the semaphore element•short sem_flg: The flags to specify options for the oprationsem_op•If sem_op > 0, semop adds the value to the corresponding semaphore element and awakens processes waiting for semaphore element to increase•If sem_op = 0, and semaphore element value is not 0, semop blocks the calling process (waiting for 0) and increments the count of processes waiting for a zero value of that element•If sem_op < 0, semop adds the value to the corresponding semaphore element value provided the result would