Реализация стратегии диспетчеризации SJF

Размещено на http://www.allbest.ru/

Введение

Планирование и диспетчеризация процессора - одна из важнейших функций операционной системы.

- Основные понятия диспетчеризации процессов

- Критерии диспетчеризации

- Алгоритмы диспетчеризации

- Диспетчеризация нескольких процессоров

- Диспетчеризация в реальном времени

- Многоуровневые очереди.

Диспетчеризация процессора - распределение его времени между процессами в системе. Цель диспетчеризации - максимальная загрузка процессора, достигаемая с помощью мультипрограммирования.

Исполнение любого процесса можно рассматривать как цикл CPU / I-O - чередование периодов использования процессора и ожидания ввода-вывода. Распределение периодов активности процессора (bursts) и ввода-вывода изображено на рисунке 1.

Последовательность активных фаз процессора и фаз ввода-вывода.

Рисунок 1

На рисунке 2 изображена примерная гистограмма периодов активности процессора, основанная на анализе реального поведения процессов в операционных системах (ОС).

Гистограмма периодов активности процессора

Рисунок 2

Из схемы видно, что чем короче период активности, тем выше частота таких периодов, и наоборот, т.е. частота периодов активности обратно пропорциональна их длительности.

1. Планировщик процессора

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

1. Переключается из состояния выполнения в состояние ожидания.

2. Переключается из состояния выполнения в состояние готовности к выполнению.

3. Переключается из состояния ожидания в состояние готовности.

4. Завершается.

Диспетчеризация типов 1 и 4 обозначается термином диспетчеризация без прерывания процесса (non-preemptive).

Диспетчеризация типов 2 и 3 обозначается термином диспетчеризация с прерыванием процесса (preemptive).

1.1 Диспетчер процессора

Диспетчер процессора - компонента ОС, предоставляющая процессор тому процессу, который был выбран планировщиком. Диспетчер выполняет последовательность действий:

- Переключает контекст

- Переключает процессор в пользовательский режим

- Выполняет переход по соответствующему адресу в пользовательскую программу для ее рестарта.

Скрытая активность (латентность) диспетчера (dispatch latency) - время, требуемое для диспетчера, чтобы остановить один процесс и стартовать другой. Разумеется, система должна стремиться минимизировать это время, однако набор критериев диспетчеризации более сложен.

1.2 Критерии диспетчеризации

Имеется пять основных критериев диспетчеризации процессора, которые так или иначе должны учитываться системой.

Использование процессора (CPU utilization) - поддержание его в режиме занятости максимально возможный период времени. Критерий оптимизации: максимизация данного показателя.

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

Время обработки процесса (turnaround time) - время, необходимое для исполнения какого-либо процесса. Критерий оптимизации: минимизация.

Время ожидания (waiting time) - время, которое процесс ждет в очереди процессов, готовых к выполнению. Критерий оптимизации: минимизация.

Время ответа (response time) - время, требуемое от момента первого запроса до первого ответа. Критерий оптимизации: минимизация.

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

1.3 Стратегия First-Come-First-Served (fcfs)

Стратегия First-Come-First-Served (обслуживание в порядке поступления) - наиболее простая стратегия диспетчеризации, при которой ресурсы процессора предоставляются процессам в порядке их поступления (ввода) в систему, независимо от потребляемых ими ресурсов, в частности, от заявленного процессом времени, требуемого для его выполнения. При рассмотрении этой и других стратегий будем использовать диаграммы Ганта (Gantt charts) изображающие имена процессов и временные диапазоны их выполнения, выраженные в некоторых единицах времени.

Рассмотрим следующий пример. Пусть процессы P₁, P₂ и P₃ введены в систему в указанном порядке со следующими периодами активности:

Процессы	Период активности
P1	24
P2	3
P3	3

Тогда при использовании стратегии FCFS для их диспетчеризации первым получит процессор первый процесс, несмотря на то, что он - наиболее долгий. Распределение процессора между процессами в данном случае изображено на рисунок 3.

Схема диспетчеризации по стратегии FCFS (пример 1)

Рисунок 3

Таким образом, время ожидания для P₁ = 0; P₂= 24; P₃ = 27.

Среднее время ожидания: (0 + 24 + 27)/3 = 17.

Если порядок процессов иной: P₂, P₃, P₁ (последний введенный в систему процесс - самый долгий), то результат их диспетчеризации будет совершенно иным (рисунок 4)

Схема диспетчеризации по стратегии FCFS (пример 2).



Рисунок 4

