Perkolacja

prir01.c

/*
 * 
 * autor: Maciej Ciemborowicz
 * Uniwersytet Jagielloński
 * PRIR 2011/2012
 *
 * kompilacja: gcc prir01.c -std=c99 -pedantic -Wall -D_XOPEN_SOURCE=600
 * uruchamianie: ./a.out rozmiar_tablicy delta_Pb ilosc_eksperymentow liczba_procesow
 * 
 * Zarys działania programu
 * 
 *    Program po pobraniu i walidacji argumentów przydziela pamięć współdzieloną,
 * w której znajduje się licznik wypisanych krotek z wynikami. Następnie,
 * po inicjacji generatora liczb pseudolosowych (/dev/urandom), w pętli
 * tworzy kolejne procesy potomne, które wykonują obliczenia dla przydzielonych
 * im prawdopodobieństw. Jeżeli jest n procesów, a numer procesu to i, 
 * proces potomny policzy wyniki dla co n-tego prawdopodobieństwa, zaczynając
 * od i-tego. Ostatnia pula prawdopodobieństw przypada procesowi rodzicowi,
 * dzięki czemu wszystkie procesy mają przydzielone zadania. Aby zachować
 * odpowiednią kolejność wyników, każdy proces sprawdza, na podstawie 
 * licznika (counter), czy policzony przez niego wynik może być już wyświetlony.
 * Jeżeli poprzednie wyniki nie zostały wyświetlone, czeka wykonując pustą pętlę.
 * Na końcu każdy proces potomny jest zakańczany, a proces rodzic czyści 
 * ponadto pamięć współdzieloną.
 * 
 *    Szukanie ścieżki odbywa się rekurencyjnie przy użyciu funkcji find_path.
 * Przyjmuje ona jako argument dwuwymiarową tablicę, współrzędne wskasujące
 * aktualne położenie, rozmiar tablicy oraz wskaźnik na dwuwartościową zmienną
 * success, która ustawiana jest na 'true' jeżeli znaleziono ścieżkę. 
 * Ze względu na specyfikę języka, przekazywanie dwuwymiarowej tablicy
 * jako argumentu funkcji wymusiło operowanie na niej na poziomie
 * adresów pamięci. Funkcja sprawdza, czy kolejne sąsiednie pola są wolne.
 * Jeśli tak, zajmuje je i wywołuje się przekazując jako argumenty współrzędne
 * tychże pól, aż do przejścia na drugi koniec tablicy, bądź braku możliwych
 * ruchów.
 * 
 *    Liczenie szansy przejścia przez tablicę wykonuje funkcja count_chance.
 * przyjmuje jako argumenty rozmiar tablicy, prawdopodobieństwo występowania
 * zajętych pól oraz liczbę eksperymentów. Podczas każdego eksperymentu
 * wypełnia losowo pola tablicy, a następnie sprawdza, czy można przez 
 * nią przejść, wywołując find_path od każdego możliwego pola startowego.
 * Jeśli udało się przejść przez tablicę, inkrementuje licznik 'sum' o 1
 * i wykonuje kolejny ekperymentów. Po wykonaniu wszystkich, zwraca stosunek
 * 'sum' to liczby przeprowadzonych eksperymentów.
 * 
 *    Za generowanie pól w tablicy odpowiada funkcja generate_state, 
 * która przyjmuje jako argument prawdopodobieństwo z jakim pole może
 * być zajęte. Zwraca wartość pola.
 * 
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <unistd.h>

#define EMPTY ' '
#define FILLED '#'

////////////////////////////////////////////////////////////////////////

void randomize();
char generate_state(float Pb);

void find_path(char **array, 
                unsigned int x, 
                unsigned int y, 
                unsigned int N, 
                bool *success);
                
float count_chance(unsigned int N, 
                    float Pb, 
                    unsigned int experiments_n);

////////////////////////////////////////////////////////////////////////

int main(int argc, char *argv[]) {

  long int N, experiments_n, processes_n, i, results_n;
  double delta_Pb;

  // walidacja
  if (argc != 5) {
    fprintf(stderr, "Error: Bad number of arguments.\n");
    return 1;
  }
  
  // pobieramy argumenty
  N = atoi(argv[1]);
  delta_Pb = atof(argv[2]);
  experiments_n = atoi(argv[3]);
  processes_n = atoi(argv[4]);
  
  // kontynuacja walidacji
  if (N < 2 || 
      delta_Pb >= 1 || 
      delta_Pb <= 0 || 
      experiments_n < 1 || 
      processes_n < 1) {
    fprintf(stderr, "Error: Wrong arguments.\n");
    return 2;
  }

  // ilość krotek z wynikami
  // results_n = 1 / delta_Pb - 1; 
  // gcc na ibisnecie ssie, trzeba mniej elegancko
  i = 0;
  while (delta_Pb*i < 1)
    ++i;
  results_n = i-1;

  // pid procesu rodzica
  pid_t parent_pid = getpid();
  
  // przydzielamy pamięć współdzieloną
  key_t key = ftok(argv[0], 'A');
  int shmid = shmget(key, sizeof(int), 0644 | IPC_CREAT); 
  int *counter = (int *)shmat(shmid, (void *) 0, 0);
  if (counter == (int *)(-1)) {
    fprintf(stderr, "Error: Memory allocation failed.\n");
    return 3; 
  }
  *counter = 0;

  // inicjalizacjujemy generator liczb pseudolosowych
  randomize();
  
  // tworzymy tyle procesów ile podano w argv
  for (i=0; i<processes_n; ++i) {
    
    // jeżeli proces jest rodzicem, 
    // i to nie jest ostatnia pula zadań (przeznaczona dla procesu rodzica)
    // tworzymy proces potomny
    if (getpid() == parent_pid && i < processes_n-1) {
      fork();
    }
    
    // jeżeli proces jest procesem potomnym,
    // lub to ostatnia pula zadań (przeznaczona dla procesu rodzica)
    // przydzielamy mu zadania
    if (getpid() != parent_pid || i == processes_n-1) {
      int j;
  
      // proces liczy szanse przejścia tablicy 
      // dla przydzielonych mu prawdopodobieństw
      for (j=i; j<results_n; j+=processes_n) {
        
        float Pb = delta_Pb * (j + 1);
        float chance = count_chance(N, Pb, experiments_n);
       
        // aby zachować odpowiedni porządek wyników, 
        // czekamy aż wszystkie wsześniejsze zostaną wypisane
        while (*counter < j) {
        }
       
        // wypisujemy wynik
        printf("%.6g\t%.6g\n", Pb, chance);
        
        // inkrementujemy licznik o 1
        ++*counter;
        // od teraz kolejny wynik może zostać wypisany
        
      }
      if (getpid() != parent_pid) {
        _exit(0);
      }
    }
    
  }

  // czekamy aż wszystkie wyniki zostaną wypisane
  while (*counter < results_n) {
  }

  // czekamy aż procesy potomne się zakończą
  waitpid(0, NULL, WUNTRACED);

  // sprzątamy
  shmdt(counter);
  shmctl(shmid, IPC_RMID, NULL);

  return 0;
  
}

////////////////////////////////////////////////////////////////////////
// inicjacja generatora liczb pseudolosowych
void randomize() {
  
  FILE *urandom = fopen("/dev/urandom", "r");
  long int seed;
  fread(&seed, sizeof(long int), 1, urandom);
  srand(seed);
  fclose(urandom);
  
}

////////////////////////////////////////////////////////////////////////
// losowanie stanu pola w tablicy
char generate_state(float Pb) {
  
  return (rand() / (double)RAND_MAX) < Pb ? FILLED : EMPTY;

}
  
////////////////////////////////////////////////////////////////////////
// ostra jazda na wskaźnikach
void find_path(char **array, 
                unsigned int x, 
                unsigned int y, 
                unsigned int N, 
                bool *success) {
  
  // jeżeli pole jest na drugim końcu tablicy, znaleziono ścieżkę
  if (x == N-1)
    *success = true;
  
  // jeżeli bieżące pole jest zajęte (możliwe w stanie początkowym), 
  // lub znaleziono ścieżkę, zakończ wykonywanie podprogramu
  if (FILLED == *((char *)array + x + N*y) || *success)
    return;
    
  // oznacz bieżące pole jako zajęte
  *((char *)array + x + N*y) = FILLED;
  
  // szukaj po lewej
  if (x >= 1 && EMPTY == *((char *)array + x-1 + N*y)) {
    find_path(array, x-1, y, N, success);
  }

  // szukaj po prawej
  if (x < N-1 && EMPTY == *((char *)array + x+1 + N*y)) {
    find_path(array, x+1, y, N, success);
  }        
  
  // szukaj na górze
  if (y >= 1 && EMPTY == *((char *)array + x + N*(y-1))) {
    find_path(array, x, y-1, N, success);
  }

  // szukaj na dole
  if (y < N-1 && EMPTY == *((char *)array + x + N*(y+1))) {
    find_path(array, x, y+1, N, success);
  }
   
}

////////////////////////////////////////////////////////////////////////
// obliczanie szansy przejścia przez tablicę
float count_chance(unsigned int N, 
                    float Pb, 
                    unsigned int experiments_n) {
    
  char array[N][N];
  unsigned int n;
  unsigned int sum = 0;
    
    // wykonywanie experiments_n eksperymentów
    for (n = 0; n < experiments_n; ++n) {
        
      unsigned int i, j;
      bool success = false;
      
      // wypełnianie tablicy
      for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {

          array[i][j] = generate_state(Pb);

        }
      }
      
      // szukanie ścieżki
      for (i = 0; i < N; ++i) {
        
        find_path((char **)array, 0, i, N, &success);
        if (true == success) {
          ++sum;          
          break;
        }
        
      }
     
    }
    
  return (float)sum / experiments_n;
  
}