Задача: Алгоритмы планирования(диспетчеризации)

  • Автор темы ge4r
  • Дата начала
G

ge4r

#1
Добрый день,нужно накатать 2 таких алгоритма и вычислить параметры их работы сравнить их.
параметры - это различные величины,получаемые из общего времени нахождения процесса в системе(в коде gtime) и времени его непрерывной работы(в коде cburst);

вот FCFS попытался накатать,но он не хочет работать,видимо ошибка в методе fcfs




C++:
#include <iostream>
#include <stdlib.h>

using namespace std;
int n;
class process {
public:
int stime;
int burst;
int cburst;
int gtime;
int priority;
int completed;
int number;
float M;
float R;
float P;

process() {
this->burst=0;
this->stime=0;
this->priority=0;
}

~process() {};
};

void random (process procs[]){
for (int i=0;i<n;i++) {
procs[i].stime=rand() % 10;
procs[i].burst=rand() % 100 + 1;
procs[i].cburst=procs[i].burst;
procs[i].completed=0;
procs[i].number=i;
procs[i].priority=rand()%4 +1;
}
}

process* min_stime(process procs[]){
int min_time = INT_MAX;
process *min;
for (int i=0;i<n;i++){
if(procs[i].completed==0 && procs[i].stime<min_time){
min_time=procs[i].stime;
min=&procs[i];
}
}
return min;
}

void fcfs (process procs[]){
process *cur=min_stime(procs);
int tick=0;
while(cur!=NULL) {
if (cur->burst==0){
cur->completed=1;
}
if (cur->completed==1){
cur->gtime=tick-cur->stime;
cur=min_stime(procs);
if (cur==NULL) break;
}
if (tick>= cur->stime){
cur->burst--;
}
tick++;
}
}

void count (process procs[]){
for (int i=0;i<n;i++){
procs[i].M=procs[i].gtime-procs[i].cburst;
procs[i].R=procs[i].cburst/procs[i].gtime;
procs[i].P=1/procs[i].R;
}
}






int main(int argc, char *argv[])
{
cout<<"Input n: ";
cin>>n;
process procs[n];
random(procs);
fcfs(procs);
count (procs);
for (int i=0;i<n;i++){
printf("M= ",procs[i].M);
}



system("PAUSE");	 
return 0;
}
 

DarkKnight

Well-known member
01.08.2010
653
0
#2
Добрый день,нужно накатать 2 таких алгоритма и вычислить параметры их работы сравнить их.
параметры - это различные величины,получаемые из общего времени нахождения процесса в системе(в коде gtime) и времени его непрерывной работы(в коде cburst);

вот FCFS попытался накатать,но он не хочет работать,видимо ошибка в методе fcfs
А можно чуть-чуть определенее..
Например : использование, конечная цель, методическая документация...
Вообщем выкиньте все что есть... Завтра обязательно посмотрю алгоритмы...
 
G

ge4r

#3
Вот методичка.
конечная цель - наплодить процессов и прогнать их через 2 алгоритма,вычисляя параметры о которых писал. и далее сравнить эти параметры и их средние величины
 

Вложения

DarkKnight

Well-known member
01.08.2010
653
0
#4
Ок.... Методичка как раз то что нужно было...
Ну так что задача до завтра подождет?
 
G

ge4r

#5
вот чуть поправил код,вроде бы даже выводит значения,но какие то уж больно большие..хотя,если берст меняется от 1 до 101,может даже и ничего. но вот от запуса к запуску значения не меняются. такое ощущение что рандом дает одни и те же значения) вот ,нашел косяк,в методе fcfs у меня обрабатывался текущий элемент cur,потом брался другой,а предыдущий херился. сделал чтоб массив новых процессов метод возвращал,но значения после каждого запуска все равно одни и те же
Апдейт. почитал про rand(), понял что зря потратил час на дебаг кода) вроде бы работает,и выдает значения нужные. единственное смущает,что М первого процесса всегда = 0,даже если старттайм у него не 0.
C++:
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>


