load-linked/store-exclusive 范式背后的想法是,如果存储在加载后很快跟随,没有干预内存操作,并且如果没有其他任何东西触及该位置,则存储可能会成功,但如果有什么else 已经触及了商店肯定会失败的位置。不能保证商店有时不会无缘无故倒闭;但是,如果加载和存储之间的时间保持在最短,并且它们之间没有内存访问,则循环如下:
do
{
new_value = __LDREXW(dest) + 1;
} while (__STREXW(new_value, dest));
通常可以依靠几次尝试就成功。如果根据旧值计算新值需要一些重要的计算,则应将循环重写为:
do
{
old_value = *dest;
new_value = complicated_function(old_value);
} while (CompareAndStore(dest, new_value, old_value) != 0);
... Assuming CompareAndStore is something like:
uint32_t CompareAndStore(uint32_t *dest, uint32_t new_value, uint_32 old_value)
{
do
{
if (__LDREXW(dest) != old_value) return 1; // Failure
} while(__STREXW(new_value, dest);
return 0;
}
如果在计算新值时发生某些变化 *dest,则此代码必须重新运行其主循环,但如果 __STREXW 由于某些其他原因失败,则只需重新运行小循环[希望不太可能,鉴于__LDREXW 和 __STREXW 之间只有大约两条指令]
附录
“根据旧值计算新值”可能很复杂的情况示例是“值”实际上是对复杂数据结构的引用。代码可以获取旧的引用,从旧的数据结构派生新的数据结构,然后更新引用。与“裸机”编程相比,这种模式在垃圾收集框架中出现的频率要高得多,但即使在编程裸机时也可以通过多种方式出现。普通的 malloc/calloc 分配器通常不是线程安全/中断安全的,但用于固定大小结构的分配器通常是。如果一个人有一个由 2 次方的数据结构组成的“池”(比如 255 个),则可以使用以下内容:
#define FOO_POOL_SIZE_SHIFT 8
#define FOO_POOL_SIZE (1 << FOO_POOL_SIZE_SHIFT)
#define FOO_POOL_SIZE_MASK (FOO_POOL_SIZE-1)
void do_update(void)
{
// The foo_pool_alloc() method should return a slot number in the lower bits and
// some sort of counter value in the upper bits so that once some particular
// uint32_t value is returned, that same value will not be returned again unless
// there are at least (UINT_MAX)/(FOO_POOL_SIZE) intervening allocations (to avoid
// the possibility that while one task is performing its update, a second task
// changes the thing to a new one and releases the old one, and a third task gets
// given the newly-freed item and changes the thing to that, such that from the
// point of view of the first task, the thing never changed.)
uint32_t new_thing = foo_pool_alloc();
uint32_t old_thing;
do
{
// Capture old reference
old_thing = foo_current_thing;
// Compute new thing based on old one
update_thing(&foo_pool[new_thing & FOO_POOL_SIZE_MASK],
&foo_pool[old_thing & FOO_POOL_SIZE_MASK);
} while(CompareAndSwap(&foo_current_thing, new_thing, old_thing) != 0);
foo_pool_free(old_thing);
}
如果不会经常有多个线程/中断/任何试图同时更新同一事物的东西,这种方法应该允许安全地执行更新。如果可能尝试更新同一项目的事物之间存在优先级关系,则最高优先级的事物在第一次尝试时保证成功,次高优先级的事物将在任何未被抢占的尝试中成功最高优先级的任务,等等。如果一个正在使用锁定,则想要执行更新的最高优先级任务将不得不等待较低优先级的更新完成;使用 CompareAndSwap 范式,最高优先级的任务将不受低级任务的影响(但会导致低级任务不得不做浪费的工作)。