Как сделать глубокое копирование нерегулярного двумерного массива - PullRequest
1 голос
/ 28 марта 2011

Я наткнулся на раздражение, когда я писал класс Java; Я не мог понять, как сделать копирование двумерного массива потоком безопасным. Это простая версия класса:

public class Frame {
  private boolean[][] content;

  public Frame(boolean [][] content) {
    boolean[][] threadSafeCopy = deepCopy(content);
    if (!(threadSafeCopy != null)) {
      throw new NullPointerException("content must not be null");
    }
    if (!(threadSafeCopy.length > 0)) {
      throw new IllegalArgumentException("content.length must be greater than 0");
    }
    if (!(threadSafeCopy[0] != null)) {
      throw new IllegalArgumentException("content[0] must not be null");
    }
    if (!(threadSafeCopy[0].length > 0)) {
      throw new IllegalArgumentException("content[0].length must be greater than 0");
    }
    for (int i = 1, count = threadSafeCopy.length; i < count; ++i) {
      if (!(threadSafeCopy[i].length == threadSafeCopy[0].length)) {
        throw new IllegalArgumentException
            (   "content[" + i + "].length [" + threadSafeCopy[i].length
              + "] must be equal to content[0].length [" + threadSafeCopy[0].length + "]"
            );
      }
    }
    this.content = threadSafeCopy;
  }

  private boolean[][] deepCopy(boolean[][] content) {
    boolean[][] result = null;
    if (content != null) {
      synchronized(content) { //do our best to make this as multi-threaded friendly as possible
        result = new boolean[content.length][];
        for (int i = 0, count = content.length; i < count; ++ i) {
          if (content[i] != null)
          {
            synchronized(content[i]) {
              result[i] = content[i].clone();
            }
          }
        }
      }
    }
    return result;
  }

  public boolean[][] getContent() {
    boolean[][] result = new boolean[this.content.length][]; //defensive copy
    for (int i = 0, count = result.length; i < count; ++i) {
      result[i] = this.content[i].clone(); //defensive copy
    }
    return result;
  }
}

Однако приведенная выше реализация метода private boolean[][] deepCopy(boolean[][] content) на самом деле не является поточно-ориентированной. Возможно, что массив активно модифицируется другим потоком, пока этот метод пытается скопировать. Конечно, я защитил себя от самого оскорбительного случая, используя synchronized в базовом массиве. Однако это не приводит к блокировке набора экземпляров массива 2-го измерения. И они могут быть изменены во время копирования.

Есть ли способ собрать блокировку объекта для каждого базового массива (content) и под-массивов (content[0], content[1], ..., content[content.length - 1]), чтобы я мог вызвать что-то вроде synchronized(objectsToLockSimultaneouslyList), и оно заблокирует все объекты одновременно и в порядке списка. Если это так, я могу спокойно скопировать содержимое массива.

Если нет, какие другие виды решений доступны для «блокирования всех модификаций массива» без необходимости изменять классы, которые создают экземпляр Frame, или изменять конструктор Frame так, чтобы он не принимал массив, а только экземпляры неизменные коллекции (которые сами по себе спускаются в другую кроличью нору).

Спасибо за любые рекомендации в этой области.

UPDATE: То, что я хочу сделать, принципиально невозможно. И мое понимание блокировки объектов с помощью синхронизированных данных также было ошибочным (tyvm glowcoder, Paulo and Brian). Сейчас я попытаюсь изменить интерфейс в Frame, чтобы использовать List<List<Boolean>>, что, кажется, кажется НАСТОЛЬКО гораздо более неэффективным. Или я могу использовать Set<XyCoordinate>, если наличие XyCoordinate означает «true». Опять же, это кажется чертовски неэффективным, но потокобезопасным. Тьфу!

Ответы [ 4 ]

1 голос
/ 28 марта 2011

Я бы порекомендовал вам изучить использование пакета java.util.concurrent.Он имеет кучу полезных классов, которые могут вам помочь.

Для вашего конкретного примера вы можете написать простой ThreadSafe2DArray класс:

public class ThreadSafe2DArray {
    private ReadWriteLock readWriteLock;
    private Lock readLock;
    private Lock writeLock;
    private boolean[][] data;

