Tuesday, February 28, 2017

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?

Monday, February 20, 2017

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?

Wednesday, February 1, 2017

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;