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