08. April 2013 · Comments Off on Genetic Algorithms: Examples using Genetic Algorithm Library · Categories: Programming · Tags: , ,

This post explains implementation of two simple genetic algorithms using Genetic Algorithm Library.

To build create a genetic algorithm we need to do following tasks:

  1. Choose representation of the chromosomes
  2. Define fitness operation
  3. Choose crossover and mutation operations and fitness comparator
  4. Choose selection, coupling, replacement, and scaling operations
  5. Choose type of algorithm and stop criteria

Example 1: Finding Minimum of f(x, y) = 5*x*sin(x) + 1.1*y*sin(y); x, y in interval (0, 10)

Important: before using the GAL, GaInitialize must be called. Also, before quitting the application, GaFinalize must be called.

The easiest way is to choose a multi-value chromosome’s representation which supports arithmetic operations [the Chromosome::Representation::GaMVArithmeticChromosome<double> class].

After choosing a chromosome’s representation, the user must define the fitness operation.

class fFitness : public GaFitnessOperation
{
public:

    virtual float GACALL operator() (const GaChromosome*
        chromosome) const
    {
        const vector<double>& vals=
            dynamic_cast<const GaMVArithmeticChromosome<double>*>
            (chromosome)->GetCode();

        return 5*vals[0]*sin(vals[0])+1.1*vals[1]*sin(vals[1]);
    }

    virtual GaParameters* GACALL MakeParameters() const { return NULL; }

    virtual bool GACALL CheckParameters(const GaParameters&
        parameters) const { return true; }
};

The fFitness class inherits the GaFitnessOperation class and overrides operator() which calculates the fitness value of the chromosome by evaluating the actual mathematical function.

The next step is to build a chromosome configuration block (CCB) which contains:

  1. pointer to parameters of chromosomes
  2. pointer to genetic operation functors [crossover, mutation, fitness operation, and fitness comparator]
  3. pointer to value set which defines the domain of x and y variables

The class Chromosome::Representation::GaValueInterval<T> is used as the chromosome’s value set because the domain of x and y variables is a continuous interval (0, 10). GaIntervalValueSet requires four bounds [low and high bounds to specify the interval of the original values, and low and high bounds to specify the interval of the inverted values] and a generator of random values.

GaValueIntervalBound<double /> valueInt(0,10);
GaValueIntervalBound<double /> invValueInt(0,10);
GaValueInterval<double /> valueSet(valueInt,invValueInt,
    GaGlobalRandomDoubleGenerator,false);

The CCB should be:

fFitness fitnessOperation;
GaChromosomeDomainBlock<double> configBlock(&valueSet,
    GaCrossoverCatalogue::Instance().GetEntryData(
    "GaMultiValueCrossover"),
    GaMutationCatalogue::Instance().GetEntryData("GaFlipMutation"),
    &fitnessOperation,
    GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMinFitnessComparator"),
    &chromosomeParams);

The CCB is defined to use the GaMultiValuesCrossover and GaFlipMutation operations. GaMinFitnessComparator is specified because the purpose of the algorithm is to find the minimum of the function.

When the CCB is defined, the user can build the prototype chromosome:

GaMVArithmeticChromosome<double> prototype(2,&configBlock);

Besides the prototype chromosome, the user must define the population’s parameters before the population object can be created:

  1. population size: 30
  2. resizable population: no [incremental algorithm is used, which does not require resizable population]
  3. population is sorted: yes
  4. scaled fitness is used for sorting: no
  5. tracking of the best chromosomes: 0 [population is already sorted]
  6. tracking of the worst chromosomes: 0 [population is already sorted]
GaPopulationParameters populationParams(30,false,true,false,0,0);

This population object uses the default configuration, except it changes the sort comparator:

  1. selection operations: GaSelectRouletteWheel
  2. number of selected chromosomes: 2
  3. coupling operation: GaInverseCoupling
  4. offspring produced: 2
  5. replacement operation: GaReplaceWorst
  6. chromosomes replaced: 2
  7. scaling operation: none
  8. sort comparator: GaMaxFitnessComparator [default] changed to GaMinFitnessComparator

Everything is now ready to create the population object:

GaPopulationConfiguration populationConfig;
populationConfig.SetParameters(populationParams);
populationConfig.SetSortComparator(
    &configBlock.GetFitnessComparator());

