100223

箱作り運動。この箱を収納する本体のイメージもだんだんできてきて、それに 合わせるために、3の倍数個じゃないサイズの箱を追加して作成。今日は追加の 2個の部材を所定サイズにまで整えたとこまで。これはSPF

FF13続き。1日1シャオロングイ運動。今日はドロップせず。あと一つ! インペ リアルガードを6つ作るのでちょっと必要数が多い。今日は、あともう一息で1 ブレイクで削りきれそうなところまでいった。面倒がらずに、できる限りベス トにオプティマチェンジが大切なんだよね。
無待機同期続き。ここで"universal object"というのが出てくる普遍物体と訳 してみた。これは具体的にはCompare-And-Swapだ(たぶんll/scも等価なんだと 思う)。これがあれば処理数によらず無待機同期な実装ができる。が、処理数が 限定されているなら限られた同意数の基本要素でも普遍になる。2コア限定なら Test-And-Setでも無待機同期を実装できるということか。しかしあまりにも実 装と乖離し過ぎていてなにがなんだか意味不だ。

Wait-Free Synchronization

MAURICE HERLIHY

Digital Equipment Corporation

ACM Transactions on Programming Langages and Systems, vol.11, no.1,
January 1991,p124-149.

図1 不可能さと一般的さの階層
----------------------------------------------------------------------
同意数	物体
----------------------------------------------------------------------
1	レジスタの読み書き
----------------------------------------------------------------------
2	Test-And-Set, Fetch-And-Add, 待ち行列, スタック
----------------------------------------------------------------------
.	.
----------------------------------------------------------------------
2n-2	n-レジスタ割当て
----------------------------------------------------------------------
.	.
----------------------------------------------------------------------
∞	メモリ-メモリ間の移動、交換、拡張待ち行列、Compare-And-Swap,
	Fetch-And-Cons, sticky byte
----------------------------------------------------------------------

これらの不可能さは、どうしても無待機同期は不可能あるいは不適切であると
いうことを示すものではない。この論文の二番目の部分では、どのような物体
の無待機な実装をするのに使える「普遍的な物体」があることを紹介する。一
般さに単純なテストを与え、n処理のシステムにおいて、物体の同意数がnより
大きい、あるいはnと等しいとしても、それが普遍的であることを示す。図1に
おいて、n層のそれぞれの物体は、n処理のシステムにおいては普遍的である。
機械の構成、あるいはプログラミング言語は、それが基本要素として普遍的な
物体を提供する場合においては、任意の無待機同期を十分に支援することがで
きる。