Examen 2h sur machine

Santa's Sack

Dans cet exercice, on se propose de créer une classe représentant la hotte de Père Noël (Sack). Pour simplifier, on ne mettra dans la hotte que le poids des cadeaux en kilogrammes donc des int. À la création de la hotte, on donnera le poids maximal que la hotte peut porter. Comme toutes les hottes dignes de ce nom, notre hotte devra être thread-safe.

La classe Sack aura les méthodes suivantes :

• Une méthode putGift(int weight) qui essaie de rajouter un cadeau de poids weight et qui bloque si l'ajout du cadeau n'est pas possible.
• Une méthode int takeGift() qui prend (donc retire) le dernier cadeau rajouté et renvoie son poids. Si la hotte est vide, la méthode bloque jusqu'à ce qu'il y ait un cadeau à enlever.

Codez la classe thread-safe Sack décrite précédemment en utilisant des ReentrantLock.

Pour tester votre code, vous écrirez un main qui :

• crée une hotte d'une capacité de 500 kg,
• démarre un thread qui, en boucle, dort 100 ms puis ajoute un cadeau de 10 kg et un cadeau de 5 kg.
• puis, qui en boucle dort 200 ms puis retire un cadeau et affiche son poids.

Écrire le main demandé.

On veut maintenant rajouter une méthode List<Integer> takeGiftsUntil(int weight) qui va prendre (donc retirer) des cadeaux dans la hotte en commençant toujours par le plus récemment ajouté jusqu'à avoir pris au moins weight kilogrammes de cadeaux. Dès que le poids est atteint ou dépassé, la méthode renvoie la liste des poids des cadeaux retirés. La méthode prend les cadeaux dès qu'elle le peut et attend d'avoir au moins le poids total demandé. On pourra ainsi demander 1000 kg de cadeaux dans une hotte de 500 kg. Autrement dit, la méthode prend des cadeaux puis, si nécessaire, attend que de nouveaux cadeaux soient rajoutés pour continuer.

On veut aussi rajouter une méthode int weightNeeded() qui renvoie la somme des poids encore nécessaires pour satisfaire tous les threads qui sont en train d'exécuter la méthode takeGiftsUntil.

Rajoutez les deux méthodes demandées à votre classe Sack.

Dans le main, on va en plus du code précédent,

• démarrer deux threads qui, en boucle dorment 1000 ms et appellent takeGiftsUntil(1000) et ensuite affichent la somme des poids des cadeaux ainsi recupérés
• et un thread qui en boucle dort 500 ms et affiche la valeur renvoyée par weightNeeded().

Rajoutez les threads demandés dans votre main.

On veut maintenant spécifier le comportement de nos méthodes en cas d'interruption.

Si les méthodes putGift et takeGift sont interrompues, elles lèvent une InterruptedException.

Si la méthode takeGiftsUntil est interrompue, elle ne s'arrête pas, mais elle devient prioritaire pour retirer des cadeaux. Tant qu'elle n'a pas fini, aucun autre thread ne peut retirer de cadeau : si un thread est en train d'appeler une des méthodes takeGiftsUntil ou takeGift, ces méthodes sont bloquées en attendant que cette méthode soit terminée). Si d'autres threads ont été interrompus pendant qu'ils appelaient la méthode takeGiftsUntil, ils sont eux aussi prioritaires et peuvent continuer à enlever des paquets. Pour signaler que le thread a été interrompu, la méthode takeGiftsUntil positionnera le statut d'interruption avant de renvoyer la liste des poids des cadeaux.

Copiez votre classe Sack dans une classe SackWithInterruption est implanter la gestion des interruptions demandée.

PokemonFactory

Dans cet exercice, on vous fournit une petite API factice qui permet d'attraper des Pokemon, de les mettre dans des Pokeball et de mettre plusieurs Pokeball dans une boîte (Crate). Le code de l'API est dans PokeAPI.java. Vous n'avez pas besoin de lire le code de l'API, toutes les informations nécessaires sont disponibles dans la brève description ci-dessous.

Un Pokemon possède un nom (name) et une rareté (rarity) comprise entre 0 et 5.

public record Pokemon(String name, int rarity){..}    

La méthode static Pokemon capture() permet d'attraper un Pokemon.

Une Pokeball possède un Pokemon pokemon et une valeur (value) entre 0 et 10.

public record Pokeball(Pokemon pokemon, int value){..}

La méthode static Pokeball trap(Pokemon pokemon) permet de mettre un Pokemon dans une Pokeball.

Une Crate contient au plus 6 Pokeball qui ont toutes la même valeur. Elle est crée grâce à la méthode static Crate box(List<Pokeball> pokeballs).

Le code ci-dessous donne un exemple d'utilisation de l'API.

public static void main(String[] args) throws InterruptedException {
    var pokemon = PokeAPI.capture();
    System.out.println(pokemon); // Pokemon[name=Ronflex, rarity=1]
    var pokeball = PokeAPI.trap(pokemon); 
    System.out.println(pokeball); // Pokeball[pokemon=Pokemon[name=Ronflex, rarity=1], value=2]
    var crate = PokeAPI.box(List.of(pokeball));
    System.out.println(crate); // Crate[content=[Pokeball[pokemon=Pokemon[name=Ronflex, rarity=1], value=2]]]
}    

Dans cet exercice, on vous demande dans le main d'une classe PokemonFactory de :

