vlocks for Bare-Metal Mutual Exclusion
Voting Locks, or “vlocks” provide a simple low-level mutual exclusion mechanism, with reasonable but minimal requirements on the memory system.
Voting Locks あるいは "vlock" は、シンプルで低レベルのmutal exclusion mechanismを実現するものである。これは、メモリシステムへの最小の要求だけが必要とされる、リーズナブルです。
These are intended to be used to coordinate critical activity among CPUs which are otherwise non-coherent, in situations where the hardware provides no other mechanism to support this and ordinary spinlocks cannot be used.
これは、一貫性の無いCPU間でのクリティカルなアクティビティの調整に利用する事を目的としています。ハードウェアがこれをサポートする他のメカニズムを提供せず、通常のスピンロックが利用できない状況で利用できます。
vlocks make use of the atomicity provided by the memory system for writes to a single memory location. To arbitrate, every CPU “votes for itself”, by storing a unique number to a common memory location. The final value seen in that memory location when all the votes have been cast identifies the winner.
vlockは、メモリシステムによって提供される原子性(atomicity)を利用して、single memory locationへ書き込みします。調停するために、全てのCPUでは"自分に投票し"、共有メモリ市にユニークな数値を書き込みます。すべての投票が行われたとき、memory locationに表示される最終の値によって、勝者が識別されます。
In order to make sure that the election produces an unambiguous result in finite time, a CPU will only enter the election in the first place if no winner has been chosen and the election does not appear to have started yet.
投票が有限の時間で、確実に結果を生み出すために、勝者が決定されておらず、投票がまだ始まっていない場合のみ、CPUは投票を行います。
Algorithm
The easiest way to explain the vlocks algorithm is with some pseudo-code:
vlock algorithmを例示する簡単な方法は、疑似コードを利用する事である。
int currently_voting[NR_CPUS] = { 0, };
int last_vote = -1; /* no votes yet */
bool vlock_trylock(int this_cpu)
{
/* signal our desire to vote */
/* 投票をしたい気持ちをsignalする */
currently_voting[this_cpu] = 1;
if (last_vote != -1) {
/* someone already volunteered himself */
/* 誰かすでに志願している */
currently_voting[this_cpu] = 0;
return false; /* not ourself */
/* それは自分ではない */
}
/* let's suggest ourself */
/* 自分自身を提案する */
last_vote = this_cpu;
currently_voting[this_cpu] = 0;
/* then wait until everyone else is done voting */
/* それ以外の全員が投票を完了するまで待機 */
for_each_cpu(i) {
while (currently_voting[i] != 0)
/* wait */;
}
/* result */
/* 結果 */
if (last_vote == this_cpu)
return true; /* we won */
/* 勝利 */
return false;
}
bool vlock_unlock(void)
{
last_vote = -1;
}
The currently_voting[] array provides a way for the CPUs to determine whether an election is in progress, and plays a role analogous to the “entering” array in Lamport’s bakery algorithm [1].
current_voting []配列は、CPUが投票が進行中であるかどうかを判断する方法を提供し、Lamportのbakery algorithm の「entering」配列と同様の役割を果たします[1]。
However, once the election has started, the underlying memory system atomicity is used to pick the winner. This avoids the need for a static priority rule to act as a tie-breaker, or any counters which could overflow.
しｋし、一度投票が開始すると、根底にあるメモリシステムの原始性を用いて、勝者の選出に使われます。これにより、tie-breakerとして機能する静的優先順位のルール、あるいは、オーバーフローする可能性のあるカウンターが必要なくなります。
As long as the last_vote variable is globally visible to all CPUs, it will contain only one value that won’t change once every CPU has cleared its currently_voting flag.
last_vote変数がすべてのCPUにglobalに可視である限り、すべてのCPUがcurrent_voting flagをクリアするまで変更されない1つの値のみが含まれます。
Features and limitations
・vlocks are not intended to be fair. In the contended case, it is the last CPU which attempts to get the lock which will be most likely to win.
vlocks are therefore best suited to situations where it is necessary to pick a unique winner, but it does not matter which CPU actually wins.
- vlockは平等であるように糸されていません。競合するケースでは、"最後の"CPUが、ロックを取得しようとする中で最も勝つ可能性が高くなります。しかたがって、vlockは唯一の勝者を決定する必要がある状況には最も適していますが、実際にどのCPUが勝者となるのかは気にしていません。
・Like other similar mechanisms, vlocks will not scale well to a large number of CPUs.
vlocks can be cascaded in a voting hierarchy to permit better scaling if necessary, as in the following hypothetical example for 4096 CPUs:
vlocksは、必要に応じてより良いscalingするために、投票階層をカスケード接続できます。例えば、4096 CPUを潜在的に有するようなケース。
もともと、Linux Kernelのソースコードの一部なので、GPLv2扱いになる（はずの認識）。
https://www.kernel.org/doc/html/latest/index.html
Licensing documentation
The following describes the license of the Linux kernel source code (GPLv2), how to properly mark the license of individual files in the source tree, as well as links to the full license text.
https://www.kernel.org/doc/html/latest/process/license-rules.html#kernel-licensing