Journal Un OS réécrit son code à la volée

Posté par  (site web personnel) .
Étiquettes : aucune
0
7
juin
2007
Il arrive que quelques extraterrestres échouent sur notre planète, qui sans eux serait parfois monotone.
Il y a 20 ans déjà Henry Massalin s'est amusé à créer sa propre machine autour d'un 68000, la quamachine, en l'honneur de son compagnon koala, dont l'onomatopée lui servant de communication se résume souvent à un "Qua !".
Basée à quelques années plus tard sur deux 68030, elle disposait de 256 Ko de Rom, 2,5 Mo de Ram, 4ko de mémoire vidéo, un circuit son maison, et poussait jusqu'à 50 Mhz les deux 68030, grace à un système tordu permettant de multiplexer la mémoire.

Il a créé Synthesis, son propre OS, écrit avec amour en assembleur 68000. Synthesis est conçu comme une sorte de Noyau Mach avec des fonctionalités de type Unix.
Mais le plus intéressant est certainement la capacité de ce noyau à réécrire son code à la volée.
Henry Massalin, créateur de musique électronique souhaitait disposer d'un OS capable de tenir la charge face à ses besoins créatifs, il lui fallait donc un OS sur optimisé, disposant de fonctionalités temps réelles performantes.

L'optimisation de son code repose sur plusieurs idées.

Par exemple, il va détecter un calcul dans lequel un paramètre est un 1 ou un 0, dans ce cas
A=1
B*A+A*A devient B+1, on économise 2 multiplications.

Plus généralement, il propose le raisonnement suivant :

Suposons que l'on doive exécuter une fonction
Fbig(p1,...,pn)
On détecte que p1 est une constante.

On va donc chercher à factoriser Fbig pour écrire
F2(p1) qui renvoi une fonction Fsmall prenant (p2,..., pn) en paramètres.

Le but est que l'on ait pour m exécutions:
Cout(F2)+m*Fsmall(p2,...,pn) < m*Fbig(p1,...,pn)


Autre idée est de supprimer les jump dans le code dus à une structuration de celui-ci basée sur des spécifications. Autrement dit, il inline le code à la volée.

Le noyau est basé sur des sortes d'objets, les Quajets, ces objets ne supportent pas l'héritage, et sont codés en assembleur.
cela permet de structurer le code de belle façon.

La thèse de Massalin resselle aussi une intéressante contribution sur la concurrence et la synchronisation.
Il désirait en effet éviter de désactiver les interruptions à tout bout de champ sur son système, éviter d'utiliser des systèmes à verrou pour gérer la concurence sur sa machine dotée de deux 68030.
J'ai pas encore tout lu et donc compris, je n'en dirai donc pas plus.

Il développe aussi une conception intéressante de l'ordonancement à "gain fin", qui consiste d'après ce que j'ai compris, à ne plus baser l'ordonancement sur le temps, mais sur les interruptions. Ce qui semble être une bonne idée.
Pareil, je n'ai pas lu, je n'en dirai pas plus.


Tout cela n'est pas tout jeune, le document a été écrit en 1992.

