[monitor] agenti ordinati

Ci sono numAgenti agenti che si muovono nello ‘spazio’ di dimesione x,y. Inizialmente sono posizionati in ordine inverso nella prima riga:

.9.8.7.6.5.4.3.2.1.0.
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .

Ogni agente si muove di una posizione (anche in diagonale) per raggiungere lo stato finale:

. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
.0.1.2.3.4.5.6.7.8.9.

La gestione degli spostamenti avviene tramite un opportuno monitor Spazio con i seguenti metodi:

  • void register(int n, int x, int y): ‘registra’ l’agente n nella posizione x,y. Questo metodo viene invocato una sola volta quando gli agenti vengono creati. Serve per inizializzare lo spazio nella configurazione iniziale.
  • boolean move(int n, int x, int y, int dx, int dy): muove l’agente n dalla posizione x,y alla posizione x+dx, y+dy. Il valori dx e dy sono nel range [-1,1] in quanto gli agenti si spostano di una sola posizione. Se la posizione è occupata l’agente attende. Il metodo ritorna false nel caso l’agente n non sia nella posizione x,y.
  • int getAgent(int x, int y): ritorna l’id dell’agente nella posizione x,y. Se la posizione è vuota ritorna -1. Questo metodo viene usato per stampare la situazione ed eseguire test.

Scopo della prova è implementare il monitor ‘Spazio’ come una classe Java il cui costruttore prende in input le dimenzioni x,y dello spazio di gioco (es. Spazio(10,10)) e con i tre metodi sopra descritti. Utilizzare il programma di test riportato qui sotto.

Programma di test

import java.util.HashSet;
import java.util.Set;

public class Test extends Thread {
  private static final int numAgenti =10; 	// numero agenti
  private static final int x=10, y=10; 		// dimensione spazio di gioco

  private final int num; 	// id dell'agente
  private final Spazio s; 	// monitor spazio di gioco
  private int my_x,my_y;
 
  // costruttore: salva id, monitor e posizione iniziale dell'agente
  Test(int num, Spazio s) {
    this.num = num;
    this.s = s;
    this.my_x = numAgenti -1 - num;
    this.my_y = 0;
  }
  
  public void run() {
    try {
      code();
    } catch (InterruptedException e) {
      System.out.println("Agente numero "+num+" interrotto!!");
    }
  }
  
  // codice dei thread
  void code() throws InterruptedException {
  	int dx, dy, i, j, a;

  	if (num == numAgenti) {
  		// questo thread stampa solo la situazione e controlla interferenze
  		// vedere nel ramo 'else' per il codice degli agenti
  		boolean done = false;
  		Set <Integer>check = new HashSet <Integer>();

		// attende che tutti gli agenti siano registrati  		
  		sleep(1000);

  		// controlla la registrazione
  		for (i=0;i<x;i++)
  			if (s.getAgent(i,0) != numAgenti-1-i) {
  				System.out.println("Errore: l'agente " + i + " non e' registrato correttamente");
  				System.exit(1);
  			}

  		// stampa e controlla la situazione ogni secondo
  		while(!done){
			// stampa
			check.clear(); // svuota l'insieme di id
		    synchronized(s) {
			    System.out.println("====");
			    for (j=0;j<y;j++) {
					for (i=0;i<x;i++) {
						a = s.getAgent(i,j);
						if (a == -1)
							System.out.print(". ");
						else {
							System.out.print("."+a);
              if (check.contains(a)) {
                System.out.println("Errore: l'agente " + a + "e' presente 2 volte!");
                System.exit(1);
              } else // lo aggiungiamo
							 check.add(a);
						}
					}
					System.out.println(".");
					// se tutti gli agenti sono sull'ultima linea
					if (j+2 == y && check.isEmpty())
						done = true;
				}
			}

			// controlla che non ci siano overlap: tutti gli agenti devono essere presenti
			if (check.size() != numAgenti) {
				// manca qualche agente!
				System.out.println("Errore: sono presenti solo gli agenti " + check);
		  		System.exit(1);
			}

			// se tutti gli agenti sono sull'ultima riga controlla che siano nell'ordine
			// giusto
			if (done) {
				for (i=0;i<x;i++)
		  			if (s.getAgent(i,y-1) != i) {
		  				System.out.println("Errore: l'agente " + i + " non e' posizionato correttamente");
		  				System.exit(1);
  					}
			} else
				sleep(1000);
		}
		// se non siamo usciti prima il test e' superato
		System.out.println("Tutti gli agenti sono posizionati correttamente");

  	} else {
  		// questo sono gli agenti

	    // si registra
	    s.register(num,my_x,my_y);
	    
	    // il giocatore e' pronto attende che tutti si registrino
	    System.out.println("Agente numero "+num+" registrato!");
	    sleep(500);

	    // qui avvengono le mosse
	    while (my_y != y-1) {
		    sleep(1000); // si muovono tutti assieme ogni secondo

		    // calcola la mossa
		    dy = 1; // scende sempre di una posizione
		    if (num == my_x)
		    	dx = 0; // posizione giusta, non si muove orizzontalmente
		    else {
			    dx = (num - my_x) / Math.abs(num - my_x); // -1,1 a seconda della necessita'
		    }

		    // prova a fare la mossa
		    if (!s.move(num,my_x,my_y,dx,dy)) {
		    	System.out.println("Agente numero "+num+ ": la posizione non corrisponde!!");
		    	System.exit(1);
		    }

		    // aggiorna la posizione
		    my_x += dx;
		    my_y += dy;

	    } 
	    
	  }
	}    

