Таблица 5. Сводная таблица для алгоритма SJF

Средневзвешенное время обращения W= 4.386213

Максимальный коэффициент мультипрограммирования равен 4

1.4 Графики

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

Средневзвешенное время обращения зависит от выбора дисциплины обслуживания. Поэтому при проектировании систем очень важное значение имеет выбор дисциплины в зависимости от характера решаемых задач.

Раздел 2. Диспетчеризация

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

Таким образом, цели диспетчирования задач следующие:

- распределение центрального процессора в динамике в соответствии

с критериями;

- эффективная отработка алгоритмов управления задачами.

- сбалансированное использование ресурсов.

- баланс между временем ответа и коэффициентом использования ресурсов.

Итак: диспетчер - это программа, которая выбирает задачи (процессы) из "очереди на выполнение", переводит их в активное состояние и передает их на обработку центральному процессору.

2.2 Задание

2.4 Диспетчеризация задач для бесприоритетной ДО FB

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

Были построены временные диаграммы мультипрограммной работы каждого, из указанных в задании алгоритмов. И проведено сравнение двух случаев по средневзвешенному времени обращения. По результатам построения временных диаграмм ДО SJF (средневзвешенное время 4.04единиц) оказалась немного более эффективной, чем ДО FIFO (4.70единиц).

Была составлена учебная программа-симулятор наглядно демонстрирующая работу диспетчера с помощью временных диаграмм. Программа-симулятор диспетчера позволяет рассмотреть работу таких ДО как LIFO и обслуживание с динамическим приоритетом (от t_обсл). Подробная трассировка алгоритмов в текстовом формате, подкреплена наглядными временными диаграммами.

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

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

2. Э. Таненбаум. Современные операционные системы. 2-е изд. - СПб.: Питер, 2007. - 1038 с.: ил.

Приложение 1. Программная реализация диспетчера

void CKR_OSDlg::FB()

