Dining Philosopher Problem and AutoResetEvent.


Introduction

Full code can be downloaded from here.

I think we all know the famous classic problem of dining philosopher. In this problem, we consider n philosophers sitting in round table and n forks and all of them want to eat the spaghetti in front of each one. To eat spaghetti, philosopher must have two forks. The problem is philosopher 1 is taking one fork and waiting philosopher2 for second fork. Similarly, philosopher 2 is taking a fork and waiting philosopher3 for a fork. And philosopher n is taking a fork and waiting philosoper1 for a fork. So, what is actually happening is each philosopher cannot get the two forks at a time because each philosopher is taking a fork and waiting. So, here is the DEADLOCK.

For 5 philosophers we can assume the figure


Fig: Dining Philosopher Problem

Similar incident can be happens in our program and operating system where many processes are struggling to get the resources. There are certain criteria which must meet to cause the deadlock. They are:

1. Each resource can be used by only one thread or process.
2. Thread/Process is holding a resource and waiting for other resource to continue.
3. Resources those are granted previously cannot be forcibly taken away.
4. There must be chain of threads/processes (more than two); each is waiting for the resource held by next
thread/process.

To avoid deadlock, we can negate any of the above conditions. For dining philosopher problem, we will negate the second condition to avoid deadlock.

Code
Full code can be downloaded from here.
I have used AutoResetEvent to implement the dining philosopher problem. I have used one AutoResetEvent as mutex and n others as philosopher events.
There are three states of philosopher.

    enum State
    {
        Thinking,
        Eating,
        Hungry
    }

Let’s look at the code:

private void TakeForks(int i)
        {
            _mutex.WaitOne();
            _philosophersState[i] = State.Hungry;
            TryGetForks(i);
            _mutex.Set();
            _philosopherEvents[i].WaitOne();
        }

        private void TryGetForks(int i)
        {
            if (_philosophersState[i] == State.Hungry &&
                _philosophersState[right(i)] != State.Eating &&
                _philosophersState[left(i)] != State.Eating)
            {
                _philosophersState[i] = State.Eating;
                _philosopherEvents[i].Set();
            }
        }

        private void PutForks(int i)
        {
            _mutex.WaitOne();
            _philosophersState[i] = State.Thinking;
            TryGetForks(right(i));
            TryGetForks(left(i));
            _mutex.Set();
        }

First of all philosopher tries to take both fork. If it is not possible, it waits for the signal from its left and right. Whenever it gets the signal, philosopher again tries to acquire both forks and same process repeats.

void checkForConflict(int i)
        {
            if (_philosophersState[left(i)] == State.Eating)
                Console.WriteLine("Conflict between " + left(i) + " and " + i);
            if (_philosophersState[right(i)] == State.Eating)
                Console.WriteLine("Conflict between " + i + " and " + right(i));
        }

Above code checks for the conflict and displays conflict message whenever two philosophers try to eat using same resource. Our program mustn’t print the conflict messages.

Conclusion
Dining philosopher is a classic deadlock problem of operating system. Every deadlock can be avoided by negating any of the four essential conditions of deadlock.

I have used AutoResetEvent as mutex and for signalling purpose. However, we can use others also.

Advertisements

C# 4.0 dynamic Keyword


Introduction

Generally, C# is statically typed languages and checked type at the compile time. Languages like Ruby, Python are dynamic and determined the objects at the run time. Visual C# 2010 introduces a new keyword, dynamic which is a static type, but an object of type dynamic bypasses static type checking. So C# can use the features of dynamic language. It was introduced for C# 4.0 only and not for .net 4.0.

Whenever you use the dynamic keyword you tell the compiler to turn off the compile time checking. For example

intellisense

You can notice intellisense is saying it is dynamic expression and operation will be resolved at runtime.  Consider above example:

dynamic dynamicString = "Test";
Console.WriteLine(dynamicString.GetType());
dynamic dynamicInteger = 9;
Console.WriteLine(dynamicInteger.GetType());

Above line of code will give an output. System.String and System.Int32.

Another thing is you can call any function and any property. If it is not declared yet, your code will still compile but you will get runtime exception.

dynamic dynamicString = "Test";
dynamicString.Display();
dynamicString.Name = "Pradip";

Note in above code actually dynamicString is String type but you can call method like Display() and property like Name which are not in String. Your code compile well but you will get run time exception.

var Vs dynamic?

You might be familier with the powerful var keyword from .net which is used for implicitly typed variables and for anonymous types. It is static and occurs at compile time. You can’t change the type of the variable at run time.

var varString = "Test";
varString.Display();

In above code, second line will result the compile time error.

Now lets look this piece of code.