	public static void main(String argv[]) throws InterruptedException {
		int j;
	    Spazio s = new Spazio(x,y); // crea il monitor
	    
	    // crea i thread dei vari colori/numeri
	   	for (j=0; j<=numAgenti; j++) {
	        (new Test(j,s)).start();
	      }
  
	}	
}


7 thoughts on “[monitor] agenti ordinati”

  1. Ho provato una soluzione per l’esercizio in questo modo:
    (Non ho fatto nessun controllo sul fatto che si potessero muovere per più di una posizione ma ho fatto si che se mi trovo nella posizione 9,9 con 1,1 finisco in 0,0 anche se non so quanto sia giusto

    public class Spazio {
        private int spazio[][];//matrice per le posizioni
        private int righe;//variabile dove salvo il numero di righe, non si sa mai
        private int colonne;//variabile dove salvo il numero di righe, non si sa mai
        public Spazio(int x, int y){
            int i,j;
            
            this.spazio=new int[x][y];//inizializzo la matrice
            this.righe=x;//salvo le righe
            this.colonne=y;//salvo le colonne
            for(i=0;i<x;i++){
                for(j=0;j<y;j++){
                    this.spazio[i][j]=-1;//pongo tutti gli elementi della matrice a -1 per rendere visibile che è vuota
                }
            }
        }
        void register(int n, int x, int y){
         //‘registra’ l’agente n nella posizione x,y. 
         // Questo metodo viene invocato una sola volta quando gli agenti vengono creati. 
         // Serve per inizializzare lo spazio nella configurazione iniziale.*/
            this.spazio[x][y]=n;
        }
        
        synchronized boolean  move(int n, int x, int y, int dx, int dy){
            // Il metodo è synchronized ovvero dentro un mutex, muove l'agente n da
            // x,y a x+dx,y+dy. Se la posizione è occupata attendo con una wait in
            // ciclo while, quando è possibile muovere eseguo una notify. Il metodo
            // ritorna false se l'agente n non si trova veramente nella posizione x,y
            //
            
            if( this.getAgent(x, y)!=n)
                return false;
            else{
                while(this.getAgent((x+dx)%this.righe, (y+dy)%this.colonne)!=-1)
                    try {
                    wait();
                } catch (InterruptedException ex) {
                    System.out.println("ERRORE WAIT ");
                }
                notify();
                this.spazio[x][y]=-1;
                this.spazio[(x+dx)%this.righe][(y+dy)%this.colonne]=n;
                return true;
            }
                
       }
                
        int getAgent(int x, int y){
            /*Ritorna l’id dell’agente nella posizione x,y, -1 se è vuota*/
            return this.spazio[x][y];
        } 
    }
    
  2. La mia soluzione.
    Speriamo che anche l’ esame sia così! 😛

    public class Spazio{
    
    	int[][] tabella;
    	
    	public Spazio(int x, int y){
    		int i,j;
    		tabella=new int[x][y];
    		/* Inizializzo le celle a -1*/
    		for(i=0;i<x;i++)
    			for(j=0;j<y;j++)
    				tabella[i][j] = -1;
    	}
    	
    	synchronized void register(int n, int x, int y){
    		tabella[x][y] = n;
    	}
    	
    	synchronized boolean move(int n, int x, int y, int dx, int dy) throws InterruptedException{
    		if(n != tabella[x][y])
    			return false; // l' agente non è nella poszione n
    		while(tabella[x+dx][y+dy] != -1)
    			wait();
    		tabella[x][y] = -1;
    		tabella[x+dx][y+dy] = n;
    		notifyAll();
    		return true;
    	}
    	
    	synchronized int getAgent(int x, int y){
    		return tabella[x][y]; // Posso restituire direttamente la cella
    	}
    }
    
  3. @Andrea: OK non serviva che chiudessi il gioco modulo righe,colonne. Gli agenti non vanno mai fuori dai bordi

    @Loris: OK ma commenta! Prendete l’abitudine di commentare sempre il codice via via che lo scrivete.

  4. Dovrebbe essere tutto ok, sembra funzionare bene 🙂

    public class Spazio {
    	int matrice[][]; //matrice delle posizioni
    	
    	public Spazio(int x, int y){
    		matrice = new int[x][y];
    		for (int i = 0; i < x; i++) {
    			for (int j = 0; j < y; j++) { //inizializzo tutte le caselle a -1 (vuote)
    				matrice[i][j] = -1;
    			}
    		}
    	}
    	/** ‘Registra’ l’agente n nella posizione x,y.
    	 *   Questo metodo viene invocato una sola volta quando gli agenti vengono creati.
    	 *   Serve per inizializzare lo spazio nella configurazione iniziale.
    	 */
    	void register(int n, int x, int y){
    		this.matrice[x][y] = n;		
    	}
    	/** Muove l’agente n dalla posizione x,y alla posizione x+dx, y+dy.
    	 *  Il valori dx e dy sono nel range [-1,1] in quanto gli agenti si spostano di una sola posizione.
    	 *  Se la posizione è occupata l’agente attende. Il metodo ritorna false nel caso l’agente n non sia nella posizione x,y.
    	 * @throws InterruptedException 
    	 */
    	synchronized boolean move(int n, int x, int y, int dx, int dy) throws InterruptedException{
    		if(dx < -1 || dx > 1 || dy < -1 || dy > 1 || matrice[x][y] != n){
    			return false;  //se il passo è troppo lungo o l'agente n non corrisponda alle coordinate ritorno false
    		}
    		while(matrice[x+dx][y+dy] != -1){ //finché la casella su cui voglio muovermi è occupata, aspetto
    			wait();
    		}
    		matrice[x+dx][y+dy] = n; //mi sposto sulla nuova casella
    		matrice[x][y] = -1; //svuoto la casella precedente
    		notify();
    		return true;
    	}
    		
    	/** Ritorna l’id dell’agente nella posizione x,y.
    	 *  Se la posizione è vuota ritorna -1.
    	 *   Questo metodo viene usato per stampare la situazione ed eseguire test.
    	 */
    
    	int getAgent(int x, int y){
    		return this.matrice[x][y]; //mi basta ritornare la casella (le vuote sono già a -1)
    	}
    	
    }
    
  5. Ecco anche la mia soluzione!

    public class Spazio {
    
    	/** Campi: 
    	 * - board è lo spazio dove si muovono gli agenti 
    	 * - sx e sy sono le dimensioni della board
    	 */
    	private int sx; 
    	private int sy;
    	private int[][] board;
    
    	/** Costruttore: 
    	 * - La board è di dimensioni date, x e y; 
    	 * - la board è inizialmente tutta a -1 (non c'è nessun agente).
    	 */
    	public Spazio(int x, int y) {
    		this.sx = x;
    		this.sy = y;
    		board = new int[x][y];
    		for (int i = 0; i < sx; i++) {
    			for (int j = 0; j < sy; j++) {
    				board[i][j] = -1;
    			}
    		}
    	}
    
    	// Metodi */
    
    	/** Register: per registrare l'esistenza degli agenti sulla board */
    	public synchronized void register(int n, int x, int y) {
    		board[x][y] = n;
    	}
    
    	/**
    	 * Move: muove l’agente n dalla posizione x,y alla posizione x+dx, y+dy. 
    	 * - I valori dx e dy sono nel range [-1,1] in quanto gli agenti si spostano di
    	 * una sola posizione. - Se la posizione è occupata l’agente attende. 
    	 * - Il metodo ritorna false nel caso l’agente n non sia nella posizione x,y.
    	 */
    
    	public synchronized boolean move(int n, int x, int y, int dx, int dy) throws InterruptedException {
    		/**
    		 * Condizione di blocco: 
    		 * - Se la posizione d'arrivo non è libera (c'è un agente, quindi c'è un numero >= 0), il thread attende;
    		 */
    		while (board[x + dx][y + dy] >= 0) {
    			wait();
    		}
    		// Quando la posizione d'arrivo si libera...
    		board[x + dx][y + dy] = n; // ...riposiziono l'agente nella nuova casella
    		if (board[x][y] == n) { //se l'agente era presente nella posizione precedente...
    			board[x][y] = -1; //...lo "cancello" dalla board...
    			notifyAll(); //..e notifico gli altri thread
    			return true;
    		} else {
    			return false; //ritorno false se l'agente era nella posizione sbagliata
    		}
    	}
    
    	/**
    	 * getAgent() ritorna l’id dell’agente nella posizione x,y. Se la posizione
    	 * è vuota ritorna -1. Questo metodo viene usato per stampare la situazione
    	 * ed eseguire test.
    	 */
    	public synchronized int getAgent(int x, int y) {
    		int val;
    		if (board[x][y] < 0) {
    			val = -1;
    		} else
    			val = board[x][y];
    		return val;
    	}
    }
    
    
  6. La mia soluzione è molto simile alle vostre, ho usato però notify() anziché notifyAll() come ha fatto anche Andrea. In questo caso quale dei due è più corretto?

    public class Spazio {
        private int[][] matrix; // matrice che rappresenta lo spazio
        
        public Spazio(int w, int h) {
            this.matrix = new int[w][h]; // crea una matrice w x h
            for(int i = 0; i < w; i ++)
                for(int j = 0; j < h; j ++)
                    matrix[i][j] = -1; // inizializza tutte le celle a -1
        }
        
        /*
         * ‘registra’ l’agente n nella posizione x,y. Questo metodo viene
         * invocato una sola volta quando gli agenti vengono creati. Serve
         * per inizializzare lo spazio nella configurazione iniziale.
         */
        public synchronized void register(int n, int x, int y) {
            this.matrix[x][y] = n; // l'agente n occupa la cella m[x][y]
        }
        
        /*
         * muove l’agente n dalla posizione x,y alla posizione x+dx, y+dy.
         * Il valori dx e dy sono nel range [-1,1] in quanto gli agenti si
         * spostano di una sola posizione. Se la posizione è occupata
         * l’agente attende. Il metodo ritorna false nel caso l’agente n
         * non sia nella posizione x,y.
         */
        public synchronized boolean move(int n, int x, int y, int dx, int dy) {
            if(this.matrix[x][y] != n) // se l'agente non si trova nella cella m[x][y]
                return false; // operazione fallita
            else {
                while(this.matrix[x + dx][y + dy] != -1) { // finche' la cella m[x][y] e' occupata
                    try {
                        this.wait(); // l'agente aspetta
                    }
                    catch(InterruptedException e) {
                        System.err.println("InterruptedException: " + e.getMessage());
                    }
                }
                this.matrix[x + dx][y + dy] = n; // sposta l'agente n nella nuova posizione
                this.matrix[x][y] = -1; // libera la posizione precedente
                this.notify(); // avvisa un'altro agente che puo' avanzare
                return true; // operazione riuscita
            }
        }
        
        /*
         * ritorna l’id dell’agente nella posizione x,y. Se la posizione è
         * vuota ritorna -1. Questo metodo viene usato per stampare la
         * situazione ed eseguire test.
         */
        public synchronized int getAgent(int x, int y) {
            return this.matrix[x][y]; // restituisce il valore della cella m[x][y]
        }
    }
    
  7. @Roberta: la verifica della presenza dell’agente è meglio farla prima del wait. Inutile attendere per poi ritornare false

    @Gabriele: OK

    @Lorenzo: meglio usare notifyAll quando hai thread che attendono eventi differenti. notify potrebbe sbloccare un thread che si riblocca e magari altri che potrebbero procedere attendono inutilmente. Di fatto in java usi spesso notifyAll avendo un’unica coda di attesa. Usi notify quando in effetti è indifferente quale thread viene sbloccato (coda in cui i thread attendono tutti lo stesso evento).

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.