Исследование алгоритмов планирования вычислительного процесса мультипроцессорных систем при пакетной обработке задач - Программирование, компьютеры и кибернетика курсовая работа
Главная
Программирование, компьютеры и кибернетика
Исследование алгоритмов планирования вычислительного процесса мультипроцессорных систем при пакетной обработке задач
Способы организации вычислительного процесса в системах с несколькими процессорами. Разработка программы на основе алгоритмов мультипроцессорных систем при пакетной обработке задач. Вычисление основных показателей эффективности для каждого алгоритма.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Построить программу на основе алгоритмов планирования вычислительного процесса мультипроцессорных систем при пакетной обработке задач.
Для каждого из алгоритмов необходимо:
- провести распределение задач на процессоры по временам их решения;
- вычислить показатели эффективности;
На основе полученных данных сравнить алгоритмы для выявления наиболее эффективного метода выполнения задач на разных процессорах.
Задачей курсовой работы является создание программы, реализующей методы управления ресурсами многопроцессорных систем при обработке пакетов задач с прерываниями и без них.
1. Количество процессоров в системе;
мультипроцессорный алгоритм планирование вычислительный
Мультипроцессорная обработка -- это способ организации вычислительного процесса в системах с несколькими процессорами, при котором несколько задач (процессов, потоков) могут одновременно выполняться на разных процессорах системы.
Не следует путать мультипроцессорную обработку с мультипрограммной обработкой. В мультипрограммных системах параллельная работа разных устройств позволяет одновременно вести обработку нескольких программ, но при этом в процессоре в каждый момент времени выполняется только одна программа. То есть в этом случае несколько задач выполняются попеременно на одном процессоре, создавая лишь видимость параллельного выполнения. А в мультипроцессорных системах несколько задач выполняются действительно одновременно, так как имеется несколько обрабатывающих устройств -- процессоров. Конечно, мультипроцессирование вовсе не исключает мультипрограммирования: на каждом из процессоров может попеременно выполняться некоторый закрепленный за данным процессором набор задач.
Мультипроцессорная организация системы приводит к усложнению всех алгоритмов управления ресурсами, например, требуется планировать процессы не для одного, а для нескольких процессоров, что гораздо сложнее. Сложности заключаются и в возрастании числа конфликтов по обращению к устройствам ввода-вывода, данным, общей памяти и совместно используемым программам. Необходимо предусмотреть эффективные средства блокировки при доступе к разделяемым информационным структурам ядра. Все эти проблемы должна решать операционная система путем синхронизации процессов, ведения очередей и планирования ресурсов. Более того, сама операционная система должна быть спроектирована так, чтобы уменьшить существующие взаимозависимости между собственными компонентами.
В наши дни становится общепринятым введение в ОС функций поддержки мультипроцессорной обработки данных. Такие функции имеются во всех популярных ОС, таких как Sun Solaris 2.x, Santa Crus Operations Open Server 3.x, IBM OS/2, Microsoft Windows NT и Novell NetWare, начиная с 4.1.
Системы пакетной обработки предназначались для решения задач в основном вычислительного характера, не требующих быстрого получения результатов. Главной целью и критерием эффективности систем пакетной обработки является максимальная пропускная способность, то есть решение максимального числа задач в единицу времени.
Для достижения этой цели в системах пакетной обработки используется следующая схема функционирования: в начале работы формируется пакет заданий, каждое задание содержит требование к системным ресурсам; из этого пакета заданий формируется мультипрограммная смесь, то есть множество одновременно выполняемых задач. Для одновременного выполнения выбираются задачи, предъявляющие разные требования к ресурсам, так, чтобы обеспечивалась сбалансированная загрузка всех устройств вычислительной машины. Например, в мультипрограммной смеси желательно одновременное присутствие вычислительных задач и задач с интенсивным вводом-выводом. Таким образом, выбор нового задания из пакета заданий зависит от внутренней ситуации, складывающейся в системе, то есть выбирается «выгодное» задание. Следовательно, в вычислительных системах, работающих под управлением пакетных ОС, невозможно гарантировать выполнение того или иного задания в течение определенного периода времени.
Рассмотрим систему с n идентичными процессорами, на которой необходимо решить L независимых задач; каждая задача решается одним процессором в течение времени t i , i=1,...,L. Требуется найти алгоритм, который для каждого данного пакета (набора) строил бы расписание решения задач на процессорах системы, обеспечивающее минимально возможное время решения. При этом достигается максимально возможная производительность системы. Например, в случае 2-процессорной системы и набора задач с временами (3,3,2,2,2) возможны различные варианты назначения задач на решение. Приведем некоторые из них:
Очевидно, что наилучший в смысле минимизации общего времени решения задач - вариант с, для которого время Т решения пакета задач совпадает с соответствующим оптимальным значением Т0 и в данном случае равно величине ? = max {max ti, l/n*?ti }
Величина ? является нижней границей для оптимального значения Т0. Действительно, длина Т любого расписания не может быть меньше ни max ti - максимального из времен решения задач пакета П, ни величины (1/n *?ti), дающей длину расписания в том случае, когда до момента завершения решения последней из задач пакета ни один процессор не простаивает, т.е. все процессоры имеют 100% загруженности.
В общем случае даже при n = 2 задача поиска оптимального значения Т при условии решения задач, является NP-трудной, т.е. все известные алгоритмы ее решения имеют трудоемкость, экспоненциально зависящую от L. Однако, если допустить возможность прерывания решения задач пакета до завершения их обслуживания, то могут быть предложены полиномиально-трудоемкие алгоритмы, приводящие к расписанию оптимальной длины Т0. При этом считается, что после прерывания решение задачи может быть возобновлено с точки прерывания на любом процессоре, не обязательно на том, на котором она первоначально решалась. Число прерываний должно быть по возможности меньшим, так как с каждым актом прерывания связаны потери машинного времени на загрузку-выгрузку задач из оперативной памяти.
Рассмотрим предложенный Макнотоном в 1959 г. алгоритм построения оптимального по длине расписания с не более чем n-1 прерываниями.
Алгоритм Макнотона заключается в предварительном упорядочении задач по убыванию времени решения и назначении задач последовательно по порядку номеров одну за другой на процессоры системы справа налево от уровня ?.
n=2, L=4, времена решения задач: (5,4,3,2). Тогда
И расписание, полученное в соответствии с алгоритмом Макнотона,
В данном случае число прерываний равно единице.
Покажем, что n-1 (максимальное число прерываний для расписания, полученного в соответствии с алгоритмом Макнотона) является достижимой границей числа прерываний. Для доказательства этого построим такой пример пакета задач, для которого алгоритм Макнотона дает расписание с числом прерываний n-1.
Тогда ? = max { n, 1/n * (n+l)*n = n+1, а расписание, получаемое в соответствии с алгоритмом Макнотона, имеет вид:
Число прерываний в этом случае, как видно, равно n-1, что и требовалось показать. Покажем теперь, что любое оптимальное расписание для этого пакета задач также имеет не менее n-1 прерываний. Очевидно, что в любом оптимальном расписании ни один процессор не простаивает на интервале [0,n+1]. Предположим, что существует некоторое оптимальное расписание с числом прерываний, меньшим n-1. Тогда, по крайней мере, 2 процессора (предположим для определенности Рк и Pl) обслуживают заявки без прерываний. Очевидно, эти процессоры обслуживают некоторые задачи Zik и Zil в интервале [0,n] без прерываний (если решение этих задач начинается позже момента времени t=0, значит до этого момента на этих процессорах решались некоторые другие задачи, решение которых прерывается в моменты начала решения задач Zik и Zil). Найдутся моменты времени t, t', такие, что n ? t < t' ? n+1, и в интервале [t, t'] хотя бы один процессор простаивает, а потому рассматриваемое решение не может быть оптимальным. Так как мы пришли к противоречию, делаем вывод о том, что предположение о числе прерываний, меньшем n-1, в оптимальном расписании ложно.
Рассмотрим систему, содержащую n идентичных процессоров, на которой необходимо решить без прерываний набор из L независимых задач с временами решения t i , i=1,...,L. Получение расписания с минимальным временем решения и в этом случае является NP-трудной задачей. Один из наиболее эффективных и нетрудоемких алгоритмов организации вычислений в этом случае -- алгоритм LPT ( longest-processing task f i rs t - самая длинная задача решается первой), являющийся частным случаем алгоритма критического пути для независимых задач. Суть этого алгоритма заключается в назначении задач в порядке убывания времени решения на освобождающиеся процессоры. Сотрудником фирмы ВellLaboratories США, Грэхемом в 1967г. был получен следующий результат:
При использовании алгоритма LPT для распределения любого пакета П={Zi}, где i=1,…,L, независимых задач без прерываний в системе с n идентичными процессорами справедливо: Т ? (4/3-1/3n)*Т0, где Т- время решения пакета П при распределении задач алгоритмом LPT.
Приведенная оценка является наилучшей.
Исследование алгоритма планирования вычислительного процесса мультипроцессорных систем при пакетной обработке задач и написание программы, реализующей демонстрацию вычислительного процесса мультипроцессорных систем при пакетной обработке данных. курсовая работа [298,2 K], добавлен 24.06.2013
Исследование алгоритма планирования вычислительного процесса мультипроцессорных систем при пакетной обработке задач. Создание программы на языке Turbo Pascal 7.0, реализующей демонстрацию вычислительного процесса систем при обработке пакетов данных. курсовая работа [388,7 K], добавлен 24.06.2013
Общая характеристика основных операций с процессами. Мультипрограммирование как способ организации вычислительного процесса. Цели, алгоритмы и оценка эффективности систем пакетной обработки. Достоинства и недостатки интерактивных операционных систем. реферат [558,0 K], добавлен 09.10.2010
Критерии и основные стратегии планирования процессора. Разработка моделей алгоритмов SPT (Shortest-processing-task-first) и RR (Round-Robin). Сравнительный анализ выбранных алгоритмов при различных условиях и различном количестве обрабатываемых данных. курсовая работа [179,3 K], добавлен 21.06.2013
Разработка вычислительной однопроцессорной программы, реализующей работу процессора по обработке очереди заявок переменной длины без предварительной сортировки заявок по длительности, с предварительной сортировкой заявок по длительности, по алгоритму SPT. курсовая работа [141,7 K], добавлен 21.06.2013
Основные принципы организации пакетной связи, структура ее кадра, состав и назначение используемой аппаратуры, ее функциональные особенности. Управление в режимах пакетной связи. Этапы разработки программы, ее листинг, применяемые языки программирования. дипломная работа [4,3 M], добавлен 20.04.2012
Нахождение рационального порядка следования запросов для обеспечения максимального критерия эффективности использования компонентов вычислительного процесса в системе. Метод ветвей и границ для максимально быстрого выполнения вычислительного процесса. курсовая работа [196,3 K], добавлен 23.08.2009
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Исследование алгоритмов планирования вычислительного процесса мультипроцессорных систем при пакетной обработке задач курсовая работа. Программирование, компьютеры и кибернетика.
Сочинение Чем Опасно Малодушие
Реферат На Тему Ацетиленові Генератори
Дипломная работа: Достоверность библейских данных в контексте светской истории и археологии
Учебное пособие: Среднетехнический факультет
Преступление И Наказание Сочинение Добро
Реферат по теме Методика обучения дошкольников элементам спортивным игр. Овладение элементами игры в баскетбол детьми старшего дошкольного возраста
Решение Контрольных Работ По Физике 8
Реферат: Главные вехи жизни и творчества В. С. Соловьёва. Его основные идеи. Скачать бесплатно и без регистрации
Реферат: Al Capone And His Ascent To Power
Релігійне життя України в роки війни та післявоєнний час
Реферат по теме Демократическое урегулирование внутригосударственных конфликтов в Судане
Учебное пособие: Методические указания и контрольные задания для студентов-заочников Салаватского индустриального колледжа по специальности 150411 «Монтаж и техническая эксплуатация промышленного оборудования» и240404 “Переработка нефти и газа”. 2009
Сочинение по теме Шибалково семя. Шолохов М.А.
Гражданское И Трудовое Право Реферат
Подготовка К Контрольной Работе Present Perfect
Теоретические Основы Безопасности Реферат
Реферат: Принципы реализации машин БД
Сочинение по теме Анализ стихотворения Н. А. Некрасова «Еду ли ночью по улице темной...»
Эссе В Магистратуру По Направлению Психология Примеры
Контрольная работа по теме Хищение. Разбой
Жизнь и творчество Фадеева - Литература реферат
Виконання покарання у виді арешту - Государство и право реферат
Франсуа Буше - Культура и искусство презентация