1. Gestion explicite des files d’attente

1.1. Généralité

La solution la plus simple (mais pas la plus élégante) pour résoudre réellement un problème de synchronisation en Java consiste en la gestion explicite des requêtes bloquées. On définit ainsi une classe Requête, qui contient les paramètres de demande. Quand une requête ne peut pas être satisfaite, on crée un nouvel objet Requête, on le range dans une structure de données, et l’activité demandeuse se bloque sur l’objet Requête. Quand une activité modifie l’état de sorte qu’il est possible qu’une (ou plusieurs) requête soit satisfaite, elle parcourt les requêtes en attente pour débloquer celles qui peuvent l’être. La condition de satisfaction et la technique de parcours permet d’implanter précisément la stratégie souhaitée.
La première difficulté provient de la protection des variables partagées par toutes les activités (état du système et des files d’attente) tout en assurant un blocage indépendant; cela conduit à l’apparition d’une «fenêtre», où une activité tente de débloquer une autre activité avant que celle-ci n’ait effectivement pu se bloquer. La deuxième difficulté réside dans l’absence d’ordonnancement lors des réveils, ce qui nécessite que la mise-à-jour de l’état soit faite dans l’activité qui réveille et non pas dans l’activité qui demande. On obtient alors la structure suivante (en italique, ce qui concerne spécifiquement le problème résolu: l’allocateur de ressources (voir Exemple):

1.2. Exemple

class Allocateur {
    
    private class Requête {
        boolean estSatisfaite = false;
        int nbDemandé;         // paramètre d’une requête
        Requête (int nb) { nbDemandé = nb; }
    }

    // les requêtes en attente de satisfaction
    java.util.List lesRequêtes = new java.util.LinkedList();
    int nbDispo = …;        // le nombre de ressources disponibles

    void allouer (int nbDemandé) throws InterruptedException
    {
        Requête r = null;
        synchronized (this) {
            if (nbDemandé <= this.nbDispo) { // la requête est satisfaite immédiatement
                this.nbDispo -= nbDemandé;    // maj de l’état
            } else {            // la requête ne peut pas être satisfaite
                r = new Requête (nbDemandé);
                this.lesRequêtes.add (r);
            }
        }
        // fenêtre => nécessité de estSatisfaite (plus en excl. mutuelle donc une autre
        // activité a pu faire libérer, trouver cette requête et la satisfaire avant
        // qu’elle n’ait eu le  temps de se bloquer effectivement).
        if (r != null) {
            synchronized (r) {
                if (! r.estSatisfaite)
                  r.wait();
                // la mise à jour de l’état se fait dans le signaleur.
            }
        }
    } // allouer

    public void libérer (int nbLibéré)
    {
        synchronized (this) {
            this.nbDispo += nbLibere;
            // stratégie bourrin : on réveille tout ce qu’on peut.
            java.util.Iterator it = lesRequêtes.iterator();
            while (it.hasNext()) {
                Requête r = (Requête) it.next();
                synchronized (r) {
                    if (r.nbDemandé <= this.nbDispo) { // requête satisfaite !
                        it.remove();
                        this.nbDispo -= r.nbDemandé; // maj de l’état
                        r.estSatisfaite = true;
                        r.notify();
                    }
                }
            }
        }
    } // libérer
}