Differences

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

--- courses:high_performance_computing:lock_free [2017/04/17 23:57] – created 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 стиле следующий интерфейс:
@@ Line 7: / Line 9: @@
  * @param <T> Тип ключей
  */
-public interface LockFreeSet<T extends Comparable<T>> {
+public interface Set<T extends Comparable<T>> {
     /**
      * Добавить ключ к множеству
@@ Line 17: / Line 19: @@
      */
     boolean add(T value);
     /**
@@ Line 27: / Line 30: @@
      */
     boolean remove(T value);
     /**
      * Проверка наличия ключа в множестве
      *
-     * Алгоритм должен быть как минимум wait-free
+     * Алгоритм должен быть как минимум wait-free для типов конечной размерноости и lock-free для остальных
      *
      * @param value значение ключа
@@ Line 37: / Line 41: @@
      */
     boolean contains(T value);
     /**
      * Проверка множества на пустоту
      *
-     * Алгоритм должен быть wait-free (достаточно lock-free, wait-free для сильно уверенных в себе)
+     * Алгоритм должен быть как минимум lock-free
      *
      * @return true если множество пусто, иначе - false
      */
     boolean isEmpty();
+    /**
+     * Возвращает lock-free итератор для множества
+     *
+     * Итератор должен быть линеаризуем в терминах представления когда-либо существовавшего вместе набора элементов
+     *
+     * @return итератор для множества
+     */
+    java.util.Iterator<T> iterator();
 }
 </code>
+//Дополнительные условности://
+  - Имя класса реализации - //SetImpl//
+  - Класс должен иметь конструктор без параметров
+  - Pull Request должен содержать в части тестирования проходящие тесты корректности на основе [[https://github.com/Kotlin/kotlinx-lincheck|lincheck]]
+  - В реализации не предполагается увидеть стандартные контейнеры из java.util.concurrent
+  - Гарантировать исполнение на JDK 11
+  - Изменение структуры данных должно происходить в разных частях независимо (то есть не должно быть contention гарантированно на одном элементе структуры данных, например - корне)
+  - Число "холостых" аллокаций для потоков, у которых не проходит CAS должно быть минимизировано