Semaphoren

Eine Semaphore ist im Prinzip ein Speicherbereich, dessen Wert von mehreren Prozessen ausgelesen und geändert werden kann. Dabei ist das Lesen und (in Abhängigkeit vom aktuellen Wert der Semaphore) Ändern des Wertes atomar, d.h. der Vorgang wird nicht von einem anderen Prozess unterbrochen, der evtl. zwischen dem Lese- und Schreibvorgang den Wert nochmals ändern könnte.

System V Semaphoren erweitern dieses Modell dahingehend, dass ein Array von Semaphoren erzeugt und durch eine einzige Operation verändert werden kann. Mit der Funktion

int semget ( key_t key, int nsems, int semflg )

werden nsems Semaphoren mit dem Schlüssel key erzeugt. Ist key noch nicht benutzt oder hat den besonderen Wert IPC_PRIVATE, so wird ein neues Array von Semaphoren angelegt und eine semid zurückgegeben, über die man Operationen auf diesem Semaphoren-Array ausführen kann. Referenziert key ein bereits existierendes Semaphoren-Array, so wird nur die damit assoziierte semid zurückgegeben.

Das Semaphoren-Array hat folgende Struktur [include/linux/sem.h]:

struct sem_array { 
  struct kern_ipc_perm sem_perm;        /* permissions .. see ipc.h */ 
  time_t sem_otime;                     /* last semop time */ 
  time_t sem_ctime;                     /* last change time */ 
  struct sem *sem_base;                 /* ptr to first semaphore in array */ 
  struct sem_queue *sem_pending;        /* pending operations to be processed */ 
  struct sem_queue **sem_pending_last;  /* last pending operation */ 
  struct sem_undo *undo;                /* undo requests on this array */ 
  unsigned long sem_nsems;              /* no. of semaphores in array */ 
};

wobei sem folgende Struktur ist:

struct sem { 
  int semval; /* current value */ 
  int sempid; /* pid of last operation */ 
};

Wenn eine Operation nicht erfolgreich ausgeführt werden kann und der Prozess blockieren darf, so wird er in die sem_pending Queue eingereiht. In dieser werden alle Prozesse und deren Operationen auf dem Semaphoren-Array die noch auszuführen sind, gesammelt.

struct sem_queue { 
  struct sem_queue * next;     /* next entry in the queue */ 
  struct sem_queue ** prev;    /* previous entry in the queue, *(q->prev) == q */ 
  struct task_struct* sleeper; /* this process */ 
  struct sem_undo * undo;      /* undo structure */ 
  int pid;                     /* process id of requesting process */ 
  int status;                  /* completion status of operation */ 
  struct sem_array * sma;      /* semaphore array for operations */ 
  int id;                      /* internal sem id */ 
  struct sembuf * sops;        /* array of pending operations */ 
  int nsops;                   /* number of operations */ 
  int alter;                   /* operation will alter semaphore */ 
};

System V Semaphoren erlauben es auch, dass bei Beenden eines Prozesses Operationen auf Semaphoren rückgängig gemacht werden. Dies soll sogenannte ''deadlocks'' verhindern. Dabei belegt ein Prozess per Semaphore eine Ressource, wird jedoch beendet bevor er die Ressource wieder freigeben kann und alle anderen Prozesse warten vergebens darauf, dass die Ressource durch die Semaphore wieder freigegeben wird.

Dazu verwaltet task_struct eine Liste mit ''undo'' Operationen, die auf die Semaphore angewandt werden, wenn der Prozess beendet wird.

struct sem_undo { 
  struct sem_undo * proc_next; /* next entry on this process */

  struct sem_undo * id_next;   /* next entry on this semaphore set */

  int semid;                   /* semaphore set identifier */

  short * semadj;              /* array of adjustments, one per semaphore */

};

Wird der Wert einer Semaphore verändert, so wird der negative Wert der Änderung in dieser undo Liste gespeichert.

Ändern kann man den Wert einer Semaphore mit der Funktion

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

Auf das Semaphoren-Array, das durch semid referenziert wird, werden nsops Operationen ausgeführt. Beginnend ab der Adresse von *sops werden nsops Felder der Struktur sembuf ausgewertet.

struct sembuf { 
  unsigned short sem_num; /* semaphore index in array */ 
  short sem_op;           /* semaphore operation */ 
  short sem_flg;          /* operation flags */ 
};

sem_num ist der Index der zu verändernden Semaphore innerhalb des Semaphoren-Arrays. sem_op der Wert der auf den Wert der Semaphore (semval) addiert wird. Über das Flag IPC_NOWAIT im Feld sem_flg kann man das Blockieren des Prozesses bei der Ausführung der Operationen verhindern. Das Flag SEM_UNDO speichert die Operation in oben beschriebener undo-Liste, damit sie rückgängig gemacht werden kann, wenn der Prozess beendet wird.

semop() garantiert, dass entweder alle Operationen erfolgreich sind oder keine davon ausgeführt wird. Eine Operation ist als ''erfolgreich'' definiert, wenn der Wert der Semaphore nach der Operation grösser Null ist oder sowohl der aktuelle Wert der Semaphore als auch der Wert der Operation Null sind.

Semaphoren erlauben eine n:m Kommunikationsbeziehung zwischen Prozessen. Es können mehrere Prozesse gleichzeitig durch das Ändern der Semaphore vielen anderen Prozessen z.B. die Belegung/Freigabe einer Ressource signalisieren. Semaphoren eignen sich jedoch nicht für den Datenaustausch.