UNIX Socket FAQ

A forum for questions and answers about network programming on Linux and all other Unix-like systems

You are not logged in.

#1 2006-11-28 04:51 PM

yurec
Member
From: Singapore
Registered: 2006-11-16
Posts: 134

Re: shared list without synchonization?

Hi
I want to use some container to implement communication between processes(producer/consumer) .I think I need list.I've read I can insert to the end of it without synchronization.

Inserting an element into a shared linked list is never atomic since it consists of at
least two pointer assignments. Nevertheless, the kernel can sometimes perform this
insertion operation without using locks or disabling interrupts. As an example of why
this works, we'll consider the case where a system call service routine (see Section
9.2) inserts new elements in a simply linked list, while an interrupt handler or
deferrable function asynchronously looks up the list.
In the C language, insertion is implemented by means of the following pointer
assignments:
new->next = list_element->next;
list_element->next = new;
In assembly language, insertion reduces to two consecutive atomic instructions. The
first instruction sets up the next pointer of the new element, but it does not modify
the list. Thus, if the interrupt handler sees the list between the execution of the first
and second instructions, it sees the list without the new element. If the handler sees
the list after the execution of the second instruction, it sees the list with the new
element. The important point is that in either case, the list is consistent and in an
uncorrupted state. However, this integrity is assured only if the interrupt handler
does not modify the list. If it does, the next pointer that was just set within the new
element might become invalid.
However, developers must ensure that the order of the two assignment operations
cannot be subverted by the compiler or the CPU's control unit; otherwise, if the
system call service routine is interrupted by the interrupt handler between the two
assignments, the handler finds a corrupted list. Therefore, a write memory barrier
primitive is required:
new->next = list_element->next;
wmb( );
list_element->next = new;
(c)
OReilly "Understanding the linux kernel"
I think if i can make (last_elem)->prev->next=null atomically i can also make erasing last element without sinchroniztion.But I have never seen such decision,so I think i'm wrong.But where? )

Offline

#2 2006-11-28 05:15 PM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,239

Re: shared list without synchonization?

Please stop quoting big pieces of text without a proper reference. Give an url or title+page number or at least the author.

It's possible to make a fully atomic linked list, but you need some atomic compare and swap instruction, and it must be a single linked list. But I won't recommend doing it though. Better to use something simpler if you can. But if you only have on process adding new elements and only one process removing elements it's much simpler. It depends on your application design and goals what is best to do. But using simple locking (mutexes or semaphores) is safest and avoids assembly stuff and headaches.

Offline

#3 2006-11-29 08:20 AM

yurec
Member
From: Singapore
Registered: 2006-11-16
Posts: 134

Re: shared list without synchonization?

I'll have some threads of one process adding new elements and some threads of another process removing.Also I need neither swap nor compare methods for that list class.That would be thousands of elements(each with size 1-2kb) added in a second.Maximum size of shared segment is 4mb.But I have to process this messages fast, even if I have no problems with size of memoryy shared.So I'm not sure I can use semaphores.Beside I have time to learn how to  use assembles stuff and to have a headache.

Offline

#4 2006-11-29 01:28 PM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,239

Re: shared list without synchonization?

First use simple mutexes, and if that turns out to be too slow you can always upgrade it (best to start adding finer grained locks, instead of going the atomic way though). Key point is that it's much easier to get working, and when you do try the hard way and it goes wrong, you know it's the new code that did it.

Offline

#5 2006-11-29 02:55 PM

yurec
Member
From: Singapore
Registered: 2006-11-16
Posts: 134

Re: shared list without synchonization?

Offline

#6 2006-11-29 03:43 PM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,239

Re: shared list without synchonization?

Oh, you're using multiple processes, sorry. I'm not sure if your pthread implementation supports shared memory mutexes, I wouldn't count on it. To be save just use sysv semaphores.

Offline

Board footer

Powered by FluxBB