Differences

This shows you the differences between two versions of the page.

--- courses:high_performance_computing:lock_free [2018/10/28 19:10] – kel
+++ courses:high_performance_computing:lock_free [2023/12/17 14:11] (current) – odoronin
@@ Line 1: / Line 1: @@
 ====== Lock-free контейнер ======
+> [[https://classroom.github.com/a/NmuLCbAq|GitHub-classroom]] для самостоятельно изучающих курс **не** в рамках университетских программ
 Необходимо реализовать в lock-free стиле следующий интерфейс:
 <code java>
 /**
- * Lock-Free очередь с приоритетами
+ * Lock-Free множество.
- * @param <T> Тип элементов
+ * @param <T> Тип ключей
  */
-public interface PriorityQueue<E extends Comparable<E>> extends Queue<E> {
+public interface Set<T extends Comparable<T>> {
+    /**
+     * Добавить ключ к множеству
+     *
+     * Алгоритм должен быть как минимум lock-free
+     *
+     * @param value значение ключа
+     * @return false если value уже существует в множестве, true если элемент был добавлен
+     */
+    boolean add(T value);
     /**
-     * Проверка очереди на пустоту
+     * Удалить ключ из множества
      *
-     * Метод должен быть lock-free (wait-free для уверенных в себе)
+     * Алгоритм должен быть как минимум lock-free
      *
-     * @return true если очередь пуста, иначе - false
+     * @param value значение ключа
+     * @return false если ключ не был найден, true если ключ успешно удален
+     */
+    boolean remove(T value);
+    /**
+     * Проверка наличия ключа в множестве
+     *
+     * Алгоритм должен быть как минимум wait-free для типов конечной размерноости и lock-free для остальных
+     *
+     * @param value значение ключа
+     * @return true если элемент содержится в множестве, иначе - false
+     */
+    boolean contains(T value);
+    /**
+     * Проверка множества на пустоту
+     *
+     * Алгоритм должен быть как минимум lock-free
+     *
+     * @return true если множество пусто, иначе - false
      */
     boolean isEmpty();
+    /**
+     * Возвращает lock-free итератор для множества
+     *
+     * Итератор должен быть линеаризуем в терминах представления когда-либо существовавшего вместе набора элементов
+     *
+     * @return итератор для множества
+     */
+    java.util.Iterator<T> iterator();
 }
 </code>
 //Дополнительные условности://
-  - Имя класса реализации - //LockFreePriorityQueue//
+  - Имя класса реализации - //SetImpl//
   - Класс должен иметь конструктор без параметров
-  - Pull Request должен содержать в части тестирования проходящие:
+  - Pull Request должен содержать в части тестирования проходящие тесты корректности на основе [[https://github.com/Kotlin/kotlinx-lincheck|lincheck]]
-    * Нагрузочные тесты на основе [[http://openjdk.java.net/projects/code-tools/jcstress/|jcstress]]
+  - В реализации не предполагается увидеть стандартные контейнеры из java.util.concurrent
-    * Тесты корректности на основе [[https://github.com/Devexperts/lin-check|lincheck]]
+  - Гарантировать исполнение на JDK 11
-  - В реализации не предполагается увидеть стандартные контейнеры из java.util.concurrent
+  - Изменение структуры данных должно происходить в разных частях независимо (то есть не должно быть contention гарантированно на одном элементе структуры данных, например - корне)
-  - Не обязательно учитывать "ограниченность" размера контейнера, в этом смысле методы "add" и "offer" эквивалентны
+  - Число "холостых" аллокаций для потоков, у которых не проходит CAS должно быть минимизировано