Michele Beltrame
tennisclub - Programmazione threaded in Perl

Assegnazione palline in un tennis club

Data di pubblicazione: 14 Aprile 2004 (Versione 1.0.2).

© 2004 Michele Beltrame. Michele Beltrame vive a Maniago, PN, è programmatore Perl e convinto sostenitore del movimento Open Source. Può essere raggiunto via e-mail all'indirizzo mb@italpro.net

© Perl Mongers Italia. Tutti i diritti riservati.


Introduzione

Dalla versione 5.6 in poi, Perl propone una nuova implementazione dei thread, chiamati thread dell'interprete o, più sinteticamente ithread. Questa implementazione, ulteriormente migliorata dalla versione 5.8 del linguaggio, prevede che ogni thread sia eseguito nel suo interprete personale: al momento della creazione di un thread, tutti i dati vengono copiati, a meno che non ne sia esplicitamente richiesta la condivisione.

Il programma presentato in questo tutorial simula l'assegnazione delle palline in un tennis club. Il club ha un certo quantitativo di palline, ed i giocatori ne richiedono un certo numero a testa. In base ad una policy, il club assegna o meno le palline richieste, oppure ne assegna un numero inferiore. Ogni giocatore e un thread che chiede le palline, gioca per un certo tempo, le restituisce, attende per un certo tempo, e poi le chiede ancora per giocare una nuova partita. Se il club non gli concede le palline, il giocatore aspetta un certo tempo e poi riprova a chiederle.


Codice Sorgente (parte 1)

 #!/usr/bin/perl -w

 use strict;
 use threads;
 use threads::shared;

 # ### Tennis club ###

 # Palline da tennis del club
 my $pallinetot = 270;

 # Palline correnti
 my $palline : shared = $pallinetot;

 # ### Giocatori ###

 # Nomi
 my @nomi = (
             'Beppe', 'Michele', 'Laura', 'Marco', 'Elena',
             'Mauro', 'Stefania', 'Mirka', 'Agenore', 'Cosimo',
             'Alessandro', 'Valentina', 'Denis', 'Sabrina', 'Anna',
             'Nicola', 'Luca', 'Frida', 'Gliano', 'Asdrubale',
             'Lisa', 'Elisa', 'Louis', 'Ernesto', 'Loris',
             );

 # Massimo tempo per completare la partita
 my $tempomax = 20;

 # Tempo di attesa se le palline sono rifiutate per riprovare
 my $tempobar = 2;

 # Tempo di attesa tra la restituzione delle palline e una nuova partita
 my $tempoidl = 3;

 # Massimo numero di palline che possono richiedere
 my $pallinemaxe = 25;

 # ### Programma principale ###

 # Crea i thread giocatori
 my @g;
 for my $i(0..$#nomi) {
     $g[$i] = threads->new(\&giocatore, $nomi[$i]);
 }

 # Attende la fine prima di uscire (non esce mai)
 for my $i(0..$#nomi) {
     $g[$i]->join();
 }


Discussione (parte 1)

Il programma, dopo aver incluso i moduli threads e threads::shared (quest'ultimo è necessario per poter condividere variabili tra un thread e l'altro), definisce alcune variabili iniziali: numero di palline appartenenti al club; nomi dei giocatori (per rendere possibile una immediata distinzione visiva di ciasun thread); tempo massimo a disposizione di ogni giocatore per completare una partita; tempo di attesa nel caso in cui il club rifiuti di concedere le palline al giocatore; tempo di attesa tra la restituzione delle palline ed una nuova richiesta di altre; numero massimo di palline che un singolo giocatore può richiedere in una volta. Notate inoltre, in questa sezione, che $palline viene definita come shared, ed assume un valore iniziale uguale a quello di $pallinetot: questa variabile rappresenta infatti il numero di palline che il club ha in un determinato istante, ed è condivisa tra tutti i thread/giocatori.

A questo punto vengono creati i thread corrispondenti ai vari giocatori, ed i loro handle vengono memorizzati nell'array @g. La creazione di un thread avviene passando al costruttore la reference alla funzione che costituirà il blocco di codice principale del thread, ed un parametro per essa, cioè il nome del giocatore. Una volta creati i thread, essi iniziano subito la loro esecuzione, ed è necessario effettuare un join() di tutti essi. Ciò avviene nel ciclo sottostante. Una volta che tutti i thread sono stati uniti al programma principale, esso attende la loro fine prima di chiudere (il che, come vedremo dopo, significa in questo caso che il programma gira in eterno). Se non avessimo chiamato join() per ogni thread, o al suo posto avessimo chiamato detach(), il programma sarebbe terminato quasi subito con l'errore:

 A thread exited while 26 other threads were still running.

Questo indica che tutti i thread dipendenti da quello principale non hanno potuto terminare la loro esecuzione, in quanto il thread principale è uscito.


Codice sorgente (parte 2: subroutine)

 # ### Subroutine ###

 # Policy 1: assegna al giocatore le palline richieste, se disponibili
 sub policy1 {
     my ($pallineric) = @_;
     ($palline >= $pallineric) ? return $pallineric : return 0;
 }

 # Policy 2: se c'e` ancora almeno il 20% delle palline disponibili, assegna
 # quelle richieste; se ce ne sono meno, ne assegna al massimo il 2.5%
 # ogni volta
 sub policy2 {
     my ($pallineric) = @_;
     if ($palline < int($pallinetot/5)) {
         if ($pallineric > int($pallinetot/40)) {
             ($palline >= int($pallinetot/40)) ? return int($pallinetot/40) : return 0;
         } else {
             ($palline >= $pallineric) ? return $pallineric : return 0;
         }
     } else {
         ($palline >= $pallineric) ? return $pallineric : return 0;
     }
 }

 # Richiesta palline
 sub chiedi_palline {
     my ($nome, $pallineric) = @_;

     # Ora $palline E<egrave> tutta nostra
     lock ($palline);

     # Assegna le palline secondo la policy desiderata
     my $pallineass = &policy2($pallineric);

     if ($pallineass > 0) {
         $palline -= $pallineass;
         print "$pallineass palline (su $pallineric richieste) concesse a $nome (totale $palline)\n";
         return $pallineass;
     } else {
         print "$pallineric palline rifiutate a $nome (totale $palline)\n";
         return 0;
     }
 }

 # Restituzione palline
 sub restituisci_palline {
     my ($nome, $pallineric) = @_;

     lock ($palline);
     $palline += $pallineric;
     print "$pallineric palline restituite da $nome (totale $palline)\n";
 }

 # Giocatore
 sub giocatore {
     my ($nome) = @_;

     # Il giocatore gioca e rigioca di continuo
     while (1) {

         # Richiedi un numero di palline tra 1 e $pallinemaxe
         my $pallineric = int(rand($pallinemaxe))+1;

         my $pallineass;

         # Chiedi le palline
         while (($pallineass = &chiedi_palline($nome, $pallineric)) == 0)  {
             sleep $tempobar;
         }
         sleep int(rand($tempomax))+1;
         &restituisci_palline($nome, $pallineass);
         sleep $tempoidl;

     }
 }


Discussione sulle subroutine

Analizziamo ora le operazioni compiute da ciascun singolo thread/giocatore. È opportuno ricordare che, al momento della creazione di un thread, tutti i dati (scalari, array, funzioni, e quant'altro) presenti nel programma in quell'istante vengono clonati: di fatto viene creato un programma uguale all'originale, che gira come un thread dipendente dal programma principale. Dunque, tutti i dati sono separati, fatta eccezione per quelli esplicitamente condivisi. Nel nostro caso viene condivisa solo la variabile $palline, che indica le palline che il tennis club ha a disposizione in un determinato istante: questo valore è infatti unico, ed ogni thread deve potervi accedere in scrittura, secondo la modalità che verrà spiegata in seguito.

La subroutine che costituisce il codice principale di ciascun thread è giocatore(). In essa viene avviato un loop infinito, ogni iterazione del quale rappresenta una partita del giocatore, divisa in tre fasi: richiesta delle palline, gioco, restituzione delle palline. Il numero di palline è determinato estraendo un numero casuale compreso tra 1 e $pallinemax, in modo da rendere diversa ogni richiesta da quella precedente. A questo punto le palline vengono richieste tramite la funzione chiedi_palline(), che ritorna il numero delle palline che sono state effettivamente assegnate al thread/giocatore, oppure 0 in caso di mancata assegnazione. In caso appunto l'assegnazione non sia stata possibile (per via della mancanza delle palline necessarie) viene atteso un certo tempo (definito dalla variabile molto opportunamente chiamata $tempobar), e poi esse vengono richieste di nuovo, finché esse non vengono assegnate. Chiaramente, durante questi secondi, un altro thread/giocatore ha il tempo di restituire le sue palline, e forse un altro ancora riesce a richiederle prima che tale tempo sia trascorso. Una volta ottenute le palline, il programma si ferma per un tempo determinato in maniera casuale tra un secondo ed il contenuto di $tempomax. Trascorso questo intervallo, le palline vengono restituite con una chiamata a restituisci_palline(). Dopo una pausa di $tempoidl secondi, il ciclo infinito riparte.

Il clou del programma risiede nella funzione chiedi_palline(), che si occupa di assegnare un certo numero di palline a ciascun thread/giocatore. Anzitutto, è necessario effettuare il lock della variabile condivisa $palline, cioè richiederne l'utilizzo esclusivo. Questa operazione è strettamente necessaria per evitare delle race condition, cioè situazioni in cui più di un thread accede allo stesso dato in contemporanea. Prendiamo infatti in esame la linea di codice in cui viene decrementato il numero di palline disponibili:

 $palline -= $pallineass

L'operatore svolge fondamentalmente due operazioni su $palline: ne legge il valore e poi lo decrementa del valore di $pallineass. Tra queste due operazioni, in caso non vi fosse un lock sulla variabile, un altro thread (o più di uno) potrebbe effettuare a sua volta un'operazione. Ad esempio, poniamo che $palline valga 27, e che un giocatore ne richieda 4 e l'altro 5; alla fine di ciò $palline dovrebbe assumere valore 18. Senza un lock potrebbe configurarsi una situazione del genere:

 THREAD1: legge $palline
 THREAD2: legge $palline
 THREAD1: decrementa $palline => 23
 THREAD2: decrementa $palline => 22

Alla fine $palline assumerebbe valore 22, annullando di fatto il decremento effettuato dal primo thread. Un modo per prevenire queste situazioni è, appunto, l'utilizzo di un lock sulla variabile che si deve gestire:

lock ($palline);

Con la chiamata a lock() viene richiesta l'aasegnazione di un lock sulla variabile passata come parametro. Se non esiste un precedente lock su di essa, esso viene concesso e l'esecuzione del programma va avanti; se è presente un lock da parte di un altro thread, il thread corrente si blocca in attesa che tale lock venga rilasciato. È fondamentale tenere a mente che lock() non previene in alcun modo accessi alla variabile passatagli come parametro da parte di altri thread, ma semplicemente causa il blocco delle chiamate a lock() da parte di altri thread sulla stessa variabile. È dunque indispensabile che tutti i thread che utilizzano tale variabile condivisa ne chiedano il lock prima di utilizzarla.

Ottenuto il lock, le palline vengono assegnate in base ad una policy. Nel programma sono incluse due funzioni, policy1() e policy2(): è possibile utilizzare una oppure l'altra; la prima assegna semplicemente le palline richieste ad ogni thread/giocatore (se ve ne sono a disposizione), l'altra è un po' più complessa e, a seconda delle palline rimaste, ne può assegnare un numero inferiorie rispetto a quelle richieste. Se l'assegnazione va a buon fine, può essere effettuato il decremento della variabile. Il lock su $palline sparisce quando la chiamata a lock() esce dallo scope, in questo caso al termine della funzione. L'uscita dallo scope rappresenta l'unica via per togliere un lock ad una variabile, in quanto non esiste alcuna funzione unlock(). Notate che è necessario chiamare lock() prima dell'assegnazione delle palline secondo la policy scelta, poiché tale operazione implica la lettura del numero di palline correnti, che poi non deve essere variato da altri thread fino a che esso non viene eventualmente decrementato dal thread corrente.

La funzione restituisci_palline() è molto più semplice: dopo aver ottenuto l'obbligatorio lock su $palline, essa semplicemente incrementa $palline del numero di palline restituire (passato come parametro).


Estensioni

Numero massimo di partite

Si potrebbe definire una variabile di configurazione che indichi il numero massimo di partite che ogni thread/giocatore può fare. Al momento della creazione del thread (cioè all'inizio della sub giocatore()), andrebbe generato un numero casuale compreso tra 1 ed il numero massimo di partite. Il loop dovrebbe poi essere modificato in modo da giocare solo il numero di partite definito dal numero casuale. In questo modo si garantirebbe un termine all'esecuzione, altrimenti eterna, del programma.

Coda per giocatori in attesa

Al momento, se le palline non sono disponibili, un giocatore attende un tempo predeterminato e poi ritorna a chiederle. Questo sistema non garantisce che il primo giocatore a cui sono negate sia il primo a cui saranno poi concesse. Si potrebbe dunque prevedere una coda, in cui vengono inseriti i giocatori a cui vengono rifiutate le palline, nell'ordine in cui essi si sono presentati a chiederle. Quando un giocatore viene/ritorna a chiedere le palline, viene controllata la sua posizione sulla coda e, in caso ci siano altri davanti a lui, gli vengono negate, oppure gli viene assegnato un numero di palline tale che quelli in coda davanti a lui non si trovino senza al loro ritorno.

Possibilità, per un thread/giocatore, di rifiutare le palline

Se il club, per qualche motivo, deve concedere un numero di palline inferiore a quello richiesto dal giocatore, si può prevedere che quest'ultimo le rifiuti, in quanto non sufficienti per permettergli di completare una partita. In questo caso sarebbe probabilmente necessari definire un numero di palline minimo richiesto da ciascun giocatore.