Алгоритмы планирования. 
Архитектура ЭВМ и систем

Особенности алгоритмов планирования рассмотрим на примере, в котором система COW содержит 8 процессоров.

Простейший алгоритм соответствует порядку «первым вошел — первым вышел» — алгоритм FIFO (рис. 19.4,а). Когда первая задача начала выполняться, происходит проверка, есть ли достаточное количество процессоров для выполнения задачи:

• • если да, то она тоже начинает выполняться;
• • если нет, то система ждет, пока не появится достаточное количество процессоров.

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

Рис. /9.4. Алгоритмы планирования в порядке «первым вошел — первым вышел». Результат применения этого алгоритма показан на рис. 19.4,6.

Алгоритм заполнения прямоугольника. Это более сложный алгоритм, для реализации которого необходимо знать, сколько процессоров требуется для каждой задачи и сколько минут займет ее выполнение. На основании этой информации планировщик заданий старается заполнить прямоугольник «процессоры — время». Результат выполнения алгоритма показан на рис. 19.4,#.

Сети межсоединений

Рассмотрим три вида сетей, которые используются в системах COW.

Сети Ethernet. Существует три версии системы Ethernet (classic, fast и gigabit Ethernet), отличающиеся производительностью. Каждый компьютер содержит сетевую плату. Платы всех компьютеров соединены электрически.

В первой разработке для создания сети использовалось непосредственное соединение провода сетевой платы с кабелем, затем появились коннекторы, а позднее кабель каждого компьютера стати подсоединять к сетевому концентратору (хабу). Последняя разработка ускорила поиск неисправностей путем последовательного отключения кабеля от сетевого концентратора. Сеть Ethernet из трех компьютеров К изображена на рис. 19.5,а.

Обмен данными осуществляется в соответствии с протоколом Ethernet:

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

В последующих разработках сетевой концентратор заменен коммутатором (рис. 19.5,б), содержащим высокоскоростную плату backplane, к которой подсоединяются канальные карты. Это позволило связать воедино все три системы Ethernet — classic, fast и gigabit Ethernet.

При поступлении пакета от исходящего компьютера в коммутатор пакет временно сохраняется в буфере, пока канальная карта не отправит запрос и не получит доступ к плате backplane. После этого пакет перемещается в канальную карту, к которой подсоединен целевой компьютер. Сети на основе gigabit Ethernet с коммутаторами находят широкое применение, так как удовлетворяют требованиям потребителей по критерию цена/производительность.

Сеть ATM. Сеть с асинхронным режимом передачи (Asynchronous Transfer Mode — ATM) разработана международным консорциумом телефонных компаний в качестве замены существующей телефонной системы на новую, полностью цифровую сеть. В настоящее время многие компании выпускают съемные платы ATM для персональных компьютеров со скоростью передачи данных 155 Мбит/с или 622 Мбит/с. В мультикомпьютерах используется второй тип плат.

В сетях АТМ, как и Ethernet, используется коммутатор. Однако между сетями имеются существенные различия:

• поскольку сеть ATM разработана для замещения телефонной системы, она представляет собой сеть с маршрутизацией информации. В такой сети перед отправкой пакета в пункт назначения исходный компьютер должен иметь виртуальную цепь (в Ethernet их нет) от исходного пункта через один или несколько коммутаторов ATM в конечный пункт (рис. 19.6). Каждый компьютер устанавливает виртуальную цепь со всеми другими компьютерами при запуске и использует их при работе. Пакеты, отправленные по виртуальной цепи, доставляются в правильном порядке, однако доставка не га;

Рис. 19.5. Пример сети Ethernet из трех компьютеров (а); коммутатор Ethernet (б).

рантируется (как и в сети Ethernet) из-за возможного переполнения буферов канальных карт;

• если сеть Ethernet может передавать целые пакеты (до 1500 байт данных) одним блоком, то в АТМ все пакеты разбиваются на ячейки по 53 байта, из них:

¦ 5 байт являются полями заголовка, которые сообщают, какой виртуальной цепи принадлежит ячейка, что это за ячейка, каков ее приоритет, а также некоторые другие сведения;

¦ 48 байт составляют полезную нагрузку.

Разбивка пакетов на ячейки и их компоновка в конце маршрута обеспечиваются аппаратными средствами.

Сеть Myrinet. Используется та же модель сети, что и сетей Ethernet и ATM, где каждая съемная плата подсоединяется к коммутатору, а коммутаторы могут соединяться в любой топологии. Сеть Myrinet пользуется популярностью у разработчиков систем COW, поскольку платы в этой сети содержат программируемый процессор и большое ОЗУ. Каналы связи сети дуплексные, по ним передаются данные со скоростью 1,28 Гбит/с в обоих направлениях. Размер пакетов не ограничен. Обеспечивается малое время ожидания и высокая пропускная способность. К особенностям следует отнести возможность управления потоком и запуска части кода прикладной программы на плате, а также надежное широковещание и мультивещание.