home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 19 / CD_ASCQ_19_010295.iso / dos / prg / noyau / manual.doc < prev    next >
Text File  |  1994-05-25  |  10KB  |  257 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.                     NOYAU MULTITACHE PREEMPTIF EN ASSEMBLEUR
  7.  
  8.                       ET NOTIONS DE PROGRAMMATION PARALLELE
  9.  
  10.  
  11.                                MASM 6.0 - TASM 
  12.  
  13.  
  14.                          Par EQUALIZER - ART OF CODE
  15.  
  16.                                     1994
  17.  
  18.  
  19.    ( ART OF CODE n'est nullement responsable des fotes de frape contenues 
  20.      dans ce document . Prière de les corriger si vous le désirez .)
  21.  
  22.  
  23.  
  24. Noyau multitache préemptif - ART OF CODE - EQUALIZER    Page 1
  25.  
  26.  
  27.  
  28.         Ce Programme et ces sources sont libres de distribution, et de 
  29. modifications de toutes sortes. Les seules conditions concernant l'utilisation
  30. de ces sources en tant que tutoriel à la programmation multitache sont :
  31.  
  32.   - Toute utilisation, modification, devra afficher EQUALIZER & Art Of Code
  33.         au moins une fois durant le déroulement du programme.
  34.   - Une petite carte postale sera la bienvenue ( à 2f80 la license, .... ! )
  35.  
  36.         Voici l'adresse d'ART OF CODE :
  37.  
  38.                                 ART OF CODE
  39.                                    805 A
  40.                            2 rue Ch de FOUCAULD
  41.                                 37200 TOURS
  42.  
  43.         Bon, attaquons les chôses serieuses !!!
  44.  
  45.         Ce noyau multitache préemptif ( de très bas niveau ) ce compose de 
  46. plusieurs parties :
  47.  
  48.         - Une gestion des files d'attentes avec niveaux de priorité.
  49.                         ( GESTFILE.ASM )
  50.         - Un DISPATCHER ( DISPATCH.ASM )
  51.         - Procédures de synchronisation entre processus.
  52.         - Gestionnaire d'interruption Timer ( HORLOGE.ASM )
  53.         - Le Noyau ( NOYAU.ASM )
  54.         - Un ensemble de processus exemples se déroulant en parallèle.
  55.                         ( PRINCIPA.ASM )
  56.  
  57.         Ce noyau est volontairement simplifié et donc, facile d'acces pour
  58. tous ceux voulant s'initier à la programmation multitache. Il pourra permettre
  59. aussi à certains programmeurs de développer des processus se déroulant en 
  60. même temps. Il tourne sur n'importe quel 286, voire même sur 8086 avec une
  61. petite adaptation du source ( remplacement des pusha et des popa ! ).
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68. Noyau multitache préemptif - ART OF CODE - EQUALIZER    Page 2
  69.  
  70. I. Données du noyau.
  71.  
  72.         Chaque processus ( programme se déroulant en parrallèle ) se trouve 
  73. dans une zone mémoire bien spécifique ( si ! ). Durant son execution, il 
  74. utilise des registres et une pile. Lors d'une commutation de tache, le noyau
  75. doit savoir rétablir l'ensemble de ces données avant de redonner la main à
  76. ce processus.
  77.  
  78.         1.1 La Table Centrale.
  79.  
  80.         La table centrale contient plusieurs champs :
  81.  
  82.         - un pointeur vers la queue d'exploitation ( qe )
  83.         - un pointeur vers le descripteur du processus en cours ( EnCours )
  84.  
  85.         Un DESCRIPTEUR DE PROCESSUS ( ddp ) est une zone mémoire contenant 
  86. différentes informations :                                
  87.          * niveau de priorité du processus.
  88.          * pointeur vers le ddp suivant ( de priorité inferieure ou égale )
  89.          * pointeur vers le ddp précédent ( de priorité superieure ou égale )
  90.          * deux zones mémoires SS et SP contenant les valeurs permettant 
  91.            d'acceder à la pile privée du processus.
  92.          * l'état du processus : BLOQUE, SUSPENDU, ACTIF, TERMINE, PRET.
  93.            Il n'y a au plus qu'un processus ACTIF à un instant donné. C'est
  94.            le processus en cours dont le descripteur est pointé par EnCours.
  95.            Un processus PRET est un processus qui attend gentiment d'avoir la 
  96.            main pour s'executer.
  97.            Les autres processus ( BLOQUE, SUSPENDU, TERMINE ) ne peuvent pas
  98.            s'executer tant qu'il n'y a pas d'évenement spécial. 
  99.                                 ( voir Sémaphore )
  100.  
  101.  
  102.         Une queue d'exploitation est tout simplement une liste chainée de 
  103. l'ensemble des processus PRETs. Cette liste chainée est stoquée sous forme de 
  104. liste circulaire avec cellule de garde. Cette cellule de garde est tout 
  105. simplement une cellule vide de priorité maximale ( INFINI ) ayant pour élement
  106. suivant le premier élément de la liste, et pour élément précédent, le dernier
  107. de la liste.
  108.  
  109.  
  110. Noyau multitache préemptif - ART OF CODE - EQUALIZER    Page 3
  111.  
  112.         1.2 Les Sémaphores.
  113.  
  114.         Un sémaphore ( séma ) est un objet contenant :
  115.                 - un compteur
  116.                 - une file d'attente. 
  117.        En fait le sémaphore est une cellule de garde ( voir plus haut ) suivit
  118. d'un octet.
  119.         Pour utiliser ces sémaphores, il est nécéssaire de n'utiliser que 2 
  120. fonctions de bases ( incluses biensur ! ) : WAIT et SIGNAL ( p et v )
  121.         Un séma est un agent de synchronisation entre plusieurs processus 
  122. ne pouvant communiquer autrement.
  123.         Je vais vous expliquer cela par le biais d'un exemple, ce sera plus 
  124. simple :
  125.  
  126.         Le dos, comme chacun le sait, s'appelle par INT 21h. Or le DOS n'est
  127. pas réentrant ! ( Deux processus ne peuvent pas appeler le DOS en même temps )
  128. Donc, initialison le compteur du séma 's' à 1 ( une utilisation à la fois ).
  129. Lorsqu'un processus voudra utiliser le dos, il devra attendre ( WAIT ) que 
  130. celui ci soit disponible. Des lors, le processus pourra appeler le DOS, puis
  131. SIGNALera aux autres que le DOS peut être utilisé.
  132.  
  133. Exemple :
  134.  
  135. Compteur(s)=1
  136.  
  137. PROCESSUS 1             PROCESSUS 2 
  138. .                       .
  139. .                       .
  140. .                       .
  141. WAIT(s)                 .
  142. INT 21h                 WAIT(s)
  143. SIGNAL(s)               INT 21h
  144. .                       SIGNAL(s)
  145. .                       .
  146. FIN                     FIN
  147.  
  148.         1.2.1 WAIT & SIGNAL
  149.  
  150.                 ** WAIT effectue une opération tres simple : 
  151.                 SI compteur >= 1 ALORS compteur = compteur - 1
  152.                 SINON rendre le processus EnCours Etat='BLOQUE'
  153.                       l'inserer dans la file d'attente du séma 's'.
  154.                 FINSI
  155.                 COMMUTER SI IL LE FAUT ( appel au DISPATCHER ).
  156.  
  157.                 ** SIGNAL effectue l'opération inverse : 
  158.                 SI file d'attente est vide ALORS compteur = compteur + 1
  159.                 SINON Extraire un processus de la file d'attente et
  160.                       mettre son état à PRET, et l'inserer dans la qe
  161.                 FINSI
  162.                 COMMUTER SI IL LE FAUT ( appel au DISPATCHER ).
  163.  
  164.                 Le DISPATCHER est une procédure dont le but est simple :
  165.  
  166.                  Le programme EnCours est il ACTIF ET le Plus Prioritaire ?
  167.                  SI OUI on ne fait rien
  168.                  SINON onmet son état à PRET, on l'insere dans la qe
  169.                        puis on prend le processus le plus prioritaire et 
  170.                        on le rend ACTIF.
  171.                  FINSI.
  172.  
  173. Noyau multitache préemptif - ART OF CODE - EQUALIZER    Page 4
  174.  
  175.                 Reprenons notre exemple de processus 1 et 2 :
  176.  
  177.         Lorsque le premier effectue le WAIT, la valeur du compteur passe à 0,
  178. puis le DOS est appelé. admettons que le Processus 2 prenne la main et arrive 
  179. au WAIT à son tour. Dans ce cas, le processus 2 sera BLOQUE dans le séma. Donc
  180. le processus 1 reprend la main, et au retour du dos, il effectue un signal qui
  181. liberera le processus 2. Puis, lors du SIGNAL du processus 2, la valeur du 
  182. compteur repassera à 1. Vous pourrez voir plusieurs exemples d'utilisation
  183. de sémaphores dans les sources.
  184.         Durant la réalisation du noyau, les séma ont beaucoup été utilisés 
  185. comme déclencheurs de processus : 
  186.  
  187. Compteur du séma = 0
  188.  
  189. PROCESSUS 1                     PROCESSUS 2
  190. WAIT                            .
  191. .                               .
  192. .                               SIGNAL
  193. .                               .
  194. .                               .
  195. FIN                             FIN
  196.  
  197. Le processus 1 se bloquera d'emblée dans le sémaphore, jusqu'a ce que le 
  198. processus 2 le libère. A ce moment là, les deux pourront s'executer en même
  199. temps.
  200.  
  201.  
  202. Noyau multitache préemptif - ART OF CODE - EQUALIZER    Page 5
  203.  
  204. II. Réalisation
  205.  
  206.         Le moteur du noyau, est le gestionnaire d'interruption HORLOGE.
  207. Celui ci est appelé toutes les 55 ms. Lors de son traitement, sommes toutes
  208. assez banal, il se bloque dans un sémaphore. Et donc, il appel le DISPATCHER
  209. par l'intermédiaire de WAIT. celui ci redonnera la main au processus le plus
  210. prioritaire de la qe. Lors de l'interruption Timer : le gestionnaire 
  211. d'interruption effectue simplement un SIGNAL sur le sémaphore dans lequel est
  212. bloqué HORLOGE. HORLOGE étant de priorité 0 ( la plus forte ), le dispatcher
  213. lui donnera la main, tout en rangeant le processus en cours à sa place dans la
  214. qe. Mais, et c'est là toute l'astuce, si il y a plusieurs processus de même
  215. priorité dans la qe, lors de l'insertion, un processus de même priorité sera
  216. inséré ( je parle bien évidemment du ddp du processus ) en dernière position.
  217. Ce mécanisme effectuera un roulement entre processus de même priorité, ceux ci
  218. s'executant donc pendant 55 ms chacun :
  219.  
  220. temps 0 :
  221. queue d'exploitation :
  222. nom     proc 1  -----   proc 2  -----   proc 3  -----   proc 4
  223. prio      5               5               5               8
  224.  
  225. EnCours : Horloge
  226.              0
  227.  
  228. temps 1 :
  229. queue d'exploitation :
  230. nom     proc 2  -----   proc 3  -----   proc 4
  231. prio      5               5               8              
  232.  
  233. EnCours : proc 1
  234.              5
  235.  
  236. temps 2 :
  237. queue d'exploitation :
  238. nom     proc 2  -----   proc 3  -----   proc 1  ----- proc 4
  239. prio      5               5               5             8 
  240.  
  241. EnCours : Horloge
  242.              0
  243.  
  244. etc ...
  245.  
  246.  
  247.         Je pense que l'examination du source ( suffisament commenté, du moins 
  248. l'espère-je !!! ). vous permettra d'elucider le mystère de la programmation 
  249. parallèle. Bon courage . bye !!!
  250.  
  251. Pour ceux qui désireraient approfondir leurs connaissances, je vous conseille
  252. le livre PRINCIPES FONDAMENTAUX DES SYSTEMES D'EXPLOITATION 
  253. de LISTER (Eurolles).
  254. Et ORDONNANCEMENT EN TEMPS REEL de JP POUGET  ( MASSON ).
  255.  
  256.  
  257.