Help required regarding Priority queue using M/M/1 Model

[SAM2012]

Hi,

I have a discrete event simulator for m/m/1 queue. How can I have a program based on priority queue using M/M/1 model. PLEASE help me to have an idea about priorities and thier implementations

[VernonDozier]

Same answer as on your other thread. To reiterate my points on that thread and possibly add some...

• The question is quite vague. There are all sorts of simulators. I could give you advice on a priority queue using STL, then have you say you're not allowed to use it. I could give you advice on how to set up two separate processes, one adding customers via a Poisson distribution and the other serving customers and you might say you don't need separate processes, I could give you advice on how to give things fake timestamps and one process, and you might come back and say that you need separate processes, etc. etc.
• We don't know if you are stuck on the mathematics theory / algorithm part of it or the coding part of it.

Assuming you are not allowed to use STL, I would write my own priority queue and not even worry about the Poisson / Exponential part of it for now. A nice little command line program of pushing to the queue, popping from the queue, printing the queue, etc. When that all works flawlessly, then set up a random number generator that pushes a job onto the queue based on the Poisson distribution and the time elapsed. Keep the "popping" part manual. When THAT works flawlessly, have someone "working the register" with a given time per customer. That register will "pop" from the queue. Get that working. Finally figure out how long each job had to wait between push and pop. I'd write a regular queue first, THEN a priority queue. You're going to notice that nice exponential distribution with the regular queue. Not so much with a priority queue.

[SAM2012]

Thanks for reply, I think I am again unable to phrase my problem. I hope this code would be self explanatory. finding problem in how to set the priority and get response time of each message. I want to define three classes of messages. Like 1 priority defines the highest class and must be served first.
While 2 is on second and then 3rd. How to set the code so that the waiting time would always be higher for class 3 of messages. COde shows that message "m" is enqueued in the server queue. Its priority is checked that could be 1,2,3 . How I should deal this then. This is the question. Code is given here.

#using <System.dll>
#using <mscorlib.dll>
#include "stdafx.h"
#include"stdio.h"
#include <msclr\marshal_cppstd.h>
using namespace System::Collections;
using namespace System;
#include<string.h>
#include<time.h>
using namespace std;
using namespace msclr::interop;
#include "message.h"
#include <vcclr.h>
#include <iostream>
using namespace System::Collections::Generic;
using namespace System::Linq;
using namespace System::Text::RegularExpressions;

////////////////////////////////////////////////////////////////
struct Ana
     {  
       double TEa;
       double TEsf;
      };

////////////////////////////////////////////////////////////////random number generator/////////////////////////////////
double expntl(double x)
      {
         double z,y;     /* Uniform random number from 0 to 1 */

         /* Pull a uniform RV (0 < z < 1) */
         do
         {

                z = (((double) rand()+1.0) / RAND_MAX);
                if(z < 0)
                 z = 1;
          }
         while ((z == 0) || (z == 1));

         /* Inversion formula for exponential RV */

       //Console::WriteLine("exponential random varaiable generated is {0}",z);
         y= (-1/x) * log(z);
       // Console::WriteLine("exponential random varaiable generated is {0}",y);
         return y;
      }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct ListNode
{
    ListNode(gcroot<message^> msg);
    gcroot<message^> msg;
    ListNode* next;
}; 
ListNode::ListNode(gcroot<message^> msg): msg(msg), next(nullptr) {}

public class queue
{
public:
    queue();
    ~queue();
    bool Empty() const;
    //int Next() const;
    void Enqueue(message^);
    void Dequeue();
        void DisplayAll() const;
      private:
    // Disable copying to keep the example simple
        gcroot<String^> bindingkey;
        queue(queue const& obj);

    ListNode* head;
    ListNode* tail;
    gcroot<String^> name; // Added this
};

queue::queue():head(nullptr), tail(nullptr) {}

queue::~queue()
{
    while (head != nullptr)
    {
        Dequeue();
    }
}



void queue::Enqueue(message^ key)
{
    if (head == nullptr)
    {
        head = tail = new ListNode(key);
    }
    else
    {
        tail->next = new ListNode(key);
        tail = tail->next;
    }
}

