Потокобезопасен ли код (код внутри)?

3
08 авг 2016 19:08
Здравствуйте.

Решил переписать свою наивную блокирующую реализацию промисов (Promise, см. ниже) на неблокирующий манер. Главным недочетом блокирующей реализации, на мой взгляд, является тот факт, что все then-действия выполняются под блокировкой и для получения блокировки метод then должен дожидаться их завершения. В ходе реализации возник вопрос: а действительно ли здесь неблокирующий алгоритм уместен? Рассудите, пожалуйста, мой спор с самим собой!

Привожу здесь максимально упрощенный вариант кода. Сомнительные моменты прокомментированы. Главный вопрос: может ли так случиться, что then-действие будет а) не выполнено вовсе б) выполнено дважды (UPD: повторное выполнение исключается "умным" хэндлером)? Побочный вопрос: а) уместен ли в таком простом случае неблокирующий подход б) не будет ли эффективнее блокирующий? в) нельзя ли как-то попроще добиться нужного эффекта?

Вот так бы это выглядело в блокирующем стиле (для полноты картины):

public class Promise {

    private Object result;
    private final List<Runnable> handlers;

    public Promise() {
        this.result = null;
        this.handlers = new LinkedList<>();
    }

    public synchronized Object result() {
        return this.result;
    }

    /** "Одноразовая" установка значения без возможности его перезаписать */
    public synchronized Promise resolve(Object result) {
        Objects().requireNonNull(result); // ADDED: Спасибо Vermut за обнаруженный баг
        if (this.result != null) return;
        this.result = result;
        handlers.forEach((h) -> h.run());
        return this;
    }

    /** Добавление then-действия: если промис не готов - добавить действие в очередь,
          готов - немедленно исполнить действие */
    public synchronized Promise then(Runnable action) {
        if (this.result != null) {
            action.run();
        } else {
            handlers.add(action);
        }
        return this;
    }
}


А вот так -- в неблокирующем. Собственно, он-то и интересует.

/** Умный хэндлер -- выполняет действие r только единожды. */
class Handler {

    public final AtomicBoolean executed;
    private final Runnable r;

    public Handler(Runnable r) {
        this.r = r;
        this.executed = new AtomicBoolean();
    }

    public void handle() {
        if (executed.compareAndSet(false, true)) {
            r.run();
        }
    }
}

public class Promise {

    private final AtomicReference<Object> result;
    private final ConcurrentLinkedQueue<Handler> handlers;

    public Promise() {
        this.result = new AtomicReference<Object>();
        this.handlers = new ConcurrentLinkedQueue<>();
    }

    public Object result() {
        return this.result.get();
    }

    /** "Одноразовая" установка значения без возможности его перезаписать */
    public Promise resolve(Object result) {
        Objects.requireNonNull(result); // ADDED: Спасибо Vermut за обнаруженный баг
        if (!this.result.compareAndSet(null, result)) return /* or throw exception */;
        // К этому месту this.result уже не сможет изменить свое значение
        while (!handlers.isEmpty()) { // Итератор коллекции может не успеть среагировать на добавление нового хэндлера
            for (Iterator<Handler> i = handlers.iterator(); i.hasNext();) {
                i.next().handle();
                // Нет смысла хранить хэндлеры дальше -- они все равно никогда не будут вызваны
                i.remove(); // ADDED: Спасибо Vermut за обнаруженный баг
            }
        }
        // handlers.clear(); // REMOVED: Спасибо Vermut за обнаруженный баг
        return this;
    }

    /** Добавление then-действия: если промис не готов - добавить действие в очередь,
          готов - немедленно исполнить действие */
    public Promise then(Runnable action) {
        if (this.result.get() != null) { // Готов - исполнить
            action.run();
        } else { // Не готов -- добавить
            Handler h = new Handler(action);
            handlers.add(h);
            if (this.result.get() != null) {
                // НО. Если хэндлер не успел добавиться до завершения промиса
                // (т.е. добавился после завершения) - он уже никогда не будет вызван.
                // Поэтому вызовем его руками. Если же он был/будет вызван дважды -- не беда. Он у нас умный.
                handlers.remove(h);  // ADDED: Спасибо Vermut за обнаруженный недочет
                h.handle();
            }
        }
        return this;
    }
}

Ответов: 5

2
26 авг 2016 23:39
Чо то я обдумал всё еще раз и решил обратно поменять своё мнение, на то что согласно JMM c этим кодом есть проблемы(если не заглядывать в исходники ConcurrentLinkedQueue). Этот пост частично основывается на моем предидущем, но выводы я сделал совсем другие.

