层次业务模型的同步锁设计

考虑以下情形：一个控制中心对一些资源进行操作，资源之间的关系为层级，如下图uml

 

基地—》车间—》工作台—》工作流

 

每一个对象都包含一些操作，比如基地：建造基地、升级基地、销毁基地、创建车间。。。

车间：建造车间、升级车间、销毁车间、创建工作台。。。

工作台。。。工作流。。。

 

1.不同的车间之间的操作可并行执行，同一车间下的不同工作台可并行操作，同一工作台下的不同操作需要同步执行，若车间内某个工作台正在执行某个操作，那么该车间将同步该操作后才可对该车间进行操作。

 

2.操作未必是针对单一元素，比如车间A的工作台1、2、3以及车间B的工作台4、5、6的升级操作需要同步，即串行升级，此时若车间A的工作台7需要操作则不受其影响，车间B的工作台8同样，但对车间A、车间B、甚至其基地O的操作则需要等待升级操作结束后

 

 

现在需要设计一个锁的模型来实现以上层次业务模型的同步/并行处理。

 

以上可分层次的业务模型中，可使用树来描述，树的叶子节点为操作，一个操作的描述为自根到叶子节点的路径，如果一个操作涉及多个叶子节点，则该操作描述为自根到该叶子节点s的子树。

 

定义执行：一次针对某个操作集合的执行

定义操作的边界：一次执行涉及的操作叶子节点的父亲集合

定义操作锁：一个次将所有边界节点加锁

 

规律：如果一个边界节点加锁，那么该边界节点的所有前继（父亲结合），和后继（孩子集合）均不能加锁

 

 

代码如下：

 

package flowlock;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import javax.xml.parsers.DocumentBuilderFactory;

import org.w3c.dom.Element;
import org.w3c.dom.NodeList;
import org.xml.sax.SAXException;

/**
 * 可分层业务模型锁， 业务描述格式为xml
 * 
 * @author dingchd
 * 
 */
public class TreeLock {
	private static final int TIME_WAIT_UNIT = 500;

	private TreeNode root = new TreeNode("root", "root");
	private Map<String, List<TreeNode>> cacheTreeNode = new HashMap<String, List<TreeNode>>();

	// 全局tree的锁
	private Lock globalLock = new ReentrantLock();

	/**
	 * 锁操作子集
	 * 
	 * @param tokenxml
	 *            操作子集的json描述
	 * @throws Exception
	 *             中断、解析失败
	 */
	public void lock(String tokenxml) throws Exception {
		tryLock(tokenxml, -1);
	}

	/**
	 * 锁操作子集，超时退出
	 * 
	 * @param tokenxml
	 * @param timeout
	 * @return 锁定成功返回true
	 * @throws Exception
	 *             中断 、解析失败
	 */
	public boolean tryLock(String tokenXml, int timeout) throws Exception {
		long curTime = System.currentTimeMillis();

		TreeNode node = convert(tokenXml);

		List<TreeNode> borderNodes = null;

		try {
			globalLock.lock();
			borderNodes = combinTree(node); // 合并操作空间
			cacheTreeNode.put(tokenXml, borderNodes);
		} finally {
			globalLock.unlock();
		}

		boolean success = false;
		List<TreeNode> waitNodes = null;
		for (;;) {
			try {
				globalLock.lock();

				waitNodes = getWaitNodes(borderNodes);

				// 如果当前所有预加锁的边界节点的所有前继和后继中不存在边界节点
				if (waitNodes.isEmpty()) {
					for (TreeNode borderNode : borderNodes) {
						borderNode.setLock(true);
					}
					success = true;
					break;
				}
			} finally {
				globalLock.unlock();
			}

			// 等待已存在的边界节点释放
			boolean needWait = false;
			for (TreeNode waitNode : waitNodes) {
				if (waitNode.isLocked()) {
					needWait = true;
					break;
				}
			}

			// 等待并进行超时检测
			if (needWait) {
				Thread.sleep(TIME_WAIT_UNIT);
				if (timeout != -1
						&& System.currentTimeMillis() - curTime > timeout) {
					break;
				}
			}
		}

		return success;
	}

	/**
	 * 从操作树获取边界节点
	 * 
	 * @param node
	 * @return
	 */
	private List<TreeNode> getBorders(TreeNode node) {
		List<TreeNode> borders = new ArrayList<TreeNode>();
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(node);

		while (!stack.isEmpty()) {
			TreeNode curNode = stack.pop();
			TreeNode[] children = curNode.getChildren();
			if (children.length == 0) {
				borders.add(curNode);
			} else {
				for (TreeNode child : children) {
					stack.push(child);
				}
			}

		}
		return borders;
	}

	/**
	 * 解锁
	 * 
	 * @param tokenxml
	 * @throws Exception
	 */
	public void unlock(String tokenxml) throws Exception {
		try {
			globalLock.lock();

			List<TreeNode> borderNodes = cacheTreeNode.remove(tokenxml);
			if (borderNodes == null) {
				throw new Exception("invalid tokenxml " + tokenxml);
			}

			for (TreeNode borderNode : borderNodes) {
				borderNode.setLock(false);
			}
		} finally {
			globalLock.unlock();
		}
	}

