deadlock. вопросы
От: abc1234573  
Дата: 16.08.11 14:21
Оценка:
На собеседованиях часто спрашивают что такое deadlock. Затем может следовать вопрос а как его можно устранить, при этом желательно привести несколько примеров устранения различными способами.
На практике это обычно решается изменением архитектуры. Как можно устранить проблему либо при использовании дополнительных алгоритмов, либо особенностей языка, библиотек, операционной системы.
Re: deadlock. вопросы
От: Lloyd Россия  
Дата: 16.08.11 14:25
Оценка: +1
Здравствуйте, abc1234573, Вы писали:

A>На собеседованиях часто спрашивают что такое deadlock. Затем может следовать вопрос а как его можно устранить, при этом желательно привести несколько примеров устранения различными способами.

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

1. Упорядочиваем доступ к ресурсам.
2. При запросе лока не ресурс, указываем время ожидания и корректно обрабатываем таймауты.
3. Используем неблокирующие структуры данных.
Re[2]: deadlock. вопросы
От: avpavlov  
Дата: 16.08.11 14:38
Оценка:
L>3. Используем неблокирующие структуры данных.

Данные пассивны, они не могут быть блокирующими или нет, наверное имелись ввиду алгоритмы?

А вот данные могут быть иммутабл, тогда к ним не надо синхронизировать доступ и это тоже способ борьбы с дедлоками (наверное).
Re[3]: deadlock. вопросы
От: Lloyd Россия  
Дата: 16.08.11 14:48
Оценка:
Здравствуйте, avpavlov, Вы писали:

L>>3. Используем неблокирующие структуры данных.


A>Данные пассивны, они не могут быть блокирующими или нет, наверное имелись ввиду алгоритмы?


Я писал не про данные, а про структуры данных.
Re: deadlock. вопросы
От: Sharov Россия  
Дата: 16.08.11 14:49
Оценка:
Здравствуйте, abc1234573, Вы писали:

http://en.wikipedia.org/wiki/Deadlock#Necessary_conditions
Кодом людям нужно помогать!
Re[4]: deadlock. вопросы
От: avpavlov  
Дата: 16.08.11 14:55
Оценка:
L>Я писал не про данные, а про структуры данных.

Оп-па, наверное тут какой-то нюанс, который всё меняет. Просвятишь?
й
Re[5]: deadlock. вопросы
От: Lloyd Россия  
Дата: 16.08.11 15:00
Оценка:
Здравствуйте, avpavlov, Вы писали:

L>>Я писал не про данные, а про структуры данных.


A>Оп-па, наверное тут какой-то нюанс, который всё меняет. Просвятишь?


Нет, не просвящу. Гугли либо по "неблокирующие структуры данных" (если хочешь на русском), либо по "lock-free data structures" (если хочешь много).
Re[6]: deadlock. вопросы
От: avpavlov  
Дата: 16.08.11 15:13
Оценка:
L>Нет, не просвящу. Гугли либо по "неблокирующие структуры данных" (если хочешь на русском), либо по "lock-free data structures" (если хочешь много).

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

Приведи мне пример "неблокирующей структуры данных" и посмотрим вместе, является она неблокирующей сама по себе или только при использовании неблокирующего алгоритма.
Re[7]: deadlock. вопросы
От: Lloyd Россия  
Дата: 16.08.11 15:17
Оценка:
Здравствуйте, avpavlov, Вы писали:

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


A>Приведи мне пример "неблокирующей структуры данных" и посмотрим вместе, является она неблокирующей сама по себе или только при использовании неблокирующего алгоритма.


Словарь — это алгоритм или структура данных?
Re[7]: deadlock. вопросы
От: fddima  
Дата: 16.08.11 15:20
Оценка:
Здравствуйте, avpavlov, Вы писали:

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


Если с википедии то:

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


Не будет алгоритма обхода дерева без дерева. А если говорить о неблокирующих структурах — то и подавно, не может быть там какой-то абстракции, скорее пачка хитростей/соглашений, именно на уровне данных и алгоритма.
Re[8]: deadlock. вопросы
От: avpavlov  
Дата: 16.08.11 15:29
Оценка: -4
L>Словарь — это алгоритм или структура данных?

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


Object get(Object key) {
 return key.hashCode();
}


Надеюсь не будешь спорить, что метод выше это реализация простейшего словаря? Причём никакими структурами данных тут и не пахнет.
Re[9]: deadlock. вопросы
От: Lloyd Россия  
Дата: 16.08.11 15:31
Оценка: +1
Здравствуйте, avpavlov, Вы писали:

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



A>
A>Object get(Object key) {
A> return key.hashCode();
A>}
A>


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


А не высосаный из пальца, а реальный словарь (например, Dictionary из .Net) — это алгоритм или структура данных?
Re[8]: deadlock. вопросы
От: avpavlov  
Дата: 16.08.11 15:33
Оценка:
F> Не будет алгоритма обхода дерева без дерева. А если говорить о неблокирующих структурах — то и подавно, не может быть там какой-то абстракции, скорее пачка хитростей/соглашений, именно на уровне данных и алгоритма.

Но первичен в данном случае именно алгоритм, и структуру данных допиливают под него. Причём, если потом оставить только допиленную структуру и убрать алгоритм — разве структура останется "неблокирующей"?
Re[9]: deadlock. вопросы
От: Lloyd Россия  
Дата: 16.08.11 15:36
Оценка:
Здравствуйте, avpavlov, Вы писали:


F>> Не будет алгоритма обхода дерева без дерева. А если говорить о неблокирующих структурах — то и подавно, не может быть там какой-то абстракции, скорее пачка хитростей/соглашений, именно на уровне данных и алгоритма.


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


У слова "структура данных" есть вполне определенный смысл, который тебе процитировали. Чего тут обсуждать?
Re[10]: deadlock. вопросы
От: avpavlov  
Дата: 16.08.11 15:37
Оценка: -1
L>А не высосаный из пальца, а реальный словарь (например, Dictionary из .Net) — это алгоритм или структура данных?

Я не понимаю, что ты пытаешься мне доказать? Что алгоритму нужна структура данных? Я с этим не спорю.

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

Если взять Dictionary из .Net, выдернуть из него поля, где он хранит данные — останется это словарём? Нет, не останется. Получается словарь словарём делает алгоритм, а не структура данных.
Re[11]: deadlock. вопросы
От: Lloyd Россия  
Дата: 16.08.11 15:42
Оценка: +1
Здравствуйте, avpavlov, Вы писали:


L>>А не высосаный из пальца, а реальный словарь (например, Dictionary из .Net) — это алгоритм или структура данных?


A>Я не понимаю, что ты пытаешься мне доказать? Что алгоритму нужна структура данных? Я с этим не спорю.


Но тем не менее это не так. Алгоритму структура данных не нужна.

A>А вот ты похоже пытаешься оспорить, что структура без алгоритма ничего из себя не представляет.


Я не знаю, что такое "структура". Речь все еще о "структуре данных"?

A>Если взять Dictionary из .Net, выдернуть из него поля, где он хранит данные — останется это словарём? Нет, не останется.


Если взять Dictionary из .Net, выдернуть из него поля, то это не будет словарь из .Net.
Если не сложно, ответь на вопрос как он был изначально задан.

A>Получается словарь словарём делает алгоритм, а не структура данных.


Ага. А если из тебя все внутренности вырезать, то через пару минут ты не останешься. Выходит ты — это селезенка.
Re[10]: deadlock. вопросы
От: avpavlov  
Дата: 16.08.11 15:43
Оценка:
L>У слова "структура данных" есть вполне определенный смысл, который тебе процитировали. Чего тут обсуждать?

Ты хочешь цитат? Их есть у меня!

http://en.wikipedia.org/wiki/Data_structure

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.


Никакого упоминания "набора функций". Более того, во втором выделении стуктуры и алгоритмы отделены друг от друга
Re[12]: deadlock. вопросы
От: avpavlov  
Дата: 16.08.11 15:46
Оценка: -3
L>Я не знаю, что такое "структура". Речь все еще о "структуре данных"?

Да

L>Если не сложно, ответь на вопрос как он был изначально задан.


Словарь — это алгоритм. Я отвечал уже на этот вопрос. Ты собираешься меня переспросить про каждую известную тебе имплементацию словаря?

L>Ага. А если из тебя все внутренности вырезать, то через пару минут ты не останешься. Выходит ты — это селезенка.


Это как раз твоя мысль. Если следовать моей мысли, то человека человеком делает не селезёнка и другие органы, а то, как они взаимодействуют друг с другом.
Re[12]: deadlock. вопросы
От: avpavlov  
Дата: 16.08.11 15:48
Оценка:
L>Если не сложно, ответь на вопрос как он был изначально задан.

Теперь моя очередь попросить тебя сделать то, что было запрошено изначально

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

Re[11]: deadlock. вопросы
От: Lloyd Россия  
Дата: 16.08.11 15:50
Оценка:
Здравствуйте, avpavlov, Вы писали:

A>Никакого упоминания "набора функций". Более того, во втором выделении стуктуры и алгоритмы отделены друг от друга


Ты похоже все еще не погуглил по предложенным словам? Последуй совету. Если останутся вопросы, можешь задать их тут или воспользоваться поиском по форуму, эта тема уже неоднократно поднималась.

Заниматься софистикой сегодня у меня как-то нет настроения. Удачи.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.