ArrayList и многопоточность в Java

Ответ 1

Существует три аспекта того, что может пойти не так, если вы используете ArrayList (например) без надлежащей синхронизации.

первый сценарий заключается в том, что если два потока будут одновременно обновлять ArrayList, он может быть поврежден. Например, логика добавления к списку выглядит примерно так:

public void add(T element) {
    if (!haveSpace(size + 1)) {
        expand(size + 1);
    }
    elements[size] = element;
    // HERE
    size++;
}

Теперь предположим, что мы имеем один процессор/ядро ​​и два потока, выполняющих этот код в том же списке в то же время. Предположим, что первый поток попадает в точку с меткой HERE и выгружается. Второй поток приходит и перезаписывает слот в elements, чтобы первый поток только что обновил свой собственный элемент, а затем увеличивает size. Когда первый поток наконец получает контроль, он обновляет size. Конечным результатом является то, что мы добавили второй элемент потока, а не первый элемент потока, и, скорее всего, также добавили в список null. (Это просто иллюстративно. На самом деле, компилятор нативного кода может изменить порядок кода и т.д. Но дело в том, что могут произойти плохие вещи, если обновления происходят одновременно.)

второй сценарий возникает из-за кэширования содержимого основной памяти в кэш-памяти процессора. Предположим, что у нас есть два потока: один добавляет элементы в список, а второй - размер списка. Когда в потоке добавляется элемент, он обновляет атрибут list size. Однако, поскольку size не volatile, новое значение size не может быть немедленно записано в основную память. Вместо этого он может находиться в кеше до точки синхронизации, в которой для модели памяти Java требуется, чтобы записи в кеш-память были сброшены. В то же время второй поток может вызвать size() в списке и получить устаревшее значение size. В худшем случае второй поток (например, вызов get(int)) может видеть несогласованные значения size и массива elements, что приводит к неожиданным исключениям. (Обратите внимание, что проблема может возникнуть даже тогда, когда есть только одно ядро ​​и нет кэширования памяти. Компилятор JIT может использовать регистры CPU для хранения содержимого кэша, и эти регистры не очищаются и не обновляются по отношению к их ячейкам памяти когда происходит контекстный переключатель потока.)

третий сценарий возникает при синхронизации операций с ArrayList; например обернув его как SynchronizedList.

    List list = Collections.synchronizedList(new ArrayList());

    // Thread 1
    List list2 = ...
    for (Object element : list2) {
        list.add(element);
    }

    // Thread 2
    List list3 = ...
    for (Object element : list) {
        list3.add(element);
    }

Если список thread2 - это ArrayList или LinkedList, и оба потока одновременно выполняются, поток 2 будет терпеть неудачу с ConcurrentModificationException. Если это какой-то другой (домашний brew) список, то результаты непредсказуемы. Проблема заключается в том, что создание list синхронизированного списка НЕ ​​ДОСТАТОЧНО, чтобы сделать его потокобезопасным в отношении последовательности операций списка, выполняемых разными потоками. Чтобы получить это, приложение, как правило, необходимо синхронизировать с более высоким уровнем/более грубым зерном.

Кроме того, я помню, что мне сказали, что несколько потоков не работают одновременно, 1 поток запускается на некоторое время, после чего выполняется другой поток (на компьютерах с одним процессором).

Правильно. Если для запуска приложения доступно только одно ядро, очевидно, что только один поток запускается за раз. Это делает некоторые из опасностей невозможными, а другие становятся гораздо менее вероятными. Тем не менее, ОС может переключаться с одного потока на другой поток в любой точке кода и в любое время.

Если это было правильно, как два потока могли одновременно получать одни и те же данные? Может быть, поток 1 будет остановлен в середине изменения чего-то, и начнется поток 2?

Угу. Это возможно. Вероятность этого очень мала ¹ но это делает эту проблему более коварной.

^{1 - Это связано с тем, что события с временным разделением потоков крайне нечасты, когда они измеряются на шкале времени аппаратных тактовых циклов.}

Ответ 2

Практический пример. В конце списка должно быть 40 элементов, но для меня это обычно показывает от 30 до 35. Угадайте, почему?

static class ListTester implements Runnable {
    private List<Integer> a;

    public ListTester(List<Integer> a) {
        this.a = a;
    }

    public void run() {
        try {
            for (int i = 0; i < 20; ++i) {
                a.add(i);
                Thread.sleep(10);
            }
        } catch (InterruptedException e) {
        }
    }
}


public static void main(String[] args) throws Exception {
    ArrayList<Integer> a = new ArrayList<Integer>();

    Thread t1 = new Thread(new ListTester(a));
    Thread t2 = new Thread(new ListTester(a));

    t1.start();
    t2.start();
    t1.join();
    t2.join();
    System.out.println(a.size());
    for (int i = 0; i < a.size(); ++i) {
        System.out.println(i + "  " + a.get(i));
    }
}

изменить
Есть более подробные объяснения (например, Stephen C post), но я сделаю небольшой комментарий, так как mfukar. (должен был сделать это сразу, когда вы отправляете ответ)

Это известная проблема приращения целого из двух разных потоков. Там хорошее объяснение в учебнике Sun Java по concurrency. Только в этом примере они имеют --i и ++i, и мы имеем ++size дважды. (++size является частью реализации ArrayList#add).

Ответ 3

Я действительно не вижу экземпляр, где строка частично модифицирована, я нахожусь здесь на правильном пути?

Этого не произойдет. Однако может случиться так, что добавляется только одна из строк. Или что во время добавления вызова возникает исключение.

Может кто-нибудь, пожалуйста, дайте мне пример, где ArrayList вызывает проблему, и Vector решает его?

Если вы хотите получить доступ к коллекции из нескольких потоков, вам необходимо синхронизировать этот доступ. Однако просто использование вектора действительно не решает проблему. Вы не получите проблем, описанных выше, но следующий шаблон все равно не будет работать:

 // broken, even though vector is "thread-safe"
 if (vector.isEmpty())
    vector.add(1);

Сам Вектор не будет поврежден, но это не означает, что он не может попасть в состояния, которые ваша бизнес-логика не захочет иметь. Вам необходимо синхронизировать код приложения (и тогда нет необходимости использовать Vector).

synchronized(list){
   if (list.isEmpty())
     list.add(1);
}

Пакеты служебных программ concurrency также имеют ряд коллекций, которые предоставляют атомарные операции, необходимые для потоков, защищенных потоками, и т.д.

Ответ 4

Когда это вызовет проблемы?

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

Кроме того, я помню, что мне сказали, что несколько потоков на самом деле выполняется одновременно, 1 поток запускать на некоторое время и другой поток после этого (на компьютерах с один процессор). Если это было правильно, то как если бы два потока никогда не обращались к одному и тому же данные одновременно? Может быть, нить 1 будет остановлена ​​в середине что-то изменит, а поток 2 начать?

Да, одноядерный процессор может выполнять только одну инструкцию за раз (на самом деле,

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

Ответ 5

Первая часть вашего запроса уже ответила. Я постараюсь ответить на вторую часть:

Кроме того, я помню, что мне сказали, что несколько потоков не работают одновременно, 1 поток запускается на некоторое время, после чего выполняется другой поток (на компьютерах с одним процессором). Если это было правильно, как два потока могли одновременно получать одни и те же данные? Может быть, поток 1 будет остановлен в середине изменения чего-то, и начнется поток 2?

в структуре wait-notify, поток, который блокирует объект, отпускает его, когда он ждет некоторое ожидание. Отличным примером является проблема производителя-потребителя. См. Здесь: текст ссылки

Ответ 6

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