1

There is one thread and only one thread which will be writing/modifying a data structure. The data structure has one field which is a socket descriptor opened by the writing thread. Two other threads will be reading the data structure and will have to do something (like polling the socket(s) stored in the structure for input data).

One thread will read one global structure written by the writing thread while the other thread will read a second global structure. In essence, the two reading threads are not accessing the same global structure.

My question is, if the writing thread makes changes to the data structure which maybe adding more records in the data structure or deleting them, will the process crash? Is there any room for any kind of instance where a run-time crash can occur?

P.S. I'm using POSIX Threads working on a Linux environment

VSN
  • 386
  • 1
  • 2
  • 11

6 Answers6

1

Is there any room for any kind of instance where a run-time crash can occur

Short answer: most likely yes. You need to protect the data structure with some kind of locking. Pthread mutexes come to mind.

Longer answer: Think about a linked list. Think about adding an element or deleting one. Typically you need to modify more than one aspect of that list, for example you need to modify 2 pointers. Now ask yourself: what will happen if:

  • The writer thread starts changing some aspect of the list (like updating the next pointer) but isn't quite done before it gets interrupted
  • The reader thread tries to read from the list

EDIT

As Blagovest Buyukliev mentions in the comments, lock-free data structures usually provide more performance so you could investigate that route.

Community
  • 1
  • 1
cnicutar
  • 178,505
  • 25
  • 365
  • 392
  • I would like to avoid pthread mutexes. I have a mechanism where the writing thread would ask the reading thread to stop polling on a socket which is to be deleted. And there is no modification of a previous record. It is either addition or deletion of a record. – VSN Mar 16 '12 at 09:35
  • 1
    @VSN You mentioned Linux. Are you aware pthread mutexes on linx are [lightning fast](http://www.kernel.org/doc/man-pages/online/pages/man2/futex.2.html) ? – cnicutar Mar 16 '12 at 09:37
  • I did not know about futex :O Wouldn't that lock the whole data structure? – VSN Mar 16 '12 at 09:43
  • @cnicutar: while the trivial solution is to protect the data using locks, a more efficient approach would be to use atomic data types which allow for a lock-free implementation. The problem sounds like a good fit for a [lock-free linked list](http://www.liblfds.org/wikipedia/images/1/1d/Valois_-_Lock-Free_Linked_Lists_Using_Compare-and-Swap.pdf). – Blagovest Buyukliev Mar 16 '12 at 09:52
  • @BlagovestBuyukliev Sure :-) So why not do the trivial stuff upfront and then if after profiling you decide `pthread_mutex_lock` eats up a lot of time switch to lock free structures ? – cnicutar Mar 16 '12 at 09:54
  • Thanks for all the help! I'll look into all of these: futexes, lock-free linked lists... How do you guys find all of this stuff? :D – VSN Mar 16 '12 at 09:57
  • @cnicutar: I'm not suggesting that the OP should do it like this straight away, I'm just mentioning another possible solution that might be worth adding to your answer. – Blagovest Buyukliev Mar 16 '12 at 09:58
  • @BlagovestBuyukliev Agreed, added. – cnicutar Mar 16 '12 at 10:42
1

In general, the answer is yes, you can easily get crashes all over the place. For example, if one thread reads an element of a linked list while the other thread deletes it, you get undefined behavior (read: a crash).

The easiest thing is to use mutex, but if you are up for some advanced techniques and got access to compare and swap operation, you can implement a lock-free linked list, but you should first profile your application to see that the speed improvement is worth your effort.

Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
0

While this depends on the data structure, for most data structures the answer is: Sure.

Consider a variable-length vector as the easiest example. The writer thread removes an element by decrementing the element count and then doing some cleanup. The reader thread iterates over all elements. Now suppose the reader thread arrives with its loop at the last element, has compared the index to the element count and is about to access the element. Context switch happens, the writer thread pops the last element, decreases the element count and cleans up the element. Now the last element is invalid, context switch happens, the reader accesses an invalid element.

thiton
  • 35,651
  • 4
  • 70
  • 100
0

Sounds like you might be interested in pipes. Initialise the two pipes before writing/reading threads start and pass the writing thread both write ends of the pipes and the reading threads the reading end of their respective pipe. Wouldn't have to worry about synchronisation issues then.

In response to question about pipes being for inter-process communications. I made the recommendation to use pipes because you talked of using sockets. Sockets which are intended for inter-network communications. This post talks about the differences between pipes and sockets on the linux kernel. For local machine communications pipes beat sockets in terms of speed and efficiency as they have a much simpler implementation than sockets. And finally you'll get no threading issues with pipes as that is taken care of for you by the kernel.

Community
  • 1
  • 1
Dunes
  • 37,291
  • 7
  • 81
  • 97
  • Aren't pipes used between two processes or am I missing something here..? – VSN Mar 16 '12 at 09:55
  • Generally, yes. But in Linux pipes have a very efficient implementation. I've updated my answer, and provided a link to a brief comparison between pipes and sockets. – Dunes Mar 16 '12 at 12:51
0

Hmm.. you may be able to get away without locking, but you need to be careful :) Each element in the array/list/whatever container could have a state enum, maybe:

enum state {EstFree,EstInUse,EstDeletePending}

To add an entry, the writer thread iterates the array/list an uses the first entry with state 'EstFree'. If there is none, it creates another element and adds it on the end.

To 'delete' an 'EstInUse' entry, set its state to 'EdeletePending'. When the thread that uses this element notices the state change, it knows to stop polling, so it sets the state to 'EstFree' and exits.

Martin James
  • 24,453
  • 3
  • 36
  • 60
0

You need to avoid races as other said already. If you don't want to use a mutex to protect your data, modern C, C11, introduces atomic operations on the language level. Until this is more widely supported directly you can use compiler extension as for gcc and compatibles (clang, icc, opencc) or via macros that emulate the new interface.

Jens Gustedt
  • 76,821
  • 6
  • 102
  • 177