using namespace std;
class process {
public:
int stime;
int burst;
int cburst;
int gtime;
int priority;
int completed;
int number;
float M;
float R;
float P;

process() {
this->burst=0;
this->stime=0;
this->priority=0;
this->gtime=0;
this->M=0;
this->R=0;
this->P=0;
this->completed=0;
}

~process() {};
};

void random (process procs[],int n){
for (int i=0;i<n;i++) {
procs[i].stime=rand() % 10 +1;
procs[i].burst=rand() % 50 + 1;
procs[i].cburst=procs[i].burst;
procs[i].completed=0;
procs[i].number=i;
procs[i].priority=rand()%4 +1;
}
}

process* min_stime(int n,process procs[]){
int min_time = INT_MAX;
process *min=NULL;
for (int i=0;i<n;i++){
if(procs[i].completed==0 && procs[i].stime<min_time){
min_time=procs[i].stime;
min=&procs[i];
}
}
return min;
}

void fcfs (int n,process procs[],process proc[]){
process *cur=min_stime(n,procs);
int tick=0;
int m=0;
while(m!=n) {
if (cur->burst==0){
cur->completed=1;
}
if (cur->completed==1){
cur->gtime=tick-cur->stime;
proc[m]=*cur;
cur=min_stime(n,procs);
m++;
if (cur==NULL) break;
}
if (tick>= cur->stime){
cur->burst--;
}
tick++;
}
}

void count (process procs[],int n){
process *cur;
for (int i=0;i<n;i++){
cur=&procs[i];
cur->M=(float)cur->gtime-cur->cburst;
cur->R=(float)cur->cburst/cur->gtime;
cur->P=(float)cur->gtime/cur->cburst;
procs[i]=*cur;
//				procs[i].M=procs[i].gtime-procs[i].cburst;
//				procs[i].R=procs[i].cburst/procs[i].gtime;
//				procs[i].P=1/procs[i].R;
}
}






int main(int argc, char *argv[])
{	  
int n=0;
cout<<"Input n: ";
cin>>n;
process *procs=new process[n];
process *proc=new process[n];
//process procs[n];
//process proc[n];
random(procs,n);
fcfs(n,procs,proc);
count (proc,n);
for (int i=0;i<n;i++){
printf("Process %d params: M=%.1f; R=%.3f; P=%.3f \n ",proc[i].number,proc[i].M,proc[i].R,proc[i].P);
}



system("PAUSE");	
return 0;
}
 
G

ge4r

#6
блин,ни черта не могу въехать,что хотят в SRR. и гугл ничего не знает.DarkKnight125 , не смотрели еще методичку?
 

DarkKnight

Well-known member
01.08.2010
653
0
#7
блин,ни черта не могу въехать,что хотят в SRR. и гугл ничего не знает.DarkKnight125 , не смотрели еще методичку?
Пока нет ge4r, сегодня день что-то дурной выдался.... За комп только почти сел....
Через 8 часов гляну.... Вообщем проснешься завтра что-нить конструктивное найдешь ;-)
Не засоряй пока мозги ;-)
 
G

ge4r

#8
да ладно уж,пока есть время и силы - позасоряю) спасибо)
 

DarkKnight

Well-known member
01.08.2010
653
0
#9
2ge4r, Я очень извиняюсь.... Сегодня был ужастный день на работе в инете не был совсем, да и дорога домой заняла 3 часа (у нас город - катком стал ;-))... Еще раз сорь, посмотреть смогу только завтра, сейчас сил нету... только спать....
 
S

someone

#11
Добрый вечер, собственно тоже интересует подобная программа(только алгоритм FCFS) Только вот интересует как реализовать отображение в виде диаграммы ганта? и кстати у меня есть алгоритм SRR, если интересует, могу скинуть. И еще могли бы хоть чуть описать свою программу? ) А то я чет вообще не понимаю ((
 
G
#12
srr кидайте,поковыряю)

а по коду что именно не понятно?

описание класса понятно?

по самому методу - берем сначала процесс с минимальным временем запуска, далее смотрим сколько \квантов времени он находится в системе (tick). далее высчитываем время его работы в системе,и делаем поле completed =1 ,то бишь что он отработал и мы его не трогаем. далее берем следующий незвершенный с минимальным временем и проделываем аналогичные действия)
 
S

someone

#13
укр комментарии) кстати если не сложно, можете написать комментарии к вашей программе?
C++:
Main.cpp
// main.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Calc.h"

int _tmain(int argc, _TCHAR* argv[])
{
CCalc calc;
char s [100];
printf("\nEnter name of file: ");
scanf("%s",&s);
printf("\n");
if (calc.init(s))
printf("\nError open file\n")
else
calc.wiev();
return 0;
}

CCalc.h
#pragma once
#include <Process.h>

struct TProcess
{
int nom; // номер процесу
int inTime; // час його входу у чергу
int length; // процесорний час, необхідний процесу
int priority; // приоритет процесса
bool flagStep; // флаг, котрий показує, це новий (false), чи старий (true) процес
int done; // час, котрий процес вже виконувався
};


class CCalc
{
public:
CCalc(void);
public:
~CCalc(void);
public:
// ініціалізує чергу, у якості параметра - приймає вказівник на строку з ім'ям файлу
int init(char * nameFile);
// розпододіляє процесорний час поміж процесами та виводить діаграму
void wiev();

public:
TProcess * proc; // Список процесів
long length; // Довжина списку процесів
};
CCalc.cpp
#include "StdAfx.h"
#include "Calc.h"

#include "stdio.h"

#define STEP_FOR_OLD 1 // шаг нарощування пріорітету для старого процесу
#define STEP_FOR_NEW 2 // шаг нарощування пріорітету для нового процесу

CCalc::CCalc()
{
proc = NULL;
length = 0;
}
CCalc::~CCalc()
{
if(proc!=NULL)
delete [] proc;
}
int CCalc::init(char * nameFile)
{
FILE * f;
f = NULL;
f = fopen(nameFile,"r");
if(f == NULL)
return -1;
fscanf(f, "%i\n", &length );
//printf("l = %i\n",length);
proc = new TProcess [length];
for (int i=0; i<length; i++)
{
fscanf(f,"%i%i%i\n",&proc.nom, &proc.inTime, &proc.length);
proc.priority = 0;
proc.flagStep = false;
proc.done = 0;
}
fclose(f);
return 0;
}
void CCalc::wiev()
{
int i;
// вивід введених значень
printf("danni faylu\n");
for(i=0; i<length; i++)
{
printf("%i %i %i\n",proc.nom, proc.inTime, proc.length);
}
printf("\ndisgrama rozpodilu protsernogo chasu po algoritmu SRR\n\n");
// вивід номеру процесу
for(i=0; i<length; i++)
printf("%3i", i+1);
printf(" prioritet \n");

bool pr = true; // признак того, що у черзі лишились процеси
int * activ; // масив номерів активних процессів
activ = new int [length];
for(i=0; i<length; i++)
activ = -1;
int cursor = 0; // вказує на елемент масиву activ, де збеігається номер процесу, що виконується
int last = 0; // вказує на перший вільний елемент масиву activ
long minPriority = 0; // показує мінімальний пріорітет старих процесів
long time = 0; // показує поточний час
while(pr)
{
pr = false;
for (i=0; i<length; i++) // цикл, у якому перераховуються пріорітети, та процеси додаються до активних
{
if (proc.nom == -1) // якщо процес закінчив виконання
continue; // пропускаємо його
pr = true; // у черзі залишились процеси
if (proc.inTime > time) // якщо процес ще не виконується
continue; // пропускаємо його
if (!proc.flagStep) // якщо процес новий
{
if (proc.priority >= minPriority)// якщо пріорітет процесу >= мінімальному старих процесів
{
activ[last] = proc.nom; // він додається до масиву активних
last++;
proc.flagStep = true; // виставляється флаг шагу старого процесу
proc.priority+=STEP_FOR_OLD; // виконується шаг старого процесу
}
else // iнакше
{
proc.priority+=STEP_FOR_NEW; // виконується шаг нового процесу
}
}
else // якщо процес старий
{
proc.priority+=STEP_FOR_OLD; // виконується шаг для старого процесу
}
}



i=0;
minPriority=0; //обнуляємо мінімальний пріорітет старих процесів
while (i<length-1 && activ == -1) i++;
if (activ != -1) // якщо є активні процеси
{
do{
cursor = (cursor+1)%length;
}while(activ[cursor]==-1 ); // циклічно збільшуемо курсор, поки він не вкаже на наступний непорожній елемент

proc[activ[cursor]-1].done++; // збільшуєм показник часу, який процес вже виконувася

/* відображаємо діаграму*/
for(i=0; i<length; i++)
{
if (i+1 == activ[cursor])
printf(" O"); // процес виконується
else
{
if(proc.nom != -1 && proc.inTime <= time)
printf(" X"); // процес ще не з'явився, або виконався
else
printf(" ");// процес очікує
}
}
//--------- вивід пріорітету
for (i=0; i<length; i++)
printf("%3i", proc.priority);
//---------
printf("\n");

/* Видалення процесів, що повністью виконались */
for(i=0; i<length; i++)
{
if(activ==-1) continue;
if(proc[activ-1].done>=proc[activ-1].length) // якщо процес виконувався необхыдний час
{
proc[activ-1].nom = -1; // то, він видаляється з черги всіх процесів
activ = -1; // та з черги активних процесів
}
}

/* Знаходження мінімального пріорітету */
minPriority = 64000;
for (i=0; i<length; i++)
{
if(activ==-1) continue;
if (proc[activ-1].priority < minPriority)
minPriority=proc[activ-1].priority;
}
if(minPriority == 64000)
minPriority = 0;

}
else
{
printf("\n");
}
time++;
}
delete [] activ;
}
C++:
 

DarkKnight

Well-known member
01.08.2010
653
0
#14
Методичка - "атас", всегда поражало, как можно по таким пособиям людей учить....
ge4r, Щас ваш код подсмотрю....
 

DarkKnight

Well-known member
01.08.2010
653
0
#15
2ge4r: Тут объясни где я указал , а так же члены класса
C++:
#include <iostream>
#include <stdlib.h>


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() 
{
//Обнулим все
burst=0;
stime=0;
priority=0;
gtime=0;
M=0;
R=0;
P=0;
completed= false;
}
~process() {};
};

// Рандомная инициализация процессов 
void random (process procs[],int n)
{
for (int i=0; i<n; i++) 
{
procs[i].stime=rand() % 10 +1;
procs[i].burst=rand() % 50 + 1;
procs[i].cburst=procs[i].burst;
procs[i].completed=0;
procs[i].number=i;
procs[i].priority=rand()%4 +1;
}
}

//Вот эта функция мне совершено не понятна
process* min_stime(int n,process procs[])
{
int min_time = INT_MAX;
process *min=NULL;
for (int i=0;i<n;i++)
{
if(procs[i].completed==0 && procs[i].stime<min_time)
{
min_time=procs[i].stime;
min=&procs[i];
}
}
return min;
}

//Алгоритм fcfs
void fcfs (int n,process procs[],process proc[])
{
process *cur=min_stime(n,procs); //Получим что то
//но для fcfs нам же не нужно получать ничего, мы обслуживаем процессы от первого до последнее (в порядке их прибывания в очередь)
int tick=0; //Наверное это проц. такт.
int m=0; //Счетчик...
while(m!=n) //Пока не ошибли все процессы как я понимаю
{
if (cur->burst==0) //Если процесс не имеет больше тактов, то он считается пополненым
{
cur->completed=true; 
}
if (cur->completed==1) //Если процесс выполнен, то
{
//Все что ниже закомментируте пожалуйста... Не улавливаю сути алгоритма
cur->gtime=tick-cur->stime;
proc[m]=*cur;
cur=min_stime(n,procs);
m++;
if (cur==NULL) break;
}
if (tick>= cur->stime)
{
cur->burst--;
}
tick++;
}
}

void count (process procs[],int n)
{
process *cur;
for (int i=0;i<n;i++)
{
cur=&procs[i];
cur->M=(float)cur->gtime-cur->cburst;
cur->R=(float)cur->cburst/cur->gtime;
cur->P=(float)cur->gtime/cur->cburst;
procs[i]=*cur;
//				procs[i].M=procs[i].gtime-procs[i].cburst;
//				procs[i].R=procs[i].cburst/procs[i].gtime;
//				procs[i].P=1/procs[i].R;
}
}

//Главная форм программы (точка входа)
int main(int argc, char *argv[])
{	  
int n=0;
cout<<"Input n: ";
cin>>n;
process *procs=new process[n];
process *proc=new process[n];

random(procs,n);
fcfs(n,procs,proc);
count (proc,n);
for (int i=0;i<n;i++)
{
printf("Process %d params: M=%.1f; R=%.3f; P=%.3f \n ",proc[i].number,proc[i].M,proc[i].R,proc[i].P);
}

system("PAUSE");	
return 0;
}
 
G
#16
C++:
#include <iostream>
#include <stdlib.h>


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() 
{
//Обнулим все
burst=0;
stime=0;
priority=0;
gtime=0;
M=0;
R=0;
P=0;
completed= false;
}
~process() {};
};

// Рандомная инициализация процессов 
void random (process procs[],int n)
{
for (int i=0; i<n; i++) 
{
procs[i].stime=rand() % 10 +1;
procs[i].burst=rand() % 50 + 1;
procs[i].cburst=procs[i].burst;
procs[i].completed=0;
procs[i].number=i;
procs[i].priority=rand()%4 +1;
}
}

//Находим процесс,который раньше всех начинает работу и не завершен, и возвращаем его,ведь при рандоме не будут что для каждого i+1 время входа будет больше предыдущего
process* min_stime(int n,process procs[])
{
int min_time = INT_MAX;
process *min=NULL;
for (int i=0;i<n;i++)
{
if(procs[i].completed==0 && procs[i].stime<min_time)
{
min_time=procs[i].stime;
min=&procs[i];
}
}
return min;
}

//Алгоритм fcfs
void fcfs (int n,process procs[],process proc[])
{
process *cur=min_stime(n,procs); 
//тут как раз таки и получаем первый процесс,пришедший на обслуживание
int tick=0; //Наверное это проц. такт.
int m=0; //Счетчик...
while(m!=n) //выполняем цикл,пока не прошли все процессы
{
if (cur->burst==0) //Если процесс не имеет больше тактов, то он считается пополненым
{
cur->completed=true; 
}
if (cur->completed==1) //Если процесс выполнен, то
{

cur->gtime=tick-cur->stime;// вычисляем общее время нахождения в системе (то есть общее время работы системы - время входа в систему процесса)
proc[m]=*cur;// засовываем обработанный процесс в новый массив
cur=min_stime(n,procs);// берем следующий пришедший,незавершенный процесс
m++;//увеличиваем счетчик
if (cur==NULL) break;
}
if (tick>= cur->stime)
{
cur->burst--;
}
tick++;
}
}

void count (process procs[],int n)
{
process *cur;
for (int i=0;i<n;i++)
{
cur=&procs[i];
cur->M=(float)cur->gtime-cur->cburst;
cur->R=(float)cur->cburst/cur->gtime;
cur->P=(float)cur->gtime/cur->cburst;
procs[i]=*cur;
//				procs[i].M=procs[i].gtime-procs[i].cburst;
//				procs[i].R=procs[i].cburst/procs[i].gtime;
//				procs[i].P=1/procs[i].R;
}
}

//Главная форм программы (точка входа)
int main(int argc, char *argv[])
{	  
int n=0;
cout<<"Input n: ";
cin>>n;
process *procs=new process[n];
process *proc=new process[n];

random(procs,n);
fcfs(n,procs,proc);
count (proc,n);
for (int i=0;i<n;i++)
{
printf("Process %d params: M=%.1f; R=%.3f; P=%.3f \n ",proc[i].number,proc[i].M,proc[i].R,proc[i].P);
}

system("PAUSE");	
return 0;
}
 

DarkKnight

Well-known member
01.08.2010
653
0
#17
Ага... Понял уже ;-)) Там оказывается в методички из всего полезного что есть это описание задания ;-)
У тебя чуть подход не верен при написании тестового алгоритма... Щас переделываю.....
 

DarkKnight

Well-known member
01.08.2010
653
0
#18
Работа опять жжет... Уже стыдно ужастно...
Только домой приехал опять (день такой же ужастный как всегда), видно все же до НГ буду адекватно и быстро отвечать только по выходным...
Вот пока что только получилось накидать на работе...
C++:
#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;
}
};

//Структура очереди
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; //Присвоим хвосту адрес нов. элемента
}
}
};

//Алгоритм fcfs
//Входные данные Work - очередь процессов уже запущенных
//				 Complete - очередь процессов уже завершенных
//				 Feature - очередь процессов которые еще не запустились
void fcfs (QProcess Work, QProcess Complete, QProcess Feature)
{
/*На этапе разработки*/
}

//Главная форм программы (точка входа)
int main(int argc, char *argv[])
{	  
setlocale(LC_ALL,".1251"); //Подгрузка локали
srand(time(NULL)); //Инициализация генератора случ. величины

int n=0; //Кол-во процессов
cout<<"Введите кол-во процессов n = ";
cin>>n; //Ввод кол-ва

//Теперь перейдем к очередям
QProcess Work; //Очередь которая обрабатывает (процесс уже запущен)
QProcess NewProcess; //Очередь процессов время запуска которых еще не наступило 
QProcess Complate; //Очередь которая уже обработалась (конец - последний обработанный)

process InitRand; 

// Рандомная инициализация процессов 
for (int i = 0; i<n; i++)
{
InitRand.random(i+1); //Сама инициализация процесса рандомным методом
NewProcess.ArrProcess(InitRand); //Добавление в очередь (процессов время запуска которых еще не наступило)
}

/*
fcfs(n,procs,proc);
count (proc,n);
for (int i=0;i<n;i++)
{
printf("Process %d params: M=%.1f; R=%.3f; P=%.3f \n ",proc[i].number,proc[i].M,proc[i].R,proc[i].P);
}
*/				
system("PAUSE");	
return 0;
}
 

DarkKnight

Well-known member
01.08.2010
653
0
#19
Не знаю получить описать сегодня сами алгоритмы, но вот

C++:
/*
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 ShowStatProcess(void)
{
cout << "Процесс(ID:"<< number << ") gtime = " << gtime << "; cburst = "<< cburst<<" Коэф. M=" << M << ";R="<< R <<";P=" <<P << endl;
cout << "Процесс создан в " << stime <<" квант/такт от нач. исполнения программы"<< 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)
{
/*На этапе разработки*/
}

//Вот, на этом этапе весь интерфес для задания полностью разработан, остается только описать алгоритмы диспечерезации процессов

//Главная форм программы (точка входа)
int main(int argc, char *argv[])

{	  
setlocale(LC_ALL,".1251"); //Подгрузка локали
srand(time(NULL)); //Инициализация генератора случ. величины

int n=0; //Кол-во процессов
cout<<"Введите кол-во процессов n = ";
cin>>n; //Ввод кол-ва

//Теперь перейдем к очередям
QProcess Work; //Очередь которая обрабатывает (процесс уже запущен)
QProcess NewProcess; //Очередь процессов время запуска которых еще не наступило 
QProcess Complate; //Очередь которая уже обработалась (конец - последний обработанный)

process InitRand; 

// Рандомная инициализация процессов 
for (int i = 0; i<n; i++)
{
InitRand.random(i+1); //Сама инициализация процесса рандомным методом
NewProcess.ArrProcess(InitRand); //Добавление в очередь (процессов время запуска которых еще не наступило)
}


NewProcess.InvateTo(8,Work); //Тест функции InvateTo
NewProcess.InvateTo(2,Work); //Тест функции InvateTo
cout << "Очередь новых(Будущих) процессов :" << endl;
PrcQ *Temp = NewProcess.First;
while(Temp)
{
cout << Temp->data.number << endl;
Temp = Temp->Next;
}

cout << "Очередь Рабочих процессов :" << endl;
Temp = Work.First;
while(Temp)
{
cout << Temp->data.number << endl;
Temp = Temp->Next;
}

Work.InvateTo(2,Complate);
cout << "Очередь Завершенных процессов :" << endl;
Temp = Work.First;
while(Temp)
{
Temp->data.ShowStatProcess();
Temp = Temp->Next;
}
/*
fcfs(n,procs,proc);
count (proc,n);
for (int i=0;i<n;i++)
{
printf("Process %d params: M=%.1f; R=%.3f; P=%.3f \n ",proc[i].number,proc[i].M,proc[i].R,proc[i].P);
}
*/				
system("PAUSE");	
return 0;
}
 

DarkKnight

Well-known member
01.08.2010
653
0
#20
Вот, закомментировал вроде подробно....
Какие еще алгоритмы из методички нужны????
C++:
/*
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++; //Увеличим квант
}


}

//Вот, на этом этапе весь интерфес для задания полностью разработан, остается только описать алгоритмы диспечерезации процессов

//Главная форм программы (точка входа)
int main(int argc, char *argv[])

{	  
setlocale(LC_ALL,".1251"); //Подгрузка локали
srand(time(NULL)); //Инициализация генератора случ. величины

int n=0; //Кол-во процессов
cout<<"Введите кол-во процессов n = ";
cin>>n; //Ввод кол-ва

//Теперь перейдем к очередям
QProcess Work; //Очередь которая обрабатывает (процесс уже запущен)
QProcess NewProcess; //Очередь процессов время запуска которых еще не наступило 
QProcess Complete; //Очередь которая уже обработалась (конец - последний обработанный)

process InitRand; 

// Рандомная инициализация процессов 
for (int i = 0; i<n; i++)
{
InitRand.random(i+1); //Сама инициализация процесса рандомным методом
NewProcess.ArrProcess(InitRand); //Добавление в очередь (процессов время запуска которых еще не наступило)
}

PrcQ *Temp; //Указатель на структуру очереди
/*
cout << "Очередь новых(Будущих) процессов :" << endl;
Temp = NewProcess.First;
while(Temp)
{
cout << Temp->data.number << endl;
Temp = Temp->Next;
}


cout << "Очередь Рабочих процессов :" << endl;
Temp = Work.First;
while(Temp)
{
cout << Temp->data.number << endl;
Temp = Temp->Next;
}
*/
//Вывод очереди завершенных процессов
fcfs(Work,Complete,NewProcess);
cout << "Очередь Завершенных процессов :" << endl;
Temp = Complete.First;
while(Temp)
{
Temp->data.ShowStatProcess();
Temp = Temp->Next;
}

system("PAUSE");	
return 0;
}
 

Вложения