TP 4 - Mémoires transactionnelles

Retour à la page de l'UE

Ce TP n'est pas à rendre.

Exercice : implémentation d'une STM

Le but de cet exercice est d'implémenter une STM (Software Transactional Memory) basique en Java. Nous allons suivre l'algorithme vu en cours.

Nous allons commencer par créer quelques classes basiques.

Question 1. Commencez par implémenter créer une classe Value qui représentera une valeur de votre mémoire transactionnelle. Celle-ci possèdera deux entiers, value et counter. Vous pouvez ajouter un ou des constructeurs ainsi qu'une fonction toString().
Question 2. Créez ensuite une classe Memory qui possèdera un tableau de Values, ainsi qu'une horloge clock (un entier). Ajoutez un constructeur qui permettra d'allouer une mémoire de taille quelconque. Le tableau sera rempli de Values qui auront la valeur zéro dans leur compteur. La classe Memory possèdera aussi un champ statique memory, qui sera une instance d'elle-même, avec une taille de 1024.
Question 3. Créez finalement une classe vide TransactionAbort, qui ne fera qu'étendre Exception.

Nous avons maintenant besoin d'une structure de données pour gérer les read sets et les write sets. Nous utiliserons pour cela la classe ValueSet suivante:

class ValueSet {
    // Tableau contenant toutes les valeurs du read/write set
    public Value map[];
    // Tableau contenant les indices utilisés dans le tableau map.
    public int   elements[];
    // Nombre d'indices utilisés.
    public int   n_elements;

    // Constructeur
    public ValueSet(int max) {
        this.map = new Value[max];
        this.elements = new int[max];
    }

    // Récupérer la valeur à un indice.
    Value get(int idx) {
        // On renvoie juste la valeur à l'indice donné (sera peut-être null).
        return map[idx];
    }

    // Mettre une valeur à un indice.
    boolean set(int idx, Value val) {
        // Si l'index est déjà utilisé, on renvoie true (val est ignoré).
        if(get(idx) != null)
            return true;

        // Sinon, on enregistre l'indice comme utilisé...
        elements[n_elements++] = idx;

        // ...et on met la valeur à cet indice.
        map[idx] = val;

        return false;
    }

    // Effacer le set.
    void clear() {
        // Seuls les indices utilisés pointent vers des valeurs non-nulles.
        for(int i=0; i < n_elements; i++)
            map[elements[i]] = null;
        n_elements = 0;
    }
}
Question 4. Ajoutez la classe ValueSet à votre projet.

Il est maintenant temps de commencer à implémenter la classe principale de notre STM. Vous pouvez utiliser le squelette suivant :

class Transaction {
    private ValueSet writeSet;
    private ValueSet readSet;
    private int      clock;

    private Transaction() {
        int mem_size = Memory.memory.values.length;
        writeSet = new ValueSet(mem_size);
        readSet  = new ValueSet(mem_size);
    }

    public static ThreadLocal<Transaction> Transaction =
        new ThreadLocal<Transaction>() {
            protected synchronized Transaction initialValue() {
                return new Transaction();
            }
        };

    public void abort() throws TransactionAbort {
        // À implémenter...
    }

    public void begin() {
        // À implémenter...
    }

    public int read(int idx) throws TransactionAbort {
        // À implémenter...
    }

    public void write(int idx, int value) throws TransactionAbort {
        // À implémenter...
    }

    public void commit() throws TransactionAbort {
        synchronized(Memory.memory) {
            if(!readSet.checkRead(clock)) {
                readSet.clear();
                writeSet.clear();
                abort();
            }
            if(!writeSet.checkWrite(clock)) {
                writeSet.clear();
                abort();
            }
            Memory.memory.clock++;
        }
    }
}

Il va maintenant valloir implémenter les différentes fonctions.

Question 5. Commencez par implémenter les fonction abort() et begin(). La première ne fait que renvoyer une exception, et la deuxième, qui correspond au début d'une transaction, ne fait que recopier l'horloge globale dans l'horloge locale.
Question 6. Implémentez la fonction read(). L'idée est la suivante : si la Value se trouve dans le write set, on la renvoie. Sinon, on récupère la Value en mémoire, et on l'ajoute au read set. Si le compteur de la Value est strictement inférieur à l'horloge locale, tout s'est bien passé et on la renvoie. Sinon on avorte la transaction.
Question 7. Implémentez la fonction write(). L'idée est la suivante : si la Value se trouve dans le write set, on la récupère, on met à jour son attribut value. Sinon, on récupère la Value en mémoire. Si le compteur de la valeur est strictement inférieur à l'horloge locale, on ajoute une copie de la Value au write set, puis on met à jour son attribut value. Sinon, on avorte la transaction.

Votre STM est presque entièrement implémentée ! Il ne reste plus qu'à gérer le commit. Celui-ci est déjà presque implémenté : il vous faut simplement ajouter deux fonctions checkRead() et checkWrite() à ValueSet.

Question 8. Implémentez la fonction checkRead(). L'idée est de parcourir les indices utilisés par le read set, et de renvoyer false (conflit) ssi le compteur de l'une des valeurs est supérieur ou égal à l'horloge locale. Vous profiterez aussi du parcours pour effacer le read set (en cas d'erreur, le parcours sera incomplet mais le read set est rééffacé dans la fonction commit()).
Question 9. Implémentez la fonction checkWrite(). L'idée est de parcourir les indices utilisés par le write set, et de renvoyer false si le compteur de l'une des valeurs est supérieur ou égal à l'horloge locale. Sinon, les valeurs du write set sont copiées dans la mémoire globale, avec la valeur de l'horloge globale. De la même manière que précédemment, dans cette deuxième boucle, vous effacerez le write set.
Question 10. Ajoutez deux compteurs statiques qui compteront le nombre de commits et d'aborts d'une transaction.

Il est maintenant temps de tester votre programme... Vous pouvez pour cela utiliser ce fichier.

Question 11. Votre STM fonctionne-t-elle comme prévu ? Main.java est assez basique : s'il vous reste du temps, implémentez un test un peu plus évolué.