GaPopulation population( &prototype, &populationConfig );

This example uses an incremental genetic algorithm [the GaIncrementalAlgorithm class]. To create the algorithm’s object:

GaMultithreadingAlgorithmParams algorithmParams(1);
GaIncrementalAlgorithm algorithm(&population,algorithmParams);

where the user specifies the population on which the genetic algorithm will operate and the parameters of the algorithm. The constructor of the algorithm’s parameters takes the number of working threads.

When the user builds a genetic algorithm for these kind of problems, it is not possible to know the exact termination criteria of the algorithm. In these situations, it is convenient to use a stop criteria based on the duration of the evolution process or its progress. One such stop criteria is a criteria based on the number of generations. The example uses only one thread because the algorithm produces only a few new chromosomes per generation.

GaGenerationCriteriaParams criteriaParams(100000);

algorithm.SetStopCriteria(
    GaStopCriteriaCatalogue::Instance().GetEntryData(
    "GaGenerationCriteria"),&criteriaParams);

The constructor of the criteria’s parameters takes the number of generations after which the algorithm should stop.

To monitor the evolution process, the user must specify an observer object to the genetic algorithm.

class fObserver : public GaObserverAdapter
{
    virtual void GACALL NewBestChromosome(const GaChromosome&
        newChromosome,const GaAlgorithm& algorithm)
    {
        const vector<double>& vals=
            dynamic_cast<const GaMVArithmeticChromosome<double>&>
            (newChromosome).GetCode();
        cout << "New chromosome found:\n";
        cout << "Fitness: " << newChromosome.GetFitness() << endl;
        cout << "x: " << vals[0] << " y: " << vals[1] << endl;
    }

    virtual void GACALL EvolutionStateChanged(GaAlgorithmState
        newState,const GaAlgorithm& algorithm)
    {
        if(newState==GAS_RUNNING)
            cout << "start\n";
        else if(newState==GAS_CRITERIA_STOPPED)
            cout << "end";
    }
};

To register the observer:

fObserver observer;
algorithm.SubscribeObserver(&observer);

And to start the algorithm:

algorithm.StartSolving(false);

StartSolving‘s parameter defines whether the algorithm should continue a previously paused evolution process [true] or it should start an entirely new process [false].

Example 2: Pattern Matching

Pattern Test Application

Screenshot – Pattern Test application

This example implements a genetic algorithm that tries to guess the sequence of characters. The example defines this sequence of characters:

const char pattern[] =
"        GGGGGGGGGGGGG               AAA               LLLLLLLLLLL             "
"     GGG::::::::::::G              A:::A              L:::::::::L             "
"   GG:::::::::::::::G             A:::::A             L:::::::::L             "
"  G:::::GGGGGGGG::::G            A:::::::A            LL:::::::LL             "
" G:::::G       GGGGGG           A:::::::::A             L:::::L               "
"G:::::G                        A:::::A:::::A            L:::::L               "
"G:::::G                       A:::::A A:::::A           L:::::L               "
"G:::::G    GGGGGGGGGG        A:::::A   A:::::A          L:::::L               "
"G:::::G    G::::::::G       A:::::A     A:::::A         L:::::L               "
"G:::::G    GGGGG::::G      A:::::AAAAAAAAA:::::A        L:::::L               "
"G:::::G        G::::G     A:::::::::::::::::::::A       L:::::L               "
" G:::::G       G::::G    A:::::AAAAAAAAAAAAA:::::A      L:::::L         LLLLLL"
"  G:::::GGGGGGGG::::G   A:::::A             A:::::A   LL:::::::LLLLLLLLL:::::L"
"   GG:::::::::::::::G  A:::::A               A:::::A  L::::::::::::::::::::::L"
"     GGG::::::GGG:::G A:::::A                 A:::::A L::::::::::::::::::::::L"
"        GGGGGG   GGGGAAAAAAA                   AAAAAAALLLLLLLLLLLLLLLLLLLLLLLL";
const int patternSize=sizeof(pattern)-1;

UThe ued symbols are: G,A,L,: and a white space.

The genetic algorithm uses a Chromosome::Representation::GaMVArithmeticChromosome<double> chromosome representation with a defined domain of values by the Chromosome::Representation::GaMultiValueSet<char> class.

