带辅助功能的读写锁
4.33/5 (3投票s)
本文描述了一种在为 Windows XP/Vista 开发读写自旋锁时的启发式方法。
引言
构建高效的读写同步对象是开发多线程应用程序的重要课题。随着多处理器/多核计算平台的开发和普及，其重要性日益增加。
这个问题的一个重要场景是，一两个写入者与多个读取者竞争。这种情况比通用的读写问题要简单。但是，如果发生高锁争用，即使使用新的、性能优越的 Windows Vista SRWLOCK，性能也可能无法接受，尤其是当写入者的性能很重要时 [1]。我们将寻找一种解决方案，在多个读取者的最大性能（如 SRWLOCK）与写入者的可接受性能（如 RWLockFavorWriters [2]）之间取得折衷。
开发这样一种高效且完整的锁定算法是困难的。取而代之的是，我们可以尝试一种启发式组合，结合两种算法——一种是快速的锁定算法，用于获取独占/共享锁；另一种是辅助算法，用于提高整体性能。至于锁定算法，我们将使用一个相当直接的读写自旋锁。一个状态变量 m_rw_status 用于控制一个写入者和多个读取者的状态。该变量的 HIWORD 是写入者活动标志；LOWORD 是活动读取者计数。HIWORD 和 LOWORD 都以原子方式更改。关键部分 m_cswriters 仅由多个写入者使用，当写入者数量很少（一两个）时效果很好。以下伪代码说明了读写自旋锁
class CACHE_ALIGN SpinRWLock
{
public:
void acquireLockShared()
{
LONG i, j;
j = acquire_read(m_rw_status );
do {
i = j & 0xFFFF;
j = acquire_interlocked_compare_exchange(&m_rw_status, i + 1, i);
pause
} while (i != j);
}
void acquireLockExclusive()
{
::EnterCriticalSection(&m_cswriters);
while(acquire_interlocked_compare_exchange(&m_rw_status,
0x1+0xFFFF, 0x0) != 0x0)
{
pause
}
}
void releaseLockShared()
{
interlocked_decrement_release( &m_rw_status );
}
void releaseLockExclusive()
{
interlocked_Xor_release(&m_rw_status, 0x1+0xFFFF);
::LeaveCriticalSection(&m_cswriters);
}
SpinRWLock()
{
::InitializeCriticalSection(&m_cswriters);
m_writers_readers_flag = 0;
}
~SpinRWLock()
{
::DeleteCriticalSection(&m_cswriters);
}
private:
CACHE_PADDING
volatile LONG m_rw_status;
CACHE_PADDING
CACHE_ALIGN
CRITICAL_SECTION m_cswriters;
};
SpinRWLock 可以在多核 PC 上运行，但在单核 PC 上不行。事实上，写入者可能会在读取者持有高度争用的共享锁时完全死锁。为了提高写入者性能，我们引入了一个辅助启发式代码，通知读取者有写入者正在等待锁。一个简单的解决方案是通过设置一个额外的辅助变量 m_helper_flag 来通知读取者。如果写入者在给定次数 MAX_WRITER_SPIN 的尝试中未能获取独占锁，则将辅助标志设置为 HELPER_SIGNAL_SLOWDOWN。此标志用于阻止读取者在下次轮到它们时获取共享锁。当活动读取者释放锁时，写入者将等待由读取者在释放锁时设置的事件 m_helper_wait_event。以下伪代码说明了通过写入者通知读取者
void acquireLockExclusive()
{
…
while(acquire_interlocked_compare_exchange(&m_rw_status, 0x1+ 0xFFFF, 0x0)!= 0x0)
{
if (++spin_count == MAX_WRITER_SPIN)
{
// helper code
…
write_release(m_helper_flag,HELPER_SIGNAL_SLOWDOWN);
while(acquire_interlocked_compare_exchange(&m_rw_status,
0x1+0xFFFF,0x0)!=0x0)
{
wait_conditionally(m_rw_status,0x0,m_helper_wait_event);
}
…
write_release(m_helper_flag, HELPER_UNDEFINED_STATE);
…
return;
}
else
{
pause
}
}
…
}
控制读写锁状态变量的操作是原子的，但辅助操作（如检查锁状态变量、读写辅助标志、设置事件）不是原子的。有一些标准技术可以让程序序列以原子方式完成。例如，可以使用关键段作为“原子化器”[3]。在我们的例子中，这样做可能会创建一个类似复合读写锁 [2,3] 的新对象。相反，我们将尝试以下非原子等待函数，并附加对锁状态变量的检查
void wait_conditionally(volatile LONG& cond_variable, int cond_min, HANDLE wait_event)
{
while(acquire_read(cond_variable) > cond_min)
{
::WaitForSingleObject(wait_event, INFINITE);
}
}
以非原子方式控制 cond_variable 和 wait_event 会带来性能损失。如果读取者错误地将 m_rw_status > 0 和 m_helper_wait_event 设置为已触发状态（见图 4），写入者至少会自旋一次，浪费处理器时间。这种情况是可能的，如果一个读取者在 releaseLockShared() 函数中设置了 m_helper_wait_event，而其他读取者线程则在 try_interlocked_increment_reader() 函数中递增 m_rw_status。函数 try_interlocked_increment_reader() 在图 4 中与 SpinRWLock::acquireLockShared() 类似（唯一的区别是前者在读取者未能获取共享锁 MAX_READER_SPIN 次尝试后返回 false）。如果两个读取者错误地触发了 m_helper_wait_event 一次，写入者开销可能约为 2000-3000 个处理器周期。写入者（在最终获取锁之前）的最大开销约为 (active_readers_count-1)*2000-3000 个处理器周期。读取者在 acquireLockShared() 函数中自旋并检查错误触发的 m_writer_release_event 的开销可能会更高。读取者将浪费处理器时间，直到写入者重置 m_writer_release_event。但是，启发式假设是，这种有害行为不会经常发生。另一个启发式假设是，整体性能损失不会超过辅助代码可能带来的性能优势。本文附带了此读写锁 SHRW 的完整代码。
void acquireLockShared()
{
if(HELPER_UNDEFINED_STATE != acquire_read(m_helper_flag))
{
wait_conditionally(m_helper_flag, HELPER_UNDEFINED_STATE,
m_helper_slowdown_event);
}
else
{
}
while( false == try_interlocked_increment_reader() )
{
wait_conditionally(m_rw_status, 0xFFFF, m_writer_release_event);
}
}
void releaseLockShared()
{
if(interlocked_decrement_release(&m_rw_status) == 0 )
{
if (acquire_read(m_helper_flag) == HELPER_SIGNAL_SLOWDOWN)
{
::SetEvent(m_reader_release_event);
}
else
{
}
}
else
{
}
}
为了改进 SHRW 对象，我们可以使用 m_rw_status HIWORD 的附加位作为辅助标志（而不是使用单独的变量 m_helper_flag）。这样改进的好处是，状态变量的所有位，包括辅助位，都可以原子地设置。如果我们将同一个 HIWORD 位同时用于辅助标志和活动写入者标志，解决方案将更加简单。
//
// Copyright (c) 2009 Valery Grebnev.
//
class CACHE_ALIGN SHRW2
{
public:
void acquireLockShared()
{
while(false == try_interlocked_increment_reader())
{
wait_conditionally(m_rw_status, 0xFFFF, m_writer_release_event);
}
}
void acquireLockExclusive()
{
::EnterCriticalSection(&m_cswriters);
int spin_count = 0;
while(acquire_interlocked_compare_exchange(&m_rw_status,0x1+0xFFFF,0x0) != 0x0)
{
if (++spin_count == MAX_WRITER_SPIN)
{
::ResetEvent(m_writer_release_event);
interlocked_Or_release (&m_rw_status, 0x1+0xFFFF);
wait_conditionally(m_rw_status, 0x1+0xFFFF, m_reader_release_event);
return;
}
else
{
pause
}
}
::ResetEvent(m_writer_release_event);
}
void releaseLockShared()
{
if(interlocked_decrement_release(&m_rw_status) == 0x1+0xFFFF )
{
::SetEvent(m_reader_release_event);
}
else
{
}
}
void releaseLockExclusive()
{
interlocked_Xor_release(&m_rw_status, 0x1+0xFFFF);
::SetEvent(m_writer_release_event);
::LeaveCriticalSection(&m_cswriters);
}
SHRW2()
{
m_rw_status = 0;
::InitializeCriticalSection(&m_cswriters);
m_writer_release_event = ::CreateEvent(NULL, TRUE, FALSE, NULL);
m_reader_release_event = ::CreateEvent(NULL, FALSE, FALSE, NULL);
}
~SHRW2()
{
::DeleteCriticalSection(&m_cswriters);
::CloseHandle(m_writer_release_event);
::CloseHandle(m_reader_release_event);
}
private:
bool try_interlocked_increment_reader()
{
LONG i, j;
j = acquire_read(m_rw_status);
int spin_count = 0;
do {
if (spin_count == MAX_READER_SPIN)
{
return false;
}
else
{
i = j & 0xFFFF;
j = acquire_interlocked_compare_exchange(&m_rw_status, i + 1, i);
spin_count ++;
}
} while (i != j);
return true;
}
inline void wait_conditionally(volatile LONG& cond_variable,
int cond_min, HANDLE wait_event)
{
while( acquire_read(cond_variable) > cond_min)
{
::WaitForSingleObject(wait_event, INFINITE);
}
}
// should be set to 1 on a Uniprocessor PC
enum { MAX_WRITER_SPIN = 1000, MAX_READER_SPIN = 1000 };
CACHE_PADDING(1)
volatile LONG m_rw_status;
CACHE_PADDING(2) CACHE_ALIGN
CRITICAL_SECTION m_cswriters;
HANDLE m_writer_release_event;
HANDLE m_reader_release_event;
};
SHRW 和 SHRW2 对象的测试结果总结在图 6 和图 7 中。测试场景和程序代码与文章 [1] 中使用的几乎相同。为了比较锁的性能，还测试了新的 Windows Vista API 用户模式锁 SRWLOCK 和 “RWLockFavorWriters” 对象 [2]。
Number of readers 1 2 4 8 4 (no writers)
RWFavorWriter
reader 0.93 1.12 1.64 2.60 1.12
writer 6.50 17.00 25.78 49.36 -
reader RSTD % 2.87 12.23 19.52 31.92 20.74
writer RSTD % 2.71 22.4 11.4 13.34 -
SHRW
reader 0.59 0.87 1.46 2.65 1.17
writer 7.36 11.33 23.32 48.06 -
reader RSTD % 5.41 13.06 24.44 25.11 7.19
writer RSTD % 5.02 6.8 7.68 7.91 -
SHRW2
reader 0.59 0.87 1.47 2.64 1.15
writer 7.38 11.46 23.48 48.06 -
reader RSTD % 6.49 12.02 24.7 24.61 5.99
writer RSTD % 6.48 6.51 8.78 9.93 -
图 6 显示，在单核 PC 上运行的锁的性能差别不大。SHRW 和 SHRW2 锁的性能相同，并且在读取者和写入者方面都略优于 RWFaivorWriter。与 SHRW 和 SHRW2 锁相比，RWFaivorWriter 对象的内核 CPU 使用率稍高（约 10-20%），这可能表明 RWFaivorWriter 更频繁地进入内核模式。
图 7 总结了在多核 PC 上的测试结果。SRWLOCK 和 RWFaivorWriter 对象的一些结果被过滤掉了。当 SRWLOCK 读取者与写入者竞争时，前者在大约 10% 的测试中发生死锁；当与两个 SRWLOCK 读取者竞争时，写入者在大约 7% 的测试中发生死锁。如果不过滤异常结果，将无法比较锁的性能。测试报告“Results\vista_tests.html”说明了 SRWLOCK 在单个线程和测试中的性能差异，包括为分析而过滤掉的异常结果；请参阅文章附件。图 7 显示了 SRWLOCK 的不稳定行为。变异系数约 120-294% 表明单个读写器线程的性能差异很大。一些 RWFaivorWriter 的测试结果被过滤掉了，因为当一个写入者与四个读取者竞争时，在 acquireLockShared() 函数中发生了死锁。
Number of readers 1 2 4 8 4 (no writers)
SRWLOCK
reader 1.36 0.24 0.57 1.17 0.59
writer 4.9 166.05 278.17 551.63 -
reader RSTD % 293.85 6.78 11.83 17.41 2.32
writer RSTD % 121.92 131.86 34.38 32.62 -
RWFavorWriter
reader 4.37 3.92 5.28 7.02 0.90
writer 6.26 13.72 20.12 54.00 -
reader RSTD % 27.25 31.96 4.41 4.74 7.78
writer RSTD % 51.33 17.37 3.64 13.29 -
SHRW
reader 0.67 1.24 1.84 2.54 0.84
writer 2.65 3.01 4.35 8.60 -
reader RSTD % 3.35 6.9 11.7 7.89 6.99
writer RSTD % 2.86 1.53 8.94 6.2 -
SHRW2
reader 0.66 1.19 1.42 2.21 0.81
writer 2.65 3.04 5.20 10.88 -
reader RSTD % 2.33 7.09 11.96 10.76 -
writer RSTD % 2.15 0.97 6.37 9.52 -
与 RWFaworWriter 对象相比，SHRW/SHRW2 的写入者和读取者性能更好。结果的变异很小，约 1-12%。锁每秒产生的线程上下文切换次数相对较少（约 200-2000 次），内核 CPU 负载约 5-10%。在多核 PC 上，SHRW/SHRW2 锁的读取者性能可能进一步提高约 20-45%。为此，写入者可以在 acquireLockExclusive() 函数的 CAS 操作循环中检查状态变量 m_rw_status（缺点是写入者性能下降约 100-200%，并且写入者和读取者的变异系数增加到 20-50%）。SHRW/SHRW2 对象的一个缺点是它们使用原子内存原语，而这些原语在所有处理器架构上可能都不可用。这限制了代码的可移植性。应审查具有获取/释放语义的读写内存操作。当 SHRW/SHRW2 移植到不同的硬件平台并使用非微软编译器编译时，应考虑它们的原子性和排序。其次，由于许多线程在同一内存位置 m_rw_status 上自旋，缓存无效和内存流量会过载，应予以考虑。为了最大限度地减少伪共享，应调整硬件依赖的对齐 CACHE_ALIGN 和缓存填充 CACHE_PADDING 值。还可能需要在单核和多核 PC 上调整 MAX_WRITER_SPIN 和 MAX_READER_SPIN 常量。
结论
SHRW/SHRW2锁是高性能的同步对象，适用于使用 Microsoft 编译器 VC++8.0/9.0 为运行在 32x/64x 单核/多核 x86 架构平台上的 Microsoft Windows XP/Vista 开发的应用程序。- 在不同的硬件/软件平台和非微软编译器上使用
SHRW/SHRW2对象需要根据特定的缓存/内存模型、原子内存原语、硬件和编译器特定操作顺序进行代码移植。 SHRW/SHRW2对象专为高度争用且写入者数量少（一两个）以及大量读取者的锁而设计。对于写入者，随着多写入者数量的增加，可能会出现性能回归、锁队列和饥饿现象。
参考文献
- Valery Grebnev。“Testing reader/writer locks”，testing_rwlocks.aspx
- Robert Saccone 和 Alexander Taskov。“CONCURRENCY: Synchronization Primitives New To Windows Vista”，http://msdn.microsoft.com/en-us/magazine/cc163405.aspx
- Ruediger R. Asche。“Compound Win32 Synchronization Objects”，http://msdn.microsoft.com/en-us/library/ms810427.aspx