Реализация стратегии диспетчеризации SJF
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
? предыдущем случае.
Эффект, продемонстрированный первым примером, носит название эффекта сопровождения (convoy effect) - увеличение среднего времени ожидания процессов в случаях, если короткий процесс обслуживается после долгого процесса.
2. Стратегия Shortest Job First (SJF)
Стратегия Shortest Job First (SJF, обслуживание самого короткого задания первым) - стратегия диспетчеризации процессора, при которой процессор предоставляется в первую очередь наиболее короткому процессу из имеющихся в системе.
В данном случае с каждым процессом связывается длина его очередного периода активности. Эта длина используется для того, чтобы первым обслужить самый короткий процесс.
Возможны две схемы применения данной стратегии:
1)Без прерывания процессов - пока процессу предоставляется процесс, он не может быть прерван, пока не истечет его квант времени.
2)С прерыванием процессов - если приходит новый процесс, время активности которого меньше, чем оставшееся время активного процесса, - прервать активный процесс. Эта схема известна под названием Shortest-Remaining-Time-First (SRTF).
Нетрудно видеть, что стратегия SJF оптимальна, в том смысле, что она обеспечивает минимальное среднее время ожидания для заданного набора процессов.
Рассмотрим пример применения стратегии SJF без прерывания процессов. Пусть набор процессов, времен их появления в системе и времен их активности следующие:
ПроцессВремя появленияВремя активностиP10.07P22.04P34.01P45.04
Схема их диспетчеризации по стратегии SJF без прерывания процессов приведена на рисунке 5.
Схема диспетчеризации процессов по стратегии SJF без прерывания.
Рисунок 5
В данном случае среднее время ожидания = (0 + 6 + 3 + 7)/4 = 4.
Теперь применим к тем же процессам стратегию SJF с прерыванием и проанализируем, как изменится среднее время ожидания. Результат применения стратегии изображен на рисунке 6.
Схема диспетчеризации процессов по стратегии SJF с прерываниями.
Рисунок 6
В данном случае принцип прерывания процесса в момент поступления в систему более короткого процесса применяется несколько раз:
-в момент 2 прерывается процесс 1 и начинает исполняться более короткий процесс 2;
-в момент 4 прерывается процесс 2 и начинает исполняться более короткий процесс 3.
Из диаграммы видно, что, вследствие применения принципа прерывания процессов, периоды непрерывного выполнения процесса на процессоре могут быть не смежными и перемежаться с периодами выполнения других процессов.
В данном случае среднее время ожидания = (9 + 1 + 0 +2)/4 = 3, т.е. оно, как и следовало предполагать, оказалось меньше, чем без применения принципа прерывания процессов.
3. Использование SJF на практике
.1 Реализация стратегии диспетчеризации SJF
И вот уже объяснив суть Shortest Job First, хотелось бы показать, где собственно используется данная стратегия. Покажем на примере перевода элементов данных из одного источника в другой. Это стратегия существенно снижает среднее время ожидания.
Например, группа читателей ждут, пока элементы станут доступными в определенном пункте назначения. Автор с ограниченными возможностями подключения (недостаточная пропускная способность, недостача ресурсов сервера или длиннолатентная (latency перевод с англ. задержка) ссылка для его читателей) влияет на издателя, который дает доступ к элементам читателям.
Это работа мотивированна работой инфраструктуры типичной Веб-публикации на сегодняшний день, где содержание элемента автора загружается на AWeb сервер, а не непосредственно к читателю. Если объем данных элементов больше чем пропускная способность линии - как в случае отправки изображения с высоким разрешением или длинных видеоролики, загружаемых через широкополосное соединение или через беспроводную связь мобильного устройства, то автор будет заинтересован в сокращении времени, пока его элементы станут доступны читателям. Принцип работы Веб-публикации подробно показан на рисунке 7. Набор элементов (? i) загружен на сайт издателя. Издатель информирует автора о популярности(Pi) каждого элемента в отдельности.
Принцип работы Веб-публикации
Рисунок 7
Конкретные примеры этого являются веб-бытовые услуги общего доступа к файлам как. Mac и Steamload, которые позволяют пользователям обмениваться большими файлами, а так же вести хостинг для мультимедийного контента. Содержание распределительной сети (такие как Akamai и интернет Mirror Image) в которой большие файлы копируются на серверы находящиеся в географической близости для пользователей, в том числе и для автора (если у него ограниченная пропускная способность). Если файлы копируются По требованию, например, по популярности, то для этого файла уделяется производительность, уменьшается время ожидания. Наша стратегия состоит в том, что бы уменьшить время работы (SJF), сделать алгоритм для передачи элемента и рассортировать по популярности. Планировщик вычисляет, основываясь на размерах файлов; сколько читателей запрашивали этот файл. Несколько запросов от одного читателя рассматривается как один.
Мы считаем, что для каждого автора есть конечное множество элементов данных для загрузки. Издатель знает количество элементов (например, получив список всех элементов) и имеет возможность сохранить их все. Кроме того, мы предлагаем неограниченные возможности связи между читателями и издателем, но огр?/p>