GaMultiValueSet<char> valueSet(false);
valueSet.Add("GAL: ","     ",5);

The fitness operation calculates the percent of matched characters and returns that number as the fitness value of the chromosomes:

class pFitness : public GaFitnessOperation
{
public:

    virtual float GACALL operator()(const GaChromosome*
        chromosome) const
    {
        const vector<char>& v=
            dynamic_cast<const GaMultiValueChromosome&ltchar>*>
            (chromosome)->GetCode();

        int score=0;
        for(int i=0;i&ltpatternSize;i++)
        {
            if(v[i]==pattern[i])
            score++;
        }

        return (float)score/patternSize*100;
    }

    virtual GaParameters* GACALL MakeParameters() const
        { return NULL; }

    virtual bool GACALL CheckParameters(const GaParameters&
        parameters) const { return true; }
};

The CCB looks like the CCB in the previous example, except it uses a new fitness operation and another fitness comparator, because its objective now is to maximize the fitness:

pFitness fitnessOperation;
GaChromosomeDomainBlock<char /> configBlock(&valueSet,
    GaCrossoverCatalogue::Instance().GetEntryData(
    "GaMultiValueCrossover"),
    GaMutationCatalogue::Instance().GetEntryData("GaFlipMutation"),
    &fitnessOperation,
    GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMaxFitnessComparator"),
    &chromosomeParams);

Prototype chromosome:

GaMultiValueChromosome prototype( patternSize, &configBlock );

This example uses a genetic algorithm with non-overlapping populations, and it produces the entire population. To increase the diversity of the produced chromosomes, the number of selected chromosomes is increased. Note that this type of an algorithm requires a resizable population. The population object and its configuration:

GaPopulationParameters populationParams(30,true,true,false,0,0);

GaPopulationConfiguration populationConfig;
populationConfig.SetParameters(populationParams);
populationConfig.SetSortComparator(
    &configBlock.GetFitnessComparator());
populationConfig.Selection().GetParameters().SetSelectionSize(6);

GaPopulation population(&prototype, &populationConfig);

As mentioned, this example uses the Algorithm::SimpleAlgorithms::GaSimpleAlgorithm class for the genetic algorithm.

GaSimpleAlgorithmParams algorithmParams(10,2);
GaSimpleAlgorithm algorithm(&population,algorithmParams);

The first argument of the parameters’ constructor is the elitism depth and the second is the number of working threads. This algorithm produces much more chromosomes per generation than the previous one, so it is suitable for parallelization.

In this example, the exact termination condition is known: when the algorithm finds the chromosome with a fitness value of 100 [100% match]. The right stop criteria is Algorithm::StopCriterias::GaFitnessCriteria:

GaFitnessCriteriaParams criteriaParams(100,GFC_EQUALS_TO,
    GSV_BEST_FITNESS);
algorithm.SetStopCriteria(
    GaStopCriteriaCatalogue::Instance().GetEntryData(
    "GaFitnessCriteria"),
    &criteriaParams);

The observer of the algorithm displays the best chromosomes as they are found:

class pObserver : public GaObserverAdapter
{
public:
    virtual void GACALL NewBestChromosome(const GaChromosome&
        newChromosome,const GaAlgorithm& algorithm)
    {
        const vector<char>& v=
        dynamic_cast<const GaMultiValueChromosome<char>&>
            (newChromosome).GetCode();

        cout<<"Generatiron: "<<
            algorithm.GetAlgorithmStatistics().GetCurrentGeneration()
            <<endl;
        cout<<"Fitness: "<<newChromosome.GetFitness();
        cout<<"\n-------------------------\n";

        for(int i=0;i<v.size();i++)
        {
            if(!(i%78))
                cout<<endl;

            cout<<v[i];
        }
        cout<<"\n-------------------------\n";
    }

    virtual void GACALL EvolutionStateChanged(GaAlgorithmState
        newState,const GaAlgorithm& algorithm)
    {
        if(newState==GAS_CRITERIA_STOPPED)
            cout<<"end.";
    }
};

The subscription of the observer is the same as in the previous example:

pObserver observer;
algorithm.SubscribeObserver( &observer );

The starting of the evolution:

algorithm.StartSolving(false);

Downloads

Source code and Demo applications

08. April 2013 · Comments Off on A Very Brief Introduction to Genetic Algorithms · Categories: Programming · Tags: ,