• démarrer 5 threads qui, en boucle, vont capturer des Pokemon en utilisant la méthode PokeAPI.capture,
• deux threads qui, en boucle, vont mettre les Pokemon capturés dans des Pokeball avec la méthode PokeAPI.trap. L'un des threads s'occupera des Pokemon dont la rareté est comprise entre 0 et 4 et l'autre, des Pokemon de rareté 5.
• pour chacune des 11 valeurs possibles pour les Pokeball, on démarrera deux threads chargés de mettre en Crate les Pokeball de la valeur correspondante. Ces threads attendrons d'avoir 6 Pokeball pour créer une Crate avec la méthode PokeAPI.box et afficheront la Crate produite avant de passer à la confection d'une nouvelle Crate.

Tous les threads doivent afficher leur nom et leurs actions.

Écrivez la classe PokeFactory demandée.

On veut maintenant que, lorsque que l'on a réussit à produire la première Crate de Pokeball de valeur 10, le programme s'arrête. On demande que les threads qui produisent les Crate produisent une dernière Crate, même incomplète, et l'affiche avant de s'arrêter.

Copiez votre code dans une classe PokeFactoryStop et modifier le main pour obtenir le comportement demandé.

MaxRecorder en lock-free

Dans cet exercice, on cherche à créer une classe MaxRecorder thread-safe que l'on crée avec une certaine capacité size. Cette classe possède une méthode process qui prend en paramètre un entier positif et qui renvoie vrai si l'entier proposé fait partie des size plus grands nombres qui ont été proposés lors d'appels à la méthode process depuis la création de la classe.

var recorder = new MaxRecorder(2);
System.out.println(recorder.process(1)); // => true   
System.out.println(recorder.process(2)); // => true
System.out.println(recorder.process(0)); // => false
System.out.println(recorder.process(5)); // => true
System.out.println(recorder.process(4)); // => true
System.out.println(recorder.process(3)); // => false

Normalement, pour gérer les cas d'égalité, on compare d'abord les valeurs et si elles sont égales, on considère comme plus grande valeur, celle qui a été proposée le plus tôt.
Mais pour simplifier l'exercice, on supposera que la méthode process n'est jamais appelée deux fois avec exactement la même valeur. Vous n'avez pas à le vérifier et cela vous évitera de vous arrachez les cheveux sur les cas d'égalité.

Donnez une implémentation thread-safe dans le cas où size vaut 1 dans une classe MaxRecorderOne qui n'utilise ni section critique, ni verrou, en utilisant la classe VarHandle.

• La méthode process va simplement dire si la valeur qui lui est passée en argument est la plus grande vue jusqu'à présent.
• On rappelle que la méthode process n'accepte en argument que des entiers positifs, ce qui peut légèrement simplifier l'implantation.
• Comme la classe MaxRecorderOne a une size fixée à 1, son constructeur ne prend pas de paramètre.

On veut maintenant traiter le cas d'une capacité positive quelconque.

On vous propose de partir de l’implantation assez naïve et non-threadsafe ci-dessous. L'idée est de conserver dans le tableau maximums les size éléments maximums rencontrés jusque là. Comme process n'accepte que des entiers positifs, initialement toutes les cases du tableau maximums peuvent être initialisée à -1. La méthode process(e) cherche le plus petit des maximums vus et le compare à la valeur value qui lui est passée en paramètre. Si la valeur passée est plus grande, on remplace la plus petite valeur du tableau maximums par le paramètre value et on renvoie vrai, sinon on renvoie faux.

import java.util.Arrays;

public class MaxRecorderBogus {

    private final int[] maximums;

    public MaxRecorderBogus(int size) {
        if (size < 1) {
            throw new IllegalArgumentException("Invalid size");
        }
        this.maximums = new int[size];
        Arrays.setAll(maximums, __ -> -1); // the elements processed are >=0, we can safely initialize with -1
    }

    /**
     * Return the index of the first occurrence of the minimal element in a
     * non-empty array
     */
    private static int findIndexOfMinimum(int[] t) {
        if (t.length == 0) {
            throw new IllegalArgumentException();
        }
        var min = t[0];
        var index = 0;
        for (var i = 1; i < t.length; i++) {
            if (t[i] < min) {
                min = t[i];
                index = i;
            }
        }
        return index;
    }

    public boolean process(int value) {
        if (value < 0) {
            throw new IllegalArgumentException("Argument must be >=0");
        }
        var indexMin = findIndexOfMinimum(maximums);
        if (value > maximums[indexMin]) {
            maximums[indexMin] = value;
            return true;
        }
        return false;
    }
}

var recorder = new MaxRecorder(2);
System.out.println(recorder.process(1)); // => true   maximums = [1,-1]
System.out.println(recorder.process(2)); // => true   maximums = [1,2]
System.out.println(recorder.process(0)); // => false  maximums = [1,2]
System.out.println(recorder.process(5)); // => true   maximums = [5,2]
System.out.println(recorder.process(4)); // => true   maximums = [5,4]
System.out.println(recorder.process(3)); // => false  maximums = [5,4]

On veut une implantation thread-safe qui n'utilise ni section critique, ni verrou. Il vous faudra donc un accès volatile aux différentes cases du tableau maximums. Pour cela, vous utiliserez la classe AtomicIntegerArray.
Implémenter cette version dans une classe MaxRecorderLockFree.