Модель памяти

Используем алгоритм. Он ключ к решению головоломки с названием "Память".

Задача

Задача текущей статьи непроста. Нам необходимо разобраться в структуре памяти живого организма. Эта задача возникла в работе не на пустом месте, а лишь как этап при поиске методов работы с алгоритмами. Её появление было неожиданно, и решение тоже стало подарком. Причём подарком в сторону нейробиологии. Полученное решение требует обсуждения. Жду в комментариях конструктивную критику, но при этом хочется обратить внимание, что полное описание всех аргументов, подкрепляющих это решение, потребует нескольких дополнительных статей с примерами со стороны процессов коммуникации, обучения и формирования естественного языка.

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

Но давайте приступим. Головоломка "Память" красива, кто-то её "запутал" без нас. Пора вернуть ей упорядоченное состояние и поставить на полку в дополнение к своей коллекции.

Поведение и нервная система

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

В предыдущей статье упомянуты методы генетического синтеза "алгоритмов жизни" организмов, и отмечено, что эти методы имеют и достоинства и недостатки. Главным недостатком является "неторопливость". Низкая скорость синтеза новых алгоритмов выживания может быть достаточной в среде, характеризуемой большим постоянством своих параметров. Тогда цикла жизни поколения организмов, который совпадает с шагом развития используемых алгоритмов, будет хватать по времени для приспособления к новым условиям. Но для среды с большей скоростью изменения состояний (например, при наличии организмов-соперников за еду) необходимы более эффективные методы синтеза "алгоритмов выживания".

Наблюдая за многими живыми организмами, мы можем найти такие методы в их поведении. Можно даже сказать, что изменяющееся в течение жизни поведение организма, использующее активацию различных "действий", влияющих на среду обитания является главным признаком такого "быстрого" синтеза. Здесь можно сделать уточнение, что не всякие методы смены поведения нам важны в текущий момент. Важны лишь те, в которых наблюдается разделение контроля исполнения.

Это разделение сформулировано на примере генетических алгоритмов в предыдущей статье. Оно формирует две группы, отличающиеся по контролю исполнения алгоритма (связного и обусловленного).

Группа связного исполнения должна управляться

• "структурой", содержащей "описание последовательности", формируемой и сохраняемой внутри организма.

Группа обусловленного исполнения будет основываться на "действиях" (внешних по отношению к упомянутой "структуре"):

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

Какая "структура" обеспечивает связное исполнение поведения организма? Что формирует описание последовательности его активности?

Такой "структурой" является нервная система, сформировавшаяся в процессе эволюции у организма и обеспечивающая взаимосвязанную регуляцию деятельности всех систем организма и реакцию на изменение условий внутренней и внешней среды ((с) Wikipedia). Мы знаем уже очень много о нервной системе:

• изучены её составляющие элементы нейроны;
• описаны группы её элементов нервные ткани и нервная сеть;
• детально исследован центральный её отдел мозг;
• рассмотрены способы организации нервной системы у различных животных.

Вся информация о нервной системе накапливается усилиями ученых разных специализаций, в том числе со стороны психологии. Научных сведений много, но даже из личного опыта мы принимаем как естественный факт, что нервная система (удобнее сказать "мозг") умеет запоминать информацию, с которой организм сталкивается в жизни. И "мозг" умеет использовать эту информацию для решения задач, встающих перед организмом. Для решения задач он взвешивает альтернативы, выбирает инструменты ("действия"), находит последовательность их применения, контролирует исполнение этой последовательности и оценивает результат (решена ли задача). Если просуммировать всю перечисленную деятельность мозга и вспомнить две предыдущие статьи. То становится очевидно.

Мозг занимается созданием Алгоритма!

Этот алгоритм еще не код программиста. Но он близок к нему, и это даёт возможность оценить деятельность мозга, считая, что она является разными этапами создания алгоритма. Этот взгляд на работу "мозга" дарит нам ключик к его структуре. Построение этой структуры отталкивается не от физического устройства рецепторов, дендритов и аксонов нейрона, и даже не от способов группировки нейронов в слои разных типов. Оно основывается на функциональном назначении и, возможно, с учётом специализации выполняемых функций в синтезе алгоритма, получится впоследствии объяснить физические особенности областей и слоев коры головного мозга. Но пока не будем столь оптимистично забегать вперёд.

Запоминание алгоритмов выживания

Давайте детальнее рассмотрим утверждение, что "мозг" запоминает информацию. Что значит запоминает? Как понять, что считать информацией? Нужно упростить ситуацию использования этих понятий. Попробуем найти и запоминание, и информацию в процессе синтеза алгоритма. Для этого нам необходимо вспомнить "действие" из определения алгоритма и его главный признак Повторимость, позволяющий это "действие" обнаружить. Организму для использования некоторого процесса в своём алгоритме, необходимо чтобы этот процесс повторялся с одинаковым результатом при одинаковых условиях своих инициализации и исполнения. Как организм может оценить, что некоторый процесс повторим, то есть является "действием"?

Для поиска новых "действий" организм должен в некоторой "структуре" запоминать последовательность событий, которые он переживает. Конечно, эта "структура" не будет содержать полной реализации записываемого процесса. Это будет описание, основывающееся на последовательности внешних "признаков" такого процесса, обнаруживаемых организмом, и выполненных "действий", которые организм использовал в этой ситуации. В дополнение к этому описанию сформированному во внутренней "структуре", у организма должна быть процедура оценки повторного "проживания" такой ситуации. И чем чаще последовательность признаков и "действий" повторяется с участием организма в среде, тем больше вероятность, что организм выявил некоторую закономерность этой среды. То есть организм запомнил информацию!

Тут мы немного упростили процесс запоминания информации это, конечно, хорошо, но выявленная закономерность среды может иметь разный результат для организма. Некоторые "признаки" свидетельствуют об опасности, и для них полезным будет действие("Убегать"). Другие "признаки" говорят о наличии еды и действие("Убегать") будет вредным поведением для организма в этой ситуации. Это не отменяет факта, что повторимость "признаков" важна. Но разделяет выявленные описания последовательностей "признаков" и "действий" на информацию двух типов:

• как полезно поступать в ситуации, описываемой "признаками";
• как в ситуации, характеризуемой "признаками", поступать нельзя.

Следует уточнить, что четких двух полярных типов, конечно, нет. Эти два типа-полюса, а между ними располагаются алгоритмы поведения отсортированные по полезности для своего организма. При этом самыми устойчивыми алгоритмами-последовательностями являются безусловно-полезные (безусловные рефлексы) и безусловно-вредные. А те алгоритмы, которые находятся посередине между этими полюсами (не полезные и не вредные), не имеют устойчивого положения и даже могут быть забыты организмом, при замещении более эффективными алгоритмами.

Мы изложили уже достаточно, чтобы подвести небольшой итог.

Организм своим поведением решает задачу (например, задачу выживания). Для решения этой задачи организм:

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

Для дальнейшего удобства введем несколько терминов.

Цепочка это одновременно и "структура" записывающая последовательность "признаков" и "действий", и "структура" контролирующая повтор исполнения последовательности записанных "признаков" и "действий" в мозге организма. На основе цепочки организм синтезирует алгоритм-стратегию для своего поведения. Методы формирования цепочек разнообразны. Один из наиболее важных это игровое поведение. В следующей статье будет детально рассмотрены возможности эволюции для синтеза в организме цепочек различных типов.

Введём термин признак как обнаружение организмом "параметров" среды (химических, термических, оптических...) при его контакте со свободными или принадлежащими некоторому процессу внешними объектами. Будем использовать обозначение признак("свет") для указания на факт обнаружения организмом конкретного признака фотонов света.

Выведем из кавычек слово "действие" и введем соответствующий термин.

Действие инициируемый организмом процесс воздействия на объекты и процессы среды. Действие, как закреплено в статье 1, обеспечено признаком Повторимость. По аналогии с признаком будем использовать обозначение действие("убегать") для указания на факт инициализации организмом конкретного действия (в представленном примере это процессы приводящие к быстрой смене своего расположения).

Реализация цепочки

Наметив приблизительную структуру памяти организма, можно перейти к реализации. В плане программирования, как способности разрабатывать новый алгоритм, у человека есть преимущества по сравнению эволюционным методом, которым в построении памяти пользовалась природа. Мы мало ограничены набором приёмов, и сразу можем использовать:

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

Почему способ копирования системы цепочек так важен? Чтобы ответить на этот вопрос представим себе человеческий мозг со множеством нейронов и установившихся между этими нейронами связей. Каким образом можно скопировать эту сложную структуру? Ведь она не линейна. Сложно даже подумать как реализовать способ её сериализации. В то время как память в нашем компьютере проста и наоборот предназначена для выполнении копии, не зависимо от того какой сложности структура хранится в её ячейках. Этим мы, как программисты, непременно воспользуемся чуть позже для оттачивания модели, основывающейся на системе цепочек. А пока сосредоточимся на ограниченности возможности природы для копирования синтезированных в виде цепочек алгоритмов от одного организма другому.

У цепочки в живом организме нет никаких других возможностей сформироваться кроме как обнаружение организмом повтора. Повтор некоторой последовательности признаков создаёт в организме макро-признак сложной ситуации. Повтор последовательности действий, несколько раз выполненных организмом, создает образец макро-действия. Почему для заучивания стихотворения (или пьесы на пианино) нам приходится снова и снова повторять произношение слов (нажатия клавиш)? Потому что нет у организма другого способа синтезировать в своей памяти рабочий алгоритм игры мелодии на музыкальном инструмента кроме Повтора. Здесь можно уточнить, что словесное описание алгоритма игры мелодии человек способен выучить без повторяемых касаний черно-белых клавиш, но научиться играть мелодию этим способом у него не получится. И для справедливости необходимо отметить, что словесное изучение алгоритма игры мелодии также не обходится без повторяющихся операций.

