На собеседованиях часто спрашивают что такое deadlock. Затем может следовать вопрос а как его можно устранить, при этом желательно привести несколько примеров устранения различными способами.
На практике это обычно решается изменением архитектуры. Как можно устранить проблему либо при использовании дополнительных алгоритмов, либо особенностей языка, библиотек, операционной системы.
Здравствуйте, abc1234573, Вы писали:
A>На собеседованиях часто спрашивают что такое deadlock. Затем может следовать вопрос а как его можно устранить, при этом желательно привести несколько примеров устранения различными способами. A>На практике это обычно решается изменением архитектуры. Как можно устранить проблему либо при использовании дополнительных алгоритмов, либо особенностей языка, библиотек, операционной системы.
1. Упорядочиваем доступ к ресурсам.
2. При запросе лока не ресурс, указываем время ожидания и корректно обрабатываем таймауты.
3. Используем неблокирующие структуры данных.
Здравствуйте, avpavlov, Вы писали:
L>>3. Используем неблокирующие структуры данных.
A>Данные пассивны, они не могут быть блокирующими или нет, наверное имелись ввиду алгоритмы?
Здравствуйте, avpavlov, Вы писали:
L>>Я писал не про данные, а про структуры данных.
A>Оп-па, наверное тут какой-то нюанс, который всё меняет. Просвятишь?
Нет, не просвящу. Гугли либо по "неблокирующие структуры данных" (если хочешь на русском), либо по "lock-free data structures" (если хочешь много).
L>Нет, не просвящу. Гугли либо по "неблокирующие структуры данных" (если хочешь на русском), либо по "lock-free data structures" (если хочешь много).
Погуглил, и таки-да, появилось ощущение, что много кто взаимозаменяет понятия "неблокирующий алгоритм" и "неблокирующая структура данных", что лично мне представляется грустным.
Приведи мне пример "неблокирующей структуры данных" и посмотрим вместе, является она неблокирующей сама по себе или только при использовании неблокирующего алгоритма.
Здравствуйте, avpavlov, Вы писали:
A>Погуглил, и таки-да, появилось ощущение, что много кто взаимозаменяет понятия "неблокирующий алгоритм" и "неблокирующая структура данных", что лично мне представляется грустным.
A>Приведи мне пример "неблокирующей структуры данных" и посмотрим вместе, является она неблокирующей сама по себе или только при использовании неблокирующего алгоритма.
Здравствуйте, avpavlov, Вы писали:
A>Погуглил, и таки-да, появилось ощущение, что много кто взаимозаменяет понятия "неблокирующий алгоритм" и "неблокирующая структура данных", что лично мне представляется грустным.
Если с википедии то:
Структура данных — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. Структура данных часто является реализацией какого-либо абстрактного типа данных.
Не будет алгоритма обхода дерева без дерева. А если говорить о неблокирующих структурах — то и подавно, не может быть там какой-то абстракции, скорее пачка хитростей/соглашений, именно на уровне данных и алгоритма.
F> Не будет алгоритма обхода дерева без дерева. А если говорить о неблокирующих структурах — то и подавно, не может быть там какой-то абстракции, скорее пачка хитростей/соглашений, именно на уровне данных и алгоритма.
Но первичен в данном случае именно алгоритм, и структуру данных допиливают под него. Причём, если потом оставить только допиленную структуру и убрать алгоритм — разве структура останется "неблокирующей"?
F>> Не будет алгоритма обхода дерева без дерева. А если говорить о неблокирующих структурах — то и подавно, не может быть там какой-то абстракции, скорее пачка хитростей/соглашений, именно на уровне данных и алгоритма.
A>Но первичен в данном случае именно алгоритм, и структуру данных допиливают под него. Причём, если потом оставить только допиленную структуру и убрать алгоритм — разве структура останется "неблокирующей"?
У слова "структура данных" есть вполне определенный смысл, который тебе процитировали. Чего тут обсуждать?
L>А не высосаный из пальца, а реальный словарь (например, Dictionary из .Net) — это алгоритм или структура данных?
Я не понимаю, что ты пытаешься мне доказать? Что алгоритму нужна структура данных? Я с этим не спорю.
А вот ты похоже пытаешься оспорить, что структура без алгоритма ничего из себя не представляет.
Если взять Dictionary из .Net, выдернуть из него поля, где он хранит данные — останется это словарём? Нет, не останется. Получается словарь словарём делает алгоритм, а не структура данных.
L>>А не высосаный из пальца, а реальный словарь (например, Dictionary из .Net) — это алгоритм или структура данных?
A>Я не понимаю, что ты пытаешься мне доказать? Что алгоритму нужна структура данных? Я с этим не спорю.
Но тем не менее это не так. Алгоритму структура данных не нужна.
A>А вот ты похоже пытаешься оспорить, что структура без алгоритма ничего из себя не представляет.
Я не знаю, что такое "структура". Речь все еще о "структуре данных"?
A>Если взять Dictionary из .Net, выдернуть из него поля, где он хранит данные — останется это словарём? Нет, не останется.
Если взять Dictionary из .Net, выдернуть из него поля, то это не будет словарь из .Net.
Если не сложно, ответь на вопрос как он был изначально задан.
A>Получается словарь словарём делает алгоритм, а не структура данных.
Ага. А если из тебя все внутренности вырезать, то через пару минут ты не останешься. Выходит ты — это селезенка.
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.
Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers.
Data structures are used in almost every program or software system. Data structures provide a means to manage huge amounts of data efficiently, such as large databases and internet indexing services. Usually, efficient data structures are a key to designing efficient algorithms. Some formal design methods and programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design.
Никакого упоминания "набора функций". Более того, во втором выделении стуктуры и алгоритмы отделены друг от друга
L>Я не знаю, что такое "структура". Речь все еще о "структуре данных"?
Да
L>Если не сложно, ответь на вопрос как он был изначально задан.
Словарь — это алгоритм. Я отвечал уже на этот вопрос. Ты собираешься меня переспросить про каждую известную тебе имплементацию словаря?
L>Ага. А если из тебя все внутренности вырезать, то через пару минут ты не останешься. Выходит ты — это селезенка.
Это как раз твоя мысль. Если следовать моей мысли, то человека человеком делает не селезёнка и другие органы, а то, как они взаимодействуют друг с другом.
L>Если не сложно, ответь на вопрос как он был изначально задан.
Теперь моя очередь попросить тебя сделать то, что было запрошено изначально
Приведи мне пример "неблокирующей структуры данных" и посмотрим вместе, является она неблокирующей сама по себе или только при использовании неблокирующего алгоритма.
Здравствуйте, avpavlov, Вы писали:
A>Никакого упоминания "набора функций". Более того, во втором выделении стуктуры и алгоритмы отделены друг от друга
Ты похоже все еще не погуглил по предложенным словам? Последуй совету. Если останутся вопросы, можешь задать их тут или воспользоваться поиском по форуму, эта тема уже неоднократно поднималась.
Заниматься софистикой сегодня у меня как-то нет настроения. Удачи.
Здравствуйте, avpavlov, Вы писали:
L>>Если не сложно, ответь на вопрос как он был изначально задан.
A>Словарь — это алгоритм. Я отвечал уже на этот вопрос. Ты собираешься меня переспросить про каждую известную тебе имплементацию словаря?
Вопрос был немного другим:
реальный словарь (например, Dictionary из .Net) — это алгоритм или структура данных?
Если не сложно, ответь именно про "Dictionary из .Net".
L>>Ага. А если из тебя все внутренности вырезать, то через пару минут ты не останешься. Выходит ты — это селезенка.
A>Это как раз твоя мысль. Если следовать моей мысли, то человека человеком делает не селезёнка и другие органы, а то, как они взаимодействуют друг с другом.
Человека человеком делает как селезенка, так и взаимодействие оной со всем остальным. А "структура данных" — это как внутренняя организация данных, так и алгоритмы роаботы с ними.
Здравствуйте, avpavlov, Вы писали:
A>Теперь моя очередь попросить тебя сделать то, что было запрошено изначально
A>
A>Приведи мне пример "неблокирующей структуры данных" и посмотрим вместе, является она неблокирующей сама по себе или только при использовании неблокирующего алгоритма.
Ты ошибаешься в определении понятия "структуры данных". В чем твоя ошибка тебе уже сказали. Как найти информацию тебе тоже сказали.
Извини, но дальше — сам.
L>>Ты ошибаешься в определении понятия "структуры данных". В чем твоя ошибка тебе уже сказали. Как найти информацию тебе тоже сказали.
A>Я тебе привёл другое определение, но ты его проигнорировал, как менее удобное для тебя
ты его просто некорректно трактовал.
например, возьми то же бинарное дерево. если для тебя это просто способ организации данных в памяти, то никто мне не помешает вставить в произвольное место дерева данные, которые там быть не должны, а то и вовсе зациклить его. следовательно, без правильного кода, работающего с этим деревом, дерево не будет выполнять своей функции быстрого поиска. эти два понятия (организация данных и способ работы с ними) просто неотъемлемы.
в этом ключе и надо трактовать "структура данных", о чем я писал.
Здравствуйте, avpavlov, Вы писали:
L>>Если не сложно, ответь именно про "Dictionary из .Net".
A>Отвечаю в последний раз — это алгоритм.
Неужели? Ну значит мне снова наврали, пойду выпью чаю с горя.
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number).
L>Неужели? Ну значит мне снова наврали, пойду выпью чаю с горя.
L>
L>In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number).
Ллойд, а ты забавный, ей богу. Пинал меня "ответь про .Нет, ответь про .Нет" и как только я ответил про .Нет, сразу перевёл тему в другую плоскость. Если ты намеренно съузил тему до словаря из .Нет, я тебя прошу приводить цитаты из МСДН, иначе ты просто демагог.
L> эти два понятия (организация данных и способ работы с ними) просто неотъемлемы. L>в этом ключе и надо трактовать "структура данных", о чем я писал.
А я считаю, что есть смысл проводить между ними черту, о чем тоже писал. Потому что если эту черту не провести, то возникает двусмысленность, из-за невозможности точно сказать, о чём в конкретный момент времени идёт речь — "о способе хранения" или "о способе хранения и манипулировании".
L>>Неужели? Ну значит мне снова наврали, пойду выпью чаю с горя.
L>>
L>>In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number).
A>Ллойд, а ты забавный, ей богу. Пинал меня "ответь про .Нет, ответь про .Нет" и как только я ответил про .Нет, сразу перевёл тему в другую плоскость.
Да нет, плоскость все та же самая. Dictionary из .Net-а — частный случай хэш-таблицы.
A>Если ты намеренно съузил тему до словаря из .Нет, я тебя прошу приводить цитаты из МСДН,
Не сузил, а спустил на землю. Занимаясь философией можно много до чего договориться, а вот раельность отрезвляет.
A>иначе ты просто демагог.
Первый признак демагога — обвинение собеседника в демагогии.
Здравствуйте, avpavlov, Вы писали:
L>> эти два понятия (организация данных и способ работы с ними) просто неотъемлемы. L>>в этом ключе и надо трактовать "структура данных", о чем я писал.
A>А я считаю, что есть смысл проводить между ними черту, о чем тоже писал. Потому что если эту черту не провести, то возникает двусмысленность, из-за невозможности точно сказать, о чём в конкретный момент времени идёт речь — "о способе хранения" или "о способе хранения и манипулировании".
Я так не считаю. "Структура данных" — устоявшийся термин и тракторать его по-своему нежелательно.
Здравствуйте, abc1234573, Вы писали:
A>На собеседованиях часто спрашивают что такое deadlock. Затем может следовать вопрос а как его можно устранить, при этом желательно привести несколько примеров устранения различными способами. A>На практике это обычно решается изменением архитектуры. Как можно устранить проблему либо при использовании дополнительных алгоритмов, либо особенностей языка, библиотек, операционной системы.
Deadlock, т.е. взаимная блокировка — чисто архитектурная проблема и решать её нужно на уровне архитектуры. Основной алгоритм — определение неделимых частей кода — транзакций. Для классического примера с википедии при первом же обнаружении deadlock'а следовало бы убрать независимый захват ресурсов A и B, и добавить захват ресурсов A + B. Возможен другой подход: если в какой то части кода захвачено монопольно более одного ресурса, то процесс захвата и освобождения должен производиться по принципу FILO, т.е. в том же случае с вики "второй процесс" должен ждать освобождения A, даже если B свободен.
Погуглил, и таки-да, появилось ощущение, что много кто взаимозаменяет понятия "неблокирующий алгоритм" и "неблокирующая структура данных", что лично мне представляется грустным.
...
Приведи мне пример "неблокирующей структуры данных" и посмотрим вместе, является она неблокирующей сама по себе или только при использовании неблокирующего алгоритма.
Изначально уже ясно, что самоцель достаточно странная. Алгоритм-структура...
Но по теме:
Словарь (ассоциативный массив) — это абстрактный тип данных (АТД, abstract data type). Стэк — АТД, хотя он же и структура данных. Их пруд пруди.
Эти самые АТД, определяют операции над собой (что логично, собственно как и все типы данных определяют операции над собой).
Таким образом эти операции иногда просто называют интерфейсом.
Хэш-таблица — это структура данных реализующая интерфейс словаря. Ничего не мешает эти же данные хранить в обычном списке выставив наружу IDictionary, ну разве что только скорость.
Таким образом структура данных определяет способ упаковки данных и методы работы над ними (алгоритмы обработки этих данных, их сложность).
Но алгоритм, в прошлом предложении — стоит не забывать, что это в том числе и жесткий контракт, особенно если вести речь о неблокирующих структурах данных. Речь изначально и шла, что невозможно отделить эти методы от самой структуры данных. Поэтому само по себе понятие неблокирующий алгоритм не особо имеет смысл, в данном контексте. Ещё примеров — пожалуйста — XOR linked list — врядли получение предыдущего/следующего элемента вне этой структуры имеет смысл. И точно так же эти методы не применимы к классическому дву-связному связному списку.
On 16.08.2011 18:21, abc1234573 wrote:
> На собеседованиях часто спрашивают что такое deadlock. Затем может следовать > вопрос а как его можно устранить, при этом желательно привести несколько > примеров устранения различными способами.
Устранить -- это разрешить ситуацию дедлока в конкретном случае, или сделать
так, чтобы её не возникало никогда в системе ?
> На практике это обычно решается изменением архитектуры. Как можно устранить
Здравствуйте, avpavlov, Вы писали:
L>>Если не сложно, ответь именно про "Dictionary из .Net".
A>Отвечаю в последний раз — это алгоритм.
Это не алгоритм и не структура данных. Это (абстрактный) тип данных. Применительно к Dictionary структурой данных будут его внутренние поля в которых находятся ключи и значения, а алгоритмами — набор операций, которые можно осуществлять над словарем (добавление значение, поиск значения, перечисление значений и ключей).
Здравствуйте, MasterZiv, Вы писали:
MZ>On 16.08.2011 18:21, abc1234573 wrote:
>> На собеседованиях часто спрашивают что такое deadlock. Затем может следовать >> вопрос а как его можно устранить, при этом желательно привести несколько >> примеров устранения различными способами.
MZ>Устранить -- это разрешить ситуацию дедлока в конкретном случае, или сделать MZ>так, чтобы её не возникало никогда в системе ?
в конкретном случае сделать так чтобы участок кода вызывающий дедлок либо его не вызывал либо дополнительно обрабатывался чтобы исключиь такую ситуацию
>> На практике это обычно решается изменением архитектуры. Как можно устранить
MZ>Да не только.
вот как раз интересно как это сделать без изменения архитектуры
Здравствуйте, abc1234573, Вы писали:
A>На собеседованиях часто спрашивают что такое deadlock.
Обычно это расшифровывается как бесконечное ожидание на объекте синхронизации, который больше нельзя переключить в свободное состояние.
A>Затем может следовать вопрос а как его можно устранить, при этом желательно привести несколько примеров устранения различными способами.
Примеров уйма, от забыл освободить, до нарушения порядка захвата-освобождения (cross deadlock). При этом один из двух мютексов с лекгостью фейла может быть системным.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
On 17.08.2011 15:51, abc1234573 wrote:
> MZ>Устранить -- это разрешить ситуацию дедлока в конкретном случае, или сделать > MZ>так, чтобы её не возникало никогда в системе ? > > в конкретном случае сделать так чтобы участок кода вызывающий дедлок либо его не > вызывал либо дополнительно обрабатывался чтобы исключиь такую ситуацию > >> > На практике это обычно решается изменением архитектуры. Как можно устранить > > MZ>Да не только. > > вот как раз интересно как это сделать без изменения архитектуры
Ну что такое "изменение архитектуры" не очень понятно, ну да ладно.
принципиально есть следующие способы разрешения дедлоков:
-- отказ от многопользовательской и/или многозадачной работы
-- сериализация доступа к блокам кода, в которых возникает дедлок (в общем-то
можно сказать локальный отказ от многозадачности в рамках куска кода).
-- установка общего глобального в приложении порядка захвата синхронизирующих
объектов.
Это из средств предотвращения дедлоков.
А средства выхода из ситуации дедлока пожалуй только два:
-- таймауты (дешёвый)
-- анализ графа зависимостей локов для выявления циклов. (дорогой).
Здравствуйте, avpavlov, Вы писали:
A>А я считаю, что есть смысл проводить между ними черту, о чем тоже писал. Потому что если эту черту не провести, то возникает двусмысленность, из-за невозможности точно сказать, о чём в конкретный момент времени идёт речь — "о способе хранения" или "о способе хранения и манипулировании".
Помимо способа хранения, структура данных также определяет некоторые инварианты. В частности, "структура" элементов двусвязного списка и бинарного дерева совершенно одинакова, тем не менее это две разные структуры данных.
Потому, что в дереве выполняется требование достижимости + требование отсутствия циклов, а в списке — требования a.next.prev == a == a.prev.next.
При таком определении становится понятно, что структура данных автоматически запрещает некоторые "алгоритмы" (в частности, те, которые нарушают инварианты) и делает возможными другие (например, бинарный поиск).
Соответственно, некоторые структуры данных позволяют обойтись без блокировок при конкурентном выполнении некоторых алгоритмов. А некоторые — нет. В частности, при реализации стека в виде односвязного списка нетрудно сделать неблокирующими все алгоритмы, построив их на иммутабельности.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
