A Study of Software Primitives in the context of Concurrent Data Structures
Abstract
The "free ride" towards faster processor speeds at the pace set by Moore’s Law has come to an end. Cramming ever smaller transistors on the same processor has reached a physical limit, and quantum technology is yet too immature to take on the challenge. Multiprocessor architectures have surged to meet the rising demand for computational power that has arisen in recent years. These architectures are capable of outperforming single-core architectures, but they require meticulous and orderly resource management to do so in a cost-efficient manner. This is where Concurrent Data Structures come to play. The new ultimate goal is to provide data structure designs that transparently manage workload balancing through several processors, ensuring correctness as well as versatility in a variety of concurrent settings. In this context, we approach the subject of providing the building blocks for Concurrent Data Structures: software and hardware synchronisation primitives. These are the operations in charge of the most critical functionalities of concurrent programs, those having to do with shared-resource management. Synchronisation primitives have to satisfy specific constraints related to correctness conditions for concurrent executions, and are therefore delicate matters worthy of unhurried study. In particular, we dive into the algorithmic details concerning the Non-blocking K-Compare-Single-Swap (KCSS) primitive proposed at (Luchangco et al., 2008), a non- blocking obstruction-free software primitive aimed at meeting the challenges posed by Concurrent Linked Data Structures. We provide a profuse educational guide through every non-trivial design feature of KCSS culminating in the proposal of a fully-functional, efficient and transparent-to-the-user C++ implementation, as well as usage instructions.
Full text
A S udy o So wa e P imi i es in he con ex o
Concu en Da a S uc u es
Es udio de P imi i as en So wa e en el con ex o
de Es uc u as de Da os Concu en es
UNIVERSIDAD COMPLUTENSE DE MADRID
FACULTAD DE INFORMÁTICA
T abajo de Fin de G ado
G ado en Ingenie ía In o má ica
Mayo 2023
Au o
Lidia Casado Nogue ales
Di igido po
Sami Genaim
Abs ac
A S udy o So wa e P imi i es in he con ex o Con-
cu en Da a S uc u es
The " ee ide" owa ds as e p ocesso speeds a he pace se by Moo e’s Law
has come o an end. C amming e e smalle ansis o s on he same p ocesso has
eached a physical limi , and quan um echnology is ye oo imma u e o ake on he
challenge. Mul ip ocesso a chi ec u es ha e su ged o mee he ising demand o
compu a ional powe ha has a isen in ecen yea s. These a chi ec u es a e capable
o ou pe o ming single-co e a chi ec u es, bu hey equi e me iculous and o de ly
esou ce managemen o do so in a cos -e icien manne . This is whe e Concu en
Da a S uc u es come o play. The new ul ima e goal is o p o ide da a s uc u e
designs ha anspa en ly manage wo kload balancing h ough se e al p ocesso s,
ensu ing co ec ness as well as e sa ili y in a a ie y o concu en se ings.
In his con ex , we app oach he subjec o p o iding he building blocks o
Concu en Da a S uc u es: so wa e and ha dwa e synch onisa ion p imi i es.
These a e he ope a ions in cha ge o he mos c i ical unc ionali ies o concu en
p og ams, hose ha ing o do wi h sha ed- esou ce managemen . Synch onisa ion
p imi i es ha e o sa is y speci ic cons ain s ela ed o co ec ness condi ions o
concu en execu ions, and a e he e o e delica e ma e s wo hy o unhu ied s udy.
In pa icula , we di e in o he algo i hmic de ails conce ning he Non-blocking K-
Compa e-Single-Swap (KCSS) p imi i e p oposed a (Luchangco e al., 2008), a non-
blocking obs uc ion- ee so wa e p imi i e aimed a mee ing he challenges posed
by Concu en Linked Da a S uc u es. We p o ide a p o use educa ional guide
h ough e e y non- i ial design ea u e o KCSS culmina ing in he p oposal o a
ully- unc ional, e icien and anspa en - o- he-use C++ implemen a ion, as well as
usage ins uc ions.
iii
Keywo ds
Concu en da a s uc u es, blocking and non-blocking synch onisa ion, sha ed mem-
o y, compa e and swap.
Resumen
Es udio de P imi i as en So wa e en el con ex o de
Es uc u as de Da os Concu en es
El ” iaje g a ui o” en el acele amien o de las elocidades de p ocesado al i mo
es ablecido po la Ley de Moo e ha llegado a su in. La in eg ación de ansis-
o es cada ez más pequeños en un mismo p ocesado ha alcanzado un lími e ísico,
y la ecnología cuán ica es aún demasiado inmadu a pa a asumi el desa ío. Las
a qui ec u as mul ip ocesado han su gido pa a sa is ace la c ecien e demanda de
pode compu acional que ha su gido en los úl imos años. Es as a qui ec u as son
capaces de supe a a las a qui ec u as de un solo núcleo, pe o equie en una ges ión
de ecu sos me iculosa y o denada pa a hace lo de mane a en able. Aquí es donde
en an en juego las Es uc u as de Da os Concu en es. El nue o obje i o inal es
p opo ciona diseños de es uc u as de da os que ges ionen de o ma anspa en e
el equilib ado de la ca ga de abajo en e p ocesado es, asegu ando co ección y
e sa ilidad en dis in os escena ios de concu encia.
En es e con ex o, abo damos el ema de p opo ciona los componen es básicos
pa a la cons ucción de Es uc u as de Da os Concu en es: las p imi i as so wa e
y ha dwa e de sinc onización. Es as son las ope aciones enca gadas de las uncional-
idades c í icas de los p og amas concu en es, las que ienen que e con la ges ión
de ecu sos compa idos. Las p imi i as de sinc onización ienen que sa is ace e-
s icciones especí icas elacionadas con las condiciones de co ección pa a ejecuciones
concu en es y, po lo an o, son asun os delicados me ecedo es de un es udio de-
allado. En pa icula , p o undizamos en los de alles algo í micos elacionados con
la p imi i a K-Compa e-Single-Swap sin bloqueo (KCSS) p opues a en (Luchangco
e al., 2008), una p imi i o en so wa e sin bloqueo (non-blocking en inglés) y lib e
de obs ucciones (obs uc ion- ee) des inada a a on a los desa íos plan eados po
las Es uc u as de Da os Enlazadas Concu en es. Apo amos una guía educa i a
ace ca de las decisiones de diseño no i iales de KCSS, que culmina con la p opues a
de una implemen ación en C++ uncional, e icien e y anspa en e pa a el usua io,
así como sus ins ucciones de uso.
Palab as cla e
Es uc u as de da os concu en es, sinc onización de bloqueo y sin bloqueo, com-
pa ición de memo ia, compa a e in e cambia .
Con en s
1. In oduc ion 1
1.1. Mo i a ion................................. 1
1.2. Goals.................................... 2
1.3. Wo kPlan................................. 3
1.4. S uc u e ................................. 3
2. Con ex ualising Concu en Da a S uc u es 9
2.1. De ini ion and Cha ac e is ics . . . . . . . . . . . . . . . . . . . . . . 9
2.2. P inciples o Concu ency . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1. A omici y ............................. 14
2.2.2. Linea izabili y . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3. Blocking and Non-Blocking Cons uc s . . . . . . . . . . . . . 16
3. Linked Da a S uc u es: Implemen ing a Concu en Linked Lis 19
3.1. The Locking Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.1. Coa se-G ained Locking . . . . . . . . . . . . . . . . . . . . . 19
3.1.2. Fine-G ained Locking . . . . . . . . . . . . . . . . . . . . . . . 21
3.2. The CAS P imi i e ............................ 24
3.3. Non-blocking K-Compa e-Single-Swap (KCSS) Ope a ion . . . . . . . 26
4. Non-blocking K-Compa e-Single-Swap (KCSS) 31
4.1. Sys emModel............................... 31
4.2. Fo malSpeci ica ion ........................... 31
4.3. Memo y Loca ions and hei Values . . . . . . . . . . . . . . . . . . . 32
4.4. Load Linked (LL) and S o e Condi ional (SC) Ope a ions . . . . . . . 35
ii
4.5. SNAPSHOT Ope a ion ........................... 45
4.6. KCSS Ope a ion.............................. 49
4.7. Limi a ions o he KCSS Ope a ion.................... 50
4.8. Rela edWo k............................... 51
5. K-CSS C++ Implemen a ion 53
5.1. Da a S uc u es and De ined Types . . . . . . . . . . . . . . . . . . . 53
5.2. Th eads and hei Iden i ie s . . . . . . . . . . . . . . . . . . . . . . . 61
5.3. Implemen a ion o me hods LL and SC ................. 63
5.4. Implemen a ion o SNAPSHOT me hod .................. 63
5.5. Implemen a ion o KCSS me hod..................... 65
5.6. KCSS UsageExample ........................... 66
5.7. ConcludingRema ks ........................... 69
6. Conclusions and Fu u e Wo k 77
Bibliog aphy 81
Chap e 1
In oduc ion
1.1. Mo i a ion
The " ee ide" owa ds as e p ocesso speeds a he pace se by Moo e’s Law
has come o an end o he compu e indus y. 20 yea s ago we eached he conclusion
ha ansis o echnology would soon ail o keep up wi h he demands o his
Law. In 2004 In el eleased he i s p ocesso con aining ansis o s smalle han
100nanome e s, only o make a public s a emen la e ha yea announcing ha
hey we e abandoning some single-co e on-going p ojec s in a ou o a new line o
de elopmen : dual-co e chips.
Since he possibili y o c amming e e smalle ansis o s on he same p ocesso
was eaching a dead-end – he only hope being he ye imma u e quan um echnol-
ogy – wo kload balancing h ough se e al p ocesso s became he new end. Mo e
p ocesso s would allow exploi ing he powe o dis ibu ing asks among hem, a oid-
ing al oge he he physical complica ions ha had a isen while ying o speed up
p ocesso s by sea ch o as e ha dwa e. While many esea ch opics s ill equi ed
ime o de elop, his new solu ion was se on he able o allow he compu e in-
dus y o p og ess in he mean ime. Soon, dual-co e a chi ec u es would u n in o
quad-co e, oc a-co e, ... Nowadays we e e o hem as mul i-co e a chi ec u es.
Mul i-co e a chi ec u es ha e p o en hei capabili y o ou pe o m single-co e
a chi ec u es, bu hey equi e me iculous and o de ly esou ce managemen o do
so. The bes enginee ing designs a e he esul o a balance be ween e iciency and
cos , and in ou pa icula case his ansla es in o a mul i-co e a chi ec u e ha
canno a o d he cos o ha ing mul iple s o age uni s o mul iple se s o e e y
esou ce a p ocesso needs in a compu e , bu ins ead has o be designed o be
e icien wi h he sha ing o hose esou ces a ailable. In ac , i is ue ha mul i-
co e a chi ec u es do no use ex a esou ces so as o no aise he cos o he
end-p oduc , bu also o e iciency’s sake, since sha ing esou ces implies sha ing
hei s a e, which implies sha ing he in o ma ion ha s a e holds, which is key o
coo dina e p ocesso s. This explains he p oli e a ion o comme cial sha ed-memo y
mul ip ocesso s: We a e sea ching o a cos -e icien design ha allows esou ce-
1
8Chap e 1. In oduc ion
4. Capí ulo 5 es udia nues a p opues a de código C++ pa a es a ope ación, cómo
sol en a los escena ios desc i os en el capí ulo an e io y cómo usa lo a a és
de un ejemplo p ác ico.
5. Capí ulo 6 p esen a nues as conclusiones del abajo ealizado y p opues as
de u u as di ecciones de in es igación y mejo a.
Chap e 2
Con ex ualising Concu en Da a
S uc u es
2.1. De ini ion and Cha ac e is ics
This wo k ocuses on Concu en Da a S uc u es o Sha ed-Memo y
Mul i-P ocesso Sys ems, which a e da a s uc u es in ended o hese sys ems
whe e, in con as o uni-p ocesso sys ems, mul iple h eads o execu ion can exe-
cu e concu en ly.
The ac ha hey a e mul i-p ocesso sys ems means hei a chi ec u e is made
up o mul iple p ocesso s (co es) ha can combine hei compu ing powe . On
he o he hand, being sha ed-memo y sys ems implies ha he e exis s a sha ed
add ess space be ween all p ocesso s, i ega dless o whe he each one has o he
local memo y uni s o hei own use. We will e e o p ocesso s (co es) as he
ha dwa e de ices ha cons i u e he Cen al P ocessing Uni (CPU) o a compu e .
Each p ocesso can spawn h eads: so wa e cons uc s ha ep esen he low o
execu ion o a p og am. Fo cla i ica ion, di e en ope a ing sys ems ha e di e en
de ini ions o wo ds h ead and p ocess, since hey a e bo h uni s o low con ol. In
his epo we will e e o hem as he same so wa e cons uc because we a e only
in e es ed in desc ibing hei beha iou as uni s o low con ol ha could execu e
concu en ly, bu we a e no in e es ed in pa icula i ies o one o ano he speci ic
ope a ing sys em o a chi ec u e.
When we say ha h eads can execu e concu en ly we mean ha hey a e
capable o execu ing a he same ime ( his does no mean hey will execu e
synch onously, as we will now explain). Fi s ly, o he sys ems unde s udy (sha ed-
memo y,mul i-p ocesso ) we assume ha concu en execu ion o mo e han one
h ead is possible because each p ocesso can spawn a leas one h ead o execu ion
a he same ime (concu en ly) as he es , and we a e in he con ex o a sys em
wi h se e al co es. The ac ha h eads do no necessa ily execu e synch onously is
key o he unde s anding o he execu ion con ex s we will be analyzing h oughou
he ollowing chap e s: we ha e said ha h eads will execu e "asynch onously" bu
9
10 Chap e 2. Con ex ualising Concu en Da a S uc u es
1sha ed ola ile in coun ;
2
3 un p oduce (){
4while ( ue){
5i ( coun == 0) {
6// Pe o m some cos ly ope a ion
7...
8coun += 1;
9p in (" P oduced 1 uni n");
10 }
11 }
12 }
Figu e 2.1: P oduce P og am
a he same ime. Execu ing "asynch onously a he same ime" means ha h eads
do no necessa ily ha e he same clock equencies, so hey a e no synch onous, bu
hey a e unning a he same ime, a hei own pace. This ul ima ely means
ha in some si ua ions he beha iou o h eads will g ea ly a y om he sequen ial
coun e pa . Fo example, in he concu en se ing we canno expec all h eads
o hal a he same ins an upon he occu ence o a ce ain e en ha hey can
all obse e. We will la e di e deepe in o he kind o e en s ha all h eads can
see. Fo now we will simply say ha e e y h ead can check i speci ic condi ions
a e obse ed on he esou ces i has access o, and mos commonly hese a e ela ed
o eads and w i es o sha ed-memo y. Fo ou pu poses, his means ha we will
ha e o be ex a ca e ul when easoning abou he beha iou o h eads and he
co ec ness o concu en da a s uc u es, which will challenge ou in ui ion.
To make all o he p e iously men ioned ideas clea , le us see an example o a
well-known concu ency p oblem and how i is sol ed using he ine-g ained mech-
anisms we ha e been alking abou : he P oduce -Consume P oblem. No e
ha his p oblem is pu pose ully buil so as o s udy he sho comings o p og ams
buil o uni-p ocesso s when used in a concu en se ing, and i can seem some-
wha a i icially buil . Suppose we ha e a mul i-p ocesso sys em consis ing o h ee
co es (which we will e e o as Co e1,Co e2and Co e3, espec i ely), and he wo
p og ams depic ed in igu es Figu e 2.1 (P oduce ) and Figu e 2.2 (Consume ).
In his code, we assume ha a iable coun is a sha ed a iable, meaning i is
loca ed in a memo y egion belonging o a sha ed add ess space ha all p ocesso s
can access, and he e o e so can any h eads hey c ea e. coun is decla ed as
ola ile, meaning on e e y access o i o use o i , i s alue will be e ched di ec ly
om memo y, and no cached. We also assume ha coun ini ially holds alue 0.
The con ex o use o p og ams such as he P oduce and Consume is one whe e
a cos ly ope a ion has o be pe o med e e y ime ano he pa icula ope a ion akes
place: one would be pe o med by he p oduce() code, and he o he one by he
consume() code. A plausible example o one such ope a ion could be eading/w i -
ing da a om/ o a bu e . In ha case, he P oduce (Figu e 2.1) would be in cha ge
o pe o ming he "cos ly ope a ion" o eading da a om he inpu sou ce, and he
2.1. De ini ion and Cha ac e is ics 11
1sha ed ola ile in coun ;
2
3 un consume (){
4while ( ue){
5i ( coun != 0) {
6// Pe o m some cos ly ope a ion
7...
8coun -= 1;
9p in (" Consumed 1 uni n");
10 }
11 }
12 }
Figu e 2.2: Consume P og am
1P oduced 1 uni
2Consumed 1 uni
3P oduced 1 uni
4Consumed 1 uni
5P oduced 1 uni
6Consumed 1 uni
7P oduced 1 uni
8...
Figu e 2.3: Possible ou pu ob ained by le ing h ee h eads execu e concu en ly,
wo o which un on he Consume P og am, one on he P oduce P og am.
Consume (Figu e 2.2) o w i ing i o he co esponding ou pu des ina ion. Va i-
able coun is he mechanism ha bo h p og ams will use o le each o he know
ha he o he one has al eady pe o med i s ope a ion.
Now le us suppose Co e1and Co e2each spawn a h ead o execu e he Con-
sume , and Co e3ano he one o execu e he P oduce . We will e e o hese
h eads as Consume 1,Consume 2and P oduce 1, espec i ely. Consume 1and
Consume 2"wan " o se he alue o coun o 0 (because i will mean hey ha e in-
ished hei "consump ion phase", dec emen ing coun by 1 uni ), while P oduce 1
wan s o se coun ’s alue o 1 (i wan s o go h ough i s "p oduc ion phase",
which inc emen s coun by a uni ).
Gi en ha he ini ial alue o coun is 0, i is easonable o assume ha once
P oduce 1,Consume 1and Consume 2s a unning, he sequence o s ings de-
pic ed on Figu e 2.3 will be p in ed un il we s op he execu ion o all h eads. How-
e e , in eali y we ha e no gua an ees ha his will be he case. This pa icula se o
s ings is he esul o a speci ic succession o e en s consis ing o : h ead P oduce 1
accessing coun ’s memo y add ess and seeing a 0 s o ed in i , hen adding 1 o i
and p in ing P oduced 1 uni ; hen one o he consume h eads (Consume 1, o
Consume 2) accessing coun ’s memo y add ess and seeing a 1 s o ed in i , sub ac -
ing 1 om i and p in ing Consumed 1 uni , which is when he cycle would s a
again. This is he expec ed beha iou in a sequen ial se ing. This beha iou can
be expec ed i we pic u e h eads as pa allel lows o execu ion ha execu e e e y
12 Chap e 2. Con ex ualising Concu en Da a S uc u es
1Consumed 1 uni
2Consumed 1 uni
3P oduced 1 uni
4Consumed 1 uni
5Consumed 1 uni
6Consumed 1 uni
7Consumed 1 uni
8Consumed 1 uni
9...
Figu e 2.4: Possible ou pu ob ained by le ing h ee h eads execu e concu en ly,
wo o which un on he Consume P og am, one on he P oduce P og am.
code s a emen in synch oniza ion o a single clock.
In a concu en se ing such as he one we ha e desc ibed ( h ee h eads execu ing
a he same ime while sha ing a common a iable coun ), he ou pu shown by
Figu e 2.3 is one possibili y among many, due o he non-de e minis ic componen
ha he in e ac ion be ween asynch onous co e clocks opens he doo o. Ano he
possible ou pu o he P oduce -Consume se up we ha e desc ibed could also be
he one depic ed by Figu e 2.4.
A a i s glance, his does no make sense because in o de o p in s ing
Consumed 1 uni alue coun has o be di e en om 0, and he only way o
achie e his is h ough he execu ion o one i e a ion o he P oduce by h ead
P oduce 1. Howe e , each o hese would esul in he p in ing o s ing P oduced
1 uni , and we do no see his s ing un il he hi d line o ou pu is eached.
Mo eo e , we do no see any mo e appa i ions o s ing P oduced 1 uni a all.
In his concu en se ing, he ollowing can happen (see Figu e 2.5 o a isual
illus a ion o he si ua ion):
P oduce 1 h ead eads a 0 in coun , and p oceeds o inc emen coun by 1
uni .
Be o e P oduce 1has ime o p in P oduced 1 uni , bo h Consume 1and
Consume 2 ead a 1 in coun , which sa is ies he condi ion o hei i -clause.
They bo h p oceed o execu e he line which modi ies coun ’s alue (coun is
cu en ly -1).
Now, Consume 1and Consume 2(each a i s own pace, no necessa ily a he
same ime) p oceed o p in ing s ing Consumed 1 uni . Then hey es a
he loop.
A his momen , P oduce 1manages o inalise i s p in ing ins uc ion, so
he console cu en ly con ains wo Consumed 1 uni s ings ollowed by one
P oduced 1 uni s ing.
The p oblem ha we encoun e a his ins an is ha coun now holds alue -1,
and he e o e P oduce 1’s i -clause will ne e be sa is ied again, since he only
2.1. De ini ion and Cha ac e is ics 13
Line 4
Consume 1
Consume 2
E olu ion o
coun
0
P oduce 1
Console:
Consume P og am P oduce P og am
Line 5 Lines 6,7
1
Line 5Line 4 Line 5 Line 4 Line 5 Line 4
Line 8
Line 5Line 4 Line 5Line 4 Line 5Line 4
Lines 6,7 Line 8
Lines 6,7 Line 8
0 -1
Line 9
Line 9
Line 9
Consumed 1 uni
Consumed 1 uni
Consumed 1 uni
Consumed 1 uni
P oduced 1 uni
-2 -3
Lines 4,5,6,7,8 Lines 4,5,6,7,8
Lines 4,5,6,7,8 Lines 4,...
Line 5
coun += 1
coun -= 1
coun -= 1
coun -= 1
coun -= 1
p in
p in
p in
Figu e 2.5: Illus a ion o a possible execu ion o he P oduce and Consume P o-
g ams in a se ing whe e he e a e wo consume s: Consume 1and Consume 2,
and one p oduce P oduce 1. No e ha he lines o code e e ed o by he ig-
u e co espond o hose a he code ha each h ead is execu ing (Consume 1and
Consume 2execu e he Consume P og am, whe eas P oduce 1execu es he P o-
duce P og am).
14 Chap e 2. Con ex ualising Concu en Da a S uc u es
execu ing h eads a e bo h "consume s" o his alue. Consume 1and Consume 2’s
i -clause will be sa is ied a e e y i e a ion, endlessly dec easing coun ’s alue
un il hei execu ion is s opped.
Wha he P oduce -Consume P oblem illus a es is he ac ha concu en
se ings in oduce non-de e minism in o execu ions de i ed om hei asynch onous
execu ion wi h espec o each o he . Th eads a e complex so wa e cons uc s ha
equi e a ine balance be ween independence, in o de o exploi he powe o mul i-
co e a chi ec u es, and cons an in e -communica ion in o de o no impede
o he h eads om p og essing o in o de no o duplica e wo k al eady done by
ano he h ead. This is he mo i a ion o doing esea ch on so wa e p imi i es
enabling communica ion and synch onisa ion o some so be ween h eads.
2.2. P inciples o Concu ency
Th oughou his sec ion we will e iew key concu ency concep s in ol ed in he
easoning o cons uc co ec Concu en Da a S uc u es.
Le us hink back o he P oduce -Consume P oblem example. How can we
make i execu e as Figu e 2.3 shows? We wan me hods p oduce() and consume()
o execu e he code wi hin hei i -clause as an indi isible uni o code, so ha
h eads can obse e he esul o he ac ions ca ied ou by hese lines o code as a
single ou come occu ing a an indi isible momen in ime. The concu ency concep
summa ising his p ope y is a omici y.
2.2.1. A omici y
A omici y (Moi and Sha i , 2004): A code block is gua an eed o be
a omic i no h ead can obse e a s a e in which he block has been
pa ially execu ed.
Achie ing a omici y can be e y cos ly, and he e o e i is common p ac ice o
aim a concu en p og ams ha limi hei equi emen s o a omic ope a ions as
much as possible while ensu ing co ec ness. The e exis so wa e and ha dwa e
p imi i es p o iding a omic ope a ions o commonly needed ac ions.
One such example a e a omic ead-modi y ope a ions, o which all mode n
mul ip ocesso s p o ide one o he ollowing p imi i es: load linked/s o e condi ional
(LL/SC) o compa e-and-swap (CAS).
Compa e-And-Swap (CAS): ope a ion ha a omically loads a memo y loca ion,
compa es he alue ead o an expec ed alue, and s o es a new one a he
loca ion i he compa ison succeeds. See Figu e 2.6 o he seman ics o his
ins uc ion in pseudo-code.
2.2. P inciples o Concu ency 15
1bool CAS(L, E, N) {
2a omic{
3i (*L == E) {
4*L = N;
5 e u n ue ;
6}else {
7 e u n alse ;
8}
9}
10 }
Figu e 2.6: The seman ics o he CAS ope a ion. The a omic keywo d equi es he
block i labels o be execu ed a omically. Figu e aken om (Moi and Sha i , 2004).
Load Linked/S o e Condi ional (LL/SC): In o ma ion aken om (Ba ei a,
2023). Toge he , hese wo ope a ions p o ide a means o synch onise memo y
load and s o e ope a ions.
•Load Linked (LL): I eads a memo y add ess α, and s o es add ess αin o
a special egis e called he link egis e , local o each p ocesso . This
egis e ’s con en a e dele ed in he es o p ocesso s whene e ano he
h ead pe o ms an LL ope a ion o he same memo y loca ion; o
whene e he same h ead ha pe o med LL calls SC and i succeeds.
•S o e Condi ional (SC): I s o es he con en o a egis e Rin a memo y
add ess α, bu only i αis he same add ess as he one s o ed in he link
egis e . O he wise, no ac ion is pe o med. I SC(α,R) was success ul i
e u ns ue, o he wise i e u ns alse.
An LL ope a ion on add ess α, ollowed by a success ul SC ope a ion on he
same add ess gua an ees ha α’s con en did no change be ween he call
o LL and he call o SC. This beha iou p o ides a means o know whe he
LL/SC we e execu ed as i hey we e a omic (wi hou being in e up ed by
o he h eads a emp ing modi ica ions o α), by analyzing he alue e u ned
by SC. I a h ead T1calls LL(α), and hen SC(α,R): i SC e u ns ue we
a e gua an eed ha h ead T1’s link egis e con ained add ess α, ead by
he LL ope a ion pe o med by T1. This means no o he LL(α)ope a ion was
pe o med in be ween T1’s LL/SC calls, because ano he h ead’s call o LL wi h
he same add ess would ha e dele ed T1’s link egis e ’s con en . I SC e u ns
alse, we know ano he h ead a emp ed o modi y α’s con en , p e en ing
T1 om comple ing i s LL/SC ope a ion.
2.2.2. Linea izabili y
Ano he key concep in concu ency is linea izabili y o ope a ions. As we ha e
seen, in concu en se ings i is no always s aigh o wa d o poin ou he exac
momen when a speci ic ac ion has aken place. Ac ions ca ied ou by some h eads
migh be obscu ed by o he concu en ly- unning h eads’ own ac ions, making hei
16 Chap e 2. Con ex ualising Concu en Da a S uc u es
ou come in isible o con using o a spec a o unawa e o he inne wo kings o he
code. To eason abou concu en p og ams’ co ec ness, we de ine linea izabili y o
p ecisely e e o his momen in ime when we can alk abou he consequences o
he execu ion o an ope a ion/a se o ope a ions on he sys em.
(He lihy and Sha i , 2008) An execu ion is called linea izable i each op-
e a ion appea s o ake e ec ins an aneously a some poin be ween i s
in oca ion and i s esponse. This poin in ime is called i s linea iza ion
poin .
2.2.3. Blocking and Non-Blocking Cons uc s
Concu ency’s main goal is o exploi he pa allel compu a ion capabili ies o
mul i-co e sys ems. Ideally, e e y ask being execu ed would ha e a disjoin se
o independen sub- asks on which he ini ial ask could be subdi ided so ha a
one- o-one assignmen om asks o co es could be d awn. Howe e , i is o en
he case ha his is no possible, and in e -dependencies be ween sub- asks impose
limi s on he p og ess ha h eads can make when hey a e unning concu en ly
and ca ying ou ela ed sub- asks.
The e exis s a classi ica ion o he "amoun o p og ess" ha h eads can make
in he si ua ion desc ibed: Blocking and Non-Blocking Cons uc s. In o ma ion
aken om (Moi and Sha i , 2004).
Blocking Cons uc s: Cons uc s belonging o his class do no gua an ee any
p og ess o be made by h eads execu ing hem. Th eads could block o e e ,
he e a e no gua an ees ha he execu ion will e mina e. One example a e
cons uc s employing locks.
Non-Blocking Cons uc s: Cons uc s belonging o his class gua an ee ha
h eads will p og ess i speci ic condi ions a e me . These condi ions a e called
P og ess Condi ions, and hey equi e ha he ailu e o inde ini e delay o a
speci ic h ead does no p e en o he h eads om making p og ess. Depend-
ing on he necessa y P og ess Condi ions, se e al sub-classes a e de ined:
•Wai -F eedom: A wai - ee cons uc gua an ees i will inalise a e a
h ead execu ing i akes a ini e numbe o i s own s eps, e-
ga dless o he iming beha iou o o he h eads.
•Lock-F eedom: A lock- ee cons uc gua an ees ha a e a h ead ex-
ecu ing his cons uc akes a ini e numbe o i s own s eps, some
h ead’s execu ion will inalise (i could ei he be his one o an-
o he h ead execu ing he same cons uc ).
•Obs uc ion-F eedom: An obs uc ion- ee cons uc gua an ees i will
inalise i a h ead execu ing i manages o no encoun e in e -
e ence om o he h eads o a ini e numbe o s eps.
2.2. P inciples o Concu ency 17
The subjec o his s udy: he KCSS ope a ion, is non-blocking, and in pa icula
obs uc ion- ee, as we will la e see.
In he concu en se ing, wha de ines a so wa e cons uc ’s p og ess gua an ees
a e he synch oniza ion p imi i es i employs. These a e he building blocks in
cha ge o he key ac ions ha can comp omise he co ec ness o he inal end-
p oduc . Synch oniza ion p imi i es a e no hing mo e han ope a ions ca ying
ou speci ic asks ha a e s aigh o wa d in he sequen ial se ing bu equi e a
ede ini ion in he concu en se ing because hei sequen ial coun e pa does no
suppo concu en uses.
The e exis so wa e and ha dwa e synch onisa ion p imi i es. The la e a e
he op imal choice in gene al, bu no all sys ems p o ide hem due o hei de-
pendence on a chi ec u e-speci ic ea u es. One example is he Compa e And Swap
(CAS) ope a ion, which is nowadays suppo ed by mos mode n a chi ec u es. So -
wa e p imi i es, on he o he hand, a e malleable and cus omisable o ou needs,
in exchange o being highe -le el, less e icien ope a ions. The e a e many exam-
ples o so wa e p imi i es, e.g. he e exis a ia ions o he CAS ope a ion p o-
iding Double-Loca ion Compa e And Swap (CAS2 o DCAS) (G eenwald, 1999), o
N-Loca ion Compa e And Swap (CASN) (Ha is e al., 2002).
In he ollowing chap e s, we will explo e he limi s and capabili ies o di e en
synch oniza ion p imi i es, and compa e hem o he KCSS p imi i e ha is he main
subjec o his wo k.
24 Chap e 3. Linked Da a S uc u es: Implemen ing a Concu en Linked Lis
1bool CAS(L, E, N) {
2a omic{
3i (*L == E) {
4*L = N;
5 e u n ue ;
6}else {
7 e u n alse ;
8}
9}
10 }
Figu e 3.6: The seman ics o he CAS ope a ion. The a omic keywo d equi es he
block i labels o be execu ed a omically. Figu e aken om (Moi and Sha i , 2004).
None heless, locking is a cos ly mechanism in e ms o memo y in some p og am-
ming languages, like C++. In o he s like Ja a, he o e head is no so high because
e e y objec has an associa ed Moni o ha can be used o lock access o he objec ,
i ega dless o whe he i is used o no . In any case, ou linked lis equi es one lock
pe node, and locks a e so wa e-suppo ed da a s uc u es. We now aim a a mo e
ligh weigh solu ion ha can un close o ha dwa e o e en be e pe o mance.
3.2. The CAS P imi i e
The i s ha dwa e-suppo ed p imi i e we know o is CAS (Compa e And Swap)
as desc ibed in Figu e 3.6. CAS(L, E, N) a omically checks i he con en o loca ion
Lma ches he expec ed alue E, modi ying L o con ain he new alue Ni i is he
case, and o he wise no pe o ming any ope a ion. We could use he CAS p imi i e in
o de o achi e a ligh weigh linked lis implemen a ion, because his p imi i e can
be di ec ly implemen ed as a ha dwa e p imi i e, in con as o so wa e-suppo ed
locking. I is such a use ul ool in concu ency ha all mode n a chi ec u es p o ide
ha dwa e suppo o i .
In con as o locking, whe e we we e gua an eed eedom o modi ica ion in any
way we wan ed so long as we we e holding he lock. CAS in oduces a new way o
hinking because i o ces us o educe all ope a ions o be pe o med on a da a
s uc u e in o swaps o memo y con en . As we will soon see, his is he eason why
some imes CAS needs o be complemen ed wi h o he synch onisa ion ools, in o de
o p o ide a co ec implemen a ion o a concu en da a s uc u e.
As an example, imagine we wan o dele e an elemen in a linked lis like he
one in Figu e 3.7, ini ially consis ing o h ee elemen s: a,band d. Le us suppose
we wan o dele e b. One migh hink ha we can simply use CAS o modi y a’s
nex _poin e ield o s o e d’s memo y add ess, so bis no longe pa o he lis .
The same goes o inse ions. I we wan ed o inse an elemen a e node b, howe e ,
we could simply modi y b’s nex _poin e ield o poin o he new elemen , and
he new elemen o poin o d.
Bu wha would happen i bo h calls occu ed concu en ly? This is wha is
3.2. The CAS P imi i e 25
ba · ·
·
d
c
·
P oblem: node c no inse ed
Th ead T1: dele e(b)
... CAS(&a.nex , b, d) ...
Th ead T2: inse (c)
... CAS(&b.nex , d, c) ...
ba · · d·
Ini ial s a e o he linked lis con aining nodes: a, b and d
Final s a e o he linked lis a e T1's dele e(b) and concu en T2's inse (c)
Figu e 3.7: Illus a ion o ailed concu en ope a ions pe o med by wo h eads:
T1and T2on a linked lis ini ially con aining h ee nodes: a,band d, ha uses as
only synch onisa ion ool single-loca ion CAS ope a ions. Figu e inspi ed by hose
p o ided in (Luchangco e al., 2008).
depic ed in Figu e 3.7. CAS gua an ees a omici y on he check o see i he expec ed
alue is s ill in he p o ided loca ion, and on he modi ica ion owa ds he new alue,
i he check was success ul. Bu wo calls o CAS on di e en loca ions can p oceed
independen ly, a omically, ha ing an undesi ed ou come because hey concep ually
depend on each o he , bu CAS is obli ious o i since i jus wo ks wi h single loca-
ions. In Figu e 3.7 we can see ha T1’s dele ion o bhas caused a->nex _poin e
o poin o d, bu a he same ime T2has pe o med an inse ion o cbe ween b
and d, esul ing in b->nex _poin e poin ing o node c. And so we ge a inal
esul ha does no co espond o applying ei he ope a ion o he ini ial lis , no
o applying bo h o i . The esul does no e en quali y as a p ope linked lis .
The p oblems we ha e encoun e ed a e due o no ha ing made su e ha he
p edecesso and successo nodes o he p o agonis node in he ope a ion emained
immu able while he elemen was being dele ed o inse ed. This is he sho all o
CAS: i ac s upon a single loca ion. A omici y is cos ly because i equi es imposing
access es ic ions o sha ed esou ces, so we ha e o aim owa ds ob aining an
e icien p imi i e p o iding some a omici y gua an ees bu no being limi ed in
applicabili y. Fo u he illus a ion o ou poin , we can ake a look a ano he
example o e a linked lis . Figu e 3.8 depic s he ailu e o wo concu en dele ions
o e a lis ini ially con aining ou nodes: a,b,cand d.
26 Chap e 3. Linked Da a S uc u es: Implemen ing a Concu en Linked Lis
Th ead T1: dele e(b)
... CAS(&a.nex , b, c) ...
Th ead T2: dele e(c)
... CAS(&b.nex , c, d) ...
Ini ial s a e o he linked lis con aining nodes: a, b, c and d
Final s a e o he linked lis a e T1's dele e(b) and concu en T2's dele e(c)
ba · · c·d·
ba · · ·
c d
·
P oblem: node c no dele ed
Figu e 3.8: Illus a ion o ailed concu en dele ions pe o med by h eads T1and
T2, o e a linked lis ini ially con aining ou nodes: a,b,cand d. Figu e inspi ed
by hose p o ided in (Luchangco e al., 2008).
We ha e jus seen ha a naï e use o single-loca ion CAS p imi i es lea es g ound
o mis akes when designing linked concu en da a s uc u es. We will now see how
a sma e combina ion o synch onisa ion ools (including CAS), al oge he wi h e i-
cien memo y managemen echniques, can p o ide a p imi i e wi h all he bene i s
o CAS’s memo y-e iciency, while allowing disjoin access pa allelism.
3.3. Non-blocking K-Compa e-Single-Swap (KCSS) Op-
e a ion
Vic o Luchangco, Ma k Moi and Ni Sha i (Luchangco e al., 2008) ha e
de ised an a omic and obs uc ion- ee so wa e synch oniza ion ope a ion called K-
loca ion-compa e single-loca ion-swap (KCSS) ha p ecisely o e comes he di icul ies
o poin e manipula ion in linked da a s uc u es wi h suppo o concu ency. KCSS
allows us o modi y a single loca ion in memo y while ensu ing ha Ko he loca ions
emain unchanged. As we will la e explain, KCSS is a so wa e-suppo ed ope a ion
ha has he ad an age o being mo e ligh weigh han gene al pu pose ansac ional-
memo y based solu ions, i p o ides disjoin access pa allelism, and i is use - iendly
because i can be used anspa en ly, like any o he so wa e ope a ion call. This
con as s wi h he opaci y o code solu ions ha u ilize complex synch onisa ion
p imi i es in e spe sed in he code and he e o e equi e ca e ul concu en easoning
o ensu e co ec ness. Finally, KCSS is an in e es ing ope a ion because i only
equi es a small cons an memo y o e head pe wo d in ol ed in he ope a ion (in
con as o o he so wa e-suppo ed ope a ions).
We will now look a a p ac ical use o KCSS o implemen a linked da a s uc u e.
3.3. Non-blocking K-Compa e-Single-Swap (KCSS) Ope a ion 27
Node {
Elemen elem;
Coun coun ;
Node* nex _poin e ;
}
elem ·coun
nex _poin e
Figu e 3.9: Illus a ion o a Node s uc u e in he mul ise implemen a ion.
a 3 ·
·
e
1
·
c1 ·b·
3 4
d
Inse node wi h coun = 1 using 2-CSS
Figu e 3.10: Illus a ion o an inse ion o e a KCSS based mul ise implemen a ion,
when he inse ed elemen was no a membe o he mul ise be o e.
To demons a e i s po en ial upon designing concu en da a s uc u es, we will
desc ibe i s beha iou when applied o a concu en mul ise 2implemen a ion based
on a linked lis . This pa icula implemen a ion choice will e idence why we ha e
educed he s udy o "linked da a s uc u es" o gene al linked lis s: because we a e
implemen ing a a ia ion o a basic linked lis .
In his pa icula case, we design a mul ise made up o a linked lis o nodes ( ol-
lowing he o ma ha can be seen on Figu e 3.9), whe e e e y node ep esen s one
dis inc elemen on he mul ise , s o ing i s non-ze o mul iplici y oge he wi h he
elemen alue, and a poin e o he nex elemen on he linked lis . Because o his,
we can al eady poin ou he simila i ies o his mul ise o he linked lis s we alked
abou in p e ious sec ions: we will encoun e simila p oblems o consis ency upon
manipula ion o he linked lis o nodes. The mul ise , howe e , poses he ex a
challenge o ha ing o manage mo e ields pe node (i.e., he mul iplici y ield).
In pa icula , o implemen a mul ise we need 2-CSS (KCSS ins ance whe e K =
2) o inse ions, and 4-CSS (KCSS ins ance whe e K = 4) o dele ions, and sea ch
ope a ions. The beha iou o hese cons uc s is as ollows (see Figu es 3.10, 3.11,
3.12 o illus a ion):
sea ch(Elemen x):This me hod is an auxilia y p ocedu e ha sea ches whe he
he mul ise con ains any appea ance o elemen x. To do his, i has o check
whe he any node on he linked lis making up he mul ise s o es a key wi h alue
x, and non-ze o mul iplici y. In pa icula , sea ch(x) e u ns wo adjacen nodes
(N1, N2) (i.e. in he lis o nodes, he nex _poin e ield o node N1 poin s o
N2) such ha N1’s key is smalle han x, and N2’s key is g ea e o equal o x.
The co ec ness o his me hod comes om i gua an eeing o ne e e u n a node
whose mul iplici y is 0. This can be achie ed by dele ing all nodes ound while
2As a cla i ica ion, when we alk abou "mul ise " we e e o he ma hema ical concep : A
gene aliza ion o he no ion o ma hema ical se , which allows duplica e alues, unlike se s.
28 Chap e 3. Linked Da a S uc u es: Implemen ing a Concu en Linked Lis
I coun > 0, inc emen o dec emen using 1CSS o CAS
ba · · ·
c 6
·
1 3 3 d
Figu e 3.11: Illus a ion o an inse ion o e a KCSS based mul ise implemen a ion, i
he e was al eady an appea ance o he inse ed elemen on he mul ise (coun > 1).
a e sing he lis whose mul iplici y is 0, making use o 4-CSS. To a oid ge ing
in o implemen a ion de ails a his ea ly s age o in oducing he eade o he KCSS
so wa e ope a ion, we will no explain how exac ly 4-CSS is used in he sea ch
ope a ion.
inse (Elemen x):This me hod inse s a node whose elemen is x. The i s
ac ion inse will ha e o do is o sea ch xin he mul ise . In case xwas al eady
p esen on he mul ise , we can simply use 1-CSS o CAS ( hei beha iou is equi -
alen , as we will la e see) o inc emen he coun ield o x’s node on he mul ise .
On he o he hand, in he case whe e we a e adding x o he mul ise o he i s
ime, (wi h mul iplici y 1), we ha e o ca e ully manipula e he node ha will be
p edecesso o he new node con aining elemen x(we will call his node node_x, and
i s p edecesso p edecesso ). To inse node_x we ha e o modi y p edecesso ’s
poin e o poin o node_x, while ensu ing ha no o he h ead is a emp ing o
change he p edecesso ->nex _poin e , no i s mul iplici y. This is because
i ano he me hod a emp s o dec emen p edecesso ’s mul iplici y o 0, while
we a e pe o ming inse (x), he p edecesso node would be dele ed du ing his
call o inse , which is making use o i . Hence he need o 2-CSS on hese 2 lo-
ca ions: p edecesso ->nex _poin e ,p edecesso ->mul iplici y. 2-CSS will
modi y he con en o p edecesso ->nex _poin e o se i o node_x’s add ess,
gua an eeing in he p ocess ha bo h loca ions main ain he alues hey held when
he call o 2-CSS was made.
dele e(Elemen x):This me hod dec ease he mul iplici y o x, i he e is a node
con aining i . dele e will ini ially sea ch o nodes con aining elemen xin he mul-
ise . I one such node is ound, and i s mul iplici y is g ea e han 1, we can
again use 1-CSS o CAS o dec emen he coun ield o x’s node. On he con-
a y, i a node (le ’s call i node_x) is ound o con ain xand i s mul iplici y is
1, node_x has o be emo ed om he mul ise (we do no allow non-ze o mul i-
plici ies). The sea ch ope a ion will ha e p o ided us wi h node_x’s p edecesso
(p edecesso ) and successo (successo ). The dele e(x) ope a ion has o mod-
i y p edecesso ->nex _poin e , o poin o successo . In he mean ime, he
ollowing 4 loca ions ha e o emain unchanged:
p edecesso ->nex _poin e : modi ying i is he main pu pose o dele e(x),
and i ano he h ead ies o do so a he same ime would cause inco ec
beha iou .
3.3. Non-blocking K-Compa e-Single-Swap (KCSS) Ope a ion 29
Remo e node wi h coun = 0 using 4-CSS
c d
ba ··
6
1 3 ··
0
Figu e 3.12: Illus a ion o a dele ion o e a KCSS based mul ise implemen a ion.
This ope a ion occu s when he elemen ’s coun ield becomes 0.
p edecesso ->mul iplici y: i has o emain immu able o he same eason
as in inse . Because a concu en a emp o change i could dec emen i
o 0, igge ing i s dele ion while his dele e(x) ope a ion is using i .
node_x->nex _poin e and node_x->mul iplici y:node_x canno be mod-
i ied a all concu en ly o his ope a ion, because i is being emo ed. I should
appea un eachable o o he h eads, and so should i s ields.
Consequen ly, we apply 4-CSS on hese 4 loca ions o se he con en o o loca ion
p edecesso ->nex _poin e o be he poin e o successo – ha is, dele ing
node_x – ensu ing all o he abo e desc ibed loca ions a e sa e o do so.
As we ha e seen, KCSS p ecisely o e comes he sho alls encoun e ed when using
locks, because i allows disjoin access pa allelism hanks o being a minimal-e ec
ope a ion ac ing on e y speci ic memo y a eas e e y ime i is used. I also gene -
alizes he applicabili y o single-loca ion CAS, by p o iding a simila beha iou upon
mo e han one loca ion. Fu he on, we will also show how i achie es memo y-
e iciency, which makes i usable on pla o ms wi h di e en capabili ies.
Chap e 4
Non-blocking K-Compa e-Single-Swap
(KCSS)
Now ha we ha e unde s ood he applicabili y o he KCSS ope a ion, we will
p esen he ools and equi emen s necessa y o implemen i , ollowing wha is
sugges ed in (Luchangco e al., 2008). A he end o his sec ion, he eade will
ha e ully unde s ood: he scena ios whe e KCSS can be used, as well as hose whe e
i is mos ad an ageous; he seman ics o KCSS and how i can be p ope ly employed.
4.1. Sys em Model
We assume a machine a chi ec u e wi h he ollowing cha ac e is ics:
A 64bi wo d a chi ec u e.
Ha dwa e suppo o he CAS ope a ion on memo y wo ds.
Some assump ions on he memo y model, ha we will discuss la e on Sec-
ion 4.7 ( hey ha e o do wi h he e ec o s o ing and eading alues on
memo y, and we p e e o delay his discussion o simpli ying he p esen a-
ion).
4.2. Fo mal Speci ica ion
KCSS (wi h K > 1, a na u al numbe ) is a so wa e ope a ion ha akes as
pa ame e s:
The add esses o Kdi e en memo y loca ions a1, ..., ak.
The expec ed alues o hose Kloca ions e1, ..., ek.
31
32 Chap e 4. Non-blocking K-Compa e-Single-Swap (KCSS)
A new alue n1 ha we wan o place in o he loca ion a1.
The e o e, a KCSS call has he ollowing o m:
KCSS([a1, ..., ak],[e1, ..., ek], n1)
and i s seman ics is as ollow: i checks ha e e y loca ion aicon ains i s expec ed
alue ei, o 1≤i≤K. I his is he case, hen i also upda es loca ion a1wi h
he new alue n1, and e u ns ue. O he wise, i does no modi y any memo y lo-
ca ion and i e u ns alse. We say KCSS ei he succeeds o ails in each o hese cases.
KCSS is obs uc ion- ee. As we ha e al eady seen in Sec ion 2.2, his means ha
h eads unning concu en ly a e only gua an eed o make p og ess i hey a e le
o un on hei own o enough ime.
4.3. Memo y Loca ions and hei Values
KCSS’s pe o mance la gely depends on he o ma es ic ions i imposes on
he memo y loca ions in ol ed in i , and he way i manages he alues ha hese
loca ions can con ain. In his sec ion, we will no discuss implemen a ion de ails o
he da a s uc u es used by KCSS, bu a he gi e only hose necessa y o explain
he big pic u e o he mechanism behind i .
Fo KCSS, a memo y loca ion is a 64bi wo d in memo y, jus like i is o he sys-
em in which i uns. Howe e , KCSS’ implemen a ion e y much elies on iden i ying
he las h ead ha has accessed a loca ion. In o de o do so, we use a mechanism
consis ing on lea ing a imes amp o he h ead ha las accessed he loca ion, e e y
ime i is accessed wi h he in en ion o w i ing o i (no e ha accessing a loca ion
wi h he in en ion o w i ing o i in his case means eading he loca ion’s alue,
pe o ming some ope a ion wi h i , and hen upda ing he he loca ion). This imes-
amp is he h ead’s iden i ie (which we will e e o as h eadID om now on),
and i is s o ed in he loca ion i sel . This loca ion could ha e con ained a no mal
alue such as he alue ypes we know (in ege , loa ing poin , poin e , ...), o i
could ha e al eady con ained he imes amp ( h eadID) o he p e ious h ead ha
had a emp ed o s a w i ing o he loca ion and had no ye inished. These wo
possibili ies allow us o di e en ia e whe he ano he h ead had al eady accessed
his loca ion o no , and i is key o ou implemen a ion. In addi ion, we ha e a
mechanism o es o e a loca ion o i s o iginal alue i a w i ing ope a ion o i ails
be o e comple ion.
I a h ead wan s o modi y a loca ion α, i i s eplaces α’s cu en alue wi h
i s own h eadID (plus o he me ada a ha we will explain la e ). Then, i sa es
he alue ha i had ound on αin o a special a ea o sha ed memo y (an a ay
called SAVED_VAL), so ha o he h eads can e e o i in he u u e i hey ind
ha αcon ains he imes amp o a h ead ha did no manage o inish w i ing o
4.3. Memo y Loca ions and hei Values 33
i , i.e., o be able o e e s α’s con en o he o iginal alue. Le us now see his
mechanism in de ail.
We dis inguish wo ypes o alues ha memo y loca ions can con ain: p og am
alues (in ege , loa ing poin , poin e , ...), and empo al alues ( he ones we ha e
been e e ing o as " imes amps"). Fo a isual illus a ion and an example o how
loca ions and hei alues a e o ganised, see Figu e 4.1.
P og am alues: Loca ions wi h his alue ype con ain an ac ual p og am
alue (such as an in ege , loa ing poin alue, a poin e , ...) ha has been
adap ed o i in 63 bi s1, plus a single bi ( he leas signi ican bi ) se o
0which is ese ed o dis inguish hem om empo al alues. Rese ing his
bi , in p ac ice means ha we ha e o sac i ice 1 bi o p ecision o no mal
p imi i e ypes. Fo poin e s, howe e , since we canno sac i ice p ecision
wi hou changing he poin e ’s alue, we simply use aligned memo y posi ions
on e en posi ions o all o he p og am’s poin e s. This migh seem es ic i e
bu in eali y, he as majo i y o mode n sys ems al eady use wo d-aligned
memo y posi ions anyway.
Tempo al alues: Loca ions wi h his alue ype con ain a pai
⟨ h eadID, agnumbe ⟩
whe e h eadID occupies 15bi s, and agnumbe 48bi s2. This amoun s o a
o al o 63bi s, because once again, he leas -signi ican bi is equi ed o dis-
inguish empo al alues om p og am alues. In his case, i will be se o
1. Tempo al alues ep esen he in o ma ion ela ed o he las access o his
loca ion: h eadID ep esen s he h ead ha las accessed i , and agnumbe
will be used o dis inguish di e en accesses by he same h ead o he same
loca ion.
As we ha e seen, a memo y loca ion α’s p og am alue is empo a ily s o ed
in a special loca ion in sha ed memo y ha is no he add ess o α. This special
loca ion is SAVED_VAL), an a ay o p og am alues ha s o es he las p og am alue
ha αhas con ained. SAVED_VAL is indexed by h ead iden i ie s, which a e unique
iden i ie s gi en o e e y h ead in he sys em.
Now ha we ha e unde s ood some key da a s uc u es used by KCSS o ep esen
in o ma ion, we will mo e on o explaining he i s and mos impo an componen s
1Fo now, we will no ge in o he de ails o how a "cas " om any p og am alue o a ype
con aining 63bi s (ins ead o 64bi s) is possible. The implemen a ion de ails will be explained in
Sec ion 5.1.
2The bi choice o ields h eadID and agnumbe is me ely a design choice. In his case, 15bi s
ha e been alloca ed o h eadID s because we assume his is enough o ensu e unique IDs o all
i ual h eads ha could exis . 48bi s ha e been alloca ed o agnumbe because we assume his
p o ides ags in a ange big enough o gua an ee no w apa ound.
40 Chap e 4. Non-blocking K-Compa e-Single-Swap (KCSS)
Example 4.4.3 (Mo i a ing he need o ags: wi hou ags) In his exam-
ple we illus a e he p oblem ha we un in o when using only h ead iden i ie s as
empo al alues, i.e., wi hou he ags. Suppose we ha e he si ua ion depic ed in
Figu e 4.7, whe e wo h eads a e a emp ing LL/SC ope a ions on he same loca ion
B, and h ead T1is al e na ing be ween he execu ion o wo asks (one execu es o
some ime, hen i is in e up ed by he o he one, which uns in he mean ime,
and so on). Loca ion Bini ially con ains a p og am alue oldValue.T1’s T ask1
is unning, and pe o ms an LL i s , placing in o Bi s h eadID T1. Then comes
T2and does he same, so Bwill con ain a empo al alue made up o T2’s h eadID
a e he i s wo LL ope a ions. Immedia ely a e i s LL,T2pe o ms an SC(B,
oldValue + y), which succeeds because no o he ope a ion o B ook place be ween
his call and T2’s LL call. The e o e, he cu en alue o loca ion Ba his s age is
a p og am alue: in ege oldValue + y.
Un il now e e y hing has wo ked ine. A e some ime, T1’s T ask2is allowed o
un (in e up ing T ask1). T1’s T ask2, obli ious o Task1’s ac ions, pe o ms a new
LL on loca ion B, placing in i a new empo al alue wi h h eadID T1. As we can
see in he igu e, his new empo al alue is indis inguishable om he one pu in o B
by T1a he e y beginning. Thanks o ha ing pu a esh ag numbe in o B h ough
LL,Task2will be awa e ha he p og am alue o Bhas changed o oldValue +
y, bu we canno say he same o Task1.T ask1wan ed o use he las alue o B
o add a quan i y x o i . Because Task1’s LL happened be o e Th ead T2changed
B’s alue o oldValue + y,T ask1’s execu ion con ex hinks ha he alue in Bis
s ill oldValue. No only his, bu when T ask2gi es way o T ask1again, Task1will
call SC o commi i s ope a ion o modi ica ion o oldValue o be oldValue + x.
Because T ask2placed Th ead T1’s h eadID in o B,Task1 hinks no-one else has
accessed Bsince i s LL, and he e o e i hinks ha Bhas con ained alue oldValue
all along, be ween T ask1’s LL and Task1’s SC. The e o e, T ask1’s SC will succeed,
placing an inco ec alue on B(inco ec because i igno es Th ead T2’s changes o
B).
Example 4.4.4 (Mo i a ing he need o ags: wi h ags.) Conside he illus-
a ion depic ed in Figu e 4.8. The same sequence o ac ions akes place, excep ha
empo al alues con ain unique ags e e y ime an LL is pe o med. The use o ags
allows Th ead T1’s T ask1 o know ha B’s con en co espond o a e sion o a
empo al alue ha was placed by a call by T1 o LL ha does no co espond o he
one Task1had used o ead he alue o Band ope a e wi h i . The e o e, when
Task1a emp s o pe o m an SC, i ails. This is he co ec beha iou . P obably,
Task1will ha e o e y LL/SC again in o de o see he la es alue o Bplaced by
Th ead T2.
The p oblem we ha e jus desc ibed is a well known concu ency issue known as
he ABA p oblem. This is i s o mal de ini ion:
(Luchangco e al., 2008) The ABA p oblem a ises when a h ead eads a
alue A in a loca ion, and la e [...] a emp s o change he loca ion om
A o a new alue, wi h he in en ion ha i any o he h ead w i es o he
4.4. Load Linked (LL) and S o e Condi ional (SC) Ope a ions 41
LL(loca ion_B)
LL(loca ion_B)
SC(loca ion_B, oldValue + x) : ue
(63bi s) 0 (1bi )
Memo y loca ion B (64 bi s) P og am
alue
in ege oldValue
Th ead T1
(63bi s) 0 (1bi )
Memo y loca ion B (64 bi s) P og am
alue
in ege oldValue + x
Task1
Task2
1 (1bi ) h ead_ID T1
Memo y loca ion B (64 bi s) Tempo al
alue
Ini ial con en s o memo y loca ion B
Th ead T2Task1
LL(loca ion_B)
SC(loca ion_B, oldValue + y) : ue
(63bi s) 0 (1bi )
Memo y loca ion B (64 bi s) P og am
alue
in ege oldValue + y
1 (1bi )
h ead_ID T2
Memo y loca ion B (64 bi s) Tempo al
alue
1 (1bi ) h ead_ID T1
Memo y loca ion B (64 bi s) Tempo al
alue
INCORRECT
Figu e 4.7: Time diag am illus a ing he p oblem de i ed om an LL/SC imple-
men a ion ha does no ely on ags o check o di e en e sions o LL ope a ions
pe o med by he same h ead. In his case, T1is obli ious o T2’s modi ica ions
o a loca ion Bbecause T1is al e na ing be ween execu ing wo asks, T ask1and
Task2, so T1pe o ms an SC ope a ion on B ha succeeds e en hough i should
no . This SC upda es he alue o B o be one ha has igno ed T2’s changes o
Bwhile T1’s Task1was no unning. I , o example, Bhad s o ed he alue o a
coun e , he e would be some inc emen s pe o med by T2 ha would ha e go en
los in he p ocess.
42 Chap e 4. Non-blocking K-Compa e-Single-Swap (KCSS)
LL(loca ion_B)
LL(loca ion_B)
SC(loca ion_B, oldValue + x) : alse
(63bi s) 0 (1bi )
Memo y loca ion B (64 bi s) P og am
alue
in ege oldValue
Th ead T1
Task1
Task2
1 (1bi ) ag_numbe n1
h ead_ID T1
Memo y loca ion B (64 bi s) Tempo al
alue
Ini ial con en s o memo y loca ion B
1 (1bi ) ag_numbe n2
h ead_ID T1
Memo y loca ion B (64 bi s) Tempo al
alue
(Found ag n2, expec ed ag n1)
Th ead T2Task1
LL(loca ion_B)
SC(loca ion_B, oldValue + y) : ue
(63bi s) 0 (1bi )
Memo y loca ion B (64 bi s) P og am
alue
in ege oldValue + y
1 (1bi ) ag_numbe m1
h ead_ID T2
Memo y loca ion B (64 bi s) Tempo al
alue
Figu e 4.8: Time diag am illus a ing how using ag numbe s sol es he p oblem
depic ed by Figu e 4.7. In his case, T1has a means o checking ha a new LL
ope a ion has happened be ween T1T ask1’s LL and i s SC. The e o e, i s SC ails,
which is he expec ed beha iou .
4.4. Load Linked (LL) and S o e Condi ional (SC) Ope a ions 43
loca ion be ween he ead and he modi ica ion a emp , he modi ica ion
will ail, lea ing he alue unchanged. Howe e , in ha in e al, he
alue may change om A o some alue B and hen back o A again, in
which case he modi ica ion ope a ion will succeed. By using ags which
a e inc emen ed e e y ime he loca ion is w i en, h eads can a oid he
ABA p oblem, p o ided he ags ha e enough bi s o a oid w apa ound
in p ac ice.
Thanks o s o ing simul aneously he h eadID and he agnumbe when we pe -
o m LL ope a ions, bo h he same h ead and o he s can exac ly know ha , i a
loca ion’s con en is a empo al alue, some h ead mus ha e an ou s anding LL
ope a ion on i , and ha h ead is p ecisely iden i ied by he h eadID a ha loca-
ion. No only his, bu a h ead who inds a loca ion’s con en s o ing a empo al
alue wi h i s own h eadID can check whe he i s cu en agnumbe ma ches he
one ound in ha loca ion. I i does ma ch, no ABA p oblem occu ed and i is
he only h ead wi h an ou s anding LL ope a ion on ha loca ion, o he wise, he
ABA si ua ion occu ed and his h ead can be awa e and ac acco dingly. This
mechanism o dealing wi h he ABA p oblem is a no el y, and i has been p oposed
by he au ho s a (Luchangco e al., 2008) o he i s ime.
Le us now go deepe in o he de ails o he READ ope a ion ha we men ioned
ea lie . This ope a ion (see Figu e 4.9 o he pseudo-code) allows h eads o de e -
mine he p og am alue o a loca ion. I wo ks by epea edly checking whe he a
loca ion con ains a p og am alue o a empo al alue, un il a p og am alue is ound.
I a p og am alue is ound, i will e u n i . I a empo al alue is ound, READ calls
an auxilia y ope a ion RESET ha will eplace he empo al alue ound wi h ha
loca ion’s p e ious p og am alue, which can be e ie ed om a ay SAVED_VAL
(see in lines 1 o 6 o RESET’s pseudo-code, in Figu e 4.9). READ hen es a s he
loop, which will end i no o he h ead has pe o med an LL on he same loca ion
in be ween READ’s s a o he new i e a ion and i s check o he loca ion’s con en .
This is he eason why we canno simply e u n he con en o he loca ion upon
pe o ming READ. The call o RESET is necessa y o p e en s a h ead’s ou s anding
LL ope a ion on i om commi ing h ough he co esponding SC, and his will be
needed in o de o suppo he SNAPSHOT and KCSS ope a ions ha will be p esen ed
la e .
Now ha we ha e desc ibed all he pieces ha con o m he LL/SC mechanism,
le us go back o he pseudo-code o LL and SC and explain i in mo e de ail.
LL pseudo-code in de ail (Figu e 4.4): An LL(α)ope a ion is expec ed o
e y un il i is capable o e u ning he p og am alue in α, which is why he i s
line o code in LL is a while( ue) loop (Line 2). LL’s loop epea edly does he
ollowing: i i s eads he con en o αusing READ.READ will e u n a p og am
alue, i ega dless o whe he αcon ained a p og am alue, o i ound a empo al
alue and RESET had o be called on α o es o e i o i s p e ious p og am alue.
LL will go on o sa e he e u ned p og am alue in o i s alloca ed posi ion in a ay
44 Chap e 4. Non-blocking K-Compa e-Single-Swap (KCSS)
1 oid RESET ( loc_s uc * a) {
2uin 64_ oldValue = a-> alue ;
3i ( is_ empo al_ alue ( oldValue )) {
4CAS (&a-> alue , oldValue , SAVED_VAL [ h ead_id ( oldValue )]);
5}
6}
7
8uin 64_ READ(loc_s uc * a) {
9while ( ue) {
10 uin 64_ al = a -> alue ;
11 i (!is_ empo al_ alue( al))
12 e u n al;
13 RESET (a);
14 }
15 }
Figu e 4.9: Pseudo-code o he READ and RESET ope a ions.
SAVED_VAL4so ha i his LL succeeds, i sel and o he h eads know wha he las
p og am alue o αwas. Then, i will gene a e he imes amp necessa y o he
c ea ion o he empo al alue ha i will a emp o place in α o inalise i s LL
ope a ion, using he cu en ly execu ing h ead’s a ibu es h eadID and agnumbe
( ecen ly inc emen ed o ensu e i s uniqueness a Line 3). The placemen a emp
is done using CAS, o ensu e i is an a omic ope a ion. A success ul CAS will mean
he LL inished co ec ly and is now an ou s anding LL o loca ion α, and so i will
e u n he p og am alue ound upon eading α. A ailed CAS will mean some o he
h ead managed o change he con en o αsomewhe e in be ween he call o READ
a Line 4 and Line 7. This is why LL has a while( ue) loop. Jus like when we saw
locking mechanisms ha equi ed y-lock() o ensu e a ailu e did no p e en
hem om p og essing, his loop se es he same pu pose.
SC pseudo-code in de ail (Figu e 4.5): A call o SC(α, newValue) by a
h ead Tis a one- ime sho a eplacing he con en o αwi h alue newValue.SC
consis s o a CAS ope a ion (Line 4) ha checks whe he αs ill holds he empo al
alue ha Thad placed he e du ing he las LL ha h ead Tpe o med, and
eplaces he con en o αby a new p og am alue newValue i ha is he case.
O he wise, i simply ails and e u n. I does no e y because one ailu e makes i
impossible o succeed in he u u e, unless he agnumbe is inc emen ed again (which
can only happen i a new LL ope a ion is pe o med by T).
4The eason why we can use a ay SAVED_VAL o s o e all o he possible p e ious p og am
alues eplaced by h eads’ empo al alues, is because we can ha e a mos as many ou s anding
LL ope a ions as h eads he e a e, and because a single h ead can ha e a mos one ou s anding
LL ope a ion in o al.
4.5. SNAPSHOT Ope a ion 45
4.5. SNAPSHOT Ope a ion
Le us ecall he pu pose o KCSS: we wan o check ha Kloca ions con ain
hei expec ed alues, and i his is he case upda e he con en s o one o hem
wi h a new alue. Un il now, we ha e ocused on he mechanism ha enables us
o ead he con en o a loca ion, use i in some in e media e calcula ions, and hen
upda e he loca ion wi h a new alue i i has no been accessed in he meanwhile.
All o his is possible using only LL/SC, and READ ope a ions. Howe e , in o de
o implemen KCSS, he i s s ep in ol ed is clea : we ha e o e ie e he con en
o Kloca ions, and hen p oceed o check i he alues ma ch he expec ed ones,
and o upda e he co esponding loca ion i possible. The e o e, we ini ially ha e o
ca y ou KREAD ope a ions. Un o una ely, his s ep canno be done by a simple
a loop ha eads all loca ions by calling READ(loca ion_X), because e e y READ
ope a ion akes a non-negligible amoun o ime. This allows o ime gaps be ween
one READ(loca ion_X) and ano he READ(loca ion_Y) whe e o he h eads a e
concu en ly execu ing and can po en ially change he con en s o loca ion_X by
he ime READ(loca ion_Y) inishes. This is a p oblem because wha we eally
wan s is o cap u e he s a e o Kmemo y loca ions a a single poin in ime, and
he alues e u ned a e only co ec i we can gua an ee ha , indeed, hey ha e
all coexis ed in hei co esponding memo y loca ions a some poin in ime. We
illus a e his in he ollowing example.
Example 4.5.1 (Mo i a ing he need o he SNAPSHOT ope a ion) Conside
he illus a ion depic ed in Figu e 4.10. Suppose we ha e wo h eads: T1and T2,
and wo loca ions Aand B.T1wan s o collec he con en o bo h loca ions, while T2
is concu en ly execu ing. T1goes ahead and pe o ms a READ(A), e ie ing alue
oldA om A. Now T2s a s execu ing and pe o ms a success ul LL/SC call on A,
changing i s con en s o newA. While T1is s ill busy wi h some hing else, T2keeps
execu ing and manages o also success ully change he con en s o B o newB. Now,
T1is eady o pe o m i s second READ ope a ion: READ(B).
T1has now cap u ed a alue o bo h Aand B, which we can conside as he
"pic u e" o memo y ha i will use o u u e calcula ions. Howe e , i has cap u ed
he con en s o Aand Bin a way such ha he "pic u e" hey o m has ne e
occu ed (i.e., bo h alues exis ed a he same ime). We can see ha T1 hinks ha
memo y loca ion Acon ains i s old alue (oldA) and ha Bcon ains newB. Bu i
we look a he memo y con en e olu ion h oughou he execu ion o bo h h eads,
loca ions Aand Bha e ne e concu en ly con ained hese wo alues. A some
poin , Ahas con ained oldAwhile Bcon ained oldB; and a some o he poin in
ime Bcon ained newB, while Acon ained i s new alue (newA).
In p ac ice, his means ha any compu a ion T1pe o ms wi h he cap u ed alues
will be inco ec , simply because he e is no poin in ime whe e he wo alues o A
and B,oldAand newB, ha e coexis ed. Suppose Aand B’s con en s co esponded o
wo coun e s. T1has cap u ed hei coun a di e en poin s in ime, and he e o e
hese alues do no ep esen a alid s a e o he coun e s.
Once again, his example illus a es he di icul ies o co ec ly pe o ming an
46 Chap e 4. Non-blocking K-Compa e-Single-Swap (KCSS)
(63bi s) 0 (1bi )
Memo y loca ion B (64 bi s) P og am
alue
in ege old_B
Ini ial con en s o memo y loca ions A and B
Th ead T2SC(loca ionA, new_A) : ue
Th ead T1
READ (loca ionA) READ (loca ionB)
(63bi s)
Memo y loca ion A (64 bi s)
in ege old_A 0 (1bi )
In memo y
Con en s o
loca ionA
Con en s o
loca ionB
A e READ(loca ionA)A e READ(loca ionB)
in ege old_A 0
SC(loca ionB, new_B) : ue
LL(loca ionA) LL(loca ionB)
A e LL/SC(loca ionA)
in ege new_A 0 in ege new_A 0 in ege new_A 0
A e LL/SC(loca ionB)
in ege old_B 0in ege old_B 0in ege new_B 0 in ege new_B 0
As seen by T1
Con en s o
loca ionA
Con en s o
loca ionB
A e READ(loca ionA) and READ(loca ionB)
in ege old_A 0
in ege new_B 0
T1's iew o memo y
loca ions A and B a e
pe o ming bo h READs
Figu e 4.10: Time diag am illus a ing he need o a SNAPSHOT ope a ion, h ough
an example whe e wo h eads T1and T2execu e concu en ope a ions o e wo
loca ions Aand B.T1 ails o ead bo h loca ions in such a way ha i e ie es
a alid s a e o memo y. I cap u es a memo y s a e ha co esponds o di e en
momen s in ime pe loca ion, and his is in alid.
4.5. SNAPSHOT Ope a ion 47
ope a ion in a concu en se ing when his ope a ion consis s on se e al sub-s eps,
ha ha e o be coo dina ed in o de o p o ide an accu a e pic u e o he s a e o
memo y. This mo i a es he in oduc ion o a new ope a ion ha p ecisely answe s
o his equi emen : p o iding a "pic u e" (which we will call SNAPSHOT) o K
memo y loca ions a once, wi h gua an ees ha i accu a ely ep esen s he s a e o
memo y a a speci ic poin in ime be ween he in oca ion o he ope a ion and i s
inalisa ion. The pseudo-code o his ope a ion can be ound in Figu e 4.11.
1uin 64_ [1..k] COLLECT_VALUES(uin 64_ k, loc_s uc *[1.. k] A) {
2uin 64_ [1..k] V;
3 o ( uin 64_ i = 1; i <= k; i++) {
4V[i] = READ(A[i]);
5}
6 e u n V;
7}
8
9uin 64_ [1.. k] COLLECT_SNAPSHOT_TS ( uin 64_ k, loc_s uc * [1.. k] A
) {
10 uin 64_ [1..k] T;
11 o ( uin 64_ i = 1; i <= k; i++) {
12 T[i] = A[i]-> snapsho _ s ;
13 }
14 e u n T;
15 }
16
17 uin 64_ [1.. k] SNAPSHOT ( uin 64_ k, loc_s uc * [1..k] A) {
18 uin 64_ [1..k] Times amps_1 , Times amps_2 ;
19 uin 64_ [1.. k] Values_1 , Values_2 ;
20 while ( ue) {
21 Times amps_1 = COLLECT_SNAPSHOT_TS (k, A);
22 Values_1 = COLLECT_VALUES (k, A);
23 Values_2 = COLLECT_VALUES (k, A);
24 Times amps_2 = COLLECT_SNAPSHOT_TS (k, A);
25 i ( o all i, ( Times amps_1 [i] == Times amps_2 [i])
26 && ( Values_1 [i] == Values_2 [i ]))
27 {
28 e u n Values_1;
29 }
30 }
31 }
Figu e 4.11: Pseudo-code o he SNAPSHOT ope a ion.
The SNAPSHOT ope a ion is a well-known non-blocking echnique capable o ob-
aining he con en o a numbe o memo y loca ions in a single poin in ime. In a
ew wo ds, i wo ks by epea edly collec ing he con en o he loca ions in a sequen-
ial manne ( h ough se e al READ ope a ions called one a e he o he by he same
h ead), and hen compa ing he e ie ed con en o he ones ead in i s p e ious
"collec ". Once wo "collec s" ha e e u ned exac ly he same alues o e e y one
o he loca ions, we can e u n hese as he SNAPSHOT o memo y.
The "collec ion" o alues is done by an auxilia y ope a ion COLLECT_VALUES
48 Chap e 4. Non-blocking K-Compa e-Single-Swap (KCSS)
(see lines 1 o 7 in Figu e 4.11), which we will explain la e in dep h. A e wo
calls o COLLECT_VALUES e u n he same se o alues, we a e gua an eed ha he
collec ed loca ions ha e main ained he same con en a a speci ic momen in ime,
which us he momen in ime is he one he SNAPSHOT ep esen s.
The only emaining ques ion is how o de e mine whe he a alue has indeed
no changed be ween bo h COLLECT_VALUES ope a ions. We a e al eady amilia
wi h he ABA p oblem (See Example 4.4.3), so we can hin a he possibili y
o i occu ing in he cou se o a SNAPSHOT ope a ion: I a h ead T1pe o ms
COLLECT_VALUES on a se o loca ions A[1..K] and e ie es alues Values_1[1..K],
bu hen comes ano he h ead T2who changes he con en s o A[1..K] o di e -
en alues Values_2[1..K] and hen back again o Values_1[1..K], a subsequen
COLLECT_VALUES call by T1would hink no one else has changed A[1..K]’s con en s
in he mean ime, and his is no ue.
To sol e he ABA p oblem once again we apply he imes amp mechanism ha
LL/SC used. These imes amps, consis ing o a uple ⟨ h eadID, agnumbe ⟩ ha will
be s o ed oge he wi h he alues ha ep esen memo y loca ions in loc_s uc ,
as we can see on Figu e 4.2, ield snapsho _ s. Th eads will upda e snapsho _ s
upon e e y modi ica ion o a loca ion s uc u e loc_s uc (See Line 9 a Fig-
u e 4.4), enabling o he s and i sel o know who has las modi ied a loca ion ( hanks
o snapsho _ s’s ield h eadID), and o di e en ia e se e al own modi ica ions
( hanks o snapsho _ s’s ield agnumbe ). Times amps will be collec ed oge he
wi h loca ions’ con en , hanks o being s o ed as loc_s uc s uc u es, by op-
e a ion COLLECT_SNAPSHOT_TS.SNAPSHOT will hen equi e ha bo h he esul o
COLLECT_VALUES and COLLECT_SNAPSHOT_TS ma ch om a collec ion o he o he
one, in o de o p o ide a co ec "pic u e" o memo y.
SNAPSHOT pseudo-code in de ail (Figu e 4.11): A call o SNAPSHOT(K,
A[1..K]) by a h ead Tconsis s o a while( ue) loop ha epea edly pe o ms
he ollowing:
1. Calls COLLECT_SNAPSHOT_TS(K, A[1..K]) and s o es he e u ned a ay o
imes amps in o Times amps_1.
2. Calla COLLECT_VALUES(K, A[1..K]) o e ie e he alues in loca ions A[1..K],
and s o e he e u ned a ay in o Values_1.
3. Then i epea s s eps 1 and 2, bu s o ing he esul s in o a ay Times amps_2
and Values_2.
4. Finally i compa es alues in a ays Values_1 and Values_2, and imes amps
Times amps_1 and Times amps_2. I no unma ched alue o imes amp is
ound, SNAPSHOT e u ns Values_1 as he esul . O he wise, i es a s on
S ep 1.
As we can see a Lines 1 o 15 o Figu e 4.11, auxilia y ope a ions COLLECT_VALUES
and COLLECT_SNAPSHOT_TS simply loop o e loca ion s uc u es and e ie e he con-
en in which hey a e in e es ed. No e he use o ope a ion READ by COLLECT_VALUES,
4.6. KCSS Ope a ion 49
which is necessa y in o de o gua an ee ha COLLECT_VALUES only e u ns p og am
alues.
4.6. KCSS Ope a ion
The inal s ep in o de o build KCSS, is o pu all pieces ha we ha e seen so
a oge he . As we discussed in Sec ion 4.2, a KCSS call:
KCSS (Loca ions[A_1..A_k], Expec edVals[e_1..e_k], newValue_1)
checks ha e e y loca ion A_i con ains i s expec ed alue e_i. I his is he case,
hen i upda es A_1 wi h he new alue newValue_1. O he wise, i does no modi y
any memo y loca ion.
We now know how o ind ou a loca ion’s p og am alue e en on loca ions
unde going changes by o he h eads; we ha e seen how o success ully modi y he
con en o a loca ion while ensu ing ha no o he h ead has accessed i ; and we
know how o co ec ly e ie e he alue o Kloca ions a a speci ic poin in ime.
These a e all he pieces we ha e o pu oge he .
1bool KCSS(uin 64_ k, loc_s uc * [1..k] A, uin 64_ [1.. k]
expec edValues , uin 64_ newValue ) {
2uin 64_ [1.. k] oldValues ;
3while ( ue) {
4oldValues [1] = LL(A [1]);
5oldValues [2.. k] = SNAPSHOT (k - 1, A[2.. k]);
6i ( o some i, oldValues[i] != expec edValues [i]) {
7SC(A[1] , oldValues [1]) ; // e e A[1] o oldValues [1]
8 e u n alse ;// KCSS was unsuccess ul
9}
10 // else y o inalise :
11 i ( SC(A[1] , newValue )) {
12 e u n ue ;// KCSS was success ul
13 }
14 }
15 }
Figu e 4.12: Pseudo-code o he KCSS ope a ion.
A h ead Texecu ing a call o KCSS simply does he ollowing ( he pseudo-code
o his ope a ion can be ound on Figu e 4.12):
1. A Line 4, Tini ia es an LL/SC on loca ion A_1 by pe o ming LL(A_1), decla -
ing i s in en ions o modi ying his loca ion.
2. A Line 5, be o e p oceeding wi h he modi ica ion o A_1,Thas o make
su e ha he Kloca ions i is conside ing will main ain hei con en
om now un il T’s ac ion o "commi ing" i s modi ica ions o A_1.
56 Chap e 5. K-CSS C++ Implemen a ion
along, he KCSS code manages uin 64_ alues which i ea s as memo y wo ds;
and auxilia y me hods a e employed a imes o p ese e he o ma cha ac e is ics
ha his ep esen a ion ca ies, anspa en ly o me hods like LL,SC,SNAPSHOT, e c.
1// loc_s uc _ o uin 64_ and in 64_
2 empla e< ypename T>
3s uc loc_s uc _ <T, s d :: enable_i _ < s d :: is_same_ <T,
uin 64_ > || s d :: is_same_ <T,in 64_ >>> : loc_s uc _base {
4
5s uc 63 {
6Tloca ion_ ype :1;
7Tcon en :63;
8};
9
10 loc_s uc _ () noexcep :
11 loc_s uc _base() {
12 }
13
14 loc_s uc _ (T ) noexcep :
15 loc_s uc _base( o_ alue_ ( )) {
16 }
17
18 cons exp inline uin 64_ o_ alue_ (T ) cons noexcep {
19 union {
20 63 x;
21 uin 64_ _x;
22 };
23 x. loca ion_ ype = 0;
24 x. con en = ;
25
26 e u n _x;
27 }
28
29 cons exp inline T om_ alue_ (uin 64_ ) cons noexcep {
30 union {
31 63 x;
32 uin 64_ _x;
33 };
34 _x = ;
35
36 e u n x. con en ;
37 }
38 };
Figu e 5.3: loc_s uc _ <T> C++ code, when Tis ei he uin 64_ o in 64_ .
Le us now look a wo key me hods in cha ge o o ma -compliance, p o ided by
all loc_s uc _ <T> decla a ions (and in pa icula by loc_s uc _ <uin 64_ >
and loc_s uc _ <in 64_ >s uc u es): o_ alue_ and om_ alue_ (lines 18
o 37 on Figu e 5.3 con ain he co esponding C++ code).
Me hod o_ alue_ (T ) is used o con e a use -p o ided alue in o i s ade-
qua e ep esen a ion as a uin 64_ alue (a memo y wo d), jus like he pseudo-code
me hod make_P og amValue did (see Figu e 4.5 o he usage o his me hod). I is
5.1. Da a S uc u es and De ined Types 57
an auxilia y me hod o "encode" a use -p o ided alue in o i s KCSS ep esen a ion,
all he while occupying a 64bi -wo d). This is done employing he C++ union capa-
bili y, which allows mo e han one a iable, possibly wi h di e en ype, o be s o ed
he same memo y. This means ha he alue in ha memo y can be in e p e ed
as one ype o ano he , depending which a iable we use o e e o i . In his case,
o_ alue_ exploi s his capabili y o e-in e p e he use -de ined alue (which
is ul ima ely a 64bi wo d uin 64_ ) as a 63 s uc u e. This is done so ha we
can ake ad an age o he ease o bi manipula ion h ough bi ield assignmen o
do he ollowing: A 63 s uc u e xis decla ed in he scope o a union cons uc ,
al oge he wi h a uin 64_ alue _x (Lines 19 o 22 on Figu e 5.3), which means
ha he assignmen s on Lines 23 and 24 in Figu e 5.3 do no only modi y x’s bi s,
bu also _x’s. In pa icula , he las bi ( 63->loca ion_ ype) o bo h xand _x
will con ain a 0 o indica e ha he alue con ained is a p og am alue; and he
emaining 63bi s ( 63->con en ) will be illed using he 64bi use -p o ided alue
, which will be au oma ically unca ed o i in o 63bi s ( his is he eal powe o
bi ield assignmen ).
Me hod om_ alue_ (uin 64_ ) does he oposi e o o_ alue_ . I ex-
ac s he con en o a KCSS p og am alue in o de o e u n i s use - o ma -
complying alue. Once again, his is done employing he C++ union capabili y o
e-in e p e he uin 64_ alue as a 63 s uc u e so ha we can easily access
he 63 s uc u e’s bi ields. Mo e speci ically, we a e in e es ed in he con en
bi s o , which a e he 63 leas signi ican ones. The e o e his me hod e u ns
63->con en , which C++’s union will au oma ically i in o a uin 64_ alue _x
ha will be hen e-in e p e ed as a T ype upon e u n.
No e ha he p ocessing we ha e desc ibed o alues o ype uin 64_ o
in 64_ a ies o o he ypes. Since KCSS has an exhaus i e se o empla es
co e ing all possible p imi i e da a ypes, he compile will choose he app op i-
a e one depending on he da a ype p o ided by he use . Poin e s a e by de aul
aligned on memo y add esses ha a e e en ha hey can be ep esen ed wi hou
he need o emo e 1 p ecision bi as i happens o in ege s (because he leas
signi ican bi is always ze o). This is also he case o ypes occupying less han
64bi s (such as in 8_ ,in 16_ ,in 32_ and single-p ecision loa ing-poin num-
be s): hey can be ep esen ed wi hou modi ying he o iginal alue because hey
i in o 63bi s, which is he maximum alloca ion o bi s ha alues can use. Thei
co esponding loc_s uc _ s uc u e jus needs o implemen he o_ alue_
and om_ alue_ me hods so ha all loc_s uc _ s uc u es sha e a common
in e ace, and all necessa y ype con e sions can be pe o med.
The C++ code co esponding o he loc_s uc _ <T> o he a o emen ioned
cases can be ound a Figu e 5.4 (code o nume ic ypes occupying less han 64bi s)
and Figu e 5.5 (code o he poin e case).
On he o he hand, double-p ecision loa ing-poin numbe s (double) pose a
new challenge because hei bi -wise ep esen a ion consis s o se e al pa s1: sign
(1 bi ), exponen (11 bi s), and man issa o ac ion (52 bi s); as we can see on
1h ps://en.wikipedia.o g/wiki/Double-p ecision_ loa ing-poin _ o ma
58 Chap e 5. K-CSS C++ Implemen a ion
1// loc_s uc _ o any nume ic ype o size smalle han 8 by es
2 empla e< ypename T>
3s uc loc_s uc _ <T,
4s d :: enable_i _ <
5(s d::is_in eg al_ <T> || s d::is_ loa ing_poin _ <T>)
6&& ( sizeo (T) < 8) >> : loc_s uc _base {
7
8loc_s uc _ () noexcep :
9loc_s uc _base() {
10 }
11
12 loc_s uc _ (T ) noexcep :
13 loc_s uc _base( o_ alue_ ( )) {
14 }
15
16 cons exp inline uin 64_ o_ alue_ (T ) cons noexcep {
17 union {
18 s uc {
19 uin 8_ loca ion_ ype ;
20 Ta2;
21 } ;
22 uin 64_ a1;
23 };
24 a1 = 0;
25 .a2 = ;
26
27 e u n a1;
28 }
29
30 cons exp inline T om_ alue_ (uin 64_ ) cons noexcep {
31 union {
32 s uc {
33 uin 8_ loca ion_ ype ;
34 Ta2;
35 } ;
36 uin 64_ a1;
37 };
38 a1 = ;
39
40 e u n .a2;
41 }
42 };
Figu e 5.4: loc_s uc _ <T> C++ code, when Tis any any nume ic ype o size
smalle han 8by es (64bi s).
5.1. Da a S uc u es and De ined Types 59
1// loc_s uc _ o poin e s
2 empla e< ypename T>
3s uc loc_s uc _ <T*> : loc_s uc _base {
4
5loc_s uc _ () noexcep :
6loc_s uc _base() {
7}
8
9explici loc_s uc _ (T* ) noexcep :
10 loc_s uc _base( o_ alue_ ( )) {
11 }
12
13 cons exp inline uin 64_ o_ alue_ (T* ) cons noexcep {
14 s a ic_asse ( ( aligno (T) & 1) == 0 );
15 union {
16 T* _aux ;
17 uin 64_ a;
18 };
19 _aux = ;
20 asse ((a & 1) == 0);// poin e mus be aligned o e en
add ess
21
22 e u n a;
23 }
24 cons exp inline T* om_ alue_ (uin 64_ ) cons noexcep {
25 union {
26 T*a;
27 uin 64_ _aux ;
28 };
29 _aux = ;
30
31 e u n a;
32 }
33 };
Figu e 5.5: loc_s uc _ <T> C++ code, when Tis a poin e .
60 Chap e 5. K-CSS C++ Implemen a ion
Figu e 5.6. In his case, "s ealing 1 p ecision bi " is s ill he mechanism we will use
o ep esen hem as loc_s uc _ s uc u es, se ing o 0 he leas signi ican bi
o he man issa. In p ac ice, jus like in he case o in ege numbe s, his means
we educe he ange o possible alues, bu in his case he loss o p ecision is e en
mo e negligible: The maximum ela i e ounding e o will be exac ly o 2−53. This
is accep able because 64bi alues co e a as amoun o possible numbe s, almos
inex inguishable o a common-use p og am. Ne e heless, he use will ha e o be
wa ned abou his limi a ion, o he sake o co ec ness.
Figu e 5.6: Componen s o a double-p ecision loa ing-poin numbe . Figu e aken
om h ps://en.wikipedia.o g/wiki/Double-p ecision_ loa ing-poin _
o ma .
Figu e 5.7 con ains he C++ code co esponding o he loc_s uc _ <T> s uc-
u e, when Tis a double-p ecision loa ing-poin numbe (double). We can see on
Line 18 ha he way me hod o_ alue_ wo ks in his case is sligh ly di e en o
he uin 64_ and in 64_ case. Ins ead o using an auxilia y s uc u e (like s uc
63) and bi ield assignmen , double alues a e be e manipula ed using bi -wise
ope a ions. So o_ alue_ uses he union cons uc o apply bi -wise ope a ion
&(logical AND) o use -p o ided alue double ( ha has been assigned o alue
double a1 and he e o e o uin 64_ a2 on Line 17 o Figu e 5.7), " u ning" he
leas signi ican bi o he man issa o 0, which will ep esen he loca ion_ ype
ield in KCSS alue o ma (being 0indica es i is a p og am alue).
All in all, we ha e p o ided p oo ha he e a e mechanisms in place so ha
use s do no ha e o meddle wi h he in e nal ep esen a ion o memo y in KCSS.
They will simply call KCSS’s me hods using w appe s ha KCSS p o ides so ha
hey can decla e which alues a e going o be suscep ible o expe iencing a KCSS
ope a ion, bu wi hou knowing wha ac ions a e being ca ied ou a he KCSS class
o enable his. When use s decla e a alue o ype KCSS::loc_s uc _ <T> (Tbeing
some ype de ini ion o hei choice), he C++ compile will au oma ically assign i
o i s co esponding empla e, whose de ini ion is such ha he es o he me hods
in KCSS (LL, SC, SNAPSHOT, ...) can use i like any o he KCSS::loc_s uc _
piece o da a.
5.2. Th eads and hei Iden i ie s 61
1 empla e<>
2s uc loc_s uc _ <double > : loc_s uc _base {
3
4loc_s uc _ () noexcep :
5loc_s uc _base() {
6}
7
8loc_s uc _ (double ) noexcep :
9loc_s uc _base( o_ alue_ ( )) {
10 }
11
12 cons exp inline uin 64_ o_ alue_ ( double ) cons noexcep {
13 union {
14 double a1;
15 uin 64_ a2;
16 };
17 a1 = ;
18 a2 = a2 & 0x e; // u n he leas signi ican
bi o he man issa o 0
19
20 e u n a2;
21 }
22
23 cons exp inline double om_ alue_ (uin 64_ ) cons noexcep
{
24 union {
25 uin 64_ a2;
26 double a1;
27 };
28 a2 = ;
29
30 e u n a1;
31 }
32 };
Figu e 5.7: loc_s uc _ <T> C++ code, when Tis a double-p ecision loa ing-poin
numbe .
5.2. Th eads and hei Iden i ie s
Ano he me hod wo h men ioning, ela ed o compliance wi h KCSS’s ep esen-
a ion o ma o alues, is me hod (depic ed in Figu e 5.8):
make_Tempo alValue(uin 16_ h ead_ID, uin 64_ ag_numbe )
As he name sugges s, his me hod akes as pa ame e s he componen s necessa y o
build a empo al alue ( h ead_ID and ag_numbe ) and e u ns he esul ing 64bi -
complian ep esen a ion ( o a eminde o empo al alues, e e o Sec ion 4.3).
Tempo al alues a e ep esen ed ia s uc Tempo alValue, which uses C++’s bi
ields o manage he bi -wise manipula ion o i s h ee componen s: loca ion_ ype
(1 bi ), h ead_ID (15 bi s) and ag_numbe (48 bi s), which make up a single
62 Chap e 5. K-CSS C++ Implemen a ion
64bi memo y wo d (uin 64_ alue). make_Tempo alValue simply ills hese ields
gi en he pa ame e s i ecei es, se ing loca ion_ ype o be 1 (which is empo al
alues’ iden i ying ai ). This las bi is p ecisely he one checked by auxilia y
me hod is_Tempo alValue(uin 64_ ), which e u ns ue i he gi en alue
is a empo al alue, and alse o he wise.
1s uc Tempo alValue {
2uin 64_ loca ion_ ype :1;
3uin 64_ h ead_ID :15;
4uin 64_ ag_numbe :48;
5};
6s a ic_asse ( sizeo (Tempo alValue) == 8 );
7
8cons exp inline bool is_Tempo alValue(uin 64_ ) cons noexcep
{
9 e u n ( & 0x0000000000000001) == 1;
10 }
11
12 inline cons exp uin 64_ make_Tempo alValue(uin 16_ h ead_ID,
13 uin 64_ ag_numbe ) cons noexcep {
14 union {
15 Tempo alValue ;
16 uin 64_ a;
17 };
18
19 . h ead_ID = h ead_ID ;
20 . ag_numbe = ag_numbe ;
21 . loca ion_ ype = 1;
22
23 e u n a;
24 }
Figu e 5.8: make_Tempo alValue C++ code, oge he wi h some auxilia y me hods.
The way o ob ain he cu en ly unning h ead’s iden i ie , is h ough me hod
my_ h ead_id(). This me hod (see Figu e 5.9) makes use o a h ead_local a i-
able my_ h ead_id ha is also s a ic, which s o es he inc emen by one uni o
p i a e a iable _ h ead_id. The combina ion o being h ead_local and s a ic
means ha his a iable has a local alue o e e y h ead (i is no sha ed) and ha
i is only assigned once ( he i s ime he me hod is called). The e o e, e e y ime
me hod my_ h ead_id() is called, i will e u n he esul o ha ing inc emen ed
p i a e a iable _ h ead_id he i s ime ha i was called.
Me hod h ead_id(uin 64_ ) (see lines 6 o 13 on Figu e 5.9) is an aux-
ilia y me hod ha ex ac s ield h ead_ID om a empo al alue a iable . I
is employed by he RESET ope a ion in o de o index he SAVED_VAL a ay (see
Sec ion 4.4 o a eminde o he RESET ope a ion).
5.3. Implemen a ion o me hods LL and SC 63
1uin 16_ my_ h ead_id() noexcep {
2 h ead_local s a ic uin 16_ my_ h ead_id = _ h ead_id ++;
3 e u n my_ h ead_id;
4}
5
6cons exp inline uin 16_ h ead_id ( uin 64_ ) cons noexcep {
7union {
8Tempo alValue ;
9uin 64_ a;
10 };
11 a = ;
12
13 e u n . h ead_ID ;
14 }
Figu e 5.9: my_ h ead_id and h ead_id C++ code.
5.3. Implemen a ion o me hods LL and SC
The C++ code o LL and SC ope a ions exac ly ollows he pseudo-code we ex-
plained in Sec ion 4.4. I we e ace ou s eps back o he pseudo-code o LL (see Fig-
u e 4.4), we can compa e bo h igu es s a emen by s a emen and see hey a e iden-
ical. In he case o SC ope a ions, howe e , he e is a mino di e ence: ou pseudo-
code implemen a ion (see Figu e 4.5) includes a call o make_P og amValue(a,
new_p og am_ al), which is no p esen on he C++ e sion o he code. This is be-
cause in his case i will ac ually be called wi h a p og am alue (i.e., a alue whose
i s bi is 0, and al eady adap ed o i in 63 bi s – see he discussion in he p e ious
sec ion). This is he esul o ou ca e ul and anspa en managemen o da a o -
ma s using loc_s uc _ <T> s uc u es and hei o_ alue_ and om_ alue_
me hods. All o KCSS’s code manages uin 64_ alues ha al eady comply o he
KCSS o ma o p og am and empo al alues, so he call o make_P og amValue
(which in C++ has an equi alen me hod named o_ alue_ ) will ha e al eady been
done be o e calling SC. We can see an example o his da a o ma compliance be o e
calling LL and SC on he KCSS ope a ion code, ha will be explained in Sec ion 5.5.
As o auxilia y ope a ions RESET and READ ( hei C++ implemen a ion can be
ound on Figu e 5.12), once again hei pseudo-code (see Figu e 4.9) and hei C++
implemen a ion exac ly ma ch i we compa e e e y code s a emen one by one.
5.4. Implemen a ion o SNAPSHOT me hod
The C++ code o he SNAPSHOT ope a ion can be ound on Figu e 5.13, al oge he
wi h he C++ code o i s auxilia y ope a ions COLLECT_SNAPSHOT_TS (Figu e 5.14)
and COLLECT_VALUES (Figu e 5.15). The eade is encou aged o look back in o
Sec ion 4.5 and e i y ha he pseudo-code p o ided o hese ope a ions (see Fig-
u e 4.11) exac ly ma ches he C++ code in Figu es 5.13, 5.14 and 5.15, he only di -
e ence being ha ou C++ implemen a ion o auxilia y ope a ions COLLECT_VALUES
64 Chap e 5. K-CSS C++ Implemen a ion
1inline uin 64_ ll( loc_s uc _base *a) noexcep {
2while ( ue) {
3TAG_NUMBERS [ my_ h ead_id () ]++;
4uin 64_ old_ al = ead(a);
5SAVED_VAL [ my_ h ead_id ()] = old_ al ;
6uin 64_ emp_ al = make_Tempo alValue ( my_ h ead_id () ,
7TAG_NUMBERS [ my_ h ead_id () ]) ;
8i ( cas (&a-> alue , old_ al , emp_ al )) {
9a-> snapsho _ s = emp_ al ;
10 e u n old_ al;
11 }
12 }
13 }
Figu e 5.10: LL ope a ion C++ code.
1inline bool sc( loc_s uc _base *a, uin 64_ new_p og_ al)
noexcep {
2uin 64_ emp_ al = make_Tempo alValue ( my_ h ead_id () ,
TAG_NUMBERS [ my_ h ead_id () ]) ;
3 e u n cas (&a-> alue , emp_ al , new_p og_ al );
4}
Figu e 5.11: SC ope a ion C++ code.
1inline oid ese ( loc_s uc _base *a) noexcep {
2uin 64_ old_ al = a-> alue ;
3i ( is_Tempo alValue ( old_ al )) {
4cas (&a-> alue , old_ al , SAVED_VAL [ h ead_id (old_ al )]);
5}
6}
7
8inline uin 64_ ead(loc_s uc _base *a) noexcep {
9while ( ue) {
10 uin 64_ al = a -> alue ;
11 i (! is_Tempo alValue ( al ))
12 e u n al;
13 ese (a);
14 }
15 }
Figu e 5.12: ese and ead ope a ions C++ code.
and COLLECT_SNAPSHOT_TS do no e u n he a ay o alues o ags, bu ins ead
modi y an a ay pa ame e hey ecei e by alue e e ence.
5.5. Implemen a ion o KCSS me hod 65
1inline oid snapsho ( s d :: size_ k, loc_s uc _base **a, uin 64_
* alues_1 ) noexcep {
2uin 64_ imes amps_1[k], imes amps_2[k];
3uin 64_ alues_2 [k ];
4
5while ( ue) {
6collec _snapsho _ s (k, a, imes amps_1 );
7collec _ alues (k, a, alues_1 );
8collec _ alues (k, a, alues_2 );
9collec _snapsho _ s (k, a, imes amps_2 );
10
11 unsigned i = 0;
12 while (i < k && imes amps_1 [i] == imes amps_2 [i] &&
alues_1 [i] == alues_2 [i ])
13 ++i;
14
15 i (i == k)
16 e u n;
17 }
18
19 e u n;
20 }
Figu e 5.13: SNAPSHOT ope a ion C++ code.
1inline cons exp oid collec _snapsho _ s(cons s d :: size_ k ,
2loc_s uc _base **a, uin 64_ * ) cons noexcep {
3 o ( unsigned in i = 0; i < k; ++i) {
4 [i] = a[i]-> snapsho _ s ;
5}
6}
Figu e 5.14: COLLECT_SNAPSHOT_TS ope a ion C++ code.
1inline oid collec _ alues(cons s d :: size_ k, loc_s uc _base
**a,
2uin 64_ * ) noexcep {
3 o ( unsigned in i = 0; i < k; ++i) {
4 [i] = ead(a[i]);
5}
6}
Figu e 5.15: COLLECT_VALUES ope a ion C++ code.
5.5. Implemen a ion o KCSS me hod
The C++ code o he KCSS ope a ion can be ound on Figu e 5.16. No e ha
KCSS is he only ope a ion among he ones we ha e desc ibed (LL,SC,SNAPSHOT, ...)
ha is public o he use o access.
The KCSS C++ implemen a ion sligh ly a ies om he pseudo-code p o ided in
72 Chap e 5. K-CSS C++ Implemen a ion
1 oid wo_ h eads() {
2
3// Ini ial lis : a(1) -> c (3) -> d(4)
4node *d = new node (4 , nullp );
5node *c = new node (3 , d);
6node *a = new node (1 , c);
7
8s d :: cou << " C ea ing ini ial lis consis ing o : n";
9p in _lis (a);
10
11 // We wan T1 o dele e node d (4) , while T2 inse s b(2).
12
13 au o dele e_d = [&]() { // Will make use o KCSS whe e K = 2.
14 // The i s loca ion in ol ed is c->nex , and he second one
is d->nex
15 s d :: cou << " Dele ing node d(4) ... n";
16 // Apply kcss ope a ion :
17 bool success = kcss_ins ance .kcss (c->nex , d , ( node *) nullp ,
KCSS:: mp (d ->nex , ( node *) nullp ));
18 i ( success ){ // Now i is sa e o dele e node e
19 s d :: cou << " Dele ion ope a ion success ul . n";
20 }else{// Failu e o kcss
21 s d :: cou << " Dele ion ope a ion unsuccess ul . n";
22 }
23 };
24 au o inse _b = [&]() { // Will make use o KCSS whe e K = 1.
25 node *b = new node (2 , c);
26 s d :: cou << " Inse ing node b(2) ... n";
27 bool success = kcss_ins ance .kcss (a->nex , c , b);
28 i ( success ){ // Now i is sa e o dele e node e
29 s d :: cou << " Inse ion ope a ion success ul . n";
30 }else{// Failu e o kcss
31 s d :: cou << " Inse ion ope a ion unsuccess ul . n";
32 }
33 };
34
35 in num_ h eads = 2;
36 s d :: h ead [ num_ h eads ];
37 [0] = s d :: h ead ( dele e_d );
38 [1] = s d :: h ead ( inse _b );
39
40 [0]. join ();
41 [1]. join ();
42
43
44 s d:: cou << " Cu en lis : n";
45 p in _lis (a);
46
47 // Pe o m he desi ed ac ions wi h he lis (...)
48
49 cleanup (a);
50 }
Figu e 5.21: KCSS ope a ion es using wo h eads o e a linked lis , on C++ code.
5.7. Concluding Rema ks 73
1 oid n_ h eads ( s d :: size_ n) {
2
3KCSS:: loc_s uc _ <in > 1 (10);
4KCSS:: loc_s uc _ <in > 2 (20);
5KCSS:: loc_s uc _ <in > 3 (30);
6
7au o = [&]() {
8while ( ue) {
9in x = kcss_ins ance . ge ( 1 );
10 i (x > 100000)
11 b eak ;
12 kcss_ins ance .kcss( 1 , x, x + 1, KCSS:: mp ( 2 , 20) , KCSS:: mp(
3 , 30));
13 }
14 };
15
16 s d :: h ead [n];
17 o (au o i = 0u; i < n; i++)
18 [i] = s d :: h ead ( );
19 o (au o i = 0u; i < n; i++)
20 [i]. join ();
21
22
23 s d:: cou << " nThe inal alue o 1 is: " << kcss_ins ance . ge (
1) << s d :: endl ;
24
25 }
Figu e 5.22: KCSS ope a ion es using n h eads concu en ly a emp ing o modi y
a single loca ion, on C++ code.
1in main (){
2
3s d :: cou << " nTes 1 n";
4one_ h ead ();
5
6s d :: cou << " nTes 2 n";
7 wo_ h eads();
8
9s d :: cou << " nTes 3 n";
10 n_ h eads (6);
11
12 e u n 0;
13 }
Figu e 5.23: KCSS ope a ion es ing main() me hod, on C++ code.
74 Chap e 5. K-CSS C++ Implemen a ion
1 empla e< s d :: size_ k>
2inline oid collec _ alues_(loc_s uc _base **a, uin 64_ * )
noexcep {
3collec _ alues_ <k - 1>(a, );
4 [k - 1] = ead (a[k - 1]) ;
5}
6
7 empla e<>
8inline oid collec _ alues_ <0 >( loc_s uc _base**, uin 64_ *)
noexcep {
9}
Figu e 5.24: Rede ini ion o ope a ion COLLECT_VALUES, on C++ code.
1 empla e< s d :: size_ k>
2inline cons exp oid collec _snapsho _ s_(loc_s uc _base **a,
3uin 64_ * ) cons noexcep {
4collec _snapsho _ s_ <k - 1 >(a, );
5 [k - 1] = a[k - 1]-> snapsho _ s ;
6}
7
8 empla e<>
9inline cons exp oid collec _snapsho _ s_ <0 >( loc_s uc _base**,
10 uin 64_ *) cons noexcep {
11 }
Figu e 5.25: Rede ini ion o ope a ion COLLECT_SNAPSHOT_TS, on C++ code.
5.7. Concluding Rema ks 75
1// e al_cond_ me hod o ede ined snapsho _
2 empla e< s d :: size_ k>
3inline bool e al_cond_(uin 64_ * alues_1, uin 64_ * alues_2 ,
uin 64_ * imes amps_1 ,
4uin 64_ * imes amps_2) noexcep {
5 e u n e al_cond_ <k - 1>( alues_1 , alues_2 , imes amps_1 ,
imes amps_2)
6&& imes amps_1 [k - 1] == imes amps_2[k - 1]
7&& alues_1 [k - 1] == alues_2 [k - 1];
8}
9
10 empla e<>
11 inline bool e al_cond_ <0 >( uin 64_ *, uin 64_ *, uin 64_ *,
12 uin 64_ *) noexcep {
13 e u n ue ;
14 }
15
16 // snapsho _ me hod
17 empla e< s d :: size_ k>
18 inline oid snapsho _ ( loc_s uc _base **a, uin 64_ * alues_1 )
noexcep {
19 uin 64_ imes amps_1[k], imes amps_2[k];
20 uin 64_ alues_2 [k ];
21
22 while ( ue) {
23 collec _snapsho _ s_ <k >(a, imes amps_1 );
24 collec _ alues_ <k >(a , alues_1 );
25 collec _ alues_ <k >(a , alues_2 );
26 collec _snapsho _ s_ <k >(a, imes amps_2 );
27
28 i ( e al_cond_ <k >( alues_1 , alues_2 , imes amps_1 ,
imes amps_2))
29 e u n;
30 }
31
32 e u n;
33 }
34
35 empla e<>
36 inline oid snapsho _ <0>(loc_s uc _base**, uin 64_ *) noexcep {
37 }
Figu e 5.26: Rede ini ion o ope a ion SNAPSHOT, on C++ code.
76 Chap e 5. K-CSS C++ Implemen a ion
1 empla e< ypename T0 , ypename ...Ts >
2bool kcss_ ( loc_s uc _ <T0 > &a0 , T0 a0_exp , T0 a0_new , Ts &&...
a gs) noexcep {
3
4cons exp s d :: size_ k = sizeo ...( a gs ) + 1;
5
6uin 64_ old_ als [k ];
7uin 64_ exp_ als [k] = { a0. o_ alue_ ( a0_exp ) ,
8( a gs . i s . o_ alue_ ( a gs . second )) ... };
9loc_s uc _base *a[k] = { &a0 , (& a gs . i s )... };
10 uin 64_ new_ = a0 . o_ alue_ ( a0_new );
11
12 while ( ue) {
13 old_ als [0] = ll(a [0]);
14
15 snapsho _ <k - 1>(a + 1, old_ als + 1);
16 i ( e al_kcss_cond_ <k >( old_ als , exp_ als )) {
17 sc(a[0] , old_ als [0]) ;
18 e u n alse ;
19 }
20 // The p e ious code block is equi alen o he ollowing :
21 // snapsho (k - 1, a + 1, old_ als + 1);
22 // o ( unsigned in i = 0; i < k; ++i) {
23 // i ( old_ als [i] != exp_ als [i ]) {
24 // sc(a[0] , old_ als [0]) ;
25 // e u n alse ;
26 // }
27 // }
28
29 i ( sc(a[0] , new_ )) {
30 e u n ue ;
31 }
32 }
33
34 e u n alse ;
35 }
Figu e 5.27: Rede ini ion o ope a ion KCSS, on C++ code.
1 empla e< s d :: size_ k>
2inline bool e al_kcss_cond_(uin 64_ * old_ alues , uin 64_ *
exp_ alues ) noexcep {
3 e u n e al_kcss_cond_ <k - 1>( old_ alues , exp_ alues )
4|| old_ alues [k - 1] != exp_ alues [k - 1];
5}
6
7 empla e<>
8inline bool e al_kcss_cond_ <0 >( uin 64_ *, uin 64_ *) noexcep {
9 e u n alse ;
10 }
Figu e 5.28: Auxilia y condi ion e alua ion ope a ion o he ede ini ion o ope a-
ion KCSS, on C++ code.
Chap e 6
Conclusions and Fu u e Wo k
Th ough his wo k we ha e mo i a ed he need o u he esea ch on ools
ha exploi he capabili ies o mul i-co e sys ems, concu ency being he answe o
Moo e’s Law s ands ill. Analysing he challenges ha Concu en -Da a-S uc u e
design aces, we ha e unde s ood he delica e balance be ween e icien communica-
ion and au onomy be ween concu en ly execu ing h eads, and how pe ec iming
o hei ac ions is key o co ec ness.
The s udy o ine-g ained and coa se-g ained so wa e synch onisa ion mecha-
nisms has allowed us o unde s and he na u e o concu en se ings bo h om
he p ac ical and he heo e ical poin o iew, es ablishing a knowledge baseline
o guide he eade on swi ching om sequen ial o concu en easoning. Coa se-
g ained mechanisms p o ide simple solu ions a he cos o e iciency and adap abil-
i y. Fine-g ained mechanisms ip he balance owa ds he opposi e side, in exchange
o highe code complexi y ha makes he s udy o hese concu ency mechanisms
a delica e ask.
A his poin , he KCSS so wa e p imi i e has been sugges ed as an adequa e
commi men be ween e iciency and adap abili y, and code complexi y and usabili y.
A p o use explana ion o e e y ele an and non- i ial ea u e o KCSS has been
assembled, o se e as an educa ional esou ce easing he unde s anding o i s inne
wo kings. We ha e explo ed KCSS’s applicabili y o he design o Concu en Da a
S uc u es, mo e speci ically Concu en Linked Da a S uc u es, emphasising i s
pe o mance wi h espec o al e na i e solu ions o he synch onisa ion challenges
posed by hese Da a S uc u es.
To b ing o ligh he eal angible impac o his p imi i e, a ully- unc ional,
e icien and anspa en - o- he-use KCSS implemen a ion has been p o ided. This
ask has challenged ou ini ial commi men o make i easy o use, due o he s ic
memo y-loca ion in e p e a ion needs o KCSS and ou desi e o make i a ailable
o all common da a ypes. Ne e heless, C++’s ample capabili ies ( empla es, bi
ields, unc ion pa ame e packs) ha e allowed us o hide all implemen a ion de ails
om he use while main aining e iciency and co e age o all common da a ypes.
Finally, we ha e s udied how his p imi i e can be u he imp o ed, and how e-
77
78 Chap e 6. Conclusions and Fu u e Wo k
la ed wo k on mul i-loca ion so wa e synch onisa ion p imi i es could complemen
i . In pa icula , he ideas pu o wa d o design KCSS can be pu in o p ac ice o
de elop a ansac ional model wi h he same unc ionali y as KCSS bu imp o ed e i-
ciency and in ui i eness o he p ocess. The main idea is o ha e ansac ional loads
in cha ge o eco ding he in o ma ion collec ed in he i s hal o he SNAPSHOT op-
e a ion ha ou cu en KCSS implemen a ion pe o ms, and ansac ional commi s
doing he second pa o his ope a ion: de e mining i any o he alues ead has
been modi ied by a concu en ope a ion since being ead by he ansac ional load.
KCSS could also ye unde go u he concu ency imp o emen s: i is possible
o educe "collisions" be ween LL/SC ope a ions a he cos o a mo e complex
SNAPSHOT ope a ion. I is also possible o euse collec ed alues and imes amps by
his ope a ion om one i e a ion o he o he , downg ading eadabili y bu imp o -
ing o e all e iciency.
Conclusión
A a és de es e abajo hemos mo i ado la necesidad de segui in es igando
he amien as que explo en las capacidades de los sis emas mul inúcleo, siendo la
concu encia la espues a al es ancamien o de la Ley de Moo e. Al analiza los
desa íos a los que se en en a el diseño de Es uc u as de Da os Concu en es, hemos
comp endido el delicado equilib io en e ene comunicación e icien e y au onomía
en e hilos ejecu ándose simul áneamen e, y cómo la sinc onización pe ec a de sus
acciones es cla e pa a la co ección.
El es udio de los mecanismos de sinc onización de so wa e de g anula idad ina
y g uesa nos ha pe mi ido comp ende la na u aleza de los en o nos de ejecución
concu en es an o desde el pun o de is a p ác ico como eó ico, es ableciendo una
base de conocimien o pa a guia al lec o en el cambio de azonamien o secuencial
a concu en e. Los mecanismos de g anula idad g uesa p opo cionan soluciones
simples a cos a de la e iciencia y la adap abilidad. Los mecanismos de g anula idad
ina inclinan la balanza hacia el lado opues o, a cambio de una mayo complejidad
del código que hace que el es udio de es os mecanismos de concu encia sea una
a ea delicada.
En es e pun o, la p imi i a de so wa e KCSS se ha suge ido como un comp o-
miso adecuado en e e iciencia y adap abilidad, y complejidad y acilidad de uso del
código. Se ha elabo ado una explicación de allada de cada ca ac e ís ica ele an e
y no i ial de KCSS, si iendo como ecu so educa i o que acili a la comp ensión
de su uncionamien o in e no. Hemos explo ado la aplicabilidad de KCSS al dis-
eño de Es uc u as de Da os Concu en es, más especí icamen e Es uc u as de
Da os Enlazadas Concu en es, en a izando su desempeño con espec o a solu-
ciones al e na i as a los desa íos de sinc onización plan eados po es as Es uc u as
de Da os.
Pa a saca a la luz el impac o angible eal de es a p imi i a, se ha p opo cionado
una implemen ación de KCSS comple amen e uncional, e icien e y anspa en e pa a
el usua io. Es a a ea ha desa iado nues o comp omiso inicial de hace la ácil de
usa , debido a las es ic as necesidades de KCSS al in e p e a las ubicaciones de
memo ia y debido a nues o deseo de que sea compa ible con odos los ipos de
da os comunes. G acias a las amplias capacidades de C++ (plan illas, campos de
bi s, paque es de pa áme os de unción) hemos podido ocul a los de alles de im-
79
80 Chap e 6. Conclusions and Fu u e Wo k
plemen ación al usua io, man eniendo la e iciencia y cobe u a de odos los ipos de
da os.
Finalmen e, hemos es udiado cómo se puede mejo a aún más es a p imi i a y
cómo el abajo elacionado con las p imi i as de sinc onización de so wa e de ubi-
cación múl iple pod ía complemen a la. En pa icula , las ideas p opues as pa a
diseña KCSS se pueden pone en p ác ica pa a desa olla un modelo ansaccional
con la misma uncionalidad que KCSS pe o con mayo e iciencia y siendo más in-
ui i o. La idea p incipal es ene lec u as ansaccionales ( ansac ional loads en
inglés) a ca go de egis a la in o mación ecopilada en la p ime a mi ad de la
ope ación SNAPSHOT que ac ualmen e ealiza nues a implemen ación de KCSS, y
gua dados ansaccionales ( ansac ional s o es) ealizando la segunda pa e de es a
ope ación: de e mina si alguno de los alo es leídos ha sido modi icado po una
ope ación concu en e desde que ue leído po la lec u a ansaccional.
KCSS ambién pod ía expe imen a mejo as de su g ado de concu encia: es
posible educi las ”colisiones” en e ope aciones LL/SC a cos a de una ope ación
SNAPSHOT más compleja. También es posible eu iliza los alo es ecopilados y los
sellos de iempos ( imes amps) ecopilados po es a ope ación, de una i e ación a la
o a, lo que educe la legibilidad pe o mejo a la e iciencia gene al.
Bibliog aphy
Ba nes, G. A me hod o implemen ing lock- ee sha ed-da a s uc u es. In P o-
ceedings o he i h annual ACM symposium on Pa allel algo i hms and a chi ec-
u es - SPAA '93. ACM P ess, 1993.
Ba ei a, J. A. C. Mul ip ocesso s: Cohe ence and synch oniza ion, compu e
a chi ec u e cou se slides. 2023.
Dohe y, S.,He lihy, M.,Luchangco, V. and Moi , M. B inging p ac ical
lock- ee synch oniza ion o 64-bi applica ions. In P oceedings o he wen y- hi d
annual ACM symposium on P inciples o dis ibu ed compu ing. ACM, 2004.
G eenwald, M. B. Non-blocking synch oniza ion and sys em design. 1999.
Ha is, T. L.,F ase , K. and P a , I. A. A p ac ical mul i-wo d compa e-
and-swap ope a ion. In Lec u e No es in Compu e Science, 265–279. Sp inge
Be lin Heidelbe g, 2002.
He lihy, M.,Elio , J. and Moss, B. T ansac ional memo y: A chi ec u al sup-
po o lock- ee da a s uc u es. In P oceedings o he 20 h Annual In e na ional
Symposium on Compu e A chi ec u e. IEEE Compu . Soc. P ess, ????
He lihy, M.,Luchangco, V.,Moi , M. and Sche e , W. N. So wa e ans-
ac ional memo y o dynamic-sized da a s uc u es. In P oceedings o he wen y-
second annual symposium on P inciples o dis ibu ed compu ing. ACM, 2003.
He lihy, M. and Sha i , N. The A o Mul ip ocesso P og amming. Mo gan
Kau mann Publishe s Inc., San F ancisco, CA, USA, 2008. ISBN 0123705916.
Luchangco, V.,Moi , M. and Sha i , N. Nonblocking k-compa e-single-swap.
Theo y o Compu ing Sys ems, Vol. 44(1), 39–66, 2008.
Moi , M. and Sha i , N. Concu en da a s uc u es. In Handbook o Da a
S uc u es and Applica ions, 47–1–47–30. Chapman and Hall/CRC, 2004.
Sha i , N. and Toui ou, D. So wa e ansac ional memo y. Dis ibu ed Com-
pu ing, Vol. 10(2), 99–116, 1997.
81