At this time, I have following 2 options in my mind, 1. When a request for a queue with a requirement of m slots, given the calendar depth n, I find n / m, say p. p is the maximum distance that can be provided amongst the slots of a queue in the calendar table. For example, n = 252 and m = 4 then p = 73. So I can assign slots 0, 73, 166 and 239 to the queue. But, these slots may be allocated to another queue. So I try to find the next slot free closest to the slot number which is not free.
But, this solution is biased towards the request rcvd first. Let me take an example and explain the problem. Suppose I get 21 requests for queues with 2 slots. Then with above solution, 1st queue with 2 slots gets: slot 0 and slot 126. Second queue gets slot 1 and slot 127, third queue gets slot 2 and slot 128. This way slots 0 - 20 and slot 126-146 will be allocated. Let us, at this point I get a request to allocate a queue with 12 slot requirement. Then p = 21. And in this case I will not be able to allocate this queue properly because my calendar table is bunched up in 2 places with 21 contiguous slots. This is a problem with this solution. 2. To solve the above problem, there is another solution. Every time a new request for a queue with m slots is rcvd, reallocate all the previously allocated queues and the new queue in the calendar table. This can use the binpack or knapsack solution which you have proposed in the other mail. In this solution we can sort the queues in ascending order of their slot requirements. The queues with larger slot requirements will be allocated first in the calendar table and then smaller slot requirement queues. I feel this will solve the issues in first solution. But, solution 2 has a problem, new queue requirements or modification in the number of slots for an already allocated queue may come very often ( can be 20-30 request in a second in some cases)and therefore running the 2nd solution may be a bit costly. So, the third solution is to mix the above 2 solution. We require second solution because 1st solution has a problem under certain conditions but it is simpler to design. So we can use 1st solution but when we hit the problem then we can use 2nd solution and then again start using 1st solution. In this way, problem with 2nd solution of heavy CPU utilization can also be reduced because 2nd solution is used only when 1st reaches a problem state. But, I still want some refinement to my solution. Any suggestions? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
