A Developer's Diary

Mar 2, 2011

Producer and Consumer Problem revisited with Events

The producer and consumer problem we visited earlier used CRITICAL_SECTION for synchronization and the threads were spinning and checking over the queue size to add or remove the elements. In this post, we are going to use Windows Event objects for synchronizing the Producer and Consumer threads.

Key Points
1. Events are kernel objects which contain an usage count, flag indicating the type of event (manual-reset or auto-reset) and another flag indicating the state (signaled or non-signaled)
2. Applications use Event Objects to notify the waiting threads that an operation has been completed
3. An event is signaled using the call
SetEvent(Handle hEvent)

4. When a manual-reset event is signaled, all threads waiting on the event become schedulable. When an auto-reset event is signaled, only one of the threads waiting on the event becomes schedulable

Event uses five functions CreateEvent, OpenEvent, SetEvent, ResetEvent, and PulseEvent. The functions I will be using in my examples are:

HANDLE CreateEvent(
  LPSECURITY_ATTRIBUTES lpEventAttributes,
  BOOL bManualReset,
  BOOL bInitialState,
  LPCTSTR lpName
);
BOOL SetEvent(
  HANDLE hEvent
);
BOOL ResetEvent(
  HANDLE hEvent
);

The Event class below is a wrapper over windows manual-reset Event Object, provides easy interface to use and also takes care of the cleanup activities for the event handles.
#ifndef _Event_H_
#define _Event_H_

//File: Event.h

#include <windows.h>
#include <process.h>
#include <iostream>

namespace examples
{
    class Event : public NonCopyable
    {
    public:
        Event()
        {
            m_evt = (HANDLE) ::CreateEvent(0, true, false, 0);
            if(NULL == m_evt)
            {
                std::cout <<  "ERROR: Cannot create event" << std::endl;
            }
        }

        ~Event()
        {
            ::CloseHandle(m_evt);
        }

        bool wait(size_t timeout)
        {
            bool retval = false;

            switch(::WaitForSingleObjectEx(m_evt, timeout == 0 ? INFINITE : timeout, false))
            {
            case WAIT_OBJECT_0:
                retval = true;
                break;
            default:
                std::cout << "ERROR: Wait Failed " << ::GetLastError() << std::endl;
                break;
            }
            ::ResetEvent(m_evt);

            return retval;
        }

        bool signal()
        {
            return ::SetEvent(m_evt);
        }

    private:
        HANDLE m_evt;
    };
}

#endif //_Event_H_
The Shared Message Queue Class
#ifndef _MQ_H_
#define _MQ_H_

//File: MQ.h

#include <iostream>
#include <deque>
#include "Lock.h"
#include "Event.h"

using namespace std;

namespace examples
{
    class MQ
    {
    public:
        MQ(size_t size = 10) : m_max_size(size){}

        ~MQ()
        {
            m_q.clear();
        }

        void add(const string& elem)
        {
            m_qlock.acquire();
            while(isFull())
            {
                m_qlock.release();
                m_evtProducer.wait(0);
                m_qlock.acquire();
            }
            m_q.push_back(elem);
            debug_print("Producer");
            m_evtConsumer.signal();
            m_qlock.release();
        }

        void remove()
        {
            m_qlock.acquire();
            while(isEmpty())
            {
                m_qlock.release();
                m_evtConsumer.wait(0);
                m_qlock.acquire();
            }
            m_q.pop_front();
            debug_print("Consumer");
            m_evtProducer.signal();
            m_qlock.release();
        }

        bool isEmpty() const
        {
            return m_q.size() == 0;
        }

        bool isFull() const
        {
            return m_q.size() >= m_max_size - 1;
        }

    private:

        void debug_print(const std::string& str) const
        {
            std::cout << str.c_str() << "  [" << ::GetCurrentThreadId() << "] Size=[" << m_q.size() << "]";
            std::cout << endl;
        }

        const size_t   m_max_size;
        deque<const string>   m_q;
        Lock           m_qlock;
        Event          m_evtProducer;
        Event          m_evtConsumer;
    };

}

#endif //_MQ_H_

Read more ...

Feb 26, 2011

Sort elements in a Collection using Comparator Interface

Continuing our series of sorting elements in a Collection, this post makes use of the Comparator interface to sort the objects.