dynamic dynamicString = "Test";
var varString = dynamicString;
varString.Display();

Now, varString is dynamic type and above code will compile. var is not a type, var keyword just instruct the compiler to infer the type from the variable’s initialization expression. So, we can use dynamic and var keyword together and they are mutually exclusive in nature.

Reflection and dynamic

Reflection is one way from which you can call invoke method (property and other also) dynamically. Compiler won’t throw any exception about even if there is no exception. But there will be complex long code in your program. For example to use String.Substring you need to write following code.

String str = "Pradip";
Type type = str.GetType();
 String subStr = (String)type.InvokeMember("Substring", System.Reflection.BindingFlags.InvokeMethod, null, str, new Object[] { 3 });

Now, using dynamic you can get same result with clean and neat code.

dynamic dynamicString = "Pradip";
String subString = dynamicString.Substring(3);

Of course, above example is not good enough to give explanation of using dynamic over reflection but you will find it better to use dynamic keyword in you application which uses reflection very much.

Adding/Removing method and property at runtime

Using dynamic keyword you can add/remove method or property from the object at the runtime. For this .net 4.0 provides ExpandoObject and DynamicObject classes defined in System.Dynamic namespace. Here is an example of adding property and method.

dynamic myObject = new ExpandoObject();
myObject.Name = "Pradip";
myObject.Display = new Action<String>(o => Console.WriteLine(myObject.Name));
myObject.Display(null);

COM Interop and dynamic

Many COM interop allow the variation in arguments type and has the return type as Object. So, there needs the casting to appropriate one to use it as the strongly typed variable. The magical dynamic keyword allows us to treat the object in COM signature as dynamic and hence prevents casting. As a result, our code will become more readable and clean.

Without dynamic we would write like this.

((Excel.Range)excelApp.Cells[1, 2]).Value2 = "Pradip";
Excel.Range range2008 = (Excel.Range)excelApp.Cells[1, 2];

And using dynamic we can write.

excelApp.Cells[1, 2].Value = "Pradip";
Excel.Range range2010 = excelApp.Cells[1, 2];

Finally

I hope, you got some knowledge about the NEW dynamic keyword in C# 4.0. The more you use it, the more you will be familier. For now we can say that dyanamic keyword has added the dynamic programming feature in statically typed language C#.

 

Getting Parent Process ID from Child without passing any arguments


In C#, Parent runs ProcessChild through System.Diagonastics.Process and ProcessChild has following codes to find its Parent process Id without use of any arguments.

using System;
using System.Collections.Generic;
using System.Text;
using System.Runtime.InteropServices;
using System.Collections;
using System.Diagnostics;
namespace ProcessChild
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(GetParentProcess().Id);
Console.Read();
}

private static Process GetParentProcess()
{
int iParentPid = 0;
int iCurrentPid = Process.GetCurrentProcess().Id;

IntPtr oHnd = CreateToolhelp32Snapshot(TH32CS_SNAPPROCESS, 0);

if (oHnd == IntPtr.Zero)
return null;

PROCESSENTRY32 oProcInfo = new PROCESSENTRY32();

oProcInfo.dwSize =
(uint)System.Runtime.InteropServices.Marshal.SizeOf(typeof(PROCESSENTRY32));

if (Process32First(oHnd, ref oProcInfo) == false)
return null;

do
{
if (iCurrentPid == oProcInfo.th32ProcessID)
iParentPid = (int)oProcInfo.th32ParentProcessID;
}
while (iParentPid == 0 && Process32Next(oHnd, ref oProcInfo));

if (iParentPid > 0)
return Process.GetProcessById(iParentPid);
else
return null;
}

static uint TH32CS_SNAPPROCESS = 2;

[StructLayout(LayoutKind.Sequential)]
public struct PROCESSENTRY32
{
public uint dwSize;
public uint cntUsage;
public uint th32ProcessID;
public IntPtr th32DefaultHeapID;
public uint th32ModuleID;
public uint cntThreads;
public uint th32ParentProcessID;
public int pcPriClassBase;
public uint dwFlags;
[MarshalAs(UnmanagedType.ByValTStr, SizeConst = 260)]
public string szExeFile;
};

[DllImport("kernel32.dll", SetLastError = true)]
static extern IntPtr CreateToolhelp32Snapshot(uint dwFlags, uint th32ProcessID);

[DllImport("kernel32.dll")]
static extern bool Process32First(IntPtr hSnapshot, ref PROCESSENTRY32 lppe);

[DllImport("kernel32.dll")]
static extern bool Process32Next(IntPtr hSnapshot, ref PROCESSENTRY32 lppe);
 }
}