Способ оптимизации работы со связными списками

Способ оптимизации работы со связными списками

Иллюстрации

Показать все

Реферат

Область техники

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

Уровень техники

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

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

На Фиг.1 показана структурная схема варианта реализации связного списка. Связный список 100 состоит из элементов списка 110, 120, 130, 140 и 150. Каждый элемент связного списка содержит собственные данные и ссылку на следующий элемент списка. Так, элемент 110 содержит блок собственных данных 111 и ссылку 112 на следующий элемент списка 120. Элемент 120 содержит блок собственных данных 121 и ссылку 122 на следующий элемент списка 130. Элемент 130 содержит блок собственных данных 131 и ссылку 132 на следующий элемент списка 140. Элемент 140 содержит блок собственных данных 141 и ссылку 142 на следующий элемент списка 150. Последний элемент списка 150 содержит только блок собственных данных 151.

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

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

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

На Фиг.2 показана структурная схема работы процессов чтения и записи со связным списком. Процессы чтения 210 и 220 осуществляют чтение элементов 110 и 120 связного списка 100 соответственно. Процесс записи 230 осуществляет изменение элемента 130 связного списка 100. Для того чтобы была обеспечена целостность получаемых процессами чтения 210 и 220 данных, указанные процессы чтения должны дождаться завершения работы процесса записи 230 с элементом связного списка 130, прежде чем начать чтение этого элемента. Таким образом, приоритет в использовании взаимного исключения в случае, представленном на Фиг.2, принадлежит процессу записи.

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

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

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

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

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

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

Таким образом, хотя перечисленные подходы направлены на решение определенных задач в области оптимизации работы со связными списками, они имеют ряд недостатков, которые были указаны выше. Настоящее изобретение позволяет более эффективно и результативно решить задачу предоставления процессам чтения непрерывного доступа к списку, при котором сохраняется целостность получаемых процессами чтения данных.

Раскрытие изобретения

Настоящее изобретение предназначено для оптимизации работы со связными списками.

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

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

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

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

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

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

Краткое описание чертежей

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

Заявленное изобретение поясняется следующими чертежами, на которых:

Фиг.1 показывает структурную схему варианта реализации связного списка.

Фиг.2 показывает структурную схему работы процессов чтения и записи со связным списком.

Фиг.3 показывает структурную схему варианта реализации способа оптимизации работы со связными списками.

Фиг.4 показывает структурную схему способа работы процесса чтения в способе оптимизации работы со связными списками.

Фиг.5 показывает структурную схему способа работы процесса записи в способе оптимизации работы со списками при выполнении операции логического удаления элемента списка.

Фиг.6 показывает структурную схему способа работы процесса записи в способе оптимизации работы со списками при выполнении операции добавления элемента списка.

Фиг.7 показывает структурную схему способа работы процесса записи в способе оптимизации работы со списками при выполнении операции удаления элемента списка.

Описание вариантов осуществления изобретения

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

На Фиг.3 показан один из вариантов реализации способа оптимизации работы со связными списками. Данный вариант реализации содержит систему управления списком 300 и собственно связный список 100. Система управления списком 300 в свою очередь состоит из устройства переключения активного счетчика 310, двух счетчиков процессов чтения 320 и 330 и устройства хранения количества элементов списка 340.

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

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

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

Устройство хранения количества элементов списка 340 предназначено для хранения и предоставления процессам чтения доступного для чтения количества элементов списка. Указанное доступное для чтения количество элементов списка процесс чтения проходит в ходе работы со связным списком 100. С целью обеспечения целостности получаемых процессами чтения данных в число доступных для чтения элементов списка, хранимое в устройстве 340, может не входить последний элемент списка, удаление либо добавление которого производится в определенный момент времени. Кроме того, как будет показано ниже, процесс чтения при начале работы со связным списком 100 после увеличения значения активного счетчика на единицу получает от устройства 340 количество элементов списка, которое ему необходимо пройти. Таким образом, каждый счетчик также подсчитывает количество процессов чтения, для которых доступно то количество элементов связного списка, которое хранилось в устройстве 340 в период времени, когда данный счетчик был активен.

В описываемом способе оптимизации работы со связными списками все операции, которые процессы записи производят с элементами связного списка 100, подразделяются на три типа: операция добавления элемента списка, операция логического удаления элемента списка и операция удаления элемента списка.

Операция добавления элемента списка используется процессом записи для добавления в связный список нового элемента.

Операция удаления элемента списка используется процессом записи для физического удаления элемента из связного списка. При этом длина списка сокращается.

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

На Фиг.4 показана структурная схема способа работы процесса чтения в способе оптимизации работы со связными списками. На этапе 410 процесс чтения начинает работу со связным списком 100. При этом значение активного в этот момент счетчика увеличивается на единицу на этапе 420. На этапе 430 процесс чтения получает от устройства хранения количества элементов списка 340 количество элементов списка, которое ему необходимо пройти, после чего обращается к первому элементу списка на этапе 440. На этапе 450 процесс чтения проверяет, не помечен ли элемент, к которому он обращается, как удаленный. В случае если элемент не помечен как удаленный, на этапе 460 производится чтение его данных, в противном случае на этапе 465 данные, содержащиеся в элементе, процессом чтения игнорируются. После этого процесс чтения на этапе 470 проверяет, не равно ли количество пройденных им элементов связного списка 100 полученному на этапе 430 количеству элементов. Если указанное равенство имеет место, процесс чтения завершает работу со списком на этапе 485, при этом значение активного на момент начала работы процесса чтения со списком счетчика уменьшается на единицу на этапе 490. В противном случае процесс чтения по ссылке первого элемента переходит к следующему элементу связного списка 100 на этапе 480. Этапы 450, 460, 465, 470 и 480 повторяются для последующих элементов связного списка 100 до тех пор, пока указанное равенство не будет достигнуто.

На Фиг.5 показана структурная схема способа работы процесса записи в способе оптимизации работы со списками при выполнении операции логического удаления элемента списка. На этапе 510 процесс записи начинает работу со связным списком 100 и производит поиск элемента списка, который необходимо удалить логически, на этапе 520. В случае если элемент не найден, процесс записи завершает работу со связным списком 100 на этапе 540. В случае если элемент найден, прежде чем завершить работу со связным списком 100 на этапе 540, процесс записи производит пометку найденного элемента удаленным на этапе 530.

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

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

На этапе 610 процесс записи начинает работу со связным списком 100, после чего, на этапе 620, определяет, присутствует ли в списке логически удаленный элемент. В случае если логически удаленный элемент в списке присутствует, процесс записи копирует данные нового элемента в логически удаленный элемент на этапе 630, после чего снимает с элемента пометку удаленным на этапе 640 и на этапе 670 завершает работу со списком. Таким образом, все процессы чтения, которые вслед за этим начнут работу со списком, увидят новый элемент вместо логически удаленного. В случае если на этапе 620 логически удаленный элемент в списке 100 не обнаружен, процесс записи добавляет новый элемент в конец списка на этапе 650, после чего на этапе 660 увеличивает на единицу значение, хранящееся в устройстве хранения количества элементов списка 340, и на этапе 670 завершает работу со списком. Таким образом, все процессы чтения, которые вслед за этим начнут работу со списком, увидят новый элемент, так как равенство между количеством пройденных процессом чтения элементов списка 100 станет равно значению, хранящемуся в устройстве хранения количества элементов списка 340, только после прочтения нового элемента.