Время ожидания процессов в данном случае: P₁ = 6; P₂ = 0; P₃ = 3.

Среднее время ожидания: (6 + 0 + 3)/3 = 3

Данный результат много лучше, чем в предыдущем случае.

Эффект, продемонстрированный первым примером, носит название эффекта сопровождения (convoy effect) - увеличение среднего времени ожидания процессов в случаях, если короткий процесс обслуживается после долгого процесса.

2. Стратегия Shortest Job First (SJF)

Стратегия Shortest Job First (SJF, обслуживание самого короткого задания первым) - стратегия диспетчеризации процессора, при которой процессор предоставляется в первую очередь наиболее короткому процессу из имеющихся в системе.

В данном случае с каждым процессом связывается длина его очередного периода активности. Эта длина используется для того, чтобы первым обслужить самый короткий процесс.

Возможны две схемы применения данной стратегии:

1) Без прерывания процессов - пока процессу предоставляется процесс, он не может быть прерван, пока не истечет его квант времени.

2) С прерыванием процессов - если приходит новый процесс, время активности которого меньше, чем оставшееся время активного процесса, - прервать активный процесс. Эта схема известна под названием Shortest-Remaining-Time-First (SRTF).

Нетрудно видеть, что стратегия SJF оптимальна, в том смысле, что она обеспечивает минимальное среднее время ожидания для заданного набора процессов.

Рассмотрим пример применения стратегии SJF без прерывания процессов. Пусть набор процессов, времен их появления в системе и времен их активности следующие:

Процесс	Время появления	Время активности
P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

Схема их диспетчеризации по стратегии 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 на практике

3.1 Реализация стратегии диспетчеризации SJF

И вот уже объяснив суть Shortest Job First, хотелось бы показать, где собственно используется данная стратегия. Покажем на примере перевода элементов данных из одного источника в другой. Это стратегия существенно снижает среднее время ожидания.

Например, группа читателей ждут, пока элементы станут доступными в определенном пункте назначения. Автор с ограниченными возможностями подключения (недостаточная пропускная способность, недостача ресурсов сервера или длиннолатентная (latency перевод с англ. задержка) ссылка для его читателей) влияет на издателя, который дает доступ к элементам читателям.

Это работа мотивированна работой инфраструктуры типичной Веб-публикации на сегодняшний день, где содержание элемента автора загружается на AWeb сервер, а не непосредственно к читателю. Если объем данных элементов больше чем пропускная способность линии - как в случае отправки изображения с высоким разрешением или длинных видеоролики, загружаемых через широкополосное соединение или через беспроводную связь мобильного устройства, то автор будет заинтересован в сокращении времени, пока его элементы станут доступны читателям. Принцип работы Веб-публикации подробно показан на рисунке 7. Набор элементов (и i) загружен на сайт издателя. Издатель информирует автора о популярности(Pi) каждого элемента в отдельности.

Принцип работы Веб-публикации



Рисунок 7

Конкретные примеры этого являются веб-бытовые услуги общего доступа к файлам как. Mac и Steamload, которые позволяют пользователям обмениваться большими файлами, а так же вести хостинг для мультимедийного контента. Содержание распределительной сети (такие как Akamai и интернет Mirror Image) в которой большие файлы копируются на серверы находящиеся в географической близости для пользователей, в том числе и для автора (если у него ограниченная пропускная способность). Если файлы копируются «По требованию», например, по популярности, то для этого файла уделяется производительность, уменьшается время ожидания. Наша стратегия состоит в том, что бы уменьшить время работы (SJF), сделать алгоритм для передачи элемента и рассортировать по популярности. Планировщик вычисляет, основываясь на размерах файлов; сколько читателей запрашивали этот файл. Несколько запросов от одного читателя рассматривается как один.

Мы считаем, что для каждого автора есть конечное множество элементов данных для загрузки. Издатель знает количество элементов (например, получив список всех элементов) и имеет возможность сохранить их все. Кроме того, мы предлагаем неограниченные возможности связи между читателями и издателем, но ограниченные возможности связи между издателем и автором. Таким образом, читатель имеет доступ к любому элементу, он становится доступным для читателя, как только полностью будет загружен на издателя. Время между первым запросом и завершении загрузки назовем как «Время ожидания». Установка всего процесса подробно показана на рисунке 7, где набор элементов показан как (и i), а популярность показана как (Pi).