В завершение этой оды "Повтору" необходимо сказать, что способ копирования алгоритмов поведения у живых организмов сложен, но уже существует. Эти способ Обучение, то есть процесс копирования алгоритмов во взаимодействии нескольких особей. Самый наглядный пример обучение детей на примере своих родителей. При таком обучении детская особь включает режим "игрового поведения" и следит за взрослой особью. И это "слежение" не простое. Оно включает:

• отождествление маленькой особи со взрослой,
• соотнесение правой руки взрослой особи и правой руки особи-ученика,
• способ добиться от правой руки обучающейся особи действия("движение") сходного с движением взрослой особи;
• способ выполнения особью-учеником нескольких разных действий при последовательном копировании движений взрослой особи;
• формирование копии алгоритма (цепочки полезных действий у обучающейся особи), основанное на нескольких повторах последовательности движений.

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

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

Очевидно, что процессы необходимые для копирования алгоритма от особи к особи требуют от организма дополнительных возможностей. Часть этих возможностей очень похожа на процессы, упоминаемые нами для описания слова "самосознание". Другая часть сводится к процессам коммуникации. Пока что стоит отложить обсуждение процессов коммуникационного синтеза цепочек на основе Языка. Этому вопросу необходимо отдельное пространство, которое будет выделено в одной из последующих статей. В этом месте стоит лишь отметить, что Язык стал самым эффективным решением ограничения возможностей копирования цепочек между живыми организмами. И очень хорошо, что на первом этапе моделирования системы цепочек для копирования мы (как программисты) можем использовать memcpy и пока не думать о коммуникации.

В завершение раздела вернемся к программной реализации системы цепочек. Не во всём природные методы работы с цепочками уступают возможностям программиста. Есть у природы фора великолепная реализация параллельно исполняющихся алгоритмов, уже отмеченная в предыдущей статье при демонстрации процессов, связанных с молекулой ДНК в живой клетке. Огромное количество цепочек работают, формируются, упорядочиваются у каждого из нас в процессе чтения этой статьи. И параметр параллельного исполнения, характеризующий наш мозг не сводится к -ми ядрам, к -ти, и даже к ядрам (как у суперкомпьютера Summit).

Да, моделирование мозга человека пока не по зубам домашнему компьютеру. Но к моделированию мозга человека пока переходить рано. А для более скромной модели мозга (например, муравья или пчелы) может хватить и процессора среднего домашнего компьютера. И когда модель всё же упрётся в производительность, у нас есть возможность перейти к использованию "параллельности" графических процессоров. Эти слова подкрепляются способом обучения модели цепочек. Для самообучения подобной модели не нужно огромного количества опорных примеров, как для нейросети глубокого обучения. А если дополнить модель способами внешнего обучения (в схеме учитель-человек + ученик-модель-организма), то и большого времени перебора вариантов цепочек не понадобится. Дело лишь за малым необходимо желание поиграться моделью, порадоваться результатам и развить для своих целей. А начальная реализация программного проекта модели уже в общем доступе.

Выводы

Есть одна проблема в написании этой серии статей. Очень хочется сразу (начиная с первой статьи) рассказать о полученном решении самых заковыристых головоломок из раздела "человеческий мозг" и "алгоритмический мир". Эти решения действительно красивы, и каждый раз приходится себя останавливать, потому что для их описания нужна минимальная общая платформа из слов-терминов. Поэтому простите за курсив в этих статьях. Эти термины действительно нужны. И надеюсь, что до их использования в написании последующих статей руки "дойдут" поскорее, не взирая на вроде бы заканчивающийся режим самоизоляции.

В текущей статье были приведены наброски модели "Системы Цепочек". Подробности и код одного из вариантов её реализации сосредоточены в отдельном проекте aipy (Python, QT, Qml, Windows+Android), в котором воплощено несколько дополнительных возможностей, описания которых не было представлено в этой статье (слой генерации цепочек, иерархия слоёв, "игровое поведение"). Конечно, способы программной реализации "Системы Цепочек" могут быть разнообразны и не ограничиваются предложенными в указанном выше проекте.

В дополнение к обозначенному в статье способу программной реализации "Системы Цепочек" имеется несколько сформированных предположений, каким образом эта система реализована на нейронной платформе в живом мозге. Но с учётом оценки уровня своих знаний нейробиологии принято решение не освещать эти гипотезы в текущем цикле статей. Для не очень научного их обсуждения есть предложение использовать платформу ai_borisov_CIT (Issues).

А теперь аванс и перспективы. Далее в цикле статей запланировано проработать следующие темы:

• эволюционный подход формирования цепочек-алгоритмов в процессе проживания организмом разных ситуаций среды;
• алгоритмы обучения с разделением на копирование между организмами макро-признаков и макро-действий;
• процессы коммуникации как коллективный способ формирования цепочек несколькими организмами и зарождение Языка (уже есть старенькая статья "Как в языке сформировать существительное?", но эту тему необходимо развить чуть больше);
• Язык самая новая, развившаяся на основе Памяти, "структура" хранения и синтеза алгоритмов, с повышением эффективности синтеза в направлении от естественных форм (речь, "сказки", суждения) к формальным (язык математики, язык физики, язык программиста).

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

Спасибо Вам за внимание.

Отзывы

Буду очень благодарен за отзывы, пожелания и предложения, так как они помогают мне скорректировать направление развития работы в обозначенной области. И заранее извиняюсь за задержку с ответами на Ваши сообщения к сожалению время, которое получается уделить любимому Хабру, очень ограничено.

Отдельное волнение у меня есть по стилю повествования и форматированию, используемым в статье (кавычки, абзацы, курсив). Напишите, пожалуйста, если у Вас есть замечания к ним. Можно личным сообщением.

Ссылки

• Open source (GPL) проект: (Общая теория алгоритмов wiki)
• Заглавная статья темы "Разрабатываем теорию алгоритмов как проект с открытым исходным кодом": (Статья Хабр 0)
• Первая статья серии "Что такое алгоритм?! Действие"(Статья Хабр 1)
• Вторая статья серии "Что такое алгоритм?! Исполнение"(Статья Хабр 2)
• Все рисунки к статье (кроме заглавного и иллюстрации стихотворения Маяковского) сформированы сообществом Wikipedia. Лицензия (Creative Commons Attribution-Share Alike 4.0 International)
• Иллюстрация к полезным и вредным стратегиям художника Николая Денисовского к книге "Что такое хорошо и что такое плохо?", Владимир Маяковский. Ленинград, Издательство "Прибой", 1925г. (описание книги)
• Видео иллюстрация к обучению игре на пианино направляет на канал Олега Переверзева (страница автора).

Идём в глубь острова сокровищ с названием "Алгоритм".

Задача

Перед Вами новая статья серии "Что такое алгоритм?". И снова непростая задача. Нам необходимо "нырнуть глубже" в структуры памяти живого организма. К сожалению, в ракурсе, предлагаемом статьёй, это направление еще исследовано слабо. Что делает материал, приведённый далее, более сложным по сравнению с излагаемым в предыдущих частях, в которых использовалась близость с методами "генетических алгоритмов", автоматизированных систем управления, систем машинного обучения с учителем и подкреплением. Поэтому прокладывать тропинку в глубь неизведанных "территорий" процессов памяти придется во многом самостоятельно. С одной стороны это очень интересно. Ведь мы с Вами первопроходцы! А с другой стороны есть опасность "заблудиться". . Чтобы приободрить в начале дороги, могу лишь сказать, что путь один раз уже пройден, туры сложены вдоль нашей дороги, карта местности прорисовывается, а клад в конце пути обещает быть внушительным.

Но как бы ни был ценен конечный пункт назначения, текущая статья просто еще один шаг в пути к эффективным методам работы с алгоритмами. И предлагаемые решения опять требуют обсуждения. Жду в комментариях конструктивную критику. Хочется еще раз упомянуть, что описание всех важных аргументов в поддержку полученных решений, не получается разместить в одной статье, в которой важно максимально подробно представить одну сторону теории. Поэтому подкрепление этих решений со стороны процессов коммуникации, обучения и формирования естественного языка будет приведено в следующих частях.

Для вскрытия структуры памяти потребуются все результаты, полученные в предыдущих статьях серии (Часть 1 "Действие", Часть 2 "Исполнение", Часть 3 "Память"). Без перечисленных там выкладок читать дальше будет сложнее.

Давайте приступим.

Эволюция цепочек

Структура запоминания в мозге "немного" сложнее, чем было описано в статье 3. Для начала описания было необходимо представить эту структуру упрощенно и выделить только самое важное:

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

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

В нашем "программном проекте мозга" нам тоже это может помочь. Нужно пробовать отследить переходы от более простых к последующим сложным состояниям "программного кода" и при этом записывать решения, фиксируемые каждым "коммитом". Если вспомнить генетиков, то этот способ подобие эволюционной геномике. Но мы будем анализировать не структуру генов, а структуру Памяти. И, конечно, следует обратить внимание на то, что этот разбор скорее "археологический", реальной последовательности развития никто не видел, и она наверняка отличается от приведенной далее. Но для нас не так важен порядок этой последовательности. Важны принимаемые с каждым шагом решения развития. И, похоже, первое важное решение для организма было использование "действия".

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

Первым важным фактором ("двигателем" эволюции) является неравномерность распределения ресурсов и условий в среде обитания. Например, если в месте расположения организма в любой момент времени есть "Еда", то организму никогда не понадобится алгоритм "Двигаться в поиске еды", а вместе с ним может не понадобиться и обязательное действие этого алгоритма действие("Двигаться").

