Laboratorio di Informatica Applicata

Laboratorio di Programmazione ad Oggetti

Roberto Sassi
Universit� degli studi di Milano - Dipartimento di tecnologie dell'informazione

• Lez1e2
• Lez3e4
• Lez5e6
• Lez7e8
• Lez9e10
• Lez11e12
• Lez13e14
• Lez15e16
• Lez17e18
• Lez19e20
• Lez21e22
• Lez23e24

Lezione in Laboratorio 2

Venerd�, 5 Dicembre 2008

Metodi ricorsivi in Java

Abbiamo spesso invocato un metodo nel corpo di un altro metodo (ad esempio, lo abbiamo fatto all'interno del corpo del metodo main). � possibile invece che un metodo chiami se stesso?

Quando una funzione chiama se stessa, implicitamente o esplicitamente, la funzione � detta ricorsiva. Il concetto non � solo legato alla programmazione. Anche in matematica esistono funzioni che vengono definite in maniera ricorsiva. Ad esempio il fattoriale di un numero pu� essere definito ricorsivamente come:

• 0! = 1
• n! = n(n-1)!

Come calcolo il fattoriale di 2? 2! = 2 × 1! e 1! = 1 × 0! = 1 × 1. La stessa idea pu� essere applicata ad un qualunque numero n. Java permette di scrivere metodi ricorsivi. Implementiamo lo stesso calcolo in un programma Java.

import javax.swing.*;

class CalcolaFattoriale {
  public static void main (String[] args) {
    String stringaInput;
    int numero;

    stringaInput = JOptionPane.showInputDialog("Inserisci n");
    numero = Integer.parseInt(stringaInput);

    JOptionPane.showMessageDialog(null, 
      "n! � " + fattoriale(numero));

    System.exit(0);
  }

  public static int fattoriale(int n) {
    if(n == 0)
      return 1;
    else
      return n*fattoriale(n-1);
  }

}

Ci� che si ottiene con un metodo ricorsivo lo si pu� ottenere con un ciclo. Vediamo ad esempio come potrebbe essere riscritto il metodo fattoriale().

  public static int fattoriale(int n) {
    int f=1;
    for(int i=1; i<=n; i++) f*=i;
    return f;
  }

La ricorsione porta spesso a scrivere codice pi� efficace ed elegante ma:

• sullo stack n copie dei parametri formali (una copia per ogni chiamata alla funzione);
• esecuzione pi� lenta (il controllo deve essere passato via via alla funzione ricorsiva).

Parametri sulla linea di comando

Tutte le volte che abbiamo dichiarato un metodo main(), lo abbiamo sempre fatto con la sintassi:

  public static void main (String[] args)  ...

Cosa � args? args � un array di oggetti String che vengono eventualmente popolati dalla JVM prima dell'invocazione del metodo main(). Il valore che essi contengono viene specificato dall'utente quando invoca la class. Ad esempio se la classe miaClasse viene invocata con

  java miaClasse arg0 arg1 arg2
  

args verr� inizializzato ad un array di 3 stringhe contenenti rispettivamente "arg0", "arg1" e "arg2". Il valore delle tre stringhe potr� essere utilizzato all'interno del nostro programma per modificarne il funzionamento. L'array args esiste comunque anche se l'utente non fornisce alcun parametro sulla linea di comando; nel tal caso args.length sar� uguale a 0. Per definizione le stringhe sulla linea di comando sono intervallate da spazi. Se volete inserire il parametro "arg 0" (notate lo spazio) dovete "proteggerlo" utilizzando le virgolette doppie:

  java miaClasse "arg 0" arg1 arg2
  

Threads concorrenti [cenni]

In un programma come nella vita di tutti i giorni � talvolta necessario fare pi� cose allo stesso tempo. Questo tipo di attivit� dal punto di vista della programmazione sono dette concorrenti. Java a differenza di altri linguaggi incorpora direttamente all'interno della gerarchia di classi alcuni strumenti adatti a gestire in modo semplice il multithreading. Come ricorderete dall'esame di sistemi operativi, pi� thread concorrenti condividono la stessa memoria.

La classe fondamentale a cui faremo riferimento � la classe Thread. Per costruire uno o pi� thread concorrenti:

1. Per prima cosa dovremo definire quale sia il "task", l'obiettivo del nostro thread. Per farlo basta scrivere una classe che implementi l'interfaccia Runnable e cio� preveda un metodo public void run(). Il metodo verr� invocato dal thread una volta in esecuzione. Il metodo run() deve contenere tutto quanto desideriamo faccia il nostro metodo.
2. Quindi dobbiamo istanziare un oggetto di classe Thread costruito a partire dal nostro oggetto che implementa l'interfaccia Runnable. Il thread una volta creato non � tuttavia in esecuzione (non � nello stato "ready").
3. Infine dobbiamo invocare sull'oggetto di classe Thread il metodo start(). Tale metodo indica allo scheduler Java che il thread � "ready" cio� pronto per essere eseguito. Lo scheduler quando lo riterr� opportuno far� partire il processo (capiremo meglio in seguito).

Vediamo con un esempio quanto descritto. I due thread seguenti scrivono sulla console due parole ad intervalli casuali.

class PingPong {
  public static void main(String[] args) {
    Runnable task1 = new Scrivi("PING");
    Runnable task2 = new Scrivi("pong");
    
    Thread t1 = new Thread(task1);
    Thread t2 = new Thread(task2);
    
    t1.start();
    t2.start();
  }
}

// Definisce un task
class Scrivi implements Runnable {
  String messaggio;
  static private int NUMERO_VOLTE = 20;
  
  public Scrivi(String m) {
    this.messaggio=m;
  }
  
  public void run() {
    for(int i=1; i<=NUMERO_VOLTE; i++) {
      System.out.print(this.messaggio + " ");
      try {
        Thread.sleep((int)(Math.random()*20));
      }
      catch(InterruptedException e) {
        System.out.println(e);
      }
    }
  }
}

Un possibile output sulla console �:

>java PingPong
PING pong PING pong PING PING pong pong PING PING pong pong PING pong PING PING
pong PING PING pong PING pong PING PING PING pong PING pong PING pong pong PING 
PING pong PING pong pong pong pong pong 

Il metodo di classe Thread.sleep(numeroMs) forza il thread in esecuzione a diventare inattivo per il numero di millisecondi specificato. Al termine del periodo di inattivit� il thread ritorna nello stato "ready" e quando sar� il suo turno, lo scheduler Java lo rimetter� in esecuzione. Il metodo ritorna un eccezione InterruptedException che deve essere trattata obbligatoriamente.

Priorit� dei thread

Anche in Java i thread possono avere diverse priorit� di esecuzione. Lo scheduler preferir� eseguire quei thread che hanno pi� alta priorit�, facendo attendere gli altri. Quando un thread viene inizializzato ha di default priorit� Thread.NORM_PRIORITY (5), ma � possibile cambiare il valore di priorit� con il metodo di istanza setPriority(livelloPriorit�). Le priorit� massima e minima sono rispettivamente Thread.MAX_PRIORITY (10) e Thread.MIN_PRIORITY (1).

La maggior parte dei sistemi operativi gestisce la concorrenza in modalit� "timeslicing" (solo alcuni la gestiscono in modalit� "preemptive", ma li trascuriamo in questo corso). In tali sistemi il tempo di esecuzione del processore viene ripartito in unit� elementari, dette "quanti" (della durata di alcuni millisecondi). Lo scheduler di volta in volta assegna un quanto di esecuzione al thread in attesa con pi� alta priorit�. � utile sapere che esiste il metodo di classe Thread.yield() che rende inattivo il thread corrente (quello che lo invoca) riportandolo nello stato "ready". Attenzione perch� il metodo pu� lasciare eseguire solo thread di uguale priorit� (se esitono): infatti il thread non sarebbe in esecuzione se esistessero thread di priorit� pi� elevata (a meno che siano in stato di "sleep") n� lo scheduler sceglier� di eseguire thread di priorit� pi� bassa visto che esiste almeno un thread (quello corrente) che deve essere eseguito. � importante avere presente quindi che se esistono thread a pi� alta priorit�, quelli di priorit� inferiore possono anche non essere eseguiti in modo indefinito!

Gestire la concorrenza

Talvolta � necessario sincronizzare tra loro le attivit� di thread differenti. Vediamolo con un esempio. Due thread devono accedere ad un area di memoria comune, per semplicit� un intero. Un thread scrive un numero progressivo nella cella comune e l'altro lo legge.

class CaricoScarico {
  public static int NUMERO_VOLTE = 10;

  public static void main(String[] args) {
    // Istanzia la cella condivisa
    CellaCondivisa miaCella = new CellaCondivisa();
    
    Runnable task1 = new Carico(miaCella);
    Runnable task2 = new Scarico(miaCella);
    
    Thread t1 = new Thread(task1);
    Thread t2 = new Thread(task2);
    
    t1.start();
    t2.start();
  }
}

/** 
  * Definisce il task di scrittura nella cella condivisa
  */
class Carico implements Runnable {
  private CellaCondivisa riferimentoCella;
  
  public Carico(CellaCondivisa r) {
    this.riferimentoCella=r;
  }
  
  public void run() {
    for(int i=1; i<=CaricoScarico.NUMERO_VOLTE; i++) {
      riferimentoCella.setCella(i);
      System.out.println("CARICO: " + i);
      try {
        Thread.sleep((int)(Math.random()*100));
      }
      catch(InterruptedException e) {
        System.out.println(e);
      }
    }
  }
}

/** 
  * Definisce il task di lettura nella cella condivisa
  */
class Scarico implements Runnable {
  private CellaCondivisa riferimentoCella;
  
  public Scarico(CellaCondivisa r) {
    this.riferimentoCella=r;
  }
  
  public void run() {
    for(int i=1; i<=CaricoScarico.NUMERO_VOLTE; i++) {
      System.out.println("          SCARICO: " + riferimentoCella.getCella());
      try {
        Thread.sleep((int)(Math.random()*100));
      }
      catch(InterruptedException e) {
        System.out.println(e);
      }
    }
  }
}

/**
  * La classe definisce oggetti di tipo CellaCondivisa che verranno letti sia dal
  * thread di lettura che da quello di scrittura
  */
class CellaCondivisa {
  int cella;
  
  public void setCella(int numero) {
    this.cella=numero;
  }    
  
  public int getCella() {
    int valore=this.cella;
    return valore;
  }
}

Come si nota da un output della classe, alcuni numeri non vengono mai letti dal thread di scarico, perch� nel frattempo il thread di carico li ha sovrascritti. Oppure alcuni numeri vengono scaricati pi� di una volta.

>java CaricoScarico
CARICO: 1
          SCARICO: 1
          SCARICO: 1
CARICO: 2
          SCARICO: 2
CARICO: 3
CARICO: 4
          SCARICO: 4
CARICO: 5
          SCARICO: 5
          SCARICO: 5
          SCARICO: 5
CARICO: 6
CARICO: 7
CARICO: 8
          SCARICO: 8
CARICO: 9
          SCARICO: 9
CARICO: 10
          SCARICO: 10

Per poter gestire la concorrenza, Java permette di dichiarare un metodo istanza come synchronized. Per gli oggetti che manifestano tali metodi, Java ha un monitor, cio� compila una lista dei thread che desiderano utilizzarli e permette solo ad un metodo alla volta di ottenere un lock sull'oggetto, cio� l'autorizzazione ad utilizzare tali metodi. Attenzione che il lock � sull'oggetto non sul metodo!

Una volta che un thread ha ottenuto un lock su di un oggetto, se qualche condizione non � soddisfatta, pu� decidere di mettersi in attesa su quell'oggetto. Per farlo di utilizza il metodo istanza wait(timeMs) dell'oggetto che � stato sincronizzato (non del thread!). Un thread che � nello stato di "wait" vi rimane fino a che � trascorso il tempo indicato nell'invocazione del metodo o fino a che qualche altro thread invoca i metodi notify() e notifyAll(). Al termine dello stato di "wait" il processo ritorna ad essere "ready" e lo scheduler Java quando sar� il suo turno gli conceder� nuovamente un quanto di esecuzione.

Attenzione che i metodi wait(), notify() e notifyAll() vengono ereditati direttamente dalla classe Object! Vediamo l'esempio di prima in cui l'accesso all'area comune di memoria � stato sincronizzato:

class CaricoScaricoSincronizzato {
  public static int NUMERO_VOLTE = 10;

  public static void main(String[] args) {
    // Istanzia la cella condivisa
    CellaCondivisa miaCella = new CellaCondivisa();
    
    Runnable task1 = new Carico(miaCella);
    Runnable task2 = new Scarico(miaCella);
    
    Thread t1 = new Thread(task1);
    Thread t2 = new Thread(task2);
    
    t1.start();
    t2.start();
  }
}

/** 
  * Definisce il task di scrittura nella cella condivisa
  */
class Carico implements Runnable {
  private CellaCondivisa riferimentoCella;
  
  public Carico(CellaCondivisa r) {
    this.riferimentoCella=r;
  }
  
  public void run() {
    for(int i=1; i<=CaricoScaricoSincronizzato.NUMERO_VOLTE; i++) {
      riferimentoCella.setCella(i);
      System.out.println("CARICO: " + i);
      try {
        Thread.sleep((int)(Math.random()*100));
      }
      catch(InterruptedException e) {
        System.out.println(e);
      }
    }
  }
}

/** 
  * Definisce il task di lettura nella cella condivisa
  */
class Scarico implements Runnable {
  private CellaCondivisa riferimentoCella;
  
  public Scarico(CellaCondivisa r) {
    this.riferimentoCella=r;
  }
  
  public void run() {
    for(int i=1; i<=CaricoScaricoSincronizzato.NUMERO_VOLTE; i++) {
      System.out.println("          SCARICO: " + riferimentoCella.getCella());
      try {
        Thread.sleep((int)(Math.random()*100));
      }
      catch(InterruptedException e) {
        System.out.println(e);
      }
    }
  }
}

/**
  * La classe definisce oggetti di tipo CellaCondivisa che verranno letti sia dal
  * thread di lettura che da quello di scrittura
  */
class CellaCondivisa {
  int cella;
  boolean daScaricare;
  
  public synchronized void setCella(int numero) {
    // Il thread che ha invocato questo metodo ha ottenuto un lock su questo oggetto
    while(daScaricare) {
      try {
        this.wait(); // metodo ereditato da Object
      }
      catch(InterruptedException e) {
        System.out.println(e);
      }
    }
    this.cella=numero;
    this.daScaricare=true;
    this.notifyAll(); // metodo ereditato da Object
  }    
  
  public synchronized int getCella() {
    // Il thread che ha invocato questo metodo ha ottenuto un lock su questo oggetto
    while(!daScaricare) {
      try {
        this.wait(); // metodo ereditato da Object
      }
      catch(InterruptedException e) {
        System.out.println(e);
      }
    }
    int valore=this.cella;
    this.daScaricare=false;
    this.notifyAll(); // metodo ereditato da Object
    return valore;
  }
}

Nell'output del thread di scarico notiamo che tutti i valori vengono letti in sequenza come desiderato. � per� possibile che, come in questo caso, il thread di scarico venga interrotto dallo scheduler Java non appena rilasciato il lock sull'oggetto miaCella e quindi che l'altro thread riesca a scrivere a monitor un nuovo valore prima di quello scaricato. Ma questo � solo un effetto estetico, nessun numero � stato perso nella sequenza di output!

CARICO: 1
          SCARICO: 1
          SCARICO: 2
CARICO: 2
CARICO: 3
          SCARICO: 3
CARICO: 4
          SCARICO: 4
CARICO: 5
          SCARICO: 5
          SCARICO: 6
CARICO: 6
CARICO: 7
          SCARICO: 7
CARICO: 8
          SCARICO: 8
CARICO: 9
          SCARICO: 9
CARICO: 10
          SCARICO: 10