TDE всех задач, которые могут выполняться на процессоре в любой данный момент времени, объединены в структуру данных, называемую очередью диспетчеризации задач TDQ (task dispatching queue). TDQ реализована как связный список в памяти, в котором TDE упорядочены по приоритетам, как показано на рисунке 9.2. Каждый TDE содержит поле приоритета, которое используется для упорядочения. TDE для приоритетной задачи открывает список.

Находящийся в SLIC диспетчер задач выбирает приоритетный (первый в списке) TDE и передает ему управление процессором. Таким образом, первый TDE связан с задачей, которая в данный момент исполняется процессором. Все остальные TDE в TDQ связаны с задачами в готовом состоянии. Текущая задача продолжает исполняться до тех пор, пока ей не придется отдать управление процессором.

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

Всякий раз, когда исполняющаяся задача отдает управление, оно передается задаче, следующей по важности в TDQ, которая и становится новой исполняющейся задачей. Таким образом, любой TDE в TDQ находится по определению либо в исполняющемся, либо в готовом состоянии.

Рисунок 9.2. Очередь диспетчеризации задач

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

Семафор имеет счетчик и список ожидания. Определены две операции (команды). Синхронизация задач осуществляется следующим образом. Оператор V увеличивает значение счетчика на 1. Оператор P проверяет значение счетчика; если оно больше 0, то уменьшает значение на 1 и дает возможность выполняться следующей команде в потоке. Если значение счетчика не больше 0, то оператор Р ждет пока значение увеличится и станет больше 0, прежде чем операция завершится и следующая команда сможет выполняться. То есть ситуация, когда при выполнении оператора Р счетчик не больше 0, означает ожидание. В этом случае, задача, выполнившая оператор Р, ждет до тех пор, пока какая-либо другая задача не увеличит счетчик с помощью оператора V.

Во многих случаях, при синхронизации желательно обменяться некоторой информацией или сообщением. Для поддержки синхронизации и передачи сообщений AS/ 400 определяет очередь приема-передачи SRQ (send/receive queue). SRQ — это структура данных в памяти, используемая как «почтовый ящик» для передачи сообщений от одной задачи к другой.

Когда исполняющаяся задача выполняет операцию «Отправить сообщение», в очередь SRQ, связанную с некоторой другой задачей, добавляется структура данных, называемая сообщением приема-передачи SRM (send/receive message). SRM содержит сообщение, которое исполняющаяся задача желает передать другой задаче. Когда исполняющаяся задача хочет получить сообщение из SRQ (из своего почтового ящика), она выполняет операцию «Принять сообщение». Если сообщения нет, то задача может подождать его поступления. Если она решает ждать, то TDE исполняющейся задачи извлекается из TDQ и помещается в список ожидания — часть каждой SRQ. Затем вызывается диспетчер задач, который выбирает готовую задачу наибольшей важности и делает ее исполняющейся.

Некоторое время спустя другая исполняющаяся задача выполняет для данной SRQ операцию «Отправить сообщение». Если TDE ждет сообщения, то он извлекается из SRQ и помещается в очередь TDQ в порядке важности (приоритетности). Если важность вновь добавленного в очередь TDE выше, чем у исполняющегося, то исполняющая задача вытесняется. Если в процессе ожидания находятся несколько SRQ, то разряд в заголовке SRQ указывает, следует ли при поступлении сообщения «разбудить» их все, или только первую.

Любая задача, чей TDE находится в очереди SRQ, по определению находится в состоянии ожидания. На рисунке 9.3 показаны перемещения TDE и то, каким образом положение TDE определяет состояние задачи.

Рисунок 9.3. Перемещения элемента диспетчеризации задач

На рисунке не показаны другие структуры данных, которые могут находиться в очередях TDE. Одна из таких структур — счетчик приема-передачи SRC (send/receive counter). SRC не занимается передачей сообщений, так что похож на обычный семафор. SLIC предоставляет операции «Отправить счетчик» и «Принять счетчик», которые позволяют синхронизировать задачи, если обмен сообщениями не нужен.

Некоторые читатели, знакомые с командами «SNDPGMMSG» (Send Program Message) и «RCVMSG» (Receive Message) в OS/400 могут спросить: имеют ли эти команды отношение к операциям, используемым структурой задач SLIC. Ответ: «Да, они состоят в очень тесном родстве». Формат SRM, SRQ и SRC спроектирован для управления задачами, но операции добавления и извлечения сообщений из очереди фундаментально одинаковы во всей системе. За реализацию всех этих функций отвечает SLIC.

В предшествующем разделе описывались ситуации, подразумевающие наличие только одного процессора, и, следовательно, только одной исполняющейся задачи. На многопроцессорной же системе потенциально может быть несколько исполняющихся задач. Многопроцессорные системы поддерживаются механизмом диспетчеризации задач, большая часть которого присутствовала еще в оригинальной System/38, хотя никогда не использовалась на этой системе. Лишь в 1990 году мультипроцессирова-ние было впервые использовано в AS/400. Оригинальная поддержка мультипроцес-сирования AS/400 до сих пор задействована не полностью, ее резервы предназначены для будущих расширений.

Ранее мы видели, что система симметричного мультипроцессирования (SMP) дает возможность ОС обрабатывать задачи на любом свободном процессоре или на всех процессорах сразу, при этом память остается общей для всех процессоров. Именно так устроена n-канальная (n-way) обработка на AS/400. Любой компонент ОС, включая диспетчер задач, может выполняться на любом или на всех процессорах системы.

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

В многопроцессорной системе одновременно исполняется несколько задач — по одной на процессор. Упрощенно, следует лишь направить на выполнение верхние n TDE из TDQ. Естественно, эти n задач имеют наивысшую приоритетность среди всех готовых задач. Однако такой простой метод часто только кажется наилучшим.

Предположим, что у нас есть две задачи, А и В, исполняющиеся на процессорах 1 и 2 в двухпроцессорной системе. Предположим далее, что задача С, приоритет которой выше чем у А, но ниже чем у В, выходит из состояния ожидания. Ее TDE будет добавлен в очередь TDQ непосредственно перед TDE задачи А. Диспетчер задач выполнит переключение задач на процессоре 1, чтобы начать исполнение задачи С. Теперь допустим, что задача В на процессоре 2 либо завершилась, либо перешла в состояние ожидания. Приоритет задачи А — наивысший среди готовых задач, и ее следует направить на процессор 2. Но этот выбор может быть не лучшим.