Вторым фактором развития биологических организмов является смерть. Никогда бы не подумал, что придётся сказать фразу следующего содержания, но: "Смерть полезна". Она позволяет выполнить развитие алгоритмов в группе родственных организмов.

И очень хорошо, что, используя Память, природа изобрела более эффективные способы синтеза алгоритмов, так что смерть современному программисту в своей работе не требуется. Но нам предстоит рассмотреть ранние этапы развития алгоритмов организма. Тогда в среде, где еда стала распределяться неравномерно, организмы, которые не научились двигаться, вымерли. А выжившие обзавелись действием("Двигаться").

Этап "Зарождение действия"

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

Как организм может повлиять на действие? Он может его использовать или не использовать. Он может его использовать изредка и часто. Он может исполнять его периодически.

Для организма в ситуации с едой, целесообразно использовать действие("Двигаться") время от времени:

1. передвинулся в новое место;
2. остановил движение;
3. некоторое время не используй движение (вместо него попробуй поесть в новом месте);
4. продолжи с пункта 1.

В виде цикла, описанного последовательностью действий, этот алгоритм можно было бы выдать программисту, но рассматриваемый организм еще не программист, и у него еще нет 10-ти пальцев и клавиатуры, чтобы "закодить" эту программу .

Что может обеспечить исполнение периодического процесса в таком простом организме? Вариантов много. Например, это может быть некая структура с длительным накоплением потенциала и с выполнением быстрой разрядки накопленного потенциала по превышению некоторого порогового значения. Если за процесс разрядки этого потенциала зацепить исполнение действия, то получается реализация алгоритма циклического повторения действия. И время, затрачиваемое на накопления потенциала, определяет период такого цикла. Для дальнейшего повествования способ реализации периодического процесса не так важен, поэтому без перебора других вариантов примем за основу эту "функциональную базу".

Первый алгоритм собран! Он тривиален, но уже может работать (помогать организму выжить). Его реализация доступна даже на биологической элементной "функциональной базе", а у программиста эта простая задача даже интереса не вызовет. Но перед тем как усложнить программисту ТЗ, давайте введём структуру описания "коммита" (этапа эволюции памяти).

Для каждого этапа развития памяти необходимо указать следующие сведения:

• пример эволюционного фактора, послужившего причиной шага развития;
• словесное описание появившейся возможности организма, с использованием которой можно синтезировать новое поведение;
• "функциональная база" организма, требуемая для выполнения текущего шага развития в дополнение к уже наследуемой от предыдущих шагов;
• описание типа алгоритма, добавляемого в арсенал организма на текущем шаге развития
• графическое представление алгоритма.

Здесь, конечно, стоит уточнить, что использования Памяти на текущем шаге развития организма минимально (это лишь запоминание удачного интервала времени между запусками действия). И формируемый алгоритм не имеет связного исполнения (в терминах статьи 2), что несколько умаляет его ценность. Но и бесконечный цикл бывает полезен программисту. А нам пора двигаться дальше и эволюционно ввести признаки в алгоритмы поведения организма.

Этап "Формирование торможения"

Давайте вернемся к примеру "Еда + Движение". В этом примере для исполнения действия("Двигаться") организму требуется "энергия" (не будем отвлекаться на уточнение типа энергии). Чтобы получить эту энергию организму необходима "еда". Поглощая энергию, запасенную в еде, организм накапливает эту энергию (потенциал действия) и при достаточном количестве выполняет действие. Накопление энергии в указанном примере обусловлено внешними для организма признаками количеством еды в текущем месте среды. Это очень похоже на описание функции "Накопление потенциала разрядка исполнением". Но c точки зрения организма такая формируемая естественным образом стратегия является вредной. Потому что в месте, где много еды, организм быстро накопит потенциал, и стратегия вынудит поменять это место на новое. А еды в новом месте может не быть.

Значит накапливаемый потенциал исполнения действия должен быть внутренним процессом, и как показывает рассмотренный пример "убегания от еды", даже при накопленном потенциале полезно не использовать действия("Двигаться"), если в текущем месте много еды. Мы нашли новый эволюционный фактор! Значит надо делать шаг развития.

Этап "Формирование рефлекса"

И было бы всё хорошо с организмом и его алгоритмом поочередного перемещения и поедания еды. Но среда изменилась, и в следующем этапе организм сам стал едой для более проворных организмов-хищников. В такой среде полезно убегать, то есть исполнять действие("Двигаться") в ситуации, когда рядом опасность (хищник). Предыдущим предложением мы записали новый эволюционный фактор, значит пора формировать новый тип алгоритма поведения. На этот раз новый тип алгоритма это рефлекс (почти в классическом его биологическом значении).

Этап "Универсализация"

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

Первой рассмотрим универсализацию нескольких ограничений.

Универсализация нескольких признаков для рефлекса представлена далее.

На этом этапе простая и классическая часть повествования закончилась. И мы переходим к интересным "сложностям".

Этап "Соревнование стратегий"

Как и прежде этап начинается с неприятного подарка среды, подготовленного для "многострадального" организма. Этот "подарок" возможность нахождения и "еды", и "опасности" в одном месте. Организму никак не выработать алгоритм поведения на основе типов алгоритмов, которые имеются в его арсенале. Значит "придётся" развиваться.

Давайте рассмотрим в чём сложность текущего этапа в плане реализации. На этом этапе появляется необходимость запоминать и сопоставлять соотношение полезности для ранее синтезированных алгоритмов поведения. Для программиста эта операция лишь добавление весов к условию и к ограничению, и последующая коррекция этих весов по результатам оценки полезности исполнения действия при одновременном участии в инициализации исполнения этих признаков (условия и ограничения).

Причём коррекция весов может быть "глобальной процедурой". То есть затрагивать большое количество не используемых в текущий момент признаков. Она обеспечивается простым увеличением веса одного текущего признака. Но при этом меняются все соотношения с весами других связанных признаков. И после изменения веса этого признака для сохранения в рабочем состоянии ранее выявленных приоритетов признаков необходимо выполнить процедуру внесения поправок в веса всех существующих признаков, которые связанны приоритетами с измененным. Такая глобальная коррекция очень накладная операция, и в большом множестве связанных признаков может стать неразрешимой в силу наличия циклических зависимостей.

Вторым и более эффективным способом коррекции является локализация сочетания исходных признаков (конкретного условия и ограничения) путем формирования на их основе макро-признака и синтеза цепочки-алгоритма с завязыванием действия уже на этот макро-признак. Тогда можно не модифицировать весов исходных признаков, то есть не нужно проводить глобальной процедуры внесения поправок в уже связанные приоритетами другие признаки. И новую стратегию с приоритетом её использования становится проще выработать. Ведь у макро-признака отдельный вес!

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

Этап "Группировка признаков"

Цепочки памяти во всех предыдущих этапах были односвязными. То есть в них запоминалась (то есть укреплялась) и взвешивалась (то есть оценивалась пользой) одна связь "признак-действие". Для разбора группировки признаков нужно запоминать больше связей. На этом этапе появляется необходимость в объединении связей в "цепь" друг за другом.

И у появления такой цепочки опять есть виновница это среда, подбрасывающая организму новые и особые ситуации, в которых полезно исполнить действие (или, наоборот, вредно его исполнять). При этом особенность каждой такой ситуации заключается в характерном одновременном наличии в среде двух (и более) признаков. И каждый из этих признаков, появляющийся в среде по отдельности, не достаточен для детектирования этой особенной ситуации. Если перейти на "программистский", то организму необходима операция И (AND) по признакам. К счастью для природы биологический вариант этой операции получился не такой ограниченный как у программиста, и его первоначальный синхронный вариант можно достаточно легким преобразованием "распространить" во времени, что обеспечивает организм возможностью детектирования не только синхронного появления признаков, но и появления последовательного (с фиксированными временными интервалами).

Теперь опишем "сложности" признаковой операции И (AND) и особенности их решения методом построения цепочки. Первая и самая главная сложность состоит в том, что если количество базовых признаков у организма , то количество макро-признаков, которые возможно выделить на синхронном парном сочетании из этих признаков . Это число больше (для ). И общее число макро-признаков увеличивается с добавлением каждой дополнительной возможности детектировать сочетания базовых признаков. Таких возможностей как:

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

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

К счастью для организма в нашей среде полезность макро-признака можно проверить без выполнения действия и без ожидания подкрепления от среды или учителя. Способ это осуществить выявление Повтора (которому посвящена статья 3). Только повторяющиеся сочетания-последовательности ("узоры") из базовых признаков являются полезными для построения алгоритма (статья 1).

Поэтому на иллюстрации группировки признаков оранжевая линия стрелок, представляющая собой цепочку, ограничена своей областью. Эта область ответственна за выявление макро-признака с оценкой повторяемости. В ней "записываются" последовательности базовых признаков, и в сопоставлении с записью определяются повторные появления таких же последовательностей. Каждое появление повтора записанной последовательности укрепляет запись этой последовательности, то есть укрепляет её формирующие связи. А те связи, которые не прошли проверку, в итоге могут ослабеть и использоваться для записи нового сочетания базовых признаков.

Описанный способ отделения формирования макро-признака от оценки исполненного действия позволяет:

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

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

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

Этап "Группировка действий"

И если признак повторяемости является дискуссионным в биологическом распознавании зрительных образов, то его использование для группировки действий сомнения почти не вызывает (вспомним пример игры на фортепиано, рассмотренный в статье 3). Основа способа формирования алгоритма, использующего последовательность действий, это повтор организмом требуемой последовательности действий! Но о каких действиях мы говорим? Ранее у организма мы рассматривали лишь одно действие, и он учился им пользоваться с пользой для себя. Такое ограничение было использовано намеренно (в угоду простоты описания вышеизложенных шагов развития). Давайте пожалеем организм и снимем это ограничение.

И на этот раз нам нужен эволюционный фактор, потребовавший от организма группировки действий. Этим фактором стало наличие ситуаций, в которых бльшей полезностью обладает последовательность действий по сравнению с их одиночным исполнением.

Схема, конечно, красивая. Но.

1. Каким способом организм подбирает действия к обнаруженной новой ситуации в среде?
2. Где он хранит оценку полезности (вредности) запомненных действий?
3. Каким образом он синтезирует цепочку последовательности действий?

Давайте разберем эти "сложности" по порядку.

Ответ на первый вопрос (о способе подборе действий) достаточно прост. Таким способом является то, что биологи называют игровой активностью. Справедливости ради стоит сказать, что не все аспекты игровой активности выделимы на рассматриваемом этапе развития организма. Многие её важные компоненты необходимо рассмотреть отдельно (что запланировано сделать в следующей статье). Но основа игровой активности уже видна это спонтанная активация организмом своих действий (обусловленная признаками или накоплением внутреннего потенциала) и анализ признаков и подкреплений, полученных в результате.

После спонтанного выполнения действия у организма есть два способа проверить полезность этого действия в пережитой ситуации. Первый способ привычный нам и хорошо проработанный подкрепление от среды или от учителя. Но есть и способ другой. И для его реализации нам снова на выручку приходит Повтор. Этот способ помогает организму определить, что исходная ситуация, описанная признаками, после воздействия исполненных действий трансформировалась в новую ситуацию. И признаки исходной ситуации, сопровожденные такими действиями, каждый раз приводят к признакам ситуации конечной. Выделив такой закон повторением, "игривый" организм сохраняет цепочку-алгоритм даже не получив подкрепления. И снова переходит в режим спонтанного поиска новых алгоритмов.

Второй вопрос сложнее. Но можно сделать несколько предположений по поводу хранения оценки полезности цепочки действий. Самым легким решением является хранение этой оценки на стыке признака исходной ситуации и цепочки, обеспечивающей последовательность действий реакции. То есть во входном признаковом узле области. Активация этого узла будет тормозиться, в случае если стратегия запомненная организмом вредна, и обеспечит торможение последующих действий цепочки.

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

Общая схема памяти завершена?

Выводы

Хотелось бы чтобы всех перечисленных этапов было достаточно, чтобы завершить разбор процессов протекающих в мозге. Но пока это не так. Природа долго работала и на основе уже описанного создала действительно красивый инструмент по работе с алгоритмами. В следующих статьях нам придется познакомиться с большим количеством шагов развития и эволюционных факторов, толкнувших организм на введение:

• иерархии в признаковые и исполнительные области памяти;
• игровой активности;
• алгоритмов копирования цепочек от организма к организму;
• языковых единиц для обеспечения исполнения коллективных алгоритмов организмов;
• использования языковых единиц для процессов копирования цепочек от организма к организму;
• способов синтеза алгоритмов на основе "цепочек" языковых единиц...

Мы на финальной черте этой статьи. Высадка на остров сокровищ "Алгоритм" произошла. Она получилась длиннее (по количеству букв), чем мне бы этого хотелось, но нас не должно волной прибоя отбросить обратно в море. Поэтому пришлось укрепиться на берегу основательней. С другой стороны количества букв в статье явно не хватает, чтобы описать всё что хочется рассказать, и некоторые подводные камни остались неосвещенными за бортом повествования. Есть предложение выстроить диалог обсуждения этих сложностей в формате вопрос-ответ в отдельной ветке Issues (Open source (GPL) проекта на GitLab).

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

Спасибо Вам за внимание.

Отзывы

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

Отдельное волнение у меня есть по стилю повествования и форматированию, используемым в статье (кавычки, абзацы, курсив). Напишите, пожалуйста, если у Вас есть замечания к ним. Можно личным сообщением.

Ссылки

• Open source (GPL) проект: (Общая теория алгоритмов wiki)
• Вводная статья темы "Разрабатываем теорию алгоритмов как проект с открытым исходным кодом". Пожалуйста, не судите строго эту наивную публикацию "сверх-идеи" устаревшей версии 2019 года: (Статья Хабр 0)
• Первая статья серии "Что такое алгоритм?! Действие"(Статья Хабр 1)
• Вторая статья серии "Что такое алгоритм?! Исполнение"(Статья Хабр 2)
• Третья статья серии "Что такое алгоритм?! Память"(Статья Хабр 3)
• Рисунок яблока в статье сформирован сообществом Wikipedia. Лицензия (Creative Commons Attribution-Share Alike 4.0 International)
• Изображение доктора Ливси и Сквайра Трелони взято из мультфильма Остров сокровищ (1988 г)

Пациент Алгоритм на операционном столе. Он жив и здоров. Поэтому отложим скальпель. Будем изучать силой своей мысли.

Задача

Это новая статья серии "Что такое алгоритм?". Каждый раз статья это решение маленькой подзадачи. В текущий момент почти все подготовлено для "вскрытия" процессов обучения. Для перехода к ним нам необходимо "вынырнуть с глубин" структур памяти живого организма, осмотренных в предыдущей статье, оценить сложность получаемой системы при переходе к иерархии и найти метод "пересадки" синтезированных цепочек одного организма в другой.

Повторю почти дословно важный момент, подчеркиваемый и ранее, но по-прежнему актуальный для выбранной формы повествования. Текущая статья, как и каждая статья серии просто один шаг в пути к эффективным методам работы с алгоритмами. Предлагаемые на этом шаге решения требуют обсуждения. Жду в комментариях конструктивную критику. Но отмечу, что не всегда получается раскрыть все важные аргументы, поддерживающие описываемые решения, в рамках одной статьи, в которой важно максимально подробно представить конкретную сторону теории. Поэтому подкрепление этих решений со стороны процессов формирования естественного языка и коммуникации отложено и будет приведено в последующих частях этой серии.

Во вскрытии структуры Памяти и процессов обучения потребуются все результаты, полученные в предыдущих статьях серии (Часть 1 "Действие", Часть 2 "Исполнение", Часть 3 "Память", Часть 3.1 "Эволюция памяти"). Без перечисленных там выкладок читать дальше будет сложнее.

Давайте приступим.

Иерархия областей памяти

Для выполнения задачи поставленной в этой статье нам необходимо вспомнить "действие" (главного героя первой статьи) и принять как истинное следующее утверждение: "Память простого живого организма синтезирует (запоминает) алгоритм его выживания". Основываясь на этих вводных, опытный программист уже может отметить, что элементарных средств, обозначенных в статье 3.1 "Эволюция памяти", достаточно для написания почти любого кода Алгоритма выживания, основывающегося на имеющихся у организма инструментах:

• элементарных действиях,
• элементарных признаках (в качестве условий к действиям),
• торможении как логической инверсии признака,
• логическом комплексировании признаков операциями OR и AND
• и объединении признаков и действий в последовательность с использованием цепочки.

Эти инструменты в силу реализации, описанной в предыдущей статье, даже дают дополнительные возможности по сравнению с элементарными средствами, имеющимися в арсенале современного программиста. Выгодно отличается, например, операция AND распределенная по времени. И самым главным преимуществом является способность такой программной системы, предоставленной для свободного существования в некоторой среде, самостоятельно формировать макро-признаки на основе простых признаков среды и группировать последовательности действий организма и "действий", существующих в среде (согласно статье 1 "Действие"), в макро-действия организма.

Но от опытного программиста не ускользнет и тот факт, что этих средств мало для поддержания написанного кода в "чистоте". То есть для "удобного" занятия развитием проекта ("Алгоритмы выживания организма") в программной среде необходимо наличие дополнительных возможностей. Первой в списке необходимых является возможность изоляции одного синтезированного (написанного) алгоритма от другого, то есть инструмента формирования подпрограмм. Подпрограмма даёт возможность развивать и вызывать исполнение алгоритма независимо от других алгоритмов.

Чтобы продолжить вспомним "область памяти", обозначенную в предыдущей статье как место детектирования повтора и формирования цепочки, обобщим эту информацию и закрепим в виде термина.

Область памяти это обособленная совокупность узлов памяти, в которой возможно формирование цепочки, объединяющей последовательность активированных близко по времени узлов, путем создания (или укрепления/ослабления имеющихся) связей между ними. При этом цепочки, существующие в области памяти, укрепляются с появлением повтора сформировавшей их последовательности активаций и ослабляются с отсутствием таких повторов.

Здесь можно отметить, что функции области памяти не ограничиваются перечисленными выше процессами. Но в борьбе с отклонением от темы текущей статьи отложу описание всех нюансов и подчеркну только важность некоторых процессов, вызванных:

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

И давайте вернемся к подпрограммам. Запоминаемая в области памяти цепочка из последовательности признаков и действий является способом записи кода алгоритма в живом организме (подобно формированию кода функции на основе последовательности строчек вызовов других функций и условий, оценивающих признаков). При своём развитии организм накапливает полезные синтезированные алгоритмы в виде цепочек. У организма пока одна возможность единая область памяти, в которой одна за другой формируются связи новых последовательностей действий и признаков.

Программисту эта ситуация должна быть знакома, особенно "старожилам", помучившимся в написании больших проектов на BASIC (и отчасти на ASM) с обильным использованием безусловных переходов. Нас (как программистов) может немного утешить тот факт, что у организма тоже был период "спагетти-кода". И организм тоже сталкивался с замедлением развития своего "программного проекта", ведь в спагетти-коде каждая модификация одного алгоритма может поломать реализации несколько других.