	/**
	 * 获取当前所有节点的前继节点中的边界节点
	 * 
	 * @param borderNodes
	 * @return
	 */
	private List<TreeNode> getWaitNodes(List<TreeNode> borderNodes) {
		List<TreeNode> waitNodes = new ArrayList<TreeNode>();

		// 从前继中查找
		for (TreeNode node : borderNodes) {
			TreeNode curNode = node;
			while (curNode != null) {
				if (curNode.isLocked()) {
					waitNodes.add(curNode);
				}
				curNode = curNode.getFather();
			}
		}

		// 从后继中查找
		Stack<TreeNode> stack = new Stack<TreeNode>();
		for (TreeNode node : borderNodes) {
			stack.push(node);
		}

		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			TreeNode[] children = node.getChildren();
			for (TreeNode child : children) {
				if (child.isLocked()) {
					waitNodes.add(child);
				} else {
					stack.push(child);
				}
			}
		}

		return waitNodes;
	}

	/**
	 * 合并操作树，返回当前合并node所反映的所有边界节点 该节点可能来自node的后继，也可能来自root的后继，合并中不进行clone操作
	 * 
	 * @param node
	 * @return
	 */
	private List<TreeNode> combinTree(TreeNode node) {
		List<TreeNode> borders = new ArrayList<TreeNode>();
		Queue<TreeNode> queue = new LinkedList<TreeNode>();

		TreeNode cloneRoot = new TreeNode("root", "root");
		cloneRoot.addChild(node);

		queue.add(cloneRoot);
		queue.add(root);

		while (!queue.isEmpty()) {
			TreeNode combinFrom = queue.poll();
			TreeNode combinTo = queue.poll();

			TreeNode[] childrenFrom = combinFrom.getChildren();
			TreeNode[] childrenTo = combinTo.getChildren();

			if (childrenFrom.length == 0) {
				borders.add(combinTo);
			} else {
				/*
				 * 遍历所有合并来源节点的孩子节点，对照合并目标的孩子节点
				 * 如果来源的孩子节点在目标中不存在，则将该节点添加到合并目标节点的孩子列表中 否则入队列，进行下次合并
				 */
				for (TreeNode childFrom : childrenFrom) {
					boolean exist = false;

					TreeNode existNode = null;
					for (TreeNode childTo : childrenTo) {
						if (childTo.equals(childFrom)) {
							exist = true;
							existNode = childTo;
							break;
						}
					}

					if (exist) {
						queue.add(childFrom);
						queue.add(existNode);
					} else {
						// 通过指针添加孩子节点，不进行clone操作，同时提取该节点的所有borders节点
						combinTo.addChild(childFrom);
						childFrom.setFather(combinTo);
						borders.addAll(getBorders(childFrom));
					}
				}
			}
		}

		return borders;
	}

	/**
	 * 将xml转化为tree
	 * 
	 * @param tokenxml
	 * @return
	 * @throws Exception
	 *             解析出错
	 */
	private TreeNode convert(String tokenXml) throws SAXException, IOException,
			Exception {
		ByteArrayInputStream bin = new ByteArrayInputStream(tokenXml.getBytes());
		Element root = DocumentBuilderFactory.newInstance()
				.newDocumentBuilder().parse(bin).getDocumentElement();

		TreeNode nodeRoot = new TreeNode(root.getNodeName(),
				root.getAttribute("id"));

		TreeNode curNode = nodeRoot;
		Element curEle = root;

		Queue<Object> queue = new LinkedList<Object>();
		queue.add(curNode);
		queue.add(curEle);

		while (!queue.isEmpty()) {
			curNode = (TreeNode) queue.poll();
			curEle = (Element) queue.poll();

			NodeList list = curEle.getChildNodes();
			int num = list.getLength();
			for (int i = 0; i < num; i++) {
				Element childEle = (Element) list.item(i);
				TreeNode childNode = new TreeNode(childEle.getNodeName(),
						childEle.getAttribute("id"));

				// 双向链接
				curNode.addChild(childNode);
				childNode.setFather(curNode);

				queue.add(childNode);
				queue.add(childEle);
			}
		}

		return nodeRoot;
	}

	public TreeNode getRoot() {
		return root;
	}

	static class TreeNode {
		private String key;
		private String value;
		private volatile boolean lock;

		private List<TreeNode> child = new ArrayList<TreeNode>();
		private TreeNode father;

		public TreeNode(String key, String value) {
			this.key = key;
			this.value = value;
		}

		public void addChild(TreeNode node) {
			child.add(node);
		}

		public void removeChild(TreeNode node) {
			child.remove(node);
		}

		public TreeNode[] getChildren() {
			TreeNode[] children = new TreeNode[child.size()];
			child.toArray(children);
			return children;
		}

		public String getKey() {
			return key;
		}

		public String getValue() {
			return value;
		}

		public void setLock(boolean lock) {
			this.lock = lock;
		}

		public boolean isLocked() {
			return lock;
		}

		public TreeNode getFather() {
			return father;
		}

		public void setFather(TreeNode father) {
			this.father = father;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj == null) {
				return false;
			}

			if (obj instanceof TreeNode) {
				TreeNode node = (TreeNode) obj;
				return key.equals(node.getKey())
						& value.equals(node.getValue());
			}

			return false;
		}

		@Override
		public String toString() {
			return key + ":" + value + ":" + hashCode();
		}
	}
}