二维数组并行执行优化：单个单元格锁机制问题排查

背景与实现概述 #

我正在进行捕食者-猎物场景模拟的二维数组计算并行化开发：

• 用二维数组存储模拟数据，每个数组元素对应一个像素
• 并行化方案：将数组按线程数划分子区域，每个线程独立处理自身对应的子区域

核心算法步骤 #

1. 在自身子区域内随机选取一个单元格(xi, yi)
2. 随机选取该单元格的相邻区域（上下左右），记为(xin, yin)
3. 随机选择执行移动、选择或繁殖操作

移动操作示例代码 #

public void move(int xi, int yi, int xin, int yin){
   String temp = this.simulationBoard[xi][yi];
   this.simulationBoard[xi][yi] = this.simulationBoard[xin][yin];
   this.simulationBoard[xin][yin] = temp;
}

并行化规则 #

• 每个线程仅在自身子区域内选取单元格
• 步骤2中需检查(xi, yi)或(xin, yin)是否处于临界区（即可能被多个线程操作的子区域边界）
• 确保临界区的数组元素同一时间仅能被一个线程读写

当前同步实现代码 #

public class SimulationBoard{

   private String[][] simulationBoard;

   ...

   public void move(int xi, int yi, int xin, int yin, boolean lockXiYi, boolean lockXinYin) {
        if(lockXiYi && lockXinYin){
            this.moveXiYiXinYinLocked(xi, yi, xin, yin);
        }
        else if(lockXiYi){
            this.moveXiYiLocked(xi, yi, xin, yin);
        }
        else if(lockXinYin){
            this.moveXinYinLocked(xi, yi, xin, yin);
        }
        else {
            this.moveUnlocked(xi, yi, xin, yin);
        }
   }
    ...

    // 此处应确保同一时间仅一个线程访问simulationBoard[xi][yi]
    public void moveXiYiLocked(int xi, int yi, int xin, int yin){
        synchronized(simulationBoard[xi][yi]){
            String temp = this.simulationBoard[xi][yi];
            this.simulationBoard[xi][yi] = this.simulationBoard[xin][yin];
            this.simulationBoard[xin][yin] = temp;
        }
    }
}

问题 #

当使用4线程运行600×400的模拟场景时，未获得性能提升，其他配置下结果类似。请问是逻辑存在错误吗？synchronized(array[xi][yi])是否会锁住整个数组？

问题分析与解答 #

1. synchronized(simulationBoard[xi][yi])不会锁住整个数组 #

它只会锁住simulationBoard[xi][yi]这个对象本身，但这里存在致命的锁设计缺陷：
你用String类型的数组元素作为锁，而String是不可变对象，且JVM会对相同字符串常量做池化处理。如果多个单元格的内容相同（比如都是代表"猎物"的同一个字符串实例），这些单元格会共享同一把锁，导致完全无关的线程操作被迫串行等待，直接扼杀并行效率。

2. 性能无提升的核心原因 #

• 共享锁导致串行化：大量相同内容的单元格共享锁，线程间争抢严重，并行执行退化为串行执行
• 临界区操作逻辑错误：moveXiYiLocked仅锁住了源单元格，但移动操作同时修改了源和目标两个单元格。如果目标单元格属于其他线程的临界区，未加锁会引发数据竞争，也可能因锁顺序不一致导致死锁
• 临界区占比过高：600×400数组划分为4个子区域后，边界临界区的操作占比可能很高，线程频繁等待锁，抵消了并行带来的性能收益

3. 优化方案 #

• 替换锁对象：创建独立的二维锁数组，每个单元格对应唯一的Object锁，避免共享锁问题：

  private Object[][] locks;
  
  // 初始化时创建锁数组
  public SimulationBoard(int rows, int cols) {
      simulationBoard = new String[rows][cols];
      locks = new Object[rows][cols];
      for (int i = 0; i < rows; i++) {
          for (int j = 0; j < cols; j++) {
              locks[i][j] = new Object();
          }
      }
  }
  

• 规范多元素操作的锁顺序：操作两个单元格时，按固定顺序获取锁（比如基于对象哈希值排序），避免死锁：

  public void move(int xi, int yi, int xin, int yin) {
      Object lock1 = locks[xi][yi];
      Object lock2 = locks[xin][yin];
      // 确保锁的获取顺序一致，避免死锁
      if (System.identityHashCode(lock1) > System.identityHashCode(lock2)) {
          Object temp = lock1;
          lock1 = lock2;
          lock2 = temp;
      }
      synchronized(lock1) {
          synchronized(lock2) {
              String tempVal = simulationBoard[xi][yi];
              simulationBoard[xi][yi] = simulationBoard[xin][yin];
              simulationBoard[xin][yin] = tempVal;
          }
      }
  }
  

• 优化临界区处理：考虑采用"计算-批量更新"模式，先计算所有单元格的新状态，再一次性批量写入数组，彻底避免实时修改的锁竞争
• 调整线程数量：如果临界区操作占比过高，减少线程数可能降低锁竞争开销，反而提升整体性能

内容的提问来源于stack exchange，提问作者Adrian Weber