• C

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?

LVL 1
940961slAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
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
Choose an Exciting Career in Cybersecurity

Help prevent cyber-threats and provide solutions to safeguard our global digital economy. Earn your MS in Cybersecurity. WGU’s MSCSIA degree program was designed in collaboration with national intelligence organizations and IT industry leaders.

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
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.