niedziela, 9 sierpnia 2009

Priority inversion interview

Interviews are great possibility to evalute one's own memory and cold blood during conversation. It is also good for remembering of some basic terms and problems.
Recentely I had to describe priority inversion problem. Basic stuff :) thread with lower priority is executed in place of higher priority thread. But why? Wait, ..., well, ..., shit, I do not remember.
Why Wikipedia is not connected to my brain - 3 threads, 2 competing for mutex, third executing, and so on (Mars Pathfinder problem, priority inheritance, priority ceiling, disabling interrupts).
Ok, but if I want to simulate such problem in Windows environment?
After quick search I found Priority Inversion and Windows NT Scheduler. I realized that:
1. real-time priority class shall be set for process - to disable kernel altering threads priorites,
2. example shall run on one core - in simple case of 3 threads,
3. on one core machine system will hang (real-time priority), therefore example can be run only on multi-core machine (but threads will use only one of the cores).
Example code for priority inversion:

class PrioriyInversion
static private object o = new object();

static void tf(object p)
string n = (string)p;
Console.WriteLine(p+" critical section needed");
lock (o)
Console.WriteLine(p+" critical section entered");
Console.WriteLine(p+" after sleep");
Console.WriteLine(p+" critical section left");

static void tf2(object p)
string n = (string)p;
Console.WriteLine(p + " start");
for (int i = 0; i < 1000000; ++i)
for (int j = 0; j < 1000000; ++j)
Console.WriteLine(p + " stop");

static void Main(string[] args)

Thread t1 = new Thread(tf);
t1.Priority = ThreadPriority.BelowNormal;
Thread t2 = new Thread(tf);
t2.Priority = ThreadPriority.AboveNormal;
Thread t3 = new Thread(tf2);
t3.Priority = ThreadPriority.Normal;


Program has Console.ReadLine() at the beginning to let user change affinity to one of the cores only and set priority class of the process to real-time. If these conditions are not achieved, priority inversion will not appear.
Additionally to change affinity and priority Windows Task Manager can be used. But if you want to see threads inside process, Process Explorer from Sysinternals (now on Microsoft page) can be used.