{

//собственно сам алгоритм

int countT=0;//счетчик в списке aMCPU

int cTr=0;

int tT=0;

int tPT=0;

int c=0;

int nIndex=0;

char s1[10];

char s2[10]=": ";

CString st;

//oDop.SV=atoi(m_SV);

//oDop.PROC=atoi(m_PROC);

CFile OutFile2("trace1.txt",CFile::modeCreate | CFile::modeWrite);

char s[80];

int len=0;

bool x=true;

while (true)

{

oDop.SortTaskTime(oDop.cTask);

c=1;

tT=oDop.T-cTr;//от чего

oDop.T+=oDop.SV;//до чего

if (oDop.T==115)

{

countT++;

countT--;

}

st.Format("%d: Супервизор старт ",tT+cTr);//oDop.aTask[i].Time,oDop.aTask[i].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

for (int n=1;n<oDop.cTask;n++) // проверяем на конец моделирования

if (oDop.aTask[n].b) c++;

if (c==oDop.cTask)

{

st.Format("%d: Супервизор финиш ",oDop.T);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

st.Format("Конец моделирования");

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

cc++;

return;

}

countT=1;

for (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T)

{

oDop.tTask[i]=oDop.aTask[i];

if (oDop.aTask[i].Time>=tT+cTr && !oDop.aTask[i].b)

{

oDop.aTask[i].Queue=1; //очередь

oDop.tTask[i].Queue=1;

st.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

}

countT++;

};

st.Format("%d: Супервизор финиш ",oDop.T);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

oDop.SortQueue(countT-1);//? сортитуем список по приоритетам

while (true) // выбираем из списка ту, которая получит свой квант

{

if (countT==1) break;

if (!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);

oDop.aTask[nIndex].Trud=0;

oDop.aTask[nIndex].b=true;

for (int j=1,in=0;j<countT-1;j++)

{

in=oDop.Index(j);

if (!oDop.aTask[in].b)

{

//oDop.aTask[in].Function(cTr);

}

}

st.Format("%d: %d задача начала выполнение ",oDop.T,oDop.aTask[nIndex].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

for (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T+cTr)

{

if (oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)

{

oDop.aTask[i].Queue=1; //очередь

//oDop.tTask[i].Queue=1;

st.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

}

}

st.Format("%d: у задачи %d закончился квант времени ",oDop.T+cTr,oDop.aTask[nIndex].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

st.Format("задача %d выполнена ",oDop.aTask[nIndex].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

GetStrPrior(oDop.cTask);

break;

}

else

{

cTr=oDop.PROC;//иначеипродвигаем время на 5 квантов

nIndex=oDop.Index(countT-1);

oDop.aTask[nIndex].Trud-=oDop.PROC;// обнуляем трудоемкость

oDop.aTask[nIndex].Prior--;

oDop.aTask[nIndex].Queue++; //очередь

for (int j=1,in=0;j<countT-1;j++)

{

in=oDop.Index(j);

if (!oDop.aTask[in].b)

{

//oDop.aTask[in].Function(cTr);

}

}

st.Format("%d: %d задача начала выполнение ",oDop.T,oDop.aTask[nIndex].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

for (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T+cTr)

{

if (oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)

{

oDop.aTask[i].Queue=1; //очередь

st.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

}

}

st.Format("%d: у задачи %d закончился квант времени ",oDop.T+cTr,oDop.aTask[nIndex].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceF.InsertString(-1,st);

GetStrPrior(oDop.cTask);

break;

}

}

else countT--; //следущая в списке

}

oDop.T+=cTr; //продвигаем модельное время

}

}

void CKR_OSDlg::Dinam()

{

//собственно сам алгоритм с динамическим приоритетом

int countT=0;//счетчик в списке aMCPU

int cTr=0;

int tT=0;

int tPT=0;

int c=0;

int nIndex=0;

char s1[10];

char s2[10]=": ";

CString st;

//oDop.SV=atoi(m_SV);

//oDop.PROC=atoi(m_PROC);

CFile OutFile2("trace1.txt",CFile::modeCreate | CFile::modeWrite);

char s[80];

int len=0;

bool x=true;

while (true)

{

oDop.SortTaskTime(oDop.cTask);

c=1;

tT=oDop.T-cTr;//от чего

oDop.T+=oDop.SV;//до чего

if (oDop.T==145)

{

countT++;

countT--;

}

st.Format("%d: Супервизор старт ",tT+cTr);//oDop.aTask[i].Time,oDop.aTask[i].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

for (int n=1;n<oDop.cTask;n++) // проверяем на конец моделирования

if (oDop.aTask[n].b) c++;

if (c==oDop.cTask)

{

st.Format("%d: Супервизор финиш ",oDop.T);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

st.Format("Конец моделирования");

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

cc++;

return;

}

countT=1;

for (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T)

{

oDop.tTask[i]=oDop.aTask[i];

if (oDop.aTask[i].Time>=tT+cTr && !oDop.aTask[i].b)

{

st.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

}

countT++;

};

st.Format("%d: Супервизор финиш ",oDop.T);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

oDop.SortPrior(countT-1);//? сортитуем список по приоритетам

while (true) // выбираем из списка ту, которая получит свой квант

{

if (countT==1) break;

if (!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);

oDop.aTask[nIndex].Trud=0;

oDop.aTask[nIndex].b=true;

for (int j=1,in=0;j<countT-1;j++)

{

in=oDop.Index(j);

if (!oDop.aTask[in].b)

{

//oDop.aTask[in].Function(cTr);

}

}

st.Format("%d: %d задача начала выполнение ",oDop.T,oDop.aTask[nIndex].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

for (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T+cTr)

{

if (oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)

{

st.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

}

}

st.Format("%d: у задачи %d закончился квант времени ",oDop.T+cTr,oDop.aTask[nIndex].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

st.Format("задача %d выполнена ",oDop.aTask[nIndex].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

GetStrPrior(oDop.cTask);

break;

}

else

{

cTr=oDop.PROC;//иначеипродвигаем время на 5 квантов

nIndex=oDop.Index(countT-1);

oDop.aTask[nIndex].Trud-=oDop.PROC;// обнуляем трудоемкость

oDop.aTask[nIndex].Prior--;

for (int j=1,in=0;j<countT-1;j++)

{

in=oDop.Index(j);

if (!oDop.aTask[in].b)

{

//oDop.aTask[in].Function(cTr);

}

}

st.Format("%d: %d задача начала выполнение ",oDop.T,oDop.aTask[nIndex].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

for (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T+cTr)

{

if (oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)

{

st.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

}

}

st.Format("%d: у задачи %d закончился квант времени ",oDop.T+cTr,oDop.aTask[nIndex].Name);

OutFile2.Write(st,st.GetLength());

OutFile2.Write("\n",1);

m_TraceD.InsertString(-1,st);

GetStrPrior(oDop.cTask);

break;

}

}

else countT--; //следущая в списке

}

oDop.T+=cTr; //продвигаем модельное время

}

}

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