Domanda Risolto Esercizi programmazione concorrente

[Not an engineer]

Salve community di inforge,
avrei bisogno di un'aiuto per la risoluzione di alcuni esercizi di programmazione concorrente in java.
Lascio qui il testo degli esercizi sperando che qualcuno possa aiutarmi.

Volevo sapere, secondo voi, qual'è l'approccio migliore con il quale affrontare questi esercizi. In particolare vorrei sapere quali thread utilizzare, quale struttura dati sia più appropriata per la classe monitor e con quali metodi gestire la sincronizzazione.

 

[Not an engineer]

Sono partito da un altro esercizio. In allegato il testo e il codice

Barbiere.java

class Barbiere extends Thread {

  private Sala sala;
  private int id;

  public Barbiere(Sala s, int i){
    super(" Barbiere ");
    sala = s;
    id = i;
  }

  public void run(){
    while(true){
      System.out.println(" Il barbiere " + id + " è pronto per servire un cliente.");
      sala.serviCliente(id);
      try{
        Thread.sleep((int)Math.random()*5001);
      }catch(InterruptedException exception){
        exception.printStackTrace();
      }
    }
  }
}

Cliente.java

class Cliente extends Thread {

  private Sala sala;
  private int id;

  public Cliente(Sala s, int i){
    super(" Cliente ");
    sala = s;
    id = i;
  }

  public void run(){
    try{
      Thread.sleep((int)Math.random()*0);
      sala.addCoda(id);
    }catch(InterruptedException exception){
      exception.printStackTrace();
    }
  }
}

Sala.java

* classe monitor */
import java.util.LinkedList;

class Sala {

  private int clienteServito;
  private int NUM_POSTI_DIVANO = 5;
  private LinkedList<Integer> divano;

  private int NUM_POSTI_SALA = 4;
  private LinkedList<Integer> sala;

  private LinkedList<Integer> cassa;

  public Sala(){
    divano = new LinkedList<>();
    sala = new LinkedList<>();
    cassa = new LinkedList<>();
  }

  public synchronized void addCoda(int id){
    System.out.println(" Arriva il cliente " + id);
    if(divano.size() < NUM_POSTI_DIVANO){
      divano.add(id);
      notifyAll();
    } else if(sala.size() < NUM_POSTI_SALA){
      sala.add(id);
      notifyAll();
    } else {
      System.out.println(" Il divano " + divano + " e la sala " + sala + " sono pieni. Il cliente " + id + " va via.");
    }
  }

  public synchronized void serviCliente(int id){
    while(divano.size() == 0){
      try{
        System.out.println(" Il barbiere " + id + " non ha nessun cliente da servire.");
        wait();
      }catch(InterruptedException e){
        e.printStackTrace();
      }
    }

    System.out.println(" Il barbiere " + id + " ottiene il cliente " + divano.getFirst());
    clienteServito = divano.removeFirst();

    /* Quando il barbiere serve i clienti seduti nel divano, il primo entrato nella sala si siede nel divano
    e succesivamente viene servito dal barbiere. */

    if(sala.size() > 0){
      divano.add(sala.removeFirst());
    }

    try{
      Thread.sleep((int)Math.random()*101);
    }catch(InterruptedException exception){
      exception.printStackTrace();
    }

    System.out.println(" Il barbiere " + id + " ha servito il cliente " + clienteServito);

    /* Una volta servito, aggiunto il cliente alla lista per il pagamento */
    cassa.add(clienteServito);
    /* Lo rimuovo dalla routine d'accesso del monitor */
    cassa.removeFirst();

    try{
      Thread.sleep((int)Math.random()*101);
    }catch(InterruptedException exception){
      exception.printStackTrace();
    }

    System.out.println(" Il barbiere " + id + " ha fatto pagare il cliente " + clienteServito);
  }
}

Main.java

