POSIX&Order&Write&Test&Rep ort!
Purpose(
!"#$%#&'%($#)&*+,-.$("#$%#/0,%#1#-(.$+-2$2#.,3-$'4$("#$56789$6%2#%$:%,(#$(#.($,-$
("#$7:;<$&%'=#>(?$8($("#-$."'@.$("#$%#.0*($'4$("#$(#.(.$,-$2,44#%#-($.A.(#1.?$
Requirements(
!"#$@%,(#$'%2#%$(#.($."'0*2$B#%,4A$("+($("#$@%,(#$'%2#%$,.$.(%,>(*A$>'-.,.(#-(?$!"#$
7:;<$4#+(0%#$%#/0,%#.$("+($("#$'%2#%$'4$@%,(#$,.$.(%,>(*A$>'-.,.(#-(?$The SWMR
updates to the data structures in the file are essentially implementing a "lock-
free" or "wait-free" algorithm in updating the data structure on
disk. See: https://en.wikipedia.org/wiki/Non-blocking_synchronization, for
example. In those algorithms, the order of updates to the data structure is critical
and if it doesn't occur correctly, the reader can get inconsistent results.$
$
C7(%,>($>'-.,.(#->A$,-$>'1&0(#%$.>,#->#$,.$("#$1'.($.(%,-3#-($>'-.,.(#->A$1'2#*?$$8($
.+A.$("+($+$%#+2$'&#%+(,'-$"+.$('$%#(0%-$ ( "#$%#.0*($'4$("#$*+(#.($@%,(#$'&#%+(,'-$
@",>"$'>>0%%#2$'-$("+($2+(+$,(#1?CDD$
E"((&FGG#-?@,H,,+?'%3G@,H,GI,-#+%,J+K,*,(ALM#4,-,(,'-N'4N*,-#+%,J+K,*,(AO?$
$
!",.$,.$+*.'$+-$+*(#%-+(,B#$4'%1$'4$@"+($56789$@%,(#$%#/0,%#$("+($+4(#%$+$@%,(#$
'&#%+(,'-$"+.$%#(0%-#2$.0>>#..P$+**$%#+2.$,..0#2$+4(#%@+%2$."'0*2$3#($("#$.+1#$2+(+$
("#$@%,(#$"+.$@%,((#-?$
Design(of(Implementation(
!"#$(#.($-+1#2$+.$(@%,(#'%2#%P$.,10*+(#.$@"+($7:;<$2'#.$KA$@%,(,-3$>"+,-#2$
K*'>H.$+-2$.##$,4$("#A$>+-$K#$%#+2$K+>H$>'%%#>(*A?$
!"#%#$,.$+$@%,(#%$&%'>#..$+-2$10*(,&*#$%#+2#%$&%'>#..#.?$
!"#$4,*#$,.$2,B,2#2$,-('$QRS$&+%(,(,'-.?$!"#-$("#$@%,(#%$@%,(#.$T$>"+,-#2$K*'>HP$#+>"$
'4$TRS$K,3P$,-$#+>"$&+%(,(,'-$+4(#%$("#$4,%.($&+%(,(,'-?$
U+>"$>"+,-#2$K*'>H$"+.$(",.$.(%0>(0%#F$
• SA(#$VDWF$'44.#($+22%#..$'4$,(.$>",*2$K*'>H?$!"#$*+.($>",*2$0.#.$V$+.$XYII?$
• SA(#$ZDTVQWF$.'1#$+%(,4,>,+*$2+(+?$
• !"#$>",*2$K*'>H$+22%#..$'4$S*'>H$T$,.$XYII$EVO?$
• !"#$>",*2$K*'>H$+22%#..$'4$S*'>H$Q$,.$("#$'44.#($+22%#..$'4$S*'>H$T?$
• !"#$>",*2$K*'>H$+22%#..$'4$S*'>H$-$,.$("#$'44.#($+22%#..$'4$S*'>H$-DT?$
[4(#%$+**$-$K*'>H.$+%#$@%,((#-P$("#$'44.#($+22%#..$'4$S*'>H$-$,.$@%,((#-$('$("#$'44.#($V$
'4$("#$4,%.($&+%(,(,'-$ES*'>H$TO?$!"#%#4'%#P$KA$("#$(,1#$("#$'44.#($+22%#..$'4$S*'>H$-$,.$
@%,((#-$('$(",.$&'.,(,'-P$+**$-$>"+,-D*,-H#2$K*'>H.$"+B#$K##-$@%,((#-?$
$