12. Очередь Майкла-Скотта. RCU

• Обсуждение очереди Майкла Скотта и её преимуществ.  

• Введение в тему и обещание новых знаний.  

• Очередь имеет структуру FIFO.  

• Методы для добавления и удаления элементов.  

• Возможность параллельного добавления и удаления элементов.  

• Создание нового элемента.  

• Перемещение указателя на хвост на новый элемент.  

• Проблемы с параллельным добавлением элементов.  

• Поток, добавляющий элемент, должен гарантировать его доступность.  

• Возможные проблемы с производительностью при добавлении элементов.  

• Очередь реализована на списке.  

• Добавление элементов в конец очереди, извлечение из головы.  

• Необходимость одновременного изменения ссылок.  

• Проблемы с производительностью при большом количестве элементов.  

• Поток, добавляющий элемент, может не успеть изменить ссылку.  

• Поток, добавляющий элемент, должен исправить ситуацию.  

• Поток, извлекающий элемент, не зависит от состояния хвоста.  

• Поток может исправить хвост, если видит, что он не пофикшн.  

• Поток, извлекающий элемент, может исправить хвост.  

• Гарантируется, что хвост отстает не более чем на один элемент.  

• Перекидываем ссылку на следующий элемент после хэда.  

• Если добавление не удалось, пытаемся еще раз.  

• Код добавления элемента в очередь имеет логику, описанную в слайдах.  

• Если следующий элемент у хвоста, заменяем ссылку на новый элемент.  

• Если элемент уже добавлен другим потоком, попытка добавления повторяется.  

• Важно, что добавление хвоста происходит сразу, без обхода всей структуры данных.  

• Если добавление удалось, фиксируем хвост.  

• Результат фиксации не важен, так как другие потоки могут помочь.  

• Если хвост не зафиксирован, фиксируем его.  

• Если очередь пуста, бросаем исключение.  

• Если очередь не пуста, фиксируем хвост и делаем один касс на голове.  

• Важно понимать, что если делаем больше одной атомарной операции, нужно заставить кого-то что-то сделать.  

• Очередь Майкла Скотта работает на основе взаимопомощи потоков.  

• Для добавления нужно два касса, для удаления один касс.  

• Вопросы по очереди задаются по очереди.  

• Лабораторная работа сложнее, но не на порядок.  

• Возможны ситуации, когда без взаимопомощи потоков все будет плохо.  

• Рассматриваются алгоритмы синхронизации, такие как RCU.  

• Задача: структура данных с множеством читателей и одним писателем.  

• Читатели должны работать параллельно, не обеспечивая потокобезопасность.  

• Писатели могут работать с структурой, но читатели не должны делать ничего для обеспечения потокобезопасности.  

• Функции read lock и write lock имеют пустую реализацию.  

• Потоки, читающие данные, работают в kernel space.  

• Один поток может выполнять операции с одной структурой данных.  

• Удаление элементов из списочной структуры данных требует двух фаз.  

• Первая фаза: перекидывание ссылки remove.  

• Вторая фаза: физическое освобождение памяти release.  

• Писатель сначала перекидывает ссылку, затем ждет завершения операций читателей.  

• Писатель должен дождаться завершения всех операций, чтобы безопасно освободить память.  

• Механизм wait for all readers используется для обеспечения безопасности.  

• Метод syncronize вызывается только писателем.  

• Писатель ждет завершения всех операций читателей.  

• Читатели не должны ничего делать, метод должен быть пустым.  

• Ядро операционной системы собрано без флага, запрещающего прерывание системных вызовов.  

• Системные вызовы в ядре не могут быть прерваны планировщиком.  

• Писатель должен дождаться завершения всех системных вызовов читателей.  

• Писатель должен проверить, что все читатели завершили свои операции.  

• Можно использовать анализ стека потоков для проверки.  

• Планировщик работает на уровне потоков, что гарантирует завершение операций в один квант времени.  

• Потоки работают параллельно на всех ядрах многоядерной системы.  

• Кванты времени могут не пересекаться.  

• Идея отслеживания вызовов функций не всегда оправдана.  

• Повышение приоритета потока при вызове функции.  

• Вытеснение других потоков для выполнения задачи.  

• Использование семафоров для проверки завершения всех потоков.  

• Функция должна проходить по всем ядрам.  

• Достаточно просто переключиться на ядро, чтобы вытеснить текущий поток.  

• Это гарантирует, что предыдущий поток завершил системный вызов.  

• Код не обрабатывает ситуации, когда поток блокирует ядро.  

• Ядро операционной системы обрабатывает такие ошибки.  

• В случае ошибок ядро сообщает об этом и предлагает перезагрузку.  

• Код может не работать в некоторых случаях, но это техническая ошибка.  

• Важно учитывать барьеры памяти и модели памяти.  

