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
Next revisionBoth sides next revision
courses:high_performance_computing:lock_free [2018/10/28 19:10] kelcourses:high_performance_computing:lock_free [2021/11/15 02:19] kel
Line 4: Line 4:
 <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  +
-  - Не обязательно учитывать "ограниченность" размера контейнера, в этом смысле методы "add" и "offer" эквивалентны+
courses/high_performance_computing/lock_free.txt · Last modified: 2023/12/17 14:11 by odoronin