    public ThreadSafe2DArray(int rows, int cols) {
        this.data = new boolean[rows][cols];
        this.readWriteLock = new ReentrantReadWriteLock();
        this.readLock = readWriteLock.readLock();
        this.writeLock = readWriteLock.writeLock();
    }

    public boolean get(int row, int col) {
        try {
            readLock.lock();
            return data[row][col];
        }
        finally {
            readLock.unlock();
        }
    }

    public void set(int row, int col, boolean b) {
        try {
            writeLock.lock();
            data[row][col] = b;
        }
        finally {
            writeLock.unlock();
        }
    }

    public boolean[][] copyData() {
        try {
            readLock.lock();
            // Do the actual copy
            ...
        }
        finally {
            readLock.unlock();
        }
    }
}

Вы также можете предоставить массив необработанных данных.и блокировка чтения / записи, если вы хотите разрешить клиентам выполнять собственную блокировку, например, если клиенты могут читать или обновлять большое количество записей в одном чанке.

Этот подход намного более гибкий, чем использованиеraw synchronized блокирует и может быть быстрее или лучше для вашего случая, хотя многое зависит от того, какого рода споры вы ожидаете на практике.Дополнительным преимуществом этого является то, что вам не нужно заставлять что-либо быть неизменным.

В принципе, если два потока когда-либо будут бороться за ресурс, они должны договориться о некоторыхсвоего рода механизм блокировки.Если поток, который заполняет массив данных, не воспроизводится нормально, тогда единственный вариант - иметь оболочку, которая вызывает блокировку.Если другой поток хорошо себя ведет, то вы также можете синхронизировать объект массива верхнего уровня в обоих потоках, или вы можете использовать подход expose-locks-and-data, или просто использовать класс, представленный выше, и вызвать copyData в вашем Frame классе.

Этот ответ получил намного дольше, чем я предполагал.Надеюсь, это имеет смысл.

РЕДАКТИРОВАТЬ: Обратите внимание, что важно поместить unlock вызов в блок finally на случай, если неожиданный RuntimeException (или Error) будет брошен где-то внутри try.В этом случае код довольно прост, так что он, вероятно, излишний, но он сделает код более удобным для обслуживания, если эта защитная сеть уже установлена.

EDIT2: Я отмечаю, что вы специально упомянули нерегулярный массив.Я оставил пример как обычный массив в интересах краткости:)

1 голос
/ 28 марта 2011

Похоже, у вас возникли некоторые недоразумения по поводу блокировки объектов.

Блок (или метод) synchronized для некоторого объекта не не избегает каких-либо изменений в этом объекте . Это только позволяет избежать того, что другие потоки одновременно находятся в синхронизированных блоках или методах одного и того же объекта (за исключением тех, которые в wait() того же объекта).

Итак, чтобы быть поточно-ориентированным здесь, вы должны убедиться, что все ваши обращения к массиву синхронизируются с одним и тем же объектом блокировки.

1 голос
/ 28 марта 2011

Я думаю, что вам лучше всего обернуть массив в объект и обеспечить синхронизированный доступ к нему. Затем вы можете сделать глубокое копирование с «дверью закрытой» для метода доступа.

void deepCopy(boolean[][] orig) {
    synchronized(orig) {
        boolean[][] result = new boolean[orig.length][];
        deepCopy(orig,0);
        return result;        
    }
}

/**
 * recursive method to lock all rows in an array, and then copy
 * them in (backwards, by chance)
 */
void deepCopy(boolean[][] orig, int row) {
    if(row == orig.length) return; // end condition
    synchronized(orig[row]) { // lock the row first
        deepCopy(orig,row+1); // lock the next row
        content[row] = new boolean[orig[row].length];
        for(int i = 0; i < content[row].length; i++)
            content[row][i] = orig[row][i];
        // now, do row - 1
    }
}
0 голосов
/ 28 марта 2011

Я действительно думаю, что вы не понимаете некоторые основные концепции многопоточности.

Если какой-то другой поток имеет ссылку на массив, который вы передаете в конструктор Frame, ничто , которое вы делаете в Frame, может вам помочь. Этот другой поток может изменить его по своему желанию.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...