[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 237
  • Last Modified:

linked list in mulithread environment

Hi,

I'm having problems with putting items in, and getting them out, of a single linked list in a multithreaded program.

What happens is, that my program crashes when i try to write to the linked list very fast with more than one thread at the same time and in the same time i try to read from the list.

Here's what i do to read : (i get the first item in the list)

if (ListPtr)
{
   Item = ListPtr;
   ListPtr = Item->Next;
}

and to write to the list :

NewItem = malloc ...
NewItem->Next = NULL;

if (ListPtr)
{
   for (ItemPtr = ListPtr; ItemPtr->Next; ItemPtr = ItemPtr->Next);
   ItemPtr->Next = NewItem;
}
else ListPtr = NewItem;

My guess is : while doing those pointermanipulations, another thread is changing them so the result is an incorrect list.

-> Is there a way to tell the compiler that two or more functions must be preformed after each other, whitout excecuting code from other thread at the same time??

or is there another sollution for my problem?

0
940961sl
Asked:
940961sl
  • 5
  • 5
1 Solution
 
940961slAuthor Commented:
The environment is WINNT, sp5 using VC6.
0
 
jkrCommented:
You'll have to serialize the access to the list by protecting the list with a synchronization object, e.g.

CRITICAL_SECTION csListLock;

InitializeCriticalSection ( &csListLock);


EnterCriticalSection ( &csListLock);
if (ListPtr)
{
   Item = ListPtr;
   ListPtr = Item->Next;
}
LeaveCriticalSection ( &csListLock);


NewItem = malloc ...
NewItem->Next = NULL;

EnterCriticalSection ( &csListLock);
if (ListPtr)
{
   for (ItemPtr = ListPtr; ItemPtr->Next; ItemPtr = ItemPtr->Next);
   ItemPtr->Next = NewItem;
}
else ListPtr = NewItem;
LeaveCriticalSection ( &csListLock);
0
 
jkrCommented:
>>My guess is : while doing those pointermanipulations,
>>another thread is changing them so the result is an
>>incorrect list.

That's absolutely correct. Thus, protecting the list guarantess that this won't happen. Protecting hereby means that *every* access to the list has to be embraced with

EnterCriticalSection ( &csListLock);

// ...

LeaveCriticalSection ( &csListLock);

The above code using the sychronization is far from being complete, as

EnterCriticalSection ( &csListLock);

ListPtr = ?; // the initial assignement should also be protected!

if (ListPtr)
{
   Item = ListPtr;
   ListPtr = Item->Next;
}
LeaveCriticalSection ( &csListLock);


BTW: When you're done, don't forget to 'DeleteCriticalSection()' ;-)
0
Evaluating UTMs? Here's what you need to know!

Evaluating a UTM appliance and vendor can prove to be an overwhelming exercise.  How can you make sure that you're getting the security that your organization needs without breaking the bank? Check out our UTM Buyer's Guide for more information on what you should be looking for!

 
940961slAuthor Commented:
Sorry people, that didn't do it. any other idea's?

I'll try to write a smaller program, just with a few threads and the linked list, because the actual program is to big and uses some obj-files.

Tnx for helping me so far.
0
 
jkrCommented:
Could you post the entire code?
0
 
940961slAuthor Commented:
I can post you the entire code, but you will not be able to run it. It's using queues of shared memory that are initialised in another program, but if you think you have enough by just looking at it... i can send you the code, yes.
I can't send you the other program, it's to big, licensed and hard to install.
0
 
jkrCommented:
>>It's using queues of shared memory
>>that are initialised in another
>>program

This could also be a reason for your problem...
0
 
940961slAuthor Commented:
No, i don't think so ...

the queues are very havily tested and are running successfully for a few years now in al kinds of situations.

actually, this is what's going on :

1. the "client program" sends a send request.
2. the "server" sends the request to the linked list
3. the thread that handles the linked list get the request out of the list and sends a send reply to the client.
4. the client sends a new request.

-> this is synchronised but a receive request can put some things in the linked list also ...

right now, i don't beleave it's a matter of accessing the linked list at the same time anymore, because i disabled the read request, so the linked list can't be accessed by 2 theads at the same time.
Also, when i remove the linked list code, and just send a send reply every time i receive a send request, the program works fine, with threads and everything. So i beleave it can't be the queues.
The weird thing is, that everything works fine if I slow down the send requests, and i'm not able to trace the line that makes the program go down. It happens a little bit everywhere in the program.

So, I think it's time for the points :-)
your answer is probably correct, and i learned something new, so i guess this means an A, tnx a lot jkr.

0
 
940961slAuthor Commented:
I found the f**cking problem :-)
The items of the linked list where allocated and freed with the functions malloc and free. And there are 2 library's for those functions : LIBC (the single thread version) and LIBCMT (yes, the multithread version) Guess which one I was using ...

Thanks for helping jkr
0
 
jkrCommented:
Hmm, you should consider using a critical section, though...
0

Featured Post

Creating Active Directory Users from a Text File

If your organization has a need to mass-create AD user accounts, watch this video to see how its done without the need for scripting or other unnecessary complexities.

  • 5
  • 5
Tackle projects and never again get stuck behind a technical roadblock.
Join Now