Programowanie współbieżne i rozproszone/PWR Ćwiczenia sem

From Studia Informatyczne

Spis treści

Tematyka zajęć

Semafory uniksowe jako jeden z mechanizmów IPC.

Literatura

Scenariusz zajęć

Wstęp

Jak już wspomnieliśmy na wykładzie, semafory w systemie Unix dostarczają znacznie bogatszej funkcjonalności niż semafory klasyczne. Zapoznamy się teraz z funkcjami systemowymi umożliwiającymi wykonywanie operacji na tych semaforach i przeanalizujemy przykładowe programy wykorzystujące semafory.

Semafory uniksowe są dostępne jako jeden z zasobów IPC. Dlatego też wszystkie uwagi ogólne dotyczące mechanizmów IPC omówione przy okazji laboratorium dotyczącego kolejek komunikatów pozostają w mocy. W szczególności zasady tworzenia zasobu, zyskiwania dostępu do niego są takie same jak przy kolejkach komunikatów. Ze względu na specyfikę semaforów funkcja semget (odpowiednik msgget) ma inne parametry. Wiąże się do głównie z tym, że semafory w Uniksie nie występują pojedynczo, lecz są grupowane w tzw. ,,zestawy semaforów. Cały zestaw stanowi pojedynczy zasób IPC. Maksymalna liczba semaforów w jednym zestawie jest zależna od konfiguracji jądra. W obrębie zestawu poszczególne semafory są numerowane kolejnymi liczbami nieujemnymi, począwszy od zera.

Tworzenie (uzyskiwanie dostępu do) zestawu semaforów

Do tworzenia zestawu semaforów lub pozyskania dostępu do już istniejącego zestawu służy funkcja systemowa:

int semget (key_t klucz, int lsem, int flagi)

Funkcja ta działa analogicznie do funkcji msgget:

  • parametr klucz jest kluczem identyfikującym zestaw
  • parametr flagi ustala prawa dostępu do zestawu semaforów oraz tryb tworzenia (opcje IPC_CREAT oraz IPC_EXCL); można tu także użyć wartość IPC_PRIVATE
  • wynikiem funkcji jest -1 w przypadku błędu lub wartość dodatnia identyfikująca zestaw w kolejnych operacjach na nim.

Ponadto w operacji semget występuje parametr lsem, który ustala liczbę semaforów w zestawie. Warto zauważyć, że parametry lsem oraz prawa dostępu ustanawiane w parametrze flagi mają znaczenie jedynie przy faktycznym tworzeniu zestawu. Jeśli skutkiem operacji jest uzystkanie dostępu do już istniejącego zestawu, to wartości te są ignorowane.

A oto przykładowy program służący do tworzenia zestawu semaforów:

#include <stdio.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <errno.h>
 
#include "err.h"
 
int main ()
{
  key_t key;
  int opperm, flags, nsems, semid, opperm_flag;
 
  printf( "\nWprowadź klucz zestawu szesnastkowo = ");
  scanf(  "%x", &key );
 
  printf( "\nWprowadź prawa dostępu szesnastkowo = ");
  scanf(  "%o", &opperm );
 
  printf( "\nWybierz wartość odpowiadającą kombinacji opcji:\n");
  printf( "0 --> Bez opcji \n");
  printf( "1 --> IPC_CREAT \n");
  printf( "2 --> IPC_EXCL \n");
  printf( "3 --> IPC_CREAT i IPC_EXCL \n");
  printf( "Opcje = ");
  scanf(  "%d", &flags );
 
  printf( "\nklucz = 0x%x, prawa = 0%o, opcje = 0%o\n", key, opperm, flags );
 
  switch ( flags ) {
    case 0:
      opperm_flag = opperm | 0;
      break;
    case 1:
      opperm_flag = opperm | IPC_CREAT;
      break;
    case 2:
      opperm_flag = opperm | IPC_EXCL;
      break;
    case 3:
      opperm_flag = opperm | IPC_EXCL | IPC_CREAT;
      break;
  }
 
  printf( "\nWprowadź liczbę semaforów w zestawie (25 max) = ");
  scanf(  "%d", &nsems );
  printf( "\nLsems = %d\n", nsems );
 
  /*********************************************************/
 
  semid = semget( key, nsems, opperm_flag );
 
  /*********************************************************/
 
  if ( semid == -1 )
    syserr("semget");
 
  printf( "\nIdentyfikator = %d\n", semid );
  return 0;
}
Ćwiczenie

