WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 || 4 | 5 |

• Жесткие требования к скорости работы алгоритма планирования задач, возникающие ввиду ограниченного объема ассоциативной памяти.

Важно отметить, что принципиальной особенностью ВСАРР является то, что задача может выполняться только в том случае, когда ей выделен определенный объем ассоциативной памяти; если задача откачана во внешнюю память, ее выполнение приостанавливается. Таким образом, организация виртуальной памяти ВСАРР и планирование задач в ВСАРР тесно связаны между собой. Организация виртуальной памяти ВСАРР требует решения следующих проблем:

• Проблема распределения внешней памяти между одновременно выполняющимися задачами.

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

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

Планирование задач в ВСАРР Характерной особенностью ВСАРР является то, что процесс вычислений происходит как в исполнительных устройствах, в которых происходит обработка пар и генерация токенов, так и в модулях ассоциативной памяти, в которых происходит сопоставление токенов и генерация пар. Более того, в общем случае нельзя сказать, кто вносит основной вклад в получение конечного результата вычислений – ИУ или модули АП, поскольку в данном вопросе все зависит от алгоритма решаемой задачи и конкретных исходных данных. Таким образом, ИУ и модули АП являются вычислительными ресурсами ВСАРР, что должен учитывать алгоритм планирования задач.

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

Как показывают расчеты, частота принятия решений об откачке и подкачке задач может быть достаточно большой – порядка 106-107 раз в секунду, причиной чего является ограниченный объем АП. Действительно, чтобы обеспечить максимальную интенсивность генерации пар в модулях АП, необходимо поддерживать их в заполненном состоянии. Если заполненность модуля падает ниже определенного порога (допустим, 80%), должна начинаться подкачка токенов в модуль. Вместе с тем, если заполненность модуля поднимается выше определенного порога (допустим, 90%), необходимо начинать откачку токенов из модуля, чтобы избежать блокировки вычислительного процесса в ВСАРР. Таким образом, частота принятия решений об откачке и подкачке определяется той скоростью, с которой меняется заполненность модуля. Данная скорость зависит как от постоянных факторов – то есть, объема модуля и темпа, с которым модуль принимает токены и генерирует пары, так и от переменных факторов – то есть, конкретных задач, которые выполняются в вычислительной системе на определенных наборах входных данных. Поскольку эффективная работа вычислительной системы должна обеспечиваться во всех ситуациях, целесообразно принятие решений об откачке и подкачке задач выполнять аппаратным образом. Эту функцию должно выполнять центральное устройство управления памятью ВСАРР. Системное программное обеспечение ВСАРР должно загружать в ЦУУП значения приоритетов задач, необходимые для принятия решений об откачке и подкачке.

Распределение ресурсов в соответствии с приоритетами в большинстве систем выполняется по следующему принципу: управление передается готовой к выполнению задаче с наивысшим приоритетом. Однако в этом случае необходимо предусматривать механизм предотвращения безостановочной работы такой задачи – например, уменьшать приоритет задачи с течением времени или ограничивать максимальный отрезок времени непрерывной работы задачи. Принципиально другим подходом является так называемое гарантированное планирование. Оно основывается на принципе передачи управления той задаче, которая за время своего предыдущего выполнения израсходовала меньше всего ресурсов из того лимита, который должен быть ей предоставлен в соответствии с ее приоритетом. Математически этот принцип может быть сформулирован следующим образом. Пусть в системе выполняется N задач. Обозначим через P абсолютный приоритет i-й задачи (присвоенный, i допустим, администратором системы), через Q объем ресурсов, i израсходованных i-й задачей за определенный промежуток времени. Q i представляет собой некую интегральную величину, характеризующую загруженность ИУ и модулей АП обработкой токенов и пар i-й задачи, которая рассчитывается на основе значений аппаратных счетчиков активности задач.

Относительный приоритет i-й задачи равен отношению P к сумме абсолютных i приоритетов всех N задач. Относительный объем израсходованных i-й задачей ресурсов равен отношению Q к общему объему ресурсов, израсходованных i всеми задачами. При постановке задач на выполнение предпочтение должно отдаваться тем задачам, у которых разность между относительным приоритетом и относительным объемом израсходованных ресурсов является наибольшей. Аппаратура ВСАРР (в частности, ЦУУП) может иметь различные встроенные средства, обеспечивающие распределение ресурсов между задачами в соответствии с их приоритетами. Вместе с тем, в силу ограничений реализации, аппаратные механизмы не всегда способны обеспечить достаточный уровень точности данного распределения. Эта проблема может решаться двумя способами.

Первый способ основан на использовании динамических приоритетов задач. Динамические приоритеты задач – те приоритеты, которые системное программное обеспечение ВСАРР загружает в ЦУУП и на основании которых ЦУУП принимает решения об откачке и подкачке. Системное ПО должно отслеживать прохождение задач на вычислительной системе и корректировать динамические приоритеты задач, у которых относительный приоритет не совпадает с относительным объемом израсходованных ресурсов. Для этого можно использовать адаптивный алгоритм: если относительный приоритет задачи приблизительно совпадает с относительным объемом израсходованных ею за определенный промежуток времени ресурсов, то динамический приоритет задачи необходимо оставить неизменным; в противном случае, динамический приоритет задачи необходимо увеличить или уменьшить на определенную величину.

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

Выбирая задачи для очередного пакета, необходимо учитывать приоритеты задач и объемы израсходованных задачами ресурсов. Такой подход аналогичен подходу, используемому в традиционных вычислительных системах, и не предъявляет сколько-нибудь серьезных требований к реализации ЦУУП.

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

Предсказуемость планирования для ВСАРР может быть обеспечена только непрерывной ротацией задач (так же, как и для традиционных вычислительных систем). При использовании механизма динамических приоритетов задач, ротацию должно осуществлять центральное устройство управления памятью. Основываясь на значениях динамических приоритетов задач, ЦУУП должно периодически снимать с выполнения одни задачи и ставить на выполнение другие задачи, стремясь обеспечить как распределение ресурсов в соответствии с приоритетами, так и полную загрузку вычислительной системы. При использовании механизма пакетов задач, ротацию осуществляет системное ПО, выбирая задачи для включения в очередной пакет.

Балансировка нагрузки для ВСАРР сводится к тому, что системное ПО должно постоянно отслеживать загрузку ИУ и модулей АП различными задачами. Для любой конфигурации ВСАРР могут быть подобраны так называемые несбалансированные задачи, которые нагружают ВСАРР неравномерно (недогружают ИУ при полной загрузке модулей АП, недогружают модули АП при полной загрузке ИУ, и так далее). Системное ПО может обнаруживать и соответствующим образом исправлять такие ситуации.

Организация виртуальной памяти в ВСАРР Виртуальная память ВСАРР предназначена для решения проблемы блокировки вычислительного процесса при переполнении ассоциативной памяти. Переполнение АП может возникать как в многозадачном режиме (если доступного объема АП недостаточно для одновременного прохождения всех выполняющихся задач), так и в монозадачном режиме (если доступного объема АП недостаточно для одновременного прохождения всех подзадач выполняющейся задачи). В случае угрозы переполнения АП часть токенов откачивается из АП в ООЗУ, что предотвращает блокировку вычислительного процесса. Поскольку объем ООЗУ также является ограниченным, в ВСАРР предусмотрена возможность откачки данных из ООЗУ в дисковую память при переполнении ООЗУ.

Обмены между АП и ООЗУ целесообразно проводить под контролем ЦУУП ввиду высокой частоты этих обменов. Алгоритм откачки и подкачки, заложенный в ЦУУП, может быть как достаточно простым, так и весьма сложным. Например, возможен такой простой алгоритм: при угрозе переполнения АП откачивать задачу с наименьшим приоритетом, при освобождении АП подкачивать задачу с наибольшим приоритетом. Такой алгоритм несложно реализовать в аппаратуре, однако ротацию задач в этом случае придется выполнять программным образом. Заложенный в ЦУУП более сложный алгоритм откачки и подкачки, поддерживающий ротацию задач на основе аппаратных счетчиков активности задач, может оказаться более эффективным с точки зрения использования ресурсов вычислительной системы.

Распределение ООЗУ между задачами и между подзадачами каждой отдельно взятой задачи может быть реализовано при помощи общепринятых механизмов страничной адресации памяти. ЦУУП поддерживает так называемую аппаратную таблицу задач (АТЗ), в которой хранится информация о задачах, выполняющихся в потоковой вычислительной машине.

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

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

Основной проблемой, связанной с откачкой страниц на диск, является проблема выбора алгоритма откачки страниц. Оптимальный алгоритм откачивает в первую очередь те страницы, которые максимально долго не будут использоваться в будущем (в общем случае, оптимальный алгоритм не может быть практически реализован из-за недоступности информации о том, как в будущем будет протекать процесс вычислений). Алгоритмы откачки, применяемые на практике, обычно основываются на том, что аппаратура выставляет для каждой страницы биты «R» (referenced) и «M» (modified). Бит «R» устанавливается при любом обращении к странице (по чтению или по записи), бит «M» – при записи в страницу. Этой информации достаточно для того, чтобы реализовать алгоритм, достаточно хорошо аппроксимирующий оптимальный алгоритм. Например, алгоритм «старения» страниц основан на периодическом опросе состояния битов «R» всех страниц с целью отследить те страницы, которые не использовались дольше всего. Алгоритм подкачки страниц в случае недоступности информации о том, как в будущем будет протекать процесс вычислений, сводится к подкачке страниц при обращении к ним. Если приблизительно известен момент времени в будущем, когда произойдет обращение к странице, то такая страница может быть подкачана заблаговременно.

Применительно к ВСАРР, стандартные алгоритмы откачки и подкачки могут быть определенным образом модифицированы, что повысит их эффективность. Во-первых, при откачке данных из АП в ООЗУ и при подкачке данных из ООЗУ в АП доступ к сегментам памяти ООЗУ, как правило, происходит по последовательным виртуальным адресам. С учетом этого обстоятельства, возникает возможность оптимизировать обмены между ООЗУ и дисками. Например, становится возможной опережающая подкачка страниц с диска в тех случаях, когда необходимо определенный сегмент, находящийся на диске, переместить в АП. Также, при откачке страниц на диск можно откачивать в первую очередь те страницы, которые находятся в «хвостах» сегментов (то есть, гарантированно будут востребованы позже всего). Вовторых, задачи, обладающие высоким приоритетом, обычно должны откачиваться на диск лишь в редких случаях (например, если задача заблокирована ввиду ожидания внешнего события). Поэтому при выборе страниц, откачиваемых на диск, необходимо совместно анализировать временные метки последнего доступа к страницам и приоритеты задач, которым принадлежат страницы. Например, страницы высокоприоритетных задач могут быть «защищены» от откачки в течение определенного периода времени.

Pages:     | 1 | 2 || 4 | 5 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»