Open Source & Linux Lab

It's better when it's simple

User Tools

Site Tools


courses:high_performance_computing:lock_free

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
courses:high_performance_computing:lock_free [2018/10/28 19:10] kelcourses:high_performance_computing:lock_free [2023/12/17 14:11] (current) odoronin
Line 1: Line 1:
 ====== Lock-free контейнер ====== ====== Lock-free контейнер ======
 +> [[https://classroom.github.com/a/NmuLCbAq|GitHub-classroom]] для самостоятельно изучающих курс **не** в рамках университетских программ
 +
 Необходимо реализовать в lock-free стиле следующий интерфейс: Необходимо реализовать в lock-free стиле следующий интерфейс:
  
 <code java> <code java>
 /** /**
- * Lock-Free очередь с приоритетами + * Lock-Free множество. 
- * @param <T> Тип элементов+ * @param <T> Тип ключей
  */  */
-public interface PriorityQueue<extends Comparable<E>> extends Queue<E> {+public interface Set<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();     boolean isEmpty();
 +    
 +    /**
 +     * Возвращает lock-free итератор для множества
 +     *
 +     * Итератор должен быть линеаризуем в терминах представления когда-либо существовавшего вместе набора элементов
 +     *
 +     * @return итератор для множества
 +     */
 +    java.util.Iterator<T> iterator();
 } }
 </code> </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 должно быть минимизировано
courses/high_performance_computing/lock_free.1540743030.txt.gz · Last modified: 2018/10/28 19:10 by kel