Skompiluj ten program i wykonaj go. Wypróbuj różne kombinacje opcji i zaobserwuj, co się dzieje, jeśli są one stosowane do istniejącego lub nowego zestawu semaforów. Obserwuj skutek wykonywanych operacji za pomocą polecenia ipcs.

Operacje na semaforach

Semafory uniksowe umożliwiają wykonywanie wielu atomowych operacji na zestawie. Ich semantykę przedstawiono na wykładzie. Obecnie skupimy się na technicznych aspektach związanych z użyciem semaforów.

Pojedynczą operacja na semaforze w zestawie opisuje się za pomocą następującej struktury sembuf:

struct sembuf {
  short int sem_num;            /* numer semafora */
  short int sem_op;             /* operacja semaforowa */
  short int sem_flg;            /* opcje */
};

Pole sem_op opisuje wykonywaną operację:

  • jeśli sem_op jest większe od zera, to semafor jest podnoszony o wartość sem_op<tt> (operacja V)
  • jeśli <tt>sem_op jest mniejsze niż zero, to semafor jest opuszczany o wartość -sem_op (operacja P)
  • jeśli sem_op jest równe zero, to proces jest wstrzymywany w oczekiwaniu na zerową wartość semafora (operacja Z).

Numer semafora w zestawie, którego dotyczy operacja znajduje się w polu sem_num. Domyślnie operacje P oraz Z są blokujące, czyli wstrzymują proces, jeśli nie może on ich zakończyć natychmiast (bo wartość semafora jest zbyt mała w przypadku operacji P lub jest niezerowa w przypadku operacji Z). Jednak podanie w polu sem_flg wartości IPC_NOWAIT zmienia zachowanie domyślne i powoduje zakończenie operacji niedających się wykonać natychmiast z sygnalizacją błędu.

Do wykonywania operacji na zestawie semaforów służy funkcja systemowa semop:

int semop (int ident, struct sembuf *operacje, unsigned loper)
  • Pierwszy parametr to identyfikator zestawu semaforów, na których wykonujemy operacje
  • Drugi parametr to wskaźnik na strukturę (tablicę struktur w przypadku wielu operacji) opisującej operacje
  • Trzeci paramert to liczba jednoczesnych operacji, jakie mają być wykonane.

Wykorzystajmy to, co już wiemy do implementacji klasycznych operacji na semaforach

int sem_init (key_t key)
/* Utworzenie jednoelementowego zestawu semaforów */
{
  int sem_id;
 
  if ((sem_id = semget (key, 1, 0666 | IPC_CREAT)) == -1)
    syserr("semget");
  return (sem_id);
}
 
void sem_call (int sem_id, int op) 
/* funkcja wykonuje jedna operacje op na pierwszym semaforze w zestawie
   o identyfikatorze sem_id */  
{
  struct sembuf sb;
 
  sb.sem_num = 0;
  sb.sem_op = op;
  sb.sem_flg = 0;
  if (semop (sem_id, &sb, 1) == -1)
    syserr("semop; op = %d", op);
}
 
void P (int sem_id)
{
  sem_call(sem_id, -1);
}
 
void V (int sem_id)
{
  sem_call(sem_id, 1);
}

Powyższe funkcje będziemy wykorzystywać w dalszym ciągu zajęć.

Ćwiczenie
Przygotuj plik nagłówkowy simple.h udostępniający przedstawione wyżej operację. Ich implementację zapisz w pliku simple.c. 

A oto program, który korzysta z funkcji semop umożliwiając wykonywanie operacji na poszczególnych semaforach w zestawie.

#include <stdio.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <errno.h>
#include "err.h"
 
int main ()
{
  struct sembuf sembuf[10], *sops;
  int retrn, flags, sem_num, i, semid, op;
  unsigned nsops;
 
  sops = sembuf;
 
  printf( "\nIdentyfikator zestawu = ");
  scanf(  "%d", &semid );
  printf( "\nsemid = %d", semid );
 
  printf( "\nLiczba operacji jaką chcesz wykonać = ");
  scanf(  "%d", &nsops );
   for ( i = 0; i < nsops; i++, sops++) {
    printf( "\nNumer semafora = ");
    scanf( "%d", &sem_num );
    sops->sem_num = sem_num;
 
    printf( "\nOperacja = ");
    scanf( "%d", &op );
    sops->sem_op = op;
    printf( "\nsem_num = %d, sem_op = %+d \n", sops->sem_num, sops->sem_op);
 
    printf( "Opcje:\n");
    printf( " 0 ---> Brak opcji \n");
    printf( " 1 ---> IPC_NOWAIT \n");
    printf( " 2 ---> SEM_UNDO \n");
    printf( " 3 ---> IPC_NOWAIT oraz SEM_UNDO \n");
    printf( "opcje = ");
    scanf( "%d", &flags );
    switch ( flags ) {
      case 0:
        sops->sem_flg = 0;
        break;
      case 1:
        sops->sem_flg = IPC_NOWAIT;
        break;
      case 2:
        sops->sem_flg = SEM_UNDO;
        break;
      case 3:
        sops->sem_flg = SEM_UNDO | IPC_NOWAIT;
        break;
    }
    printf( "\nOpcje = %o\n", sops->sem_flg );
  } /* for */
 
  sops = sembuf;
 
  /*************************************************************/
 
  retrn = semop( semid, sops, nsops );
 
  /*************************************************************/
 
  if ( retrn == -1 )
    syserr("semop");
 
  printf( "\nUdało się! \n");
  printf( "Wynik funkcji semop ----> %d\n", retrn);
  return 0;
}

Ćwiczenia. Uogólniona sekcja krytyczna

W systemie dostepnych jest M jednostek pewnego zasobu. W systemie działają procesy wg następującego schematu:

#include <stdio.h>
#include "wspolne.h"
#include "protokol.h"
 
int main (int argc, char *argv[])
{
  int pid = getpid(), ile;
  if (argc !=2)
    {
      printf ("Zla liczba argumentow w programie %s", argv[0]);
      exit (1);
    }
  ile=atoi (argv[1]);
  if (ile > M || ile < 1)
    {
      printf ("Niepoprawna wartość argumentu programu %s", argv[0]);
      exit (1);
    }
 
  Inicjuj();
 
  for (;;)
    {
      wlasne_sprawy (pid);
      Pobierz (ile);
      sekcja_krytyczna (pid);
      Oddaj (ile);
    }
}

Jak widać każdy proces uruchamia się z jednym argumentem --- jest to liczba zasobów, które rezerwuje dla siebie wchodząc do sekcji krytycznej. Biblioteka wspólne udostępnia dwie funkcje:

void wlasne_sprawy (pid_t pid)
{
  printf ("Proces %d:  wlasne sprawy\n", pid);
  sleep (2);
}
 
void sekcja_krytyczna (pid_t pid)
{
  printf ("Proces %d:  sekcja krytyczna\n", pid);
  sleep (3);
}

Przygotuj plik protokol.c implementujący trzy funkcje:

  • Inicjuj ()
  • Pobierz (int ile)
  • Oddaj (int ile)

tak, aby proces mógł wejść do sekcji krytycznej tylko wówczas, gdy jest dostępnych co najmniej ile zasobów. Proces rezerwuje te zasoby na czas pobytu w sekcji i oddaje je po wyjściu z niej.

Rozwiązanie 1

Pierwszy wariant rozwiązania polega na wykorzystaniu jednego semafora. W protokole wstepnym (Pobierz) semafor ten jest opuszczany ile razy o 1, w protokole końcowym jest podnoszony ile razy o 1:

#include <sys/ipc.h>
#include <sys/sem.h>
#include "protokol.h"
 
