[Kos-dev] An introduction to Wait-Free and Lock-Free data structures
Christophe Avoinne
kos-dev@enix.org
Mon, 25 Jun 2001 14:46:55 +0200
This is a multi-part message in MIME format.
------=_NextPart_000_0005_01C0FD85.AE06C1D0
Content-Type: multipart/alternative;
boundary="----=_NextPart_001_0006_01C0FD85.AE06C1D0"
------=_NextPart_001_0006_01C0FD85.AE06C1D0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Tout particuli=E8rement indiqu=E9 pour le SMP et m=EAme pour les non =
SMP. Pour information l'instruction "xchgcmp" en x86 s'apparante =E0 la =
primitive CAS et l'instruction "xchgcmp8b" s'apparante =E0 une variante =
limit=E9e de la primitive DCAS (limit=E9e car les deux mots =E0 comparer =
et modifier simultan=E9ment doivent =EAtre contigus en m=E9moire). J'ai =
utilis=E9 DCAS pour g=E9rer une pile avec des "push" et "pop" atomiques =
qui fonctionnent aussi bien en SMP ou non sans la n=E9cessit=E9 =
d'utiliser des primitives de synchronisation comme les mutex, =
particuli=E8rement d=E9gradatives lors des contentieux (n=E9cessit=E9 de =
r=E9ordonnancement particuli=E8rement gourmand en ressource CPU). Je =
vous dis =E7a pour que vous ne soyez pas tenter de ne faire que des =
spinlocks alors qu'un CAS ou un DCAS peut faire l'affaire. Et puis c'est =
bon de savoir qu'il existe des techniques plus subtiles que les =
s=E9maphores ou les mutex.
Pour ceux qui ne mont pas reconnu, je suis Hlide.
http://www.wcug.wwu.edu/lists/smpdev/199702/msg00021.html
------=_NextPart_001_0006_01C0FD85.AE06C1D0
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META content=3D"text/html; charset=3Diso-8859-1" =
http-equiv=3DContent-Type>
<META content=3D"MSHTML 5.00.3018.900" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>Tout particuli=E8rement indiqu=E9 pour =
le SMP et m=EAme=20
pour les non SMP. Pour information l'instruction "xchgcmp" en x86 =
s'apparante =E0=20
la primitive CAS et l'instruction "xchgcmp8b" s'apparante =E0 une =
variante=20
limit=E9e de la primitive DCAS (limit=E9e car les deux mots =E0 comparer =
et modifier=20
simultan=E9ment doivent =EAtre contigus en m=E9moire). J'ai utilis=E9 =
DCAS pour g=E9rer=20
une pile avec des "push" et "pop" atomiques qui fonctionnent aussi bien =
en SMP=20
ou non sans la n=E9cessit=E9 d'utiliser des primitives de =
synchronisation comme les=20
mutex, particuli=E8rement d=E9gradatives lors des contentieux =
(n=E9cessit=E9 de=20
r=E9ordonnancement particuli=E8rement gourmand en ressource CPU). Je =
vous dis =E7a=20
pour que vous ne soyez pas tenter de ne faire que des spinlocks alors =
qu'un CAS=20
ou un DCAS peut faire l'affaire. Et puis c'est bon de savoir qu'il =
existe des=20
techniques plus subtiles que les s=E9maphores ou les mutex.</FONT></DIV>
<DIV> </DIV>
<DIV><FONT face=3DArial size=3D2>Pour ceux qui ne mont pas reconnu, je =
suis=20
Hlide.</FONT></DIV>
<DIV> </DIV><BR> <A=20
href=3D"http://www.wcug.wwu.edu/lists/smpdev/199702/msg00021.html">http:/=
/www.wcug.wwu.edu/lists/smpdev/199702/msg00021.html</A></BODY></HTML>
------=_NextPart_001_0006_01C0FD85.AE06C1D0--
------=_NextPart_000_0005_01C0FD85.AE06C1D0
Content-Type: application/octet-stream;
name="An introduction to Wait-Free and Lock-Free data structures.url"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="An introduction to Wait-Free and Lock-Free data structures.url"
[DEFAULT]
BASEURL=http://www.wcug.wwu.edu/lists/smpdev/199702/msg00021.html
[InternetShortcut]
URL=http://www.wcug.wwu.edu/lists/smpdev/199702/msg00021.html
Modified=80927D8C73FDC0014C
------=_NextPart_000_0005_01C0FD85.AE06C1D0--