VPF::работа со Стеками и Очередями - Форум программистов

simple

Дата 25.10.2011, 16:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 25.10.2011

Репутация: нет
Всего: нет

Доброго времени суток! Есть такая задачка, над которой я уже очень долго бьюсь, плохо понимая как вообще можно это реализовать.
Вот суть:

Система состоит из процессора P, трёх очередей F0, F1, F2 и стека S. В систему поступают запросы на выполнение задач.

Задачи считывать из файла. В файле например может быть такая таблица:

имя задачи    длительность выполнения    момент поступления   приоритет

   qw                                   3                                       7                           0
   we                                   5                                       8                           2
   jh                                    15                                      10                         0

и тд...

Поступающие запросы ставятся в соответствующие приоритетам очере-ди. Сначала обрабатываются задачи из очереди F0. Если она пуста, можно обрабатывать задачи из очереди F1. Если и она пуста, то можно обрабаты-вать задачи из очереди F2. Если все очереди пусты, то система находится в ожидании поступающих задач (процессор свободен), либо в режиме обработ-ки предыдущей задачи (процессор занят). Если поступает задача с более вы-соким приоритетом, чем обрабатываемая в данный момент, то обрабатывае-мая помещается в стек и может обрабатываться тогда и только тогда, когда все задачи с более высоким приоритетом уже обработаны.

Вот мои наработки, но помоему полный бред:

Код


#include<fstream>
#include<string>
#include<clocale>
#include<iostream>
#include<stdio.h>
using namespace std;

struct Tasks{
    string name;
    string runtime;
    string arrival_time;
    string priority;
};


void file(istream& ifs)
{
    string buf,str;
    long j=0,count=0;
    // поиск количества строк в файле
    while(getline(ifs, str))
    {
            count++;
    }
    Tasks* task=new Tasks[j];
    // считываем в массив структур;
    while(ifs>>buf)
    {
        if (task[j].name=="")
        {
            task[j].name=buf; continue;
        }
        if (task[j].runtime=="")
        {
            task[j].runtime=buf; continue;
        }
        if (task[j].arrival_time=="")
        {
            task[j].arrival_time=buf; continue;
        }
        task[j].priority=buf;
        j++;//переход на след. задачу;
    }
}

// описание динамической структуры для реализации СТЕКА
struct Stack
{
    struct Stack *link;
    char info;
};
// описание глобальных переменных - указатели на верхушку СТЕКА
struct Stack *Top;
struct Stack *Top1;
// Заполнение Стека
void Func_Stack(Tasks *task; long j)
{ Top1 = NULL;
Top = NULL;

per:
{   struct Stack *p1;
    struct Stack *p;
    p1 = new struct Stack;
    p = new struct Stack;
    &p->task[j];
    p->link = Top;
    Top = p;
 p1->task[j]=p->task[j];
    p1->link = Top1;
    Top1 = p1;
    }
}


void Func0(Tasks *task, long j, int cnt0)
{
    struct F0 {
        Task 0info; 
        struct F0 *next;
    };

 typedef F0 *F0Ptr; // указатель на тип F0 
 F0Ptr head0 = NULL; 
 F0Ptr v0;// указатель на текущий элемент
 F0Ptr tail0; // указатель на "хвост" очереди 
 F0Ptr d0; // указатель на удаляемый элемент
 if (head0 == NULL) 
 { 
     head0 = new F0;
     head0->task[j];
     cnt0++;
     head0->next = NULL; 
     tail0 = head0;
 }
v0 = new F0;
v0->0info = task[j];
v0->next = tail0->next;
tail0 = v0;
cnt0++;
if ((CPU==true)||(process_priority>(head0->task[j].priority)))
{
    d0 = head0;
    head0 = head0->next;
    delete d0;
}

void Func1(Tasks *task, long j,int cnt0, int cnt1)
{
    struct F1 {
        Task info1; 
        struct F1 *next;
    };

 typedef F1 *F1Ptr; // указатель на тип F1 
 F1Ptr head1 = NULL; 
 F1Ptr v1; // указатель на текущий элемент 
 F1Ptr d1; // указатель на удаляемый элемент
 F1Ptr tail1; // указатель на "хвост" очереди 
 if (head1 == NULL) 
 { 
     head1 = new F1;
     head1->task[j];
     cnt1++;
     head1->next = NULL; 
     tail1 = head1;
 }
v1 = new F1;
v1->1info = task[j];
v1->next = tail1->next;
tail1 = v1;
cnt1++;
if (((CPU==true)&&(cnt0==0))||(process_priority>(head1->task[j].priority)))
{
    d1 = head1;
    head1 = head1->next;
    delete d1;
}
}

void Func2(Tasks *task, long j, int cnt0, int cnt1, int cnt2)
{
    struct F2 {
        Task task[j]; 
        struct F2 *next;
    };

 typedef F2 *F2Ptr; // указатель на тип F2 
 F2Ptr head = NULL; 
 F2Ptr v2; // указатель на текущий элемент 
 F2Ptr d2; // указатель на удаляемый элемент
 F2Ptr tail2; // указатель на "хвост" очереди 
 if (head2 == NULL) 
 { 
     head2 = new F2;
     head2->task[j];
     cnt2++;
     head2->next = NULL; 
     tail2 = head2;
 }
v2 = new F2;
v2->2info = task[j];
v2->next = tail2->next;
tail2 = v2;
cnt2++;
if (((CPU==true)&&(cnt0==0)&&(cnt1==0))||(process_priority>(head2->task[j].priority)))
{
    d1 = head2;
    head2 = head2->next;
    delete d2;
}
}


int main()
{
    setlocale(LC_ALL,"rus");
    ifstream ifs("wow.txt", ios:: in );
    if (!ifs)
    {
        cerr<<"Ошибка открытия файла"<<endl;
    return 1;
    }
    file(ifs);
    bool CPU;
    CPU=true;
    long timer;
    int cnt0=0, cnt1=0, cnt2=0;
    for (j=0;j<count;j++)
    {
    for (timer=0;timer<n;timer++)
    {
        if (task[j].arrival_time==timer)
        {
            switch (task[j].priority)
            {
            case '0': Func0(task,j,cnt0);
            case '1': Func1(task,j,cnt0,cnt1);
            case '2': Func2(task,j,cnt0,cnt1,cnt2);
            }

    return 0;
}

bsa

Дата 25.10.2011, 19:16 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

1. почему у тебя в структуре все поля строковые? Логично было оставить строковым только первое, а остальные - числовыми
2. Очереди удобнее поместить в массив. В итоге приоритет будет выступать индексом для выбора очереди
3. Почему у тебя везде используется слово "стек"? По идее, в данном случае более уместна очередь (queue), причем, с возможностью вставлять данные в ее начало

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

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

simple

Дата 26.10.2011, 21:02 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 25.10.2011

Репутация: нет
Всего: нет

1.Возникла проблема считывания из файла информации разного типа.
2. очередь и стек нужно реализовать динамически в виде списков.
3.да,вы правы, там нужно переименовать стек на очередь.

моя загвоздка заключается в том, что я не понимаю как реализовать в целом заданную систему, как соединить все части вместе. полная каша smile

sQu1rr

Дата 27.10.2011, 00:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

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

bsa

Дата 27.10.2011, 14:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Цитата(simple @ 26.10.2011, 22:02

)

Возникла проблема считывания из файла информации разного типа.

Если не секрет, какая проблема? cin >> s.run_time >> s.arrival_time >> s.priority;

Цитата(simple @ 26.10.2011, 22:02

)

2. очередь и стек нужно реализовать динамически в виде списков.

Я тебе про другое:

Код

for(int i = 0; i < 3; ++i) {
   if (!queue[i].empty()) {
        task = queue[i].front();
        queue[i].pop();
        break;
   }
}
//process task here

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »