/*
codeby.net
Autor: DarkKnight125 (Denis Goncharov)
*/
#include <iostream>
#include <time.h>
using namespace std;
using namespace std;
//Класс процесс
class process {
public:
int stime; //Время вхождение процесса в систему
int burst; // А это как я понимаю, за сколько процессортных циклов выполниться процесс (итераций-тактов до завершения)
int cburst; // Время в работе
int gtime; //Общее время нахождения процесса в системе
int priority; //Приоритет
bool completed; //Флаг выполнения (сделаем bool)
int number; //Наверное номер процесса, *пока не знаю точно*
float M;
float R;
float P;
//Конструктор по умолчанию
process()
{
//Обнулим все
stime = 0;
burst=0;
cburst = 0;
gtime=0;
priority=0;
completed= false;
M=0;
R=0;
P=0;
}
~process() {};
void random(int Number)
{
stime= rand() % 100 +1;
burst= rand() % 50 + 1;
cburst=0;
completed=0;
number= Number;
priority=rand()%4 +1;
}
//Подсчет статистических данных *после завершения процесса*
void InitStatictic(void)
{
M = gtime - cburst; //Потери времени
R = (double) cburst/gtime; //Реактив.
P = (double) gtime/cburst; //Штраф
}
//Статистика процесса (для завершенных процессов)
void ShowStatProcess(void)
{
cout << "Процесс(ID:"<< number << ") gtime = " << gtime << "; cburst = "<< cburst<<" Коэф. M=" << M << ";R="<< R <<";P=" <<P << endl;
cout << "Процесс создан в " << stime <<" квант/такт от нач. исполнения программы"<< endl << endl;
}
};
//Структура очереди
struct PrcQ
{
process data; //Информация по процессу
PrcQ *Next; //Указатель на след. процесс очереди
};
//Конечно проще и адекватнее использовать двунаправленный список, но все же у нас процессы, и поэтому мы ограничимся обычной очередью,
//Пусть и алгоритм удаления из середины и конца будет немного громозким, зато для отценки любого из алгоритмов методички, этот подход самый наилучший
//Класс очередь процессов
class QProcess
{
public:
PrcQ Elt; //Элемент очереди
PrcQ *First; //Указатель на первый элемент очереди
PrcQ *Curr; //Текущий (хвост очереди) элемент очереди
//Конструктор класса очереди поумолчанию
QProcess()
{
First = NULL; //Выставим указатели начала и хвоста в нуль (пустая очередь)
Curr = NULL;
}
//Функция добавления элемента в очередь
void ArrProcess(process pr)
{
PrcQ *Temp = new PrcQ; //Выделим память под элемент очереди
Temp ->data = pr; //Запишим в нее инфу по процессу
Temp ->Next = NULL; //Указатель на след. элемент выставим в NULL (т.к. добавляем только в конец очереди)
if (!First) //Если указатель на начало NULL, то очередь пустая
{
First = Curr = Temp; //Присвоим ук. на начало, хвосту, текущий доб. элемент
}
else //Если же очередь не пуста
{
Curr->Next = Temp; //Указатель на след. элемент выставим в наш новый элемент
Curr = Temp; //Присвоим хвосту адрес нов. элемента
}
}
//Функция исключения (переноса) процесса в другую очередь)
//Входные данные Number - номер (ID) процесса
// toQProcess - ссылка на очередь к которую процесс переместить
// Результат true - если процесс найден и перемещен, false - если процесса с такии ID нет
bool InvateTo(int Number, QProcess &toQProcess)
{
PrcQ *Temp = First; //Заведем временную переменую в которую поставим начало очереди - которая вызывает функцию (из которой процесс изымается)
PrcQ *LastTemp = NULL; //Указатель на предыдущий элемент
PrcQ *MustDel = NULL; //Элемент очереди который будет удален (т.к. мы выделяем память в функции AddProcess)
bool Search = false; // Поставим флаг поиска в false
//Если удаляемый первый элемент если id процесса = Number
if (Temp->data.number == Number) //Если первый в очереди процесс равен Number
{
MustDel = Temp; //Выставим указатель удаления на память этого элемента
First = Temp->Next; //Первому элементу очереди присвоим процесс следующего
Search = true; //Флаг поиска установим в true
}
else //Инача (т.е. удаляемый (переносимый) процесс не первый, то
{
while (Temp->Next) //Циклим до тех пор, пока укатель Temp->Next не укажет на NULL (иными словами до последнего элемента, не включая его)
{
//Если в цикле был найден элемент с нужным номером (Id)
if (Temp->Next->data.number == Number)
{
//То инициализируем его удаление
MustDel = Temp->Next;
Temp->Next = Temp->Next->Next;
Search = true;
break;
}
LastTemp = Temp; //Сюда пишим текущий (после итерации он предыдущий)элемент (он нам понадобиться для проверки, если процесс переноса - последний)
Temp = Temp->Next; //Перейдем к след. элементу
}
//Проверим не является ли удал. процесс последним
if (Temp->data.number == Number)
{
MustDel =Temp;
Curr = LastTemp;
Curr->Next = NULL;
}
}
//Если есть что удалять (перемещать)
if (MustDel)
{
toQProcess.ArrProcess(MustDel->data); //Добавим в очередь(в которую переправляем) процесс
delete MustDel; //Почистим память выделеную для процесса
}
return Search; //Вернем результат
}
};
//Алгоритм fcfs
//Входные данные Work - очередь процессов уже запущенных
// Complete - очередь процессов уже завершенных
// Feature - очередь процессов которые еще не запустились
void fcfs (QProcess &Work, QProcess &Complete, QProcess &Feature)
{
//Итак начнем... Алгоритм fcfc
unsigned int Tick = 0; //Кванты процессорного времени (так называемы тики) //Для начала обнулим
PrcQ *Temp;
//Пока есть хоть один процесс в работе или в будущих процессах то выводняем
while (Work.First || Feature.First)
{
//Если время наступило, то перенесем процессы их Feature в Work
PrcQ *TempFeature = Feature.First; //Установим указатель на Feature.First
while (TempFeature) //Пока указатель не NULL выполняем поиск процессов которые должны запустить на этом такте (обходим очередб)
{
//Если время запуска процесса соответствует такту
if (TempFeature->data.stime == Tick)
{
Temp = TempFeature->Next; //То запомним указатель на след. элемент
Feature.InvateTo(TempFeature->data.number,Work); //Перенесем из Feature в Рабочую (Work) очередь
TempFeature = Temp; //Перейдем к след. элементу в очереди
}
else
TempFeature = TempFeature->Next; //Если ничего не найдено, то просто перейдем к след. элементу очереди
}
//Ну вот, с процессами которые должны войти все.. Перейдем теперь к рабочим
//По алгоритму FCFS (Первый вошел - он и выполняете) мы не отпустим процесс пока не завершим его
PrcQ *TempWork = Work.First; //Поэтому Получим первый процесс в очереди Work
//И будем выполнять его на этом такте если конечно процесс в рабочей очереди вообще есть
if (TempWork)
{
TempWork->data.burst--; //Уменьшим такты до завершения
TempWork->data.cburst++; //Увеличим время работы процесса
}
//На этом такте с процессом все.. Теперь в рабочих процесса увеличим время их нахождения в системе и если он завершился то перенесем его в
//очередь завершенных
TempWork = Work.First; //Поставим указатель на первый элемент очереди (рабочей)
while (TempWork)
{
TempWork->data.gtime++; //Увеличим время нахождения процесса в системе
if(TempWork->data.burst == 0) //Процесс завершился
{
TempWork->data.InitStatictic(); //Расчет статистики по процессу
Temp = TempWork->Next;
Work.InvateTo(TempWork->data.number,Complete);
TempWork = Temp;
}
else
TempWork = TempWork->Next;
}
Tick++; //Увеличим квант
}
}
//Алгоритм SRR (selfish RR – эгоистичный RR)
//Входные данные Work - очередь процессов уже запущенных
// Complete - очередь процессов уже завершенных
// Feature - очередь процессов которые еще не запустились
void srr (QProcess &Work, QProcess &Complete, QProcess &Feature)
{
const int dA = 3; //Приращение для новых процессов
const int dB = 1; //Приращение для выбранных процессор
//Итак начнем... Алгоритм SRR
unsigned int Tick = 0; //Кванты процессорного времени (так называемы тики) //Для начала обнулим
PrcQ *Temp;
//Пока есть хоть один процесс в работе или в будущих процессах то выполняем
while (Work.First || Feature.First)
{
//Если время наступило, то перенесем процессы их Feature в Work
PrcQ *TempFeature = Feature.First; //Установим указатель на Feature.First
while (TempFeature) //Пока указатель не NULL выполняем поиск процессов которые должны запустить на этом такте (обходим очередь)
{
//Если время запуска процесса соответствует такту
if (TempFeature->data.stime == Tick)
{
Temp = TempFeature->Next; //То запомним указатель на след. элемент
Feature.InvateTo(TempFeature->data.number,Work); //Перенесем из Feature в Рабочую (Work) очередь
TempFeature = Temp; //Перейдем к след. элементу в очереди
}
else
TempFeature = TempFeature->Next; //Если ничего не найдено, то просто перейдем к след. элементу очереди
}
//Теперь сама суть SRR, Нам нужно выстроить рабочую очередь по убыванию приоритетов
QProcess WorkNew; // Новая очередь
PrcQ *TempWork = Work.First; //Поэтому Получим первый процесс в очереди Work
while (TempWork) //Теперь будем обходить рабочую очередь пока в ней не останется ни одного элемента (все они должны перейти в нов. раб. очередь)
{
PrcQ *TempWork2 = Work.First; //Еще один указатель на первый эл. Work (для влож. цикла), мы же ищим макс. приоритеты
PrcQ *Replace = NULL; //Какой эл. очереди будем вытеснять
int MaxPrioritet = -1; //Максимальное значение приоритета (выставим его в минимум = -1)
while(TempWork2) //Пока не обошли всю очередь
{
if (TempWork2->data.priority > MaxPrioritet) //Если приоритет процесса > MaxPrioritet, то
{
Replace = TempWork2; //Запомним указатель на элемент
MaxPrioritet = TempWork2->data.priority; //Перезапишим макс. значение приоритета
}
TempWork2 = TempWork2->Next; //Перейдем к след. элементу
}
Work.InvateTo(Replace->data.number,WorkNew);//Запишим в новую очередь WorkNew процесс с макс приоритетом
TempWork = Work.First; //Поэтому Получим первый процесс в очереди Work и продолжным искать макс. приоритет из оставщихся элементов
}
Work = WorkNew; //Заменим очереди
//По алгоритму SRR выполним первый процесс на 1 такт и перещитаем приоритеты
TempWork = Work.First; //Поэтому Получим первый процесс в очереди Work
if (TempWork)
{
TempWork->data.burst--; //Уменьшим такты до завершения
TempWork->data.cburst++; //Увеличим время работы процесса
}
//На этом такте с процессом все.. Теперь в рабочих процесса увеличим время их нахождения в системе и если он завершился то перенесем его в
//очередь завершенных
TempWork = Work.First; //Поставим указатель на первый элемент очереди (рабочей)
while (TempWork)
{
TempWork->data.gtime++; //Увеличим время нахождения процесса в системе
//Вот тут будем пересчитывать приоритеты
if (TempWork->data.cburst == 0) //Если управление вообще не было еще переданно процессу
TempWork->data.priority += dA; //То увеличим на dA = 3
else TempWork->data.priority += dB; //Иначе (процесс уже хоть раз но выполнялся) на dB = 1;
if(TempWork->data.burst == 0) //Процесс завершился
{
TempWork->data.InitStatictic(); //Расчет статистики по процессу
Temp = TempWork->Next;
Work.InvateTo(TempWork->data.number,Complete);
TempWork = Temp;
}
else
TempWork = TempWork->Next;
}
Tick++; //Увеличим квант
}
}
//Вот, на этом этапе весь интерфес для задания полностью разработан, остается только описать алгоритмы диспечерезации процессов
//Главная форм программы (точка входа)
int main(int argc, char *argv[])
{
setlocale(LC_ALL,".1251"); //Подгрузка локали
srand(time(NULL)); //Инициализация генератора случ. величины
int n=0; //Кол-во процессов
cout<<"Введите кол-во процессов n = ";
cin>>n; //Ввод кол-ва
//Теперь перейдем к очередям
QProcess Work; //Очередь которая обрабатывает (процесс уже запущен) FCFS
QProcess NewProcess; //Очередь процессов время запуска которых еще не наступило FCFS
QProcess Complete; //Очередь которая уже обработалась (конец - последний обработанный) FCFS
// и тоже для SRR
QProcess WorkSRR; //Очередь которая обрабатывает (процесс уже запущен) SRR
QProcess NewProcessSRR; //Очередь процессов время запуска которых еще не наступило SRR
QProcess CompleteSRR; //Очередь которая уже обработалась (конец - последний обработанный) SRR
process InitRand;
// Рандомная инициализация процессов
for (int i = 0; i<n; i++)
{
InitRand.random(i+1); //Сама инициализация процесса рандомным методом
NewProcess.ArrProcess(InitRand); //Добавление в очередь (процессов время запуска которых еще не наступило) FCFS
InitRand.priority = 1; //изменим приоритет для SRR (там первоначально все приоритеты равны)
NewProcessSRR.ArrProcess(InitRand); //Добавление в очередь (процессов время запуска которых еще не наступило) SRR
}
PrcQ *Temp; //Указатель на структуру очереди
//Вывод очереди завершенных процессов FCFS
fcfs(Work,Complete,NewProcess);
cout << "Очередь Завершенных процессов FCFS:" << endl;
Temp = Complete.First;
while(Temp)
{
Temp->data.ShowStatProcess();
Temp = Temp->Next;
}
cout << "----------------------------------------------------" << endl;
//Вывод очереди завершенных процессов SRR
srr(WorkSRR,CompleteSRR,NewProcessSRR);
cout << "Очередь Завершенных процессов SRR:" << endl;
Temp = CompleteSRR.First;
while(Temp)
{
Temp->data.ShowStatProcess();
Temp = Temp->Next;
}
system("PAUSE");
return 0;
}