Key Idea
The
sort(List list, Comparator c)
method sorts the specified (modifiable) list in the order specified by the comparator

The Employee Java Bean below makes use of the EmployeeNameComparator class to sort the Employee elements in the list. Also, note the use of NullSafeComparator
package com.samples;

//File: Employee.java

public class Employee
{
    private String empName = null;
    private int empAge;

    public Employee(String name, int age)
    {
        this.empName = name;
        this.empAge = age;
    }

    public String getEmpName()
    {
        return empName;
    }

    public void setEmpName(String empName)
    {
        this.empName = empName;
    }

    public int getEmpAge()
    {
        return empAge;
    }

    public void setEmpAge(int empAge)
    {
        this.empAge = empAge;
    }
}
package com.samples;

//File: EmployeeTest.java

import java.awt.print.Printable;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class EmployeeTest
{
    public static void main(String args[])
    {
        Employee[] empArray = {
            new Employee("Spiderman", 29),
            new Employee("Superman", 30),
            new Employee(null, 0),
            new Employee("Batman", 35),
            new Employee("Perry", 25)
        };
        List<Employee> list = Arrays.asList(empArray);

        DebugPrint(list);
        Collections.sort(list, new EmployeeNameComparator(new NullSafeComparator(new StringComparator(), true)));
        DebugPrint(list);
        Collections.sort(list, new EmployeeAgeComparator());
        DebugPrint(list);
    }

    private static void DebugPrint(List<Employee> list)
    {
        System.out.println();
        System.out.println("== DEBUG ==");
        Iterator<Employee> itr = list.iterator();
        while (itr.hasNext())
        {
            Employee emp = itr.next();
            System.out.println("[Name]: " + emp.getEmpName() + "("   + emp.getEmpAge() + ")");
        }
    }
}
Important
The
NullSafeComparator
class prevents the program from crashing with
NullPointerException
when null is passed to the
compareTo()
function in
StringComparator
class. The class also takes care of the sorting of the
null
elements in the list
package com.samples;

//File: NullSafeComparator.java

import java.util.Comparator;

public class NullSafeComparator implements Comparator
{
    private Comparator comparator;
    private boolean nullsAreHigh;

    public NullSafeComparator(Comparator comparator, boolean nullsAreHigh)
    {
        this.comparator = comparator;
        this.nullsAreHigh = nullsAreHigh;
    }

    public int compare(Object o1, Object o2)
    {
        if(null == o1 && null == o2)return 0;
        if(null == o1 && null != o2)return (nullsAreHigh ? 1 : -1);
        if(null == o2 && null != o1)return (nullsAreHigh ? -1 : 1);

        return comparator.compare(o1, o2);
    }
}

package com.samples;

//File: EmployeeNameComparator

import java.util.Comparator;

public class EmployeeNameComparator implements Comparator<Employee>
{
    private Comparator comparator;

    public EmployeeNameComparator(Comparator comparator)
    {
        this.comparator = comparator;
    }

    public int compare(Employee o1, Employee o2)
    {
        return comparator.compare(o1.getEmpName(), o2.getEmpName());
    }
}
package com.samples;

//File: StringComparator.java

import java.util.Comparator;

public class StringComparator implements Comparator<String>
{
    public int compare(String o1, String o2)
    {
        return o1.compareTo(o2);
    }

}
package com.samples;

//File: EmployeeAgeComparator.java

import java.util.Comparator;

public class EmployeeAgeComparator implements Comparator<Employee>
{
    public EmployeeAgeComparator()
    {
    }

    public int compare(Employee o1, Employee o2)
    {
        if(o1.getEmpAge() == o2.getEmpAge())
        {
            return 0;
        }

        return o1.getEmpAge() > o2.getEmpAge() ? 1 : -1;
    }
}
The sample run of the program shows the Employee list sorted by name and then sorted by age.
Output:

Read more ...

Feb 25, 2011

Sort elements in a collection using Comparable Interface

The Collections class in java provides the following methods for sorting the specified (modifiable) list. This post deals with the first method from the list.

void sort(List list)
void sort(List list, Comparator c)

Key Points

The
sort(List list)
method sorts the elements in ascending order according to the natural ordering of it's elements. The ordering is defined by implementing Comparable interface and overriding the
compareTo()
method. All the elements must implement Comparable interface and must be mutually comparable

Sorting elements using the Comparable Interface

The following example makes use of Person Java Bean to demonstrate the use of Comparable interface and sort in natural order
package com.samples;

//File: Person.java

public class Person implements Comparable<Person>
{
    private String name;
    private int age;

    public Person(String name, int age)
    {
        this.name = name;
        this.age = age;
    }

    public String getName()
    {
        return name;
    }

    public void setName(String name)
    {
        this.name = name;
    }

    public int getAge()
    {
        return age;
    }

    public void setAge(int age)
    {
        this.age = age;
    }

    /**

     * Provides sorting algorithms with a comparison method for natural ordering
     * of Person elements
     */
    @Override
    public int compareTo(Person p)
    {
        return this.name.compareTo(p.name);
    }
}

package com.samples;

//File: PersonTest.java

import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class PersonTest
{
    public static void main(String args[])
    {
        Person[] pArray = {
                new Person("Superman", 30),
                new Person("Spiderman", 35),
                new Person("Hitman", 27),
                new Person("Batman", 32),
                new Person("Perry", 10)
        };
        List list = Arrays.asList(pArray);

        DebugPrint(list);
        Collections.sort(list);
        DebugPrint(list);
    }

    private static void DebugPrint(List<Person> list)
    {
        System.out.println();
        System.out.println("== DEBUG ==");
        Iterator<Person> itr = list.iterator();
        while (itr.hasNext())
        {
            Person p = itr.next();
            System.out.println("[Name]: " + p.getName() + "(" + p.getAge() + ")");
        }
    }
}
Output:

Read more ...

Feb 24, 2011

Orphan Users in SQL Server 2005

All Sql Server logins are stored in a system base table in master database. Whenever a new user is created, a corresponding entry is added in the system base table. There is a associated login entry for every user in system base table which also stores an associated SID (security identifier).

Key Idea

1. An orphan user is one which does not have an associated login entry in the System Base Tables (syslogins for sql server 2000 and sys.server_principals for sql server 2005+)
2. A user is also rendered orphan if the security identifier of the user does not match with the one stored in the system base tables in the master database

Orphaned users are generally created when you do either of the following:
1. Restore a database backup from one server to another
2. Restore an old copy of master database
3. Accidently remove a login belonging to a user

Reporting Orphaned Users
To see all the orphaned users in the database, execute the following query

EXEC sp_change_users_login 'report'

The orphan users if present will be shown as:

OrphanUser1 0x296D8B7BC71BA7459884FE8C17BFC32B
OrphanUser2 0x5F8AD799262298479F6F15FB07E9B0C6

Fixing Orphaned Users
To fix these orphaned users we have to relink the security identifier of the users with the security identifiers of the logins in the system base table. The below query helps fix and reset the password for the orphaned users

EXEC sp_change_users_login 'auto_fix', 'OrphanUser1', null, 'OrphanUser1'
EXEC sp_change_users_login 'auto_fix', 'OrphanUser2', null, 'OrphanUser2'

The above queries will add the login entries if not already present with the given password. In case the login entries are already present, you can use the shorter version of the above queries to fix the problem

EXEC sp_change_users_login 'auto_fix', 'OrphanUser1'
EXEC sp_change_users_login 'auto_fix', 'OrphanUser2'


Note: You may observe the following error: An invalid parameter or option was specified for procedure 'sys.sp_change_users_login' if you are using 'Auto_Fix' as the action instead of 'auto_fix'

References:
Troubleshooting Orphaned Users
MSDN: System Base Tables
Fixing Orphaned Users

Read more ...

Feb 16, 2011

Mutex vs Semaphores

Key Points

1. Only the thread which acquires the mutex can release the mutex successfully.
2. A binary semaphore (semaphore with a count of 1) is similar to mutex but allows other threads to release it.
A thread which owns a mutex can acquire the same mutex recursively without blocking it's execution. This prevents the thread from deadlocking itself while waiting for the mutex it already owns. To release it's ownership under such circumstances, the thread must release the mutex the same number of times it acquired it.

A semaphore is a synchronization object which maintains a count between zero and a maximum value. The count is decremented each time a thread acquires a semaphore and incremented when a thread releases the semaphore. When the semaphore count reaches 0, the thread attempting to acquire the semaphore will be blocked unless some other thread increments it. Thus, a semaphore is useful in limiting the number of threads sharing a resource.

Read more ...