Linux: Difference between livelocks and deadlocks

Everyone knows what a deadlock [2] is!

Wait for graph as described on wikipedia

Defn Deadlock:
Two or more entities vying to get two or more locks in out of order. This leads to each entity waiting for the other entity to release the lock. Since no one releases their held lock the system is stuck and there is no easy recovery.

What is a livelock then?

What datastructure does the CFS use and why

CFS is the Linux kernels completely fair scheduler. It uses red black (RB) trees. 

Red Black trees - datastructure

Nice notes on understanding red-black trees are here [1] and [2].

Why and How is it used in the scheduler?

Code snippet to maintain moving averages

I want to maintain moving averages over a window without keeping individual elements in that window. A simple way to do it?

double approxRunningAverage (double avgres, double new_measurement) {

    avgres -= avgres / N;
    avgres += new_measurement / N;

    return avgres;
}