Здравствуйте, C.A.B, Вы писали:
CAB>Это была-бы замечательная идея если бы я дезайнил ЯП для математиков, для их абстрактного мира. Но в отличии от, люди решающие конкретные проблемы, работают с конкретными объектами материального мира, и у всех этих объектов есть состояние.
У математических объектов тоже есть своего рода состояние. Например, в множество можно добавлять элементы. Но у математических объектов нет носителя, следовательно, мы можем не заморачиваться с оптимизацией, как в одном носителе держать в разное время разные объекты и их не перепутать. В результате алгоритм получается проще и прозрачней, а также максимально параллельным — нет искуственных зависимостей по использованию носителей, только неизбежные зависимости по данным. И будучи максимально параллельным, математически правильный алгоритм свободен от дедлоков по определению. Далее, при реализации алгоритма, нам возможно придется оптимизировать использование носителя (памяти), но это надо делать после разработки математической формы алгоритма, сохраняя его параллельность и корректность. Недаром говорят, что преждевременная оптимизация — корень всех бед.
CAB>PS: Думаю гораздо важнее хорошее соотношение затраты/польза на/от программы, нежели её "правильность".
Ну-ну. Какая вообще польза от неправильной программы?
rfq>У математических объектов тоже есть своего рода состояние. Например, в множество можно добавлять элементы. Но у математических объектов нет носителя, следовательно, мы можем не заморачиваться с оптимизацией, как в одном носителе держать в разное время разные объекты и их не перепутать.
Проблема синхронизации не в носителе, и даже не в состоянии(если у вас всего один поток — нет проблем), проблема в том что два или более потока исполнения могут влиять на работу _друг_друга_. Через состояние, через посылку сообщений, не важно. Думаю кстати, для математических объектов это тоже справедливо, например вы математик, пока вы работаете самостоятельно всё просто, но когда вы начинаете работать в группе математиков над некоторой общей задачей, сразу начинаются проблемы с "синхронизацией". rfq>В результате алгоритм получается проще и прозрачней, а также максимально параллельным — нет искуственных зависимостей по использованию носителей, только неизбежные зависимости по данным. И будучи максимально параллельным, математически правильный алгоритм свободен от дедлоков по определению.
Очень и очень спорное утверждение. Попробуйте решить таким способом какую ни будь практическую задачу для двух+ потоков, например клиент-сервер или обработку массива данных. CAB>>PS: Думаю гораздо важнее хорошее соотношение затраты/польза на/от программы, нежели её "правильность". rfq>Ну-ну. Какая вообще польза от неправильной программы?
Польза есть ни тогда когда программа "правильная", а тогда когда программа делает "то что нужно", даже если она делает это "неправильным" способом и написана "неправильно". Но это не существенно, просто вы выбрали не удачный термин или я его неправильно понял.
Между тем,что я думаю,тем,что я хочу сказать,тем,что я,как мне кажется,говорю,и тем,что вы хотите услышать,тем,что как вам кажется,вы слышите,тем,что вы понимаете,стоит десять вариантов возникновения непонимания.Но всё-таки давайте попробуем...(Э.Уэллс)
M>>Это — описание мьютекса на общих данных. Именно это и есть и будет дедлоком, когда читать/записывать будет много потоков сразу, а какая-то из операций записи зависнет. CAB>Такое конечно возможно, но ИМХО, проблемы внутри потока (навроде while true =>) к синхронизации потоков имеют слабое отношение, потому в этом контексте не вижу особого смысла их рассматривать. Да и "виновника торжества" легко будет найти при отладке. Но допустим. Какие ещё причины дедлоков ты видиш?
У тебя же проблемы не внутри потока Е тебя ест толпа функций, каждая из окторых — отдельный поток, и общие данные, к которым они все рвутся.
CAB>>>По большому счёту это оно и есть, но атомарной операцией является вся функция-писатель. Функции читатели вообще не блокируются если не выполняется запись. M>>Нет. Это оно не есть. Потому что читатели блокируются, пока идет запись. CAB>Если читатель не блокируется на время записи и размер данных превышает размер машинного слова(запись и чтение которого атомарно), то он рискует получить кашу в виде полуобновлённых данных.
Эээээ. Для простых типов данных это может быть и так, для сложных (массивы/списки, например) это далеко не так.
CAB>Можно буферизировать записываемые данные т.е. не лочить их на время выполнения и обновлять по завершении функции-писателя. Но для этого нужны дополнительные ресурсы. M>>Это — дедлок только в случае, если операция send синхронная. И это легко разруливается штатными средствами Erlang'а CAB>Не понял. Суть кода выше: актор A отправляет сообщение "a" актору B, тот в ответ отправляет сообщение "b" актору A, который в ответ отправляет сообщение "a" и так далее по кругу. Как от такого спасёт отдельный процесс?
Если это — просто сообщения, то:
— если они асинхронные, то ничего страшного не происходит. Ну шлют они друг другу сообщения — и? Так половина систем с потоками работает.
— если они синхронные, они дедлочатся и ждут ответа друг друга, то это на раз два переписывается в асинхронном стиле
В целом ситуация А вызвало Б, которое сразу вызвало А, которое сразу вызвало Б ортогональна потокам.
Здравствуйте, rfq, Вы писали:
rfq>Здравствуйте, C.A.B, Вы писали: CAB>> Когда появляются общие переменные всё становится несколько сложнее
rfq>Вы замечали, что в математике нет понятия изменяемой переменной, как она используется в программировании?
В математике есть всё. В матфизических разделах, изущающих движение, есть понятие пути в фазовом прстранстве, например.
В теории алгоритмов есть понятие автомата, у котрого тоже есть изменяемое внутреннее состояние. То что мы формализуем изменяемые объекты с помощью функций -- это
технический приём, поскольку современная математика основана на теории множеств. Содержательно же, любой математик движущуюся точку в фазовом пространстве понимает именно как изменяемый объект.
Здравствуйте, C.A.B, Вы писали:
M>>Это — описание мьютекса на общих данных. Именно это и есть и будет дедлоком, когда читать/записывать будет много потоков сразу, а какая-то из операций записи зависнет. CAB>Такое конечно возможно, но ИМХО, проблемы внутри потока (навроде while true =>) к синхронизации потоков имеют слабое отношение, потому в этом контексте не вижу особого смысла их рассматривать. Да и "виновника торжества" легко будет найти при отладке. Но допустим. Какие ещё причины дедлоков ты видиш?
Во-первых, не блокировать читателей вы не сможете. Потому что иначе понятие "атомарности записи" у вас исчезает.
Поясню на пальцах: вот у вас есть "писатель", который хочет атомарно (т.е. согласованно) поменять две переменные.
Например, переложить Z из X в Y:
X-=Z; // 1
Y+=Z; // 2
Очевидно, что такой писатель сохраняет инвариант X+Y, что и является намерением программиста.
Читатель, который у вас "не блокируется", рискует прочитать данные ровно между операциями 1 и 2, и увидеть неконсистентное состояние. Поэтому вам придётся либо блокировать читателей, либо отказаться от понятия атомарности.
CAB>Можно буферизировать записываемые данные т.е. не лочить их на время выполнения и обновлять по завершении функции-писателя. Но для этого нужны дополнительные ресурсы.
Вы пытаетесь изобрести изоляцию транзакций. Почитайте Бернстайна, чтобы вам стало понятно, о чём вообще идёт речь, и какие методики изобретены к настоящему моменту для СУБД. Вот прямо сейчас вы изобрели т.н. "блокировочник", и судорожно пытаетесь добавить в него черты "версионника".
Так, чисто для справки: в 1970х некто Дийкстра показал, что любые стратегии работы с разделяемыми данными приводят к возможности дедлока. Для решения этой маленькой частной проблемки он предложил отказаться от разделяемых данных, а взамен — концепцию "гармонично взаимодействующих процессов". Именно они и реализованы в Эрланге.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, C.A.B, Вы писали:
CAB>Проблема синхронизации не в носителе, и даже не в состоянии(если у вас всего один поток — нет проблем), проблема в том что два или более потока исполнения могут влиять на работу _друг_друга_. Через состояние, через посылку сообщений, не важно.
Нет. Само понятие "потока исполнения" опирается на понятие "состояния", поэтому проблема синхронизации существует только при наличии состояния. Просто ваша ментальная модель построена на Тьюринговском формализме. А если бы вы начинали с частично-рекурсивных функций Чёрча, то для вас концепция потока исполнения была бы чужда.
CAB>Очень и очень спорное утверждение. Попробуйте решить таким способом какую ни будь практическую задачу для двух+ потоков, например клиент-сервер или обработку массива данных.
Потоки — это не задача. Потоки — это решение. Вот, например, массив данных можно обработать в Excel. Там вы можете написать довольно сложную программу, при этом ни разу не воспользовавшись понятием "поток". Подробности того, сколько нативных потоков выделять для вычисления, оставлены инфраструктуре.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, C.A.B, Вы писали:
CAB>т.е. каждый вызов выполняется в новом потоке.
Каждый поток создает свой стек потока равный 1мб.
Предположим создается простейшее серверное приложение из трех функций.
К приложению подключаются 3 тысячи клиентов.
Расход памяти — 9гб.
Это слишком жирно для трех функций, вам не кажется?
Или я что-то не понимаю?
CAB>>Такое конечно возможно, но ИМХО, проблемы внутри потока (навроде while true =>) к синхронизации потоков имеют слабое отношение, потому в этом контексте не вижу особого смысла их рассматривать. Да и "виновника торжества" легко будет найти при отладке. Но допустим. Какие ещё причины дедлоков ты видиш? M>У тебя же проблемы не внутри потока Е тебя ест толпа функций, каждая из окторых — отдельный поток, и общие данные, к которым они все рвутся.
И один зависший поток не даёт им "прорваться", проблема ведь не в том что они рвутся в том что поток повис. CAB>>Если читатель не блокируется на время записи и размер данных превышает размер машинного слова(запись и чтение которого атомарно), то он рискует получить кашу в виде полуобновлённых данных. M>Эээээ. Для простых типов данных это может быть и так, для сложных (массивы/списки, например) это далеко не так.
Почему? Если массив/списки мутабельны для них это то-же справедливо. M>- если они асинхронные, то ничего страшного не происходит. Ну шлют они друг другу сообщения — и? Так половина систем с потоками работает.
И загружают на 100% два процессора. Хотя конечно это легче обнаружить и процессы не перестают реагировать на другие сообщения.
Между тем,что я думаю,тем,что я хочу сказать,тем,что я,как мне кажется,говорю,и тем,что вы хотите услышать,тем,что как вам кажется,вы слышите,тем,что вы понимаете,стоит десять вариантов возникновения непонимания.Но всё-таки давайте попробуем...(Э.Уэллс)
Здравствуйте, Sinclair, Вы писали: CAB>>Проблема синхронизации не в носителе, и даже не в состоянии(если у вас всего один поток — нет проблем), проблема в том что два или более потока исполнения могут влиять на работу _друг_друга_. Через состояние, через посылку сообщений, не важно. S>Нет. Само понятие "потока исполнения" опирается на понятие "состояния", поэтому проблема синхронизации существует только при наличии состояния.
//Поток A
...
wait_notify()
notify(B)
...
//Пoток B
...
wait_notify()
notify(A)
...
S>Просто ваша ментальная модель построена на Тьюринговском формализме. А если бы вы начинали с частично-рекурсивных функций Чёрча, то для вас концепция потока исполнения была бы чужда.
Т.е. нет потоков исполнения — нет проблемы синхронизации потоков исполнения? CAB>>Очень и очень спорное утверждение. Попробуйте решить таким способом какую ни будь практическую задачу для* двух+ потоков, например клиент-сервер или обработку массива данных. S>Потоки — это не задача. Потоки — это решение.
* с помощью
Между тем,что я думаю,тем,что я хочу сказать,тем,что я,как мне кажется,говорю,и тем,что вы хотите услышать,тем,что как вам кажется,вы слышите,тем,что вы понимаете,стоит десять вариантов возникновения непонимания.Но всё-таки давайте попробуем...(Э.Уэллс)
Здравствуйте, C.A.B, Вы писали: S>>Нет. Само понятие "потока исполнения" опирается на понятие "состояния", поэтому проблема синхронизации существует только при наличии состояния. CAB>
CAB>
Ну и к чему вы это привели? У вас есть какой-то вопрос? Задайте его, не стесняйтесь. Вы только сначала подумайте над тем, что вы называете термином "поток". Если будут сложности — посмотрите на какую-нибудь платформенно-специфичную реализацию, например x86, JVM, или CLR.
S>>Просто ваша ментальная модель построена на Тьюринговском формализме. А если бы вы начинали с частично-рекурсивных функций Чёрча, то для вас концепция потока исполнения была бы чужда. CAB>Т.е. нет потоков исполнения — нет проблемы синхронизации потоков исполнения? CAB>>>Очень и очень спорное утверждение. Попробуйте решить таким способом какую ни будь практическую задачу для* двух+ потоков, например клиент-сервер или обработку массива данных. S>>Потоки — это не задача. Потоки — это решение. CAB>* с помощью
Вы странный. Вам говорят: в чистом ФП потоков нет. А вы просите решение на ФП с использованием потоков.
Вот вам простая задача на обработку массива данных:
1. Массив устроен как набор пар (таймстэмп, значение с плавающей запятой):
(2013-05-06 01:00:00.523, 1.0)
(2013-05-06 01:00:01.007, 1.1)
...
2. Массив уже отсортирован по возрастанию timestamp
3. Рассчитайте running average значения по пяти отсчётам
Реализуйте её при помоши MS Excel. А теперь попробуйте притулить в ваше решение потоки.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
CAB>>>Такое конечно возможно, но ИМХО, проблемы внутри потока (навроде while true =>) к синхронизации потоков имеют слабое отношение, потому в этом контексте не вижу особого смысла их рассматривать. Да и "виновника торжества" легко будет найти при отладке. Но допустим. Какие ещё причины дедлоков ты видиш? M>>У тебя же проблемы не внутри потока Е тебя ест толпа функций, каждая из окторых — отдельный поток, и общие данные, к которым они все рвутся. CAB>И один зависший поток не даёт им "прорваться", проблема ведь не в том что они рвутся в том что поток повис.
Я об этом и говорил еще четыре сообщения тому назад
CAB>>>Если читатель не блокируется на время записи и размер данных превышает размер машинного слова(запись и чтение которого атомарно), то он рискует получить кашу в виде полуобновлённых данных. M>>Эээээ. Для простых типов данных это может быть и так, для сложных (массивы/списки, например) это далеко не так. CAB>Почему? Если массив/списки мутабельны для них это то-же справедливо.
Потому что чтение далеко не всегда идет из того же места, где производится изменение
M>>- если они асинхронные, то ничего страшного не происходит. Ну шлют они друг другу сообщения — и? Так половина систем с потоками работает. CAB>И загружают на 100% два процессора.
Возможно, но тестировть лень
CAB>Хотя конечно это легче обнаружить и процессы не перестают реагировать на другие сообщения.
S>Ну и к чему вы это привели? У вас есть какой-то вопрос? Задайте его, не стесняйтесь.
Ну как бы состояния нет а дедлок есть. S>Вы только сначала подумайте над тем, что вы называете термином "поток". Если будут сложности — посмотрите на какую-нибудь платформенно-специфичную реализацию, например x86, JVM, или CLR.
Термином "поток" я здесь называю поток выполнения инструкций(например операторов ЯП), безотносительно к реализации. S>Вы странный. Вам говорят: в чистом ФП потоков нет. А вы просите решение на ФП с использованием потоков.
Ok, обобщим: Допустим у нас есть две активные сущности(например клиент и сервер), я прошу решить задачу их взаимодействия чтобы "максимально параллельным, математически правильный алгоритм свободен от дедлоков по определению
", без потоков, на ФП — не важно. S>3. Рассчитайте running average значения по пяти отсчётам S>Реализуйте её при помоши MS Excel. А теперь попробуйте притулить в ваше решение потоки.
Допустим потоки там не нужны. Но меня больше интересует
вопрос: как это распаралеллить(чтоб ускорить вычисление)?
Между тем,что я думаю,тем,что я хочу сказать,тем,что я,как мне кажется,говорю,и тем,что вы хотите услышать,тем,что как вам кажется,вы слышите,тем,что вы понимаете,стоит десять вариантов возникновения непонимания.Но всё-таки давайте попробуем...(Э.Уэллс)
CAB>>>>Если читатель не блокируется на время записи и размер данных превышает размер машинного слова(запись и чтение которого атомарно), то он рискует получить кашу в виде полуобновлённых данных. M>>>Эээээ. Для простых типов данных это может быть и так, для сложных (массивы/списки, например) это далеко не так. CAB>>Почему? Если массив/списки мутабельны для них это то-же справедливо. M>Потому что чтение далеко не всегда идет из того же места, где производится изменение
Тогда веть придётся синхронизировать не только доступ ко всему массиву, но и к каждому элементу по отдельности.
Между тем,что я думаю,тем,что я хочу сказать,тем,что я,как мне кажется,говорю,и тем,что вы хотите услышать,тем,что как вам кажется,вы слышите,тем,что вы понимаете,стоит десять вариантов возникновения непонимания.Но всё-таки давайте попробуем...(Э.Уэллс)
Здравствуйте, -n1l-, Вы писали: N>Расход памяти — 9гб. N>Это слишком жирно для трех функций, вам не кажется? N>Или я что-то не понимаю?
Не нужно создать по одному системному потоку на вызов, достаточно создать пул потоков(например по число физических процессоров), откуда системные потоки будут "браться" по необходимости. Так же не нужно выполнять каждую функцию в отдельном потоке, те из них что компилятор сможет определить как "быстрые" могут вызваться в контексте того же потоке.
Между тем,что я думаю,тем,что я хочу сказать,тем,что я,как мне кажется,говорю,и тем,что вы хотите услышать,тем,что как вам кажется,вы слышите,тем,что вы понимаете,стоит десять вариантов возникновения непонимания.Но всё-таки давайте попробуем...(Э.Уэллс)
N>Пул потоков занимает 100мб, следовательно там может быть не больше 100 потоков.
100 не надо(это не имеет смыла, программа не будет работать быстрее). Если например в системе имеется 4 процессора(ядра), то достаточно 4-х системных потоков(хотя, если это нужно, можно и больше чтобы использовать вытесняющую многозадачность). N>Что если они исчерпаются средствами вашего языка?
Новые вызовы будут ожидать появления в пуле свободных потоков, т.е. ожидать когда какая ни будь работающая функция завершится или остановится на wait.
Между тем,что я думаю,тем,что я хочу сказать,тем,что я,как мне кажется,говорю,и тем,что вы хотите услышать,тем,что как вам кажется,вы слышите,тем,что вы понимаете,стоит десять вариантов возникновения непонимания.Но всё-таки давайте попробуем...(Э.Уэллс)
Здравствуйте, C.A.B, Вы писали:
S>>Ну и к чему вы это привели? У вас есть какой-то вопрос? Задайте его, не стесняйтесь. CAB>Ну как бы состояния нет а дедлок есть. CAB>Термином "поток" я здесь называю поток выполнения инструкций(например операторов ЯП), безотносительно к реализации.
Ну конечно же есть состояние. Чем, по-вашему, отличается поток "до" wait_notify(), "во время" wait_notify(), и "после" wait_notify()? Вот вы говорите о выполнении инструкций — значит, есть понятияме instruction pointer. Кроме того, у вас там идут вызовы — значит, есть stack. Эти понятия — и есть состояние, без которого никакого "потока" нет.
S>>Вы странный. Вам говорят: в чистом ФП потоков нет. А вы просите решение на ФП с использованием потоков. CAB>Ok, обобщим: Допустим у нас есть две активные сущности(например клиент и сервер), я прошу решить задачу их взаимодействия чтобы "максимально параллельным, математически правильный алгоритм свободен от дедлоков по определению
", без потоков, на ФП — не важно.
Как только вы ввели "две активные сущности", вы ввели понятие потока управления.
CAB>Допустим потоки там не нужны. Но меня больше интересует
вопрос: как это распаралеллить(чтоб ускорить вычисление)?
В случае чистой математики — частично-рекурсивные функции отвечают на ваш вопрос. Вот у вас есть определения функций, есть граф зависимостей. В каждый момент у вас есть функции, у которых определены все входы => значит, можно выполнить вычисление этих функций. Если таких функций больше, чем одна, то можно запустить вычисления параллельно в таком же количестве аппаратных потоков. После вычисления становятся "доступными" другие функции, их можно вычислять дальше.
На практике слишком мелкая гранулярность подобных функций во-первых, плохо читается, а во-вторых, требует слишком много накладных расходов на шедулинг. Грубо говоря, императивная вычислялка факториала записывается в две инструкции x64 (если пренебречь ограничением на область определения), и молотит со скоростью 1 итерация за такт.
А "функциональная" многопотоковая вычислялка будет на каждой итерации "просматривать" список задач в очереди на исполнение, вытаскивать задачу из списка, вытаскивать параметры, выполнять задачу, записывать результат, обновлять статус зависимых задач. Вряд ли удастся сделать это за 1 такт.
Поэтому пока что копают в сторону
1. Ручного описания гранул шедулинга — прямо на уровне Task<T> t = new {...};// описываем код, который можно шедулить независимо, и определяем зависимости.
2. Автоматических конвертеров "активных" алгоритмов в "реактивные" — типа await/async в новом шарпе
Эрланг, по большому счёту — это п.1. с акцентом на отказ от совместного использования данных.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, C.A.B, Вы писали:
CAB>100 не надо(это не имеет смыла, программа не будет работать быстрее). Если например в системе имеется 4 процессора(ядра), то достаточно 4-х системных потоков(хотя, если это нужно, можно и больше чтобы использовать вытесняющую многозадачность).
Не вижу связи между ядрами и потоками. (в данном контексте)
100 потоков у вас по умолчанию в пуле потоков уже есть и созданы.
Вы говорите, что каждый вызов функции будет выполнятся в отдельном потоке, следовательно для задачи из трех функций на сервере и 3к клиентов память исчерпается мгновененно.
CAB>Новые вызовы будут ожидать появления в пуле свободных потоков, т.е. ожидать когда какая ни будь работающая функция завершится или остановится на wait.
ок, а если функция не завершится или не остановится, то это приведет к зависанию?
CAB>>>Почему? Если массив/списки мутабельны для них это то-же справедливо. M>>Потому что чтение далеко не всегда идет из того же места, где производится изменение CAB>Тогда веть придётся синхронизировать не только доступ ко всему массиву, но и к каждому элементу по отдельности.
Ну, в Erlang'е для новых версий так и собираются делать, емнип. Но сейчас презентацию не найду.
S>1. Ручного описания гранул шедулинга — прямо на уровне Task<T> t = new {...};// описываем код, который можно шедулить независимо, и определяем зависимости. S>2. Автоматических конвертеров "активных" алгоритмов в "реактивные" — типа await/async в новом шарпе
Здесь добавлю, что в Erlang'е вообще «классическое» написание такое:
1. пишем последовательный код
2. Запихиваем код (иногда — без изменений) в gen_server под управлением спуервизора
3. PROFIT!
То есть да, пункт 1, но с посматриванием на пукт 2
Е тебя ест толпа функций, каждая из окторых — отдельный поток, и общие данные, к которым они все рвутся.
