Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 49
Есть ли доказательства, что без потоков параллельное программирование невозможно? Мне они не попадались.
Знаете, это уже за гранью добра и зла. Вы как будто намеренно демонстрируете собственную необучаемость. Вам в комментариях к вашим статьям уже неоднократно говорили, что само по себе "параллельное программирование" возникает только когда код реально исполняется параллельно на параллельно работающих ядрах CPU. А современные ОС распределяют по ядрам именно что потоки/треды (threads). Даже если вы свое приложение разбиваете на N однопоточных процессов, все равно единицей диспетчеризации для ОС является поток/тред.
Так что без параллельно работающих потоков (пусть даже в вырожденном виде из N однопоточных процессов) у вас не будет параллельного программирования по определению.
Но других-то вариантов не предлагают?!
Еще как предлагают.
Бывает, конечно, что-то и предложат, но это «что-то» легко тонет в болоте многопоточности.
Ничего не тонет. Вот, к примеру, несколько вариантов реализации задачи обедающих философов на базе многопоточности, в которой пользователю не нужно иметь дела ни с mutex-ами, ни с atomic-ами, ни с condition_variable: тыц. И это все было описано здесь на Хабре еще до того, как вы начали публикать свои трудночитаемые и написанные псевдонаучным языком статьи с росказнями о том, как избавиться от ужасов параллельного программирования путем оказа от самого праллельного программирования.
Здравствуйте! Я искренне рад Вас слышать.
Но Вы, как мне представляете, не очень меня понимаете.
Ну, первое. Я совсем не против потоков. А на аппаратном уровне - так даже за. Но я против засилья многопоточности (потоки и многопоточность, строго говоря это разные вещи), у которой, скажем так, слабая теоретическая база. Фактически ее нет. Я, например, что-то не припоминаю, чтобы где-то серьезно рассматривалась параллельная модель, состоящая из множества параллельных блок-схем. Можно было-бы ее назвать - сеть БС. Возможно, я не прав. Но даже, если бы где-то и рассматривалась, то я ее скорее бы просто ее проигнорировал.
Безусловно, в определенном смысле я необучаемый, т.к. обучаться тому, во что я абсолютно не верю, - зачем? Какая польза от этого? В статье же я даже представил доказательство, почему моя вера обоснована. Все строго, все научно. Или в моем доказательстве есть пробелы, ошибка? Есть или нет? Уж Вы-то должны в этом разбираться. Если что-то не так, то подскажите. Я только скажу спасибо и, возможно, начну штудировать, обучаться какой-нибудь другой теории. Но какой? Посоветуйте, подскажите.
Теперь о DPP. Я просмотрел Вашу статью. Интересно, конечно, но по мне как-то сложновато. Ну, это может в силу моей необучаемости :). Но Я обратил внимание на протоколы работы философов. Вы, как автор кода, можете ли и своих философов попросить пересортировать вилки и опубликовать протокол их работы? Было бы поучительно посмотреть.
В статье же я даже представил доказательство, почему моя вера обоснована.
Доказательство обоснованности веры? Это какой-то оксюморон. Либо доказательства, либо вера. Вы уж определитесь.
Все строго, все научно.
Нудно, трудночитаемо и с закосом под наукообразие -- может быть.
Вы, как автор кода, можете ли и своих философов попросить пересортировать вилки и опубликовать протокол их работы?
Вы, мягко говоря, ничего не поняли. А учить вас -- только портить.
Доказательство обоснованности веры?
Тут даже с Вами соглашусь. И даже скажу спасибо. Определился. Поскольку опровержений нет, то, безусловно, моя вера, благодаря Вам, стала обоснованной научной теорией :)
Ну, и с философами, похоже, что-то у Вас не ладится. Какие-то они у Вас непокорные. Простую сортировку не могут осилить. А так, конечно, по "вере" хотелось бы сравнить. И так теория стала только "крепшее" ;).
Есть ли доказательства, что без потоков параллельное программирование невозможно? Мне они не попадались.
Вы хотите доказательство определения?
Таки давайте, посмотрим.
Тут надо главным образом определиться с тем, что называть потоком.
У меня есть вариант, но прежде хотелось бы знать что Вы считаете потоком. Только одно условие - определение не должно быть привязано к железу.
Я считаю, что это спор о терминах.
Сам я слово "поток" использую применительно к соответствующей структуре операционной системы или библиотеки среды программирования.
Все же Ваше определение привязано к реализации. Пусть не железной, но программной. Я думаю, что поток лучше определять через формальное понятие алгоритма. Другими словами, поток = алгоритм, а алгоритм = поток. Т.е. поток и алгоритма - это слова синонимы. Я нашел такое определение алгоритма: "Алгоритм - это правило, сформулированное на некотором языке и определяющее процесс переработки допустимых исходных данных в искомые результаты". Разве не похоже на понятие потока?
Алгоритмы имеют разные формы (модели). Блок-схема - поток, КА - поток, МТ - тоже поток. Короче, любое формальное определение алгоритма - это одновременно и определение потока. Пока так, если не копать глубже.
Другими словами, поток = алгоритм, а алгоритм = поток.
Если у вас "поток" тождественнен "алгоритму", то откуда претензии к "многопоточному" программированию, ведь это всего-то "много-алгоритменное" программирование должно быть в вашей картине мира.
Так оно не только в "моей картине мира", а и на самом деле такое. Речь, конечно, о классическом подходе. Если Вы поменяете алгоритмическую модель, то картинка уже будет другая. В статье об этом тоже сказано.
В моей же "картине" каждый поток - автоматная машина, с управлением в форме КА. А множество потоков - это множество АМ, управление которых объединено в сеть автоматов в едином времени.
Замечание. Я немного отредактировал терминологию, применяя вместо понятия КА понятие АМ.
Да, и точнее называть нынешнее многопоточное программирование "много-блок-схемным". По имени той модели алгоритма, которая используется.
В пределах такта сначала выполняются все предикаты, а только потом все действия
Вот это и есть ваш поток выполнения. Последовательность шагов образует поток.
Его автоматный аналог – философы на конвейере – 0.02 сек
А если этих философов покормить на видео карте - там запустить автоматы. То какая скорость будет тогда?
Вопрос, конечно, интересный, но это уже специализированный вариант, а подобные вещи за рамками моих интересов, да и, если честно, компетенции тоже. Речь все же должна идти в первую очередь не о философах, а о реализации автоматов. Видимо, на тех же GPU. Вопрос, требующий отдельного изучения и реализации, похоже, тоже.
Достаточно просто показать, что любой МТ можно поставить в соответствие эквивалентный конечный автомат[10].
Это очень спорное утверждение, требующее строгого и дотошного доказательства. В статье я его не увидел, честно говоря.
Дело в том, что Тьюрингову машину как раз таки невозможно в общем случае реализовать как конечный автомат. Это связано с тем, что у машины Тьюринга неограниченная память (как бы бесконечная лента), а у конечного автомата нет внешней памяти и ограниченное число возможных состояний, на то он и конечный, он хранит только текущее состояние и переходит по входным данным.
Я полистал статьи по ссылкам, взять хотя бы статью Шалыто, там идёт фактически распознавание лишь регулярного языка, где конечный автомат вполне применим, а ему надо было попробовать гораздо более широкий класс, называемый рекурсивно перечислимыми языками, и тут внезапно выяснится, что машина Тьюринга вполне себе справляется, а вот конечный автомат - нет.
Если ограничить машину Тьюринга конечным количеством памяти (лентой фиксированной длины), теоретически её можно смоделировать с помощью конечного автомата, но это частный случай и в общем не относится к общей модели машины Тьюринга.
Ну, конечно Вы правы. Но и я прав. Только мы правы по-разному. Ну, вот бывает такое. В этот раз случилось :) В написанную мною фразу я вложил в том числе и свое понимание, а это не верно. Правильно надо было написать, Надо было так (или близко к этому): "Управление любой МТ можно поставить в соответствие эквивалентный структурный конечный автомат". Меня оправдывает только то, что привел ссылку, где это все расписано и на примерах показано.
В данном случае под термином "конечный автомат" я все же имею в виду "автоматную машину" (АМ). Она, как и МТ, имеет управление, но только в форме структурного конечного автомата (СКА), имеет операторы, которые изменяют ленту, и имеет память хоть в форме ленты, как и МТ. Здесь, конечно, нужно уточнить еще понятие СКА. Но если все это делать, то это сведется почти по объему к статье, на которую я дал ссылку.
Поэтому я согласен с Вашим замечанием, то только частично. Все же по-большому счету я прав. Каждую МТ можно представить как АМ. Так будет точнее. По любому, обсуждая, нужно больше ссылаться на статью, где все это расписано подробно.
Вы же изложили классический взгляд на МТ и КА. И Вы в классическом понимании абсолютно правы. Только с одной поправкой я в своем доказательстве рассматриваю АМ , а не чистый КА. Как-то так ;)
В данном случае под термином "конечный автомат" я все же имею в виду "автоматную машину" (АМ). Она, как и МТ, имеет управление, но только в форме структурного конечного автомата (СКА), имеет операторы, которые изменяют ленту, и имеет память хоть в форме ленты, ...
Ну да, тогда можно что угодно реализовать, даже двоичное умножение в общем случае.
Помоему задача DPP решается вообще без всяких мютексов и прочей хни. Достаточно отобрать у философов право брать вилки самостоятельно, вместо этого раздавать им вилки по неоходимости (ввести в схему официанта). В такой схеме философ постоянно занимается делом (думает), но когда он захотел поесть, он должен сигнализировать об этом официанту (например открытием рта) и ждать пока ему принесут ровно две вилки. После того, как философ поел, он закрывает рот, официант забирает у него вилки и отдает другому (или не отдает вообще никому). Официант, в свою очередь, мониторит наличие свободных вилок и ведет учет очередей на "поесть". Алгоритм диспетчеризации (раздачи вилок) при этом может быть каким угодно - Round-Robin, FIFO и т.д. Такой подход позволяет решать подмножество задача с N философами и M вилками, где N и M произвольные целые числа. А также для задач где философам могут потребоваться еще и ложки, ножи и прочая столовая утварь. В таких сложных задачах использование семафоров/мютексов это прямой путь в тупик. :-)
Собсно, это упрощенная модель по которой работают многозадачные операционные системы.
Помоему задача DPP решается вообще без всяких мютексов и прочей хни.
У автора статьи эта задача как раз и решается без всяких мютексов и Ко.
Но не за счет "волшебных" свойств КА, в которые свято верует автор, а за счет того, что его система ВПК принипиально работает только в однопоточном режиме: она сама последовательно запускает зарегистрированных в ВПК КА. Да еще и, насколько я понимаю, сама "квантует" время их работы. Типа сейчас никто не работает, а ВПК перевычисляет предикаты, привязанные к состояниям КА. Потом опять никто не работает, а ВПК обновляет состояния КА после изменения предикатов. А потом последовательно каждый КА может среагировать на изменение состояния, но не более того. И так по кругу, все на одном рабочем потоке.
При этом еще, ЕМНИП, в ВПК автора статьи один КА может беспрепятственно читать состояние другого КА.
Т.е. то, что на самом деле продвигает автор в своей разработке, к параллельному программированию отношения не имеет. На что ему регулярно указывают в комментариях.
то, что на самом деле продвигает автор в своей разработке, к параллельному программированию отношения не имеет.
Оно, безусловно, имеет отношение в первую очередь к реализации модели параллельных вычислений. с этого надо начинать критику, если она у Вас есть. Строго говоря, нужно показать, что то, что реализует автор, не является алгоритмической моделью параллельного типа. Такой критики от Вас нет.
В реализацию Вы понемногу вникаете. Отдаю Вам должное :) Т.е. не совсем так, но уже все ближе и ближе ;). Правда, к ВПК я не имею отношения :). Надеюсь, что все же Вы имели в виду ВКПа. Не принципиально, но для понимания о чем идет речь - существенно.
Оно, безусловно, имеет отношение в первую очередь к реализации модели параллельных вычислений
Я прочитал уже не одну вашу статью и не первый раз пытаюсь выудить из вас хоть что-то вменяемое в комментариях, но пока так и не увидел ничего, чтобы относилась к параллельным вычислениям или параллельному программированию.
... и не первый раз пытаюсь выудить из вас хоть что-то вменяемое
В попытках объяснить Вам я уже сам разобрался в том, что пытаюсь объяснить :)
Ну, а теперь серьезно. Чем отличается последовательный алгоритм от параллельного? Только одним - моделью управления. У параллельного она параллельная, у последовательного последовательная. Параллельная модель обязательно включает компоненты, которые работают параллельно/одновременно. Последовательная модель - один компонент.
Модели компонент могут быть тоже разными. У меня - автомат (тьфу - "автоматная машина", конечно). Множество компонентов - сеть автоматов (сеть - это их параллельное (!) управление). Вы, например, насколько я понял, продвигаете модель акторов. Отдельный актор - это последовательная модель. Множество одновременно работающих акторов - параллельная модель. У Вас - актор (в нем ,кстати, нужно выделить управление. Какое оно?). У меня "автоматная машина" (с автоматным управлением, конечно).
У моих параллельных вычислений управление - сеть автоматов. В Ваших параллельных вычислениях модель управления - не знаю. Она как-то не озвучена...
Ну, как? Так понятнее?
Только одним - моделью управления.
Что такое "модель управления"?
Ну, как?
Все так же: много наукоподобных словесов, смысла мало.
Так понятнее?
Нет.
Вы не знаете, что такое модель управления? Но, видимо, если задаете вопрос, то ... нет :(
Случай, конечно, крайне запущенный, но... А управляющие операторы обычных языков программирования Вам известны? Вот они и реализуют модель управления. По крайней мере в модели БС.
Вот они и реализуют модель управления.
Т.е. в вашем представлении обычные if, while/for, switch и goto -- это модель управления?
И из чего же тогда состоит т.н. "параллельная модель управления"?
По крайней мере в модели БС.
БС -- это, надо полагать, "блок-схема"?
Все именно так.
И из чего же тогда состоит т.н. "параллельная модель управления"?
Из того, что я уже сказал. В Вашем случае это "if, while ..." в одном потоке и то же самое - в других потоках. В моем случае автомат в одном потоке, автомат в другом потоке (или этом же, хотя это и не принципиально) и дополнительно они синхронизированы по времени. Вот две разные модели параллелизма.
В Вашем случае это "if, while ..." в одном потоке и то же самое - в других потоках.
Какой-то бессмысленный поток слов. Если вы говорите о разных моделях управления, то какие именно модели относятся к вашей "параллельной модели"?
Вы ведь сами сказали:
Чем отличается последовательный алгоритм от параллельного? Только одним - моделью управления. У параллельного она параллельная, у последовательного последовательная.
В последовательном алгоритме, согласно вашим же словам "моделью управления" являются "if, while/for, switch, goto". Значит в "параллельном алгоритме" должно быть что-то другое.
Что?
Если можно, то без наукообразной туфты.
Вот две разные модели параллелизма.
Боюсь, у вас какие-то собственные представления о "моделях параллелизима", ибо банальная эрудиция и простейший поиск в Google говорят о том, что моделями параллелизма являются, например, параллелизм данных, параллелизм задач, параллелизм инструкций.
Боюсь, у вас какие-то собственные представления о "моделях параллелизима", ибо банальная эрудиция и простейший поиск в Google говорят о том, что моделями параллелизма являются, например, параллелизм данных, параллелизм задач, параллелизм инструкций.
Ну а здесь параллелизм автоматов и состояний. Дело в том, что все пытаются натянуть изложенный материал на "классический" параллелизм, когда на нескольких ядрах запустили потоки по одному на ядро и дальше всё просто, но это сюда не укладывается.
Я некоторое время назад общался с Вячеславом по электропочте и в общем примерно понял, что имеется ввиду. Здесь идёт параллельный переход компонентов автоматов из одного состояния в другое.
Может это будет проще понять, если представить пять философов запрограммированных в пяти FPGA с соединениями - вилками, управляемых единым тактовым генератором. В реальном мире ближайшим аналогом как ни странно, будет ПЛК (программируемый логический контроллер). Суть ПЛК в циклической работе - он читает свои входы, производит необходимые вычисления в соотвтетствии с заложенной логикой, затем, переходит в новое состояние и выставляет выходы. В современном ПЛК (типа B&R) я могу запустить несколько параллельных задач, но они будут синхронизированы относительно чтения входов и переходов автоматов, в них сидящих, в новое состояние, он идеологически близок к ВКПа в этом смысле. В этом и есть параллелизм. В принципе это можно и на стандартных потоках реализовать, но их надо будет тактировать общим генератором по входам и выходам, это можно сделать применяя классическое рандеву, и от такта к такту все они будут отрабатывать параллельно, перескакивая из одного соcтояния в другое.
С академической точки зрения это всё весьма познавательно, но тут разница примерно как между учебником "Теория автоматов" и тем автоматами, которые идут в продакшен.
На том же Расте пять философов в самом наипростейшем случае (без официанта) реализуются как-то так, тут меньше сорока строчек и всё прозрачно:
use rand::Rng;
use std::{sync::{Arc, Mutex}, thread,time::Duration,};
fn philosopher(id: usize, forks: Arc<[Mutex<()>]>) {
let (left, right) = (id, (id + 1) % forks.len());
loop {
let eat_time = rand::rng().random_range(500..1500);
let think_time = rand::rng().random_range(500..1500);
println!("Философ {} думает {} ms", id, think_time);
thread::sleep(Duration::from_millis(think_time));
// Asymmetrische Reihenfolge -> verhindert Deadlock
if id % 2 == 0 {
let _right = forks[right].lock().unwrap();
let _left = forks[left].lock().unwrap();
println!("Философ {} кушает (RL) {} ms", id, eat_time);
thread::sleep(Duration::from_millis(eat_time));
} else {
let _left = forks[left].lock().unwrap();
let _right = forks[right].lock().unwrap();
println!("Философ {} кушает (LR) {} ms", id, eat_time);
thread::sleep(Duration::from_millis(eat_time));
}
}
}
fn main() {
const N: usize = 5;
let forks: Arc<[Mutex<()>]> =
(0..N).map(|_| Mutex::new(())).collect::<Vec<_>>().into();
let mut handles = Vec::with_capacity(N);
for i in 0..N {
let forks = Arc::clone(&forks);
handles.push(thread::spawn(move || philosopher(i, forks)));
}
for h in handles { h.join().unwrap();}
}дедлока тут нет, а рандомные времена размышления и приёма пищи более-менее гарантируют, что никто голодным не останется.
Здесь нет ответа на поставленный вопрос. Поэтому вы зря потратили и свое, и мое время.
Сама идея рекламируемых автором статьи сетей конечных автоматов, в которых автоматы работают параллельно друг другу, давным-давно понятна. И я в упор не вижу, чем это принципиально отличается от такой модели параллельных вычислений, как "параллелизм задач". С той лишь разницей, что в случае с КА и ВКП приходится делать stop-the-world после каждого такта для того, чтобы обновить условия (выходы, о которых вы пишете) и сделать новые значения видимыми для следующего такта.
В принципе вы сами и ответили, выходы ведь заведены на входы, что образует логическую петлю, вот это вот замыкание автор и пытается слегка переосмыслить, что ли.
В предыдущих статьях много раз рассматривался тривиальный триггер, в котором как раз есть эти обратные связи:
И, по мнению автора, критерий "правильности" симуляции — вход триггера в метастабильное состояние (чего несложно добиться).
Ну ещё как пример — ПИД регулятор, который мы тут тоже обсуждали в контексте нечёткой логики, в составе которого есть дифференцирующий каскад, в котором также есть обратная связь:
В дискретном мире приходится вводить задержку распространения, а в "идеально параллельном" они будут распространяться мгновенно. С другой стороны это всё тысячу раз симулировалось в том же Симулинке. Это же можно проследить и в данной задачке Дейкстры.
Разве что подача материала несколько специфична — выдернуты скриншоты из ВКПа, плюс пассажи типа "Очень большое влияние на скорость и его стабильность оказывает графика и диалоги. Если их закрыть, то..." совершенно лишние.
Размышления и попытка взглянуть на всё это слегка под другим углом в общем не являются так уж бездарно потраченным временем. В предыдущих обсуждениях мне вот пришлось освежить знания в теории автоматов, уже это хорошо. Даже просто списки литературы, которыми автор сопровождает посты, весьма ценные, хоть там и книжки чуть ли не полувековой давности.
Моя главная претензия к автору в том, что он в своих статьях упорно говорит о параллельном программировании, хотя то, что он предлагает к использованию, имхо, к классическому параллельному программированию не имеет отношения. Собственно, об этом я ему уже говорил прямым текстом.
Сюда же следует добавить еще и стремление автора "навести тень на плетень", т.е. написать так и приплести столько специфических терминов, чтобы затемнить простую, в сущности, идею:
используется модель с независимыми задачами (каждый КА у автора может рассматриваться как отдельная задача);
для обмена данными между задачами применяется схема с общей памятью (КА могут свободно читать состояния друг друга).
И если бы автор не стремился лезть с этим всем в сторону параллельного программирования и не катил бочку на многопоточное программирование, то и претензий к нему бы не было. Ну занимается человек автоматным программированием, ну и здорово. Рассказывает об этом, что вообще замечательно. Опытом делится, что только можно приветствовать.
Но когда он свой специфический опыт и свои специфические задачи (для которых, как мне видится, вообще лучше оставаться в рамках однопотока) пытается распространить на проблемы параллельного программирования... Ну это, мягко говоря, триггерит. Т.к. есть очень сильное ощущение, что "нам втирают какую-то дичь" (с)
С этим согласен, тут слишком много дискуссии о терминологии, и не хватает некоторой "академичности", что ли. В идеале весь материал надо многократно прогнать через этакий "дистиллятор", чтобы очистить от наслоения сивушных масел ненужных деталей, оставив лишь чистую квинтэссенцию идеи.
Ну а здесь параллелизм автоматов и состояний.
Правильно говорить - автоматов. Поскольку речь о сетях из автоматов. Если автоматы параллельны, то и состояния будут такие же.
дедлока тут нет, а рандомные времена размышления и приёма пищи более-менее гарантируют, что никто голодным не останется.
Не знаю, не знаю. Нужны более веские доказательства. Возьмем "моих" философов. Четко обозначено состояние, которое может порождать дедлок. Тут же показано, как из него выходить. Далее показана стратегия, как в него не попасть еще раз. "Более-менее" - это все же не выход :)
...вот это вот замыкание автор и пытается слегка переосмыслить, что ли.
Совсем не так. Автор вводит в модель инерционность и это решает многие проблемы параллелизма. В том числе и проблему обратных связей. Вот такой "побочный эффект".
"Очень большое влияние на скорость и его стабильность оказывает графика и диалоги. Если их закрыть, то..." совершенно лишние.
Если бы я так считал, то не говорил об этом. Это тоже "побочный эффект" модели. Насколько я представляю скоростью потоков управлять нет возможности. А в ВКПа без проблем. Помещение диалогов в более медленное пространство - это большой плюс. А чего-то можно организовать и более быстрый "автоматный поток". В своей разработки этим я пользуюсь постоянно. Это дает, порой, большой эффект с точки зрения производительности.
хоть там и книжки чуть ли не полувековой давности
Были бы современные аналоги я бы и на них дал ссылку. Их или нет или они мне не известны. Но раньше занимались наукой параллельных вычислений, создавали параллельные модели. Сейчас что-то не встречалось подобных вещей.
С этим согласен, тут слишком много дискуссии о терминологии, и не хватает некоторой "академичности", что ли.
Хотелось бы развеять Ваше заблуждение... Если сравнить те автоматы, о которых сейчас говорят, ту форму, в которой они представлены, с автоматами с той моделью, которую реализует ВКПа, то более "академичных" автоматов просто нет.
В идеале весь материал надо многократно прогнать через этакий "дистиллятор", чтобы очистить от наслоения сивушных масел ненужных деталей, оставив лишь чистую квинтэссенцию идеи.
А вот это здравая мысль. Попробую свои же "сивушные масла" удалить из своих же статей и создать совсем краткое описание идеи. Но только не просите пояснять тогда некоторые "академические" термины ;) Их будет, предупреждаю, достаточное число. Например, такое понятие, как "модель параллельных вычислений". Кое-кто так до сих пор не знает, что это такое ;) Все основные понятия созданы, действительно, лет пятьдесят или даже более тому лет назад. Читайте, учите, готовьтесь... а я попробую сократить материал до минимума. Пожелайте мне удачи :)
Типа сейчас никто не работает, а ВПК перевычисляет предикаты, привязанные к состояниям КА. Потом опять никто не работает, а ВПК обновляет состояния КА после изменения предикатов. А потом последовательно каждый КА может среагировать на изменение состояния, но не более того.
Тут ничего не мешает выполняться этому всему параллельно и независимо. Только потом возникнет момент синхронизации общей памяти (ресурсов, состояний КА, вилок итп).
Тут ничего не мешает выполняться этому всему параллельно и независимо. Только потом возникнет момент синхронизации общей памяти (ресурсов, состояний КА, вилок итп).
И вас здесь ничего не смущает?
Типа "параллельно и независимо" за которым следует "момент синхронизации общей памяти".
Ес-но синхронизация остановит все вычисления ВПК, независимо они могут выполняться в остальное время.
Я про то, что Ваше высказывание про однопоток в общем случае неверно - все может распараллеливаться самым обыкновенным образом.
А что там у Автора происходит, я не знаю. Синхронизация святым духом ВПК и МОДЕЛИ, вероятно. Кода то нет.
Я про то, что Ваше высказывание про однопоток в общем случае неверно - все может распараллеливаться самым обыкновенным образом.
Про какое именно из моих высказываний идет речь?
А что там у Автора происходит, я не знаю.
Автор давал ссылку на свой ВКП на github-е (вот он, если не ошибаюсь: https://github.com/lvs628/VCPa), я даже его скачивал и пытался найти там многопоточность и не нашел. И в коментариях к одной из статей этого же автора он сам подтвердил, что у него все сугубо в один поток исполняется.
А где тут сортировка и чего?
Если философ при еде сортирует (меняет местами по номеру) вилки - это типичная пузырьковая. Да и то, философы сидят по кругу, еще надо определить кто первый, чтобы не запустить передачу по кругу "максимальной" вилки.
А философ в данном контексте - это КА выполняемый в отдельном потоке. Никаких противоречий.
Второе. Достаточно просто показать, что любой МТ можно поставить в соответствие эквивалентный конечный автомат[10]. При этом, несмотря на конечность числа состояний, их может быть любое число. Главный вывод, вместо МТ мы без потери общности можем рассматривать конечные автоматы (КА).
Это категорически неверно, поскольку МТ бесконечна. А поставить в соответствие бесконечному множеству конечное число состояний автомата в современной математике нельзя. Выдержка из учебника тут.
А что Вы скажете на это.
Машина Тьюринга
Это Минский М. Вычисления и автоматы. М.: Мир, 1971. – 364 с.
Скрижали неграмотных аборигенов, а возможно, частный случай. Как "учебная" ложка например =)
Вы подменяете понятия или как это нынче модно говорить, натягиваете сову на глобус. Марвин Ли пишет про автомат с внешней памятью, "соединённый с лентой", и здесь говорится о управляющем автомате машины Тьюринга, а в статье из этого слелан вывод, что "любой МТ можно поставить в соответствие эквивалентный конечный автомат". Давайте будем аккуратны в цитировании и терминологии.
Следующее утверждение, кстати, тоже требует комментария, вот это "Из теории автоматов известно, что любой автомат можно разложить на множество параллельных автоматов, используя операцию декомпозиции автомата по операции умножения.". Вы лихо оперируете словами "любой", но если автомат уже представлен в минимальной форме, то он может и не допустить дальнейшей декомпозиции на более простые автоматы через операцию умножения без потери эквивалентности, этого можно достичь лишь ценой усложнения параллельных автоматов. Мелочь, но всё же.
"Лихачу"-то не я, а тот же Мелихов. И потом какая связь между автоматом в минимальной (?) форме и операцией декомпозиции? Если он минимизирован до одного состояния, то разлагать его не нужно. Хотя при желании, думаю, конечно можно. Если так уж хочется ;) А если состояний больше, то само определение декомпозиции предполагает получение в результате эквивалентного произведения автоматов. Если будет "потеря", то это уже не верное разложение. Я так думаю! ;)
Ну и на всяк случай - "скрижаль" :)
Мелихов А.Н. Ориентированные графы и конечные автоматы
Кстати, легко нашел электронный вариант книжки.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Искусство выжить. Простое руководство для настоящих программистов