je pense avoir "compris" les synchronisations des données avec les mutex.
Mais comment le systeme garanti lui
la synchronisation du mutex (qui par essence doit etre accedé par plusieur
thread)?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
IR
Bruno Causse wrote:
je suis hors sujet [mes excuses].
Mes excuses de même, mais bon c'est un sujet qui m'intéresse donc je vais répondre quand même.
je pense avoir "compris" les synchronisations des données avec les mutex.
Si tu n'es pas _sûr_ d'avoir compris les principes des primitives de synchronisation (en tant que "boîtes noires"), je sais pas si ma réponse te sera d'une grande utilité, mais bon... allons-y malgré tout :-p
Mais comment le systeme garanti lui la synchronisation du mutex (qui par essence doit etre accedé par plusieur thread)?
Sur les plateformes modernes, la meilleure méthode est d'utiliser un type de CAS (instruction "compare and swap" atomique) au sein d'une boucle ("spin lock"), avant de repasser la main au kernel pour bloquer le thread si l'attente dure trop longtemps (le coût d'un spin lock étant bien souvent moindre que le coût d'un changement de privilège).
Sur des plateformes moins évoluées (et monoprocesseur), la bonne vieille méthode de l'inhibition d'interruptions est souvent utilisée.
Le principe étant dans les deux cas de garantir que : - la lecture de la valeur originale - la comparaison avec une valeur connue - l'écriture éventuelle d'une nouvelle valeur soient atomiques (non interruptibles).
La question que je me pose quant à moi étant : en environnement multiprocesseurs ne disposant PAS d'instructions atomiques de type CAS, comment garantir l'atomicité d'une série d'opérations (est-ce seulement possible...)?
Cheers, -- IR
Bruno Causse wrote:
je suis hors sujet [mes excuses].
Mes excuses de même, mais bon c'est un sujet qui m'intéresse donc je
vais répondre quand même.
je pense avoir "compris" les synchronisations des données avec les
mutex.
Si tu n'es pas _sûr_ d'avoir compris les principes des primitives de
synchronisation (en tant que "boîtes noires"), je sais pas si ma
réponse te sera d'une grande utilité, mais bon... allons-y malgré
tout :-p
Mais comment le systeme garanti lui
la synchronisation du mutex (qui par essence doit etre accedé par
plusieur thread)?
Sur les plateformes modernes, la meilleure méthode est d'utiliser un
type de CAS (instruction "compare and swap" atomique) au sein d'une
boucle ("spin lock"), avant de repasser la main au kernel pour
bloquer le thread si l'attente dure trop longtemps (le coût d'un
spin lock étant bien souvent moindre que le coût d'un changement de
privilège).
Sur des plateformes moins évoluées (et monoprocesseur), la bonne
vieille méthode de l'inhibition d'interruptions est souvent
utilisée.
Le principe étant dans les deux cas de garantir que :
- la lecture de la valeur originale
- la comparaison avec une valeur connue
- l'écriture éventuelle d'une nouvelle valeur
soient atomiques (non interruptibles).
La question que je me pose quant à moi étant : en environnement
multiprocesseurs ne disposant PAS d'instructions atomiques de type
CAS, comment garantir l'atomicité d'une série d'opérations (est-ce
seulement possible...)?
Mes excuses de même, mais bon c'est un sujet qui m'intéresse donc je vais répondre quand même.
je pense avoir "compris" les synchronisations des données avec les mutex.
Si tu n'es pas _sûr_ d'avoir compris les principes des primitives de synchronisation (en tant que "boîtes noires"), je sais pas si ma réponse te sera d'une grande utilité, mais bon... allons-y malgré tout :-p
Mais comment le systeme garanti lui la synchronisation du mutex (qui par essence doit etre accedé par plusieur thread)?
Sur les plateformes modernes, la meilleure méthode est d'utiliser un type de CAS (instruction "compare and swap" atomique) au sein d'une boucle ("spin lock"), avant de repasser la main au kernel pour bloquer le thread si l'attente dure trop longtemps (le coût d'un spin lock étant bien souvent moindre que le coût d'un changement de privilège).
Sur des plateformes moins évoluées (et monoprocesseur), la bonne vieille méthode de l'inhibition d'interruptions est souvent utilisée.
Le principe étant dans les deux cas de garantir que : - la lecture de la valeur originale - la comparaison avec une valeur connue - l'écriture éventuelle d'une nouvelle valeur soient atomiques (non interruptibles).
La question que je me pose quant à moi étant : en environnement multiprocesseurs ne disposant PAS d'instructions atomiques de type CAS, comment garantir l'atomicité d'une série d'opérations (est-ce seulement possible...)?
Cheers, -- IR
Jean-Marc Bourguet
IR writes:
La question que je me pose quant à moi étant : en environnement multiprocesseurs ne disposant PAS d'instructions atomiques de type CAS, comment garantir l'atomicité d'une série d'opérations (est-ce seulement possible...)?
1/ Il y a d'autres types de primitives de synchronisation que CAS (une simple incrémentation atomique avec comparaison du résultat à 0 suffit; le modèle load-linked, store-conditional du MIPS est à ma connaissance celui permettant les implémentations les plus performantes).
2/ Si on ne dipose pas de primitives atomiques, mais qu'on a quand même moyen d'optenir des garanties sur l'ordonnancement des lectures/écritures (soit directement, soit via l'utilisation de barrières), on peut s'en servir pour bâtir ce qu'on veut. Parfois ça suffit pour faire des choses utiles (faire une recherche lock free algorithm).
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
IR <no_email@use.net.invalid> writes:
La question que je me pose quant à moi étant : en environnement
multiprocesseurs ne disposant PAS d'instructions atomiques de type
CAS, comment garantir l'atomicité d'une série d'opérations (est-ce
seulement possible...)?
1/ Il y a d'autres types de primitives de synchronisation que CAS (une
simple incrémentation atomique avec comparaison du résultat à 0 suffit; le
modèle load-linked, store-conditional du MIPS est à ma connaissance celui
permettant les implémentations les plus performantes).
2/ Si on ne dipose pas de primitives atomiques, mais qu'on a quand même
moyen d'optenir des garanties sur l'ordonnancement des lectures/écritures
(soit directement, soit via l'utilisation de barrières), on peut s'en
servir pour bâtir ce qu'on veut. Parfois ça suffit pour faire des choses
utiles (faire une recherche lock free algorithm).
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
La question que je me pose quant à moi étant : en environnement multiprocesseurs ne disposant PAS d'instructions atomiques de type CAS, comment garantir l'atomicité d'une série d'opérations (est-ce seulement possible...)?
1/ Il y a d'autres types de primitives de synchronisation que CAS (une simple incrémentation atomique avec comparaison du résultat à 0 suffit; le modèle load-linked, store-conditional du MIPS est à ma connaissance celui permettant les implémentations les plus performantes).
2/ Si on ne dipose pas de primitives atomiques, mais qu'on a quand même moyen d'optenir des garanties sur l'ordonnancement des lectures/écritures (soit directement, soit via l'utilisation de barrières), on peut s'en servir pour bâtir ce qu'on veut. Parfois ça suffit pour faire des choses utiles (faire une recherche lock free algorithm).
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
IR
Jean-Marc Bourguet wrote:
IR writes:
La question que je me pose quant à moi étant : en environnement multiprocesseurs ne disposant PAS d'instructions atomiques de type CAS, comment garantir l'atomicité d'une série d'opérations (est-ce seulement possible...)?
1/ Il y a d'autres types de primitives de synchronisation que CAS (une simple incrémentation atomique avec comparaison du résultat à 0 suffit; le modèle load-linked, store-conditional du MIPS est à ma connaissance celui permettant les implémentations les plus performantes).
Si j'ai bien compris la première partie...
INC mutex BEQ mutex_acquired DEC mutex ; pour contrebalancer le INC "raté" BRA mutex_not_aquired
Par contre, je vais de ce pas me documenter sur le modèle MIPS que tu évoques (j'ai surtout un passif 68x et x86, donc MIPS reste une bête étrange pour moi :-p)...
2/ Si on ne dipose pas de primitives atomiques, mais qu'on a quand même moyen d'optenir des garanties sur l'ordonnancement des lectures/écritures (soit directement, soit via l'utilisation de barrières), on peut s'en servir pour bâtir ce qu'on veut. Parfois ça suffit pour faire des choses utiles (faire une recherche lock free algorithm).
En ce qui me concerne, tous les travaux sur les algos lock/wait free que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela dit, c'est plus que certainement dû au fait que les implémentations des algos en question visaient des _CISC_ récents...
En tous cas merci pour ces pistes, encore de la lecture à rajouter à la (déjà longue) liste. :-)
Cheers, -- IR
Jean-Marc Bourguet wrote:
IR <no_email@use.net.invalid> writes:
La question que je me pose quant à moi étant : en environnement
multiprocesseurs ne disposant PAS d'instructions atomiques de
type CAS, comment garantir l'atomicité d'une série d'opérations
(est-ce seulement possible...)?
1/ Il y a d'autres types de primitives de synchronisation que CAS
(une simple incrémentation atomique avec comparaison du résultat à
0 suffit; le modèle load-linked, store-conditional du MIPS est à
ma connaissance celui permettant les implémentations les plus
performantes).
Si j'ai bien compris la première partie...
INC mutex
BEQ mutex_acquired
DEC mutex ; pour contrebalancer le INC "raté"
BRA mutex_not_aquired
Par contre, je vais de ce pas me documenter sur le modèle MIPS que
tu évoques (j'ai surtout un passif 68x et x86, donc MIPS reste une
bête étrange pour moi :-p)...
2/ Si on ne dipose pas de primitives atomiques, mais qu'on a quand
même moyen d'optenir des garanties sur l'ordonnancement des
lectures/écritures (soit directement, soit via l'utilisation de
barrières), on peut s'en servir pour bâtir ce qu'on veut. Parfois
ça suffit pour faire des choses utiles (faire une recherche lock
free algorithm).
En ce qui me concerne, tous les travaux sur les algos lock/wait free
que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela
dit, c'est plus que certainement dû au fait que les implémentations
des algos en question visaient des _CISC_ récents...
En tous cas merci pour ces pistes, encore de la lecture à rajouter à
la (déjà longue) liste. :-)
La question que je me pose quant à moi étant : en environnement multiprocesseurs ne disposant PAS d'instructions atomiques de type CAS, comment garantir l'atomicité d'une série d'opérations (est-ce seulement possible...)?
1/ Il y a d'autres types de primitives de synchronisation que CAS (une simple incrémentation atomique avec comparaison du résultat à 0 suffit; le modèle load-linked, store-conditional du MIPS est à ma connaissance celui permettant les implémentations les plus performantes).
Si j'ai bien compris la première partie...
INC mutex BEQ mutex_acquired DEC mutex ; pour contrebalancer le INC "raté" BRA mutex_not_aquired
Par contre, je vais de ce pas me documenter sur le modèle MIPS que tu évoques (j'ai surtout un passif 68x et x86, donc MIPS reste une bête étrange pour moi :-p)...
2/ Si on ne dipose pas de primitives atomiques, mais qu'on a quand même moyen d'optenir des garanties sur l'ordonnancement des lectures/écritures (soit directement, soit via l'utilisation de barrières), on peut s'en servir pour bâtir ce qu'on veut. Parfois ça suffit pour faire des choses utiles (faire une recherche lock free algorithm).
En ce qui me concerne, tous les travaux sur les algos lock/wait free que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela dit, c'est plus que certainement dû au fait que les implémentations des algos en question visaient des _CISC_ récents...
En tous cas merci pour ces pistes, encore de la lecture à rajouter à la (déjà longue) liste. :-)
Cheers, -- IR
Radamanthe
IR wrote:
En ce qui me concerne, tous les travaux sur les algos lock/wait free que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela dit, c'est plus que certainement dû au fait que les implémentations des algos en question visaient des _CISC_ récents...
Il y avait pourtant TAS sur 68k, et ce CISC a presque 30 ans.
-- R.N.
IR wrote:
En ce qui me concerne, tous les travaux sur les algos lock/wait free
que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela
dit, c'est plus que certainement dû au fait que les implémentations
des algos en question visaient des _CISC_ récents...
Il y avait pourtant TAS sur 68k, et ce CISC a presque 30 ans.
En ce qui me concerne, tous les travaux sur les algos lock/wait free que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela dit, c'est plus que certainement dû au fait que les implémentations des algos en question visaient des _CISC_ récents...
Il y avait pourtant TAS sur 68k, et ce CISC a presque 30 ans.
-- R.N.
IR
Radamanthe wrote:
IR wrote:
En ce qui me concerne, tous les travaux sur les algos lock/wait free que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela dit, c'est plus que certainement dû au fait que les implémentations des algos en question visaient des _CISC_ récents...
Il y avait pourtant TAS sur 68k, et ce CISC a presque 30 ans.
Tu noteras que je n'ai pas prétendu que CAS <=> "récent", seulement que les algos wait free dont j'ai eu connaissance visaient des CPU récents (disposant de CAS, qui devient donc l'implémentation de choix).
Cela dit, étant donné la tournure de ma phrase je comprends que ça ait pu porter à confusion.
Cheers, -- IR
Radamanthe wrote:
IR wrote:
En ce qui me concerne, tous les travaux sur les algos lock/wait
free que j'ai eu l'occasion d'étudier utilisaient une forme de
CAS. Cela dit, c'est plus que certainement dû au fait que les
implémentations des algos en question visaient des _CISC_
récents...
Il y avait pourtant TAS sur 68k, et ce CISC a presque 30 ans.
Tu noteras que je n'ai pas prétendu que CAS <=> "récent", seulement
que les algos wait free dont j'ai eu connaissance visaient des CPU
récents (disposant de CAS, qui devient donc l'implémentation de
choix).
Cela dit, étant donné la tournure de ma phrase je comprends que ça ait
pu porter à confusion.
En ce qui me concerne, tous les travaux sur les algos lock/wait free que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela dit, c'est plus que certainement dû au fait que les implémentations des algos en question visaient des _CISC_ récents...
Il y avait pourtant TAS sur 68k, et ce CISC a presque 30 ans.
Tu noteras que je n'ai pas prétendu que CAS <=> "récent", seulement que les algos wait free dont j'ai eu connaissance visaient des CPU récents (disposant de CAS, qui devient donc l'implémentation de choix).
Cela dit, étant donné la tournure de ma phrase je comprends que ça ait pu porter à confusion.
Cheers, -- IR
Jean-Marc Bourguet
IR writes:
2/ Si on ne dipose pas de primitives atomiques, mais qu'on a quand même moyen d'optenir des garanties sur l'ordonnancement des lectures/écritures (soit directement, soit via l'utilisation de barrières), on peut s'en servir pour bâtir ce qu'on veut. Parfois ça suffit pour faire des choses utiles (faire une recherche lock free algorithm).
En ce qui me concerne, tous les travaux sur les algos lock/wait free que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela dit, c'est plus que certainement dû au fait que les implémentations des algos en question visaient des _CISC_ récents...
Vraissemblablement. Si l'histoire t'intéresse, recherche Wheeler et CAS dans groups.google...
En tous cas merci pour ces pistes, encore de la lecture à rajouter à la (déjà longue) liste. :-)
Si j'ai bonne mémoire, L. Lamport a publié ce genre d'algo dans les années 70.
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
IR <no_email@use.net.invalid> writes:
2/ Si on ne dipose pas de primitives atomiques, mais qu'on a quand
même moyen d'optenir des garanties sur l'ordonnancement des
lectures/écritures (soit directement, soit via l'utilisation de
barrières), on peut s'en servir pour bâtir ce qu'on veut. Parfois
ça suffit pour faire des choses utiles (faire une recherche lock
free algorithm).
En ce qui me concerne, tous les travaux sur les algos lock/wait free
que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela
dit, c'est plus que certainement dû au fait que les implémentations
des algos en question visaient des _CISC_ récents...
Vraissemblablement. Si l'histoire t'intéresse, recherche Wheeler et CAS
dans groups.google...
En tous cas merci pour ces pistes, encore de la lecture à rajouter à
la (déjà longue) liste. :-)
Si j'ai bonne mémoire, L. Lamport a publié ce genre d'algo dans les années
70.
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
2/ Si on ne dipose pas de primitives atomiques, mais qu'on a quand même moyen d'optenir des garanties sur l'ordonnancement des lectures/écritures (soit directement, soit via l'utilisation de barrières), on peut s'en servir pour bâtir ce qu'on veut. Parfois ça suffit pour faire des choses utiles (faire une recherche lock free algorithm).
En ce qui me concerne, tous les travaux sur les algos lock/wait free que j'ai eu l'occasion d'étudier utilisaient une forme de CAS. Cela dit, c'est plus que certainement dû au fait que les implémentations des algos en question visaient des _CISC_ récents...
Vraissemblablement. Si l'histoire t'intéresse, recherche Wheeler et CAS dans groups.google...
En tous cas merci pour ces pistes, encore de la lecture à rajouter à la (déjà longue) liste. :-)
Si j'ai bonne mémoire, L. Lamport a publié ce genre d'algo dans les années 70.
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
