Ce TP n'est pas à rendre.
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.
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().
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.
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;
}
}
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.
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.
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.
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.
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()).
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.
Il est maintenant temps de tester votre programme... Vous pouvez pour cela utiliser ce fichier.
Main.java est assez
basique : s'il vous reste du temps, implémentez un test un peu plus évolué.