void queue::Dequeue()
{
    ListNode* temp = head->next;
    delete head;
    head = temp;
}

void queue::DisplayAll() const
{
    for (ListNode* p = head; p; p = p->next)
    {
                Console::WriteLine("the element is {0}", p->msg->routingk);
    }

}




/////////////////////////////////////////////////////////////////queue List class//////////////////////////////////////////////


int main(array<System::String^> ^args)
{
  //four queues are created and added to the list of the queues
   queue *server = new queue;
  System::Collections::Generic::SortedList<double, String^>^ slist = gcnew System::Collections::Generic::SortedList<double, String^>();
 double TWork=0.0,TimDep=0.0; 
 struct Ana *Analysis;                                           
 Analysis = new Ana[15];
  int id=0;
  int no=0;
  int cursor=0; 
  double value=0.01;
  srand(clock());
  double Time=0.0,currtime=0.0;
  Time=currtime+expntl(0.1);  
  slist->Add(Time,"A");

 while(id<100)
  {
    currtime=slist->Keys[cursor]; 
    //Console::WriteLine("the time at which the message start processing is Key = {0}",currtime);
    if(slist->Values[cursor]=="A") 
    { 
      Analysis[no].TEa=currtime;
      Time= currtime+expntl(0.2);
      message^ m = gcnew message(1); 
      server->Enqueue(m);
      slist->Add(Time,"A");
      no= no+1;
       if(m->getType==1)                    
        {
          TimDep=currtime+expntl(0.9);
           slist->Add(TimDep,"D"); 
         }
       else 
           if(m->getType==2)
     }

     else
        if(slist->Values[cursor]=="D")
        {
           Analysis[id].TEsf=currtime;
           id=id+1;
          }

   cursor=cursor+1;
  }

 Console::ReadLine(); 
}

[VernonDozier]

I searched in vain for a call to Dequeue. Perhaps I missed it. I saw one in the destructor, but that doesn't count. I also see nowhere where you store the priority. You possibly don't need to store it if you enqueue it properly, but it'll make life easier to store it.

Priority queues are not FIFO like regular queues, so you can't just insert at the tail and pop from the head. I imagine you want to use a heap, not a linked list.

[SAM2012]

Can you please imagine it without using queue, you are right with priorities it is not FIFO. Now I am working to do it without queues.

[VernonDozier]

Can you please imagine it without using queue, you are right with priorities it is not FIFO. Now I am working to do it without queues.

I have a discrete event simulator for m/m/1 queue.

You lost me. The whole point of your thread, I thought, was that you are trying to understand how an M/M/1 queue system worked and the relationship between the Poisson arrival distribution of customers coming into the queue and the service time for a customer, which will be an exponential distribution. This is for a NON-priority (i.e. a regular FIFO) queue. I can understand if you are throwing away the wrod "priority" and now modeling a plain old queue, but you're saying instead that you are throwing out the word "queue". I'm assuming you don't actually mean that. Otherwise functions like "Enqueue" and "Deque" don't make sense, nor does the phrase "M/M/1 Queue".

I imagine you mean "Imagine it as a regular queue". If not, I have no clue what your question is.

Assuming I am right, it is indeed OK to maintain the queue as a Linked List if you like. No one can run your code due to some of the includes. For example, I've never seen this one. Perhaps others have.

<msclr\marshal_cppstd.h>

You are also using MSDN collections like System::Collections::Generic::SortedList. I'm sure they're perfectly fine, but it's a little hard for non-Microsoft folks like me to go through your code. There are perfectly good generic, portable STL collections like list and queue.

To simulate you need to push to the queue based on some probability distribution based on time. You also need a service time for the cashiers. And when the cashier is idle, that cashier should attempt to pop from the queue. Presumably you should have a class that includes both a queue time and a pop time that you need to fill in. I see neither.

I again see no attempt to dequeue anything anywhere. I also see you writing your own queue AND using a Microsoft-based pre-written linked list that does it for you. Write your own or use one that's pre-written for you. Doing both just confuses thing.

In short, I suggest that you figure out exactly what you are trying to accomplish, throw away what you have, and start from scratch.

[SAM2012]

OK can you help me for one thing if possible. Here the code for exponential distribution. I want to generate random variables using this distribution, But its giving me repeated numbers How can I solve this. AND Is it necessary to give some parameter in this function I want to just have a returned value.

*

double expntl()
    {
      double z,y;     /* Uniform random number from 0 to 1 */

                      /* Pull a uniform RV (0 < z < 1) */
      do
      {

          z = (((double) rand()+1.0) / RAND_MAX);
          if(z < 0)
             z = 1;

       }
      while ((z == 0) || (z == 1));
     Console::WriteLine("exponential random varaiable generated is {0}",z);
      /* Inversion formula for exponential RV */
      y=(-1) * log(z);
     //Console::WriteLine("exponential random varaiable generated is {0}",y);
      return y;
    }

*

[SAM2012]

I am using srand(clock()); in the code as well

[VernonDozier]

Sorry, can't duplicate that. I get different values each time. Post your output.

#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstdlib>
using namespace std;


double expntl()
    {
      double z,y;     /* Uniform random number from 0 to 1 */

                      /* Pull a uniform RV (0 < z < 1) */
      do
      {

          z = (((double) rand()+1.0) / RAND_MAX);
          if(z < 0)
             z = 1;

       }
      while ((z == 0) || (z == 1));
     printf("uniform random varaiable generated is %f\n",z);
      /* Inversion formula for exponential RV */
      y=(-1) * log(z);
     printf("exponential random varaiable generated is %f\n",y);
      return y;
    }


int main()
{
    srand(time(NULL));
    while(1)
    {
        expntl();
        getchar();
    }
    return 0;
}

Output...

uniform random varaiable generated is 0.533255
exponential random varaiable generated is 0.628755

uniform random varaiable generated is 0.051078
exponential random varaiable generated is 2.974394

uniform random varaiable generated is 0.421361
exponential random varaiable generated is 0.864265

uniform random varaiable generated is 0.523236
exponential random varaiable generated is 0.647724

uniform random varaiable generated is 0.353992
exponential random varaiable generated is 1.038482

[SAM2012]

Hi,

Thanks for the function, Now Help me for this one. Actually I want to have a simple function that create the random numbers between 1 to 3. But each time its hould give a different one.

int getP()
{
int i;
//srand((unsigned)time(NULL));
srand(clock());
i = (rand() % 3 + 1);
return i;
Console::WriteLine("the element is {0}",i);
}

when I call this function in the loop.
The output is:

the elemnt is 1
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 2
the elemnt is 3
the elemnt is 3
the elemnt is 3
the elemnt is 3
the elemnt is 3
the elemnt is 3
the elemnt is 3
the elemnt is 3
the elemnt is 3
the elemnt is 3
the elemnt is 3

How can I have the random generation of these digits

[SAM2012]

my complete code of simulator is here. Sorry for not bing clear,But I have tried to put comments

// the program is about having random messages with random priorities and sorting them in queues and processing message whose priority is high.

//#include<stdlib.h> 
#using <System.dll>
#using <mscorlib.dll>
#include "stdafx.h"
#include"stdio.h"
#include <msclr\marshal_cppstd.h>
using namespace System::Collections;
using namespace System;
#include<string.h>
#include<time.h>
using namespace std;
using namespace msclr::interop;
#include <vcclr.h>
#include <iostream>
using namespace System::Collections::Generic;
using namespace System::Linq;
using namespace System::Text::RegularExpressions;

////////////////////////////////////////////////////////////////
struct Ana    //A structure to store the arrival time, departure time with priority of each message. 
     {  
       double TEa;
       double TEsf;
       int priority;
      };

////////////////////////////////////////////////////////////////random number generator/////////////////////////////////
double expntl()
    {
      double z,y;     /* Uniform random number from 0 to 1 */

                      /* Pull a uniform RV (0 < z < 1) */
      do
      {

          z = (((double) rand()+1.0) / RAND_MAX);
          if(z < 0)
             z = 1;
        // Console::WriteLine("exponential random varaiable generated is {0}",z);
       }
      while ((z == 0) || (z == 1));

      /* Inversion formula for exponential RV */
      y=(-1) * log(z);
    // Console::WriteLine("exponential random varaiable generated is {0}",y);
      return y;
    }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct ListNode
{
    ListNode(int value);
    int value;
    ListNode* next;
}; 
ListNode::ListNode(int value): value(value), next(nullptr) {}

public class queue
{
public:
    queue();
    ~queue();
    bool Empty() const;
    int Next() const;
    void Enqueue(int value);
    void Dequeue();
        void DisplayAll() const;
        int getP() const;


      private:
    // Disable copying to keep the example simple

        queue(queue const& obj);

    ListNode* head;
    ListNode* tail;
    gcroot<String^> name; // Added this
};

queue::queue():head(nullptr), tail(nullptr) {}

queue::~queue()
{
    while (head != nullptr)
    {
        Dequeue();
    }
}


bool queue::Empty() const
{
    return head == nullptr;
}

int queue::Next() const
{
    return head->value;
}

void queue::Enqueue(int value)
{
    if (head == nullptr)
    {
        head = tail = new ListNode(value);
    }
    else
    {
        tail->next = new ListNode(value);
        tail = tail->next;
    }
}

void queue::Dequeue()
{
    ListNode* temp = head->next;
    delete head;
    head = temp;
}

void queue::DisplayAll() const
{
    for (ListNode* p = head; p; p = p->next)
    {
                Console::WriteLine("the element is {0}", p->value);
    }

}
int getP()
{
int i;
//srand((unsigned)time(NULL));
srand(clock());
i = (rand() % 3 + 1);
return i;
//Console::WriteLine("the element is {0}",i);
}

/////////////////////////////////////////////////////////////////queue List class//////////////////////////////////////////////

int main(array<System::String^> ^args)
{
  //three queues are created to store the messages priorties wise. cat1 will store all messages with priority 1 and cat2 for 2. I want to have departure of all the messages with
    //priority 1 first then for 2 and then for 3.

   queue *cat1 = new queue;
   queue *cat2 = new queue;
   queue *cat3 = new queue;

  System::Collections::Generic::SortedList<double, String^>^ slist = gcnew System::Collections::Generic::SortedList<double, String^>();
 double TWork=0.0,TimDep=0.0; 
 struct Ana *Analysis;                                           
 Analysis = new Ana[100];
  int id=0;
  int no=0,Qbro=0;
  int cursor=0; 
 double delay=0.00011;
  srand(clock());
  double Time=0.0,currtime=0.0;
  Time=currtime+expntl();  
  slist->Add(Time,"A");

  int flag=0;
 while(id<=50)
  {
    currtime=slist->Keys[cursor]; 
    //Console::WriteLine("the time at which the message start processing is Key = {0}",currtime);
    if(slist->Values[cursor]=="A") 
    { 

      Analysis[no].TEa=currtime;
      Time= currtime+expntl(); 
      slist->Add(Time,"A");
      srand(clock());
      flag=getP();
      Analysis[no].priority=flag;
      Console::WriteLine("the flag is {0}",flag); 
      if(flag==1)
         cat1->Enqueue(1);
      else if(flag==2)
        cat2->Enqueue(2);
      else if(flag==3)
        cat3->Enqueue(3);
      no=no+1;

   if(!(cat1->Empty()))     
       {
         TimDep= currtime+expntl(); 
          slist->Add(TimDep,"D");     
           //cat1->Dequeue();
         }
   else if (!(cat2->Empty())) { 
          TimDep= currtime+expntl()+delay; 
          slist->Add(TimDep,"D");     
           //cat1->Dequeue();
         }
    else if (!(cat3->Empty())) { 
          TimDep= currtime+expntl()+delay; 
          slist->Add(TimDep,"D");     
           //cat1->Dequeue();
            }
    }
else
  if(slist->Values[cursor]=="D")    
       {
         if(Analysis[id].priority==1)
          cat1->Dequeue();
         else if(Analysis[id].priority==2)
          cat2->Dequeue();
         else if(Analysis[id].priority==3)
          cat3->Dequeue();

         Analysis[id].TEsf=currtime;
         id=id+1;   
       }

   cursor=cursor+1;
  }

 for(int i=0; i<=100; i++)
    {
         Console::WriteLine("Key = {0},  Value = {1}",slist->Keys[i],slist->Values[i]);         
     } 

 /*for(int i=0; i<20; i++)
        {
            TWork=Analysis[i].TEsf-Analysis[i].TEa;     
            Console::WriteLine("the arrival at queue  {0} message is {1} ",i, Analysis[i].TEa); 
            Console::WriteLine("the message priority is  {0} message is {1}",i, Analysis[i].priority);
           Console::WriteLine("the finished by server is  {0} message is {1}",i, Analysis[i].TEsf);
           Console::WriteLine("the response time for server is   {0}", TWork); 
           Console::WriteLine("                                  "); 
           Console::WriteLine("                                 "); 
}*/
  Console::WriteLine("  The elements in the first queue are "); 
 cat1->DisplayAll();
  Console::WriteLine("  The elements in the second queue are "); 
 cat2->DisplayAll();
  Console::WriteLine("  The elements in the third queue are "); 
 cat3->DisplayAll();

 Console::ReadLine(); 
}

[SAM2012]

Please ignore if some of the header files are not related what I have been using.

[VernonDozier]

int getP()
{
  int i;
  //srand((unsigned)time(NULL));
  srand(clock());
  i = (rand() % 3 + 1);
  return i;
  Console::WriteLine("the element is {0}",i);
}

Line 8 appears to be unreachable to me. Line 7 is "return i". How can you ever get past it? Therefore I don't understand how you're getting the output you are getting, which apparently is from line 8? Again, line 8 seems like it can never be executed because of line 7.

Line 5 needs to be moved to the very first line on main(). You seed a random number generator once and only once in the program and you do that first thing so you don't forget about it. You don't seed it in a function that is repeatedly called. No wonder you're getting the same number over and over again. clock() is going to keep returning the same value, so your seed will always be the same, and you keep re-seeding it. Look at my program. Notice where I place the srand call and do then same in yours.

[SAM2012]

Thank you very much for the helping answers. I have another query.

struct Ana    //A structure to store the arrival time, departure time with priority of each message. 
         {  
           double TEa;
           double TEsf;
           int priority;
          };
  for(int i=0; i<20; i++)   {
  TWork=Analysis[i].TEsf-Analysis[i].TEa;       
 Console::WriteLine("the arrival at queue  {0} message is {1} ",i, Analysis[i].TEa); 
 Console::WriteLine("the message priority is  {0} message is {1}",i, Analysis[i].priority);
Console::WriteLine("the finished by server is  {0} message is {1}",i, Analysis[i].TEsf);
Console::WriteLine("the response time for server is   {0}", TWork); 
               }

Actually I want to sort the average response time of each message class according to the priority of the message. like the average response time of priority 1, the average response time of priority 2, the average response time of priority 3. PLEASE HELP !

[VernonDozier]

Sorting data is sorting data, regardless of how it got there. You have data elements, you have some method of deciding whether one element is less that another element, and you have a variety of sorting methods (quick sort, merge sort, insertion sort, etc.). If the question is how to generate the data to sort, that's one thing. If the question is about how to sort data, use any of the algorithms I mentioned, or another. If you need help sorting, you'll want to start a new thread because that's irrelevant to the fact that you're dealing with a priority queue.

[SAM2012]

I have somewhat sorted out my issue, But need some help regarding queues operation, which I already have. To help explain the problem you need to look at this code and the queue operations given in the above posted code.

if(Analysis[no].priority==1)
         cat1->Enqueue(no);
      else if(Analysis[no].priority==2)
         cat2->Enqueue(no);
      else if(Analysis[no].priority==3)
         cat3->Enqueue(no);

      while(!(cat1->Empty()))
         {
            p= cat1->Next();
            TimDep= currtime+expntl();
            slist->Add(TimDep,"D");
            Analysis[p].TEsf=TimDep;
         }

consider we have 3 queues cat1, cat2, cat 3. I want to insert items with pririty 1,2,3 respectively. which I am doing via this code. Now I want to process these inserted messages(items "no"). First I want to process all messages in queue "cat1" and dequeue them one by one untill its empty, then it should move to "cat2" and same process and then to "cat3". I am stuck in the process of iterating through each element of queue how can I do that? can you help me please!!!!