Table of contents
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
Параллельные программы в РуСи
Даже школьников нужно учить параллельному программированию. Не будем произносить громких слов, что развитие вычислительной техники традиционными способами подошло к физическим пределам, поэтому дальнейшее ускорение вычислений возможно только за счет их распараллеливания, а это требует совершенно новых приемов и инструментов программирования. Приведем более простые и близкие нам примеры из робототехники.
Пусть робот должен получить информацию из нескольких десятков или даже сотен датчиков (сенсоров), обработать эту информацию в реальном масштабе времени и принять оптимальное решение. Датчики выдают информацию в непредсказуемые моменты времени, поэтому если опрашивать их последовательно (есть такой жаргонный, но многое хорошо объясняющий термин «жужжать»), будут большие потери времени. Существенно более эффективная реализация состоит в помещении каждого датчика в отдельный процесс, если информация появляется, процесс ее посылает в виде сообщения специального вида, в противном случае процесс ничего не делает, процессор не занимает (программисты говорят «спит»), поэтому операционная система может отдать все ресурсы другим процессам.
В принципе, переключение процессов тоже занимает определенные ресурсы системы (во многих операционных системах весьма заметные), поэтому были придуманы упрощенные варианты процессов – нити. Не будем в этом учебном курсе вдаваться в технические детали (позже на мат-мехе все растолкуют!), но сразу скажем, что есть стандарт 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 с номером семафора в качестве параметра, русский эквивалент н_вверх_сем.