1. Наш канал codeby в telegram. Пишем об информационной безопасности, методах защиты информации, о программировании. Не пропускай новости с кодебай, будь в тренде ! Подробнее ...

    Скрыть объявление

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

Тема в разделе "Вопросы новичков и не только", создана пользователем ge4r, 11 дек 2010.

  1. ge4r

    ge4r Гость

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

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




    Код:
    #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;
    }
     
  2. DarkKnight

    DarkKnight Well-Known Member

    Репутация:
    0
    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    А можно чуть-чуть определенее..
    Например : использование, конечная цель, методическая документация...
    Вообщем выкиньте все что есть... Завтра обязательно посмотрю алгоритмы...
     
  3. ge4r

    ge4r Гость

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

    Вложения:

  4. DarkKnight

    DarkKnight Well-Known Member

    Репутация:
    0
    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Ок.... Методичка как раз то что нужно было...
    Ну так что задача до завтра подождет?
     
  5. ge4r

    ge4r Гость

    Репутация:
    0
    вот чуть поправил код,вроде бы даже выводит значения,но какие то уж больно большие..хотя,если берст меняется от 1 до 101,может даже и ничего. но вот от запуса к запуску значения не меняются. такое ощущение что рандом дает одни и те же значения) вот ,нашел косяк,в методе fcfs у меня обрабатывался текущий элемент cur,потом брался другой,а предыдущий херился. сделал чтоб массив новых процессов метод возвращал,но значения после каждого запуска все равно одни и те же
    Апдейт. почитал про rand(), понял что зря потратил час на дебаг кода) вроде бы работает,и выдает значения нужные. единственное смущает,что М первого процесса всегда = 0,даже если старттайм у него не 0.
    Код:
    #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;
    }
     
  6. ge4r

    ge4r Гость

    Репутация:
    0
    блин,ни черта не могу въехать,что хотят в SRR. и гугл ничего не знает.DarkKnight125 , не смотрели еще методичку?
     
  7. DarkKnight

    DarkKnight Well-Known Member

    Репутация:
    0
    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Пока нет ge4r, сегодня день что-то дурной выдался.... За комп только почти сел....
    Через 8 часов гляну.... Вообщем проснешься завтра что-нить конструктивное найдешь ;-)
    Не засоряй пока мозги ;-)
     
  8. ge4r

    ge4r Гость

    Репутация:
    0
    да ладно уж,пока есть время и силы - позасоряю) спасибо)
     
  9. DarkKnight

    DarkKnight Well-Known Member

    Репутация:
    0
    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    2ge4r, Я очень извиняюсь.... Сегодня был ужастный день на работе в инете не был совсем, да и дорога домой заняла 3 часа (у нас город - катком стал ;-))... Еще раз сорь, посмотреть смогу только завтра, сейчас сил нету... только спать....
     
  10. ge4r

    ge4r Гость

    Репутация:
    0
    хорошо)
     
  11. someone

    someone Гость

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

    ge4r Гость

    Репутация:
    0
    srr кидайте,поковыряю)

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

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

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

    someone Гость

    Репутация:
    0
    укр комментарии) кстати если не сложно, можете написать комментарии к вашей программе?
    Код:
    
    
    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[i] != -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[i].nom != -1 && proc[i].inTime <= time)
    printf(" X"); // процес ще не з'явився, або виконався
    else
    printf(" ");// процес очікує
    }
    }
    //--------- вивід пріорітету
    for (i=0; i<length; i++)
    printf("%3i", proc[i].priority);
    //---------
    printf("\n");

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

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

    }
    else
    {
    printf("\n");
    }
    time++;
    }
    delete [] activ;
    }
    [code=cpp][/CODE][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
     
  14. DarkKnight

    DarkKnight Well-Known Member

    Репутация:
    0
    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Методичка - "атас", всегда поражало, как можно по таким пособиям людей учить....
    ge4r, Щас ваш код подсмотрю....
     
  15. DarkKnight

    DarkKnight Well-Known Member

    Репутация:
    0
    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    2ge4r: Тут объясни где я указал , а так же члены класса
    Код:
    #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;
    }
     
  16. ge4r

    ge4r Гость

    Репутация:
    0
    Код:
    #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;
    }
     
  17. DarkKnight

    DarkKnight Well-Known Member

    Репутация:
    0
    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Ага... Понял уже ;-)) Там оказывается в методички из всего полезного что есть это описание задания ;-)
    У тебя чуть подход не верен при написании тестового алгоритма... Щас переделываю.....
     
  18. DarkKnight

    DarkKnight Well-Known Member

    Репутация:
    0
    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Работа опять жжет... Уже стыдно ужастно...
    Только домой приехал опять (день такой же ужастный как всегда), видно все же до НГ буду адекватно и быстро отвечать только по выходным...
    Вот пока что только получилось накидать на работе...
    Код:
    #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;
    }
     
  19. DarkKnight

    DarkKnight Well-Known Member

    Репутация:
    0
    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Не знаю получить описать сегодня сами алгоритмы, но вот

    Код:
    /*
    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;
    }
     
  20. DarkKnight

    DarkKnight Well-Known Member

    Репутация:
    0
    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Вот, закомментировал вроде подробно....
    Какие еще алгоритмы из методички нужны????
    Код:
    /*
    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;
    }
     

    Вложения:

    • Задача: Алгоритмы планирования(диспетчеризации)
      fcfs.jpg
      Размер файла:
      117,7 КБ
      Просмотров:
      44
Загрузка...
Похожие Темы - Задача Алгоритмы планирования(диспетчеризации)
  1. petiablack
    Ответов:
    0
    Просмотров:
    94
  2. disub
    Ответов:
    1
    Просмотров:
    203
  3. Kazua
    Ответов:
    1
    Просмотров:
    222
  4. Rina
    Ответов:
    0
    Просмотров:
    161
  5. School_Information
    Ответов:
    2
    Просмотров:
    283

Поделиться этой страницей