Разработка алгоритмов

В любой момент времени данные могут иметь одно из следующих состояний:

- Данные уже существуют, но ещё не добавлены в структуру. Безопасное состояние, так как ещё ни один поток, кроме пишущего, не имеет к ним доступа. Переводится в следующее состояние пишущим потоком после добавления данных в структуру.

- Данные находятся в структуре и являются актуальными. Безопасное состояние, так как доступ к данным могут получать только читающие потоки, которые не изменяют их. Переходят в следующее состояние после устаревания.

- Данные находятся в структуре, но уже не являются актуальными. Опасное состояние, так как читающие потоки всё ещё могут получать доступ к данным, а пишущий поток уже перезаписывает их, при этом новые данные добавляются в структуру, а старые добавляются в список выбывших узлов и переходят в следующее состояние.

- Данные находятся в списке выбывших узлов, и ни один поток не может получить к ним доступ, однако один или несколько читающих потоков всё ещё работают с данными. Опасное состояние, так как при освобождении памяти из-под данных в текущем состоянии возникнут ошибки при чтении. После того как все читающие потоки завершили работу с данными, они переходят в следующее состояние.

- Данные находятся в списке выбывших узлов и не используются в текущий момент, при этом ни один поток не может получить к ним доступ. Безопасное состояние, предшествующее освобождению памяти из-под данных.

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

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

При разработке алгоритма чтения необходимо учитывать все принципы неблокирующей синхронизации, чтобы не получить ошибку при доступе к данным, так как отсутствие любого из принципов может привести к ошибке. В то же время при разработке алгоритма записи достаточно учитывать следующие принципы: узлы неизменяемого типа, подмена указателей и атомарные операции, чтобы не произошла ошибка доступа к данным читающими потоками во время их изменения пишущим потоком. Данные принципы полностью обеспечивают это. Принцип специальных методов управления памятью в данном случае не важен, так как пишущий поток всего один.

Кроме этого необходимо предусмотреть операцию освобождения памяти, а для этого, в соответствии с выбранными методами, требуется предусмотреть операцию добавления узла в список выбывших узлов. Её целесообразно объединить с операцией записи, так как данная операция всегда выполняется после изменения элемента массива.

Далее важно определиться с потоком, в котором будет вызываться операция освобождения памяти. Существует несколько возможных вариантов:

1) Вызов операции освобождения памяти в пишущем потоке.

2) Вызов операции освобождения памяти в читающем потоке.

3) Вызов операции освобождения памяти и в пишущем, и в читающем потоке.

Каждый из вариантов имеет свои достоинства и свои недостатки. Вызов операции освобождения памяти в пишущем потоке позволяет упростить освобождение памяти, так как данный поток всего один и не надо отслеживать какие-либо изменения со стороны других потоков. С другой стороны, если читающие потоки в данный момент используют все старые данные, то будет осуществлён вызов, в котором память не освободится. Вызов операции освобождения памяти в читающем потоке позволяет ускорить освобождение памяти, но усложняет взаимодействия между потоками, что может привести как к ошибкам, так и к общему уменьшению быстродействия. Третий вариант обеспечивает максимально быстрое освобождение памяти, но приводит к ещё большим проблемам, чем второй. Даже если использовать для выполнения новый поток, который всегда будет один (то есть поток, прежде чем вызвать операцию освобождение памяти, проверяет, не выполняется ли он уже), то всё равно будут потери в быстродействии. А учитывая то, что разрабатываемые алгоритмы должны иметь максимальное быстродействие, наиболее предпочтительным является первым вариант.

Однако и для первого варианта есть возможность выполнения освобождения памяти в новом потоке. В том случае, если выполнение происходит в пишущем потоке, освобождение памяти упрощается, так как не надо отслеживать изменения со стороны других потоков, но это может привести к тому, что новые данные уже поступили и поток должен бы уже писать их, а он занят освобождением памяти, в связи с чем читающие потоки могут либо работать с неактуальными данными, либо ожидать новые данные. В случае же выполнения освобождения памяти в новом происходит ускорение за счёт параллельного выполнения, однако это не избавляет нас от той ситуации, когда читающий или пишущий поток приостанавливается. К тому же может произойти следующая ситуация: вершина списка выбывших узлов не используется, и мы перед освобождением памяти из-под данного узла изменяем вершину с текущего узла на следующий, а в это время читающий поток уже добавил новый узел и изменил вершину. В результате получается, что добавленный пишущим потоком узел не находится в списке выбывших узлов и поэтому освободить из-под него память не представляется возможным в данных условиях. В связи с этим необходимо либо отслеживать изменения со стороны пишущего потока, либо всегда начинать освобождение узла со следующего после вершины, а память из-под неё освобождать перед завершением программы, так как в этом в любом случае может появиться необходимость, если пишущий поток завершился раньше читающих. Кроме этого необходимо отслеживать ситуацию, при которой произойдёт вызов второго потока, когда первый не завершил свою работу. Данная ситуация может привести к проблемам и ошибкам при освобождении, однако её легко отследить, но несмотря на это всё равно будут дополнительные задержки при выполнении. К тому же при наличии всего лишь одного пишущего потока и нескольких читающих, удобнее выполнять освобождение памяти в пишущем потоке, а не в отдельном, особенно в условиях системы с процессором с небольшим количеством ядер. Поэтому было принято решение выполнять освобождение памяти в пишущем потоке.

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

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

Дата добавления: 2015-11-14