0

I am writing a timer-based scheduler to accomplish the task of informing a certain process of what to do and when.

The Idea:

Inform an X process of certain requests to perform at timed-intervals. So if the X process needs to perform an action every Y seconds, the scheduler should send the desired request to the X process to perform the action every Y seconds. There could be multiple requests of different time intervals to be sent out by the scheduler, and obviously equal amount of actions to be done by X process.

In addition, it's priority-based: if multiple requests have the same timeout expiry, the request with a highest priority is sent out first.

My thoughts:

  • Create a posix periodic timer (timer_create()) and set them up (timer_settime()) with the specified expiry time for each request
  • Create a priority queue, into which a request is written within the timer callback (triggers every expiry time).
  • Have a main thread that probably reads from a priority queue every certain number of seconds, and writes back the read value to a message queue which wakes up the X process. Now, X process knows to service the request however it wants (not our concern).

Concerns:

  • If there are multiple requests with the same timeout, how do we ensure the requests are sent in the order of priorities?

My idea is: In the main thread, block it on priority queue and as soon as it's populated from the timer callback, signal the main thread to wake up (via semaphore or conditional variable perhaps) and wait for 1 second before reading from a priority queue. 1 second assuming is long enough to ensure requests of the same priority are already written to a priority queue and the main thread first reads the request of the highest priority, which is then sent out to a message queue.

Could this be a feasible solution?

A scenario:

TimerA and TimerB expire at the same time, but TimerA has a higher priority. The posix timer could invoke the callback for either TimerA or TimerB first. The idea is to ensure the request from TimerA is sent out first followed by that from TimerB

Edit:

I made this basic flowchart to help visualize.

xyf
  • 109
  • 4
  • Did you read about the implementation of cron? https://en.wikipedia.org/wiki/Cron The History section discusses a similar method with important differences used by popular cron implementations. – joshp Aug 14 '21 at 19:26
  • you are using lots of undefined terms "request", "timeout expiry", "action" etc. can you give a simple example of input and output – Ewan Aug 14 '21 at 19:31
  • sorry. @Ewan check this: https://imgur.com/a/ZDdwIJz. Let me know if it's still not clear – xyf Aug 14 '21 at 19:39
  • sorry not clear. I mean like input is a list tasks that have to be run every y seconds? output is the the tasks being run and timestamps? – Ewan Aug 14 '21 at 19:41
  • so basically: 1) timers are created/armed 2) timer callback is triggered for every time expiry: if `Timer A` expires in 5 seconds, a callback is invoked within a thread. It then writes a certain message to send to a priority queue. 3) priority queue is read in `main thread`. 4) the read value is written to a message queue which wakes up `X process`. In basic words, `X process` is being notified what to do when, and that's what the timer scheduler is doing – xyf Aug 14 '21 at 19:47

1 Answers1

1

If you consider timers that expire less than one second from each other to have expired at the same time, then your solution of waiting on a condition variable and then sleeping an additional second before processing the contents of the queue is a good way to make sure that "same time" events are handled in order of priority.

Your solution does have the drawback that it introduces a variable latency of up to 1 second. It is up to you to decide if that is a problem or not.

Bart van Ingen Schenau
  • 71,712
  • 20
  • 110
  • 179
  • Yeah, the 1 second part could lead to missed events too at some point I feel, and it's not always needed. If an event has a unique timeout, the main thread doesn't need to wait for a second before reading off the priority queue. Do you have any other alternative techniques to suggest? – xyf Aug 15 '21 at 07:10
  • @xyf, my preferred option would be to get the priority aspect of the events out of the system (they have the same priority and are handled in order of arrival, even if that is within the same millisecond). If the priority is *really* important, then I would make the processing in `X process` interruptable, so that a higher priority event can interrupt the processing of a lower priority one. But that is a completely different design than you used in your question. – Bart van Ingen Schenau Aug 16 '21 at 06:45