Chinaunix首页 | 论坛 | 博客
  • 博客访问: 103113961
  • 博文数量: 19283
  • 博客积分: 9968
  • 博客等级: 上将
  • 技术积分: 196062
  • 用 户 组: 普通用户
  • 注册时间: 2007-02-07 14:28
文章分类

全部博文(19283)

文章存档

2011年(1)

2009年(125)

2008年(19094)

2007年(63)

分类: Oracle

2008-03-31 13:07:14

来源:赛迪网    作者:小桥

阻塞算法介绍

目前,很多关于并发算法的研究都聚集在非阻塞算法(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、非阻塞算法的思想不单可用于系统底层框架,而且适用于任何地方。

阅读(272) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~