• Планировщик должен поставить поток на ядро, даже если ему нечего делать.  

• Код может проходить по своему же ядру, что не является ошибкой.  

• Это может быть не оптимально, но не ошибочно.  

• Пришло время для дальнейших обсуждений и оптимизации.  

• Ядро операционной системы обрабатывает замену процессора на горячую.  

• Если ядро скомпилировано без поддержки этой функциональности, код ничего не делает.  

• В случае поддержки, код обрабатывает начало и окончание замены процессора.  

• В специализированных серверах можно заменять процессоры на горячую.  

• Это позволяет увеличивать или уменьшать производительность без перезагрузки системы.  

• В таких серверах обычно есть два резервных блока питания.  

• Windows может работать на таких серверах, но это редко применяется.  

• В ядре операционной системы существует более 100 структур данных, использующих технику синхронизации.  

• Производительность современных операционных систем во многом зависит от этого подхода.  

• Если разрешить прерывания, теряется инвариант завершения операции.  

• Для решения этой проблемы добавляется счетчик эпохи структуры данных.  

• Писатель инкрементирует счетчик, а читатели копируют его и инкрементируют в конце.  

• Комментарии в коде ядра операционной системы помогают понять сложные многопоточные операции.  

• Комментарии разделяют код на понятные части для чтения и изменения.  

• В коде часто используются барьеры памяти и семантика эквайр.  

• Техника копирования и обновления заключается в создании копии структуры данных перед изменением.  

• Это позволяет избежать копирования всей структуры данных, что повышает производительность.  

• В общем случае, лучше разделять читателей и писателей, чтобы избежать постоянного копирования.  

• В пользовательском пространстве разработчики используют другие алгоритмы и механизмы.  

• Слайды Максима Хижинского с конференции 2015 года помогут понять, как это реализуется.  

• Хижинский является одним из самых квалифицированных разработчиков алгоритмов и механизмов.  

• Автор недавно сменил работу и продолжает выступать на конференциях.  

• На слайде показано, что добавление данных в структуру данных не вызывает проблем, так как читатели продолжают работать.  

• Проблемы возникают при удалении данных, когда писатель меняет эпоху структуры данных.  

• Глобальная эпоха структуры данных представлена как атомарное целое число.  

• В ядре используется счетчик из одного бита, так как важно только изменение эпохи, а не количество изменений.  

• В пользовательском пространстве используется счетчик для вложенного захвата.  

• Мьютекс используется только для писателей, чтобы избежать конфликтов.  

• Структура данных читателя состоит из локальной эпохи и указателя на следующую структуру данных.  

• Читатель регистрируется и получает структуру данных для работы.  

• Читатель при входе в секцию чтения получает глобальную эпоху и сохраняет её в локальную.  

• После завершения работы читатель меняет свою локальную эпоху.  

• Читатель выполняет две атомарные операции: получение глобальной эпохи и изменение локальной эпохи.  

• Писатель захватывает примитив синхронизации и ждет, пока все читатели выйдут из текущей эпохи.  

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

• Логика работы писателя проста: он ждет, пока все читатели завершат свои операции.  

• Использование однобитовой эпохи может привести к проблемам из-за неатомарности операций.  

• Писатель может удалить узел, пока читатель еще работает, что приводит к некорректному удалению.  

• Для решения этой проблемы писатель выполняет операцию дважды, ожидая дольше, чем нужно.  

• Код на слайде является реальным и используется в библиотеках.  

• В Linux есть пакет, который позволяет использовать примитивы синхронизации в пользовательском пространстве без написания прикладного кода.  

• Пакет включает стандартные решения для копирования, обновления, реализации и пространства.  

• Эти решения могут использоваться в прикладном коде как библиотечные.  

• "Россия" - это примитив синхронизации, используемый в ядре операционной системы.  

• Он активно применяется в более чем сотне структур данных.  

• "Россия" эффективен для случаев с большим количеством читателей и малым количеством писателей.  

• "Россия" полезен в случаях, когда требуется высокая производительность.  

• В прикладном коде его использование оправдано, если стандартные контейнеры не справляются.  

• Важно знать, что "Россия" подходит для конкретных ситуаций, которые можно определить только на практике.  

• "Россия" обеспечивает вейт-фри чтение, но не лок-фри запись.  

• Это позволяет сочетать в одной структуре данные с разными уровнями безопасности.  

• Реализация "России" на Java возможна, но не рекомендуется.  

• Использование системного кода через дженай не всегда оправдано.  

• Реализация на Java возможна с использованием существующих абстракций, таких как AtomicInteger и LockSupport.  

• Java не может обеспечить гарантированную производительность.  

• Алгоритмы, требующие такой производительности, редко используются в Java.  

• Это связано с тем, что такие системы обычно не соответствуют классу систем, где применяются языки со сборщиком мусора.