Most efficient way to implement preemptive waiting queue?

Question

Hi all. I've been racking my brain trying to figure this out. Here is the scenario. I essentially have a sorted static list that contains various times that an event is supposed to happen. For visualization:

+-----------------------+
|  Time  |  LastUpdate  |
|-----------------------|
|    1   |   03:10:00   | 0
|    2   |   03:10:00   | 1
|    2   |   03:10:00   | 2
|    3   |   03:10:00   | 3
|    3   |   03:10:00   | 4
|    4   |   03:10:00   | 5
+-----------------------+

So, the first time through the method, the lastTime property is going to be null, so it will "do some work" and set the lastTime property to the current time. The time property signifies when the item will need to be executed again. For instance, since element 0 has a lastTime of 03:10:00 and a Time of 1, it will need to be executed at 03:11:00, element 1 and 2 both have a lastTime of 03:10:00 and both need to be executed at 03:12:00, and so and so forth.

Here is a rough implementation of what I have going:

public static IList<Item> _list;

public void DoSomething()
{
    while (true)
    {
     for (int i = 0; i < _list.Count; i++)
     {
      var item = new Item();

      if (DateTime.MinValue.Equals(_list[i].LastUpdate))
      {
       item = DoWork(_list[i].Url);
       _list[i].LastUpdate = item.LastUpdate;
       Console.WriteLine(item.Title + " @ " + item.LastUpdate + "; i = " + i);
      }
      else
      {
       var timeToSleep = ((_list[i].LastUpdate.AddMinutes(_list[i].Time)).Subtract(DateTime.Now));

       if (timeToSleep.TotalMilliseconds > 0)
       {
        for (int j = 0; j < i; j++)
        {
         var lastRet = _list[j].LastUpdate.AddMinutes(_list[j].Time);
         var nextFetch = DateTime.Now.Add(timeToSleep);

         if (lastRet < nextFetch)
         {
          item = DoWork(_list[i].Url);
          _list[i].LastUpdate = item.LastUpdate;
          Console.WriteLine(item.Title + " @ " + item.LastUpdate + "; i = " + i);
         }
        }
       }

       if (timeToSleep.TotalMilliseconds > 0)
       {
        Console.WriteLine("Sleeping until: " + DateTime.Now.Add(timeToSleep));
        System.Threading.Thread.Sleep(timeToSleep);
       }

       item = DoWork(_list[i].Url);
       _list[i].LastUpdate = item.LastUpdate;
       Console.WriteLine(item.Title + " @ " + item.LastUpdate + "; i = " + i);
      }
     }

     Console.WriteLine("--------------------------");
    }
}

If there is nothing that needs to be done, it will sleep until the next item in the list is ready to be updated. The inner for loop is put in place to prevent the more frequently updated items from having to wait until the less frequently items are updated before it can update itself again. In an ideal scenario, it will check to see if any items above it need updating before it calls Sleep. If any items above the current item will need updating before the the current item sleeps, then go ahead and update them. If not, then the current item will go call Sleep to wait until it is ready to be updated. I hope this makes sense.

Am I going about this totally wrong? Is there an easier solution to this? I am open to any and all suggestions. Also, please keep in mind that this list could potentially grow to thousands of items. Thanks in advance.

Answer 1

I don't entirely understand your problem description, but this seems unnecessarily complicated to me. How about:

public static IList<Item> _list;

public void DoSomething()
{
    while (true)
    {
        DateTime minDate = DateTime.MaxValue;

        for (int i = 0; i < _list.Count; i++)
        {
            DateTime nextExecution = _list[i].LastUpdate.AddMinutes(_list[i].Time);

            if (nextExecution <= DateTime.Now)
            {
                var item = DoWork(_list[i].Url);
                _list[i].LastUpdate = item.LastUpdate;
                nextExecution = _list[i].LastUpdate.AddMinutes(_list[i].Time);
                Console.WriteLine(item.Title + " @ " + item.LastUpdate + "; i = " + i);
            }

            if (nextExecution < minDate)
                minDate = nextExecution;
        }

        TimeSpan timeToSleep = minDate.Subtract(DateTime.Now));

        if (timeToSleep.TotalMilliseconds > 0)
        {
            Console.WriteLine("Sleeping until: " + minDate);
            System.Threading.Thread.Sleep(timeToSleep);
        }
    }
}

If the number of tasks becomes large, you might want to keep a linked list that is ordered by the next calculated execution time. That way, you don't have to loop through the entire list every iteration.