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

Martedì, 4 Dicembre 2007

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 eventualemente 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 programa 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. 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 modalita "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 si "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.

>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.

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