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