Genetic algorithms operate on a set of possible solutions called chromosomes. Chromosomes store coded solution and an addition value fitness value. Because of the random nature of genetic algorithms, solutions found by an algorithm can be good, poor, or infeasible [defective, erroneous] and this information is represented by fitness value and it tells genetic algorithm how good the solution is. These are the two main components of a chromosome.

Chromosomes are grouped into population [set of solutions] on which the genetic algorithm operates. In each step [generation], the genetic algorithm selects chromosomes from a population [selection is usually based on the fitness value of the chromosome] and combines them to produce new chromosomes [offspring]. These offspring chromosomes form a new population [or replace some of the chromosomes in the existing population] in the hope that the new population will be better than the previous ones. Populations keep track of the worst and the best chromosomes, and stores additional statistical information which can be used by the genetic algorithm to determine the stop criteria.

A chromosome, in some way, stores the solution which it represents. This is called the representation [encoding] of the solution. There are a number of probable ways to represent a solution in such a way that it is suitable for the genetic algorithm [binary, real number, vector of real number, permutations, and so on] and they mostly depend on the nature of the problem.

Chromosome representation

Diagram – Chromosome representations [for maximization of a single-parameter function]

Chromosome representation

Diagram – Chromosome representations [Traveling Salesman Problem]

Genetic algorithms produce new chromosomes [solutions] by combining existing chromosomes. This operation is called crossover. A crossover operation takes parts of solution encodings from two existing chromosomes [parents] and combines them into a single solution [new chromosome]. This operation depends on the chromosome representation, and can be very complicated. Although general crossover operations are easy to implement, building specialized crossover operations for specific problems can greatly improve the performance of the genetic algorithm.

Crossover Operation Examples

Diagram – Crossover operation examples

Before a genetic algorithm finishes the production of a new chromosome, after it performs a crossover operation, it performs a mutation operation. A mutation operation makes random, but small, changes to an encoded solution. This prevents the falling of all solutions into a local optimum and extends the search space of the algorithm. Mutations as well as crossover operations depend on the chosen representation.

Mutation Operation Examples

Diagram – Mutation operation examples [swap mutation is performed over the first, and over the second, an invert mutation is performed]

Crossover and mutation operations are not always performed when producing a new chromosome. If crossover is not performed, the genetic algorithm produces a new chromosome by copying one of the parents. The rates of crossover and mutation operations are called crossover probability and mutation probability, respectively. The crossover probability is usually high [about 80%], and the mutation probability should be relatively low [about 3%, but for some problems, a higher probability gives better results]. A higher mutation probability can turn the genetic algorithm in to a random search algorithm.

The last operations defined by genetic algorithms used to manipulate chromosomes are fitness operations and fitness comparators. A fitness operation measures the quality of the produced solution [chromosome]. This operation is specific to the problem, and it actually tells the genetic algorithm what to optimize. Fitness comparators [as their name suggests] are used to compare chromosomes based on their fitness. Basically, a fitness comparator tells the genetic algorithm whether it should minimize or maximize the fitness values of chromosomes.

Choosing parents for the production of new chromosomes from a population is called selection. Selection can be based on many different criteria, but it is usually based on the fitness value. The idea behind this is to select the best chromosomes from the parents in the hope that combining them will produce better offspring chromosomes. But, selecting only the best chromosomes has one major disadvantage, all chromosomes in a population will start to look the same very quickly. This narrows the exploration space, pushes the genetic algorithm into the local optimum, and prevents the genetic algorithm from finding possibly better solutions that reside in inaccessible areas of the exploration space. To preserve the diversity of chromosomes [and a wider exploration space] within the population, selection operations usually introduce a factor of randomness in the selection process. Some implementations of selection operations are entirely random.

One problem may occur with selection operations that are based on fitness values. When there is a chromosome with a dominant fitness value, it will be selected most of the times, thus it will cause problems similar to the existing ones. To prevent this, fitness values can be scaled [transformed] to lower the difference between dominant chromosome(s) and the rest of the population [this allows other chromosomes to be selected]. There are many ways to transform a fitness value. Usually, they are implemented by applying a mathematical transformation to the fitness value, but there are other methods like ranking based scaling that use the rank [based on the raw fitness values of chromosomes] of a chromosome as the scaled fitness value.

