[ChiQQn]

#programowanie #cplusplus

Hejka mirki, mam na algorytmach zaimplementować harmonogram procesora, z sortowaniem procesów według priorytetów. Wyczytałem, że najlepszym sposobem żeby to osiągnąć jest zbudowanie wielopoziomowej kolejki ze sprzężeniem zwrotnym. Problemem jest to, że nie mogę zmieniać nagłówków, które dostaliśmy ani korzystać z STL. Mam kilka pytań odnośnie tego zadania.

1. Czy istnieje szansa w sposób który nie ignoruje tego co już tam jest, zaimplementowania wielopoziomowej kolejki? (widzę to tak że schduler jest kolejką kilku kolejek, ale jako że węzły mają wartości takie jak ID czy value, nie mam pomysłu jak to napisać)

2. Prosiłbym o naprowadzenie na to jak wykonać jakieś wydajne sortowanie po priorytecie. Może quick sort? Czy wymagane jest robienie sortowania na tymczasowej kolejce, czy jest możliwość posortowania wewnątrz starej?

3. Dlaczego waszym zdaniem funkcja nodeDequeue jest wirtualna? W jaki sposób sugerowalibyście jej użycie

Przepraszam za zajmowanie waszego czasu, ale wszystkie zasoby na które trafiłem odnoszą się do STL. Wołam @kuhwa bo też ci się to pewnie przyda xD. Kod poniżej

#include
using namespace std;

class Node
{
public:

Node(int value, Node* nextptr = nullptr, Node* prevptr = nullptr, int currentpriority = 0)
{
this->value=value;
next = nextptr;
prev = prevptr;
priority = currentpriority;

}

int getVal(void)
{
return value;
}

Node* getNext(void)
{
return next;
}

Node* getPrev(void)
{
return prev;
}

void setVal(int value)
{
this->value = value;
}

void setPrev(Node* prevptr)
{prev = prevptr; };

void setNext(Node* nextptr)
{
next = nextptr;
}

int getPriority(void)
{
return priority;
}

void setPriority(int priority)
{
this->priority = priority;
}

private:
Node* next;
Node* prev;
int priority;
int value;
};

class Stack
{
public:
Stack(void)
{
top = nullptr;
}

~Stack(void)
{
while (NodePop() != nullptr);
}

void Push(int value)
{
Node* tmp = new Node(value,top);
top = tmp;
}

Node* NodePop(void)
{
Node* tmp = top;
if (top != nullptr) top = top->getNext();
return tmp;
}

int Pop(void)
{
Node* tmp = NodePop();
int ret = 0;
if (tmp != nullptr)
{
ret = tmp->getVal();
}

else
{
throw "Stack Empty";
}
delete tmp;
return ret;
}

private:

Node* top;
};

class Queue
{
public:
Queue(void)
{
back = front = nullptr;
}

~Queue(void)
{
while (NodeDequeue() != nullptr);
}

void Enqueue(int i, int priority = 0)
{
Node* tmp = new Node(i, back, nullptr, priority);
back = tmp;
if (front == nullptr) front = back;
else
{
tmp = back->getNext();
tmp->setPrev(back);
}
}

int Dequeue(void)
{
Node* tmp = NodeDequeue();
int ret = 0;
if (tmp != nullptr)
{
ret = tmp->getVal();
}
else
{
throw "Queue Empty";
}
if (front == nullptr) back = front; // queue now empty
delete tmp;
return ret;
}

protected:

Node* back;
Node* front;

private:

virtual Node* NodeDequeue(void)
{
Node* tmp = front;
if (front != nullptr)
{
front = front->getPrev();
if (front != nullptr) front->setNext(nullptr);
}
return tmp;
}
};

class Scheduler : public Queue
{

public:

private:

Node* NodeDequeue(void);

};

[wytrzzeszcz]

@ChiQQn: pastebin ?

[wytrzzeszcz]

@ChiQQn: do procesów proponuje poprostu tablice kolejek ale co ja tam wiem

[ChiQQn]

@wytrzzeszcz: http://pastebin.com/LAwKNUbK

to jest projekt na zaliczenie. Musimy używać nagłówków które dostaliśmy i dostosować kod do wymogów.

[ChiQQn]

@kuhar: @wytrzzeszcz: prosze, czytajcie zanim odpowiecie. One mają być tak jak są i nie moge tego zmienić. Muszę pracować na strukturach które dostałem

[wytrzzeszcz]

@ChiQQn: (⌐ ͡■ ͜ʖ ͡■) a przeraszam

[nadmuchane_jaja]

@ChiQQn: za stary jestem i nawet nie chce mi sie tego kodu analizować, przepraszam

[GlenPL]

C++ bez STL jest upośledzony, moim zdaniem błędem jest kazać komuś napisać coś jednocześnie zabierając mu klawiaturę...

[G.....n]

@ChiQQn: Masz się skupić na uczciwości, przepustowości, opóźnieniu, deadline'ach?

[G.....n]

@ChiQQn: PS. Multi-level feedback queue może być, ale nie musi, najlepszym rozwiązaniem. Linux odszedł od niego dawno temu na rzecz , BSD i Windows nadal z niego korzystają. Linux korzysta z drzew czerwono-czarnych w CFS.

[ChiQQn]

@Ginden: dzięki za rzeczową odpowiedź. Mam pod uwagę zabrać tylko priorytet (pozostałych parametrów brak w klasie) problemem jest to że nie jestem pewien czy używając interfejsu queue jestem w stanie napisać scheduler który się będzie składał z kilku kolejek. Jakbyś to zrobił? Obecnie pracuje nad wprowadzeniem quicksorta do sheduera.