Мы подошли к эволюционному фактору. На этот раз он не такой наглядный, как в примерах предыдущей статьи с "Едой" и "Хищником". Но среда опять играет в нём ключевую роль, предоставляя организму множество разнообразных ситуаций, для каждой из которых полезны отличающиеся алгоритмы. И в такой среде успешнее выживает тот организм, который способен синтезировать и использовать бльшее число алгоритмов!

Как организму запомнить большое количество алгоритмов? Как в реализации Памяти убрать сильную связность этих алгоритмов? Как достичь изоляции одного алгоритма от другого?

Ответом на все эти вопросы становится появление в организме нескольких обособленных областей памяти, которые обеспечивают его возможностью формирования цепочек разных алгоритмов отдельно (каждый в своей области памяти). При этом у каждой вспомогательной области должна быть возможность использовать элементарные действия организма. То есть необходим доступ к области памяти, отвечающей за эти действия. Этот подход порождает множество сложностей. Самой очевидной из которых является сложность разрешения конфликта управления между несколькими областями памяти (а значит разными алгоритмами), одновременно использующими одни и те же элементарные действия. Но уже по традиции сложные моменты рассмотрим позднее. А пока перейдём к самому тривиальному случаю.

И для этого рассмотрим минимальное количество областей памяти (то есть 2 области) и введем их специализацию по возможности непосредственно исполнить элементарные действия организма. Так область памяти 1 не будет иметь непосредственного доступа к действиям, ответственность за инициализацию выполнения которых целиком возложим на область памяти 2 ("исполнительную" область памяти). При таком разделении между полученными областями памяти необходимы связи, которые становятся внутренними функциями организма. Все выходы области памяти 1 (в том числе сгруппированные макро-признаки) можно назвать "внутренними действиями" организма. И эти "внутренние действия" с использованием связей становятся тождественны "внутренним признакам" для области памяти 2.

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

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

В первом и втором этапе в пережитых ситуациях была выявлена полезная организму закономерность среды по использованию Действия("1") и Действия("2"). В этапе 3 на основе игрового поведения была выявлена еще одна закономерность, фиксирующая, что последовательность Действие("1") Действие ("2") имеет в среде отклик в виде Признака("А"). На этапе 4 был выявлен повтором макро-Признак { Признак("1") Признак("2") } и выявлено полезное при этом макро-признаке организму действие, которым оказалось макро-Действие{ Действие("1") Действие("2") }. На этапе 5 была выявлена вредная закономерность по использованию Действия("1") при наличии Признака("3").

Таблица описанных закономерностей была сформирована достаточно произвольно. Целью ставилось показать развитие системы алгоритмов организма, формирующихся разными способами:

• с использованием признака Повторимость и с использованием подкрепления пользой;
• с увязыванием действия за подкрепляющий признак и за ограничивающий признак;
• с выполнением группировки макро-признака и формирования макро-действия.

Описание приведенных этапов вышло лишь немного сложнее (за счет формирования внутренних признаков) чем было бы в случае использования организмом одной области памяти. В силу большого сходства описание развития более простого варианта опущено. А до полнофункционального иерархического варианта остался один шаг. Этот шаг введение внутренней области памяти, которая может использовать спонтанную активацию узлов ("игровое поведение"). Такую область памяти далее будем называть "активной" (чтобы подчеркнуть её отличие от "признаковой" область памяти).

При введении промежуточного слоя должны сохраниться все ранее доступные способы построения алгоритмов поведения организма. Поэтому нельзя вносить усложнения в реализацию сопоставления входного признака и выходного действия организма. Это сопоставление можно осуществить проведением признака сквозь внутренний слой без изменения, например, как это сделано для цепочки { признак("Внутренний 5") действие("Внутреннее 3") }. В остальном внутренний слой не мешает, а только только добавляет возможности (как в выявлении макро-признаков, так и в формировании макро-действий) и тем самым способствует разработке более сложных алгоритмов и сохранению большего их количества в Памяти организма.

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

• конфликты внутренних областей памяти за управление;
• возможности усложнения взаимодействия областей памяти с перенаправлением внутренних действий на области памяти внутреннего анализа;
• способы временной блокировки "исполнительной" области памяти торможением.

Эти вопросы очень важны, потому что при объединении дарят организму возможность самоанализа (пока не языкового) и прогнозирования. Но, к сожалению, они весьма объёмны и не вписываются в тему текущей статьи, а потому будут рассмотрены в статьях последующих.

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

Копирование памяти

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

Даже при кратком обзоре неполной модели памяти живого организма становится понятно, что структура хранения описания алгоритмов в ней очень многосвязна. Это кардинально отличается от линейной структуры хранения описания алгоритмов, используемой в генетическом коде организма. И во многом поэтому копирование такого описания по наследству от организма к организму весьма ограничено. Но полезные алгоритмы выживания, синтезированные одним организмом, безусловно будут полезны и другому родственному организму. И процедура копирования алгоритма почти во всех случаях должна быть более эффективна чем самостоятельный повторный синтез этого же алгоритма другим организмом. Мы подходим к объяснению почему коллективные живые организмы более развиты по сравнению с организмами, ведущими одиночный образ жизни. Они при взаимодействии научились передавать синтезированные в памяти цепочки!

И опорой для первого шага такого копирования служит способ, которым формируется цепочка в организме. Если исключить подсказки от признака Повторимость, то этот способ переживание ситуации, характеризуемой некоторыми признаками и сопровождаемой игровым (спонтанным) выбором действия с последующим анализом его полезности. Каким же образом можно скопировать полезный алгоритм другого организма? Конечно, для этого не стоит пересаживать гипофиз и семенники от человека собаке, как описывает М.Булгаков. Есть более простой способ.

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

• (шаг 1) совместное попадание организма-ученика и организма-учителя в ситуацию, которую копируемый алгоритм использует, при этом организм-ученик должен зафиксировать характеризующие эту ситуацию признаки в своей области памяти;
• (шаг 2) выполнение в переживаемой ситуации организмом-учеником необходимого действия, идеально если это действие будет полностью совпадать с действием организма-учителя;
• закрепление сформированной в организме-ученике цепочки с использованием нескольких повторов шагов 1 и 2 или с применением подкрепления от организма-учителя.

Если первый шаг не вызывает сложностей для нескольких живущих совместно родственных особей, то шаг второй (активное копирование действий другой особи) не так тривиален. Он требует механизма, обеспечивающего подобное поведение. И не было бы у организмов процессов обучения, если бы копирование поведения другой родственной особи не было жизненно важным эволюционным фактором, появившимся еще до необходимости копирования сложных цепочек. Этот эволюционный фактор у живущих коллективно организмов звучит так: "Убегай в ту же сторону, если бегут живущие с тобой родственные особи". Это основа стадного поведения, работающего на уровне инстинктов даже у человека при его попадании в соответствующие условия. Похоже, что развитие способности копирования поведения родственной особи в экстренных ситуациях стало основой процессов обучения и всех впоследствии появившихся способов зеркального копирования алгоритмов поведения (уже не обязательно для экстремальных ситуаций) между родственными организмами.

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

• страх способ торможения игрового поведения при большой доле неизвестных признаков или детектировании опасного признака среды;
• слезы как способ использовать алгоритмы родителей для своего выживания (тождественны фразе "Очень нуждаюсь в чем-то, но никак не могу получить самостоятельно", направленной родственной особи);
• смех как способ детской особи сигнализировать свое нахождение в режиме обучения, а для взрослой особи способ заместить агрессивную реакцию на нелепое игровое поведение своего ребенка, то есть двусторонний способ перейти в состояние обучения.

Обособленно стоят инстинкты, связанные с половым влечением. Но их рассмотрение в текущей работе можно опустить, ввиду отсутствия необходимости повторять процессы копирования живых организмов в разрабатываемой компьютерной системе. Ведь копирование компьютерной программы и её состояния для современных вычислительных машин достаточно тривиально.

Мы несколько удалились от процессов обучения. И пока описано только копирование односвязной цепочки {признак действие}. Как же копировать макро-признаки и макро-действия?

Сначала разберем простой ответ для макро-действия. Этот способ уже описан в статье 3 "Память" на примере с фортепиано. В университете мы называли это практикой. А по факту это многократные повторы организмом последовательности элементарных действий, составляющих копируемое макро-действие. Хорошо, что у современного программиста есть более эффективные методы копирования алгоритмов чем у живых организмов. И копирование макро-действий в разрабатываемой компьютерной системе можно не целиком списывать с организма.

А вот описать способы копирования между организмами макро-признаков сложнее. Для реализации этих процессов цепь эволюционных факторов привела организмы к использованию коммуникации и впоследствии создала Язык. Начало их рассмотрения будет приведено в следующей статье.

И в этот раз не будет выводов. Ведь и Булгаков оставил нас самих решать, стоит ли так играть темой мозга, но сам Шарикова снова сделал Шариком...

Спасибо Вам за внимание.

Отзывы

Буду очень благодарен за отзывы, пожелания и предложения, так как они помогают мне скорректировать направление развития работы в этой области.

Отдельное волнение у меня есть по стилю повествования и форматированию, используемым в статье (кавычки, абзацы, курсив). Напишите, пожалуйста, если у Вас есть замечания к ним. Можно личным сообщением.

Ссылки