Scaling Fitness Values

Diagram – Scaling fitness value [shows the selection probability of chromosomes]

A coupling operation defines how the selected chromosomes [parents] are paired for mating [mating is done by performing a crossover operation over the paired parents and applying a mutation operation to the newly produced chromosome]. This operation gives better control over the production of new chromosomes, but it can be skipped and new chromosomes can be produced as the selection operation selects parents from the population.

Coupling Operation Flowchart

Diagram – Coupling operation flowchart

Selection Operation with no Coupling Operation Flowchart

Diagram – Selection operation without coupling operation flowchart

The next step performed by a genetic algorithm is the introduction of new chromosomes into a population. Offspring chromosomes can form a new population and replace the entire [previous] population [non-overlapping population], or they can replace only a few chromosomes in the current population [overlapping population]. For overlapping populations, the replacement operation defines which chromosomes are removed [usually the worst chromosomes] from the current population and which offspring chromosomes are inserted. By replacing chromosomes, there is a chance that the genetic algorithm will lose the best chromosome[s] [found so far]. To prevent this, the concept of elitism is introduced into genetic algorithms. Elitism guarantees that the best chromosome[s] from the current generation are going to survive to the next generation.

An algorithm performs the previously described steps one by one in sequence, and when they have been performed, it is said that a generation has passed. At the end of each generation, the genetic algorithm checks the stop criteria. Because of the nature of genetic algorithms, most of the time, it is not clear when the algorithm should stop, so a criteria is usually based on statistical information such as the number of the generation, the fitness value of the best chromosome, or the average fitness value of the chromosomes in the population, the duration of the evolution process…

Genetic Algorithm Flowchart

Diagram – Flowchart of a genetic algorithm [overlapping population coupling operation]

Genetic Algorithm Flowchart

Diagram – Flowchart of a genetic algorithm [overlapping population without coupling operation]

Genetic Algorithm Flowchart

Diagram – Flowchart of a genetic algorithm [non-overlapping population with coupling operation]

07. April 2013 · Comments Off on Queued Spinlocks · Categories: Programming · Tags: , , , , , ,

Queued spinlocks are designed as replacement for standard spinlock as main synchronization mechanism in kernel mode of an OS. They provide better performance on multiprocessor systems by reducing contention of interconnection bus during busy waiting, providing fairness and locality of reference. Standard spinlocks suffers from contention of interconnection between processors caused by usage of a single memory location shared by all processors for spinning. This significant increase traffic between processors is caused by cache coherency protocol. On the other hand, when queued spinlocks are used, each processor uses its own memory location to spin which avoids memory sharing and ease traffic between processor, in addition to that, memory used for spinning is located on the stack currently used by the processor which further improves performance. Queued spinlocks also guarantee that processors will enter guarded critical section in the same order in which they arrive, which is not the case with standard spinlocks.

Implementation

// represents processor in wait queue of the spinlock
struct qsl_entry
{

    // next processor in the queue that is waiting to enter section
    qsl_entry* next;

    // indicates whether the access to section
    // has been granted to processor
    int state;

};

// queued spinlock
struct qsl
{

    // the last processor in the queue
    // that is waiting to enter section
    qsl_entry* tail;

};

// requests access to critical section guarded by the spinlock,
// if the section is already taken it puts processor to wait
// and insert it into queue
// lck - queued lock that used to guard section
// ent - entry that represent processor in queue of the spinlock
void lock_qsl(qsl* lck, qsl_entry* ent)
{
    __asm
    {
        mov eax, ent;
        mov ebx, lck;

        // prepare queue entry
        mov [eax], 0;
        mov edx, eax;
        mov [eax]qsl_entry.state, 1;

        // store it as the last entry of the queue
        lock xchg [ebx], eax;

        // if the section available - grant access to processor?
        test eax, eax;
        jz enter_section;
            // link new entry with the rest of queue
            mov [eax], edx

            // wait for processor's turn
            wait1:
                pause;
                cmp [edx]qsl_entry.state, 1;
                je wait1;

        enter_section:
    }
}

