|
阻塞算法介绍
目前，很多关于并发算法的研究都聚集在非阻塞算法(nonblocking algorithms)上，这种算法使用低层原子化的机器指令取代锁，比如compare-and-swap，从而保证数据在兵法访问下的一致性。非阻塞算法广泛应用于操作系统和jvm的线程和进程调度、垃圾回收以及实现所和其他的并发数据结构。
与基于锁的方案相比，非阻塞算法的设计和实现都要复杂一些，但是它们在可伸缩性和活跃度上占有很大的优势。因为非阻塞算法可以让多个线程在竞争相同资源时不会发生阻塞，所以它能在更精化的层面上调整粒度，并能大大减少开销。进一步而言，它们对死锁和其他活跃度问题具有免疫性。基于锁的算法中，如果一个线程在持有锁的时候休眠，或者停滞不前，那么其它线程就都不能前进了，而非阻塞算法不会受到单个线程失败的影响。在java 5.0中，使用atomic variable classes，比如atomicinteger和atomicreference，能够高效构建非阻赛算法。
非阻塞算法的关键思想就是cas，cas是compare and set的缩写，也常被称为lock-free或者wait-free，通过把compare和set两个操作原子化，使得不需要使用锁，但是能够解决并发中的资源争用问题。由于cas常常是一个回退算法+外循环，所以又被称为spin-lock。由于cas没有使用锁，线程持续执行，又称为非阻塞算法(non-blocking)。术语不统一，有细微差别，但都差不多表示同一个东西，我都列在这里，方便大家理解。
非阻塞算法的实现通常包括如下部分：外循环、回退、cas操作。伪码如下：
while (true) // 外循环
{
准备数据
if cas_op() == success then
break;
end if
|
}
非阻塞算法思想在关系数据库开发中的应用
有人说，非阻塞算法这种技术底层框架提供，不需要了解，其实不然，cas思想可以应用任何地方，包括数据结构、服务接口、数据库应用等等。我这篇文章要讲的内容就是在关系数据库应用中使用cas思想。
关系数据库数据库提供了"update t set fstate = xx where fstate = xx"，执行这样的sql，会返回一个更新行数，在jdbc或者odbc或者ado .net中都可以获得更新行数。上面的sql，如果更新行数>0，则是更新成功，否则是没有进行任何更新，这是很典型的cas。可以说，关系数据库 原生支持cas。
关系数据库中采用事务来确保并发时的原子性，事务实际上就是一种“锁”。关系数据库中通常有排他锁和共享锁的概念，这有点类似于java中readwritelock。需要更新数据时，我们通常使用到关系数据库的排他锁，在oracle中需要使用select … for update，在microsoft sql server中，使用lock hints。
我们举两个例子描述cas在关系数据开发中的应用。
例一 读取并更新
传统使用数据库事务的实现
public long transactiongetandincrement(connection conn, long id) throws exception {
// 为了简化，不适用try...finally的方式释放statement和resultset等资源
conn.setautocommit(false);
long expect = null;
// 读取当前值
string sql = "select fvalue from t_test_cas t where fid = ? for update";
preparedstatement stmt = conn.preparestatement(sql);
stmt.setlong(1, id);
resultset rs = stmt.executequery();
if (rs.next()) expect = rs.getlong(1);
rs.close();
stmt.close();
if (expect == null) {
conn.commit();
throw new exception("id '" + id + "' invalid.");
}
// 更新加1
sql = "update t_test_cas set fvalue = ? where fid = ?";
stmt = conn.preparestatement(sql);
stmt.setlong(1, expect.longvalue() + 1);
stmt.setlong(2, id);
int updatecount = stmt.executeupdate();
stmt.close();
if (updatecount == 0) throw new exception("id '" + id + "' invalid.");
conn.commit();
return expect.longvalue();
}
cas方式的实现
// 为了简化，不适用try...finally的方式释放statement和resultset等资源
public long casgetandincrement(connection conn, long id) throws exception {
for (;;) { // 外循环
long expect = null;
string sql = "select fvalue from t_test_cas t where fid = ?";
preparedstatement stmt = conn.preparestatement(sql);
stmt.setlong(1, id);
resultset rs = stmt.executequery();
if (rs.next()) {
expect = rs.getlong(1);
}
rs.close();
stmt.close();
if (expect == null) throw new exception("id '" + id + "' invalid.");
// 比较更新
sql = "update t_test_cas set fvalue = ? where fid = ? and fvalue = ?";
stmt = conn.preparestatement(sql);
stmt.setlong(1, expect.longvalue() + 1);
stmt.setlong(2, id);
stmt.setlong(3, expect.longvalue());
int updatecount = stmt.executeupdate();
stmt.close();
// 如果updatecount > 0，更新成功，返回退出循环，否则回退重来
if (updatecount > 0) return expect.longvalue();
}
}
|
例二 使用cas读取并且删除数据表中最小的值的一行
public long compareanddelete
(connection conn) throws exception {
for (;;) { //外循环
long minvalue = null;
// 读取最小值
string sql = "select min(fvalue) from t";
preparedstatement stmt = conn.preparestatement(sql);
resultset rs = stmt.executequery();
if (rs.next()) minvalue = rs.getlong(1);
rs.close();
stmt.close();
if (minvalue == null) return null;
// 比较删除
sql = "delete from t where fvalue = ?";
stmt = conn.preparestatement(sql);
stmt.setlong(1, minvalue.longvalue());
int updatecount = stmt.executeupdate();
stmt.close();
// 如果updatecount > 0，
删除成功，返回退出循环，否则回退重来
if (updatecount > 0) return minvalue;
}
}
|
在例二的场景中，使用事务还不好实现，因为oracle中使用了min函数就不能使用 for update。
性能比较
在oracle 10g上作测试，使用cas的方式测试例一，在10个线程并发测试跑1000次，cas的方式会比使用事务的方式快10~20。如果加大线程跑并发，cas的性能逐渐下降，也符合cas算法在激烈竞争下性能不高的场景。但是实际环境中，很少会在同一点上存在激烈竞争，所以采用cas的方式会比使用事务的方式效率更高。
总结
1、在关系数据库开发中使用非阻塞算法，由于非阻塞算法自身保证原子性，所以不能在嵌套在事务中使用。
2、使用非阻塞算法不使用事务，不适用悲观的独占锁，不存在激烈竞争的情况下，性能比采用事务的方式性能更好。
3、非阻塞关系数据库算法，适用于分布式工作流系统、后台调度程序等场景，能够在并发和集群环境下工作良好。
4、非阻塞算法的思想不单可用于系统底层框架，而且适用于任何地方。
|
