非阻塞算法思想.doc

数据结构算法:非阻塞算法思想阻塞算法介绍目前，很多关于并发算法的研究都聚集在非阻塞算法（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 THENBREAK;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) mit();throw new Exception(id + id + invalid.);/ 更新加1sql = 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.);mit();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的方式会比使用事务的方式快1020.如果加大线程跑并发，CAS的性能逐渐下降，也符合CAS算法在激烈竞争下性能不高的场景。但是实际环境中，很少会在同一点上存在激烈竞争，所以采用CAS的方式会比使用事务的方