// release access to critical section guarded by the spinlock
// it also grants access to next processor in the queue if there is one
// lck - queued lock that used to guard section
// ent - entry that represent processor in queue of the spinlock
void unlock_qsl(qsl* lck, qsl_entry* ent)
{
    __asm
    {
        mov eax, ent;
        mov ebx, lck;
        xor ecx, ecx;
        mov edx, eax;

        // release section and get next processor in the queue
        // which is waiting for the section
        lock cmpxchg [ebx], ecx;

        // is this the last processor waiting for the queue?
        je exit_section;

            // wait for processor that just has started
            // entering into section
            wait2:
                pause;
                cmp [edx], ecx;
                je wait2;

            // grant access to next processor in the queue
            mov eax, [edx];
            mov [eax]qsl_entry.state, ecx;

        exit_section:
    }
}

If you need to use it in 64-bit environment you can use 64-bit wide registers (rax, rbx…) registers instead of 32-bit wide (eax, ebx…) and set type of state field in qsl_entry structure to long long instead of int.

Explanation

Let examine the function that acquires the lock more closely:

P-CPU – the last CPU that arrived to the lock. It either holding the lock or is trying to acquire the lock.
N-CPU – CPU that should get the lock next, after the CPU that is currently holds it release the lock.
C-CPU – current CPU that is executing instruction stream being discussed.

Before the execution of lock xchg [ebx], eax instruction, [ebx] is reference to lck->tail which is address of qsl_entry used the P-CPU. eax stores address of qsl_entry used by the C-CPU. After the execution is done, eax will store address of qsl_entry whose next field should be modified to point to qsl_entry of the C-CPU, and qsl->tail will store address of qsl_entry used by the C-CPU. Needless to say lock ensures that this will be done atomically if more CPU hit it simultaneously.

If qsl->tail was null, section was not occupied by any CPU. Since now eax stores this value next test is enough to see if section is available: test eax, eax and jz enter_section. If the test fails it means that the section is already locked. If that that is the case we instruct P-CPU that it needs to notify C-CPU that section is free when P-CPU exits section. We do this by writing address of qsl_entry used by the C-CPU to next field of qsl_entry used by P-CPU, or in code: mov [eax], edx.

Now we just need to wait for P-CPU to set state field of C-CPU’s qsl_entry to 0 which is implemented in wait1 loop. Note that cmp [edx]qsl_entry.state, 1 does not need lock prefix. Instructions that performs just reads or just writes of bytes, words and dwords (qwords too in case CPU is running in 64-bit mode) are guaranteed that be atomic if they are properly aligned.

Now let’s see how freeing the acquired lock works:

Before the execution of lock cmpxchg [ebx], ecx instruction, eax holds address of qsl_entry used by C-CPU, ebx stores address of lck->tail and ecx is 0. After the execution, if there where no other CPU waiting for the lock, then qsl_entry of the C-CPU and lck->tail are equal, cmpxchg was successful ([ebx] == eax) and it set lck->tail to null which will mark section as free again. Otherwise the instruction did not perform any actions, except setting C-CPU’s flags, and it means that C-CPU should notify the N-CPU that the lock is free for it to acquire. Again lockxchg instruction while it is trying to acquire the lock.

Since cmpxchg modifies CPU’s zero flag with the result of comparison we can us je exit_section instruction to skip notification when there are no CPUs waiting.

When there is CPUs waiting, we must ensure that N-CPU finish putting itself in the queue before we notify it. Since we know that C-CPU’s qsl_entry is not lck->tail, we know that next of C-CPU’s qsl_entry cannot be null. That is the period between the execution of lock xchg [ebx], eax and mov [eax], edx in function that acquires lock. So we need to wait for N-CPU to set next and we are good to go. This is implemented by wait1 loop. Finally when the loop exits, we can notify N-CPU that is free to enter the section by setting state field of its qsl_entry to 0.

Using the Code

This is a simple example:

qsl lock;
int thread_1(void* p)
{
    qsl_entry entry;
    while( 1 )
    {
        lock_qsl( &lock, &entry );
        printf( "thread " );
        printf( "%d", (int)p );
        printf( "\n" );
        unlock_qsl( &lock, &entry );
     }
     return 0;
}

int main()
{
    CreateThread( NULL, 0, (LPTHREAD_START_ROUTINE)thread_1,
        (void*)1, 0, NULL ); 
    CreateThread( NULL, 0, (LPTHREAD_START_ROUTINE)thread_1,
        (void*)2, 0, NULL ); 
    getchar();
    return 0;
}