• Open source (GPL) проект: (Общая теория алгоритмов wiki)
• Вводная статья темы "Разрабатываем теорию алгоритмов как проект с открытым исходным кодом". Пожалуйста, не судите строго эту наивную публикацию "сверх-идеи" устаревшей версии 2019 года: (Статья Хабр 0)
• Первая статья серии "Что такое алгоритм?! Действие"(Статья Хабр 1)
• Вторая статья серии "Что такое алгоритм?! Исполнение"(Статья Хабр 2)
• Третья статья серии "Что такое алгоритм?! Память"(Статья Хабр 3)
• Четвертая статья серии "Что такое алгоритм?! Эволюция памяти"(Статья Хабр 3.1)
• Основа иллюстраций к статье взята из экранизации Владимира Бортко 1988г повести Михаила Афанасьевича Булгакова Собачье сердце
• Образец демонстрирующий проявление "стадного чувства" является ссылкой на одноименную серию телепередачи "Галилео"
• Рисунки яблока и "спагетти-кода" в статье сформированы сообществом Wikipedia. Лицензия (Creative Commons Attribution-Share Alike 4.0 International)

В первой статье цикла мы познакомились с простыми неблокирующими алгоритмами, а также рассмотрели отношение happens before, позволяющее их формализовать. Следующим шагом мы рассмотрим понятие гонки данных (data race), а также примитивы, которые позволяют избежать гонок данных. После этого познакомимся с атомарными примитивами, барьерами памяти, а также их использованием в механизме seqcount.

С барьерами памяти некоторые разработчики ядра Linux уже давно знакомы. Первый документ, содержащий что-то похожее на спецификацию гарантий, предоставляемых ядром при одновременном доступе к памяти он так и называется: memory-barriers.txt. В этом файле описывается целый зоопарк барьеров вместе с ожидаемым поведением многопоточного кода вядре. Также там описывается понятие парных барьеров (barrier pairing), что похоже на пары release-acquire операций и тоже помогает упорядочивать работу потоков.

В этой статье мы не будем закапываться так же глубоко, как memory-barriers.txt. Вместо этого мы сравним барьеры с моделью acquire и release-операций и рассмотрим, как они упрощают (или, можно сказать, делают возможной) реализацию примитива seqcount. К сожалению, даже если ограничиться лишь наиболее популярными применениями барьеров это слишком обширная тема, поэтому о полных барьерах памяти мы поговорим в следующий раз.

Гонки данных и атомарные операции

Рассматриваемое здесь определение гонок данных впервые сформулировано в C++11 и с тех пор используется многими другими языками, в частности, C11 и Rust. Все эти языки довольно строго относятся к совместному доступу к данным без использования мьютексов: так позволяется делать только со специальными атомарными типами данных, используя атомарное чтение и атомарную запись в память.

Гонка данных возникает между двумя операциями доступа к памяти, если 1) они происходят одновременно (то есть, не упорядочены отношением A происходит перед B), 2) одна из этих операций это запись, и 3) хотя бы одна из операций не является атомарной. Врезультате гонки данных (сточки зрения C11/C++11) может произойти что угодно неопределённое поведение. Отсутствие гонок данных ещё не означает невозможность состояний гонки (race conditions) валгортимах: гонка данных это нарушение стандарта языка, а состояние гонки это ошибка вреализации алгортима, вызванная неправильным использованием мьютексов, acquire-release семантики, или и того и другого.

Избежать гонок данных и вызываемого ими неопределённого поведения очень легко. Самый простой способ это работать с данными только из одного потока. Если данные должны быть доступны другим потокам, то работа с ними должна быть упорядочена нужным вам образом с помощью acquire и release-операций. Наконец, вы можете воспользоваться атомарными операциями.

C11, C++11, Rust предоставляют целый спектр атомарных операций доступа к памяти, гарантирующих некоторый порядок доступа (memory ordering). Нас интересуют три вида: acquire (для чтения), release (для записи), и relaxed (для того и другого). Что делают acquire и release вам уже должно быть ясно, в ядре Linux это называется smp_load_acquire() и smp_store_release(). А вот relaxed-операции обеспечивают так называемый нестрогий порядок доступа к памяти. Нестрогие операции не создают никаких отношений порядка между потоками. Их единственная задача это предотвратить гонку данных и избежать нарушения строгой буквы стандарта.

На практике, Linux ожидает от компиляторов и процессоров больше гарантий, чем того требуют стандарты языков программирования. В частности, в ядре считается, что обычные, неатомарные операции доступа к памяти не приводят к неопределённому поведению лишь потому, что где-то там другой процессор трогает тот же участок памяти. Нет, естественно, при гонке данных считанное или записанное значение может быть неопределённым и содержать что попало. Например, половинку старого и половинку нового значения; и если это указатель, то разыменовывать его не стоит. Но от гонки данных как таковой компьютер не взрывается.

Кроме того, компиляторы порой очень изобретательны при оптимизациях и им очень многое позволяется делать, при условии сохранении наблюдаемого поведения в одном потоке (даже ценой неожиданного поведения во всех остальных потоках). Так что идея нестрого упорядоченного нострого атомарного доступа к памяти оказывается полезна и в ядре Linux, где для этих целей существуют макросы READ_ONCE() и WRITE_ONCE(). Считается хорошим стилем использовать READ_ONCE() и WRITE_ONCE(), когда вам нужны явные операции с памятью, что мы отныне и будем делать в примерах кода.

Эти макросы уже встречались в первой части:

    поток 1                           поток 2    -----------------------------     ------------------------    a.x = 1;    smp_wmb();    WRITE_ONCE(message, &a);          datum = READ_ONCE(message);                                      smp_rmb();                                      if (datum != NULL)                                        printk("%x\n", datum->x);

Они похожи на smp_load_acquire() и smp_store_release(), но первый аргумент тут является lvalue, а неуказателем (внимание на присваивание message в потоке1). При отсутствии иных механизмов, избегающих гонок данных (вроде захваченного спинлока), настоятельно рекомендуется использовать READ_ONCE() и WRITE_ONCE() при обращении к данным, доступным другим потокам. Сами эти операции не упорядочены, но всегда используются вместе с чем-то ещё, вроде другого примитива или механизма синхронизации, который уже обладает release и acquire семантикой. Так атомарные операции оказываются в итоге упорядочены нужным образом.

Пусть, например, у вас есть struct work_struct, которые в фоне затирают ненужные массивы единичками. После запуска задачи у вас есть другие важные дела и массив вам не нужен. Когда понадобится, то вы делаете flush_work() и гарантированно получаете единички. flush_work(), как и pthread_join(), обладает acquire-семантикой и синхронизируется с завершением struct work_struct. Поэтому читать из массива можно и обычными операциями чтения, которые гарантированно произойдут после записи, выполненной задачей. Однако, если вы забиваете единичками регионы, которые могут пересекаться и обновляться из нескольких потоков, то им следует использовать WRITE_ONCE(a[x],1), а не просто a[x]=1.

Всё становится сложнее, если release и acquire-семантика обеспечивается барьерами памяти. Рассмотрим в качестве примера реальный механизм seqcount.

Seqcounts

Seqcount (sequence counter) это специализированный примитив, сообщающий вам, а не изменилась ли структура данных, пока вы с ней работали. У seqcounts довольно узкая зона применимости, где они показывают себя хорошо: защищаемых ими данных должно быть немного, при чтении не должно быть никаких побочных эффектов, а записи должны быть сравнительно быстрыми и редкими. Но зато читатели никогда не блокируют писателей и никак не влияют на их кеш. Эти довольно существенные преимущества, когда вам нужна масштабируемость.

Seqcount работает с одним писателем и множеством читателей. Обычно seqcount комбинируется смьютексом или спинлоком для того, чтобы гарантировать эксклюзивный доступ писателям; врезультате получается примитив seqlock_t, как его называют в Linux. Вне ядра слова seqlock и seqcount порой используются как синонимы.

Фактически, seqcount это счётчик поколений. Нечётный номер поколения означает, что в этот момент времени со структурой данных работает писатель. Если читатель увидел нечётный номер на входе в критическую секцию или если номер изменился на выходе из критической секции, то структура данных возможно изменялась. Читатель мог увидеть лишь несогласованную часть этих изменений, так что ему следует повторить всю свою работу с начала. Для корректного функционирования seqcount читатель должен корректно опознавать начало и конец работы писателя. По паре load-acquire и store-release операций на каждую сторону. Если раскрыть все макросы, то простая [и неправильная] реализация seqcount на уровне отдельных операций с памятью выглядит примерно так:

    поток 1 (писатель)                 поток 2 (читатель)    --------------------------------    ------------------------                                        do {    WRITE_ONCE(sc, sc + 1);                 old = smp_load_acquire(&sc) & ~1;    smp_store_release(&data.x, 123);        copy.y = READ_ONCE(data.y);    WRITE_ONCE(data.y, 456);                copy.x = smp_load_acquire(&data.x);    smp_store_release(&sc, sc + 1);     } while(READ_ONCE(sc) != old);

Этот код слегка похож на передачу сообщений из первой части. Здесь видно две пары load-acquire store-release операций: для sc и для data.x. И довольно легко показать, что они обе необходимы:

• Когда поток 2 выполняется после потока1, то при первом чтении sc он должен увидеть значение, которое поток1 туда записал вторым присваиванием. Пара smp_store_release() и smp_load_acquire() здесь гарантирует, что чтение произойдёт после записи.
• Когда потоки исполняются одновременно, то если поток2 уже увидел новое значение какого-либо поля пусть data.x то он должен увидеть и новое значение sc при проверке цикла. Пара smp_store_release() и smp_load_acquire() здесь гарантирует, что как минимум первый инкремент sc будет видно и поток 2 уйдёт на второй круг.

^{Вопрос на самопроверку: зачем читатель делает & ~1?}

