Parallel

Parallel Ranking List

    A. First Edition

    I am practicing with multi-thread.

    B.The problem

    The problem is quite unusual, I mean unimaginable. Say we have a link list and suddenly we are becoming crazy to want to

    dismantle our link list to make them parallel, for example, to save them in an array. However, before breaking the link

    we would like to know their ranks or their position in the link list in order to put them in array in an appropriate

    order. So, this is the question and more particularly, Professor Probst thinks we are rich enough to waste some

    resources to assign each node in list with a thread to solve the problem in a multi-thread manner.

    The following is the original link list:

    [index:1, rank:1]-->[index:2, rank:1]-->[index:4, rank:1]-->[index:0, rank:1]-->[index:3, rank:1]

    Finally you break the list to make them all at same level, say in an array with appropriate rank being calculated for each.

    now print the result
    index:0, randk:2
    index:1, randk:5
    index:2, randk:4
    index:3, randk:1
    index:4, randk:3
    Press any key to continue

กก

C.The idea of program
กก

    There are many ways to do this job and for multi-threading environment, you have to have necessary protection of

    critical section. See one node's rank can be easily calculated by adding its next node's rank to itself provided

    that its next node is not writing its rank. That is to say, you must make sure that adding rank of your next node

    would not be concurrent with changing the position of your next node. Then the rank you are adding is sure the

    correct one. Using a simple lock to ensure it.

    D.The major functions

    E.Further improvement

    F.File listing

    1. main.cpp (main)

    file name: main.h

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

    using namespace std;

    const int MaxListNode=20;

    struct Node
    {
    	int rank;
    	int index;
    	Node* next;
    };

    Node nodes[MaxListNode];
    bool added[MaxListNode]={false};

    Node* head=NULL, *tail=NULL;

    HANDLE worker[MaxListNode];

    void initialize();

    void addNode(int index);

    void printList();

    DWORD WINAPI run(void* param);

    HANDLE mutex;
    int counter=0;

    int demon[MaxListNode];

    void interrupt(int index);

    int main()
    {
    	srand(time(0));
    	initialize();
    	printList();
    	for (int i=0; i<MaxListNode; i++)
    	{
    		ResumeThread(worker[i]);
    	}
    	while (counter<MaxListNode)
    	{
    		Sleep(0);
    	}
    	cout<<"now print the result\n";
    	for (i=0; i<MaxListNode; i++)
    	{
    		cout<<"index:"<<nodes[i].index<<", randk:"<<nodes[i].rank<<endl;
    	}

    	return 0;
    }

    void printList()
    {
    	Node* ptr=head;
    	while (ptr!=NULL)
    	{
    		cout<<"index:"<<ptr->index<<", rank:"<<ptr->rank<<"\n";
    		ptr=ptr->next;
    	}
    }

    void addNode(int index)
    {
    	if (head==NULL)
    	{
    		head=tail=&nodes[index];
    	}
    	else
    	{
    		tail->next=&nodes[index];
    		tail=&nodes[index];
    	}
    }

    void initialize()
    {
    	int count=0, index;
    	for (int i=0; i<MaxListNode; i++)
    	{
    		nodes[i].index=i;
    		nodes[i].rank=1;
    		nodes[i].next=NULL;
    		demon[i]=rand()%10;
    		worker[i]=CreateThread(NULL, 0, run, (void*)&nodes[i], CREATE_SUSPENDED , NULL);
    	}
    	while (count<MaxListNode)
    	{
    		index=rand()%MaxListNode;
    		if (added[index])
    		{
    			continue;
    		}
    		added[index]=true;
    		addNode(index);
    		count++;
    	}
    	mutex=CreateMutex(NULL, false, NULL);

    }

    bool acquire(Node* ptr)
    {
    	WaitForSingleObject(mutex, INFINITE);
    	if (ptr==NULL)
    	{
    		ReleaseMutex(mutex);
    		return true;
    	}
    	int index=ptr->index;
    	if (added[index])//means old
    	{
    		added[index]=false;
    		ReleaseMutex(mutex);
    		return true;
    	}
    	//means it is locked: false
    	ReleaseMutex(mutex);
    	return false;
    }

    void release(Node* ptr)
    {
    	WaitForSingleObject(mutex, INFINITE);
    	if (ptr!=NULL)
    	{
    		added[ptr->index]=true;
    	}
    	ReleaseMutex(mutex);
    }

    void interrupt(int index)
    {
    	if (demon[index]<4)
    	{
    		Sleep(0);
    	}
    }

    DWORD WINAPI run(void* param)
    {
    	while (true)
    	{
    		if (acquire((Node*)param))
    		{
    			//WaitForSingleObject(mutex, INFINITE);
    			interrupt(((Node*)param)->index);
    			Node* ptr=((Node*)param)->next;
    			interrupt(((Node*)param)->index);
    			if (acquire(ptr))
    			{
    				interrupt(((Node*)param)->index);
    				if (ptr==NULL)
    				{
    					counter++;
    					release(ptr);
    					release((Node*)param);
    					break;
    				}
    				else
    				{
    					((Node*)param)->rank+=ptr->rank;
    					((Node*)param)->next=ptr->next;

    				}
    				interrupt(((Node*)param)->index);
    				release(ptr);
    			}
    			interrupt(((Node*)param)->index);
    			release((Node*)param);
    		}
    		Sleep(0);
    	}
    	return 0;
    }

    กก

    The input is something like following:

    Here is the result:

    index:16, rank:1
    index:11, rank:1
    index:7, rank:1
    index:12, rank:1
    index:6, rank:1
    index:13, rank:1
    index:14, rank:1
    index:8, rank:1
    index:1, rank:1
    index:17, rank:1
    index:10, rank:1
    index:2, rank:1
    index:18, rank:1
    index:0, rank:1
    index:15, rank:1
    index:5, rank:1
    index:9, rank:1
    index:19, rank:1
    index:3, rank:1
    index:4, rank:1
    now print the result
    index:0, randk:7
    index:1, randk:12
    index:2, randk:9
    index:3, randk:2
    index:4, randk:1
    index:5, randk:5
    index:6, randk:16
    index:7, randk:18
    index:8, randk:13
    index:9, randk:4
    index:10, randk:10
    index:11, randk:19
    index:12, randk:17
    index:13, randk:15
    index:14, randk:14
    index:15, randk:6
    index:16, randk:20
    index:17, randk:11
    index:18, randk:8
    index:19, randk:3
    Press any key to continue