Re[17]: deadlock. вопросы
От: Sinclair Россия http://corp.ingrammicro.com/Solutions/Cloud.aspx
Дата: 01.09.11 12:28
Оценка: +1
Здравствуйте, avpavlov, Вы писали:

A>А я считаю, что есть смысл проводить между ними черту, о чем тоже писал. Потому что если эту черту не провести, то возникает двусмысленность, из-за невозможности точно сказать, о чём в конкретный момент времени идёт речь — "о способе хранения" или "о способе хранения и манипулировании".

Помимо способа хранения, структура данных также определяет некоторые инварианты. В частности, "структура" элементов двусвязного списка и бинарного дерева совершенно одинакова, тем не менее это две разные структуры данных.
Потому, что в дереве выполняется требование достижимости + требование отсутствия циклов, а в списке — требования a.next.prev == a == a.prev.next.

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

Соответственно, некоторые структуры данных позволяют обойтись без блокировок при конкурентном выполнении некоторых алгоритмов. А некоторые — нет. В частности, при реализации стека в виде односвязного списка нетрудно сделать неблокирующими все алгоритмы, построив их на иммутабельности.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
http://rsdn.org/File/5743/rsdnaddict.GIF
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.