Этот принцип имеет смысл когда автор загружает процессы на издателя и процессы не требуют сложных расчетов. Например, когда мы переносим содержимое жесткого диска с объемом 500-Гб через Gigabit Ethernet и передачи нескольких десятков видео, каждое по 10 Мб, через ADSL соединение (максимальная скорость передачи 128 кбит/с), оба потребуют больше часа на передачу. Время передачи такое же как, передача несколько широкоформатных изображении «raw» (перевод с англ сырой), в 8-мегапиксельной камере, через беспроводной сети 3G. Мы не берем в счет пропускную способность канала, но вместо этого экспортируем с более широким спектром время передачи, которые могут связаны с конкретными сценариями, которые перечислены выше.

Мы предлагаем два варианта расписания стратегии. Первый из них, является статистическим, в смысле, что популярность данных элементов фиксирована и известна до начала загрузки. Доказано что планирование SJF на основе отношения размера приводит к минимальному времени ожидания.

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

3.2 Статический способ

процессор обслуживание задание стратегия

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

Рассмотрим множество ?, где N задач (элементы будут загружены):

Формула (1)

?=(и1, и2,… иn).

Если время начинается в то время, когда множество ? готово к передаче в издательство, и если время fi, когда задача иi была загружена, то среднее время ожидания (AWT average waiting time) для всех задач этого множества при графике у:

формула AWT(2)

Это определение AWT выражает среднее время ожидания для каждого запроса, основываясь на том, сколько ждет читатель до начала загрузки. Для учета элементов запрашиваемых больше чем одним читателем, мы включаем популярность pi элемента иi. То есть количество читателей обслужено им. Выражено здесь на рисунке 9:

Формула AWT (по популярности) (3)

И вместо нахождения среднего по количеству задач, N, усреднить от общего количества ожидающих запросов M рисунок 10:

Усреднить от общего количества

Обратите внимание, что при р = 1 ? я, то (3) эквивалентно (2). Не запрошенные элементы (р = 0) не включены в ожидание времени, так что никто не ждет их. Мы предполагаем, что их передача откладывается до тех пор пока не передадутся запрошенные элементы.

Заключение

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

Мы доказали, что элементы планирования данных, разместив по популярности и по размеру, и минимизирует среднее время ожидания (AWT), как определенно в (2), при pi не меняется со временем и планируем, один раз до начала передачи. Мы показали, как этот алгоритм работает лучше, чем обычный простой SJF который использует в качестве вычислительных затрат только размер элемента. Кроме того, мы обнаружили, что если элементов много (больше шести), то наша формула не поможет производительности. В будущем мы надеемся, что получиться увеличить количество элементов

Исходя их всех вышеизложенных формул, можно увидеть, что стратегия Shortest Job First существенно уменьшает среднее время ожидания. И реализует движок работы многих веб сайтов, веб-публикации и серверов, таких как youtube.com, tweeter.com, depositfiles.com и т.д.

Список литературы

1. В.О. Сафонов. Основы современных операционных систем. http://www.untuit.ru

2. Simone Lupetti, Dmitrii Zagorodnov. Data popularity and shortest-job-first scheduling of network transfer. IKT 2010 project number 146986/431. University of Tromso

Приложение

КОД ПРОГРАММЫ SJF НА ЯЗЫКЕ С++

# include<stdio.h>

# include<conio.h>

# include<alloc.h>

struct node

{int process_no;

int btime;

struct node *link;

};

void append (struct node **, int, int);

void display (struct node *, int);

void chart (struct node **);

void main()

{clrscr();

struct node *p;

p = NULL; /* Empty Linked list */

int i=1, time;

char ans = 'y';

while (ans!= 'n')

{printf («\nEnter Burst Time For Process No.%d:», i);

scanf («%d»,&time);

append (&p, i, time);

printf («Any More Process (Y/N)?»);

ans = getche();

i++;

}

getch();

clrscr();

printf («\nThe Order Of Execution Of Process For SJF Algorithm Will be: -»);

display (p, 1);

getch();

printf («\nThe Waiting Time Of Process For SJF Algorithm Will be: -»);

display (p, 2);

getch();

chart(&p);

getch();

}

void append (struct node **q, int i, int time)

{struct node *r,*temp = *q;

r = (struct node *) malloc (sizeof(struct node));

r->process_no = i;

r->btime = time;

/* If list is empty or new data to be inserted b4 the first node */

if (*q==NULL || (*q)->btime > time)

{*q = r;

(*q)->link = temp;

}

else

{/* traverse the entire linked list

to search the position the new node to be inserted */

while (temp!= NULL)

{if (temp->btime <=time &&(temp->link->btime > time || temp->link ==NULL))

{r->link = temp->link;

temp->link = r;

r->link = NULL;

}

temp = temp->link;

}

}

}

