Техническое описание ядра Т-системы
(реализация от 30 Мая 1998г.)
Содержание
- Введение
- Базовые технические решения
- Организация процесса вычисления задач пользователя-автотрансформация вычислительной сети
- Требования Т-системы к аппаратному и программному окружению
- Основные выводы
- Основные структуры данных. Т-структуры
- Компоненты Т-системы
Данный раздел содержит описания и обоснования технических решений, принятых и использованных при реализации текущей версии ядра Т-системы.
Базовые технические решения
Различные подходы к распараллеливанию программ
Основной проблемой при создании мультипроцессорной вычислительной техники следует признать проблему распараллеливания программ, что включает в себя:
- организацию процесса вычисления в виде нескольких фрагментов (задач, гранул параллелизма), способных выполняться одновременно;
- распределение задач по различным процессорным элементам (ПЭ) мультипроцессора (внешнее планирование);
- обеспечение передачи данных между параллельными фрагментами и синхронизации параллельных фрагментов.
Существует несколько подходов к решению проблемы распараллеливания программ:
- ручное статическое распараллеливание;
- автоматическое статическое распараллеливание;
- автоматическое динамическое распараллеливание.
Ручное статическое распараллеливание
При ручном статическом распараллеливании программист на некотором языке параллельного программирования в процессе написания программы (в статике) организует:
- разбиение задачи на параллельные фрагменты;
- их распределение по ПЭ мультипроцессора;
- обмен данными между ними и синхронизацию.
Основной недостаток данного подхода состоит в том, что на программиста возлагается дополнительная нагрузка. Ему необходимо не только запрограммировать задачу, но и позаботиться о ее распараллеливании. Это ведет к снижению производительности труда программиста и, что более существенно, к снижению надежности программ.
Кроме того, при ручном статическом распараллеливании не всегда можно добиться глубокого (предельного) распараллеливания программы-в силу теоретических ограничений возможностей статического анализа. Это общий недостаток всех статических подходов к решению проблемы распараллеливания программ. Более подробный анализ данного обстоятельства приведен в следующем разделе.
Автоматическое статическое распараллеливание
В данном подходе используют распараллеливающий компилятор, который на этапе компиляции (в статике):
- пытается обнаружить информационно независимые фрагменты задачи,
- оформить их параллельное выполнение, синхронизацию и передачу данных.
Несмотря на то, что применение этого метода несомненно облегчает задачу распараллеливания, статический анализ для многих случаев не способен предусмотреть все сочетания условий, которые могут возникнуть в процессе выполнения программы. Это является следствием алгоритмической неразрешимости данной проблемы для общего случая.
Данный недостаток ведет к снижению эффективности выполнения прикладной программы и, как следствие, снижению производительности вычислительной системы в целом.
Еще одним недостатком статического подхода (и ручного, и автоматического) является зачастую возникающая необходимость проводить распараллеливание программы заново в случае изменения конфигурации системы (например, изменения числа процессоров) и/или в случае изменения входных данных, которое часто приводит к изменению загрузки отдельных процессоров или процессорных элементов.
Автоматическое динамическое распараллеливание
В данном подходе фрагменты программы, которые могут быть выполнены
параллельно, обнаруживаются системой (операционной средой параллельного
выполнения) в динамике-в процессе выполнения программы.
Это позволяет проводить балансировку загрузки отдельных процессорных
элементов, составляющих вычислительную систему и, как следствие,
без изменения исполнять системные и прикладные программы на вычислительных
установках различной конфигурации (адаптируемость к изменению
конфигурации).
Реализация данного варианта распараллеливания позволяет рассчитывать
на достижение более глубокой степени параллелизма, так как в общем
случае только в динамике возможно определить, когда и сколько
параллельных ветвей возникнет в процессе счета, какие информационные
связи будут установлены между ними и какая синхронизация между
ними потребуется для их корректного выполнения.
Выбор подхода к распараллеливанию программ
Основываясь на приведенном выше анализе различных подходов к распараллеливанию программ, для операционной среды параллельного программирования-Т-системы-выбрана и реализована концепция автоматического динамического распараллеливания программ.
Организация процесса вычисления задач пользователя-автотрансформация вычислительной сети
Применяемая в Т-системе методика автоматического динамического
распараллеливания программ основана на использовании вычислительной
модели "автотрансформация вычислительной сети". В этой
модели процесс вычислений представляется в виде автотрансформации
сети, узлами которой являются процессы и обрабатываемые данные.
Данное решение является весьма традиционным. Практически все
известные реализации идеи автоматического динамического распараллеливания:
- потоковые машины (data flow);
- редукционные машины (reduction machine);
- автоматные сети (проект ряда МДА: ЕС2704, ЕС2740, ЕС2727),-
Т-система отличается от перечисленных разработок деталями реализации, в которых учтены недостатки, выявленные в упомянутых проектах.
Различают различные подходы к определению размера (вычислительной сложности) тех параллельных фрагментов, на которые разбивается программа:
- Крупноблочное (large grained) распараллеливание. В этом случае параллельными фрагментами являются отдельные задачи или подзадачи пользователей, информационно несвязанные (слабо связанные) между собой. Такой уровень параллелизма-"каждой задаче-свой процессор"-характерен для обычных операционных систем для мультипроцессорных ЭВМ. Подход не имеет отношения к концепции автоматического динамического распараллеливания программ.
- Мелкозернистое (fine grained) распараллеливание. В этом случае параллельными фрагментами являются отдельные элементарные операции (data flow), комбинаторы (элементарные функции, reduction machine). Чрезмерное "измельчение" гранул параллелизма приводит к тому, что накладные расходы на организацию параллельного выполнения фрагментов могут в несколько раз превышать вычислительную сложность этих фрагментов. Тем самым, на накладные расходы может уходить большая часть производительности мультипроцессора.
- Средне зернистое (coarse grained) распараллеливание.
В этом случае параллельные фрагменты имеют среднюю вычислительную
сложность (достаточное количество операторов входного языка высокого
уровня-104106 команд процессора-что соответствует таким
понятиям, как подпрограмма, функция). Фрагменты должны быть:
- достаточно крупными, чтобы их вычислительная сложность превышала бы накладные расходы на организацию их выполнения;
- достаточно мелкими, чтобы в процессе выполнения можно было бы ожидать возникновения такого количества таких фрагментов, которое будет достаточным для загрузки всех ПЭ мультипроцессора.
Т-система ориентирована на поддержку средне зернистого распараллеливания вычислений. При этом размер гранул параллелизма определяется пользователем-элементами распараллеливания являются вычисления вызовов так называемых Т-функций (аналоги из традиционных языков программирования: функции, подпрограммы).
С точки зрения входного языка элементами распараллеливания являются Т-функции. При этом, входной язык по сути является строго функциональным. Однако тела Т-функций могут быть запрограммированы на императивном языке. Данная возможность, несомненно, является привлекательной для программистов, работающих, например, в области численного анализа-не только потому, что их обычно отпугивает традиционный синтаксис функциональных языков программирования, но и вследствие предоставляющейся возможности использовать при реализации Т-функций значительную часть уже существующих традиционных алгоритмических решений.
В каждый момент времени состояние процесса вычисления представлено
в виде сети, узлами которой являются процессы (вызовы
Т-функций) и данные, расположенные в звеньях-тегированных
участках памяти фиксированного размера. Дуги, объединяющие
звенья в сеть представляются в виде особого рода указателей.
В начале вычисления сеть состоит из одного корневого процесса.
Узел-процесс соответствует некоторому вызову Т-функции. Процесс
имеет:
- несколько (возможно ни одного) входов-аргументов Т-функции и вспомогательных Т-переменных;
- несколько (по крайней мере-один) выходов-результатов Т-функции.
Звенья-потребители содержат так называемые невычисленные значения. Если некоторый процесс попытается использовать такое значение для вычисления выражения, его выполнение прервется, и он будет объявлен "неготовым к выполнению". Когда соответствующее значение будет вычислено и звено-потребитель получит обычное значение, процесс перейдет в состояние готовности, и его выполнение может быть продолжено. Данный механизм является единственным механизмом синхронизации процессов.
Процессы составляют активную часть сети при ее трансформации. Выполняясь, процесс создает новые данные, а также модифицирует и/или деактуализирует свои собственные данные. Кроме того, выполняющийся процесс может создать новые фрагменты сети за счет вызова Т-функций. При этом порождаются новые процессы, им передаются в качестве входов (аргументов) фрагменты уже имеющейся сети а их выходы соединяются дугами с звеньями-потребителями.
Т-функции являются "чистыми функциями", побочные эффекты запрещены. Это дает возможность распределять процессы между процессорами и, таким образом, распараллеливать выполнение вычислений.
Требования Т-системы к аппаратному и программному окружению
Т-система спроектирована и реализована таким образом, что она
представляет собой распределенную систему программирования, рассчитанную
на работу в следующей программно-аппаратной среде: сильно связанная
сеть (с протоколом IP) процессорных модулей, работающих
под управлением операционной системы Linux.
Рисунок 1. Аппаратное исполнение ВС
Функционирование Т-системы в составе вычислительной системы (ВС), основывающейся в части аппаратуры на прототипе комплекса аппаратных средств мультипроцессора обеспечивается следующим:
- прототип комплекса аппаратных средств мультипроцессора представляет собой совокупность ПЭ на базе микропроцессоров фирмы Intel серий Pentium PRO и Pentium II (вычислительная часть аппаратуры ВС: "HW для вычислений"-см. Рисунок 1), объединенную в сильно связанную аппаратную сеть с использованием коммуникационной аппаратуры класса Fast Ethernet (коммуникационная часть аппаратуры ВС: "HW для коммуникаций" и "HW соединения"- см. Рисунок 1);
- низкоуровневое программное обеспечение ВС обеспечивает функционирование ОС Linux в вычислительной части аппаратуры ВС и реализацию IP-протокола на коммуникационной части аппаратуры ВС;
- тем самым, на базовом уровне программирования, ВС представляет собою сильно связанную IP-сеть Linux-машин (см. Рисунок 2).
Техническое решение по реализации базового уровня программирования ВС в виде сильно связанной IP-сети Linux-машин среди прочего обусловлено следующим:
Рисунок 2. Базовый уровень программирования ВС
- Unix на сегодняшний день стал одной из самой распространенной операционной системой высокопроизводительных ЭВМ. Linux является наиболее надежной, мобильной, бурно развивающейся и эффективной ветвью Unix-а. Привлекательной чертой Linux-а является ее статус public domain (достояние общества). Система доступна в Internet с полным набором исходных текстов и является свободной (бесплатной). Систему сопровождают и развивают ее пользователи, среди которых много высококвалифицированных программистов. Новые версии ядра Linux-а выпускаются в среднем раз в две недели.
- IP-сеть Linux-машин поддерживает возможности адресации любой Linux-машины и передачи данных (с выполнением необходимой маршрутизации) между двумя произвольными Linux-машинами в этой сети. Таким образом, на логическом уровне IP-сеть можно рассматривать как полный (каждый с каждым) набор двухточечных соединений и не решать проблемы маршрутизации и передачи данных в Т-системе-эти проблемы уже решены на уровне IP-протокола. Это не означает, что конструкция и физическая топология сети не влияют на производительность ВС: конечно, сеть с небольшой задержкой и высокой пропускной способностью лучше, чем с большой задержкой и низкой пропускной способностью. Однако, это проблемы не рассматривались при реализации Т-системы-считалось, что они учтены при реализации аппаратных средств и низкоуровневого ПО ВС.
- IP-сеть Linux-машин поддерживает разнообразные сетевые возможности (программный сервис): распределенную разделяемую файловую систему (NFS), возможности удаленного запуска задач (RCP/RSH), различные средства компьютерных телекоммуникаций (Telnet, ftp, WWW) и пр. Тем самым, снимается проблема обеспечения ВС многими базовыми средствами ПО.
- Linux поддерживает режим крупноблочного распараллеливания ("каждой задаче-свой процессор") для многопроцессорных установок с общей памятью. Таким образом поддерживается одновременное исполнение в рамках одного мультипроцессорного ПЭ нескольких пользовательских процессов: вычислительная часть ПЭ ВС по сути является многопроцессорной Linux-машиной, содержащей [1..4] микропроцессоров класса Pentium P6 и общую для них память.
- Для вычислительных установок класса "IP-сеть Linux-машин",
а значит и для ВС, имеется богатый набор реализаций (как правило,
свободных-бесплатных):
- прикладных пакетов (редакторы текстов, системы поддержки проектов, графические пакеты и т.д.) и систем программирования (C, C++, Fortran, ADA, Lisp, Refal Plus, Gofer и т.д.);
- систем параллельного программирования PVM, MPI и пр., реализующих различные модели ручного статического распараллеливания, которые могут быть прекрасным дополнением к Т-системе в некоторых областях использования ВС.
- Т-система по своему построению является переносимой системой,
способной выполняться не только на ВС, но и на любой вычислительной
установке, которая является (или может быть приведена к виду)
IP-сети Linux-машин. Это свойство, в частности, обеспечивает
работоспособность Т-системы как на различных конфигурациях ВС,
так и на будущих модификациях ВС.
В данном разделе изложены и обоснованы следующие технические решения, использованные для реализации Т-системы:
- Т-система реализует автоматическое динамическое распараллеливание программ.
- Используется модель представления процесса вычислений в виде процесса автотрансформации вычислительной сети. Для представления вычислительной сети в памяти ВС используются списковые структуры звеньев.
- Реализуется средне зернистое распараллеливания программ. Фрагментами параллелизма являются тела Т-функций. Они определяются программистом при описании алгоритма на Т-языке.
- Т-язык является чистым функциональным языком по своей природе. Однако для определения тел Т-функций используется традиционная императивная нотация.
- Т-система предназначена для исполнения в следующей аппаратно-программной
среде: IP-сеть Linux-машин. Аппаратные средства и низкоуровневое
ПО ВС в совокупности являются тесно связанной (быстрой) IP-сетью
Linux-машин. При этом:
- В каждом ПЭ (Linux-машине) выполняется один или несколько экземпляров Т-системы, являющихся в терминах ОС Linux процессами пользовательского уровня.
- Каждый из этих экземпляров Т-системы (соисполнителей) имеет возможность обмениваться сообщениями со всеми соисполнителями, работающими в рамках той же задачи пользователя. Для этого используются средства, предоставляемые программным интерфейсом сетевого протокола IP.
- Каждый экземпляр Т-системы ответственен за локальную организацию вычислений в виде автотрансформации вычислительной сети и за взаимодействия с другими соисполнителями.
- Совокупность всех экземпляров Т-системы образует распределенную операционную среду параллельного выполнения задачи пользователя.
Основные структуры данных. Т-структуры
Вычислительная сеть в Т-системе представлена списковыми структурами специального вида, которые мы будем называть Т-структурами. Т-структуры состоят из звеньев.
Рисунок 3. ЗвеноЗвено является элементарной единицей памяти, используемой при построении Т-структур (см. Рисунок 3). Размер звена-12 байтов-достаточен:
- для того, чтобы разместить любое скалярное значение (см. Рисунок 4) или специальный указатель на другую Т-структуру-держатель Т-структуры;
- для организации системных информационных структур.
Каждое звено содержит тэг, который определяет, какого рода данные содержатся в данном звене. Подробнее тэги звеньев будут описаны ниже.
Рисунок 4. Примеры звеньев со скалярными значениямиПростейшей Т-структурой является одиночное звено со скалярным значением (см. Рисунок 4.)
Другие примеры одиночных звеньев-потребители (звенья с неготовыми значениями) и держатели-будут рассмотрены ниже.
Рисунок 5. Примеры мультизвеньевЕсли объем памяти, необходимый для хранения скалярной информации превышает 10 байтов, то для хранения данной информации нужно использовать бестэговую область (мультизвено) необходимого размера. Мультизвено (см. Рисунок 5) состоит из расположенных подряд N+1 звена. Первое звено является заголовком бестэговой области (мультизвена) и имеет тэг со значением TTAG_PACKED. Непосредственно за данным звеном следует несколько (N0) бестеговых звеньев, образующих область (до 12N байтов) для хранения произвольных данных (например, для хранения массива целых-см. Рисунок 5(а),- или строки символов-см. Рисунок 5(б),- и т.п.).
Везде далее не будет смешиваться понятия звена (12 байтов) и мультизвена (12(N+1) байтов).
Рисунок 6. Примеры Т-структур и их держателейТ-структурами будем называть расположенные подряд одиночные звенья и мультизвенья.
Рисунок 7. Потребители и поставщик
Звено-держатель-указатель специального вида, удерживающий (указывающий на) Т-структуру-имеет тэг TTAG_HOLDER и содержит адрес первого звена в Т-структуре и количество звеньев в ней.
Заметим, что сам по себе держатель является одиночным звеном. Следовательно держатель может входить в некоторую Т-структуру).
Примеры Т-структур и их держателей-см. Рисунок 6.Невычисленные значения, потребители, поставщики, кольца.
Еще одним случаем одиночного звена является звено-потребитель. Звено-потребитель содержит невычисленное значение, то есть такое значение, которое должно быть в дальнейшем вычислено как результат (один из выходов) процесса)-одного из совокупности процессов, параллельно выполняющихся в Т-системе.
Для данного потребителя будем называть поставщиком тот выход процесса, значение которого после завершения вычислений примет потребитель. У каждого потребителя обязательно имеется ровно один поставщик, и у поставщика может быть произвольное количество потребителей (в том числе и ни одного).
На диаграммах будем обозначать отношение "поставщик-потребитель" особым видом связей (дуг)-см. Рисунок 7.
Такое изображение отражает только логические связи, а не реальное размещение указателей в звеньях. Действительно, у одного поставщика может быть любое количество потребителей (например, три-см. Рисунок 7- или больше). А в звене можно разместить только два указателя. Таким образом, логические связи между поставщиком и потребителем необходимо представить при помощи такого размещения указателей в поставщике и потребителях, что:- из каждого звена-потребителя можно локализовать (найти адрес)
соответствующего звена-поставщика;
Рисунок 8. Представление отношения "поставщик-потребители" при помощи кольца- из звена-поставщика можно локализовать (найти адрес) любого его потребителя;
- при этом в каждом звене расположено не более двух указателей.
Всем этим условиям удовлетворяет двунаправленный кольцевой список (везде далее-кольцо) который и используется в Т-системе для представления отношения поставщик-потребители между звеньями-см. Рисунок 8.
В общем случае в кольце могут быть следующие звенья:- Ровно одно звено поставщик. Звенья-поставщики являются
системными звеньями и могут быть элементами только системных Т-структур:
"процесс" и "входной разъем".
Тэг звена-поставщика имеет одно из следующих трех значений:
- TTAG_OUT-выход процесса.
- TTAG_OUT_FWD-фиктивный выход процесса.
- TTAG_OUT_INCONN-выход входного разъема.
Рисунок 9. Примеры колец с системными звеньями- Несколько (возможно ни одного) звеньев потребителей.
Тэг звена-потребителя имеет одно из следующих двух значений:
- TTAG_NOTREADY-потребитель является обычным одиночным звеном и может входить в любые Т-структуры (как пользовательские, так и системные).
- TTAG_NOTREADY_OUT-системное звено-потребитель, элемент системной Т-стуктуры "выходной разъем", аргумент выходного разъема.
- Вспомогательные системные звенья. Для реализации операций,
связанных с отношением "поставщик-потребитель" в кольце
дополнительно могут находиться вспомогательные системные звенья
с тэгами:
- TTAG_ALTQUE-системное звено, предназначено для реализации системного вызова ALT;
- TTAG_SRCPROC-системное звено, удерживает процесс, выход которого является поставщиком в данном кольце.
Достаточно общие случаи колец изображены ниже-см. Рисунок 9:
Рисунок 10 содержит изображение общей структуры элемента кольца
Рисунок 10. Звено-элемент кольцаПроцесс
Рисунок 11. Процесс
Системная Т-структура процесс состоит из следующих звеньев (см. Рисунок):- звенья Out1,...,Outnout (тег TTAG_OUT)-один или несколько выходов процесса (поставщики);
- звено ListMemb (тег TTAG_LISTMEMB)-элемент системного списка для постановки процесса в системный список "очередь готовых процессов" или в системный список "очередь пренатальных процессов" (готовых, но еще не выполнявшихся процессов);
- звено Alt (тег TTAG_ALT) для построения ALT-списка;
- звено Proc (тег TTAG_PROC или TTAG_PROC_PRENATAL)-удерживает всю Т-структуру процесса (см. Рисунок 11 и Рисунок 12);
- бестэговое звено TThread-служит для сохранения состояния процесса (см. Рисунок 12);
- звенья In1,...,Innin (с любыми несистемными тегами: TTAG_VOID, TTAG_PACKED, TTAG_HOLDER, TTAG_NOTREADY)-один или несколько входов процесса (аргументы и вспомогательные переменные).
С каждым процессом связан свой поток управления (thread), соответствующий выполнению Т-функции пользовательской программы. Звено TThread содержит информацию об этом потоке управления:- Для пренатального процесса в звене TThread содержится информация, необходимая для инициализации процесса-идентификация Т-функции, которая связана с данным процессом.
- Для выполнявшегося и приостановленного процесса в звене TThread
содержится указатель на специальную область в которой сохранено
вся информация, необходимая для продолжения выполнения приостановленного
потока управления. Более точно: при любом обращении процесса
к Т-системе состояние выполнения его потока управления сохраняется
в специальной области сохранения (определяется библиотекой TTHREAD)
и в звене TThread сохраняется указатель на данную область.
Рисунок 12. Пара звеньев Proc и TThread
Рисунок 13. Системные звенья, содержащие уникальную идентификацию OutId Т-структуры, передаваемой при помощи разъемовВходные и выходные разъемы предназначены для передачи Т-структур между различными экземплярами Т-систем (соисполнителями). Каждая предназначенная к передаче (при помощи разъемов) Т-структура имеет уникальную идентификацию OutId. Передача Т-структуры с идентификатором OutId из соисполнителя Б соисполнителю А оформляется при помощи пары разъемов (см. Рисунок 14):
- Выходной разъем (в Т-системе Б) состоит из пяти звеньев:
- звено (с тэгом TTAG_VOID) содержащее идентификатор ExeIdА соисполнителя А;
- два звена ListMemb, RackMemb (с тэгами TTAG_LISTMEMB) используемые для постановки разъема в различные системные списки разъемов;
- звено (с тегом TTAG_OUTCONN) содержащее OutId (см. Рисунок 13);
- звено In-вход разъема (возможные тэги: TTAG_VOID, TTAG_HOLDER,
TTAG_NOTREADY_OUT).
Рисунок 14. Пара разъемов для передачи Т-структуры- Входной разъем (в Т-системе А) состоит из пяти звеньев:
- звено Out (с тэгом TTAG_OUT_INCONN-до передачи, с тэгом TTAG_VOID или TTAG_HOLDER-после передачи данных)-выход разъема;
- два звена ListMemb, RackMemb (с тэгами TTAG_LISTMEMB) используемые для постановки разъема в различные системные списки разъемов;
- звено (с тегом TTAG_INCONN) содержащее OutId (см. Рисунок 13);
- звено (с тэгом TTAG_VOID) содержащее идентификатор ExeIdБ соисполнителя Б.
Таким образом, все входные и выходные разъемы образуют пары: каждому входному разъему отвечает ровно один выходной разъем.
Как входной, так и выходной разъем могут находиться в одном из двух основных состояний:- состояние "данные не запрошены". В этом случае звено разъема, содержащее его OutId ("центральное" звено разъема), имеет тег TTAG_OUTCONN-в случае выходного разъема или тег TTAG_INCONN-в случае входного разъема;
- состояние "данные запрошены" (Requested). В этом случае центральное звено разъема будет иметь тег TTAG_OUTCONN_REQ или TTAG_INCONN_REQ - для выходного и входного разъемов соответственно.
Рисунок 15 (а) содержит изображение процесса П в некотором соисполнителе (Т-системе А) и еще один соисполнитель-Т-система Б. Рассмотрим процесс передачи процесса П из Т-системы А в Т-систему Б.
В момент передачи существует возможность, что один или несколько выходов Outi передаваемого процесса П станут поставщиками для новых получателей, расположенных в соисполнителе Б, еще до завершения передачи туда процесса П. Поэтому заранее необходимо иметь в соисполнителе Б "временную замену" для каждого из таких поставщиков Outi. Для этого в соисполнителе Б создаются системные структуры "фиктивный выход процесса" (см Рисунок 15 (б)). Фиктивный выход процесса состоит из трех звеньев:- звено Out (с тэгом TTAG_OUT_FWD) является звеном-поставщиком и заменяет собой один из выходов Outi процесса П (находящегося в состоянии передачи соисполнителю Б);
- звено ListMemb (с тэгом TTAG_LISTMEMB) используется для постановки фиктивного выхода в системный список фиктивных выходов;
- звено OutId (с тэгом TTAG_OUTID_FWD) содержит OutId выходного разъема- потребителя выхода Outi процесса П.
После завершения передачи процесса П (см Рисунок 15 (в)) Т-структура "фиктивный выход процесса" будет заменена реальным поставщиком-выходом Outi процесса П.
Системная Т-структура кольцевой ALT-список порождается при выполнении системного вызова ALT в некотором процессе А. В список входят следующие структуры (см. Рисунок 9 (б, в)):
- Звено Alt (тег TTAG_ALT) процесса А.
- Т-структуры AltQ-AltA из пары звеньев каждая: звено AltQ с тэгом TTAG_ALTQUE и звено AltA с тегом TTAG_ALTALT.
При этом, звенья AltQ являются получателями для некоторых поставщиков (значения от которых ожидает процесс А), а звенья AltA образуют двунаправленный кольцевой ALT-список со звеном Alt процесса А.
Таким образом, в каждом ALT-списке всегда присутствует ровно одно звено Alt некоторого процесса А и одна или несколько Т-структур AltQ-AltA.
Процесс А, звено Alt которого ввязано в некоторый ALT-список, является неготовым к исполнению. При выполнении некоторым поставщиком попытки разместить значение в каком-либо звене AltQ из этого ALT-списка, происходит следующее:
- ALT-список разрушается.
- Процесс А переводится в состояние "готов к исполнению".
Рисунок 15. Передача процесса. Фиктивные выходы процесса
Рисунок 16. Системные звенья-элементы двунаправленных списков: ALT-списка, системных очередейТ-система использует различные системные очереди для удержания и обработки различных объектов (Т-структур):
- очередь готовых к исполнению процессов;
- очередь пренатальных процессов;
- очередь фиктивных выходов;
- очереди входных и выходных разъемов;
- вспомогательные системные очереди.
Все системные очереди состоят из следующих звеньев (см. Рисунок 16):- Голова очереди (тег TTAG_LISTHEAD).
- Несколько (возможно ни одного) элементов очереди-звеньев с тегом TTAG_LISTMEMB в составе удерживаемых в очереди Т-структур.
Голова очереди и элементы очереди провязаны в двунаправленный кольцевой список. Голова очереди удерживается системным указателем, расположенным вне звеньевой системной области памяти.Каждое звено содержит тэг, который определяет, какого рода данные содержатся в данном звене. Тэг звена может иметь одно из значений из перечислимого типа ttag (см. ниже Таблица 1).
Таблица 1. Тэги звеньев Значение тэга Описание TTAG_VOID Звено содержит скалярное значение от 1 до 10 байтов. Для уточнения типа значения в приложениях может быть использован 11-тый байт звена. См. Рисунок 4. TTAG_PACKED Звено является заголовком бестэговой области (мультизвена): непосредственно за данным звеном следует несколько (N0) бестеговых звеньев, образующих область (до 12N байтов) для хранения произвольных данных (например, для хранения массива целых или строки символов и т.п.). См. Рисунок 5. TTAG_HOLDER Звено-держатель: указатель специального вида, удерживающий (указывающий на) Т-структуру. См. Рисунок 6. TTAG_NOTREADY Звено-потребитель: содержит невычисленное значение и входит в двунаправленный кольцевой список звеньев-кольцо. См. Рисунок 7-Рисунок 10. В кольце присутствует ровно одно звено-поставщик. Кольцо содержит все звенья-потребители, связанные отношением "поставщик-потребитель" с данным звеном-поставщиком. Это позволяет выполнять операцию передачи данных от поставщика всем его потребителям. TTAG_NOTREADY_OUT Системное звено-потребитель, элемент системной Т-стуктуры "выходной разъем": аргумент выходного разъема. См. Рисунок 7-Рисунок 10. TTAG_OUT TTAG_OUT_FWD TTAG_OUT_INCONN Звенья-поставщики являются системными звеньями, элементами системных Т-структур: "процесс" и "входной разъем". См. Рисунок 7-Рисунок 10. Звено с тэгом TTAG_OUT-выход процесса.
Звено с тэгом TTAG_OUT_FWD-фиктивный выход процесса.
Звено с тэгом TTAG_OUT_INCONN-выход входного разъема.
TTAG_ALT TTAG_ALTQUE TTAG_ALTALT Системные звенья, предназначены для реализации системного вызова ALT. См. Рисунок 9-Рисунок 11, Рисунок 16. TTAG_PROC TTAG_PROC_PRENATAL Системное звено, элемент системной Т-структуры "процесс". См. Рисунок 11, Рисунок 12 TTAG_OUTCONN_REQ TTAG_OUTCONN Системное звено, элемент системной Т-структуры "выходной разъем". Два варианта тэга соответствуют двум состояниям выходного разъема: выдан или нет запрос на передачу данных. См. Рисунок 13-Рисунок 15. TTAG_INCONN_REQ TTAG_INCONN Системное звено, элемент системной Т-структуры "входной разъем". Два варианта тэга соответствуют двум состояниям входного разъема: выдан или нет запрос на передачу данных. См. Рисунок 13-Рисунок 15. TTAG_LISTHEAD TTAG_LISTMEMB Системные звенья, служащие для построения системных очередей. См. Рисунок 16. Звено с тэгом TTAG_LISTHEAD-голова очереди, звено с тэгом TTAG_LISTMEMB-элемент очереди (входит в некоторую системную Т-структуру).
TTAG_SRCPROC Системное звено, особый случай элемента кольца. См. Рисунок 9, Рисунок 10. TTAG_OUTID_FWD Системное звено, элемент системной Т-структуры "фиктивный выход процесса". См. Рисунок 15. TTAG_SAME Системный тэг. Компоненты Т-системы
TThreads: поддержка множественных потоков управления
Основные принципы поддержки множественных потоков управления в Т-системеКак уже упоминалось в главе 3, с каждым процессом в Т-системе связан свой поток управления (thread), соответствующий выполнению Т-функции пользовательской программы. Таким образом, в рамках одного соисполнителя (Т-системы), являющегося с точки зрения ОС Linux обычным пользовательским процессом, должны сосуществовать множественные потоки управления.
Используемый в Т-системе аппарат множественных потоков управления, основывается на следующих принципах:- каждый поток управления имеет собственное состояние, включающее
в себя:
- содержимое регистров микропроцессора;
- содержимое стека потока управления: его автоматические переменные и фреймы вызовов обычных функций (не Т-функций);
- набор собственных статических переменных потока управления, доступных с использованием глобального указателя p_ttstaticals;
- наряду с обычными потоками управления существует выделенный, который называется главным потоком управления;
- обычные потоки управления взаимодействуют с главным потоком управления, используя системные вызовы;
- при выполнении системного вызова состояние текущего потока управления сохраняется в специально выделенной для этого области, и управление передается главному потоку управления;
- главный поток управления исполняет заказы обычных потоков управления, переданные ему с использованием системных вызовов;
- главный поток управления осуществляет планирование обычных потоков управления. После выполнения очередного системного вызова главный поток управления принимает решение о том, какой поток управления будет выполняться в дальнейшем и активизирует его.
Поддержка аппарата множественных потоков управления, основанного этих принципах, стандартными средствами ОС Linux в настоящее время не поддерживается и реализуется отдельной компонентой Т-системы-TThreads.Обычный поток управления в TThreads описывается структурой tthread. Эта структура включает в себя:
- информацию о том, активизировался ли (выполнялся ли) данный поток управления;
- для не выполнявшегося (пренатального) потока управления-информацию, необходимую для активизации потока управления: идентификацию функции, которая является стартовой функцией данного потока управления;
- для выполнявшегося и приостановленного потока управления в звене TThread содержится указатель на структуру tt_user данного потока управления.
Структура tt_user включает в себя:- содержимое стека потока управления;
- собственные статические переменные потока управления;
- структуру данных, предназначенную для обмена информацией между данным потоком управления и главным потоком управления;
- область памяти, предназначенную для сохранения регистров микропроцессора в момент приостановки данного потока управления (в момент системного вызова). Эта информация может быть использована впоследствии для восстановления состояния регистров микропроцессора и продолжения выполнения ранее приостановленного потока управления.
При написании программ на языке Си определение потока включает в себя следующий набор определений:- определение структуры, содержащей собственные статические переменные потока управления;
- определение стартовой функции потока управления. При активизации потока управления управление будет передано этой функции. Стартовая функция потока управления должна быть определена как функция без параметров, возвращающая целое значение;
- определение структуры tt_descr, используемой при активизации потока управления.
Структура tt_descr содержит следующие поля:- поле fp_start-указатель на стартовую функцию потока управления;
- поле p_staticals-указатель на инициализированную статическую структуру, которая содержит исходное состояние собственных статических переменных потока управления;
- поле i_staticals_size-размер набора собственных статических переменных потока управления в байтах-целого типа;
- поле i_stacksize-объем стека (в байтах), необходимый для выполнения данного потока управления-целого типа;
- другие дополнительные поля.
Структура tt_descr используется при активизации потока управления (из пренатального состояния). Доступ структуре tt_descr, соответствующей данному потоку управления, осуществляется путем индексации глобальной таблицы tt_task двумя значениями целого типа: номером модуля и номером потока управления в модуле. Таким образом, для активизации потока управления достаточно этих двух значений, которые и представляют собой состояние потока управления, находящегося в пренатальной форме.Программный интерфейс TThreads
Интерфейс с TThreads представляет собой набор функций, реализующих следующие операции:
- инициализацию системы поддержки множественных потоков управления;
- создание нового потока управления;
- активизацию потока управления и продолжение выполнения приостановленного потока управления;
- взаимодействие обычных потоков управления с главным потоком управления;
- завершение потока управления.
Ниже подробно рассмотрена каждая из этих операций.Для инициализации всей системы поддержки множественных потоков управления используется вызов функции init_tthreads (без параметров). Ниже приведен ее прототип на языке Си:
void init_tthreads (void);
Данная функция выделяет в стеке пользовательского процесса 2 области памяти:
- область памяти для размещения стека главного потока управления,
- область памяти для размещения стека, предназначенного для обработки внешних программных прерываний-сигналов, в терминах ОС Linux.
Кроме того, она инициализирует механизм выделения в стеке пользовательского Linux-процесса областей памяти для обычных потоков управления.
Инициализация TThreads должна быть выполнена до любых вызовов других интерфейсных функциям TThreads. После вызова init_tthreads текущим потоком управления является главный поток управления.Создание нового потока управления
Для создания нового потока управления используется вызов функции init_tt. В качестве параметров этой функции передаются:
- указатель на структуру tthread;
- два значения целого типа: номер потока управления в модуле и номер модуля.
Ниже приведен прототип этой функции на языке Си:struct tthread * init_tt (struct tthread * ttp, int i_fnum, int i_modnum);
Функция init_tt проверяет корректность переданных ей в качестве аргументов номера модуля и номера потока управления в модуле и в случае ошибки возвращает нулевой указатель (NULL). В случае, если аргументы корректны, функция производит инициализацию структуры tthread таким образом, чтобы она содержала полную информацию о новом потоке управления. Созданный таким образом поток управления находится в пренатальном состоянии.
В качестве результата в этом случае возвращается первый аргумент функции-указатель на инициализированную функцией структуру tthread.Вызов функции swtch_tt может быть использован:
- для активизации потока управления, находящегося в пренатальном состоянии
- или для продолжения выполнения ранее приостановленного потока управления.
Прототип данной функции на языке Си выглядит следующим образом:int swtch_tt (struct tthread * ttp, int i_val);
Функция swtch_tt предназначена только для вызова на фоне главного потока управления. В качестве параметров ей передаются:
- указатель на структуру tthread того потока управления, которому передается управление;
- значение целого типа, которое будет передано потоку управления в качестве результата системного вызова-в том случае, если функция swtch_tt вызвана для продолжения выполнения ранее приостановленного потока.
Если функция swtch_tt вызвана для активизации потока управления, находящегося в пренатальном состоянии, то в этом случае, основываясь на данных структуры tthread будет выполнен запуск потока управления.Поддержка взаимодействия потоков управления с главным потоком управления
Потоки управления взаимодействуют только с главным потоком управления. Для обеспечения этого взаимодействия используются системные вызовы. Аппарат системных вызовов поддерживается функцией call_ttmain.
int call_ttmain (int i_val)
Параметр (int i_val) определяет номер системного вызова и передается в главный поток управления. Для передачи дополнительной информации нужно использовать поле tt_data структуры tt_user.Главный поток управления может завершить любой другой поток управления при помощи вызова функции destroy_tt:
void destroy_tt (struct tthread * ttp)
Параметр (struct tthread * ttp) определяет тот поток управления, который надо завершить.Вычислительная компонента является основной компонентой Т-системы, поддерживающей реализацию используемой модели вычисления. Данная компонента реализована как часть главного потока управления и реализует следующий набор системных вызовов:
- SPARK-порождение нескольких новых процессов и построение соответствующих отношений "поставщик-потребитель";
- DROP-очистка звена от текущего значения (в том числе-от неготового значения, то есть вывод звена из множества потребителей некоторого поставщика);
- ASSIGN-копирование значения из одного звена в другое (в том числе-копирование неготового значения);
- ALT-ожидание готовности одного из нескольких звеньев;
- SEND-передача значения от поставщика потребителям;
- SEND_WITH_RELINK-передача значения от поставщика потребителям с возможностью организации потоковой передачи;
- REALEXIT-завершение всего процесса вычислений (всех соисполнителей) Т-задачи;
- NOOP-временная приостановка процесса с одновременной активизацией главного главному потоку управления.
Главным в ряду системных вызовов, приводящих к трансформации вычислительной сети, безусловно является системный вызов SPARK, предназначенный для организации комбинированного вызова нескольких функций входного языка. Мы рассмотрим наиболее простой случай, организацию вызова одной функции.
Для организации вызова T-функции, имеющей N параметров и M возвращаемых значений, порождается процесс с соответствующим числом входов и выходов (см. Рисунок 17). Для собственных нужд процесс может иметь дополнительные входы (локальные Т-переменные).
На входы процесса подаются параметры вызываемой функции, а его выходы рассматриваются как поставщики возвращаемых Т-функцией значений. На входы процесса могут быть поданы (см. Рисунок 17):- скалярное значение (1), например, литера 'A';
- держатель списка (2);
- ссылка на выход другого процесса (3) (неготовое значение);
а выходы могут быть присоединены к различным потребителям, в числе которых могут быть:- звено, входящее в состав Т-структуры (4);
- вход процесса (5), выполняющего системный вызов SPARK.
Рисунок 17. Пример выполнения системного вызова SPARK в процессе П
Поставщики и потребители-фундаментальные понятия вычислительной сети. Поставщиками обычно являются выходы процессов, потребителями могут быть практически любые звенья, в их числе и входы любых процессов. Когда мы говорим, что поставщик присоединен к потребителю, мы подразумеваем, что на поставщик возложена обязанность сформировать в будущем некоторое значение и передать его указанному потребителю. Мы будем говорить, что звено, являющееся потребителем, содержит невычисленное значение, в отличие от настоящих (вычисленных) значений, таких как числа и держатели.
Во время выполнения процесса могут возникнуть условия, при которых его выполнение не может быть продолжено. В этом случае процесс приостанавливается (засыпает), а когда упомянутые условия исчезают, возобновляется (будится), то есть объявляется готовым. Объявление процесса готовым подразумевает, что процесс попадает в очередь готовых процессов, откуда он со временем будет выбран главным потоком управления (Т-системой) для выполнения.
Вновь созданный системным вызовом SPARK процесс объявляется пренатальным, то есть готовым к выполнению, но "не сделавшим еще первого вздоха"-не выполнившим ни единой команды. Пренатальные процессы оказываются в отдельной очереди, откуда они выбираются для выполнения в том случае, если основная очередь готовых процессов оказывается пустой-не содержащей ни единого процесса. Порождающий процесс после завершения вызова SPARK продолжает свое выполнение.
Среди сетевых преобразований наиболее важную роль играют манипуляции с невычисленными значениями. Такие звенья, как входы процессов или элементы внешних списков, во многом подобны внутренним переменным, и могут быть частью различных выражений, например, арифметических. Если в момент вычисления арифметического выражения звено содержит настоящее значение, никаких затруднений не возникает. Если же в звене хранится невычисленное значение, процесс, вычисляющий выражение, должен быть приостановлен до тех пор, пока значение не будет вычислено. Существуют, однако, некоторые операции, использующие невычисленные значения, которые могут быть выполнены без приостановки процесса. В число таких операций входят некоторые манипуляции со списками, передача параметров новому процессу, присваивание другому входу или элементу списка, пересылка значения в собственный выход.
Рисунок 18. Системный вызов DROP(x)
Ниже мы даем описание остальных системных вызовов, приводящих к трансформации вычислительной сети.Системный вызов DROP(x) приводит к очистке звена x от текущего невычисленного значения. В этом случае происходит разрушение связи между потребителем x и его поставщиком (см. Рисунок 18). Все байты звена x обнуляются, а тэг устанавливается в значение TTAG_VOID.
Системный вызов DROP(x) не меняет содержимое звена x, если данное звено содержит вычисленное значение.
Рисунок 19. Различные варианты выполнения системного вызова ASSIGN(x,y)
в процессе ПСистемный вызов ASSIGN(x,y) выполняет копирование значения из звена y в звено x. При этом (см. Рисунок 19):
- Звено x теряет свое прежнее значение. Если это было невычисленное значение, то связь между x и поставщиком разрушается.
- После этого значение звена y копируется в звено x. Если это невычисленное значение, то x становится потребителем того же поставщика, что и y.
Заметим, что семантика вызова ASSIGN(x,y) одна и та же во всех случаях: x теряет свое прежнее значение и получает то значение, что имеет звено y.Системный вызов ALT(x,y,...z) выполняемый в процессе П приводит к "засыпанию" процесса П (переходу его в неготовое к выполнению состояние) до наступления события "по крайней мере одно из звеньев x, y, ... z имеет готовое значение".
Заметим, что если в момент выполнения системного вызова одно из звеньев x, y, ... z имеет готовое значение, то "засыпание" процесса П не происходит.
Важный частный случай системного вызова-ALT(x)-имеет алиасное имя: WAIT(x). Системный вызов WAIT(x) гарантирует, что после его выполнения звено x имеет готовое значение.
Единственные операции, которые можно выполнять с неготовыми значениями-это их передача (ASSIGN, SEND), разрушение (DROP) и опрос тэга. Поэтому, системный вызов WAIT(x) следует использовать перед каждой операцией, требующей готовности значения звена x (например, перед арифметическими операциями с содержимым звена x). Исключением являются те ситуации, когда у программиста-или у компилятора с языка высокого уровня-есть уверенность, что звено x заведомо содержит готовое значение.
Процедуры реализации системного вызова ALT рассмотрены в разделах 3.2.4 и 3.2.5.4.
Рисунок
20. Различные варианты выполнения системного вызова SEND(x,y)
в процессе ПСистемный вызов SEND(x,y), выполняемый в процессе П, передает значение звена x всем потребителям выхода y процесса П (см. Рисунок 20).
В результате выполнения вызова SEND(x,y) может быть передано как готовое, так и неготовое значение, находящееся в звене x. При рассылке неготового значения, потребители поставщика y становятся потребителями того же поставщика, что и у звена x.
Заметим, что семантика вызова SEND(x,y) одна и та же во всех случаях: все потребители поставщика y получают то значение, что имеет звено x.
После выполнения данного вызова выход y теряет всех своих потребителей.Системный вызов SEND_WITH_RELINK
Системный вызов SEND_WITH_RELINK(x,y,z,c), выполняемый в процессе П, является модификацией вызова SEND, описанного в разделе 4.2.5.
(а) Выполнение системного вызова SEND_WITH_RELINK(x,y,z,c)
в процессе П
(б) Передача очередного элемента списка в процессе потоковой передачи
с использованием системного вызова SEND_WITH_RELINKРисунок 21. Примеры различных вариантов выполнения в процессе П системного вызова
SEND_WITH_RELINK(x,y,z,c)
В отличие от системного вызова SEND, в результате выполнения в процессе П вызова SEND_WITH_RELINK, помимо передачи значения звена х всем потребителям выхода y процесса П, происходит "перепривязка" выхода y к звену c: звено c принимает неготовое значение и становится потребителем выхода y. Выход z процесса П используется при этом в качестве вспомогательного, и всем его потребителям-если таковые имелись-также рассылается значение звена х. После выполнения данного вызова выход y оказывается поставщиком звена c-см. Рисунок 21(а).
Вызов SEND_WITH_RELINK предназначен для реализации в пользовательской программе передачи списков. Рисунок 21(б) содержит изображение примера использования данного системного вызова для реализации потоковой передачи списка.Системный вызов REALEXIT(int err_code), выполняемый в процессе П приводит к завершению всех Т-процессов во всех соисполнителях данной Т-задачи и выдаче системного кода завершения err_code.
Системный вызов NOOP, выполняемый в процессе П приводит к временной приостановке процесса П и активизации главного потока управления. Примером использования данного вызова является библиотечная функция _ut_process_pkt. Обращение к данной функции приводит к временной приостановке процесса П и передаче управления коммутационной компоненте главного потока управления-только в том случае, если от коммутационной компоненты требуется деятельность, связанная с обработкой внешних сообщений. В случае, если на момент выполнения данного системного вызова подлежащие обработке внешние сообщения отсутствуют, приостановки процесса не происходит. Периодические обращения к функции _ut_process_pkt могут использоваться для уменьшения времени реакции соисполнителя на внешние сообщения на фоне выполнения процессов, являющихся особенно "тяжелыми" и длительными по времени гранулами параллелизма.
Компонента управления звеньевой памятью
Все Т-структуры, входящие в состав тех фрагментов общей вычислительной сети, которые расположены в памяти отдельного соисполнителя, находятся в области звеньевой памяти-непрерывном разделе всего адресного пространства соисполнителя, состоящем из расположенных последовательно звеньев. Компонента управления звеньевой памятью поддерживает основные операции работы с памятью, необходимые ядру Т-системы и Т-функциям для построения звеньевых Т-структур:
- захват звеньевой памяти-выделение заданного количества последовательно расположенных звеньев из области звеньевой памяти;
- сборку мусора-неявное освобождение тех расположенных в области звеньевой памяти и захваченных ранее звеньев, которые уже не используются вычислительной сетью.
Рассмотрим каждую из этих операций подробнее.Захват звеньевой памяти производится путем обращения к системной функции alloc_tcell, которой в качестве параметра передается значение целого типа-требующееся число расположенных подряд звеньев:
utcell * alloc_tcell (unsigned i_numcell);
В качестве результата функция alloc_tcell возвращает указатель на первое звено захваченной памяти. В случае, если область звеньевой памяти не содержит затребованного количества свободных последовательно расположенных звеньев, операция захвата памяти вызывает сборку мусора.
Операция захвата памяти является одной из наиболее часто выполняемых Т-системой операций, используемой для построении вычислительной сети. Поэтому важным является требование эффективной реализации этой операции. Одной из мер, принятых для удовлетворения этого требования, является специальная реализация частного случая этой операции-захвата одного звена:utcell * alloc_one_tcell (void);
Используемые в Т-системе структуры данных и механизмы работы с находящимися в звеньевой памяти значениями приводят к невозможности систематического использования явной операции освобождения памяти. Поэтому в момент выделения звеньевой памяти, необходимой для построения очередного фрагмента вычислительной сети, может возникнуть ситуация, при которой область звеньевой памяти не содержит требуемого количества свободных звеньев, расположенных последовательно-см. Рисунок 22 (а). В этом случае компонента Т-системы, ответственная за управление звеньевой памятью, выполняет операцию сборки мусора-поиск и освобождение тех захваченных ранее звеньев, которые на момент проведения сборки мусора уже не используются вычислительной сетью.
В текущей версии Т-системы используется алгоритм сборки мусора, относящийся к классу компактирующих: его применение приводит не только к освобождению не используемых вычислительной сетью звеньев, но и к переносу всех используемых-активных-звеньев в одну непрерывную область, прилегающую к началу звеньевой памяти. При этом алгоритм гарантирует сохранение порядка расположения звеньев: используемые вычислительной сетью звенья, расположенные до сборки мусора последовательно, будут расположены последовательно и в том же порядке и после сборки мусора (см. Рисунок 22). Таким образом, используемый алгоритм позволяет предотвратить фрагментацию звеньевой памяти, не нарушая целостности Т-структур.
Рисунок 22. Компактирующая сборка мусора: состояние области звеньевой памяти до выполнения сборки мусора (а); после выполнения сборки мусора (б).
Компактирующие алгоритмы сборки мусора относятся к разряду "stop-and-copy"-алгоритмов: на время проведения сборки мусора процесс вычислений приостанавливается. Поэтому эффективность реализации такого алгоритма является критической для Т-системы: длительные паузы во время вычислений являются неприемлемыми. Реализация сборки мусора в текущей версии Т-системы использует алгоритм "страничных таблиц", являющийся модификацией известного алгоритма "катящихся таблиц".
Оригинальный алгоритм компактирования мусора по методу "катящихся таблиц" состоит из четырех фаз:- поиска всех активных звеньев и пометки их как активных;
- перемещения всех активных звеньев к одной из границ звеньевой памяти и построения таблицы перемещения звеньев, которая располагается в звеньевой памяти вплотную к ее противоположной границе;
- сортировки таблицы перемещения;
- сканирования всех активных звеньев и коррекции хранящихся в них указателей на основе бинарного поиска в таблице перемещения.
Алгоритм "страничных таблиц", в отличие от алгоритма "катящихся таблиц", предусматривает разбиение звеньевой памяти на участки равной длины-страницы. Данный алгоритм также состоит из четырех фаз:- поиска всех активных звеньев и пометки их как активных (совпадает с первой фазой оригинального алгоритма "катящихся таблиц");
- перемещения всех активных звеньев в каждой странице к одной из границ страницы с одновременным построением вплотную к противоположной границе каждой страницы таблицы перемещения звеньев данной страницы и построением "каталога страничных таблиц" вне звеньевой памяти;
- постраничного сканирования всех активных звеньев и коррекции хранящихся в них указателей на основе бинарного поиска в страничных таблицах перемещения, размер которых значительно меньше, чем размер общей таблицы;
- сдвига массивов активных звеньев, расположенных постранично непрерывно, к одной из границ звеньевой памяти.
Такая модификация исходного алгоритма позволяет заменить потенциально достаточно трудоемкую (пропорциональную по времени n*log(n), где n - общее число ячеек) процедуру сортировки глобальной таблицы перемещения на гораздо менее трудоемкую (пропорциональную по времени k, где k - число активных ячеек) процедуру постраничного сдвига активных ячеек и, таким образом, сократить общее время, затрачиваемое на компактирование.
Наличие сборки мусора является важной особенностью Т-системы. Она, в частности, приводит к необходимости "удержания" в звеньевой памяти данных, необходимых Т-функции для ее вычислений.
Для реализации "удержания" некоторой Т-структуры Т-функция может:- разместить требующуюся Т-структуру в области рабочих звеньевых переменных данной Т-функции (эта область является частью системной Т-структуры "процесс", соответствующей данной Т-функции и "удерживается" звеном Proc Т-структуры "процесс");
- разместить в "удерживаемом" каким-либо образом участке звеньевой памяти держатель требующейся Т-структуры.
Если необходимая Т-функции Т-структура не "удерживается" с использованием одной из описанных выше возможностей, то в момент захвата звеньевой памяти эта Т-структура может быть уничтожена-занимаемая ею память может быть освобождена в процессе сборки мусора. При этом важно помнить, что захват звеньевой памяти может производиться не только Т-функцией, но и ядром Т-системы, поэтому "удержание" необходимо осуществлять не только при захвате памяти, но и при исполнении любого системного вызова, за исключением системных вызовов DROP и ASSIGN, исполнение которых не требует захвата дополнительной памяти и не может вызвать сборку мусора.
Еще одним важным обстоятельством, связанным с использованием компактирующего алгоритма сборки мусора, является изменение адресов "удерживаемых" в звеньевой памяти Т-структур в результате выполнения сборки мусора. В том случае, если доступ к Т-структуре осуществляется с использованием указателя на структуру, находящегося в ее держателе, это обстоятельство не имеет большого значения: алгоритм сборки мусора построен таким образом, что в результате ее выполнения такие указатели сохраняют корректные значения, т.е. держатели продолжают удерживать те же структуры, что и до сборки мусора. Если же для операций с элементами Т-структур используются "обычные" указатели, то программист (или компилятор с языка высокого уровня) должен следить за тем, чтобы после выполнения системных вызовов и захватов памяти значения таких указателей корректировались с использованием указателей, содержащихся в держателях соответствующих структур.
Как уже было отмечено, обычно сборка мусора вызывается неявно-в момент захвата звеньевой памяти. Однако при необходимости Т-функция может явно обратиться к ядру с заказом на проведение сборки мусора. Эта возможность реализуется путем вызова функцииvoid _ut_sys_gc (unsigned i_numcell);
Основная задача, которую решает коммуникационная компонента Т-системы-это задача логического объединения фрагментов вычислительной сети, расположенных в памяти отдельных соисполнителей, в единую вычислительную сеть. Механизмы и алгоритмы, используемые коммуникационной компонентой Т-системы для решения этой задачи, включают в себя:
- алгоритмы функционирования механизма разъемов;
- алгоритмы преобразования Т-структур в транспортную форму для передачи их от одного соисполнителя другому и обратного преобразования принятой транспортной формы в Т-структуры;
- алгоритмы внешнего планирования-распределения процессов по различным соисполнителям;
- Т-протокол-базовый протокол обмена данными для передачи транспортных форм и обмена сообщениями между соисполнителями;
- алгоритмы спрямления транзитных пар разъемов;
- распределенный запуск в рамках ВС задачи, реализованной с использованием Т-системы.
На уровне взаимодействия с ОС Linux коммутационная компонента Т-системы использует сокеты-программный интерфейс различных протоколов передачи данных между процессами ОС Linux. Передача данных между соисполнителями, расположенными в разных процессорных модулях, основывается на использовании протокола UDP (один из протоколов семейства TCP/IP). В том случае, когда обмен данными осуществляется элементами Т-системы, расположенными в одном процессорном модуле, могут использоваться как UDP-сокеты, так и UNIX domain-сокеты.
На основе UDP- и UNIX domain-сокетов коммуникационная компонента Т-системы реализует сетевой протокол более высокого уровня-Т-протокол,-предназначенный для обеспечения "надежного" обмена сообщениями между соисполнителями-в отличие от протокола UDP, являющегося "ненадежным", то есть не обеспечивающим гарантию доставки сообщения от источника пакета к его получателю. В текущей реализации Т-системы Т-протокол условно разбит на 2 составляющих-транспортный и прикладной уровни Т-протокола.
Элементарной базовой структурой данных, используемой соисполнителями для обмена информацией, является Т-пакет, состоящий из заголовка и тела пакета (см. Рисунок 23). Заголовок Т-пакета имеет фиксированный формат, и включает в себя 4 поля:- сигнатуру;
- тип пакета;
- идентификатор (порядковый номер пакета);
- длину пакета вместе с заголовком.
Все поля заголовка являются 4-байтовыми целыми, с порядком байтов, идентичным порядку байтов используемому, центральными процессорами вычислительных узлов ВС. Тело пакета (возможно, нулевой длины) располагается в пакете непосредственно за его заголовком. Формат тела пакета определяется его типом.
Рисунок 23. Формат Т-пакета.
Типы пакетов прикладного уровня не интерпретируются транспортным уровнем Т-протокола. Для обеспечения корректного взаимодействия уровней Т-протокола используется разбиение различных типов пакетов на классы по признакам, описанным ниже (см. Таблица 2).Таблица 2. Признаки различных типов пакетов Наименование признака Описание USER Пакет, относящийся к типу, имеющему данный признак, является пакетом прикладного уровня. MULTIHEAD Пакет, относящийся к типу, имеющему данный признак, содержит фрагмент той части сообщения, предназначенного для передачи нескольким соисполнителям, которая является различной для различных соисполнителей. MULTIDATA Пакет, относящийся к типу, имеющему данный признак, содержит фрагмент той части сообщения, предназначенного для передачи нескольким соисполнителям, которая является общей для различных соисполнителей. BROADCAST Пакет, относящийся к типу, имеющему данный признак, предназначен для широковещательной передачи всем соисполнителям.
Кроме того, для обеспечения передачи сообщений, состоящих из нескольких пакетов, используется индикатор CONT, располагающийся в заголовке пакета в поле типа пакета. В том случае, если данный индикатор (его численное значение в текущей реализации Т-протокола равно 128) установлен, транспортный уровень рассматривает данный пакет как промежуточный (не последний) пакет сообщения, состоящего из нескольких пакетов.
Типы пакетов, используемые на транспортном уровне Т-протокола, приведены ниже (см. Таблица 3).Таблица 3. Типы пакетов, используемые на транспортном уровне Т-протокола Наименование типа пакета Численное значение типа пакета Описание TPKT_CTS 1 Пакет, подтверждающий получение любого пакета Т-протокола (за исключением пакетов типа TPKT_CTS). Используется для обеспечения "надежной" передачи пакетов на транспортном уровне Т-протокола. TPKT_REG 0 Пакет, используемый для оповещения начального-центрального-соисполнителя о возникновении нового соисполнителя данной задачи. По получении данного пакета центральный соисполнитель регистрирует передавшего данный пакет соисполнителя в таблице всех соисполнителей данного приложения. Пакеты данного типа используются при старте приложения. TPKT_REGH 2 Пакет, используемый центральным соисполнителем для оповещения соисполнителей о возникновении нового соисполнителя данного приложения. Используется также для оповещения вновь зарегистрированного соисполнителя об остальных соисполнителях. Пакеты данного типа используются при старте приложения. TPKT_AUTOID 3 Используется для оповещения соисполнителя о присвоенном ему идентификаторе. Пакеты данного типа используются при старте приложения. TPKT_STOP 5 Используется для оповещения соисполнителя о завершении работы приложения и для инициализации завершения компонент соисполнителя. Данный тип пакетов имеет признак BROADCAST TPKT_RIP 6 Используется для синхронизации завершения компонент соисполнителя. TPKT_MAINT 4 Зарезервирован для системных целей.
Как видно из приведенных в таблице данных, ни один из типов пакетов транспортного уровня-за исключением типа TPKT_STOP-не обладает ни одним из специальных признаков.
Типы пакетов, используемые на транспортном уровне Т-протокола, приведены ниже (см. Таблица 4).Таблица 4. Типы пакетов, используемые на прикладном уровне Т-протокола Наименование типа пакета Численное значение типа пакета Описание TPKT_DATAREQ 12 Используется реализацией алгоритма функционирования разъемов для запроса на передачу транспортной формы данных (см. разделы 4.4.2-4.4.3). TPKT_TFSNGL 7 Пакет, предназначенный для передачи транспортной формы данных-в ее простейшем варианте (см. раздел 4.4.3). TPKT_TFDATA_OUTS 9 Пакет, являющийся фрагментом сообщения, содержащего транспортную форму данных (см. раздел 4.4.3)-в ее общем случае. Содержит информацию об одном из тех соисполнителей, которым должна быть передана данная транспортная форма, и идентификацию входных разъемов, которые являются получателями передаваемых в транспортной форме данных.
Данный тип пакетов имеет признак MULTIHEAD.TPKT_TFDATA 10 Пакет, являющийся фрагментом сообщения, содержащего транспортную форму данных-в ее общем случае (см. раздел 4.4.3). Содержит часть передаваемых в транспортной форме данных.
Данный тип пакетов имеет признак MULTIDATA.TPKT_TFPROC 8 Пакет, являющийся фрагментом сообщения, содержащего транспортную форму процесса (см. раздел 0). TPKT_PROCREQ 11 Используется для запроса процесса простаивающим соисполнителем (см. раздел 0). Данный тип пакетов имеет признак BROADCAST TPKT_KILL 16 Используется реализацией алгоритма функционирования разъемов для оповещения соисполнителя о необходимости деактуализации выходного разъема, являющегося элементом разъемной пары (см. раздел 4.4.2), а также реализацией алгоритма спрямления транзитных разъемных пар (см. раздел 4.4.5). TKTP_RENAME 13 Используется реализацией алгоритма спрямления транзитных разъемных пар (см. раздел 4.4.5). TPKT_COPY 15 Используется реализацией алгоритма спрямления транзитных разъемных пар (см. раздел 4.4.5). TPKT_OC2TFSTAT 17 Используется реализацией алгоритма спрямления транзитных разъемных пар (см. раздел 4.4.5). TPKT_MELT 14 Используется реализацией алгоритма спрямления транзитных разъемных пар (см. раздел 4.4.5).
В текущей реализации транспортного уровня Т-протокола соисполнитель разбит на две составляющие, являющиеся отдельными процессами ОС Linux:- программный коммутатор, непосредственно реализующий передачу Т-пакетов между соисполнителями, расположенными в разных процессорных модулях с использованием протокола UDP в качестве базового транспортного уровня;
- вычислитель, включающий в себя большую часть коммутационной компоненты и все остальные компоненты Т-системы-TThreads, вычислительную компоненту и компоненту управления звеньевой памятью и взаимодействующий с программным коммутатором с использованием механизма UNIX domain сокетов.
Такая схема реализации коммутационной компоненты позволяет вычислителю избежать задержек, связанных с необходимостью обеспечения "надежной" передачи пакетов с использованием потенциально "ненадежного" протокола UDP. Кроме того, в случае, если вычислительный узел ВС является мультипроцессорным, такая схема создает возможность параллельного исполнения программного кода программного коммутатора и вычислителя-то есть позволяет совместить по времени передачу данных между различными узлами ВС и собственно процесс вычислений.Алгоритмы функционирования входных и выходных разъемов играют одну из важнейших ролей в Т-системе. Именно разъемы, являясь элементами подграфов вычислительной сети, расположенных в звеньевой памяти отдельных соисполнителей, объединяют их в единую вычислительную сеть.
Базовым элементом всей алгоритмики функционирования механизма разъемов является понятие разъемной пары. Разъемная пара состоит из двух разъемов-входного разъема In и выходного разъема Out,-расположенных в памяти различных соисполнителей Cin и Cоut соответственно. При этом (см Рисунок 24):- разъем In является источником для нескольких потребителей, находящихся в звеньевой памяти соисполнителя Cin;
- разъем Out является одним из потребителей какого-либо источника,
находящегося в звеньевой памяти соисполнителя Cout;
Рисунок 24. Разъемная пара- каждый из разъемов In и Out содержит в звене OutId один и тот же уникальный идентификатор, соответствующий данной разъемной паре;
- разъем In содержит в звене ExeId идентификатор соисполнителя Cout, а разъем Out-идентификатор соисполнителя Cin.
Построенная таким образом разъемная пара позволяет поддерживать между источником разъема In и потребителями разъема Out такую же логическую связь, как если бы они находились в звеньевой памяти одного и того же соисполнителя.
В случае, если какой-либо процесс в соисполнителе Cin затребует результат, поставщиком которого является разъем In, то в соисполнитель Cin отправит соисполнителю Cout сообщение-заказ на передачу данных разъемом Out. При этом разъем In переходит в состояние "Requested" (данные запрошены)-для предотвращения повторных запросов на передачу данных. Получив заказ на передачу данных, соисполнитель Cout переведет разъем Out в состояние "Requested".
В тот момент, когда поставщик разъема Cout будет осуществлять рассылку вычисленного значения, разъем Cout, находящийся в состоянии "Requested", инициирует формирование транспортной формы, содержащей вычисленное значение, и соисполнитель Cout отправит соисполнителю Cin сообщение, содержащее сформированную транспортную форму с данными для разъема In.
Получив сообщение с транспортной формой, соисполнитель Cin разместит полученные данные в своей звеньевой памяти, произведет рассылку полученного вычисленного значения и уничтожит разъем In. В момент уничтожения разъема In соисполнитель Cin отправит соисполнителю Cout заказ на уничтожение разъема Out.
Описанный выше базовый алгоритм работы разъемной пары реализует механизм передачи данных по требованию, предотвращая таким образом передачу данных, которые реально не потребуются для вычислений и таким образом снижая накладные расходы.Транспортная форма-это формат фрагментов вычислительной сети, который позволяет передавать эти фрагменты между различными соисполнителями. Формирование транспортной формы той или иной Т-структуры инициируется в тот момент, когда источник какого-либо кольца производит рассылку данной Т-структуры своим потребителям в качестве вычисленного значения, а одним из потребителей является выходной разъем, находящийся в состоянии "Requested". Транспортная форма представляет собой список буферов, каждый из которых передается как отдельный Т-пакет. Передаваемая подряд между соисполнителями совокупность Т-пакетов транспортной формы образует единое сообщение.
Транспортная форма содержит полную идентификацию (OutId+Exeid) всех тех входных разъемов, которые являются получателями находящихся в транспортной форме данных.
Простейшим случаем транспортной формы является транспортная форма, получателем этой транспортной формы является единственный разъем-в том случае, если она содержит скалярное значение (звено с тэгом TTAG_VOID) или NIL-особый случай держателя, у которого поля указателя и длины являются нулевыми. В этом случае и идентификатор разъема, и само значение звена упаковываются в единый пакет, имеющий тип TPKT_TFSNGL-см. Рисунок 25(а). Во всех остальных случаях транспортная форма содержит один или несколько-в зависимости от количества соисполнителей, запросивших данный фрагмент вычислительной сети и количества входных разъемов являющихся его получателями-пакетов типа TPKT_TFOUTS, а также один или несколько пакетов типа TPKT_TFDATA, содержащих запрошенные данные.
Наиболее общий вариант транспортной формы-см. Рисунок 25(б)-формируется в том случае, если рассылаемое готовое значение является держателем некоторой Т-структуры. В этом случае в транспортную форму наряду с самим держателем помещаются все звенья, составляющие удерживаемую Т-структуру. Каждое из этих звеньев, в свою очередь, может содержать скалярное значение, мультизвено, неготовое значение или держатель. При передаче таких содержащихся в передаваемой Т-структуре держателей и неготовых значений в процессе построения транспортной формы порождаются новые разъемные пары: выходные разъемы вновь созданных разъемных пар остаются в звеньевой памяти, а выходные разъемы помещаются в транспортную форму-см. Рисунок 25(б).
а)
б)Рисунок 25. Формирование транспортной формы данных: простейший случай (а),
общий случай (б)Особым случаем транспортной формы является транспортная форма процесса (см. ниже).
Внешнее планирование, передача процессов
Распараллеливание процесса вычислений в Т-системе основано на передаче процессов между соисполнителями. Внешним планированием будем называть следующую совокупность функций соисполнителей (экземпляров Т-систем):
- принятие одним из соисполнителей решения о выдаче запроса другим соисполнителям о необходимости передачи ему процесса ("я недогружен");
- принятие одним из соисполнителей решения о передаче по упомянутому выше запросу одного из своих процессов ("я могу поделиться работой-передаю процесс").
Процессы в Т-системе являются активными элементами вычислительной сети при ее трансформации. В частности выполняющийся процесс может создать новые фрагменты сети за счет вызова Т-функций. При этом будут созданы новые процессы, также являющиеся элементами вычислительной сети. У каждого соисполнителя может существовать множество готовых к выполнению процессов.
В процессе трансформации вычислительной сети возможны ситуации, когда один или несколько соисполнителей или простаивают (нет готовых к выполнению процессов) или перегружены (не хватает памяти для проведения дальнейших преобразований вычислительной сети). Алгоритмы внешнего планирования призваны устранять или предотвращать подобные ситуации, проводя балансировку загрузки различных процессорных модулей путем передачи процессов между соисполнителями и обеспечивая таким образом распараллеливание вычислений и оптимизацию использования вычислительных ресурсов ВС.
Существуют различные подходы к реализации внешнего планирования:- диффузионный алгоритм;
- алгоритм Торгашева основанный на использовании гистерезисной петли в шкале загруженности соисполнителя;
- и др.
В текущей реализации Т-системы используется модификация диффузионного алгоритма, при которой:- не рассматривается понятие окрестности соисполнителя-все соисполнители считаются близкими;
- шкала загруженности соисполнителя содержит только три значения-"я простаиваю", "я работаю, но поделиться нечем", "я работаю и могу поделиться работой".
- передаче подлежат только процессы, находящиеся в пренатальном (см. раздел 4.2.1) состоянии.
Данный алгоритм реализуется следующим образом:- в случае, когда главный поток управления вычислителя обнаруживает, что в соисполнителе нет ни одного готового к выполнению процесса, им формируется сообщение PROCREQ ("запрос процесса"), ретранслируемое программным коммутатором всем остальным соисполнителям;
- получив сообщение PROCREQ, вычислитель запоминает информацию о выдавшем запрос процесса соисполнителе в системной очереди запросов процессов;
- перед выборкой на выполнение очередного процесса главный поток управления вычислителя просматривает системную очередь запросов процессов и-в том случае, если есть такая возможность-выбирает процесс из очереди пренатальных процессов, посылая сообщение с транспортной формой данного процесса тому соисполнителю, информация о котором находится в системной очереди запросов процессов;
- после передачи транспортной формы процесса выдавшему запрос процесса соисполнителю информация о данном соисполнителе удаляется из системной очереди запросов процессов;
- получивший транспортную форму процесса соисполнитель переносит процесс и переданные вместе с ним разъемы в звеньевую память, помещая процесс в очередь пренатальных процессов.
Транспортная форма процесса формируется аналогично транспортной форме данных (см. раздел 4.4.3). Различия между общим случаем транспортной формы данных и транспортной формой процесса заключаются в следующем:- транспортная форма процесса не включает в себя пакетов типа TPKT_TFOUTS, все пакеты транспортной формы процесса имеют тип TPKT_TFPROC;
- в процессе формирования транспортной формы процесса происходит деактуализация звеньев процесса, находящихся в звеньевой памяти соисполнителя, формирующего транспортную форму;
- выходы процесса, помещаемого в транспортную форму, заменяются в звеньевой памяти соисполнителя входными разъемами. Эти разъемы становятся поставщиками для всех потребителей результатов процесса, расположенных в звеньевой памяти соисполнителя, формирующего данную транспортную форму. Выходные разъемы, образующие разъемные пары с созданными таким образом входными разъемами, также помещаются в транспортную форму.
Рисунок 15 содержит изображение одного из возможных сценариев передачи транспортной формы процесса Рисунок 15.При трансформациях вычислительной сети возможно возникновение транзитных пар разъемов-в том случае, если поставщиком выходного разъема оказывается входной разъем. Рисунок 26 содержит изображение примера последовательности событий, приводящих к возникновению транзитной пары.
Пусть выход процесса П в соисполнителе А является поставщиком разъема С'outА разъемной пары С'outА- С'inВ, и соисполнитель А принял решение о передаче процесса П соисполнителю Б-см. Рисунок 26(а).
При формировании транспортной формы процесса П происходит построение разъемной пары: входной разъем CinА остается в звеньевой памяти соисполнителя А в качестве замены выхода процесса П, а выходной разъем CoutБ помещается в транспортную форму, предназначенную для передачи соисполнителю Б. Таким образом, разъем С'outА оказывается потребителем разъема CinА-образуется транзитная пара CinА-С'outА-см. Рисунок 26(б).
Как следствие этого, при передаче потребителям разъема С'inВ данных, являющихся результатом вычислений проведенных процессом П в соисполнителе Б, будут выполнены две передачи сообщения с транспортной формой данных: одна-от соисполнителя Б соисполнителю А, вторая-от соисполнителя А соисполнителю В-см. Рисунок 26(в). Такая ситуация является нежелательной, так как приводит к транзитным пересылкам транспортных форм данных между соисполнителями, приводящим к неоправданному увеличению нагрузки на коммутационные компоненты соисполнителей и среду передачи, снижая таким образом эффективность всей вычислительной системы в целом.
Рисунок 26. Возникновение транзитной пары разъемов при передаче процесса П
Особенно явной неэффективность становится в том случае, если в описанном выше примере положить Б равным В (считать Б и В одним и тем же соисполнителем Б=В). Тогда передача потребителям разъема С'inБ=В данных, вычисленных процессом П в соисполнителе Б=В, потребует две передачи транспортных форм!
Для устранения подобных ситуаций коммуникационная компонента Т-системы реализует алгоритмы спрямления транзитных пар: транзитные пути передачи данных заменяются на нетранзитные, а соответствующие транзитные пары по возможности деактуализируются.
Для взаимодействия соисполнителей в процессе спрямляющих транзакций коммуникационная компонента использует сообщения KILL, RENAME, COPY, OC2TFSTAT и MELT, каждое из которых состоит из одиночного пакета типов TKTP_KILL, TKTP_RENAME, TKTP_COPY, TKTP_OC2TFSTAT и TKTP_MELT соответственно. Идею реализации алгоритмов спрямления транзитных пар можно проиллюстрировать на примере сценария спрямления той транзитной пары, сценарий возникновения которой был изображен выше-см. Рисунок 26.
В данном случае сценарий спрямления транзитной пары состоит из следующих шагов:- При формировании транспортной формы процесса П в соисполнителе А для передачи данного процесса в соисполнитель Б строится разъемная пара: входной разъем CinА остается в звеньевой памяти соисполнителя А в качестве замены выхода процесса П, а выходной разъем CoutБ помещается в транспортную форму, предназначенную к передаче соисполнителю Б. В этот момент обнаруживается, что одним из потребителей выхода процесса был выходной разъем С'outА, который в данный момент оказался потребителем разъема CinА: образовалась транзитная пара CinА-С'outА. С учетом этого обстоятельства разъем CinА помечается как запрещенный для уничтожения-замораживается, а соисполнителю В, в котором расположен входной разъем C'inВ разъемной пары С'outА-C'inВ посылается сообщение RENAME, информирующее соисполнитель В о том, что первичным поставщиком значения, предназначенного к передаче по данной разъемной паре стал разъем CoutБ, расположенный в соисполнителе Б-см. Рисунок 27(а). В соисполнителе А инициируется передача транспортной формы процесса П в соисполнитель Б.
- Получив сообщение RENAME, соисполнитель В создает входной разъем C''inВ и посылает соисполнителю Б сообщение COPY-запрос на создание разъема C''outБ, который должен являться потребителем того же поставщика, что и разъем CoutБ. После этого соисполнитель В деактуализирует разъем C'inВ и посылает соисполнителю А сообщение KILL, содержащее заказ на деактуализацию разъема С'outА-см. Рисунок 27(б). Соисполнитель Б получает транспортную форму процесса П и переносит ее в звеньевую память.
- Получив сообщение COPY, соисполнитель Б создает разъем C''outБ, который становится потребителем того же поставщика, что и разъем CoutБ-то есть выхода процесса П, и таким образом возникает спрямленная разъемная пара C''outБ-С''inВ. Затем соисполнитель Б посылает соисполнителю А сообщение MELT, извещающее соисполнитель А о том, что пометка разъема CinА как запрещенного для уничтожения должна быть снята-разъем CinА должен быть разморожен. Соисполнитель А получает сообщение KILL и деактуализирует разъем С'outА-см. рисунок 27(в).
- Соисполнитель А получает сообщение MELT и размораживает разъем CinА. Спрямляющая транзакция на этом завершается-результирующая конфигурация данного фрагмента вычислительной сети не содержит транзитных путей передачи транспортных форм данных-см. рисунок 27(г).
Приведенный выше сценарий вследствие асинхронности функционирования соисполнителей обладает высокой степенью вариабельности. Например, соисполнитель Б может получить сообщение COPY от соисполнителя В до получения транспортной формы процесса П. В данном случае в качестве замены выхода процесса П в соисполнителе Б будет создана системная Т-структура фиктивный выход процесса (см раздел 3.2.5.3), которая первоначально будет выполнять роль поставщика для вновь созданного разъема C''outБ. По получении процесса П от соисполнителя А фиктивный выход процесса будет деактуализирован соисполнителем Б, а все его получатели-в том числе и разъем C''outБ-станут получателями выхода процесса П.
Рисунок 27. Спрямление транзитной пары разъемов,
возникающей при передаче процесса ППри передаче транспортной формы данных также существует возможность возникновения транзитной пары разъемов-в том случае, если звено, являющееся элементом Т-структуры, передаваемой в составе транспортной формы общего вида, содержит неготовое значение, и поставщиком данного значения является входной разъем.
Рисунок 28. Возникновение транзитной пары разъемов при передаче данных
Рисунок 28(а) иллюстрирует данную ситуацию: при формировании в соисполнителе А транспортной формы данных для передачи соисполнителю Б держателя и удерживаемого им массива звеньев, одно из передаваемых звеньев имеет неготовое значение, поставщиком которого является входной разъем CinА разъемной пары СoutВ-CinА. В соответствие с общим алгоритмом формирования транспортной формы данных, для передачи неготового значения формируется разъемная пара С'outА-C'inБ, входной разъем которой C'inБ помещается в транспортную форму в качестве поставщика данного неготового значения, а выходной разъем С'outА остается в звеньевой памяти соисполнителя А и становится потребителем того же поставщика, что и исходное звено, то есть выхода разъема CinА. Таким образом, образуется транзитная пара разъемов CinА-С'outА-см. Рисунок 28 (а).
После размещения в звеньевой памяти соисполнителя Б данных, переданных соисполнителем А в данной транспортной форме, и выдачи соисполнителем Б запроса на получение данного неготового значения будут выполнены две передачи сообщения с транспортной формой данных: одна-от соисполнителя В соисполнителю А, вторая-от соисполнителя А соисполнителю Б-см. Рисунок 28 (б).
Рисунок 29. Спрямление транзитной пары разъемов, возникающей при передаче данных
Основной вариант сценария спрямления такой транзитной пары несколько проще описанного выше сценария спрямления транзитной пары, возникающей при передаче процесса, и использует обмен сообщениями COPY и MELT между соисполнителями, участвующими в спрямляющей транзакции. В данном случае сценарий спрямления транзитной пары состоит из следующих шагов:- При формировании транспортной формы для передачи соисполнителю Б в соисполнителе А обнаруживается, что одно из передаваемых звеньев содержит неготовое значение, поставщиком которого является входной разъем CinА разъемной пары СoutВ-CinА. С учетом этого обстоятельства разъем CinА замораживается, а в транспортную форму в качестве поставщика данного неготового значения помещается входной разъем C'inБ-см. Рисунок 29 (а). В звено разъема C'inБ, содержащее ExeId (см. разделы 3.2.5.2, 4.4.2), помещается идентификатор соисполнителя В.
- Размещая в звеньевой памяти полученную от соисполнителя А транспортную форму данных, соисполнитель Б обнаруживает, что поставщиком переданного в данной транспортной форме неготового значения является входной разъем C'inБ, ExeId которого (в данном случае-идентификатор соисполнителя В) отличается от идентификатора отправителя транспортной формы-соисполнителя А. Соисполнитель Б посылает соисполнителю В сообщение COPY-запрос на создание разъема C'outВ, который должен являться потребителем того же поставщика, что и разъем CoutВ. Данное неготовое значение и разъем C'inБ размещаются в звеньевой памяти соисполнителя Б-см. Рисунок 29(б).
- Получив сообщение COPY, соисполнитель В создает разъем C'outВ, который становится потребителем того же поставщика, что и разъем CoutВ-образуется полноценная разъемная пара C'outВ-C'inБ. Затем соисполнитель В посылает соисполнителю А сообщение MELT, извещающее соисполнитель А о том, что разъем CinА должен быть разморожен-см. Рисунок 29(в).
- Соисполнитель А получает сообщение MELT и размораживает разъем CinА. Спрямляющая транзакция на этом завершается-результирующая конфигурация данного фрагмента вычислительной сети не содержит транзитных путей передачи транспортных форм данных-см. Рисунок 29(г).
Старт работы распределенного приложения, реализованного с использованием Т-системы
Помимо описанных выше функций, коммуникационная компонента Т-системы реализует сценарий распределенного запуска приложения, реализованного с использованием Т-системы,. на всех вычислительных узлах ВС. В текущей реализации Т-системы основной вариант данного сценария состоит из следующих шагов:
- Запуск программного коммутатора на том вычислительном узле ВС, где был инициализирован запуск приложения (в дальнейшем данные программный коммутатор и вычислительный узел будем называть центральными). В качестве параметров запуска программный коммутатор получает имя исполняемого файла приложения и аргументы приложения. Программный коммутатор захватывает UDP-сокет, необходимый для обеспечения обменов сообщениями с остальными соисполнителями и создает Unix domain сокет, необходимый для обмена сообщениями с вычислителем.
- Запуск вычислителя на центральном вычислительном узле-центрального вычислителя, производимый программным коммутатором. В качестве параметров запуска коммутатор передает вычислителю аргументы приложения и имя Unix domain сокета для обмена сообщениями с программным коммутатором. Вычислитель проводит инициализацию приложения и устанавливает соединение с программным коммутатором.
- Начало работы приложения. Центральный программный коммутатор с использованием установленного соединения передает вычислителю сообщение, состоящее из одиночного пакета типа TPKT_AUTOID, содержащего идентификатор вычислителя. Вычислитель приступает к выполнению приложения.
- Копирование (если это необходимо) с использованием механизма RCP ОС Linux программного кода приложения на остальные (удаленные) вычислительные узлы ВС и запуск на них программных коммутаторов с использованием механизма RSH ОС Linux. После запуска удаленные программные коммутаторы выполняют действия, аналогичные действиям центрального программного коммутатора на шаге 1. В качестве параметров запуска удаленным программным коммутаторам передаются имя исполняемого файла и аргументы приложения, а также идентификатор UDP-сокета, захваченного центральным программным коммутатором.
- Запуск вычислителей на каждом из удаленных вычислительном узлов ВС. Производится аналогично запуску центрального вычислителя (см шаг 2 данного сценария).
- Регистрация вновь запущенных соисполнителей у центрального программного коммутатора. Производится центральным коммутатором по получении пакетов типа TPKT_REG, посылаемых удаленными коммутаторами. По получении пакета данного типа центральный коммутатор также рассылает всем уже зарегистрировавшимся на данный момент соисполнителям пакеты типа TPKT_REGH, содержащие информацию о вновь зарегистрировавшемся соисполнителе. Вновь зарегистрировавшемуся соисполнителю передается сообщение, состоящее из серии пакетов типа TPKT_REGH, содержащее информацию о всех соисполнителях, зарегистрировавшимся на данный момент.
- Начало работы удаленного соисполнителя. По получении пакета TPKT_REGH удаленный программный коммутатор с использованием установленного на шаге 5 соединения передает вычислителю сообщение AUTOID, содержащее идентификатор вычислителя. Вычислитель переходит в активное состояние.
Первый шаг данного сценария-запуск программного коммутатора-может производиться как непосредственно, так и через посредство передачи на выполнение исполняемого файла приложения. В том случае, когда выполнение программного кода приложения инициируется не программным коммутатором, а, например, непосредственно пользователем из командной строки ОС Linux, вычислитель обнаруживает этот факт и передает на выполнение программный коммутатор, инициируя шаг 1 описанного выше сценария.