Discussion :

[shaiHulud]

Bonjour à tous,

Je vous pose d'abord ma question précise, puis je vous raconte pourquoi elle est apparue:

Disposant d'une liste d'objets pondérés (par des floats ou int positifs), comment créer une liste L de ces objets tels que:
- Chaque objet O soit présent a peu prés len(L) *O.pondération dans L
- Chaque objet soit présent au moins une fois (sauf peut etre ceux de pondération nulles)
- L'entrelacement soit maximum (ou grand) : je veux le maximum d'objets différents et différents de O entre deux apparitions successives de O dans L (et ceux pour tous les objets O).
- De longueur pas trop importante.

Merci d'avance pour vos suggestions. Voici maintenant la petite histoire pour ceux qui ont le courage:

J'utilise les générateurs afin de simuler du threading sous Python. Le principe est le suivant:
* Un thread est un générateur
* thread.start() revient à rajouter thread à un conteneur ThreadPool
* ThreadPool est reponsable de la boucle principale de ce réacteur. Cette boucle s'occupe d'appeler successivement iter() sur chaque generateur contenu dans ThreadPool.

Une petite remarque:
J'ai découvert Twisted depuis, et j'ai réalisé qu'il s'agissait d'implémenter un réacteur,en favorisant les générateurs plutot que les callbacks. Pour l'instant j'en reste à mon implémentation, mais je passerai peut etre en Twisted un jour.

Voici le problème:

Comment définir des priorités associées à chaque thread, qui fasse que la boucle principale du réacteur apelle plus souvent les thread à haute priorité ?

J'utilise pour l'instant une solution fruste:
- Une priorité est un entier, ou None (priorité normale)
- A chaque itération n dans la boucle du réacteur, je choisis un thread avec priorité si n%priorité == 0, s'il existe, sinon je choisis le prochain thread sans priorité.

Cette solution:
- Est approximative ,mais cela ne me dérange pas : appeler un thread 12 fois en 20 sec un thread que je comptais appeler seulement 10 fois n'est pas un problème pour moi. Je n'ai pas besoin de controler exactement la priorité, seulement de manière approchée.
- Etait rapide à coder
- N'ajoute pas beaucoup de surcharge au méchanisme de réacteur (par exemple: pas besoin de stocker combien de fois chaque thread a été appelé)
- Assure l'entremèlement des tâches. Par exemple, assure que tous les threads sans priorité sont appelés une fois chacun avant d'en rappeler un une seconde fois.
- Mais elle a une limitation sérieuse. Les priorités doivent être uniques, entières et souvent des nombres premiers, car si thread1.prio divise thread2.prio, thread2 sera en général masquée. C'est problématique dès que j'ai besoin de définir la priorité de beaucoup de tâches

Je cherche à aller au plus vite tout en restant efficace (il faut que le code propre au réacteur soit rapide pour laisser au threads le temps de tourner). Je pensais à la solution suivante:
* Les priorités sont des floats.
* A chaque itération, je tire au hasard le thread à éxécuter, en tenant compte des pondérations = priorités.

Je pense que la question devient vite difficile, et je voulais avoir votre sentiment sur les points suivants:

- Il est préférable d'utiliser une librairie toute prête comme Twisted (je ne sais pas si Twisted permet de pondérer ses générateurs)

- Choisir au hasard les taches à effectuer dans un réacteur me semble être une bêtise. En effet on ne controle plus l'entremèlement des taches, et respecter exactement les probabilités n'est pas vital pour moi.

- Ce dernier point pourrait être contourné en utilisant des outils avancés de simulation aléatoire, comme une Monte-Carlo Markov-Chain (tirages non indépendants).

[dividee]

Ma proposition:
Chaque thread possède une priorité de base, et une priorité courante. Initialement, les deux valeurs sont égales. A chaque étape, le scheduler sélectionne le thread ayant la priorité courante la plus petite, et reprogramme ce thread en incrémentant la priorité courante de la priorité de base.

Dans le code ci-dessous, les threads sont stockés dans un tas (heap), ce qui devrait être assez efficace.

Exemple (Python 3):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from heapq import heapify, heappush, heapreplace
 
class Thread:
    def __init__(self, priority):
        self.priority = priority
        self._curr_prio = priority
 
    def __repr__(self):
        return 'T(%d)' % self.priority
 
    def __lt__(self, other):
        return self._curr_prio < other._curr_prio
 
class Scheduler:
    def __init__(self, threads):
        self._threads = list(threads)
        heapify(self._threads)
 
    def __iter__(self):
        return self
 
    def add(self, thread):
        threads = self._threads
        curr = threads[0]._curr_prio if len(threads) > 0 else 0
        thread._curr_prio = thread.priority + curr
        heappush(threads, thread)
 
    def next(self):
        threads = self._threads
        t = threads[0]
        t._curr_prio += t.priority
        return heapreplace(threads, t)
 
if __name__ == '__main__':
    s = Scheduler(Thread(i) for i in range(1,11))
    counts = [0]*10
    for i in range(10000):
        t = s.next()
        counts[t.priority-1] += 1
        if i < 50:
            print(t.priority, end=' ')
    print()
    for i,c in enumerate(counts):
        print('T(%d) = %d' % (i+1,c))

Résultat:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
1 2 1 3 1 4 2 1 5 1 6 3 1 2 7 1 2 1 8 4 3 9 1 2 1 10 5 1 4 2 1 6 3 1 2 1 7 3 5 1 4 2 1 8 1 2 1 9 3 6 ...
T(1) = 3415
T(2) = 1708
T(3) = 1138
T(4) = 854
T(5) = 683
T(6) = 569
T(7) = 487
T(8) = 426
T(9) = 379
T(10) = 341

Sur mon PC, un million d'itérations du scheduler prend environ 3 secondes avec 10 threads et 5 secondes avec 100 threads.

[shaiHulud]

Merci dividee pour ton aide.

Si j'ai bien compris, tu choisis à chaque itération le thread i qui minimise K(i)/priorité(i).

Merci pour l'implémentation avec heap, pour l'instant je me tapais un max() qui doit en effet être bien plus long. Je ne connais pas trop les complexités des heap. Ta méthode donne-t'elle un O(1) (par rapport an nb de threads) ?

Entre temps j'ai pondu une version similaire à la tienne, basée sur les durées plutot que sur le comptage: je sélectionne le thread qui a tourné il y a le plus longtemps: min dT(i)/priorité(i) (désolé de pas mettre mon code, il est imbriqué à plein d'autres trucs et est peu lisible)

Il me reste tout de même 2 questions:
1/ Si l'utilisateur rentre des priorités trop élevées, certains threads n'auront quasiment jamais la main (la longueur des cycles est pas controlée). De même rien n'empêche le même thread d'etre appelé plein de fois de suite, ce que je voudrais éviter. Avec ces méthodes, l'entrelacement semble peu optimal.

2/ Est ce préférable de se baser sur le comptage des appels (comme toi) ou sur les durée écoulées ? A priori pour moi, stocker le temps depuis le dernier appel n'est pas trés couteux car le scheduler update un champ clock dont se sert l'essentiel de mon programme, plutot que de rappeler time.clock(). Je penche donc pour la solution en durée dans mon cas.

[dividee]

Si j'ai bien compris, tu choisis à chaque itération le thread i qui minimise K(i)/priorité(i).

Je ne te suis pas vraiment, je ne vois pas ce qu'est K(i).
[EDIT] ah K(i) c'est le nombre d'appels du thread i ? Dans ce cas, oui, enfin plus ou moins, car dans mon code une valeur de priorité plus faible indique un thread "plus prioritaire", et c'est plutôt K(i)*priorité(i) qui est minimisé.

Je ne connais pas trop les complexités des heap. Ta méthode donne-t'elle un O(1) (par rapport an nb de threads) ?

O(log n) (n=nb de threads) car l'insertion dans un heap est O(log n).

Entre temps j'ai pondu une version similaire à la tienne, basée sur les durées plutot que sur le comptage: je sélectionne le thread qui a tourné il y a le plus longtemps: min dT(i)/priorité(i) (désolé de pas mettre mon code, il est imbriqué à plein d'autres trucs et est peu lisible)

