# Scheduling Algorithm for Video Player

Background:
In a nutshell. I coded a video player application (on linux). I used a proprietary library/API, with this, video and audio frames comes with well defined format. After decoding (via API), I call scheduling() function for video and audio frames and library does the rest. For argument sake I oversimplified the example.

Now let's say we switched to open source API (like Libav) with this I have everything similar as before except scheduling functions.

The Question:

Short Version:
I need help to devise a scheduling algorithm to use in my video player.

Long Version:
I have video frames and audio frames with timestamps (can be converted to wallclock time via a simple function). Naive approach I did was, rendering frames same order immediately as they arrive. This looks like working but overtime lips sync problem occurs (as expected). I don't quite get it what scheduling function I used before actually doing and since these are closed source (comes as pre-compiled) I can't check it.

Notes:
The original function takes these parameters (if these give some idea/help):

theFrame in frame to display
displayTime in time at which to display the frame in timeScale units
displayDuration in duration for which to display the frame in timeScale units
timeScale in time scale for displayTime and displayDuration

I have all of this parameters/values for each frame.

Update:
What is a scheduling algorithm supposed to do?
What I know is, Scheduling algorithm buffers frames and outputs (video or audio) on scheduled time.

What are its outputs?
Audio and video uses different function but basically does same thing. It outputs video or audio. Simplest terms you see the video and hear audio on the player application thanks to this function correctly in sync.

What are the requirements?
1) Frame to output (video or audio). i.e. YUV Frame Buffer or a PCM packet for audio.
2) Timestamp (stamped on encoder side). i.e. 64bit signed integer, after simple conversion function gives a wall clock kinda time (HH:MM:SS.ms).
3) Timing information (stream time_base and frame duration) i.e. time_base for video : 1(num)/50(den=framerate), duration is tricky let's say it's 1/framerate secs (20 ms in this example)

What is the "overtime lips sync problem"?
Video and audio goes out of sync. In other words, video and audio doesn't match anymore.

What I'm asking is a generic logic for a Scheduling Algorithm, I don't wanna bore with you with details, so I kept is simple.

Think I have a file (like a SRT subtitle file) it has text on every line and timestamp. And I wanna print it on linux terminal line by line according to it's timestamps.

My naive thinking will be:
1) Start a timer when program starts, load the file (SRT) on the memory.
2) Parse lines and timestamps.
3) Find the line with (in the SRT) closest to our timer and print it.
4) Repeat step (3) until EOF

In my original question/problem, I can't load whole media file, it can be a live stream or very big file. I can only buffer few seconds worth of frames (i.e. 25 frames (each for video or audio)).

So what should I do ?

• What is a scheduling algorithm supposed to do? What are its outputs? What are the requirements? What is the "overtime lips sync problem"? – D.W. Jun 26 '18 at 16:21
• Updated the question, please check it again. – the kamilz Jun 27 '18 at 8:04
• is the user able to seek (change the timer) in the middle of of the video? – sunny-lan Jun 28 '18 at 0:07
• No. It's should run on live stream, which is not seekable. – the kamilz Jun 28 '18 at 8:18

If frames are stored in order:

Read the next frame. Delay until the time when you are supposed to display it. Display it. Repeat.

If the timestamp is in the past, you can either display that frame now and immediately read the next frame, or you can drop that frame and display the next frame.

If frames are not stored in order:

Store the frames in a priority queue, with the time when it is supposed to be displayed as the key. Then, repeat the following: extract the next frame from the priority queue (a DeleteMin operation), wait until the time when you are supposed to display it, display it, then repeat.

Or, just sort the frames by the time when they are supposed to appear and apply the simple algorithm at the beginning of my answer.

• It's good to you cover both ordered and unordered cases. Thanks a lot. – the kamilz Jun 29 '18 at 15:37