Представим исполнение программы, которое ломает ваш алгоритм, если не сможем доказать, что такое исполнение невозможно то алгоритм действительно сломан. И так сценарий который будем безуспешно опровергать:
  • Есть поток Listener который подписывается на Promise то есть вызывает then
  • Есть поток Resolver который комплетит Promise то есть вызывает метод resolve
  • (1) Listener читает значение из атомика null
  • (2) Resolver успешно выполняет compareAndSet завершая Promise
  • (3) Resolver Проверяет очередь на пустоту и видит, что она пустая не видит подписчиков в очереди, и благополучно завершается.
  • (4) Listener добавляет таску в очередь.
  • (5) Listener читает значение из атомика результат, и снова читает из него null(???), ну допустим потому что никто не гарантрует насколько быстро читатель увидит обновления в атомике. И всё в очереди висит таска, но она не будет никогда выполнена.

Ключевой момент этого сценария отмечен (???). Если сможем доказать что чтение null на этом шаге возможно, то значит такой сценарий имеет право на жизнь и алгоритм нельзя считать рабочим.

Для начала протестируем, что такое исполнение не нарушает 17.4.4. Synchronization Order - при любом выполнении программы все synchronization actions должны выстраиваться synchronization order, причем это полный порядок, то есть про абсолютно любое действие синхронизации мы должны иметь возможность сказать произошло оно раньше или позже другого действия синхронизации. Давайте пересчитаем действия синхронизации в плохом сценарии:
(1) Listener читает значение из атомика - чтение из атомика является syncronization action согласно джавадокам на пакет java.util.concurrent.atomic
(2) Resolver выполняет compareAndSet - это тоже действие синхронизации согласно джавадокам на тот же пакет.
(3) Resolver Проверяет очередь на пустоту, то есть вызывает isEmpty() на очереди - если не заглядывать в реализацию метода isEmpty то в джавадоках не сказано что метод порождает какую либо синхронизацию, то есть действием синхронизации в данном случае это не является.
(4) Listener добавляет таску в очередь - тоже самое что и (3), джавадоки ConcurrentLinkedQueue молчат, поэтому не считаем это за действие синхронизации.
(5) Listener читает значение из атомика результат - как и пункт (1) это действие синхронизации.
И так если наш сценарий допустимый, то есть если в (5) мы прочитали null то как должны были быть выстроенны (1), (2) и (5) относительно друг друга в synchronization order? (1) и (5) выполнялись в одном треде, тут synchronization order совпадает с program order и (1) должен стоять в любом случае раньше (5), тут всё достаточно просто. Что можно сказать про (2)? И (1) и (5) согласно сценарию прочитали из атомика null, значит (2) не мог стоять в порядке раньше (1) иначен бы (1) не прочитал null, так же (2) не мог вклинится между (1) и (5) иначе бы (5) не прочитал null, то есть единственный вариант расположения (2) synchronization order для нашего сценария это будет поставить (2) после после (5), таким образом если наш негативный сценарий допустим то synchronization order выглядит так (1) -> (5) -> (2), или если схематично то так:
| Completer Thread | Listener Thread |
|                            |           (1)         |
|                            |           (5)         |
|              <---------------------          |
|            (2)            |                        |

Вроде ничего криминального согласно Synchronization Order мы не нашли.


Теперь протестируем не нарушает ли такой сценрий выполнения Happens Before Order, мы обязаны это сделать согласно спеке:
Quote:

An execution is happens-before consistent if its set of actions is happens-before consistent

Давайте построим happens-before-order. Пересчитаем happens before рёбрышки(между тредами естественно), интуитивно возможные кандидаты на intra tread связи это (4)->(3),(3)->(4) и (5)->(2), разберем их по порядку:
  • (4)->(3) Скупой javadoc к классу ConcurrentLinkedQueue обещает нам только один эффект "Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a ConcurrentLinkedQueue happen-before actions subsequent to the access or removal of that element from the ConcurrentLinkedQueue in another thread." Однако согласно легенде (4) не видит (3) поэтому и нету никакого happen-before ребра
  • (3)->(4) то же что и предидущий пункт, только еще легче, согласно тем же джавадоком чтение из очереди того факта что она пустая вообще никаким образом не может быть happens-before записи элемента в эту очередь.
  • (5)->(2)??? А теперь самое интересное и неожиданное. Happens before рёбра порождают только лишь synchronizes-with отношения, но даже не смотря на то что в единственно валидном для такого исполнения synchronization order (5) предшествовал (2), (5) не состоит synchronized with отношении с (2), потому что (5) это чтение, а (2) это запись, а synchronized-wth связи порождаются от записи к чтению, а не наоборот. Я феерически продолбал этот тонкий момент в предидущем посте и в результате неправильно прочертил ребро от (5) к (2), которого на самом деле нет.

Итого в нашем сценарии апокалипсиса у нас нет НИОДНОГО happens-before ребра между двумя тредами, а значит нет и ограничений на порядок в каком они могли видеть действия друг друга как угодно, в том числе и так как описанно в нашем негативном сценарии.