Si je comprends bien c'est un genre de "fair scheduling", similaire à ce que fait l'ordonnanceur du noyau Linux (http://fr.wikipedia.org/wiki/Completely_Fair_Scheduler). C'est plus avancé que ma solution, si tu as pu l'implémenter en O(log n).

Il me reste tout de même 2 questions:
1/ Si l'utilisateur rentre des priorités trop élevées, certains threads n'auront quasiment jamais la main (la longueur des cycles est pas controlée).

Tu ne peux pas limiter l'intervalle de priorités valides ?
Sinon tu pourrais aussi ajuster dynamiquement la priorité des threads et donner un malus à un thread qui s'exécute longtemps...

De même rien n'empêche le même thread d'etre appelé plein de fois de suite, ce que je voudrais éviter. Avec ces méthodes, l'entrelacement semble peu optimal.

Si les priorités sont limitées à des valeurs raisonnables, je ne vois pas trop pourquoi ça poserait un problème. Mais si tu tiens vraiment à ce que le même thread ne soit pas exécuté deux fois de suite, il y a certainement moyen de modifier ton algorithme pour forcer cela.

2/ Est ce préférable de se baser sur le comptage des appels (comme toi) ou sur les durée écoulées ? A priori pour moi, stocker le temps depuis le dernier appel n'est pas trés couteux car le scheduler update un champ clock dont se sert l'essentiel de mon programme, plutot que de rappeler time.clock(). Je penche donc pour la solution en durée dans mon cas.

En théorie utiliser les durées donne une répartition plus équitable (fair) du CPU. Mais comme on est ici en Python, et que le process python est lui-même schedulé par l'OS, cela peut poser un problème, car clock() (en tout cas sous Windows), retourne le temps total écoulé (wall clock time) et pas le temps utilisé par le process Python uniquement. Si le processeur est lourdement chargé par d'autre process, cela va fausser les mesures.

[shaiHulud]

Merci pour ces éclaircissements.

Effectivement K(i) était bien le nombre d'appel au thread i.

Je pensais avoir une solution en log(N) en utilisant ton implémentation, mais ce n'est pas aussi simple pour les durées car l'incrémentation dépend de ce qu'il s'est passé sur les autres threads. Je pense donc rester en O(N). Pour mes besoins courants (un jeu vidéo), j'aurais au maximum 20 ou 30 threads.

En ce qui concerne l'entrelacement, il me semble que nos deux méthodes ont le problème suivant. Avec 2 threads par exemple, si la priorité de T1 = 2.1* priorité de T2, T1 va quasiment tout le temps être exécuté 2 fois de suite. Nos approches sont assez précises sur le respect de la priorité, ce qui se paie par un mauvais entrelacement. Je me demande comment faire l'inverse (aussi bien informatiquement que mathématiquement).

En ce qui concerne le temps mesuré (temps process ou système), je précise que je ne vise pas le thread ayant tourné le moins de temps, mais celui qui a été appelé il y a le plus longtemps (lequel des 2 est le fair scheduling ?). Du coup j'ai l'impression d'être insensible à ce faussage des mesures.

Encore merci

[dividee]

En ce qui concerne l'entrelacement, il me semble que nos deux méthodes ont le problème suivant. Avec 2 threads par exemple, si la priorité de T1 = 2.1* priorité de T2, T1 va quasiment tout le temps être exécuté 2 fois de suite. Nos approches sont assez précises sur le respect de la priorité, ce qui se paie par un mauvais entrelacement. Je me demande comment faire l'inverse (aussi bien informatiquement que mathématiquement).

Je ne comprends pas ce que tu veux. Ca me parait normal, si T1 a 2 fois la priorité de T2, qu'il soit exécuté deux fois plus souvent. S'il n'y a que deux thread, cela signifie qu'il sera exécuté deux fois de suite la plupart du temps. A quoi ça servirait de définir des priorité sinon ? Si tu veux un entrelacement optimal, tu fais un simple round-robin, pas besoin de priorités.

En ce qui concerne le temps mesuré (temps process ou système), je précise que je ne vise pas le thread ayant tourné le moins de temps, mais celui qui a été appelé il y a le plus longtemps (lequel des 2 est le fair scheduling ?). Du coup j'ai l'impression d'être insensible à ce faussage des mesures.

Tu as raison, le fair scheduling est bien basé sur "celui qui a été appelé il y a le plus longtemps". Effectivement le problème est moins grave dans ce cas, mais je ne pense pas que tu y sois complètement insensible. La surestimation du temps aura tendance à booster les threads avec une priorité élevée, il me semble, car la mesure du temps est pondérée par les priorités.

[shaiHulud]

Merci à tous

J'ai enfin trouvé ce que je cherche à faire: il s'agit des low discrepancy sequence: on respecte la loi marginale souhaitée, mais la mémoire est plus forte que pour des nombres pseudo-aléatoires. Par exemple:
http://en.wikipedia.org/wiki/Low-discrepancy_sequence

Cette solution améliore l'entrelacement par rapport aux méthodes proposées. J'ai même trouvé un package python pour les générer.


Sinon pour répondre à Dividee (que je remercie pour sa réponse):
Je connais mal le round robin. Comment puis-je y inclure des priorités ?

J'ai effectivment pris un mauvais exemple, voici ce que je voulais dire. Prends 3 thread au lieux de 2 avec un thread de priorité double: T1.prio= T2.prio = 1 et T3.prio= 2. Les méthodes en question risquent de souvent faire
T1 T2 T3 T3 T1 T2 T3 T3,...
Alors que je préférerais l'alternance
T1 T3 T2 T3 T1 T3 ...

La surestimation du temps aura tendance à booster les threads avec une priorité élevée

Certes, mais comme les priorités agissent de manière multiplicatives, et que l'effet que tu décris semble multiplicatif aussi (relatif au temps pris par le thread), je crois que ma conclusion reste valable.