Но если внимательно присмотреться и подумать*, то в коде есть хитрая ошибка! Так как писатель неделает ни одной acquire-операции, то присваивание data.y в принципе может произойти ещё до первого инкремента sc. Конечно, можно психануть и делать вообще всё исключительно через load-acquire/store-release, но это пальба из пушки по воробьям и только маскирует проблему. Если подумать ещё чуть-чуть, то можно найти правильное и эффективное решение.
________
* Вот я, например, сразу не заметил этой ошибки и мне уже в комментариях подсказали.

В первой статье мы видели, что порой в Linux используют WRITE_ONCE() и smp_wmb() вместо smp_store_release(). Аналогично, smp_rmb() и READ_ONCE() вместо smp_load_acquire(). Эти частичные барьеры памяти создают особый тип отношений порядка между потоками. А именно, smp_wmb() делает все последующие неупорядоченные присваивания release-операциями, а smp_rmb(), соответственно, превращает предыдущие неупорядоченные чтения в load-acquire. (Строго говоря, это несовсем так, но примерно так о них можно думать.)

Попробуем улучшить работу с полями data:

    поток 1 (писатель)                 поток 2 (читатель)    ------------------------------      ------------------------    // write_seqcount_begin(&sc)        do {    WRITE_ONCE(sc, sc + 1);                 // read_seqcount_begin(&sc)    smp_wmb();                              old = smp_load_acquire(&sc) & ~1;    WRITE_ONCE(data.x, 123);                copy.y = READ_ONCE(data.y);    WRITE_ONCE(data.y, 456);                copy.x = READ_ONCE(data.x);    // write_seqcount_end(&sc)              // read_seqcount_retry(&sc, old)    smp_store_release(&sc, sc + 1);         smp_rmb();                                        } while(READ_ONCE(sc) != old);

Даже если не знать семантики smp_wmb() и smp_rmb(), любому программисту очевидно, что такой код гораздо проще завернуть в удобный API. С данными можно работать, используя обычные атомарные операции (а модель памяти Linux даже позволяет и неатомарные), тогда как волшебные барьеры можно спрятать за read_seqcount_retry() и write_seqcount_begin().

Добавленные барьеры разделяют READ_ONCE() и WRITE_ONCE() на группы, обеспечивая безопасность работы seqcount. Но тут есть пара нюансов:

• Во-первых, неупорядоченные атомарные операции остаются неупорядоченными. Поток 2 может увидеть новое значение data.y вместе со старым data.x. Для seqcount это непроблема, так как последующая проверка sc приведёт к повтору цикла.
• Во-вторых, барьеры дают меньше гарантий, чем load-acquire и store-release. Чтение через smp_load_acquire() гарантированно происходит перед чтениями и записями в память, которые следуют за ним. Аналогично, присваивание через smp_store_release() происходит не только после предыдущих записей в память, но и чтений в том числе. Тогда как smp_rmb() упорядочивает лишь чтения, а smp_wmb() только записи. Правда, взаимный порядок между чтениями и записями, наблюдаемый из других потоков редко важен на практике именно по этой причине в ядре долгое время использовались только smp_rmb() и smp_wmb().

В случае seqcount порядок между чтениями и записями не особо важен, так как читатель никогда не пишет в общую память. В потоке писателя же операции очевидно упорядочены как надо. Логика тут слегка неочевидная размышляйте, пока не дойдёт. Пока код остаётся таким же простым, как и в примере, то он будет работать. Если читателю всё же потребуется изменять память, то для этих присваиваний потребуется уже что-то другое, не seqcount.

Предыдущий абзац очень неформально всё описывает, но это хорошая иллюстрация того, почему важно знать паттерны неблокирующего программирования. Это знание позволяет размышлять окоде на более высоком уровне без потери точности. Вместо того, чтобы описывать каждую инструкцию отдельно, вы можете просто сказать: data.x и data.y защищены seqcount sc. Иликаквпредыдущем примере: a передаётся другому потоку через message. Мастерство неблокирующего программирования отчасти состоит в умении узнавать и использовать подобные паттерны, облегчающие понимание кода.

На этом, пожалуй, пока и остановимся. Естественно, тема барьеров далеко не исчерпана, поэтому вследующей статье мы рассмотрим полные барьеры памяти, как барьеры вообще работают, и ещё больше примеров их использования в ядре Linux.

В первых двух статьях цикла мы рассмотрели четыре способа упорядочить доступ к памяти: load-acquire и store-release операции впервой части, барьеры чтения и записи в память вовторой. Теперь пришла очередь познакомиться с полными барьерами памяти, их влиянием на производительность, и примерами использования полных барьеров в ядре Linux.

Рассмотренные ранее примитивы ограничивают возможный порядок исполнения операций спамятью четырьмя различными способами:

• Load-acquire операции выполняются перед последующими чтениями и записями.
• Store-release операции выполняются после предыдущих чтений и записей.
• Барьеры чтения разделяют предыдущие и последующие чтения из памяти.
• Барьеры записи разделяют предыдущие и последующие записи в память.

Внимательный читатель заметил, что одна из возможных комбинаций в этом списке отсутствует:

Оказывается, обеспечить глобальный порядок записей и последующих чтений из памяти гораздо сложнее. Процессоры вынуждены прилагать отдельные усилия для этого. Сохранение такого порядка стоит недёшево и требует явных инструкций. Чтобы понять причину этих особенностей, нам придётся спуститься на уровнь ниже и присмотреться к тому, как процессоры работают спамятью.

Что творится внутри процессоров

В первой статье уже упоминалось, что на самом деле процессоры обмениваются сообщениями через шину вроде QPI или HyperTransport, поддерживая таким образом когерентность кешей. На уровне ассемблера, правда, этого не видно. Там есть только инструкции записи и чтения из памяти. Acquire и release-семантика отдельных операций реализуется уже конвеером исполнения инструкций конкретного процессора, с учём его архитектурных особенностей.

Например, на x86-процессорах любое чтение из памяти это load-acquire операция, а любая запись это store-release, потому что так того требует спецификация архитектуры. Тем не менее, это ещё незначит, что в коде для x86 можно никак не обозначать acquire и release-операции. Барьеры влияют не только на процессор, но и на оптимизации компилятора, которые тоже могут переупорядочивать операции с памятью.

Кроме того, архитектура x86 негарантирует, что все процессоры будут видеть операции с памятью в одинаковом порядке. Рассмотрим следующий пример, где по адресам a и b изначально расположены нули:

    CPU 1                    CPU 2    -------------------      --------------------    store 1 => a             store 1 => b    load  b => x             load  a => y

Как бы вы ни переставляли эти операции между собой, как минимум одна из записей в память будет находиться перед соответствующим чтением. Соответственно, можно было бы ожидать, что либо в x, либо в y, либо в обоих окажется единица. Но даже на x86 может случиться так, что ивx, ивy будут считаны нули.

Почему? Дело в том, у каждого процессора есть так называемый буфер записей (store buffer), находящийся между процессором и его L1-кешем. Запись в память обычно изменяет только часть кеш-линии. Если кеш-линия инвалидирована, то процессору сперва надо достать новые данные из памяти аэто медленно. Поэтому новые данные для записи складываются в буфер, который позволяет процессору продолжить работу не ожидая обновления кеша.

Буфер записей не особо мешает процессорам сохранить глобальный порядок операций с памятью, когда это чтениечтение, чтениезапись, записьзапись:

• Если процессор переупорядочивает инструкции в конвеере для увеличения производительности (out-of-order execution), то механизм спекулятивного исполнения инструкций может сохранять порядок операций относительно чтений из памяти. Процессор начинает отслеживать кеш-линии смомента их чтения и до момента, когда инструкция чтения покидает конвеер. Если на этом промежутке кеш-линия оказывается вытеснена из кеша, то все спекулятивно исполненные и незавершённые операции, зависящие от считанного значения, требуется повторить, считав новое значение из памяти. Если же отслеживаемая кеш-линия остаётся на месте, то все последующие операции спамятью будут завершены после чтения, так как инструкции покидают конвеер и завершают исполение уже впорядке их следования впрограмме.
• Сохранить порядок записей между собой ещё проще: каждому процессору достаточно переносить записи в кеш в порядке их поступления в буфер записей. Дальше протокол когерентности всё сделает сам.

Но вот гарантировать, что только что записанное одним процессором значение будет считано другим процессором это гораздо сложнее. Во-первых, новое значение может застрять на некоторое время в буфере записей одного процессора, и пока оно не попадёт в L1-кеш, другие процессоры его не увидят. Во-вторых, чтобы процессор всегда видел свои же записи, все чтения сперва проходят через буфер записей (механизм store forwarding). То есть, если у CPU1 или CPU2 вих буферах записей окажутся значения для b и a соответственно, то они увидят именно их предыдущие значения (нули), независимо от состояния кешей.

Единственный способ получить ожидаемое поведение это сбросить весь буфер записей вкеш после записи и перед чтением. Несамая дешёвая операция (пара-тройка десятков циклов), но именно это делает полный барьер памяти smp_mb() в Linux. Рассмотрим теперь, как это выглядит наC:

    поток 1                       поток 2    -------------------           --------------------    WRITE_ONCE(a, 1);             WRITE_ONCE(b, 1);    smp_mb();                     smp_mb();    x = READ_ONCE(b);             y = READ_ONCE(a);

Допустим, в x получается ноль. Что должно для этого произойти? Волнистой линией обозначим ситуацию, когда WRITE_ONCE(b,1) не успевает перезаписать значение, считываемое другим потоком. (Вмодели памяти ядра такое отношение называется from-reads.) Поведение потоков можно описать так:

    WRITE_ONCE(a, 1);           |      -----+----- smp_mb();           |           v    x = READ_ONCE(b);   >  WRITE_ONCE(b, 1);                                         |                                    -----+----- smp_mb();                                         |                                         v                                  y = READ_ONCE(a);

Вспомните, что атомарные операции сами по себе ничего не упорядочивают между потоками. Барьеры тоже не обладают acquire- или release-семантикой. Никаких общих гарантий порядка выполнения операций здесь нет, но есть некоторые специальные гарантии наблюдаемого поведения, на которые всё же можно рассчитывать.

Полный барьер в потоке2 гарантирует, что к моменту выполнения READ_ONCE(a) буфер записей будет сброшен в кеш. Если это произойдёт перед READ_ONCE(b), то она уже увидит запись WRITE_ONCE(b,1) и в x должна будет оказаться единица. Соответственно, если там оказался ноль, порядок выполнения должен быть другим READ_ONCE(b) должна выполниться первой:

    WRITE_ONCE(a, 1);              WRITE_ONCE(b, 1);           |                              |           |                         -----+----- smp_mb();           |                              |           v                              v    x = READ_ONCE(b); -----------> y = READ_ONCE(a);                      (если x = 0)

Благодаря транзитивности, READ_ONCE(a) втаком случае увидит эффект WRITE_ONCE(a,1) и, соответственно, y=1 когда x=0. Аналогично, если второй поток всё ещё видит ноль вa, то полный барьер в первом потоке гарантирует, что READ_ONCE(a) выполнится перед READ_ONCE(b):

    WRITE_ONCE(a, 1);              WRITE_ONCE(b, 1);           |                              |      -----+----- smp_mb();               |           |                              |           v                              v    x = READ_ONCE(b); <----------- y = READ_ONCE(a);                      (если y = 0)

То есть, если y=0, то обязательно x=1. Порядок выполнения операций негарантируется, но каким бы он ни оказался, x и y теперь немогут одновременно содержать нули. Иначе READ_ONCE(a) должна была бы выполниться перед READ_ONCE(b), а READ_ONCE(b) перед READ_ONCE(a), что невозможно.

Модель памяти Linux не считает такие ситуации отношением happens-before между потоками, ведь ни одна из операций не имеет acquire или release-семантики и порядок между ними, строго говоря, не определён. Но тем не менее, барьеры памяти всё же способны влиять на поведение потоков, что позволяет писать высокоуровневые примитивы синхронизации, пользователи которых могут рассчитывать на вполне определённое неопределённое поведение. Рассмотрим теперь, как барьеры применяются на практике.

Синхронизация сна и пробуждения

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

Рассмотрим типичный пример. Пусть один поток хочет попросить другой что-то сделать. Адругой поток часто бывает занят, либо вообще устаёт работать и хочет поспать самоудаляется из планировщика потоков и отправляется на неопределённое время всон. Первому потоку надо растормошить второй. Вкоде это выглядит как-то так:

    поток 1                               поток 2    -------------------                   --------------------------    WRITE_ONCE(dont_sleep, 1);            WRITE_ONCE(wake_me, 1);    smp_mb();                             smp_mb();    if (READ_ONCE(wake_me))               if (!READ_ONCE(dont_sleep))      wake(thread2);                        sleep();

Если второй поток видит в dont_sleep ноль, то первый поток увидит в wake_me единицу иразбудит второй поток. Выглядит, как будто у первого потока release-семантика (представьте, что wake() это как mutex_unlock()). Если же первый поток увидит в wake_me ноль, то второй поток обязательно увидит единицу в dont_sleep и просто непойдёт спать. Второй поток это как бы acquire-половинка операции.

Всё это держится на предположении, что команды первого потока нетеряются. Если, например, wake() вызывается после READ_ONCE() во втором потоке, но до sleep(), то второй поток недолжен витоге заснуть. Как вариант, эти операции могут блокироваться на общем мьютексе. Вот вам ещё один пример того, как неблокирующие приёмы программирования применяются вместе с традиционной синхронизацией. Вданном случае это неявляется проблемой, так как блокировки будут очень редкими.

Приём действительно работает и применяется, например, в интерфейсах prepare_to_wait() и wake_up_process(). Они были добавлены в ядро ещё в ветке 2.5.x, что в своё время подробно разбиралось наLWN. Если раскрыть вызовы функций, то можно увидеть знакомые строки:

    поток 1                                       поток 2    -------------------                           --------------------------    WRITE_ONCE(condition, 1);                     prepare_to_wait(..., TASK_INTERRUPTIBLE) {    wake_up_process(p) {                            set_current_state(TASK_INTERRUPTIBLE) {      try_to_wake_up(p, TASK_NORMAL, 0) {             WRITE_ONCE(current->state, TASK_INTERRUPTIBLE);        smp_mb();                                     smp_mb();        if (READ_ONCE(p->state) & TASK_NORMAL)      }          ttwu_queue(p);                          }      }                                           if (!READ_ONCE(condition))    }                                               schedule();

Как и с seqcount, все барьеры спрятаны за удобным высокоуровневым API. Собственно, как раз использование барьеров или load-acquire/store-release операций и придаёт acquire- или release-семантику всему интерфейсу. Вданном случае wake_up_process() обладает release-семантикой, аset_current_state() распространяет свою acquire-семантику на вызов prepare_to_wait().

Ещё часто бывает, что флажок проверяют дважды, дабы по возможности избежать лишних вызовов wake():

    поток 1                               поток 2    -------------------                   --------------------------    WRITE_ONCE(dont_sleep, 1);            if (!READ_ONCE(dont_sleep)) {    smp_mb();                               WRITE_ONCE(wake_me, 1);    if (READ_ONCE(wake_me))                 smp_mb();      wake(thread2);                        if (!READ_ONCE(dont_sleep))                                              sleep();                                          }

В ядре подобные проверки можно найти в tcp_data_snd_check(), вызываемой из tcp_check_space() одним потоком и tcp_poll() в другом потоке. Код здесь довольно низкоуровневый, так что разберём его подробнее. Если в буфере сокета закончилось место, то надо подождать, пока оно освободится. tcp_poll() в одном потоке устанавливает флаг SOCK_NOSPACE раз места нет, то надо спать перед проверкой __sk_stream_is_writeable(), вот здесь:

    set_bit(SOCK_NOSPACE, &sk->sk_socket->flags);    smp_mb__after_atomic();    if (__sk_stream_is_writeable(sk, 1))      mask |= EPOLLOUT | EPOLLWRNORM;

Если возвращаемая маска будет пустой, то для вызывающего кода это означает, что сокет не готов (и надо ждать, пока будет готов). smp_mb__after_atomic() это специализированная версия smp_mb() с аналогичной семантикой. Коптимизациям барьеров мы ещё вернёмся, но позже.

Другой поток, занятый отправкой данных из сокета, должен впоследствии разбудить первый поток. tcp_data_snd_check() сперва отправляет TCP-пакеты, освобождая место в буфере можно неспать, место появилось затем проверяет флажок SOCK_NOSPACE, и наконец (через указатель нафункцию sk->sk_write_space()) попадает в sk_stream_write_space(), где флажок сбрасывается и если там кто-то спит, то его будят. Вызовов функций тут немного, так что я думаю, вы сами легко разберётесь. Также обратите внимание на комментарий в tcp_check_space():

    /* pairs with tcp_poll() */    smp_mb();    if (test_bit(SOCK_NOSPACE, &sk->sk_socket->flags))      tcp_new_space(sk);

Парное использование барьеров означает, что функции составляют взаимосвязанную пару операций с acquire и release-семантикой. По барьерам чтения или записи в память легко понять, какая у чего семантика: acquire для чтения, release для записи. Сполными барьерами же для понимания семантики следует читать код вокруг них и думать. Внашем случае мы знаем, что функция, инициирующая пробуждение tcp_check_space() обладает release-семантикой. Соответственно, у tcp_poll() acquire-семантика.

Подобный приём идиому можно заметить почти везде, где в ядре используется smp_mb(). Например:

• Workqueues таким образом решают, может ли рабочий поток отправиться поспать, если ему больше нечего делать. Будильником здесь выступает insert_work(), тогда как wq_worker_sleeping(), очевидно, хочет спать.
• Системный вызов futex() с одной стороны имеет пользовательский поток, записывающий новое значение в память, а барьеры являются частью futex(FUTEX_WAKE). Сдругой стороны находится поток, выполняющий futex(FUTEX_WAIT) и все операции с флажком wake_me внутри ядра. futex(FUTEX_WAIT) получает через аргумент ожидаемое значение в памяти, и потом решает, надо ли спать или уже нет. См.длинный комментарий в начале kernel/futex.c, где подробно рассматривается этот механизм.
• В контексте KVM роль сна играет переход процессора в гостевой режим, когда он отдаётся враспоряжение виртуальной машины. Для того, чтобы выбить процессор из рук гостевой ОС ивернуть его себе обратно, kvm_vcpu_kick() отправляет межпроцессорное прерывание. Вглубине стека вызовов можно найти kvm_vcpu_exiting_guest_mode(), где видно знакомые нам комментарии о парных барьерах вокруг флажка vcpu->mode.
• В драйверах virtio можно найти два места, где smp_mb() используется похожим образом. Содной стороны находится драйвер, который иногда хочет прервать операцию и пинает занятое устройство прерыванием. Сдругой стороны есть устройство, которому иногда надо отсигналить ожидающему драйверу о завершении операции.

На этом знакомство с барьерами памяти оглашается оконченным. Вследующей части мы примемся за операции compare-and-swap, их применение для оптимизации блокировок и важную роль вреализации неблокирующих связных списков.