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

На первую часть вашего запроса уже дан ответ. Я попытаюсь ответить на вторую часть:

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

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

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

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

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

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

Да, одноядерный процессор может выполнять только одну инструкцию за раз (на самом деле, конвейерная обработка существует уже некоторое время, но, как однажды сказал профессор, это «бесплатный» параллелизм) . Несмотря на то, что каждый процесс, запущенный на вашем компьютере, выполняется только в течение определенного периода времени, затем он переходит в состояние ожидания. В этот момент другой процесс может начать/продолжить свое выполнение. А потом перейти в состояние простоя или закончить. Выполнение процессов чередуется.

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

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

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

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

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

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

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

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

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

Практический пример. В конце списка должно быть 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' s), но я сделаю небольшой комментарий, так как mfukar спросил. (надо было сделать это сразу, при отправке ответа)

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

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

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

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

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

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

Третий сценарий возникает при синхронизации операций в 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);
    }

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

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

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

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

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

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