冲突可串行性判别算法

1）冲突可串行性判别算法。

数据库——冲突可串行化调度-CSDN博客

简介

​ 冲突可串行性判别算法用于在并发事务管理中判断多个事务是否可以在不引入冲突的情况下按某种顺序串行执行。在数据库管理系统和事务处理系统中尤为重要，目的是确保多个事务能够以一种合法的、没有数据不一致的方式执行。

核心思想：基于事务操作之间的冲突关系构建图，并使用拓扑排序判断图中是否存在环。如果图中存在环，则表示操作不可串行化；如果无环，则表示可串行化。

代码实现

TransactionOperation.java

package org.example.并发控制.冲突可串行化判断;

// 事务操作
public class TransactionOperation {
    int transactionId;
    int resuorceId;
    Type type;
    enum Type{
        READ, WRITE
    }

    public TransactionOperation(int transactionId, int resuorceId, Type type) {
        this.transactionId = transactionId;
        this.resuorceId = resuorceId;
        this.type = type;
    }

    public TransactionOperation() {
    }
}

SerializableConflictChecker.java

package org.example.并发控制.冲突可串行化判断;

import java.util.*;


public class SerializableConflictChecker {
    // 判断俩事务操作是否冲突
    public static boolean isConflict(TransactionOperation a, TransactionOperation b) {
        if (a.transactionId == b.transactionId)
            return true;
        return !(a.resuorceId != b.resuorceId || (a.type != TransactionOperation.Type.WRITE && b.type != TransactionOperation.Type.WRITE));
    }

    // 可串行化判断
    public static boolean isSerializable(List<TransactionOperation> opList) {
        // 将事务操作按照事务id分组
        // 假设事务id是连续的，从0开始
        Map<Integer, List<TransactionOperation>> transacList = new HashMap<>();
        for (TransactionOperation operation : opList) {
            if (!transacList.containsKey(operation.transactionId)) {
                transacList.put(operation.transactionId, new ArrayList<>());
            }
            transacList.get(operation.transactionId).add(operation);
        }

        // 生成一个大小为 n (事务数量)的图，然后4层for循环暴力遍历，每两个事务（A,B）里面的两对操作是否冲突，
        // 若冲突,则将列表中先发生的操作对应的事务 产生一条边 指向另一个事务
        int n = transacList.size();
        boolean[][] graph = new boolean[n][n];
        Set<Integer> keySet = transacList.keySet();
        for (Integer i : keySet) {
            for (Integer j : keySet) {
                if (i == j) continue;
                List<TransactionOperation> list1 = transacList.get(i);
                List<TransactionOperation> list2 = transacList.get(j);

                for (int k = 0; k < list1.size(); k++) {
                    for (int l = 0; l < list2.size(); l++) {
                        if (isConflict(list1.get(k), list2.get(l))) {
                            int i1 = opList.indexOf(list1.get(k));
                            int i2 = opList.indexOf(list2.get(l));
                            // 列表中先发生的操作对应的事务 产生一条边 指向另一个事务
                            if (i1 < i2) {
                                graph[i][j] = true;
                            } else {
                                graph[j][i] = true;
                            }
                        }
                    }
                }
            }
        }
        // 最后判断图中是否有环，有环则不可串行化
        // 使用拓扑排序判断是否有环

        // 计算入度
        int processedNodes = 0; // 已处理节点数
        int[] inDegree = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j]) {
                    inDegree[j]++;
                }
            }
        }
        // 初始化：将入度为0的节点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        // 拓扑排序
        while (!queue.isEmpty()) {
            int i = queue.poll();
            processedNodes++;
            for (int j = 0; j < n; j++) {
                if (graph[i][j]) {
                    inDegree[j]--;
                    if (inDegree[j] == 0) {
                        queue.offer(j);
                    }
                }
            }
        }
        return processedNodes == n;
    }
}

测试

@Test
public void test() {
    // 可串行化样例
    List<TransactionOperation> opList = new ArrayList<>();
    opList.add(new TransactionOperation(0, 1, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(0, 0, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(1, 1, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(1, 0, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(2, 0, TransactionOperation.Type.WRITE));

    System.out.println(SerializableConflictChecker.isSerializable(opList));
}

@Test
public void test2() {
    // 不可串行化样例
    List<TransactionOperation> opList = new ArrayList<>();
    opList.add(new TransactionOperation(0, 1, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(1, 0, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(1, 1, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(0, 0, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(2, 0, TransactionOperation.Type.WRITE));

    System.out.println(SerializableConflictChecker.isSerializable(opList));
}

@Test
public void test3() {
    // 可串行化样例
    List<TransactionOperation> opList = new ArrayList<>();
    opList.add(new TransactionOperation(1, 0, TransactionOperation.Type.READ));
    opList.add(new TransactionOperation(0, 1, TransactionOperation.Type.READ));
    opList.add(new TransactionOperation(1, 0, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(2, 0, TransactionOperation.Type.READ));
    opList.add(new TransactionOperation(0, 1, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(2, 0, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(1, 1, TransactionOperation.Type.READ));
    opList.add(new TransactionOperation(1, 1, TransactionOperation.Type.WRITE));

    System.out.println(SerializableConflictChecker.isSerializable(opList));
}

@Test
public void test4() {
    // 不可串行化样例
    List<TransactionOperation> opList = new ArrayList<>();
    opList.add(new TransactionOperation(1, 0, TransactionOperation.Type.READ));
    opList.add(new TransactionOperation(0, 1, TransactionOperation.Type.READ));
    opList.add(new TransactionOperation(1, 0, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(1, 1, TransactionOperation.Type.READ));
    opList.add(new TransactionOperation(2, 0, TransactionOperation.Type.READ));
    opList.add(new TransactionOperation(0, 1, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(2, 0, TransactionOperation.Type.WRITE));
    opList.add(new TransactionOperation(1, 1, TransactionOperation.Type.WRITE));

    System.out.println(SerializableConflictChecker.isSerializable(opList));
}

算法也是对其进行了正确判断