N
|
T
|
tp
|
Pr
|
0
|
30
|
5
|
3
|
1
|
20
|
30
|
8
|
2
|
40
|
27
|
11
|
3
|
40
|
29
|
5
|
4
|
70
|
107
|
7
|
5
|
50
|
113
|
5
|
6
|
70
|
174
|
9
|
7
|
50
|
183
|
10
|
8
|
90
|
327
|
19
|
9
|
30
|
379
|
13
|
2.3 Исходные условия
Вариант выбирается согласно последним двум цифрам зачетной книжки (09).
Соответственно варианту выбираются дисциплины обслуживания, то есть:
·
бес
приоритетная: FB - Feed Back (обратная связь) - многоуровневый
циклический алгоритм
·
приоритетная:
ДО динамическим приоритетом (зависимость от времени обслуживания - tобсл..);
планирование алгоритм
диспетчеризация моделирование
2.4 Диспетчеризация задач для
бесприоритетной ДО FB
На рисунке 4 представлена схема циклической ДО (FB)
Рис. 4. Схема циклической ДО (FB)
n=1 -
это первая очередь, в нее поступает входной поток заявок. Из нее заявка
поступает на ресурс и/или полностью обслуживается или снова поступает в
очередь, но с номером на 1 больше. Поток заявок поступает в самую приоритетную
очередь n=1. Заявка получает квант и переходит
в очередь n+1. Заявка в i-ой очереди обслуживается, если пусты все остальные очереди.
В очереди N заявки обслуживаются до завершения
(в очереди N принцип FIFO + RR).
Рис.5. Алгоритм ДО FB.
2.5 Диспетчеризация задач для ДО с
динамическим приоритетом (зависимость от времени обслуживания)
Приоритет изменяется в период выполнения задания (tобсл.). На рисунке представлена временная
диаграмма изменения приоритета от времени.
Рис.6. Временная диаграмма изменения приоритета от времени.
Особенности организации: Дисциплина обслуживания, основанная на
абсолютных приоритетах. Во время выполнения процесса его приоритет уменьшается
с каждым тиком. Если приоритет процесса становится меньше приоритета процесса
стоящего в очереди готовых, процесс будет вытеснен с выполнения. Это позволяет
уменьшить дискриминацию процессов, возникающую при использовании дисциплин
обслуживания с абсолютными приоритетами. Для ДО с линейно возрастающим
приоритетом характерна зависимость:
Pi(t) = ai*tожид. + bi*tвыполн., где Pi(t) - приоритет i- ой
работы.
Смена выполняющегося задания происходит в следующих случаях:
1. процесс завершен или произошла ошибка;
2. процесс перешел в состояние ожидания;
. приоритет задания становится меньше, чем у ожидающего в очереди
готовых задания с наибольшим приоритетом
. в очереди появился процесс с большим приоритетом
Достоинства системы с динамическим приоритетом:
· возможность настраиваться при изменении характеристик
входного потока на эффективное обслуживание;
· дисциплина основана на реальных динамических характеристиках
заявок.
· Учитывает приоритетность задач
· Уменьшает возможность недобросовестного использования
механизмов приоритетов
Недостатки:
· Возможность бесконечного откладывания низкоприоритетных
процессов
· Сложная организация, так как необходим пересчет приоритетов
Рис.7. Блок-схема алгоритма ДО с динамическим приоритетом.
.6 Алгоритм функционирования
диспетчера
Диспетчер определяет, какой работе выделить квант времени следующим
образом. После того, как запускается процесс связанный с диспетчером происходит
анализ причин прерывания проблемной работы. Причин прерывания может быть несколько:
истёк выделенный квант времени, работа полностью выполнилась и завершилась.
Поступление новых работ не прерывает выполнение текущих, а анализируется
диспетчером, после окончания выделенного кванта.
После анализа прерывания и изменения очереди на выполнение (исключение
завершившихся, добавление поступивших) диспетчер принимает решение, какой из
работ выделить следующий квант времени. Это решение принимается на основе одной
из двух дисциплин обслуживания FB и
ДП.
Рис. 8. Блок-схема алгоритма диспетчера.
2.7 Описание программы
Программа Disp позволяет
произвести моделирование c
помощью одного из двух алгоритмов: FB или обслуживание с динамическим приоритетом (зависимость от времени
обслуживания tобсл).
Запуск программы осуществляется по команде Disp.exe
Внешний вид программы представлен на рисунке 9.
В меню программы можно задать параметры моделирования.
SV -
время работы супервизора;
PROC -
продолжительность кванта времени в течении которого обрабатывается задание;
Рабочая область поделена на подобласти в верхнем самом большом окне
выводится временная диаграмма моделирования по одному из выбранному алгоритму,
внизу расположены 2 окна (слева и справа), в которые выводится трассировка по
каждому алгоритму (слева - FB, справа
- с динамическим приоритетом).
Так же предусмотрена кнопка Clear - очистить, для того чтобы можно было несколько раз выводить временные
диаграммы разных алгоритмов.
Рис.9. Внешний вид программы
.8 Результаты моделирования.
Временные диаграммы
Рис.10. Временная диаграмма результатов моделирования алгоритма FB
Рис.11. Временная диаграмма результатов моделирования алгоритма с
динамическим приоритетом
Заключение
В результате проделанной работы были пополнены знания о общей организации
ОС, её внутренней структуре, разновидностях, алгоритмах работы основных
составляющих ОС, были изучены принципы планирования управления вычислительными
ресурсами верхнего уровня, а также диспетчирования (управления процессами).
Были построены временные диаграммы мультипрограммной работы каждого, из
указанных в задании алгоритмов. И проведено сравнение двух случаев по
средневзвешенному времени обращения. По результатам построения временных
диаграмм ДО SJF (средневзвешенное время 4.04единиц)
оказалась немного более эффективной, чем ДО FIFO (4.70единиц).
Была составлена учебная программа-симулятор наглядно демонстрирующая
работу диспетчера с помощью временных диаграмм. Программа-симулятор диспетчера
позволяет рассмотреть работу таких ДО как LIFO и обслуживание с динамическим приоритетом (от tобсл).
Подробная трассировка алгоритмов в текстовом формате, подкреплена наглядными
временными диаграммами.
При построении диаграмм также учитывались требования задач к ресурсам
системы (оперативная память и внешняя память), а также время загрузки задачи из
внешней памяти.
Список литературы
1. Л.А.
Коршикова. Операционные системы как системы управления вычислительными
ресурсами: Учеб. пособие. - Новосибирск.: НГТУ, 2007. - 52с.: ил.
2. Э.
Таненбаум. Современные операционные системы. 2-е изд. - СПб.: Питер, 2007. - 1038
с.: ил.
Приложение 1. Программная
реализация диспетчера
void CKR_OSDlg::FB()
{
//собственно сам алгоритм
int countT=0;//счетчик
в списке aMCPU
int cTr=0;tT=0;tPT=0;c=0;nIndex=0;s1[10];s2[10]=":
";st;
//oDop.SV=atoi(m_SV);
//oDop.PROC=atoi(m_PROC);OutFile2("trace1.txt",CFile::modeCreate
| CFile::modeWrite);s[80];len=0;x=true;(true)
{.SortTaskTime(oDop.cTask);=1;
tT=oDop.T-cTr;//от чего
oDop.T+=oDop.SV;//до
чего
if (oDop.T==115)
{++;-;
}.Format("%d: Супервизор старт
",tT+cTr);//oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st); (int n=1;n<oDop.cTask;n++)
// проверяем на конец моделирования
if (oDop.aTask[n].b) c++;(c==oDop.cTask)
{.Format("%d: Супервизор финиш
",oDop.T);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);.Format("Конец
моделирования");.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);++;
return;
}
countT=1;
for (int i=1;i<oDop.cTask;i++)//формируем
список только что поступивших задач
if (oDop.aTask[i].Time<oDop.T)
{.tTask[i]=oDop.aTask[i];(oDop.aTask[i].Time>=tT+cTr
&& !oDop.aTask[i].b)
{.aTask[i].Queue=1;
//очередь.tTask[i].Queue=1;.Format("%d: %d задача поступила
",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);
}++;
};.Format("%d: Супервизор финиш
",oDop.T);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);.SortQueue(countT-1);//? сортитуем список по приоритетам
while
(true) // выбираем из списка ту, которая
получит свой квант
{(countT==1) break;(!oDop.tTask[countT-1].b)
{
if (oDop.tTask[countT-1].Trud<=oDop.PROC)
//если осталось у задачи трудоемкость меньше,//чем 5 квантов
{
cTr=oDop.tTask[countT-1].Trud; //то продвигаем время на труд этой
задачи
nIndex=oDop.Index(countT-1);.aTask[nIndex].Trud=0;.aTask[nIndex].b=true;(int
j=1,in=0;j<countT-1;j++)
{=oDop.Index(j);(!oDop.aTask[in].b)
{
//oDop.aTask[in].Function(cTr);
}
}.Format("%d: %d задача начала выполнение
",oDop.T,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st); (int i=1;i<oDop.cTask;i++)//формируем
список только что поступивших задач
if (oDop.aTask[i].Time<oDop.T+cTr)
{(oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)
{.aTask[i].Queue=1; //очередь
//oDop.tTask[i].Queue=1;.Format("%d: %d задача поступила
",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);
}
}.Format("%d: у задачи %d закончился квант времени
",oDop.T+cTr,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);.Format("задача
%d выполнена
",oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);(oDop.cTask);;
}
{=oDop.PROC;//иначеипродвигаем время на 5 квантов
nIndex=oDop.Index(countT-1);
oDop.aTask[nIndex].Trud-=oDop.PROC;// обнуляем трудоемкость
oDop.aTask[nIndex].Prior--;.aTask[nIndex].Queue++;
//очередь(int j=1,in=0;j<countT-1;j++)
{=oDop.Index(j);(!oDop.aTask[in].b)
{
//oDop.aTask[in].Function(cTr);
}
}.Format("%d: %d задача начала выполнение
",oDop.T,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st); (int i=1;i<oDop.cTask;i++)//формируем
список только что поступивших задач
if (oDop.aTask[i].Time<oDop.T+cTr)
{(oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)
{.aTask[i].Queue=1; //очередь.Format("%d: %d задача
поступила
",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);
}
}.Format("%d: у задачи %d закончился квант времени
",oDop.T+cTr,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);(oDop.cTask);;
}
}countT--; //следущая в списке
}
oDop.T+=cTr; //продвигаем модельное время
}
}CKR_OSDlg::Dinam()
{
//собственно сам алгоритм с динамическим приоритетомcountT=0;//счетчик в
списке aMCPU
int cTr=0;tT=0;tPT=0;c=0;nIndex=0;s1[10];s2[10]=":
";st;
//oDop.SV=atoi(m_SV);
//oDop.PROC=atoi(m_PROC);OutFile2("trace1.txt",CFile::modeCreate
| CFile::modeWrite);s[80];len=0;x=true;(true)
{.SortTaskTime(oDop.cTask);
c=1;=oDop.T-cTr;//от чего.T+=oDop.SV;//до чего
if (oDop.T==145)
{++;-;
}.Format("%d: Супервизор старт
",tT+cTr);//oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);
for (int n=1;n<oDop.cTask;n++) // проверяем на конец моделирования
if (oDop.aTask[n].b) c++;(c==oDop.cTask)
{.Format("%d: Супервизор финиш
",oDop.T);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);.Format("Конец моделирования");.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);
cc++;;
}=1;(int i=1;i<oDop.cTask;i++)//формируем список только что
поступивших задач
if (oDop.aTask[i].Time<oDop.T)
{.tTask[i]=oDop.aTask[i];(oDop.aTask[i].Time>=tT+cTr
&& !oDop.aTask[i].b)
{.Format("%d: %d задача
поступила
",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);
}++;
};.Format("%d: Супервизор финиш
",oDop.T);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);
oDop.SortPrior(countT-1);//? сортитуем список по приоритетам(true) //
выбираем из списка ту, которая получит свой квант
{(countT==1) break;(!oDop.tTask[countT-1].b)
{(oDop.tTask[countT-1].Trud<=oDop.PROC) //если осталось у задачи
трудоемкость меньше,//чем 5 квантов
{=oDop.tTask[countT-1].Trud; //то продвигаем время на труд этой задачи
nIndex=oDop.Index(countT-1);.aTask[nIndex].Trud=0;.aTask[nIndex].b=true;(int
j=1,in=0;j<countT-1;j++)
{=oDop.Index(j);(!oDop.aTask[in].b)
{
//oDop.aTask[in].Function(cTr);
}
}.Format("%d: %d задача
начала выполнение
",oDop.T,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);
for (int i=1;i<oDop.cTask;i++)//формируем список только что
поступивших задач
if (oDop.aTask[i].Time<oDop.T+cTr)
{(oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)
{.Format("%d: %d задача
поступила
",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);
}
}.Format("%d: у задачи %d закончился квант времени
",oDop.T+cTr,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);.Format("задача %d выполнена
",oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);(oDop.cTask);;
}
{
cTr=oDop.PROC;//иначеипродвигаем время на 5
квантов=oDop.Index(countT-1);.aTask[nIndex].Trud-=oDop.PROC;// обнуляем
трудоемкость
oDop.aTask[nIndex].Prior--;(int j=1,in=0;j<countT-1;j++)
{=oDop.Index(j);(!oDop.aTask[in].b)
{
//oDop.aTask[in].Function(cTr);
}
}.Format("%d: %d задача
начала выполнение
",oDop.T,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);
for (int i=1;i<oDop.cTask;i++)//формируем список только что
поступивших задач
if (oDop.aTask[i].Time<oDop.T+cTr)
{(oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)
{.Format("%d: %d задача
поступила
",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);
}
}.Format("%d: у задачи %d закончился квант времени
",oDop.T+cTr,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);(oDop.cTask);;
}
}countT--; //следущая в списке
}.T+=cTr; //продвигаем модельное время
}
}