Fibonacci in multithreading

Un programmino di test per verificare l'uso della libreria boost thread.

La classe Fibonacci permette di calcolare il numero di fibonacci ma, per velocizzare le operazioni, quando la classe viene instanziata viene creato un nuovo thread che si prende carico di precalcolare i numeri di fibonacci.

Per evitare i problemi di overflow il numero più alto calcolabile é impostato a 40 (via la costante MAX_INDEX).

L'algoritmo per il calcolo del numero é di default quello di calcolo brutale, ma é possibile attivare l'ottimizzazione che permette di riutilizzare i valori già calcolati, velocizzando notevolmente l'esecuzione.

Qui il codice, a seguire qualche commento:

#include <iostream>
#include <vector>
#include <boost/thread.hpp>
#include <boost/thread/condition.hpp>

using namespace std;

class Fibonacci {
public:
  static const int MAX_INDEX = 40;

  Fibonacci(bool optim = false);
  ~Fibonacci();

  unsigned int get(unsigned int index);

private:
  std::vector<unsigned int> values;
  bool optim;

  boost::mutex mx;
  boost::condition cond;
  boost::thread tCalc;

  unsigned int getValue(unsigned int index);
  void precalc();
};

const int Fibonacci::MAX_INDEX;

unsigned int Fibonacci::getValue(unsigned int index) {
  if(optim)
  {
    boost::mutex::scoped_lock lock(mx);
    if(index < values.size())
      return values.at(index);
  }

  switch (index) {
  case 0:
    return 0;
  case 1:
    return 1;
  default:
    boost::this_thread::interruption_point();
    return getValue(index - 2) + getValue(index - 1);
  }
}

void Fibonacci::precalc() {
  for(int iteration = 0; iteration <= MAX_INDEX; ++iteration)
  {
    unsigned int value = getValue(iteration);
    boost::mutex::scoped_lock lock(mx);
    values.push_back(value);
    cond.notify_one();
  }
}

Fibonacci::Fibonacci(bool optim) : optim(optim) {
  values.reserve(MAX_INDEX);
  tCalc = boost::thread(&Fibonacci::precalc, this);
}

Fibonacci::~Fibonacci() {
  tCalc.interrupt();
  tCalc.join();
}

unsigned int Fibonacci::get(unsigned int index) {
  if(index < 0 || index > MAX_INDEX)
    return 0;
  boost::mutex::scoped_lock lock(mx);
  while(index >= values.size()) {
    cout << "Please wait ..." << endl;
    cond.wait(mx);
  }
  return values.at(index);
}


void fib() {
  Fibonacci fib;

  int input;
  while(true) {
    cout << "Your input [1 .. " << Fibonacci::MAX_INDEX << "]: ";
    cin >> input;
    if(input < 1 || input > Fibonacci::MAX_INDEX)
      break;
    cout << "Fibonacci of " << input << " is " << fib.get(input) << endl;
  }
  cout << "Bye" << endl;
}

Per usare la classe basta instanziarla, cosa che fa partire il thread che fa partire il precalcolo, e quindi chiamare il metodo get() specificando quale numero di fibonacci si voglia ottenere.

Il costruttore accetta un parametro opzionale che permette di ottimizzare l'algoritmo di calcolo. Nel test uso la versione senza ottimizzazione, in modo da osservare meglio il funzionamento del programma.

Altra cosa che fa il costruttore é istanziare un oggetto boost::thread sulla funzione Fibonacci::precalc() dell'oggetto corrente.

Il thread esegue la funzione precalc() che fa un loop determinato da MAX_INDEX per pre-calcolare i numeri di fibonacci. Delega alla funzione ricorsiva getValue() il calcolo del valore specifico, quindi mette un lock sul mutex che controlla il vettore, fa una push_back e quindi notifica alla condizione sul lock che qualcosa é cambiato nella cache.

La funzione getValue(), se l'ottimizzazione non é abilitata, genera il numero di fibonacci per ricorsione. Altrimenti ritorna il valore già calcolato e memorizzato nella cache - se esiste.

Da notare l'uso di boost::this_thread::interruption_point(); per definire un punto in cui é possibile interrompere l'esecuzione del thread.

Mentre un thread lavora per la generazione dei numeri di fibonacci, l'altro resta in attesa che l'utente immetta quale numero voglia calcolare.

La get() si occupa di andare a leggere nella cache se il numero richiesto sia già stato calcolato. Per far ciò crea un lock sul mutex che controlla l'accesso al vettore, se vede che il numero non é ancora stato generato, segnala all'utente che deve pazientare e si mette in attesa sulla condizione. Abbiamo visto sopra che ogni volta che un nuovo numero di fibonacci viene messo nella cache l'altro thread manda una notifica alla condizione. Ricevuta la notifica controlliamo di nuovo se la condizione é soddisfatta, e così via finché abbiamo il via libera all'accesso alla cache.

Ultima cosa che resta da vedere é il distruttore della classe, che manda un interrupt all'altro thread, e quindi fa una join.