Скретч‎ > ‎

Параллельное программирование

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

Задача 1. Имеется объект Пчела с двумя костюмами: «крылья вверх» и «крылья вниз». Необходимо создать случайный анимированный полёт Пчелы.

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

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

всегда

следующий костюм

ждать 0,1 секунд

конец

всегда

плыть 1 секунд в точку

x: [случайное число от -235 до 235]

y: [случайное число от -175 до 175]

конец
 

Так можно ввести понятие параллельности потоков. Дальнейшее решение задачи предусматривает поворот Пчелы в направлении движения путём сравнения её старых и новых x-координат.

Задача 2. Имеются два объекта: Лошадь и Пицца. Пицца появляется в случайном месте экрана. Лошадь, управляемая с клавиатуры, должна съесть Пиццу, после чего Лошади начисляется одно очко. Съеденная Пицца появляется в новом месте экрана и т.д.

Для решения этой задачи необходимо, чтобы дети умели работать с переменными.

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

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

поставить [очки] в 0

всегда

если [касается [Пицца]]

передать [исчезни] и ждать

изменить [очки] на 1

конец

 

когда я получу [Исчезни]

спрятаться

передать [появись]

 

когда я получу [появись]

показаться

установить x в [случ. число от -230 до 230]

установить y в [случ. число от -170 до 170]
 

Листинг основного скрипта Лошади

Листинг скриптов
Пицца

 

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


При дальнейшем изучении программирования на Scratch можно начинать систематически изучать более абстрактные технологии. В 5‑6 классах ученики уже вполне способны воспринимать такие понятия как «многопоточность», «синхронизация», «голодание», «взаимная блокировка», «мьютекс», «семафор» и др. Даже если до сих пор эти термины не звучали на занятиях, основные идеи уже подхвачены и усвоены большинством ребят — иначе не написать ни одной сколько-нибудь серьёзной программы.

Задача синхронизации возникает в любой параллельной программе, где потоки работают с общими ресурсами. Большинство ребят, занимающихся Scratch с первого класса, хорошо знакомы с проблемами синхронизации потоков и имеют в запасе несколько приёмов решения таких проблем. Теперь самое время систематизировать полученные знания. В качестве иллюстрации возможностей Scratch в области преподавания основ параллельного программирования рассмотрим две задачи: (3) о синхронизации потоков при помощи установки барьера и (4) об использовании мьютекса для организации критических секций.

Задача 3. Имеется три объекта (Бегемот, Собака и Утка), которые движутся со случайной переменной скоростью в направлении четвёртого объекта — Дерева. Требуется сделать так, чтобы все три движущихся объекта встретились у Дерева и дальнейшее движение продолжили вместе.

Поскольку движение случайное (по абсолютной величине скорости), то рассчитать заранее время начала совместного движения невозможно: оно должно начаться, как только последний (самый медленный) объект придёт в точку встречи. Одним из стандартных подходов к решению таких задач является механизм барьеров. Scratch не имеет для этого функций, аналогичных содержащимся в библиотеке pthreads, поэтому нам придётся позаботиться и о написании «системного» кода. С методической точки зрения это очень кстати, так как, с одной стороны, не составляет особого труда, а с другой — позволяет яснее представить себе внутренние, системные механизмы изучаемой технологии.

«Системные» функции возложим на Дерево. Его задачей будет дать команду к началу движения и вести счётчик прибывших объектов. Как только счётчик станет равен трём, дать команду к общему движению.

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

when I receive [I’m here!]

change n by 1

if n=3

broadcast [Go together]

when I receive [Start!]

repeat until [touching Palmtree?]

…….

end

broadcast [I’m here]
 

Листинг основного скрипта Дерева

Листинг основного скрипта объекта

 

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

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

Здесь «критической секцией» будет процедура совершения прыжка. То есть нужно обеспечить объекту возможность (а) добраться до критической секции и (б) находиться в ней одному. В Scratch нет функций типа send() и receive(), так что пересылку адресных сообщений будем выполнять при помощи всё тех же broadcast и broadcast_and_wait, которые обрабатывает только тот объект, которому они предназначены.

«Системные» функции возложим на объект Фон (stage). Он будет поддерживать работу с мьютексом. Сам мьютекс будет переменной, принимающей значение «ноль» если прыгать можно и «один» — если нельзя. Другими словами, мьютекс показывает количество объектов, находящихся в данный момент в «критической секции».

Рассмотрим в качестве примера объект Кот. Доступ в критическую секцию организуется при помощи простого скрипта:

forever

broadcast [cat_mutex_lock] and wait

broadcast [cat_jump] and wait

broadcast [mutex_unlock]

end
 

Первое сообщение запрашивает мьютекс и дожидается его освобождения. Второе сообщение посылается в том случае, когда получено «невидимое» сообщение от Фона, что мьютекс освободился и передан объекту (осуществляется командой broadcast_and_wait); это сообщение запускает процедуру прыжка (здесь не рассматривается). Третье сообщение освобождает мьютекс. Самым сложным для понимания моментом является необходимость вызова broadcast_and_wait для передачи первого адресного сообщения и возможность использования broadcast для передачи третьего безадресного (общего) сообщения.

Остальные «прыгающие» объекты описываются аналогично.

Фон должен обрабатывать первое и третье сообщения. В первом обработчике мы ждём, пока мьютекс освободится и затем захватываем его. Важно понимать, что пока Фон дожидается освобождения мьютекса (в цикле wait until mutex=0), объект тоже ждёт освобождения мьютекса, так как для захвата использовался broadcast_and_wait. Освобождение мьютекса Фоном сводится к обнулению соответствующей переменной.

when I receive [cat_mutex_lock]

wait until mutex=0

set mutex to 1

end
 

when I receive [mutex_unlock]

set mutex to 0

end

Листинг основных скриптов Фона

 

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

  выполнение какого-либо действия при нахождении вне критической секции;

  случайные задержки, которые показывают, что механизм на самом деле работает;

  запись Фоном последовательности состояний объектов в список для лучшего понимания процесса;

  замена мьютекса на семафор, разрешающий нахождение в критической секции не более заданного числа объектов;

   и др.
 

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

Выводы
 

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

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

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

Автор: В. О. Дженжер, Л. В. Денисова

Comments