CODEWITHSUNDEEP
asp.net.netvb.netmultithreadingqueue
EJD
EJD

Reputation: 751

Calculate Queue Wait Times

I am looking to calculate the wait in a queue per position or a general time based on your queue position. It is a FIFO.

List of current performance status of the service

Size            AvTime  Queue Processing AvgFileSize(mb)
1 (0 - 1 mb)    2.57    18    3          0.21
2 (1 - 5 mb)    12.43   2     4          2.16
3 (5 - 10 mb)   23.38   9     8          6.72
4 (10 - 25 mb)  38.17   1     4          12.52
5 (>= 25 mb)    109.31  0     0          32.41

The current list of processing and queued batch files. Only lists the current users files so that is why there are queue numbers missing.

Queue       Filename                Status
30          Batch (3456).XML(2)     Queue    
20          Batch (2399).xml(3)     Queue    
14          batch (1495).xml(1)     Queue    
12          batch (1497).xml(1)     Queue    
15          batch (1499).xml(1)     Queue    
10          batch (1500).xml(4)     Queue    
13          batch (1496).xml(1)     Queue    
11          batch (1501).xml(1)     Queue    
9           batch (1498).xml(1)     Queue    
8           batch (1494).xml(1)     Queue    
7           batch (1493).xml(1)     Queue    
6           batch (1492).xml(1)     Queue    
5           batch (1491).xml(1)     Queue    
4           batch (1490).xml(1)     Queue    
3           batch (1).xml(1)        Queue    
2           Batch1.xml(1)           Queue    
1           Batch1.XML(2)           Queue    
            Batch1.xml(1)           Processing   
            Batch1.xml(1)           Processing   
            Batch1.xml(3)           Processing   
            Batch1.xml(4)           Processing   
            Batch1.xml(1)           Processing   
            Batch1.xml(3)           Processing   
            Batch1.xml(3)           Processing   
            Batch1.xml(3)           Processing   
            Batch1.xml(4)           Processing   
            Batch1.xml(4)           Processing   
            Batch1.xml(2)           Processing   
            Batch1.xml(3)           Processing   
            Batch1.xml(3)           Processing   
            Batch1.xml(2)           Processing   
            Batch1.xml(2)           Processing   
            Batch1.xml(3)           Processing   
            Batch1.xml(3)           Processing   
            Batch1.xml(4)           Processing   
            Batch1.xml(2)           Processing

So I am looking to add more information to the list how long until a batch file at position 20 will be waiting in the queue before it starts processing.

Queue       Filename                Status
30 (*30min) Batch (3456).XML(2)     Queue    
20 (*10min) Batch (2399).xml(3)     Queue
...
*estimated

Upvotes: 0

Views: 1035

Answers (1)

Duncan
Duncan

Reputation: 527

Your question doesn't quite provide enough context to make it possible to answer, but I can make some guesses based on the sample displays you provided.

Looks like you have a "single queue, multiple server" setup. In other words, you have a single FIFO queue, and a some fixed number N of jobs that can be in processing at any given time. Is that right?

For your algorithm, let's assume you have the following information:

  • Position of our job in queue (position N means there are N jobs ahead of us)
  • Size of our job
  • Size of each job ahead of us in the queue
  • Pool of jobs being processed, with a certain maximum size N
  • Size of each job currently being processed
  • Elapsed time for each job currently in process (how long since that job started)

First of all, you will need a function ExpectedJobDuration(jobsize) that computes an expected job processing time for a job of a given size, based on the statistics shown in your "performance status" table. This looks pretty straightforward. Given a job size, first figure out which of your five size categories it falls into (0: 0-1mb, 1: 1-5mb, etc.) Then take your job size and multiply by the average time divided by the average size of jobs in that category. That will give you an estimate of ExpectedJobDuration(jobsize), which will tell you how long it takes to run a job of a given size, under the assumption that job time is proportional to job size, for jobs within a particular size range.

Now, for a job of a given size that's already been in process for a given time ElapsedProcessingTime, how long do we expect it to to take complete? A simple answer would be something like:

   ExpectedRemainingTime = ExpectedJobDuration(jobsize) - ElapsedProcessingTime.

For jobs sitting the the queue this will be exactly the same as the expected job duration; for jobs already being processed we subtract the time the job has already been in work. However, if there is some random variation in job processing times, this is not exactly right, and could turn out to be negative. This is sort of like the actuarial problem: the average lifespan of a person is X years, how long do we expect someone to live if they are already Y years old? You would need a lot more statistical data to compute this, so for practical purposes, if the answer comes out negative, just set it to zero. (If someone is 100 years old, and the average human lifespan is 90, expect them to die at any moment. That's not quite right, but perhaps OK as a first approximation. Unless you are the 100 year old person, and not yet ready to die. :-))

OK, now we have a way to compute how long each job ahead of us in the queue should take, and how long it should take to complete jobs already in process.

If the number of jobs currently being processed is less than N (the max that can be processed at any given time) then our job can start right away. So in that case we have the answer - expected delay until our job can start is zero seconds.

Now let's look at the case where we are in position 0 in the queue. That means there are no jobs ahead of us in the queue, so our expected time to start is the minimum of the ExpectedRemainingTime of the jobs in the processing pool.

Now that gives us the basis for a recursive function that computes delay until our expected start time. 

DelayUntilStart(jobPool, currentJob, queue) {
   find minJob in jobPool with minimum ExpectedRemainingTIme
   if currentJob is in position zero of queue
      return expectedRemainingTime(minJob)
   else
      remove minJob from jobPool
      pop the top job from the queue and put it in the jobPool      
      return ExpectedRemainingTime(minJob) + DelayUntilStart(jobPool, currentJob, queue)
   done
}

Note - we may have a very long job ahead of us in the queue - but that doesn't mean we have to wait for it to complete. We just have to wait for it to get into the pool of jobs currently being processed, and then a shorter job might complete and let us into the pool.

The algorithm I just described is going to be an approximation. But it's probably about as good you are going to get without a lot of statistics about job processing times. For practical purposes I bet it would work pretty well.

Upvotes: 1

Related Questions