В общем получается что сценарий из начала поста не нарушил ни Synchronization Order, ни happens-before order, вполне себе валидное исполнение.

В общем с теоритической точки зрения оперируя только JMM можно сделать вывод что алгоритм не рабочий, а вот с практической точки зрения если пойти дальше джавадоков на ConcurrentLinkedQueue и смотреть прямо в код её реализации, то мы прийдём к другому выводу, так как любая операция всегда апдейтит голову через CAS, даже проверка на пустоту когда уже видит что очередь пустая, всё равно апдейтит голову. Но правильно либудет надеятся на незадокументированные особенности реализации, это отдельный вопрос.
2
09 авг 2016 19:20
По основным вопросам. Все корректно. Про видимость записи ответил в соответствюущей ветке. Видимости достаточно, так что выполнено будет.

По дополнительным.
Можно делать блокирующим, можно делать неблокриующим. В любом случае, ваша реализация гораздо более уместна, чем исходная. Она хотя бы не впадает в deadlock на основных сценариях вроде

Promise<Integer> a = ...;
Promise<Integer> b = ...;

// В одном потоке
a.then(va -> b.then(vb -> ()));
// В другом потоке
b.then(vb -> a.then(va -> ()));

Если a и b уже resolved, это и будет классический deadlock. Ваша реализация такому не подвержена.

Быстродействие нужно измерять. Для promise обычно разницы особой нет. Их типичный сценарий использования - работа со вводом/выводом, там экономии на синхронизации не видно. А на других задачах все может зависеть от количества конкуретных потоков, например.

По-другому реализовать можно. Попроще - зависит от предпочтений.
Самый простой вариант с точки зрения реализации - использовать synchronized только по-минимуму.
Promise then(Runnable action) {
  boolean runAction;
  synchronized(this) {
    runAction = result != null;
    if (!runAction) queue.add(action);
  }

  if (runAction) action.run();
}

В resolve похоже. В synchronized-блоке принимается решение и при необходимости "считывается" очередь. А вот обработчики выполняются уже вне synchronized-блока.
1
09 авг 2016 08:19
Вот теперь намного лучше.

Вместо того чтобы позволить GC собрать очередь самому, когда Promise перестанет быть достижимым, Вы решили чистить очередь самостоятельно, на ранней стадии, когда становится понятно, что задачи в очереди уже не нужны после их выполнения. На мой взгляд в данном конкретном случае, это абсолютно правильно помочь GC, потому, что ожидание на долговыволняющимся промисе, может привести к тому что он переживет несколько минорных сборок мусора в молодом поколении, будет перемещен в старое и потянет туда же в старое очередь, а очередь потнянет за собой все таски, и там они пролежат до FullGC, и что самое неприятное при неблагоприятных обстояьтельствах массовое утекание тасок из молодого поколения в старое будет приближать этот Full GC, то есть очищая очередь Вы предотвращаете проблему которая имеет название Nepotism, от неё например загибался twitter из-за ошибки в scala коллекциях. Но нужно довести дело до конца, в методе then, в том брэнче когда решили исполнить таску прям в методе then нужно после h.handle() вызывать handlers.remove(h), иначе задачу помощи GC нельзя считать выполненной.
1
08 авг 2016 21:31
Интересная тема.

Предлагаю исправить сначала явный баг: Итератор очередь не очищает, соответсвенно метод resolve уйдёт в бесконечный цикл.

Потом либо запрещайте в resolve передавать null и кидайте эксепшен, либо как Даг Ли в CompletableFuture используйте в Compare&Swap специальный null object, иначе result.compareAndSet(null, null)) всегда возвращает true.

kalaider :

Побочный вопрос: а) уместен ли в таком простом случае неблокирующий подход б) не будет ли эффективнее блокирующий?

Вполне уместен и уже тысячу раз был реализован в различных библиотеках, например в ListenableFuture из Guava. Такой функционал естественно востребован, потому что java.util.concurrent.Future очень неудобна тем, что ожидание на неё результата блокирует тред, а блокрироваться и ничего не делать это глупо. Ну и собственно начиная с восьмерки непосредсвенно в JDK появилась CompletableFuture.

kalaider :

в) нельзя ли как-то попроще добиться нужного эффекта?

Трудно сказать. В уже имеющихся реализациях набор функционала в десятки раз превышает тот, что есть у Вас, поэтому и кода там конечно во много раз больше написанно чем у Вас. Но прежде всего нужно пофиксить баг бесконечным циклом и потом проверить получившийся алгоритм на корректность, а уже потом можно будет поискать возможность написать короче, рассуждать о эффективности или не эффективности нерабочего алгоритма бессмысленно.
-2
09 авг 2016 10:49
UPDATED: написанное в этом посте считать недействительным, ниже отдельным постом я написал опровержение своих доводов.
Просьба запинусовать этот пост, чтобы он не висел на первом месте

Теперь же что касается корректности и ответа на главный вопрос:
Quote:
Главный вопрос: может ли так случиться, что then-действие будет а) не выполнено вовсе

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

На ум приходит только один негативный сценарий апокалипсиса для вашего алгоритма, подтверждать или опровергать возможность такого исполнения будем в дальнейшем:
  • Есть поток Listener который подписывается на Promise то есть вызывает then
  • Есть поток Resolver который комплетит Promise то есть вызывает метод resolve
  • (1) Listener читает значение из атомика null.
  • (2) Resolver успешно выполняет compareAndSet завершая Promise
  • (3) Resolver Проверяет очередь на пустоту и видит, что она пустая не видит подписчиков в очереди, и благополучно завершается.
  • (4) Listener добавляет таску в очередь.
  • (5) Listener читает значение из атомика результат, и снова читает из него null(???), ну допустим потому что никто не гарантрует насколько быстро читатель увидит обновления в атомике. И всё в очереди висит таска, но она не будет никогда выполнена.

Ключевой момент этого сценария отмечен (???). Если сможем доказать что чтение null на этом шаге возможно, то значит такой сценарий имеет право на жизнь и алгоритм нельзя считать рабочим.

Доказательство невозможности существование такого сценария:
Согласно разделу спецификации 17.4.4. Synchronization Order при любом выполнении программы все synchronization actions должны выстраиваться synchronization order, причем это полный порядок, то есть про абсолютно любое действие синхронизации мы должны иметь возможность сказать произошло оно раньше или позже другого действия синхронизации.
Давайте пересчитаем действия синхронизации в плохом сценарии:
(1) Listener читает значение из атомика - чтение из атомика является syncronization action согласно джавадокам на пакет java.util.concurrent.atomic
(2) Resolver выполняет compareAndSet - это тоже действие синхронизации согласно джавадокам на тот же пакет.
(3) Resolver Проверяет очередь на пустоту, то есть вызывает isEmpty() на очереди - если не заглядывать в реализацию метода isEmpty то в джавадоках не сказано что метод порождает какую либо синхронизацию, то есть действием синхронизации в данном случае это не является.
(4) Listener добавляет таску в очередь - тоже самое что и (3), джавадоки ConcurrentLinkedQueue молчат, поэтому не считаем это за действие синхронизации.
(5) Listener читает значение из атомика результат - как и пункт (1) это действие синхронизации.
И так если наш сценарий допустимый, то есть если в (5) мы прочитали null то как должны были быть выстроенны (1), (2) и (5) относительно друг друга в synchronization order? (1) и (5) выполнялись в одном треде, тут synchronization order совпадает с program order и (1) должен стоять в любом случае раньше (5), тут всё достаточно просто. Что можно сказать про (2)? И (1) и (5) согласно сценарию прочитали из атомика null, значит (2) не мог стоять в порядке раньше (1) иначен бы (1) не прочитал null, так же (2) не мог вклинится между (1) и (5) иначе бы (5) не прочитал null, то есть единственный вариант расположения (2) synchronization order для нашего сценария это будет поставить (2) после после (5), таким образом если наш негативный сценарий допустим то synchronization order выглядит так (1) -> (5) -> (2).
Давайте теперь раложим всё по тредам и построим happens-before-order:

| Completer Thread | Listener Thread |
|                           |        (1)            |
|                           |        (4)            |
|                           |        (5)            |
|           <-----------------------          |
|       (2)                |                        |
|       (3)                |                        |

Стрелкой обозначено synchronizes-with edge. Согласно разделу 17.4.5. Happens-before Order cвязь synchronizes-with автоматически порождает и связь happens-before, у нас (5) synchronizes-with (2), значит и hb(5,2), значит согласно тому же разделу спеки поток Completer уже находясь в пункте (2) должен был видеть все изменения в памяти сделанные потоком Listener которые предшествуют пункту 5, другими словами Completer на шаге (2), не мог увидеть очередь пустой, потому что он обязан видеть добавление в очередь из пункта (4). Значит наш сценарий апокалипсиса не имеет права на жизнь, таким образом программа исполнится не может!!

То есть доказать невозможность существания такого сценария нам даже не помешали невнятные джавадоки на ConcurrentLinkedQueue, в которых ничего не сказано про то что методы isEmpty и add тоже порождают synchronization actions внутри реализации. Поскольку других сценириев исполнения при которых алгоритм может быть сломан я не могу придумать, поэтому по карйне моему скромному мнению считаю алгоритм рабочим.
Модераторы: Нет
Сейчас эту тему просматривают: Нет