Министерство образования и науки РФ
Новосибирский Государственный Технический Университет
Кафедра ВТ
Курсовая работа
по дисциплине «Операционные системы»
на тему:
«Планирование и диспетчеризация»
Выполнил: Трегубов :
Группа: АМ-509
Вариант 921
Новосибирск 2008
Содержание
1. Раздел 1. 3
1.1 Задание. 3
1.2 Теоретические основы планирования и диспетчеризации. 3
1.3 Исходные данные. 5
1.4 Временные диаграммы при использовании дисциплин FIFO и SJF. 5
1.5 Сравнительный анализ двух диаграмм.. 8
2. Раздел 2. 9
2.1 Задание. 9
2.2 Структурные схемы дисциплины обслуживания. 9
2.3 Программная реализация. 10
2.4 Временные диаграммы.. 23
3. Заключение. 26
4. Список литературы.. 27
2. Раздел 1
2.1 Задание
Необходимо построить временную диаграмму мультипрограммной работы при использовании двух дисциплин обслуживания FIFO и SJF и провести сравнение этих двух дисциплин для выявления лучшей из них для заданного входного набора данных
2.2 Теоретические основы планирования и диспетчеризации
Планирование распределения процессора производится на нескольких уровнях. Один из них - средний уровень планирования - диспетчеризация. На этом уровне диспетчер задач (планировщик процессов) выбирает одну задачу из числа готовых к выполнению и предоставляет ей процессор. Каждая задача занимает процессор относительно малое время (как правило, недостаточное для выполнения задачи), затем диспетчирование повторяется, процессор выделяется другой задаче. Диспетчер принимает текущие решения в динамике сложившейся конкретной обстановки.
Диспетчер – программа, которая выбирает задачи из “очереди на выполнение”, переводит их в активное состояние, и передаёт им контроль над центральным процессором.
Дисциплина обслуживания – это правила, в соответствии с которым из очереди выбирается соответствующее требование и предоставляется ресурс.
Требования к ДО:
1) ДО должны обеспечивать высокий показатель эффективности, при этом время ожидания должно быть равномерно
2) Необходимо, чтобы ДО была минимальна по трудоёмкости
Приоритет – это преимущественное право на первоочередное обслуживание.
Рис. 1. Классификация ДО
Бесприоритетные ДО: выбирают заявки без учёта их важности, а по принципу последовательности поступления.
Линейные ДО: характеризуются одинаковым средним временем ожидания независимо от длительности заявки.
Циклические ДО: Имеются циклические очереди к ресурсу, т. е. очереди использующие принцип квантования ∆t т. е выбранная заявка получает ограниченный квант времени ∆t. В результате этого она может обслуживаться только с учётом определённого требования, она может завершиться полностью, либо заявки не хватит времени ∆t. В случае нехватки времени ∆t обслуживание прерывается, заявка становится в конец очереди и выбирается следующая по порядку
Приоритетные ДО: выбирают заявки c учётом их важности.
1. Линейная дисциплина обслуживания FIFO (First In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь первой.
2. Линейная дисциплина обслуживания LIFO (Last In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь последней.
3. Линейная дисциплина обслуживания RAND (Randomize). Случайный выбор заявки из очереди.
4. Циклическая дисциплина обслуживания RR (Round Rotation). Отличается от FIFO лишь временем обслуживания. Каждая заявка получает определённый квант времени (одинаковый для всех) .
5. Дисциплина обслуживания с фиксированным приоритетом SJF (Short Job First). Из очереди заявок на обслуживание выбирается заявка с минимальным временем обслуживания.
6. Дисциплина обслуживания с фиксированным приоритетом PRT (PRioriTy). Из очереди заявок на обслуживание выбирается заявка с максимальным приоритетом.
Существует несколько оценок эффективности планирования. Одной из них является время обращения задания – время, прошедшее с момента поступления задания в систему до момента завершения его выполнения.
,
где t – время обращения задания; tЗ – время завершения задания; tП – время поступления задания.
Но эта оценка не является универсальной. Например, если сравнивать время обращения одночасового и одноминутного задания (при условии, что задания начнут выполняться сразу же, как только поступят в систему), то время обращения одночасового задания будет значительно больше, чем время обращения одноминутного. Но это совсем не значит, что одночасовое задание было обслужено плохо, т. к. время обращения задания не может быть меньше времени выполнения.
Более универсальной оценкой, позволяющей сравнивать между собой задания любой длины, является взвешенное время обращения
,
где W – взвешенное время обращения;
T – действительное время выполнения задания (трудоемкость).
Для случая M заданий можно провести оценку по среднему взвешенному времени обращения
,
где 
– средневзвешенное время обращения;
– взвешенное время обращения i-го задания;
M – количество заданий.
Планирование распределения процессора производится на нескольких уровнях. Один из них – диспетчеризация. На этом уровне диспетчер задач (планировщик процессов) выбирает одну задачу из числа готовых к выполнению и предоставляет ей процессор. Каждая задача занимает процессор относительно малое время (как правило, недостаточное для выполнения задачи), затем диспетчирование повторяется – процессор выделяется другой задаче. Диспетчер принимает текущие решения в динамике сложившейся конкретной обстановки.
Таким образом, цели диспетчирования задач следующие:
· распределение центрального процессора в динамике в соответствии с критериями;
· эффективная отработка алгоритмов управления задачами.
· сбалансированное использование ресурсов.
· баланс между временем ответа и коэффициентом использования ресурсов.
Итак: диспетчер – это программа, которая выбирает задачи (процессы) из «очереди на выполнение», переводит их в активное состояние и передает их на обработку центральному процессору.
2.3 Исходные данные
Вариант по первому разделу работы: 921
Таблица 1. Исходные данные
Номер задачи п/п | X | K | Используемая ОП v | Используемая внешняя память h | Трудоемкость T | Время поступления tp | Время загрузки tз |
0 | 864 | 3 | 4 | 1 | 10 | 3 | 5 |
1 | 465 | 6 | 7 | 4 | 20 | 9 | 20 |
2 | 672 | 6 | 7 | 4 | 20 | 15 | 20 |
3 | 121 | 7 | 9 | 1 | 30 | 22 | 5 |
4 | 264 | 7 | 9 | 1 | 30 | 29 | 5 |
5 | 265 | 7 | 9 | 1 | 30 | 36 | 5 |
6 | 272 | 8 | 4 | 6 | 40 | 44 | 30 |
7 | 321 | 5 | 5 | 0 | 30 | 49 | 0 |
8 | 664 | 4 | 3 | 2 | 60 | 53 | 10 |
9 | 65 | 9 | 1 | 3 | 50 | 62 | 15 |
Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) ti=ki.
2.4 Временные диаграммы при использовании дисциплин FIFO и SJF
Изобразим временные диаграммы планирования для обеих дисциплин обслуживания на рис. 1 и рис. 2., а затем посчитаем средневзвешенное время и приведем сравнительную характеристику обеих дисциплин при заданных условиях.
Посчитаем средневзвешенное время для обеих дисциплин:
i | WiFIFO | WiSJF |
0 | 1 | 1 |
1 | 1,28 | 1 |
2 | 1,5 | 1,05 |
3 | 2,26 | 4,36 |
4 | 3,06 | 8,14 |
5 | 3,97 | 8,94 |
6 | 3,7 | 1,1 |
7 | 7,87 | 1,15 |
8 | 4,31 | 1,12 |
9 | 4,38 | 1,08 |
Wср. FIFO = 3,33
Wср.SJF = 2,89
2.5 Сравнительный анализ двух диаграмм
Из общего для двух дисциплин следует отметить, что и для дисциплины FIFO, и для SJF максимальный коэффициент мультипрограммирования достиг 4. Длительность выполнения всех задач оказалось приблизительно одинаковая. Также у обеих дисциплин наблюдаются незначительные простои процессора в ожидании задач для выполнения.
Дисциплина обслуживания SJF обладает меньшим значением средневзвешенного времени обращения (Wср.SJF = 2,89) по сравнению с FIFO (Wср. FIFO = 3,33). Это объясняется тем, что заданий с малой трудоёмкостью в системе больше, чем продолжительных, поэтому их быстрая обработка позволяет улучшить производительность системы. Следовательно, для такой исходной последовательности заданий выгоднее использовать дисциплину обслуживания SJF.
3. Раздел 2
3.1 Задание
Разработать структуру функционирования диспетчера работ в вычислительной системе, заданной в разделе 1. и реализовать ее программно.
Вариант 6.
Диспетчер использует метод разделения времени в сочетании с приоритетами. Используемый дисциплины обслуживания: бесприоритетная – FB(обратная связь), приоритетная – с относительным приоритетом.
Выполнение приоритетной заявки не прерываются при поступлении более приоритетной. На рисунке 11 представлена схема алгоритма обслуживания (относительный приоритет).
3.2 Структурные схемы дисциплины обслуживания
Дисциплина обслуживания с относительными приоритетами:
Рис. 3. Схема алгоритма обслуживания с относительным приоритетом
Дисциплина обслуживания с обратной связью (Feed Back):
Рис. 4. Схема алгоритма обслуживания с обратной связью (FB)
3.3 Программная реализация
· Дисциплина FB (Обратная связь)
#include <iostream>
#include <windows. h>
using namespace std;
void RusText(char *c) //Фунция вывода на экран
{ //русского текста
char tmp[80];
CharToOemA(c, tmp); //из библиотеки windows. h
cout<<tmp;
}
class Task
{
public:
int v;
int h;
int cpu;
int t_post;
int t_real;
int Flag_End;
Task() //Конструктор по умолчанию
{
v=0;
h=0;
cpu=0;
t_post=0;
t_real=0;
Flag_End=0;
}
Task(int nv, int nh, int ncpu, int nt_post) //Конструктор с параметрами
{
v=nv;
h=nh;
cpu=ncpu;
t_post=nt_post;
t_real=0;
Flag_End=0;
}
};
void main()
{
Task Z[10]; //Очередь работ
Z[0]=Task(4,1,10,3); //Заполнение исходными данными
Z[1]=Task(7,4,20,9);
Z[2]=Task(7,4,20,15);
Z[3]=Task(9,1,30,22);
Z[4]=Task(9,1,30,29);
Z[5]=Task(9,1,30,36);
Z[6]=Task(4,6,40,44);
Z[7]=Task(5,0,30,49);
Z[8]=Task(3,2,60,53);
Z[9]=Task(1,3,50,62);
int Q_Load[10]; //Очередь на загрузку
for(int i=0; i<10; i++)
Q_Load[i]=-1;
int Q_Proc[10][10]; //Очередь на процессоре
for(int i=0; i<10; i++)
for(int j=0; j<10; j++)
Q_Proc[i][j]=-8;
int Time=0; // реал тайм
int Kvant_D=5; // квант диспетчеру
int Kvant_W=10; // квант работе
int V=16;
int H=12;
int p=0;
int Do=0;
int pointer=0;
int Iteration=0;
int Cnt_UnDone=10; //Количество неотработанных задач
int i, j;
RusText("\n Дисциплина бесприортитная - FB (Обратная Связь) \n");
RusText("\n.\n Начало трассировки |\n'\n\n");
for(Iteration=0;Cnt_UnDone>0;Iteration++) //Пока не все работы выполнились
{
RusText("** Итерация "); cout<<Iteration<<" **"<<endl;
RusText("Время = "); cout<<Time<<endl;
RusText("Количество свободных ресурсов: ");
cout<<"V="<<V<<" H="<<H<<endl;
RusText("На процессоре: \n");
RusText("Очереди: ");
for(i=0; i<6; i++)
{
cout<<"["<<i<<"] ";
for(j=0; j<10; j++)
if (Q_Proc[i][j]!=-8) cout<<Q_Proc[i][j]<<" ";
cout<<"\t";
}
cout<<endl;
RusText("Время обработки задач: ");
for(i=0; i<10; i++)
if (Z[i].t_real==-1) cout<<"X ";
else cout<<Z[i].t_real<<" ";
cout<<endl;
RusText("СОБЫТИЯ: \n");
for(i=0; i<10; i++) //Просмотр очереди на процессоре
for(j=0; j<10; j++) //Просмотр очереди на процессоре
{
if(Q_Proc[i][j]!=-8 && Z[Q_Proc[i][j]].t_real>=Z[Q_Proc[i][j]].cpu && Z[Q_Proc[i][j]].Flag_End!=1)
{
H+=Z[Q_Proc[i][j]].h;
V+=Z[Q_Proc[i][j]].v;
Z[Q_Proc[i][j]].Flag_End=1;
RusText("\tЗавершилась задача "); cout<<Q_Proc[i][j];
RusText(" ( освободила ресурсы: ");
cout<<"v="<<Z[Q_Proc[i][j]].v<<" h="<<Z[Q_Proc[i][j]].h<<" )"<<endl;
Cnt_UnDone--;
Z[Q_Proc[i][j]].t_real=-1;
if(Q_Proc[i][j+1]!=-8)
{
for(int k=j; k<9; k++)
Q_Proc[i][k]=Q_Proc[i][k+1];
Q_Proc[i][j]=-8;
}
else
{
Q_Proc[i][j]=-8;
}
}
}
for(i=0; i<=9; i++) // Просмотреть задачи на необходимость загрузки
{
if(Time>=Z[i].t_post && Z[i].Flag_End!=1 && Q_Load[i]==-1)
{
if(Z[i].h<=H && Z[i].v<=V)
{
H=H-Z[i].h;
V=V-Z[i].v;
Q_Load[i]=Time;
RusText("\tПоступила на загрузку задача "); cout<<i;
RusText(" ( заняла ресурсы: ");
cout<<"v="<<Z[i].v<<" h="<<Z[i].h<<" )"<<endl;
}
}
}
// Просмотр очереди загрузки
for(i=0; i<10; i++)
{
if(Q_Load[i]>0)
{
if(Time-Q_Load[i]>=Z[i].h*5)
{
Do=1;
Q_Load[i]=-2;
for (int k=0; k<9; k++)
if (Q_Proc[0][k]==-8)
{ Q_Proc[0][k]=i; break; }
RusText("\tЗавершена загрузка задачи "); cout<<i<<endl;
}
}
}
Time+=Kvant_D;
if(Do!=0)
{
for (int n=0; n<10; n++)
{
if (Q_Proc[n][0]!=-8)
{
Z[Q_Proc[n][0]].t_real+=Kvant_W;
for (int m=0; m<10; m++)
{
if (Q_Proc[n+1][m]==-8) { Q_Proc[n+1][m]=Q_Proc[n][0]; break; }
}
for(int k=0; k<9; k++)
Q_Proc[n][k]=Q_Proc[n][k+1];
break;
}
}
Time+=Kvant_W;
}
}
RusText("\n-.\n Трассировка завершена |\n-'\n");
}
· Дисциплина c относительным приоритетом
#include <iostream>
#include <windows. h>
using namespace std;
void RusText(char *c) //Фунция вывода на экран
{ //русского текста
char tmp[80];
CharToOemA(c, tmp); //из библиотеки windows. h
cout<<tmp;
}
class Task
{
public:
int v;
int h;
int cpu;
int t_post;
int pr;
int t_real;
int Flag_End;
Task() //Конструктор по умолчанию
{
v=0;
h=0;
cpu=0;
t_post=0;
pr=0;
t_real=0;
Flag_End=0;
}
Task(int nv, int nh, int ncpu, int nt_post, int npr) //Конструктор с параметрами
{
v=nv;
h=nh;
cpu=ncpu;
t_post=nt_post;
pr=npr;
t_real=0;
Flag_End=0;
}
};
void main()
{
Task Z[10]; //Очередь работ
Z[0]=Task(4,1,10,3,5); //Заполнение исходными данными
Z[1]=Task(7,4,20,9,37);
Z[2]=Task(7,4,20,15,2);
Z[3]=Task(9,1,30,22,7);
Z[4]=Task(9,1,30,29,11);
Z[5]=Task(9,1,30,36,4);
Z[6]=Task(4,6,40,44,9);
Z[7]=Task(5,0,30,49,3);
Z[8]=Task(3,2,60,53,1);
Z[9]=Task(1,3,50,62,12);
int Q_Load[10]; //Очередь на загрузку
for(int i=0; i<10; i++)
Q_Load[i]=-1;
int Q_Proc[10]; //Очередь на процессоре
for(int i=0; i<10; i++)
Q_Proc[i]=0;
int Time=0; // реал тайм
int Kvant_D=5; // квант диспетчеру
int Kvant_W=10; // квант работе
int Doing=-1;
int V=16;
int H=12;
int p=0;
int Do=0;
int pointer=0;
int Iteration=0;
int Cnt_UnDone=10; //Количество неотработанных задач
int i, j;
RusText("\n Дисциплина Приоритетная - Относительный приоритет \n");
RusText("\n.\n Начало трассировки |\n'\n");
for(Iteration=0;Cnt_UnDone>0;Iteration++) //Пока не все работы выполнились
{
RusText("\n** Итерация "); cout<<Iteration<<" **"<<endl;
RusText("Время = "); cout<<Time<<endl;
RusText("Количество свободных ресурсов: ");
cout<<"V="<<V<<" H="<<H<<endl;
RusText("На процессоре: ");
for(i=0; i<10; i++)
if (Q_Proc[i]!=0) cout<<Q_Proc[i]<<" ";
cout<<endl;
RusText("Время обработки задач: ");
for(i=0; i<10; i++)
if (Z[i].t_real==-1) cout<<"X ";
else cout<<Z[i].t_real<<" ";
cout<<endl;
RusText("СОБЫТИЯ: \n");
for(j=0; j<p; j++) //Просмотр очереди на процессоре
{
if(Z[Q_Proc[j]].t_real>=Z[Q_Proc[j]].cpu && Z[Q_Proc[j]].Flag_End!=1)
{
H+=Z[Q_Proc[j]].h;
V+=Z[Q_Proc[j]].v;
Z[Q_Proc[j]].Flag_End=1;
RusText("\tЗавершилась задача "); cout<<Q_Proc[j];
RusText(" ( освободила ресурсы: ");
cout<<"v="<<Z[Q_Proc[j]].v<<" h="<<Z[Q_Proc[j]].h<<" )"<<endl;
Doing=-1;
Cnt_UnDone--;
Z[Q_Proc[j]].t_real=-1;
if(j+1!=p)
{
for(int k=j; k<p; k++)
Q_Proc[k]=Q_Proc[k+1];
Q_Proc[p]=0;
p--;
}
else
{
Q_Proc[p-1]=0;
p--;
}
}
}
for(i=0; i<=9; i++) // Просмотреть задачи на необходимость загрузки
{
if(Time>=Z[i].t_post && Z[i].Flag_End!=1 && Q_Load[i]==-1)
{
if(Z[i].h<=H && Z[i].v<=V)
{
H=H-Z[i].h;
V=V-Z[i].v;
Q_Load[i]=Time;
RusText("\tПоступила на загрузку задача "); cout<<i;
RusText(" ( заняла ресурсы: ");
cout<<"v="<<Z[i].v<<" h="<<Z[i].h<<" )"<<endl;
}
}
}
// Просмотр очереди на загрузку
for(i=0; i<10; i++)
{
if(Q_Load[i]>0)
{
if(Time-Q_Load[i]>=Z[i].h*5)
{
Do=1;
Q_Load[i]=-2;
Q_Proc[p]=i;
RusText("\tЗавершена загрузка задачи "); cout<<i<<endl;
p++;
}
}
}
Time+=Kvant_D;
if(Do!=0)
{
if (p!=0)
{
if (Doing!=-1)
{
Z[Doing].t_real+=Kvant_W;
Time+=Kvant_W;
}
else
{
pointer=p-1;
int max=0;
int max_i=-1;
for (int i=0; i<p; i++)
{
if (Iteration==17)
int a=5;
if (Z[Q_Proc[i]].pr>max)
{
max=Z[Q_Proc[i]].pr;
max_i=i;
}
}
Doing=Q_Proc[max_i];
Z[Q_Proc[max_i]].t_real+=Kvant_W;
Time+=Kvant_W;
}
}
}
}
RusText("\n-.\n Трассировка завершена |\n-'\n");
}
· Трассировка FB
Дисциплина бесприоритетная - FB (Обратная Связь)
----.
Начало трассировки |
----'
** Итерация 0 **
Время = 0
Количество свободных ресурсов: V=16 H=12
На процессоре:
Очереди: [0] [1] [2] [3] [4] [5]
Время обработки задач: 0 0
СОБЫТИЯ:
** Итерация 1 **
Время = 5
Количество свободных ресурсов: V=16 H=12
На процессоре:
Очереди: [0] [1] [2] [3] [4] [5]
Время обработки задач: 0 0
СОБЫТИЯ:
Поступила на загрузку задача 0 ( заняла ресурсы: v=4 h=1 )
** Итерация 2 **
Время = 10
Количество свободных ресурсов: V=12 H=11
На процессоре:
Очереди: [0] [1] [2] [3] [4] [5]
Время обработки задач: 0 0
СОБЫТИЯ:
Поступила на загрузку задача 1 ( заняла ресурсы: v=7 h=4 )
Завершена загрузка задачи 0
** Итерация 3 **
Время = 25
Количество свободных ресурсов: V=5 H=7
На процессоре:
Очереди: [0] [1] 0 [2] [3] [4] [5]
Время обработки задач:0 0 0
СОБЫТИЯ:
Завершилась задача 0 ( освободила ресурсы: v=4 h=1 )
Поступила на загрузку задача 2 ( заняла ресурсы: v=7 h=4 )
** Итерация 4 **
Время = 40
Количество свободных ресурсов: V=2 H=4
На процессоре:
Очереди: [0] [1] [2] [3] [4] [5]
Время обработки задач: X 0
СОБЫТИЯ:
Завершена загрузка задачи 1
** Итерация 5 **
Время = 55
Количество свободных ресурсов: V=2 H=4
На процессоре:
Очереди: [0] [1] 1 [2] [3] [4] [5]
Время обработки задач: X0 0
СОБЫТИЯ:
Завершена загрузка задачи 2
** Итерация 6 **
Время = 70
Количество свободных ресурсов: V=2 H=4
На процессоре:
Очереди: [0] [1] 1 2 [2] [3] [4] [5]
Время обработки задач: X 0 0
СОБЫТИЯ:
Поступила на загрузку задача 9 ( заняла ресурсы: v=1 h=3 )
** Итерация 7 **
Время = 85
Количество свободных ресурсов: V=1 H=1
На процессоре:
Очереди: [0] [1] 2 [2] 1 [3] [4] [5]
Время обработки задач: X 0 0
СОБЫТИЯ:
Завершилась задача 1 ( освободила ресурсы: v=7 h=4 )
Поступила на загрузку задача 7 ( заняла ресурсы: v=5 h=0 )
Поступила на загрузку задача 8 ( заняла ресурсы: v=3 h=2 )
Завершена загрузка задачи 7
Завершена загрузка задачи 9
** Итерация 8 **
Время = 100
Количество свободных ресурсов: V=0 H=3
На процессоре:
Очереди: [0] 9 [1] 2 7 [2] [3] [4] [5]
Время обработки задач: X X 0
СОБЫТИЯ:
Завершена загрузка задачи 8
** Итерация 9 **
Время = 115
Количество свободных ресурсов: V=0 H=3
На процессоре:
Очереди: [0] 8 [1] 2 7 9 [2] [3] [4] [5]
Время обработки задач: X X 10
СОБЫТИЯ:
** Итерация 10 **
Время = 130
Количество свободных ресурсов: V=0 H=3
На процессоре:
Очереди: [0] [1] [2] [3] [4] [5]
Время обработки задач: X X0 10
СОБЫТИЯ:
** Итерация 11 **
Время = 145
Количество свободных ресурсов: V=0 H=3
На процессоре:
Очереди: [0] [1] 7 9 8 [2] 2 [3] [4] [5]
Время обработки задач: X X0 10
СОБЫТИЯ:
Завершилась задача 2 ( освободила ресурсы: v=7 h=4 )
Поступила на загрузку задача 6 ( заняла ресурсы: v=4 h=6 )
** Итерация 12 **
Время = 160
Количество свободных ресурсов: V=3 H=1
На процессоре:
Очереди: [0] [1] 9 8 [2] 7 [3] [4] [5]
Время обработки задач: X X X
СОБЫТИЯ:
** Итерация 13 **
Время = 175
Количество свободных ресурсов: V=3 H=1
На процессоре:
Очереди: [0] [1] 8 [2] 7 9 [3] [4] [5]
Время обработки задач: X X X
СОБЫТИЯ:
Завершена загрузка задачи 6
** Итерация 14 **
Время = 190
Количество свободных ресурсов: V=3 H=1
На процессоре:
Очереди: [0] [1] 8 6 [2] 7 9 [3] [4] [5]
Время обработки задач: X X X 0
СОБЫТИЯ:
** Итерация 15 **
Время = 205
Количество свободных ресурсов: V=3 H=1
На процессоре:
Очереди: [0] [1] 6 [2] 7 9 8 [3] [4] [5]
Время обработки задач: X X X 0
СОБЫТИЯ:
** Итерация 16 **
Время = 220
Количество свободных ресурсов: V=3 H=1
На процессоре:
Очереди: [0] [1] [2] [3] [4] [5]
Время обработки задач: X X X 0
СОБЫТИЯ:
** Итерация 17 **
Время = 235
Количество свободных ресурсов: V=3 H=1
На процессоре:
Очереди: [0] [1] [2] 9 8 6 [3] 7 [4] [5]
Время обработки задач: X X X 0
СОБЫТИЯ:
Завершилась задача 7 ( освободила ресурсы: v=5 h=0 )
** Итерация 18 **
Время = 250
Количество свободных ресурсов: V=8 H=1
На процессоре:
Очереди: [0] [1] [2] 8 6 [3] 9 [4] [5]
Время обработки задач: X X X X 20 30
СОБЫТИЯ:
** Итерация 19 **
Время = 265
Количество свободных ресурсов: V=8 H=1
На процессоре:
Очереди: [0] [1] [2] 6 [3] 9 8 [4] [5]
Время обработки задач: X X X X 30 30
СОБЫТИЯ:
** Итерация 20 **
Время = 280
Количество свободных ресурсов: V=8 H=1
На процессоре:
Очереди: [0] [1] [2] [3] 9 8 6 [4] [5]
Время обработки задач: X X X X 30 30
СОБЫТИЯ:
** Итерация 21 **
Время = 295
Количество свободных ресурсов: V=8 H=1
На процессоре:
Очереди: [0] [1] [2] [3] 8 6 [4] 9 [5]
Время обработки задач: X X X X 30 40
СОБЫТИЯ:
** Итерация 22 **
Время = 310
Количество свободных ресурсов: V=8 H=1
На процессоре:
Очереди: [0] [1] [2] [3] 6 [4] 9 8 [5]
Время обработки задач: X X X X 40 40
СОБЫТИЯ:
** Итерация 23 **
Время = 325
Количество свободных ресурсов: V=8 H=1
На процессоре:
Очереди: [0] [1] [2] [3] [4] 9 8 6 [5]
Время обработки задач: X X X X 40 40
СОБЫТИЯ:
Завершилась задача 6 ( освободила ресурсы: v=4 h=6 )
Поступила на загрузку задача 3 ( заняла ресурсы: v=9 h=1 )
** Итерация 24 **
Время = 340
Количество свободных ресурсов: V=3 H=6
На процессоре:
Очереди: [0] [1] [2] [3] [4] 8 [5] 9
Время обработки задач: X X X 0 0 0 X X 40 50
СОБЫТИЯ:
Завершилась задача 9 ( освободила ресурсы: v=1 h=3 )
Завершена загрузка задачи 3
** Итерация 25 **
Время = 355
Количество свободных ресурсов: V=4 H=9
На процессоре:
Очереди: [0] [1] 3 [2] [3] [4] 8 [5]
Время обработки задач: X X XX X 40 X
СОБЫТИЯ:
** Итерация 26 **
Время = 370
Количество свободных ресурсов: V=4 H=9
На процессоре:
Очереди: [0] [1] [2] 3 [3] [4] 8 [5]
Время обработки задач: X X XX X 40 X
СОБЫТИЯ:
** Итерация 27 **
Время = 385
Количество свободных ресурсов: V=4 H=9
На процессоре:
Очереди: [0] [1] [2] [3] 3 [4] 8 [5]
Время обработки задач: X X XX X 40 X
СОБЫТИЯ:
Завершилась задача 3 ( освободила ресурсы: v=9 h=1 )
Поступила на загрузку задача 4 ( заняла ресурсы: v=9 h=1 )
** Итерация 28 **
Время = 400
Количество свободных ресурсов: V=4 H=9
На процессоре:
Очереди: [0] [1] [2] [3] [4] [5] 8
Время обработки задач: X X X X 0 0 X X 50 X
СОБЫТИЯ:
Завершена загрузка задачи 4
** Итерация 29 **
Время = 415
Количество свободных ресурсов: V=4 H=9
На процессоре:
Очереди: [0] [1] 4 [2] [3] [4] [5] 8
Время обработки задач: X X X X 10 0 X X 50 X
СОБЫТИЯ:
** Итерация 30 **
Время = 430
Количество свободных ресурсов: V=4 H=9
На процессоре:
Очереди: [0] [1] [2] 4 [3] [4] [5] 8
Время обработки задач: X X X X 20 0 X X 50 X
СОБЫТИЯ:
** Итерация 31 **
Время = 445
Количество свободных ресурсов: V=4 H=9
На процессоре:
Очереди: [0] [1] [2] [3] 4 [4] [5] 8
Время обработки задач: X X X X 30 0 X X 50 X
СОБЫТИЯ:
Завершилась задача 4 ( освободила ресурсы: v=9 h=1 )
Поступила на загрузку задача 5 ( заняла ресурсы: v=9 h=1 )
** Итерация 32 **
Время = 460
Количество свободных ресурсов: V=4 H=9
На процессоре:
Очереди: [0] [1] [2] [3] [4] [5]
Время обработки задач: X X X X X 0 X X 60 X
СОБЫТИЯ:
Завершилась задача 8 ( освободила ресурсы: v=3 h=2 )
Завершена загрузка задачи 5
** Итерация 33 **
Время = 475
Количество свободных ресурсов: V=7 H=11
На процессоре:
Очереди: [0] [1] 5 [2] [3] [4] [5]
Время обработки задач: X X X X X 10 X X X X
СОБЫТИЯ:
** Итерация 34 **
Время = 490
Количество свободных ресурсов: V=7 H=11
На процессоре:
Очереди: [0] [1] [2] 5 [3] [4] [5]
Время обработки задач: X X X X X 20 X X X X
СОБЫТИЯ:
** Итерация 35 **
Время = 505
Количество свободных ресурсов: V=7 H=11
На процессоре:
Очереди: [0] [1] [2] [3] 5 [4] [5]
Время обработки задач: X X X X X 30 X X X X
СОБЫТИЯ:
Завершилась задача 5 ( освободила ресурсы: v=9 h=1 )
.
Трассировка завершена |
'
· Трассировка OP
Дисциплина Приоритетная - Относительный приоритет
---.
Начало трассировки |
---'
** Итерация 0 **
Время = 0
Количество свободных ресурсов: V=16 H=12
На процессоре:
Время обработки задач: 0 0
СОБЫТИЯ:
** Итерация 1 **
Время = 5
Количество свободных ресурсов: V=16 H=12
На процессоре:
Время обработки задач: 0 0
СОБЫТИЯ:
Поступила на загрузку задача 0 ( заняла ресурсы: v=4 h=1 )
** Итерация 2 **
Время = 10
Количество свободных ресурсов: V=12 H=11
На процессоре:
Время обработки задач: 0 0
СОБЫТИЯ:
Поступила на загрузку задача 1 ( заняла ресурсы: v=7 h=4 )
Завершена загрузка задачи 0
** Итерация 3 **
Время = 25
Количество свободных ресурсов: V=5 H=7
На процессоре:
Время обработки задач:0 0 0
СОБЫТИЯ:
Завершилась задача 0 ( освободила ресурсы: v=4 h=1 )
Поступила на загрузку задача 2 ( заняла ресурсы: v=7 h=4 )
** Итерация 4 **
Время = 30
Количество свободных ресурсов: V=2 H=4
На процессоре:
Время обработки задач: X 0
СОБЫТИЯ:
Завершена загрузка задачи 1
** Итерация 5 **
Время = 45
Количество свободных ресурсов: V=2 H=4
На процессоре: 1
Время обработки задач: X0 0
СОБЫТИЯ:
Завершена загрузка задачи 2
** Итерация 6 **
Время = 60
Количество свободных ресурсов: V=2 H=4
На процессоре: 1 2
Время обработки задач: X0 0
СОБЫТИЯ:
Завершилась задача 1 ( освободила ресурсы: v=7 h=4 )
Поступила на загрузку задача 3 ( заняла ресурсы: v=9 h=1 )
** Итерация 7 **
Время = 75
Количество свободных ресурсов: V=0 H=7
На процессоре: 2
Время обработки задач: X X0
СОБЫТИЯ:
Завершена загрузка задачи 3
** Итерация 8 **
Время = 90
Количество свободных ресурсов: V=0 H=7
На процессоре: 2 3
Время обработки задач: X X0
СОБЫТИЯ:
Завершилась задача 2 ( освободила ресурсы: v=7 h=4 )
Поступила на загрузку задача 6 ( заняла ресурсы: v=4 h=6 )
Поступила на загрузку задача 8 ( заняла ресурсы: v=3 h=2 )
** Итерация 9 **
Время = 105
Количество свободных ресурсов: V=0 H=3
На процессоре: 3
Время обработки задач: X X X
СОБЫТИЯ:
Завершена загрузка задачи 8
** Итерация 10 **
Время = 120
Количество свободных ресурсов: V=0 H=3
На процессоре: 3 8
Время обработки задач: X X X
СОБЫТИЯ:
Завершена загрузка задачи 6
** Итерация 11 **
Время = 135
Количество свободных ресурсов: V=0 H=3
На процессоре: 3 8 6
Время обработки задач: X X X
СОБЫТИЯ:
Завершилась задача 3 ( освободила ресурсы: v=9 h=1 )
Поступила на загрузку задача 4 ( заняла ресурсы: v=9 h=1 )
** Итерация 12 **
Время = 150
Количество свободных ресурсов: V=0 H=3
На процессоре: 8 6
Время обработки задач: X X X X
СОБЫТИЯ:
Завершена загрузка задачи 4
** Итерация 13 **
Время = 165
Количество свободных ресурсов: V=0 H=3
На процессоре: 8 6 4
Время обработки задач: X X X X
СОБЫТИЯ:
** Итерация 14 **
Время = 180
Количество свободных ресурсов: V=0 H=3
На процессоре: 8 6 4
Время обработки задач: X X X X
СОБЫТИЯ:
** Итерация 15 **
Время = 195
Количество свободных ресурсов: V=0 H=3
На процессоре: 8 6 4
Время обработки задач: X X X X
СОБЫТИЯ:
Завершилась задача 6 ( освободила ресурсы: v=4 h=6 )
Поступила на загрузку задача 9 ( заняла ресурсы: v=1 h=3 )
** Итерация 16 **
Время = 210
Количество свободных ресурсов: V=3 H=6
На процессоре: 8 4
Время обработки задач: X X X X 10 0 X 0 0 0
СОБЫТИЯ:
Завершена загрузка задачи 9
** Итерация 17 **
Время = 225
Количество свободных ресурсов: V=3 H=6
На процессоре: 8 4 9
Время обработки задач: X X X X 20 0 X 0 0 0
СОБЫТИЯ:
** Итерация 18 **
Время = 240
Количество свободных ресурсов: V=3 H=6
На процессоре: 8 4 9
Время обработки задач: X X X X 30 0 X 0 0 0
СОБЫТИЯ:
Завершилась задача 4 ( освободила ресурсы: v=9 h=1 )
Поступила на загрузку задача 5 ( заняла ресурсы: v=9 h=1 )
** Итерация 19 **
Время = 255
Количество свободных ресурсов: V=3 H=6
На процессоре: 8 9
Время обработки задач: X X X X X 0 X 0 0 10
СОБЫТИЯ:
Завершена загрузка задачи 5
** Итерация 20 **
Время = 270
Количество свободных ресурсов: V=3 H=6
На процессоре: 8 9 5
Время обработки задач: X X X X X 0 X 0 0 20
СОБЫТИЯ:
** Итерация 21 **
Время = 285
Количество свободных ресурсов: V=3 H=6
На процессоре: 8 9 5
Время обработки задач: X X X X X 0 X 0 0 30
СОБЫТИЯ:
** Итерация 22 **
Время = 300
Количество свободных ресурсов: V=3 H=6
На процессоре: 8 9 5
Время обработки задач: X X X X X 0 X 0 0 40
СОБЫТИЯ:
** Итерация 23 **
Время = 315
Количество свободных ресурсов: V=3 H=6
На процессоре: 8 9 5
Время обработки задач: X X X X X 0 X 0 0 50
СОБЫТИЯ:
Завершилась задача 9 ( освободила ресурсы: v=1 h=3 )
** Итерация 24 **
Время = 330
Количество свободных ресурсов: V=4 H=9
На процессоре: 8 5
Время обработки задач: X X X X X 10 X 0 0 X
СОБЫТИЯ:
** Итерация 25 **
Время = 345
Количество свободных ресурсов: V=4 H=9
На процессоре: 8 5
Время обработки задач: X X X X X 20 X 0 0 X
СОБЫТИЯ:
** Итерация 26 **
Время = 360
Количество свободных ресурсов: V=4 H=9
На процессоре: 8 5
Время обработки задач: X X X X X 30 X 0 0 X
СОБЫТИЯ:
Завершилась задача 5 ( освободила ресурсы: v=9 h=1 )
Поступила на загрузку задача 7 ( заняла ресурсы: v=5 h=0 )
Завершена загрузка задачи 7
** Итерация 27 **
Время = 375
Количество свободных ресурсов: V=8 H=10
На процессоре: 8 7
Время обработки задач: X X X X X X X 10 0 X
СОБЫТИЯ:
** Итерация 28 **
Время = 390
Количество свободных ресурсов: V=8 H=10
На процессоре: 8 7
Время обработки задач: X X X X X X X 20 0 X
СОБЫТИЯ:
** Итерация 29 **
Время = 405
Количество свободных ресурсов: V=8 H=10
На процессоре: 8 7
Время обработки задач: X X X X X X X 30 0 X
СОБЫТИЯ:
Завершилась задача 7 ( освободила ресурсы: v=5 h=0 )
** Итерация 30 **
Время = 420
Количество свободных ресурсов: V=13 H=10
На процессоре: 8
Время обработки задач: X X X X X X X X 10 X
СОБЫТИЯ:
** Итерация 31 **
Время = 435
Количество свободных ресурсов: V=13 H=10
На процессоре: 8
Время обработки задач: X X X X X X X X 20 X
СОБЫТИЯ:
** Итерация 32 **
Время = 450
Количество свободных ресурсов: V=13 H=10
На процессоре: 8
Время обработки задач: X X X X X X X X 30 X
СОБЫТИЯ:
** Итерация 33 **
Время = 465
Количество свободных ресурсов: V=13 H=10
На процессоре: 8
Время обработки задач: X X X X X X X X 40 X
СОБЫТИЯ:
** Итерация 34 **
Время = 480
Количество свободных ресурсов: V=13 H=10
На процессоре: 8
Время обработки задач: X X X X X X X X 50 X
СОБЫТИЯ:
** Итерация 35 **
Время = 495
Количество свободных ресурсов: V=13 H=10
На процессоре: 8
Время обработки задач: X X X X X X X X 60 X
СОБЫТИЯ:
Завершилась задача 8 ( освободила ресурсы: v=3 h=2 )
-------.
Трассировка завершена |
-------'
3.4 Временные диаграммы
По трассировке, полученной с помощью созданных программ, изобразим временные диаграммы диспетчеризации для обеих дисциплин обслуживания
4. Заключение.
В ходе данной работы мне удалось углубить знания по данной дисциплине в области планирования и диспетчеризации процессов, построение временных диаграмм планирования для двух дисциплин от руки позволило лучше понять принцип организации планирования на верхнем уровне и выяснить, какая дисциплина из двух является лучшей на заданном входном наборе и почему.
Наиболее сложной частью в работе для меня оказался раздел диспетчеризации, и, в основном, создание программы, позволяющей моделировать процесс диспетчеризации, используя те же входные данные, что и в разделе 1, так как процесс перехода от алгоритма к программной реализации поддается без ошибок не сразу.
5. Список литературы
1. , . Системное программное обеспечение - Спб.: Питер, 20с. илл.
2. Коршикова практикум по дисциплине "Операционные системы": Методическое пособие. – Новосибирск: http://ermak. cs. *****/~mos/index. htm.
3. Коршикова указания к курсовой работе по дисциплине" Системное программное обеспечение"