class Main {
  public static void main(String[] args) {

    Sala sala = new Sala();

    int nBarbieri = 3;
    Barbiere barbieri[] = new Barbiere[nBarbieri];

    for(int i=0; i<nBarbieri; i++){
      barbieri[i] = new Barbiere(sala, i);
      barbieri[i].start();
    }

    int nClienti = 100;
    Cliente clienti[] = new Cliente[nClienti];

    for(int i=0; i<nClienti; i++){
      clienti[i] = new Cliente(sala, i);
      clienti[i].start();
      try{
        Thread.sleep((int)Math.random()*501);
      }catch(InterruptedException exception){
        exception.printStackTrace();
      }
    }
  }
}

 

[St3ve]

Anzitutto ti faccio notare che (int)Math.random() * pippo equivale a scrivere ((int)Math.random()) * pippo che fa sempre zero: tutti i tuoi sleep non servono a niente. Fai una cosa di questo tipo

Thread.sleep(5000 + (int)(Math.random()*100));

Ancora più importante, il grosso del tuo codice e tutte i meccanismi di sincronizzazione sono all'interno di Sala. Hai un unico oggetto Sala in tutto il codice quindi se un barbiere sta eseguendo serviCliente (ad esempio), nessun altro barbiere potrà eseguire serviCliente. Hai tanti threads, ma il tuo codice è seriale. Non può esserci più di un barbiere che lavora contemporaneamente, non può entrare nessun cliente se un barbiere lavora anche se la sala è mezza vuota, ecc...

Ti posto la soluzione. Non dare per scontato che sia corretta, questa roba va debuggata e pensata come si deve... io l'ho fatta di notte e non ho particolare interesse a sbattermi più di quel tanto. Di sicuro funziona meglio del tuo e spero possa servirti per capire meglio qual'è l'approccio con cui va risolto il problema: devi cercare di mantenere il lock per meno tempo possibile, devi avere una funzione lenta per simulare un carico di lavoro pesante che vuoi eseguire in modo asincrono e (cosa a cui io non ho prestato molta attenzione) devi cercare di svegliare meno gente possibile. Tutto ciò mantenendo la fairness (i.e., chi prima arriva, prima viene servito) e rispettando i requisiti dell'esercizio.

Main.java

public class Main {
    public static void main(String[] args) {
        Shop shop = new Shop();
        for (int i = 0; i < 20; i++) new Thread(new Customer(shop)).start();
        for (int i = 0; i < 3; i++) new Thread(new Barber(shop)).start();
    }
}

Shop.java

import java.util.List;
import java.util.Queue;
import java.util.ArrayList;
import java.util.ArrayDeque;

public class Shop {
    public final int STAND = 10;
    public final int COUCH = 5;
    private List<Customer> standing = new ArrayList<Customer>();
    private Queue<Customer> sitting = new ArrayDeque<Customer>();

    public synchronized boolean enter(Customer c) {
        if (standing.size() >= STAND) return false;
        System.out.println(c + " enters the shop");
        standing.add(c);
        return true;
    }

