Coding / designing a universal thread-safe limiter (i.e., limiting the execution of X () to Y many times per second)

Question

I plan to create a class to limit the execution of a function to a given amount within a specified time, for example:

• Max. 5 files in 1 second

It should be thread safe, and the performance hit should be minimal.

How would you create such a class? I have a few ideas, but none of them seemed right to me.

Is there any known design pattern for such a task? (I encode .NET, but any language is fine)

From the outer class, it should work like this (assuming it's singleton):

Setup:

Limiter.Instance.MaxExecutionPerSecond = 5 

Then we will call it in threads before executing our function, and if necessary, it blocks the thread:

 Limiter.Instance.WaitIfRequired() 

Answer 1

Something like that?

 using Timer = System.Threading.Timer; class Limiter{ public static readonly Limiter Instance = new Limiter(); Limiter(){} int max; Semaphore counter; List<Timer> timers = new List<Timer>(); // warning: not thread safe! public int MaxExecutionPerSecond{ get{return max;} set{counter = new Semaphore(max = value, value);} } public void WaitIfRequired(){ // Our semaphore starts with a count of MaxExecutionPerSecond. // When we call WaitOne(), it decrements the count. If the count // is already zero, the call to WaitOne() will block until another // thread calls Release() to increment the count. counter.WaitOne(); // Set a timer to increment the semaphore in one second. Timer t = null; t = new Timer(o=>{ // Increment the semaphore. counter.Release(); // We no longer need to protect this timer from the GC. timers.Remove(t); t.Dispose(); }); // Hold a reference to this timer to keep it from being disposed of. timers.Add(t); // Set the timer to release the semaphore in one second. t.Change(1000, Timeout.Infinite); } } 

---

EDIT

Keep in mind that the above code will prevent multiple threads from starting at once. If the threads are long, then it is still possible to simultaneously execute multiple threads. For example, if you start 5 threads per second, but each thread runs for 1 second, then at any given time in 10 seconds 10 threads will theoretically execute.

If you want you to never have more than 5 threads running right away, the easiest way is to drop the custom Limiter class and just use Semaphore directly.

 const int maxThreadCount = 5; static Semaphore counter = new Semaphore(maxThreadCount, maxThreadCount); static void NewThread(object state){ counter.WaitOne(); // do something counter.Release(); } 

Now it's about as simple as it can be. One caveat: creating new threads and sleeping them immediately is generally considered a bad idea. It uses system resources to create a thread that does nothing. It is better to queue requests and start new threads (or, even better, use streams of thread threads) to process them only when they have the right to start. It is harder and harder to achieve. Depending on the design, an additional flow for the scheduler / control may be required. Something like that:

 class Limiter{ class WorkData{ readonly ParameterizedThreadStart action; readonly object data; public ParameterizedThreadStart Action{get{return action;}} public object Data {get{return data;}} public WorkData(ParameterizedThreadStart action, object data){ this.action = action; this.data = data; } } readonly Semaphore threadCount; readonly Queue<WorkData> workQueue = new Queue<WorkData>(); readonly Semaphore queueCount = new Semaphore(0, int.MaxValue); public Limiter(int maxThreadCount){ threadCount = new Semaphore(maxThreadCount, maxThreadCount); Thread t = new Thread(StartWorkItems); t.IsBackground = true; t.Start(); } void StartWorkItems(object ignored){ while(queueCount.WaitOne() && threadCount.WaitOne()){ WorkData wd; lock(workQueue) wd = workQueue.Dequeue(); ThreadPool.QueueUserWorkItem(DoWork, wd); } } void DoWork(object state){ WorkData wd = (WorkData)state; wd.Action(wd.Data); counter.Release(); } public void QueueWork(ParameterizedThreadStart action, object data){ lock(workQueue) workQueue.Enqueue(new WorkData(action, data)); queueCount.Release(); } } 

In this class, I removed the singleton property and set the constructor a maxThreadCount . This avoids the lack of thread safety in a first class property. There are other ways to ensure thread safety, but this was the easiest.

Answer 2

For the resolution you are looking for, DateTime.Now is a great watch and very cheap. It is updated with an accuracy of just over 15 ms. In this example, call the Operation () method just before the operation:

 using System; class Throttle { private int mTrigger; private int mOperations; private DateTime mStart; public Throttle(int maxOperationsPerSecond) { if (maxOperationsPerSecond < 1) throw new ArgumentException(); mTrigger = maxOperationsPerSecond; } public void Operation() { mOperations += 1; if (mOperations > mTrigger) { TimeSpan span = DateTime.UtcNow - mStart; if (span.TotalMilliseconds < 1000) System.Threading.Thread.Sleep(1000 - (int)span.TotalMilliseconds); mOperations = 1; } if (mOperations == 1) mStart = DateTime.UtcNow; } } 

Create an instance of the class in your thread, do not share it.

Answer 3

I assume that getting the current time is inexpensive compared to what the function will do.

In this case, I did something like this in Scala, and the design pattern would look something like this:

• WaitIfRequired should block if it is already running. (This would be a "synchronized method" in Java, I'm not sure what the .NET equivalent is.)
• Queuing the times WaitIfRequired was called.
• If the queue length passes MaxExecutionPerSecond , cut it off until it is longer than MaxExecutionPerSecond .
• Turn the top of the queue if its MaxExecutionPerSecond long. If from this time the time is more than a second, press the current time on the tail of the queue and immediately return; enough time has passed. If it is less than a second, sleeping for the time necessary for it to be second (that is, 1 second is the elapsed time) before pressing and returning.

What is it.

You can play with this by querying at most N calls in time T, replacing “one second” with T.

Now, if you do not have synchronized methods, everything becomes a little more interesting (but only a little). Then you need an external locking mechanism to make sure that only one thread at a time is read and wait times.