Il fut un temps, ce temps n'étant pas encore révolu puisqu'il couvre des débuts d'UNIX à FreeBSD 4 et Linux 2.4, ou la grande majorité des *nix utilisait un algorithme d'ordonancement souvent nommé "decay". On trouvera la description d'un tel algorithme dans le chapitre 10 de Understanding the linux kernel mais aussi celui de FreeBSD 4.
Depuis quelque temps une classe d'algorithme nouveau fait son emerge dans l'ordonancement de tache. Ce type d'algorithme est nommé "event driven". Avant les ordonanceurs avait une complexite en 0(n) [n nombre de processus/threads dans le systeme]. Pour BSD par exemple on était obligé de parcourir l'ensemble de la liste de processus toute les secondes. Quand on pense que Ingo Molnar a lancer 110 000 threads sur un 2.5 y'a six mois ca laisse songeur :-)
Bref a ma connaissance ingo Molnar a été le premier a implemente un ordonnanceur "event driven" sur un système d'exploitation grand publique. Le principe de ceux ci est d'eviter tout parcour de la liste et d'avoir un complexite en O(1).
Pour faire dans les grosses lignes on utilise deux files de processus. L'une des deux files est la file courante. Quand un processus a utiliser tout le temps qui lui etait imparti on le passe dans l'autre file. quand la file courante est vide on swap les deux files. Tout cela c'est du O(1) partout.
Ingo Molnar fut le premier, suivit de près par Jeff Robertson qui a écrit... ULE. Ils utilisent le même concept. Après il faut être très niait pour croire que ce son Ingo Molnar ou Jeff Robertson sont les inventeurs de ce principe. Il doit y avoir quelques dizaine de papier présentant des algorithmes similaires. Voila celui qui correspond au code d'Ingo Molnar
Pour l'ordonnanceur de linux il n'y a pas de papier officiel il me semble. J'ai rapidement fait un commentaire du code de celui-ci dans un projet de DEUG. Ceux que ca interesse peuvent consulter
[il s'agit d'un brouillon nullement destine a etre mis en ligne, si vous voyez des fautes je suis preneur]
Donc je ne vois pas le problème, ni l'histoire des licences qui ressort. C'est bizarre mais ce sont les mêmes qui crient au FUD pour SCO et commencent a sortir plus ou moins n'importe quoi pour les autres. Et j'ai lu le code de molnar il y'a 7 mois, celui de Jeff il y'a 2 mois... si quelqu'un peu me trouver du code commun entre les deux ca m'interesse, par ce que moi j'ai pas vu.
Sur ce, je conseil a tout ceux qui perdent leur temps a troller stupidement d'aller lire un peu de code ca fait du bien des fois. Et non il n'y a rien de revolutionnaire dans les algorithmes utilisés, de plus tout ceux qui ont deja suivit le developpement d'un ordonanceur savent que c'est une semaine pour l'écrire, un an pour le régler et virer tout les problèmes. Le code n'est pas transposable comme certain aimerait le croire.
# Re: FreeBSD pompe sur Linux 2.6 !
Posté par ckyl . En réponse au journal FreeBSD pompe sur Linux 2.6 !. Évalué à 8.
Premièrement la partie technique :
Il fut un temps, ce temps n'étant pas encore révolu puisqu'il couvre des débuts d'UNIX à FreeBSD 4 et Linux 2.4, ou la grande majorité des *nix utilisait un algorithme d'ordonancement souvent nommé "decay". On trouvera la description d'un tel algorithme dans le chapitre 10 de Understanding the linux kernel mais aussi celui de FreeBSD 4.
http://madchat.org/netadm/kern/kern.bsd/the_freebsd_process_schedul(...)
http://madchat.org/netadm/kern/kern.linux/ch10.html(...)
Depuis quelque temps une classe d'algorithme nouveau fait son emerge dans l'ordonancement de tache. Ce type d'algorithme est nommé "event driven". Avant les ordonanceurs avait une complexite en 0(n) [n nombre de processus/threads dans le systeme]. Pour BSD par exemple on était obligé de parcourir l'ensemble de la liste de processus toute les secondes. Quand on pense que Ingo Molnar a lancer 110 000 threads sur un 2.5 y'a six mois ca laisse songeur :-)
Bref a ma connaissance ingo Molnar a été le premier a implemente un ordonnanceur "event driven" sur un système d'exploitation grand publique. Le principe de ceux ci est d'eviter tout parcour de la liste et d'avoir un complexite en O(1).
Pour faire dans les grosses lignes on utilise deux files de processus. L'une des deux files est la file courante. Quand un processus a utiliser tout le temps qui lui etait imparti on le passe dans l'autre file. quand la file courante est vide on swap les deux files. Tout cela c'est du O(1) partout.
Ingo Molnar fut le premier, suivit de près par Jeff Robertson qui a écrit... ULE. Ils utilisent le même concept. Après il faut être très niait pour croire que ce son Ingo Molnar ou Jeff Robertson sont les inventeurs de ce principe. Il doit y avoir quelques dizaine de papier présentant des algorithmes similaires. Voila celui qui correspond au code d'Ingo Molnar
http://www.usenix.org/events/usenix01/nieh.html(...)
Pour ULE on regardera
http://madchat.org/netadm/kern/kern.bsd/ULE.pdf(...)
Pour l'ordonnanceur de linux il n'y a pas de papier officiel il me semble. J'ai rapidement fait un commentaire du code de celui-ci dans un projet de DEUG. Ceux que ca interesse peuvent consulter
http://mistral.unice.fr/~mathieuc/sched/book.html#AEN470(...)
[il s'agit d'un brouillon nullement destine a etre mis en ligne, si vous voyez des fautes je suis preneur]
Donc je ne vois pas le problème, ni l'histoire des licences qui ressort. C'est bizarre mais ce sont les mêmes qui crient au FUD pour SCO et commencent a sortir plus ou moins n'importe quoi pour les autres. Et j'ai lu le code de molnar il y'a 7 mois, celui de Jeff il y'a 2 mois... si quelqu'un peu me trouver du code commun entre les deux ca m'interesse, par ce que moi j'ai pas vu.
Sur ce, je conseil a tout ceux qui perdent leur temps a troller stupidement d'aller lire un peu de code ca fait du bien des fois. Et non il n'y a rien de revolutionnaire dans les algorithmes utilisés, de plus tout ceux qui ont deja suivit le developpement d'un ordonanceur savent que c'est une semaine pour l'écrire, un an pour le régler et virer tout les problèmes. Le code n'est pas transposable comme certain aimerait le croire.