На Фиг.7 показана структурная схема способа работы процесса записи в способе оптимизации работы со списками при выполнении операции удаления элемента списка. Так как в указанной операции элемент удаляется физически, в рассматриваемом алгоритме исключена вероятность получения процессом чтения нецелостных данных. На этапе 710 процесс записи начинает работу со связным списком 100 и на этапе 720 производит поиск элемента списка, который необходимо удалить. Указанный алгоритм рассматривается для случая, когда элемент, который необходимо удалить, найден в списке. В случае если элемент найден не будет, процесс записи завершает работу со связным списком 100. После того как элемент, который необходимо удалить, найден, процесс записи на этапе 730 определяет, является ли данный элемент последним в списке. В случае если элемент, который необходимо удалить, является последним в списке, процесс записи на этапе 735 уменьшает на единицу значение, хранящееся в устройстве хранения количества элементов списка 340, и на этапе 745 переключает активный счетчик с помощью устройства переключения активного счетчика 310. Все процессы чтения, которые вслед за этим начнут работу со списком, не увидят элемента, который необходимо удалить, так как равенство между количеством пройденных процессом чтения элементов станет равно значению, хранящемуся в устройстве хранения количества элементов списка 340, при прохождении процессом чтения предпоследнего элемента списка. Элемент, который необходимо удалить, может быть виден только тем процессам чтения, которые начали работу со списком до уменьшения на единицу значения устройства 340 на этапе 735 и, следовательно, до переключения активного счетчика на этапе 745. Так как указанные процессы чтения начинали работу со списком до переключения активного счетчика на этапе 745, при завершении их работы со списком будет уменьшаться на единицу счетчик, который после переключения активного счетчика на этапе 745 стал неактивным. Значение «ноль» указанного счетчика будет свидетельствовать о том, что все процессы чтения, которым мог быть виден удаляемый элемент, закончили работу со списком. Поэтому для того, чтобы избежать случая получения процессом чтения нецелостных данных, прежде чем удалить последний элемент списка процессу записи необходимо удостовериться в том, что значение неактивного счетчика равно нулю. С этой целью на этапе 755 процесс записи определяет, является ли значение неактивного счетчика равным нулю. В случае если значение неактивного счетчика не равно нулю, процесс записи на этапе 785 ожидает до тех пор, пока это значение не станет равным нулю. В случае если значение неактивного счетчика равно нулю, процесс записи удаляет последний элемент списка на этапе 765 и завершает работу со списком на этапе 775.

В случае если элемент, который необходимо удалить, не является последним в списке, процесс записи помечает данный элемент как удаленный на этапе 740 по алгоритму для операции логического удаления, описанному выше. После этого, на этапе 750, процесс записи производит копирование данных из последующего элемента в элемент, который на этапе 740 был помечен как удаленный. Далее процесс записи на этапе 760 снимает пометку удаленным с элемента, в который на этапе 750 были скопированы данные из последующего элемента, а сам последующий элемент помечает как удаленный на этапе 770. Таким образом, процесс записи меняет местами элемент, который необходимо удалить, с последующим элементом. То есть элемент, который необходимо удалить, перемещается к концу списка. Этапы 740, 750, 760 и 770 повторяются до тех пор, пока элемент, который необходимо удалить, не станет последним в списке, после чего данный элемент удаляется согласно этапам 735, 745, 755, 765, 775 и 785 описываемого алгоритма.

Стоит также отметить, что этапы 745, 755 и 785, на которых происходит переключение активного счетчика, проверка значения неактивного счетчика и ожидание момента времени, когда данное значение станет равным нулю, могут осуществляться и для других операций изменения связного списка.

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

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

2. Способ по п.1, в котором процесс записи перемещает элемент, который необходимо удалить, в конец списка в случае, если элемент, который необходимо удалить, не является последним в списке.

3. Способ по п.1, в котором процесс записи также производит логическое удаление элемента списка путем пометки элемента удаленным, при этом данные логически удаленного элемента списка игнорируются процессом чтения, и элемент остается в списке.

4. Способ предоставления процессам чтения непрерывного доступа к связному списку, который содержит один процесс записи и, по крайней мере, один процесс чтения, и в котором при добавлении нового элемента списка:все процессы чтения без ожидания получают доступ к списку и разделяются на процессы чтения, которые начали работу со списком до добавления нового элемента, и на процессы чтения, которые начали работу со списком после добавления нового элемента, при этом:а) процессы чтения, которые начали работу со списком до добавления нового элемента, выполняются для количества элементов списка, не содержащих добавляемый элемент;б) процессы чтения, которые начали работу со списком после добавления нового элемента, выполняются для количества элементов списка, содержащих добавленный элемент.

5. Способ по п.4, в котором процесс записи добавляет новый элемент в конец списка, в случае, если в списке нет логически удаленного элемента.

6. Способ по п.4, в котором процесс записи добавляет новый элемент путем копирования данных нового элемента в логически удаленный элемент и снятия с логически удаленного элемента пометки удаленным, в случае если в списке присутствует логически удаленный элемент.