    public synchronized void sit(Customer c) {
        try {
            while (sitting.size() >= COUCH) wait();
            sitting.add(c);
            notifyAll();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public synchronized Customer customer() throws InterruptedException {
        while (sitting.size() == 0) wait();
        return sitting.remove();
    }
}

Barber.java

public class Barber implements Runnable {
    private static int count;
    public final int id;
    private Shop shop;

    public Barber(Shop shop) {
        this.id = ++count;
        this.shop = shop;
    }

    public String toString() { return "Barber " + id; }

    public synchronized void run()  {
        try {
            while (true) {
                System.out.println(this + " is waiting for customers");
                Customer c = shop.customer();    // choose the customer
                System.out.println(this + " is cutting the hair of " + c);
                synchronized(c) { c.notify(); }  // call the customer
                working();
                System.out.println(this + " is getting payed by " + c);
                synchronized(c) { c.notify(); }  // goodbye customer
            }
        } catch(InterruptedException e) {
            e.printStackTrace();
        }
    }

    public void working() {
        try {
            Thread.sleep(5000 + (int)(Math.random()*100));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Customer.java

public class Customer implements Runnable {
    private static int count;
    public final int id;
    private Shop shop;

    public Customer(Shop shop) {
        this.id = ++count;
        this.shop = shop;
    }

    public String toString() { return "Customer " + id; }

    public synchronized void run() {
        try {
            if (!shop.enter(this)) {
                System.out.println("The shop is full and " + this + " goes away");
                return;
            }

            System.out.println(this + " waits standing up");
            shop.sit(this);
            System.out.println(this + " sits on the couch");
            wait();  // wait for some barber to call me
            System.out.println(this + " is getting an haircut");
            wait();  // wait for the barber to finish me
            System.out.println(this + " exits the shop");
        } catch(InterruptedException e) {
            e.printStackTrace();
        }
    }
}

Comunque sta roba è ovviamente una variante di sleeping barber problem. Quelli sopra sono varianti di altri problemi abbastanza standard. Il mio codice potrebbe essere buggato, ma una vaga idea sulla struttura generale la puoi trovare su wikipedia o su altri siti e libri.
In generale, non mettere mai il carico di lavoro pesante in una metodo della risorsa condivisa. Funzionerà, ma diventa seriale.

 

[Not an engineer]

Gli darò un'occhiata. Grazie per la risposta

Messaggio unito automaticamente: 12 Agosto 2020

Un'altra domanda
In questo esercizio (in allegato il testo - Pizzeria) posso utilizzare un unico thread "Gruppo"? Oppure ho la necessità di utilizzare un altro thread scrittore? Per il tavolo comune conviene dichiarare una strutturati dati a parte o utilizzare sempre un'unica struttura con una costante che mi indica il numero massimo di tavoli?

 

[St3ve]

Sorry ho notato solo ora l'edit, non mi era arrivata la notifica.

In questo esercizio (in allegato il testo - Pizzeria) posso utilizzare un unico thread "Gruppo"? Oppure ho la necessità di utilizzare un altro thread scrittore? Per il tavolo comune conviene dichiarare una strutturati dati a parte o utilizzare sempre un'unica struttura con una costante che mi indica il numero massimo di tavoli?

Mi sembra un esercizio molto più semplice rispetto a quello dei barbieri.
Un thread per ogni gruppo e basta, non sono sicuro di capire la tua idea di "thread scrittore": un thread che si preoccupa di assegnare i tavoli alle persone (se è questo ciò che intendi) non ti serve. Secondo un unica classe per gestire i tavoli è sufficiente.

 

[Not an engineer]

Sorry ho notato solo ora l'edit, non mi era arrivata la notifica.


Mi sembra un esercizio molto più semplice rispetto a quello dei barbieri.
Un thread per ogni gruppo e basta, non sono sicuro di capire la tua idea di "thread scrittore": un thread che si preoccupa di assegnare i tavoli alle persone (se è questo ciò che intendi) non ti serve. Secondo un unica classe per gestire i tavoli è sufficiente.

Sì, intendevo proprio questo. Purtroppo ho ancora qualche difficoltà a risolvere questi esercizi e credo siano dovute a mie lacune sull'argomento. Spero domani, tempo permettendo, di farti vedere il mio codice (sto rifacendo in base a quello che mi hai fatto vedere)
Grazie per le rispose!

 

[Not an engineer]

Sorry ho notato solo ora l'edit, non mi era arrivata la notifica.


Mi sembra un esercizio molto più semplice rispetto a quello dei barbieri.
Un thread per ogni gruppo e basta, non sono sicuro di capire la tua idea di "thread scrittore": un thread che si preoccupa di assegnare i tavoli alle persone (se è questo ciò che intendi) non ti serve. Secondo un unica classe per gestire i tavoli è sufficiente.

Per caso sapresti darmi delucidazioni sui vari controlli da fare nell'esercizio della pizzeria? Mi riferisco in particolare al controllo sul tavolo comune e sulla composizione dei gruppi.
(L'idea è quella di ottimizzare l'occupazione nei tavoli)

Questo è quello che ho fatto io (ma manca ciò che ti ho scritto sopra)

import java.util.List;
import java.util.LinkedList;

class Pizzeria {

    private LinkedList<Gruppo> tavoli;
    public static int NUM_TAVOLI = 15;

    public Pizzeria() {
        tavoli = new LinkedList<>();
    }

    public synchronized void siedi(Gruppo g){
        while(tavoli.size() >= NUM_TAVOLI){
            try{
                wait();
            }catch(InterruptedException exception){
                exception.printStackTrace();
            }
        }

        tavoli.add(g);
        notifyAll();
    }

    public synchronized Gruppo remove(){
        return tavoli.remove();
    }
}

class Gruppo extends Thread {

    private Pizzeria pizzeria;
    private int id;
    private int composizione;

    public Gruppo(Pizzeria pizzeria, int id, int composizione){
        this.pizzeria = pizzeria;
        this.id = id;
        this.composizione = composizione;
    }

    public int getComposizione(){
        return composizione;
    }

    public void mangiando(){
        try{
            Thread.sleep(5000 + (int)(Math.random()*101));
        }catch(InterruptedException exception){
            exception.printStackTrace();
        }
    }

    public synchronized void run(){
        try{
            System.out.println(this + " arriva in pizzeria.");
            pizzeria.siedi(this);
            System.out.println(this + " si è seduto al tavolo.");
            mangiando();
            pizzeria.remove();
            System.out.println(this + " è andato via dalla pizzeria.");
        }catch(Exception exception){
            exception.printStackTrace();
        }       
    }
}

import java.util.Random;

class Main {

    public static void main(String[] args) {
        Pizzeria pizzeria = new Pizzeria(15);
        Random random = new Random();

        int nGruppi = 25;
        Gruppo gruppi[] = new Gruppo[nGruppi];
        
        for(int i=0; i<nGruppi; i++){
            gruppi[i] = new Gruppo(pizzeria, i, random.nextInt(10)+1);
            gruppi[i].start();
            try{
                Thread.sleep(1000 + (int)(Math.random()*101));
            }catch(InterruptedException exception){
                exception.printStackTrace();
            }
        }
    }
}

 

[St3ve]

Non ho totalmente chiara questa parte del testo: "una pizzeria ha N tavoli che possono ospitare 2, 4 o 6 persone ciascuno". Devo aspettarmi J tavoli da 2, K tavoli da 4 e L tavoli da 6 in modo tale che J+K+L=N; oppure devo aspettarmi N tavoli allargabili dove: se si siede 1 persona spreco 1 posto, se si siedono 2 persone ne spreco 0, se si siedono 3 spreco 1, se si siedono 4 ne spreco 0, se si siedono 5 spreco 1, se si siedono 6 ne spreco 0 e non si possono mai sedere più di 6 persone?

Nel primo caso secondo me te la puoi cavare con 3 variabili intere (tavoli2, tavoli4 e tavoli6) che partono da un numero fisso e poi calano fino a 0. Nel secondo caso puoi usare sempre quelle tre variabili, ma le fai partire da zero e fai rispettare tavoli2 + tavoli4 + tavoli6 <= N. Il tavolo comunitario lo tratti come int tavoli1 = 20; che arriva a zero (o tavoli1 che parte da 0 e arriva a 20).

Lo spreco, ovvero i posti liberi non occupabili da altri clienti, lo calcoli man mano che entra ed esce la gente. Il gruppo deve ricordarsi da quanti elementi è composto e dove è stato assegnato così che al momento di uscire puoi liberare il tavolo giusto. Se ti trovi meglio puoi anche far ricordare questa cosa a Pizzeria, ma mi sembra leggermente più complesso.

La soluzione semplice manda in starvation: i gruppi da 10 vengono superati dai gruppi da da 7 (8 e 9) sebbene entrambi ambiscono a sedersi sullo stesso tavolo. In prima fase, dimenticati di questo difetto.

 

[Not an engineer]

Io avevo pensato ad una cosa del genere
N tavoli = 15 di cui 8 da due, 4 da quattro, 2 da sei e 1 comune

I problemi che non riesco a bypassare sono:
1. I tavoli sono comunque 15 e quindi i gruppi che si siedono nel tavolo comune non vengono inseriti nella lista (dopo il 15°esimo)

import java.util.List;
import java.util.LinkedList;

class Pizzeria {

    private LinkedList<Gruppo> tavoli;
    public static int NUMERO_TAVOLI = 15;
    private int tavoliDue = 8;
    private int tavoliQuattro = 4;
    private int tavoliSei = 2;
    private int tavoloComune = 20;

    public Pizzeria(){
        tavoli = new LinkedList<>();
    }

    public synchronized void siedi(Gruppo gruppo){
        while(tavoli.size() >= NUMERO_TAVOLI){
            try{
                wait();
            }catch(InterruptedException exception){
                exception.printStackTrace();
            }
        }

        if(gruppo.getComposizione() <= 2 && tavoliDue !=0){
            tavoli.add(gruppo);
            notifyAll();
            tavoliDue --;
        } else if(gruppo.getComposizione() <= 4 && tavoliQuattro != 0){
            tavoli.add(gruppo);
            notifyAll();
            tavoliQuattro --;
        } else if(gruppo.getComposizione() <= 6 && tavoliSei != 0){
            tavoli.add(gruppo);
            notifyAll();
            tavoliSei --;
        } else if(gruppo.getComposizione() <= 10 && gruppo.getComposizione() < tavoloComune && tavoloComune !=0){
            tavoli.add(gruppo);
            notifyAll();
            tavoloComune = tavoloComune - gruppo.getComposizione();
        }
    }

Facendo così però non so come capire lo specifico gruppo a che tavolo è associato quindi non so come incrementare le variabili nel metodo remove()

 

[St3ve]

I tavoli sono comunque 15 e quindi i gruppi che si siedono nel tavolo comune non vengono inseriti nella lista (dopo il 15°esimo)

Non ho ancora letto la tua soluzione quindi non so se basta, ma puoi trattare il tavolo comune da 20 come se fossero 20 tavoli da una persona. Roba del tipo:
NUMERO_TAVOLI = 8 + 4 + 2 + 20 = 34
invece di
NUMERO_TAVOLI = 8 + 4 + 2 + 1 = 15.

Prova a vedere se ti aiuta a sbloccarti, poi mal che vada provo a risolverlo anche io.

 

[Not an engineer]

Credo che l'accesso ai tavoli del messaggio di prima sia giusto. Continuo ad avere difficoltà nel rimuovere i gruppi dai tavoli. Col fatto che un gruppo composto da 2 persone può finire in un tavolo da 4, nel momento in cui devo andare ad incrementare le variabili dei singoli tavoli non so come fare a capire di che tavoli si tratta. Pensavo di utilizzare un array dove ad ogni cella corrisponde una tipologia di tavolo.
Ad ogni modo, domani proverò nuovamente! Grazie per le risposte

ps: quel syncronized(c) che utilizzi nel metodo run a cosa serve esattamente?

 

[St3ve]

ps: quel syncronized(c) che utilizzi nel metodo run a cosa serve esattamente?

La classe Object di java implementa il meccanismo dei monitor (e.g., wait, notify e synchronized). Preso un oggetto obj, solo un thread può eseguire entrare nel blocco synchronized(obj) { /* blocco */ }. Questo ti permette di applicare il meccanismo di mutua esclusione.

Scrivere

class classe {
    public synchronized void metodo {
        // codice
    }
}

equivale a scrivere

class classe {
    public void metodo {
        synchronized(this) {
            // codice
        }
    }
}

Nel mio caso, all'interno di barber::run abbiamo:

1. prendo un cliente e sono sincronizzato sul negozio, quindi mentre prendo un cliente nessun'altro può prendere un cliente e nessun cliente può entrare o uscire dal negozio (amenoché non sono in attesa del cliente);
2. notifico il cliente che ho preso che è rimasto in attesa di essere servito (e.g., si alza e si siede sulla poltrona di lavoro);
3. lavoro;
4. notifico il cliente che ho terminato di tagliargli i capelli e può pagare e uscire dal negozio.

Quando notifico il cliente, voglio che nessun altro barbiere (thread) provi a interagire (in mutua esclusione) con il cliente e voglio che il cliente non stia facendo (in mutua esclusione) niente. Praticamente, voglio essere l'unico che parla con il cliente e voglio che il cliente non stia facendo niente che gli richieda un po' di tempo per se stesso senza che nessuno lo disturbi. Voglio avere un accesso esclusivo al cliente, per questo synchronized(c).

Il synchronized su barber::run non serve a niente e si può rimuovere. L'avevo messo perché in teoria (non l'ho implementato) il barbiere potrebbe rimanere in attesa che il cliente cerchi i soldi e lo paghi o roba del genere. Alla fine ho messo la println su Barber invece che su Customer, quindi il synchronized sul metodo non serve a niente. Puoi rimuoverlo e ci guadagni qualche microsecondo in performance.

 

[Not an engineer]

Sto provando nuovamente e,
ho inizializzato le variabili a 0 per i tavoli "normali" e a 20 quella del cavolo comune. L'accesso lo garantisco così

public synchronized void siedi(Gruppo g){
        while(tavoliDue + tavoliQuattro + tavoliSei == TOT){
            try{
                wait();
            }catch(InterruptedException e){
                e.printStackTrace();
            }
        }

        if(g.getComposizione() <= 2 && tavoliDue < 8){
            tavoli.add(g);
            notifyAll();
            tavoliDue ++;
        } else if(g.getComposizione() <= 4 && tavoliQuattro < 4){
            tavoli.add(g);
            notifyAll();
            tavoliQuattro ++;
        } else if(g.getComposizione() <= 6 && tavoliSei < 2){
            tavoli.add(g);
            notifyAll();
            tavoliSei ++;
        } else if(g.getComposizione() <= 10 && g.getComposizione() <= tavoloComune){
            tavoli.add(g);
            notifyAll();
            tavoloComune = tavoloComune - g.getComposizione();
        }
    }

Il problema è quando sempre quello, quando vado a rimuovere il gruppo dal tavolo non so a quale sia associato e quindi non so quale variabile decrementare
Inoltre, il testo dice che il gruppo si pone in wait quando non trova posto neanche nel tavolo comune, quindi credo che quel while vada rivisto

 

[St3ve]

Non elegantissimo, ma dovrebbe farti capire una possibile soluzione.

public class Restaurant {
    public final String name;

    private Map<Customers, Integer> assign = new HashMap<Customers, Integer>();
    private Map<Integer, Integer> tables = new HashMap<>(Map.of(1, 20, 2, 2*8, 4, 4*4, 6, 6*2));

    public Restaurant(String name) { this.name = name; }

    public synchronized Optional<Entry<Integer, Integer>> bestFit(Customers c) {
        return tables.entrySet().stream()
            .filter(e -> e.getKey() >= c.quantity && e.getValue() >= c.quantity)
            .min(Map.Entry.comparingByKey());
    }

    public synchronized void enter(Customers c) throws InterruptedException {
        Entry<Integer, Integer> entry;
        while ((entry = bestFit(c).orElse(null))) wait();
        System.out.println(c + " sits in " + (entry.getKey() == 1 ? "shared" : entry.getKey()));
        assign.put(c, entry.getKey());
        tables.put(entry.getKey(), entry.getValue() - (entry.getKey() == 1 ? c.quantity : entry.getKey()));
    }

    public synchronized void exit(Customers c) {
        int t = assign.remove(c);
        tables.put(t, tables.get(t) + (t == 1 ? c.quantity : t));
        notifyAll();
    }

    public String toString() { return name; }
}

Se vuoi ti giro anche il resto del codice, ma quello non dovrebbe essere un problema. Per essere più puliti si potrebbe anche definire la classe Table, etc... ma diciamo che a noi interessano di più i meccanismi di sincronizzazione quindi ce la sbrighiamo in fretta con gli interi.

 

[Not an engineer]

Problema risolto, chiudo!