Le lien : http://www.cs.columbia.edu/~library/TR-repository/reports/re(...)

  • # Curryfication

    Posté par  (site web personnel) . Évalué à 10.

    En d'autres termes, une fonction F : <x_1, ..., x_n> → y devient une fonction F_1 : x_1 → (<x_2, ..., x_n> → y), soit une fonction prenant un argument et renvoyant une fonction prenant n-1 arguments, etc...

    Ca s'appelle la curryfication, et c'est aussi ce qui explique qu'une fonction prenant deux entiers et renvoyant un entier ait usuellement le type int → int → int au lieu de (int * int) → int.

    Enfin bref, functional programming rulez da world, rien de nouveau sous le soleil :-)

    • [^] # Re: Curryfication

      Posté par  . Évalué à -2.

      > Enfin bref, functional programming rulez da world, rien de nouveau sous le soleil :-)

      Je n'ai pas tout compris. Ça signifie que tu crois que les langages objets ce n'est que de la fumisterie amenée à domination par Sun avec Java et étendue par Microsoft avec C# ?

      • [^] # Re: Curryfication

        Posté par  (site web personnel) . Évalué à 2.

        Faudrait savoir, tu parles de java/C# ou de langages objet ?

        Sinon, smalltalk et ruby sont très chouettes et il y a de bonnes idées dedans, mais ça ne vaut pas haskell ou ocaml niveau élégance ou efficacité.

        Quant à java et assimilés, la raison pour laquelle ils sont si répandus est la même que l'explication de pourquoi les chefs sont toujours les gens les plus médiocres.

        • [^] # Re: Curryfication

          Posté par  . Évalué à 8.

          C'est quand même aussi parceque les entreprises qui les soutiennent on réussi à fournir un framework étendu, une bonne documentation et une communauté active....

          Le framework en particulier est bien plus important que les qualités intrinséques du langage à l'heure du choix.

        • [^] # Re: Curryfication

          Posté par  . Évalué à 7.

          Tu prends tout à l'envers.
          Java et C# sont des langages médiocres parce qu'ils sont répandus.
          smalltak, ocaml ou haskell sont très chouettes parce qu'ils ne sont utilisé que par une poignée de vrai geek (ou nerds, je ne sais plus la différence maintenant)

    • [^] # Re: Curryfication

      Posté par  (site web personnel) . Évalué à 3.

      J'aurais appelé cela de l'évaluation partielle. Une application directe du théorème s-n-m*. Une des 3 caractéristiques des systèmes acceptables de programmation. (les 2 autres caractéristiques étant la Turing-complétude et l'existence d'une fonction universelle).

      Bref, ça n'a rien de propre aux langages fonctionnels...

      *: fr.wikipedia connait ce théorème sous le nom de "théorème d'itération" de Kleene.

      • [^] # Re: Curryfication

        Posté par  (site web personnel) . Évalué à 2.

        Oui, c'est bien la même idée. Et en effet, s-n-m nous dit que tout langage raisonnable saura le faire, mais on sait aussi qu'on peut jouer à quake sur une machine de Turing. Ce n'est pas pour autant que ce sera facile, ou même raisonnablement possible de le faire.

        En l'occurence, pour que la curryfication ait un sens, il faut que les fonctions soient des objets de première classe, sinon tu n'auras même pas la notion de "renvoyer une fonction". D'où les liens avec langages fonctionnels.

    • [^] # Re: Curryfication

      Posté par  . Évalué à 1.

      Currying qui sera possible dans C# 3 actuellement en beta (puisque ça en parle en-dessous)

      • [^] # Re: Curryfication

        Posté par  . Évalué à 1.

        <troll>alors que dans n'importe quel langage décent, on peut l'ajouter soi-même en 2 minutes</troll>

  • # OS ou compilateur ?

    Posté par  (site web personnel) . Évalué à 2.

    Je ne comprend pas le lien entre OS et recompilation. Et quand est-ce que le code est optimisé ? En temps réel ?

    • [^] # Re: OS ou compilateur ?

      Posté par  (site web personnel) . Évalué à 3.

      L'OS est entièrement écrit en Asm 68000 et génère en temps réel de l'assembleur 68000

      « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker

      • [^] # Re: OS ou compilateur ?

        Posté par  (site web personnel) . Évalué à 3.

        Bon, je n'ai pas lu, mais il ne ma parait pas du tout évident que :

        temps(optimisation) + temps(exécution_code_optimisée) < temps(execution_code_pas_optimisé)

        • [^] # Re: OS ou compilateur ?

          Posté par  (site web personnel) . Évalué à 5.

          Ça devient intéressant quand

          temps(optimisation) + n * temps(exécution_code_optimisé) < n * temps(exécution_code_pas_optimisé)

          quelque soit n entier naturel non nul.

          C'est ce principe qui est utilisé par le compilateur JIT des JVMs modernes.

          • [^] # Re: OS ou compilateur ?

            Posté par  . Évalué à 5.

            > quelque soit n entier naturel non nul.

            ou plutot pour tout n superieur a un N qu'on espère exister et le plus petit possible...

  • # Hum...

    Posté par  . Évalué à 4.

    A la lecture du titre, j'ai compris quelque chose de plus mieux qu'une "banale" optimisation a la volée du code. En effet, a quand le système d'exploitation qui réécrit vraiment ses parties les plus externes ou les plus voués aux optimisations ?

    Je m'explique. Avec les avancés techniques dans le domaines de l'intelligence artificielles (programme générationnelle adaptatifs, etc) il devient possible de specifier la forme d'un code, son utilisation, de faire mouler le tout sur quelques centaines de milliers de générations et d'avoir finalement un truc pas mal codé. Cela se fait depuis un certains temps avec les algorithmes génétiques, (et certaines autres métaheuristiques), alors pourquoi ne pas généraliser ?

    Deux catégories particulières se prêtent bien a ce type de réecritures : D'abord les parties nécéssitant une forte optimisation (piles, gestionnaire de priorité, parties hard du noyeau), et les drivers. En effet, ces derniers ne sont finalement qu'une interface entrée/sortie. Il n'y aurait qu'a specifier l'entrée, la sortie, et mouliner le tout.

    Bref, bref...

    • [^] # Re: Hum...

      Posté par  (site web personnel) . Évalué à 1.

      C'est vrai qu'on pourrait aller nettement plus loin qu'à l'époque où le problème était plutot de réussir à mixer deux fichiers wav en temps réel...

      Il y a un américain qui a travaillé sur l'évolution d'algorithme par génie génétique (je ne retrouve plus le numéro de Pour la Science contenant l'article en question), au bout de 1000 h de calcul, il arrivait à obtenir quelque chose. C'était avec des PII 300 en cluster...

      Je pense que c'est une voie intéressante, mais qu'il faudrait peut être y connecter nu filtre, une taxinomie en particulier, qui permette de filtrer la recherche à taton que feront les algo génétique dans l'espace solutions.
      Ca permettrait à un algo génétique de faire évoluer un tri par insertion en tri à bulle, voire un tri alpha. Pour cela il faudrait qu'il "comprenne" la notion d'ordre que l'on trouve dans une liste de données, et pour cela il faut une taxinomie qui "explicite" les structures de bases du langage (booléen, entier, tableaux, arbre, etc...) en les associant avec des propriétés mathématique (les propriétés d'entiers, le fait qu'un tableau est ordoné dans ses indices, l'arithmétique booléenne, toussa).

      C'est bien joli tout ça, mais ça prendrai plus de temps à générer du code performant qu' à exécuter l'existant...

      Et de toutes façons, on commence à avoir des compilateurs à analyse de flot qui rend inutile la moitié des optimisations à la volée, qui sont détectées à la compilation.

      « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker

    • [^] # Re: Hum...

      Posté par  . Évalué à 10.

      de faire mouler le tout

      C'était mouliner je suppose...
      L'abus de tribune nuit gravement à la santé orthographique ;-)

  • # Multidesk OS...

    Posté par  . Évalué à 9.

    ... le retour de la vengeance!

    • [^] # Re: Multidesk OS...

      Posté par  . Évalué à 9.

      Sachez que MultiDeskOS se modifiera lui-même par la suite et qu'il
      pourra aussi créer de nouveaux programmes de manière tout à fait
      autonome. Or, l'assembleur n'est pas quelque chose qu'on peut comprendre
      sans analyse poussée, contrairement au code MultiDeskOS.
      -- Jayce - Polymorphisme et chevilles --

  • # 68k

    Posté par  (site web personnel) . Évalué à 10.

    Ontologia, j'aime bien tes journaux et ta quête du langage / OS idéal.

    Le 68k et suivant (aujourd'hui les Coldfire principalement), sont conçus pour être facile à programmer.
    Ils disposent d'un jeu d'instruction simple et efficace. Ils sont logiques et abordables et c'est d'ailleurs pour ça qu'ils me semble-t-il ont longtemps résisté au C.

    L'exemple que tu cites est frappant. Je monte ma machine en bidouillant un système bi-proc, je code un OS en assembleur et au finale j'ai quelque chose d'hyper intéressant.

    J'irais pas jusqu'à dire que sur 68k on savait s'amuser :-p Je remarque juste en passant que certains processeurs portent une certaine façon de coder.

    Bref je trouve mais peut-être ai-je tord que les questions de fond sur le modèle de programmation des machines est un peut trop absente des débats sur les langages et les OS.

    • [^] # Re: 68k

      Posté par  (site web personnel) . Évalué à 2.

      j'aime beaucoup moi aussi, tu devrais faire des journaux plus souvent ... Et finalement je regrette d'avoir fait un IUT et ne pas avoir fait une Licence car j'aurais pu apprendre les langages fonctionnels.

      • [^] # Re: 68k

        Posté par  (site web personnel) . Évalué à 10.

        t'as de la chance, l'informatique est - encore aujourd'hui - un des métier où l'on peut être autodidacte.

    • [^] # Re: 68k

      Posté par  . Évalué à 3.

      Par ailleurs, il ne faut pas oublier que depuis ... heu.... l'architecture Alpha ? les réordonnancements dans le pipeline d'exécution, la prédiction de branchement, et la distribution du code à exécuter entre plusieurs calculateurs sont des fonctions classiques à l'intérieur des processeurs courants, au point que leur présence a grandement réduit le besoin pour les compilateurs de trop vouloir optimiser les courtes séquences de code.

      • [^] # Re: 68k

        Posté par  . Évalué à 6.

        ... Et sont à l'origine de la méga-dissipation de châleur qu'on observe actuellement sur les processeurs (pas qu'à cause de ces mécanismes, mais quand même ...). Et introduisent aussi une part non-négligeable d'inconnu pour qui veut obtenir des performances maximales, car on ne sait plus trop quoi fait quoi, entre le cache intelligent qui précharge tout seul, le coeur intelligent qui précharge tout seul, le coeur dans le désordre, qui interroge le cache partagé avec le coeur dans le désordre aussi d'à côté ...

        • [^] # Re: 68k

          Posté par  (site web personnel) . Évalué à 3.

          Bin, sur x86, il est difficile de faire autrement, vu le nombres d'architectures existantes. Les optimisations faîtes par le proco, c'est possible quand il n'y a qu'une seule architecture sur le marché.

    • [^] # Re: 68k

      Posté par  . Évalué à 1.


      L'exemple que tu cites est frappant. Je monte ma machine en bidouillant un système bi-proc, je code un OS en assembleur et au finale j'ai quelque chose d'hyper intéressant.



      La thèse de Massalin resselle aussi une intéressante contribution sur la concurrence et la synchronisation.
      Il désirait en effet éviter de désactiver les interruptions à tout bout de champ sur son système, éviter d'utiliser des systèmes à verrou pour gérer la concurence sur sa machine dotée de deux 68030.



      Il faut savoir justement que le 68k a une instruction DCAS (double compare and swap), ce qui la rend particulierement interessante pour programmer des multiprocesseurs. En particulier, synthethis est completement lock-free (i.e. sans verrou)

      Les processeurs modernes n'incluent pas cette instruction, ce qui rend la chose encore plus difficile, ce qui fait que tres peu de systemes d'exploitation empruntent cette voie.

      • [^] # Re: 68k

        Posté par  . Évalué à 2.

        Oui enfin, faire un swap hardware entre 2 processeurs, c'est « facile ». Le faire entre 4, 8, 16 processeurs/coeurs, c'est quand même autre chose.

    • [^] # Re: 68k

      Posté par  (site web personnel, Mastodon) . Évalué à 1.

      J'irais pas jusqu'à dire que sur 68k on savait s'amuser :-p Je remarque juste en passant que certains processeurs portent une certaine façon de coder.

      En fait, si, coder en assembleur sur le 68k, c'est fun et (presque) facile. A fortiori si tu connais le C, et que tu prends le temps d'étudier le code généré.
      Ensuite tu t'inspires de ça pour gérer les variables locales et les passages de paramètres. Un peu de rigueur là-dessus, et c'est parti....

      Ah, le bon vieux temps du Metacomco...

  • # Et Windows (3.1|98|Me|2000|XP|Vista) alors ?

    Posté par  . Évalué à 10.

    Ça fait longtemps que chez Microsoft ils ont un OS qu'il est possible de patcher à la volée, grâce à la technique - brevetée, sûrement - du Microsoft BufferOverflow System. Et ça fonctionne même à distance.

    P'tit joueur, va...

  • # Et au final...

    Posté par  . Évalué à 5.

    ... l'OS devient de plus en plus intelligent, développe une conscience propre, prend le contrôle de toutes les machines, asservit l'humanité et mets tout le monde dans la Matrice.

    Faut se méfier avec ces petites bêtes là !

    ---> []

    • [^] # Re: Et au final...

      Posté par  . Évalué à 6.

      C'est pas la Matrice, cette histoire, c'est celle de SkyblogNet

      • [^] # Re: Et au final...

        Posté par  . Évalué à 7.

        Haaa, non, imagine que les machines apprennent à communiquez à travers les blogs O_O

        "Kikou ! Tte RzistanC sRé Futil ! \o/"
        Les machines extermineuses d'orthographe........

        • [^] # Re: Et au final...

          Posté par  . Évalué à 6.

          apprennent à communiquez

          Elles agissent deja sur LinuxFr ...!

          :)

        • [^] # Re: Et au final...

          Posté par  . Évalué à 2.

          Ouf, tant que ce n'est pas « Kikoo ! All your skyblogs are belong to us LoL ! » .
          (Sinon, Matrix, ce n'est pas la suite logique de Terminator ?)

          • [^] # Re: Et au final...

            Posté par  . Évalué à 1.

            T'as du perdre le fils de l'histoire quand Neo regarde dans le miroir et y voie John Connor, et lui dit :
            "Saloperie d'imprimante, toujours à me bouffer mes cartouches d'encre à un prix monstrueux. On est toujours au même point."

          • [^] # Re: Et au final...

            Posté par  . Évalué à 2.

            « Kikoo ! All your skyblogs are belong to us LoL ! »


            Perso, pas de problème. Je veux bien leur laisser ...

  • # JIT

    Posté par  . Évalué à 5.

    Bravo tu viens de découvrir le concepte Just in time.

    Bon apres le journal est assez confu, surtout que c'est bien beau toute ces optimisations a la volée, mais ca a un coup.

    Par exemple inliner le code à la voler, signifie plus ou moins reloger tout le code. Sur un bytecode fait pour ca, c'est pas trop dur, sur de l'assembleur bon courage.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.