Параллельность

Параллельные программы в РуСи

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

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

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

Студент мат-меха Александр Головань реализовал для РуСи в довольно общем виде библиотеку поддержки процедур стандарта POSIX, но оказалось, что правила работы с ней довольно трудно объяснить начинающим программистам, в основном, из-за большого количества указателей на произвольные объекты (void *) и работы с динамически отводимой памятью, поэтому в данном параграфе мы представим существенно упрощенную модель работы с нитями.

Мы исходим из того, что основным способом применения РуСи является цепочка:

«графическая модель – текст на РуСи – компилятор - интерпретатор», причем интерпретатор может работать как на компьютере, так и на непосредственно на роботе.

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

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

struct message{int numTh; int data;}

При посылке сообщения поле numTh содержит номер нити, в которую посылается сообщение, при приеме сообщения – номер нити, откуда сообщение пришло, data – это содержание сообщения.

В тексте на РуСи каждая нить обрамляется скобками специального вида t_create и t_exit, префикс t_ означает thread, русские эквиваленты н_создать и н_конец, префикс н_ означает нить.

Для приостановки работы нити используется оператор t_sleep с одним целым параметром – количество миллисекунд, на которые нужно приостановить работу нити, русский эквивалент н_спать.

Посылка сообщения осуществляется оператором t_msg_send с параметром типа struct message, русский эквивалент н_послать. РуСи имеет расширение стандартного языка Си для записи структур {a, b}, особенно удобное для формирования параметра оператора н_послать.

Прием сообщения осуществляется функцией t_msg_receive без параметров, выдающей значение типа struct message, русский эквивалент н_получить.

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

В 1965 году знаменитый ученый Эдсгер Дейкстра предложил новую концепцию в программировании – семафоры, над которыми возможны три операции: установить (level), опустить (down) и поднять (up). Операция опустить уменьшает значение семафора на 1, если это значение становится отрицательным, процесс, выполнивший эту операцию, приостанавливается (suspend). Операция поднять увеличивает значение семафора на 1, если какой-то процесс был приостановлен из-за этого семафора, он продолжит работу (resume). Важно, что операции опустить и поднять являются неделимыми, то есть действия добавить/отнять единицу и проверка на знак должны выполняться подряд без каких-либо прерываний со стороны других процессов.

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

Стандарт POSIX включает в себя эти три действия над семафорами.

Определить новый семафор можно с помощью функции t_sem_create, которая имеет целый параметр level (начальное значение семафора) и выдает целое значение – номер нового семафора. Русский эквивалент этой функции н_создать_сем.

Действие опустить осуществляется с помощью оператора t_sem_wait с целым параметром – номер семафора, русский эквивалент н_вниз_сем.

Действие поднять осуществляется с помощью оператора t_sem_post с номером семафора в качестве параметра, русский эквивалент н_вверх_сем.