Real time scheduling for multimedia server using standard Java

Media Server is the systems in which the operational correctness depends not only on the results of the computation but also on the time at which these results are produced. Time critical processes must be executed under timeliness limitation, which is usually described as a term deadline. Tasks must either be completed or its execution must start by the deadline.

The scheduler is the component of the Media Server that selects which process to run next. The scheduler (or process scheduler, as it is sometimes called) can be viewed as the code that divides the finite resource of processor time between the runnable processes on a server.

Many papers have been published in the field of real-time scheduling. Unfortunately much of the published work consists of scheduling algorithms that are defined for systems with preemptive multitasking like Real Time Operating Systems. In preemptive multitasking, the scheduler decides when a process is to cease running and a new process is to resume running. The act of involuntarily suspending a running process is called preemption. The time a process runs before it is preempted is predetermined, and is calle

d the timeslice of the process. Primitive thread management capabilities of standard Java are making unavailable direct implementation of known algorithms. However it is possible to extract from this published material some general purpose techniques.

Thread model and task queue.

There is no way to distrubute CPU time between threads using the Standard Java API. Normaly it means that we anyway can use published materials but with assumption that number of CPUs equal to 1 and construct scheduler around uniprocessor model. Let's now consider CPUs as a single processor with total power equal to sum of all available CPUs. If all CPUs are equivalent, what we have exactly, then it allows to use the model with dynamic task priorities and EDF policy as base. The following diagram depicts the architecture of scheduler.

Each time when new task arrives Acceptor analysis parameters of the task, determines its priority and delivers task to the "ready queue" where position of the task relates to its priority. The task with high priority resides closer to the head of queue and task with lower priority resides closer to tail.

CPUs executes tasks and calculate feedback as difference between estimates and actual result. Finally Scheduler updates the miss rate counter used for congestion control and updates task priority.

I/O CPU Burst Cycle

Saying about media server it is possible to classify inner processes as "IO bound" or "CPU bound". The server make heavy use of I/O endpoints and spend much time waiting for I/O operations to complete; the latter are number-crunching transcoding tasks that require a lot of CPU time. The execution of a process consists of an alternation of CPU bursts and I/O bursts.

The frequency of I/O operations usage inside Media server is very high, espacially for legacy DS0 channels, what means that I/O actions must fill the whole space between CPU bound tasks.

Test results

The actual implementation is still under strong test but even the first tests shows high stability and very good CPU utilization. Bellow is the diagram of average miss rate as dependency of scheduled periodic tasks with period - 20ms, worst execution time 1ms and max jitter 3ms. Congestion control disabled

The archived miss rate is comparebale with bestes real time schedulers constructed on preemtive OS. This test was running on 4-core CPU and thus 80 tasks scheduled relates to 100% of CPU utilzation. Very good result compared with RMA theoretical maxim of 69,3%,