“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 200 — #210
i
i
i
i
i
i
i
i
200
4
• La programmation concurrente dataflow
son exécution et le remet dans la file. L’arrêt forcé d’un fil qui s’exécute s’appelle la
préemption.
Pour s’assurer que chaque fil obtient environ le même temps de calcul, un ordonnanceur a deux approches. La première est de compter le nombre de pas d’exécution et de
donner le même nombre à chaque fil. La deuxième est d’utiliser un rythmeur qui donne
le même temps à chaque fil. Les deux approches sont pratiquées. Comparons-les :
– L’approche du compteur a l’avantage que l’exécution de l’ordonnanceur est déterministe : l’exécution répétée du même programme préemptera les fils exactement
aux mêmes moments. Un ordonnanceur déterministe est souvent utilisé pour les
applications à temps réel dur, où il faut des garanties pour les durées des calculs.
– L’approche du rythmeur est plus efficace parce que le rythmeur est implémenté
dans le matériel. Par contre, l’ordonnanceur n’est plus déterministe. Tout événement dans le système d’exploitation, comme une opération disque ou réseau,
changera l’instant exact des préemptions.
Le système Mozart utilise un rythmeur.
Les niveaux de priorité
Pour beaucoup d’applications, il faut plus de contrôle sur le partage de temps entre
les fils. Par exemple, pendant un calcul, un événement peut arriver qui nécessite un
traitement d’urgence qui doit contourner le calcul « normal ». D’un autre côté, il
ne devrait pas être possible pour des calculs urgents d’affamer des calculs normaux,
causant des ralentis démesurés.
Un compromis qui marche bien en pratique est d’avoir des niveaux de priorité pour
les fils. On donne à chaque niveau de priorité un pourcentage minimum du temps du
processeur. À l’intérieur de chaque niveau de priorité, les fils partagent équitablement
le temps comme avant. Le système Mozart utilise cette technique. Il a trois niveaux de
priorité, haut (high), moyen (medium) et bas (low). Il y a trois files, une par niveau
de priorité. Par défaut, le temps est partagé entre les priorités dans les proportions
100 :10 :1 pour les priorités haut-moyen-bas. L’implémentation est très simple : pour
toutes les dix tranches de temps données à un fil à haute priorité, on donne une tranche
à un fil à moyenne priorité. Pareillement, pour toutes les dix tranches de temps données
à un fil à moyenne priorité, on donne une tranche à un fil à basse priorité. Les fils à
haute priorité, s’il y en a, partagent au moins 100/111 (environ 90 %) du temps entre
eux. Pareillement, les fils à moyenne priorité, s’il y en a, partagent au moins 10/111
(environ 9 %) du temps entre eux. Finalement, les fils à basse priorité, s’il y en a,
partagent au moins 1/111 (environ 1 %) du temps entre eux. Ces pourcentages sont
des bornes inférieures garanties. S’il y a moins de fils, ils peuvent être plus élevés.
Par exemple, s’il n’y a pas de fils à haute priorité, alors un fil à moyenne priorité peut
i
i
i
i
i
i
i
i
200
4
• La programmation concurrente dataflow
son exécution et le remet dans la file. L’arrêt forcé d’un fil qui s’exécute s’appelle la
préemption.
Pour s’assurer que chaque fil obtient environ le même temps de calcul, un ordonnanceur a deux approches. La première est de compter le nombre de pas d’exécution et de
donner le même nombre à chaque fil. La deuxième est d’utiliser un rythmeur qui donne
le même temps à chaque fil. Les deux approches sont pratiquées. Comparons-les :
– L’approche du compteur a l’avantage que l’exécution de l’ordonnanceur est déterministe : l’exécution répétée du même programme préemptera les fils exactement
aux mêmes moments. Un ordonnanceur déterministe est souvent utilisé pour les
applications à temps réel dur, où il faut des garanties pour les durées des calculs.
– L’approche du rythmeur est plus efficace parce que le rythmeur est implémenté
dans le matériel. Par contre, l’ordonnanceur n’est plus déterministe. Tout événement dans le système d’exploitation, comme une opération disque ou réseau,
changera l’instant exact des préemptions.
Le système Mozart utilise un rythmeur.
Les niveaux de priorité
Pour beaucoup d’applications, il faut plus de contrôle sur le partage de temps entre
les fils. Par exemple, pendant un calcul, un événement peut arriver qui nécessite un
traitement d’urgence qui doit contourner le calcul « normal ». D’un autre côté, il
ne devrait pas être possible pour des calculs urgents d’affamer des calculs normaux,
causant des ralentis démesurés.
Un compromis qui marche bien en pratique est d’avoir des niveaux de priorité pour
les fils. On donne à chaque niveau de priorité un pourcentage minimum du temps du
processeur. À l’intérieur de chaque niveau de priorité, les fils partagent équitablement
le temps comme avant. Le système Mozart utilise cette technique. Il a trois niveaux de
priorité, haut (high), moyen (medium) et bas (low). Il y a trois files, une par niveau
de priorité. Par défaut, le temps est partagé entre les priorités dans les proportions
100 :10 :1 pour les priorités haut-moyen-bas. L’implémentation est très simple : pour
toutes les dix tranches de temps données à un fil à haute priorité, on donne une tranche
à un fil à moyenne priorité. Pareillement, pour toutes les dix tranches de temps données
à un fil à moyenne priorité, on donne une tranche à un fil à basse priorité. Les fils à
haute priorité, s’il y en a, partagent au moins 100/111 (environ 90 %) du temps entre
eux. Pareillement, les fils à moyenne priorité, s’il y en a, partagent au moins 10/111
(environ 9 %) du temps entre eux. Finalement, les fils à basse priorité, s’il y en a,
partagent au moins 1/111 (environ 1 %) du temps entre eux. Ces pourcentages sont
des bornes inférieures garanties. S’il y a moins de fils, ils peuvent être plus élevés.
Par exemple, s’il n’y a pas de fils à haute priorité, alors un fil à moyenne priorité peut