Разработка структур данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
нешних факторов (конкуренции со стороны других потоков, факта блокирования других потоков). Это самая сильная гарантия. Обычно это означает, что используются только такие примитивы, как atomic_exchange, atomic_increment, atomic_fetch_and_add (InterlockedExchange, InterlockedIncrement, InterlockedExchangeAdd), и в алгоритме нет циклов, на выполнение которых могут повлиять другие потоки. Такие примитивы, как atomic_compare_exchange (InterlockedCompareExchange) обычно не используется, так как с ним обычно связан цикл вида выполнять atomic_compare_exchange, пока он не будет выполнен успешно.
Пример wait-free алгоритма:
increment_reference_counter(rc_base* obj)
{_increment(obj->rc);
}decrement_reference_counter(rc_base* obj)
{(0 == atomic_decrement(obj->rc)) obj;
}
Как видно, любой поток может выполнить эти функции за конечное число шагов, не зависимо ни от чего, однако нет никаких гарантий, что результатом выполнения данного алгоритма будут ожидаемые данные, так как используемые примитивы гарантируют отсутствие конфликтов между двумя вызовами, но не предотвращают возникновение некорректных данных.
Lock-free
Lock-free алгоритмом или алгоритмом без блокировок называется такой алгоритм, который гарантирует, что в течении времени, за которое некий программный поток выполнит некое известное ограниченное число шагов в операции над таким объектом или структурой, некий, возможно, другой поток обязательно завершит операцию над этим объектом или структурой.
Иными словами данный алгоритм гарантирует прогресс как минимум для одного потока. Другие потоки могут ждать, но один поток минимум должен прогрессировать. Система в целом продвигается вперед. Это более слабая гарантия, чем wait-free. Обычно используется примитив atomic_compare_exchange (InterlockedCompareExchange).
Пример lock-free алгоритма:
void stack_push(stack* s, node* n)
{* head;
{= s->head;>next = head;
}(!atomic_compare_exchange(s->head, head, n));
}
Как видно, любой поток может крутиться в этом цикле теоретически бесконечно. Но любой повтор этого цикла означает, что какой-то другой поток успешно выполнил свою операцию. И никакой заблокированный/прерванный поток не может препятствовать продвижению других потоков. Отсюда следует, что система в целом продвигается вперед не зависимо ни от чего. В отличие от wait-free алгоритмов, lock-free алгоритмы благодаря использованию примитивов в цикле не только гарантируют отсутствие конфликтов между вызовами, но и предотвращают возникновение некорректных данных.
Obstruction-free
Obstruction-free алгоритмом или алгоритмом без препятствий называется такой алгоритм, который гарантирует, что каждая операция, выполняемая согласно этому алгоритму, будет выполнена за определенное известное число шагов в том случае, если выполнение все конкурирующие потоков приостановлено.
Поток продвигается вперед, только если не встречает конкуренции со стороны других потоков. В частности это означает, что при сильной конкуренции возможно никакой поток не будет совершать продвижения. То есть система будет находиться в так называемом livelock. Это самая слабая гарантия. Этот класс алгоритмов может показаться немного странным, поэтому стоит заметить, что заблокированные/прерванные потоки не могут препятствовать прогрессу других потоков, и obstruction-free алгоритмы могут быть более быстрые, чем lock-free.
.3 Выводы
На основе проведённого обзора можно сделать следующие выводы:
)В связи с тем, что одним из наиболее ограниченных ресурсов вычислительной системы является процессорное время, для решения поставленной задачи предпочтительнее использовать неблокирующую синхронизацию, так как в отличие от блокирующей синхронизации она гарантирует доступ к данным любому потоку в любой момент времени и отсутствие deadlock, что особенно важно для систем реального времени.
)В соответствии с четвёртым принципом неблокирующей синхронизации были рассмотрены специальные методы управления памятью, после чего было принято решения реализовать методы неблокирующего подсчёта ссылок и опасных указателей. Это обусловлено тем, что метод использования агрегатных счетчиков ссылок или поточных временных штампов является блокирующим без использования специального планировщика, а метод использования специальных тегов (счетчиков изменений) затрудняет повторное использование памяти.
)В разрабатываемой структуре для читающих потоков необходимо использовать алгоритмы без блокировок, так как необходимо следить не только за отсутствием конфликтов, но и предотвращать возникновение некорректных данных, а для пишущего потока достаточно алгоритма без ожидания, так как наличие только одного пишущего потока позволяет обеспечить отсутствие некорректных данных.
Глава 2. Разработка структуры и алгоритмов взаимодействия
.1 Требования к разрабатываемой структуре данных и обоснование выбранных методов реализации
Задачей данного дипломного проекта является разработка структуры данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени. Последнее условие накладывает существенные ограничения на время доступа к данным и выполнения операций, в связи с чем реализация на основе блокирующих алгоритмов не является оптимальной.
При разработке структуры данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени с использованием неблокирующей синхронизации необходимо учитывать, что структура данных должна:
)Состоять из задаваемого и постоянного в пределах одной программы числа элемен