int S; /* Identyfikator zestawu semaforów */
 
void Inicjuj (void)
/* Tworzy jeden zestaw z jednym semaforem i inicjuje go M */
{
 
  if ((S=semget (KLUCZ, 1, IPC_CREAT | IPC_EXCL | 0666)) == -1)
    {
      if ((S=semget (KLUCZ, 1, 0)) == -1)
        syserr ("blad w inicjuj");
    }
  else
    V(M);
}
 
void V (int n)
{
  struct sembuf sb;
 
  sb.sem_num = 0;
  sb.sem_op  = n;
  sb.sem_flg = 0;
 
  if (semop (S, &sb, 1) == -1)
    syserr ("blad w V");
}
 
void P (int n)
{
  struct sembuf sb;
  sb.sem_num = 0;
  sb.sem_op  = -n;
  sb.sem_flg = 0;
 
  if (semop (S, &sb, 1) == -1)
    syserr ("blad w V");
}
 
void Pobierz (int ile)
{
{
  int i;
 
  for (i=1; i<= ile; i++)
    P(1);
}
 
void Oddaj (int ile)
{
  int i;
 
  for (i=1; i<= ile; i++)
    V(1);
}

Rozwiązanie to zawiera poważny błąd synchronizacyjny. Może dojść do blokady!

Rozwiązanie drugie

Jest to poprawka pierszego rozwiązania, w której pętla w protokole wstępnym wykonuje się pod ochroną dodatkowego semafora. Tym razem program jest poprawny, ale dość kosztowny: wymaga wykonywania wielu operacji semaforowych.

#include <sys/ipc.h>
#include <sys/sem.h>
 
#include "protokol.h"
 
int S;
 
void Inicjuj (void)
{
 
  if ((S=semget (KLUCZ, 2, IPC_CREAT | IPC_EXCL | 0666)) == -1)
    {
      if ((S=semget (KLUCZ, 2, 0)) == -1)
        syserr ("blad w inicjuj");
    }
  else
    {
      V (0, 1);
      V (1, M);
    }
}
 
void V (short nr, int n)
{
  struct sembuf sb;
 
  sb.sem_num = nr;
  sb.sem_op  = n;
  sb.sem_flg = 0;
 
  if (semop (S, &sb, 1) == -1)
    syserr ("blad w V");
}
 
void P (short nr, int n)
{
  struct sembuf sb;
 
  sb.sem_num = nr;
  sb.sem_op  = -n;
  sb.sem_flg = 0;
 
  if (semop (S, &sb, 1) == -1)
    syserr ("blad w V");
}
 
 
void Pobierz (int ile)
{
  int i;
 
  P (0, 1);
  for (i=1; i<= ile; i++)
    P(1, 1);
  V (0, 1);
}
 
void Oddaj (int ile)
{
  int i;
 
  for (i=1; i<= ile; i++)
    V(1, 1);
}

Rozwiązanie trzecie

Najbardziej narzucające się rozwiązanie z semaforem zwiększanym/zmniejszanym od razu odpowiednią liczbę razy:

#include <sys/ipc.h>
#include <sys/sem.h>
 
#include "protokol.h"
 
int S;
 
void Inicjuj (void)
{
 
  if ((S=semget (KLUCZ, 1, IPC_CREAT | IPC_EXCL | 0666)) == -1)
    {
      if ((S=semget (KLUCZ, 1, 0)) == -1)
        syserr ("blad w inicjuj");
    }
  else
    {
      V(M);
    }
}
 
void V (int n)
{
  struct sembuf sb;
 
  sb.sem_num = 0;
  sb.sem_op  = n;
  sb.sem_flg = 0;
 
  if (semop (S, &sb, 1) == -1)
    syserr ("blad w V");
}
 
void P (int n)
{
  struct sembuf sb;
 
  sb.sem_num = 0;
  sb.sem_op  = -n;
  sb.sem_flg = 0;
 
  if (semop (S, &sb, 1) == -1)
    syserr ("blad w V");
}
 
void Pobierz (int ile)
{
  P (ile);
}
 
void Oddaj (int ile)
{
  V(ile);
}
 
Ale tym razem możemy zagłodzić procesy oczekujące na wiele zasobów. 
==== Rozwiązanie czwarte ====
Dwa semafory. Pierwszy o takim samym działaniu, co w poprzednim rozwiązaniu oraz dodatkowy semafor o takim samym działaniu co w rozwiązaniu drugim:
<source>
#include <sys/ipc.h>
#include <sys/sem.h>
 
#include "protokol.h"
 
int S;
 
void Inicjuj (void)
{
 
  if ((S=semget (KLUCZ, 2, IPC_CREAT | IPC_EXCL | 0666)) == -1)
    {
      if ((S=semget (KLUCZ, 2, 0)) == -1)
        syserr ("blad w inicjuj");
    }
  else
    {
      V (0, 1);
      V (1, M);
    }
}
 
void V (short nr, int n)
{
  struct sembuf sb;
 
  sb.sem_num = nr;
  sb.sem_op  = n;
  sb.sem_flg = 0;
 
  if (semop (S, &sb, 1) == -1)
    syserr ("blad w V");
}
 
void P (short nr, int n)
{
  struct sembuf sb;
 
  sb.sem_num = nr;
  sb.sem_op  = -n;
  sb.sem_flg = 0;
 
  if (semop (S, &sb, 1) == -1)
    syserr ("blad w V");
}
 
 
void Pobierz (int ile)
{
  int i;
 
  P (0, 1);
  P (1, ile);
  V (0, 1);
}
 
void Oddaj (int ile)
{
  int i;
 
  V (1, ile);
}

Priorytetowy dostęp do zasobu

Na wykładzie pokazano semafory Agerwali i ich wykorzystanie do realizacji priorytetowego dostępu do zasobu. Zaimplementuj ten algorytm.

#include <stdio.h>
#include <unistd.h>
#include <wait.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <errno.h>
 
#include "err.h"
 
#define KLUCZ 1234L
#define N 5
 
int semid;
 
void wlasne_sprawy (int kto)
{
  printf ("%d: Wlasne sprawy\n", kto);
  sleep (3);
}
 
void sekcja_krytyczna (int kto)
{
  printf ("%d: Wchodze do sekcji\n", kto);
  sleep (4);
  printf ("%d: Wychodze z sekcji\n", kto);
}
 
void PE (int k)
{
  int i;
 
  struct sembuf sb [N];
 
  sb[0].sem_num = 0;
  sb[0].sem_op = -1;
  sb[0].sem_flg = 0;
 
  for (i=1;i<=k; i++)
    {
      sb[i].sem_num = i;
      sb[i].sem_op = 0;
      sb[i].sem_flg = 0;
    }
 
  if (semop (semid, sb, k+1) == -1)
    syserr("blad w semop");
}
 
void V (int k)
{
  struct sembuf sb;
 
  sb.sem_num = k;
  sb.sem_op = 1;
  sb.sem_flg = 0;
 
  if (semop (semid, &sb, 1) == -1)
    syserr("blad w semop");
}
 
void P (int k)
{
  struct sembuf sb;
 
  sb.sem_num = k;
  sb.sem_op = -1;
  sb.sem_flg = 0;
 
  if (semop (semid, &sb, 1) == -1)
    syserr("blad w semop");
}
 
 
void process (int prio)
{
  int k;
 
  k = prio - 1;
 
  for (;;)
    {
      wlasne_sprawy(prio);
      V (prio);
      PE (k);
      P (prio);
      sekcja_krytyczna(prio);
      V (0);
    }
}
 
 
int main (void)
{
  pid_t p;
  int i;
 
  if ((semid = semget (KLUCZ, N+1, IPC_CREAT | 0666 ))==-1)
    syserr ("Blad w semget");
 
  V(0);
 
  for (i=1; i<=N; i++)
    switch(p=fork())
      {
      case -1:  syserr ("Blad w fork");
      case 0: process (i);
      }
 
  for (i=1; i<=N; i++)
    wait (0);
 
  semctl (semid, IPC_RMID, 0);
  return -1;
}