void display (struct node *q, int kk)

{struct node *temp;

int wtime, avg=0, total = 0, count=0;

temp = q;

int i;

printf («\n»);

printf («\n\t\t % c», 218);

for (i=1; i<33; i++)

{if (i==17)

printf («%c», 194);

else

printf («%c», 196);

}

printf («%c», 191);

if (kk==1)

{printf («\n\t\t % c PROCESS NO. %c BURST TIME %c\n», 179,179,179);

}

if (kk==2)

{printf («\n\t\t % c PROCESS NO. %c WAIT TIME %c\n», 179,179,179);

}

printf («\t\t % c», 195);

for (i=1; i<33; i++)

{if (i==17)

printf («%c», 197);

else

printf («%c», 196);

}

printf («%c», 180);

while (temp!=NULL)

{count++;

if (kk==1)

{printf («\n\t\t % c %d. %c %3d %c», 179, temp->process_no, 179, temp->btime, 179);

}

if (kk==2)

{if (temp ==q) /* First Process In The Ready Queue */

{wtime = 0;

total+= temp->btime;

avg+=wtime;

}

else

{wtime = total;

total+= temp->btime;

avg +=wtime;

}

printf («\n\t\t % c %d. %c %3d %c», 179, temp->process_no, 179, wtime, 179);

}

temp=temp->link;

}

printf («\n\t\t % c», 192);

for (i=1; i<33; i++)

{if (i==17)

printf («%c», 193);

else

printf («%c», 196);

}

printf («%c», 217);

if (kk==2)

{printf («\nThe Average Waiting Time (%d % c % d) =%.2f», avg, 246, count, float (avg/float(count)));

}

}

void chart (struct node **q)

{

printf («\n»);

printf («\nThe Glant Chart Is As Follows:-\n»);

struct node *temp,*temp1,*temp2,*temp3,*temp4;

temp = *q; temp1 = *q; temp2 = *q; temp3 = *q; temp4=*q;

int sum = 0; float sfactor;

while (temp4!=NULL)

{sum+=temp4->btime;

temp4 = temp4->link;

}

if (sum<80)

{sfactor = 1.0;

}

else

{sfactor = (sum % 80)/float(sum);

}

int i, k=0;

printf («%d», k);

while (temp3!= NULL)

{if((sfactor*temp3->btime) == 0)

{goto harsh;

}

for (i=-1; i<=(sfactor*temp3->btime); i++)

{printf(«»);

}

k+=temp3->btime;

printf («%d», k);

harsh:

temp3=temp3->link;

}

printf («\n»);

while (temp!=NULL)

{if (temp == *q)

{

printf («%c % c», 218,196);

if((sfactor*temp->btime) == 0)

{goto last;

}

for (i=-1; i<=(sfactor*temp->btime); i++)

{printf («%c», 196);

}

if (temp->link!= NULL)

{printf («%c», 194);

}

else

{printf («%c», 191);

}

}

else

{if((sfactor*temp->btime) == 0)

{goto last;

}

for (i=-1; i<=(sfactor*temp->btime); i++)

{printf («%c», 196);

}

if (temp->link!= NULL)

{printf («%c», 194);

}

else

{printf («%c», 191);

}

}

last:

temp = temp->link;

}

printf («\n»);

printf («%c», 179);

while (temp1!= NULL)

{if((sfactor*temp1->btime) == 0)

{goto last1;

}

for (i=0; i<=(sfactor*temp1->btime); i++)

{if (i==int (sfactor*temp1->btime)/2)

{printf («P % d», temp1->process_no);

}

else

printf(«»);

}

printf («%c», 179);

last1:

temp1 = temp1->link;

}

printf («\n»);

while (temp2!=NULL)

{if (temp2 == *q)

{printf («%c % c», 192,196);

if((sfactor*temp2->btime) == 0)

{goto last2;

}

for (i=-1; i<=(sfactor*temp2->btime); i++)

{printf («%c», 196);

}

if (temp2->link!= NULL)

{printf («%c», 193);

}

else

{printf («%c», 217);

}

}

else

{if((sfactor*temp2->btime) == 0)

{goto last2;

}

for (i=-1; i<=(sfactor*temp2->btime); i++)

{printf («%c», 196);

}

if (temp2->link!= NULL)

{printf («%c», 193);

}

else

{printf («%c», 217);

}

}

last2:

temp2=temp2->link;

}

}

Размещено на Allbest.ru