Как стать автором
Обновить

Семафоры, гонки, критические секции и Scratch. Зомби против растений

Время на прочтение 4 мин
Количество просмотров 6K

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


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



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


Также я буду писать скрипты таким образом, чтобы минимизировать их дублирование. Т.е. буду использовать клоны спрайтов, а не отдельные спрайты. Освоить данный стиль программирования очень важно, чтобы избежать в будущем лавинных изменений (1 изменение ведет к 4) и упростить поиск ошибок.


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


→ Ссылка на заготовку игры


Скопируйте примеры кода и получите результат.


ВАЖНО: изменять можно только спрайт «Горохострел»


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


Создать 4-8 растений не сложно. Клонируй, клонируй и еще раз клонируй. А теперь подойдем к моменту, что данные растения должны стрелять. Задумайтесь, 4-8 растений хотят одновременно получить доступ к одному спрайту пули.


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


Если говорить в терминах, то пулякритический ресурс/секция. А борьба за право обладать данным ресурсом называется гонкой. Другими словами, 4 объекта/клона растения начинают гонку за право обладания критической секцией/ресурсом.


Какой алгоритм выстрела в двух словах?


  1. Передать пуле координаты клона растения
  2. Создать клон пули по координатам, который будет лететь в сторону зомби.

Если не осуществить доступ к данному алгоритму/скрипту, то будут последствия. Ведь этот скрипт и есть критическая секция. Все пули вылетят из последнего выставленного клона, без каких либо задержек.



Для передачи местоположения клона растения пули, нам необходимо место через которое мы будем передавать координаты (х, у). Я использую список «координата клона ореха», так как два данных значения должны передаваться вместе.


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







Для упорядочивания доступа к секции у нее должен быть страж, который стоит на входе, чтобы только один объект мог получить доступ к пули и создать его копию. Его имя — семафор. Семафор — примитив упорядочивания доступа к ресурсу, который гарантирует использование ресурса только одним объектом, и может принимать несколько значений (0,1, 2 ,3, 4, в нашем случае).


Попробуем написать доступ к критической секции через семафор.


  1. Ждем случайное количество долей секунды, чтобы сразу минимизировать одновременную блокировку ресурса несколькими клонами объектов.
  2. Запрашиваем доступ у стража/семафора. Поэтому увеличиваем значение семафора на 1.
  3. Проверяем, что никто больше не занял семафор. Ваше значение должно быть равно точно 1. И если это так, то выполняем критическую секцию.
  4. И в любом случае, отпускаем семафор, т.е. уменьшаем значение на 1.

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





Сценарий, при котором никто не выполнит критическую секцию


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


Сценарий, при котором клон 1 выполнит критическую сецкию


Клон 1 вновь получил процессорное время. Он захватывает семафор и переходит к следующей операции сравнения. Проверяя значение семафора он видит, что только один он получил доступ, он переходит к критической секции и вдруг, процессор прерывает его выполнение и клон 2 вступает в игру. Он захватывает семафор, движется к следующей инструкции сравнения и он видит, что он уже не первый, кто захватил данный ресурс. И обходит стороной критическую секцию. Процессор вновь дает время клону 1 и тот приступает к выполнению критической секции. Выполняет ее и выпускает семафор. Клон 2 также выпускает и гонка начинается вновь.


Мы сейчас коснулись небольшого кусочка работы в многопоточной среде. Где множество объектов стремятся работать с одним ресурсом и их скрипты работают одновременно. Остается только сделать так, чтобы у нас было 10 выстрелов и выстрелы проходили через равные отрезки времени, хотя бы примерно ;) Для этого добавим переменную «выстрел состоялся» с зоной видимости «только для этого спрайта».





Успехов детям и взрослым в многопоточном программировании.


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


PS: Вам будет полезна эта статья — она расскажет про работу переменных с зоной видимости «Только для этого спрайта».

Теги:
Хабы:
+9
Комментарии 2
Комментарии Комментарии 2

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн