More Effective Use of Shared Memory on Linux

An anonymous reader writes "Making effective use of shared memory in high-level languages such as C++ is not straightforward, but it is possible to overcome the inherent difficulties. This article describes, and includes sample code for, two C++ design patterns that use shared memory on Linux in interesting ways and open the door for more efficient interprocess communication."

Comments

SysV IPC is obsolete

[bogolisk]

some1 should tell the authors to rtfm.

$ man shm_open

Re:SysV IPC is obsolete

[KiloByte]

The university, ~8 years ago, Concurrent Programming lab:

(talking about ftok)
Me: But, what is done to prevent clashes if different programs use the same key?
Prof: Nothing.
Me: Eh? That's fucking sabotage. (I used "cholerous", but that was in Polish)
Prof: And that's why we won't use SysV IPC in subsequent lessons.

The authors here use a static key of 0x1234...

Re:SysV IPC is obsolete

[maxwell demon]

The authors here use a static key of 0x1234...

Well, that should be a safe choice, because no sane person would use 0x1234, therefore this key is still unused. :-)

Re:SysV IPC is obsolete

[Anonymous Coward]

0x1234? Amazing! That's the combination on my luggage!

shmem (soon in Boost!)

[Cyberax]

There is a great C++ library for shared memory support: SHMEM. It can place complex objects and STL-like containers in shared memory. And it is crossplatform (POSIX and Windows are supported).

And it will soon (hopefully) be a part of Boost!

Re:shmem (soon in Boost!)

[maxwell demon]

It can place complex objects and STL-like containers in shared memory.

Depends on your definition of "complex objects".

From the documentation:

Virtuality forbidden

This is not an specific problem of Shmem, it is a problem for all shared memory object placing mechanisms. The virtual table pointer and the virtual table are in the address space of the process that constructs the object, so if we place a class with virtual function or inheritance, the virtual function pointer placed in shared memory will be invalid for other processes.

Basically, I would have been surprised if they had found a solution for that. But I guess it cannot be portably solved. Instead, the system would have to be prepared for it. I could imagine that objects in a shared library (so the same code is guaranteed to be shared to both processes) could be placed in shared memory, if the compiler/runtime system provided the means for it (say, instead of the pointer to a VMT, it would contain an offset into the constant data section of the shared library, and something to identify the library with, say a system-wide unique active library index which is generated by the dynamic linker).

Re:C++ has bigger memory issues

[ObsessiveMathsFreak]

In fact, forget it; just use an actual OO language instead.

C++ is an actual Object Oriented language, which is of course half the problem.

If you mean a pure OO language like Java, in which everything is an object except for primitives and it takes ten classes and wrappers just to read a file, well then C++ isn't exactly an Object Oriented language as such. Perhaps you mean Smalltalk or the like.

I tell you what though, C++ is still around after all this time. With all the hype surrounding Java, Perl, C#, Python, etc, etc, etc C++ programmers are still there beavering away with the god awful sytax Stroustrup left them with. Even after all the improvments, all the innovation and all the additional research into computer languages, for a hell of a lot of tasks, there is really no real alternative to C++.

I don't say this as a C++ fanboy, even though I am "somewhat" fond of the language when it is used properly, and not in garbled and unreadable line noise. I say this simply as a statement of fact. There is still no successor to C++.

I don't want garbage collection so much as I want a cleanup and rationalisation of the syntax. GC would be nice, but forcing more readable code would be even better.

const

[hey]

I suppose everything marked const could be shared.

This is nothing new

[Anonymous Coward]

You've been able to do this for a while using process shared mutexes and condition variables which allow you to do the same things you could do with pthreads and shared memory. The tradeoff is you get better performance avoiding syscalls to do IPC but it's less robust. If you get a segfault, you have to assume that the shared memory is in an unknown state and either shutdown or restart everything. The other processes can (or will be able) to detect this using once robust futex support is in Linux. Idiot programmers will of course ignore this and continue to use the corrupted memory anyway just like they do now with sysV semaphores used as mutexes with the SEM_UNDO option to allow the semaphore to auto reset if a process exits without resetting it.

Anyway, old stuff. Wake me up when you start talking about the newer tricks with shared memory.

CML

[putko]

For concurrent applications, it is hard to beat Reppy's CML.
http://portal.acm.org/citation.cfm?id=113470

In particular, the things you synchronize on are first-class. Also you can speculatively send/receive things. Normal "select" is only for reading. You don't have to manage your memory either.

There are other concurrent languages, but CML is nice in that it has a formal semantics, so unlike typical languages like "C", "C++", Erlang or Java, a program has a meaning other than "whatever the program does when I run it."

You can implement the primitives of CML in your favorite higher-order language, so you don't have to be limited by ML. That's what's in Reppy's book.

A proper implementation can achieve speeds that are about 30x faster than pthreads for typical tests like "ping/pong".

Hardware-enforced sharing: OLD HAT

[VernonNemitz]

Quite a few years ago, there was a brief popularity of something called VRAM (video ram) that had memory cells specifically designed with one input line and TWO output lines. The idea was that the part of the hardware needing to construct an image for the screen ONLY needed to read memory, while the system responsible for creating the image needed both read and write access. Ever since then, I've wondered why they don't use this kind of memory in multi-processor systems, for communication between processors, such that Processor A has read/write access to a block of VRAM, to give info to Processor B (it has read-access only), while Processor B has read/write access to a different block of VRAM, to give info to Processor A (it has read-access only).

Re:Hardware-enforced sharing: OLD HAT

[TheRaven64]

Because it's a really ugly hack that only works in a specific domain. If the frame buffer is being read and updated at the same time, you might get some screen corruption. This is irritating, but not really a problem. If a general piece of memory is being read from and written to at the same time, then the reading process gets garbage data. This means that you need to put locks around your memory (which you do anyway) to prevent this, which eliminates the advantage of the second read line.

Doors

[Anonymous Coward]

I'm surprised no-one has mentioned Solaris Doors. Doors is an IPC mechanism whereby the first process (client) can hand off any residual time in its timeslice to the second process (server) resulting in short IPC calls running much less time as there is no discarded timeslice time and no wait for the server process to be scheduled (since it uses the client's timeslice).

Re:C++ has bigger memory issues

[theCoder]

C++ already has a garbage collector. Just allocate your objects on the stack instead of the heap:

void foo()
{
  SomeObject obj;
 
// other code
 
// poof -- obj is deallocated automatically, even if an exception is thrown
}

I work on a project that has tens of thousands of C++ classes, and very few "new" and "delete" operations (more "new" than "delete" because we have a class that manages reference counting like a heap garbage collector would do).

People who think they always need to "new" objects in C++ have spent way too much time using Java.

Here's another hint -- pass objects to functions as const references:

void foo(const SomeObject& obj)
{
// code
}

This way, a copied object isn't allocated for the passing (no memory at all is in fact allocated). The biggest drawback is you can only call "const" methods on the object, but this is outweighed by not using pointers. Not that I don't like pointers, they just increase the complexity and should be used prudently. And as my .sig says, be sure to free those mallocs!

Re:10 fold speed improvement - Dekkers mutex ! fas

[Anonymous Coward]

Yes, some algorithms are worth remembering...

This one is worth remembering as one to avoid -- it's based on the idea of a busy-wait. Look at the while(test) { /* do nothing */ } loop and outer while loop. This should not be done. Semaphores might be slower in the specific case, but overall system performance will benefit from using best-practices.

There's a reason this algorithm lies in rest in academic journals: it's only useful as a teaching tool.

Re:10 fold speed improvement - Dekkers mutex ! fas

[Anonymous Coward]

IMHO this algorithm is not a panacea because :

- It does busy waiting. If one thread holds the 'mutex' for a long time, the other thread will take a lot of CPU for nothing.
If you really need to take the resource as soon as it is available without giving up the proc, then have a look at "spin locks".

- It is not very scalable.
First, you need one version of the algorithm for mono proc one for bi proc, etc. Of course you could put them all in a shared lib and select one at runtime.
Second, the algo seems to be O(N), N being the number of processors. Therefore the algo slows down when the number of proc increases.

- And last: it is unclear to me how you pass turn when there are more than 2 procs involved. Does this algorithm work when there is more than 2 processors ?

Re:10 fold speed improvement - Dekkers mutex ! fas

[at_18]

I tried unsuccessfully, verbally, to get a Phd in comp Sci with embedded management experience to believe me it is 100% sound.... argued for 40 minutes. The guy never had a clue.

The guy had a clue. Your algorithm is a busy-wait loop, so your CPUs will be maxed at 100% while waiting, and the thread will be pushed by the scheduler to lower priority, and so on...

And?

[ratboy666]

Ok, I get it... it's an attempt to exploit shared memory in C++.

And why is this news? Is it so difficult that nobody has done it? No, that can't be -- the shm stuff can be wrapped. This is so important that it rates a "design pattern"? Not it either -- the one illustrated isn't the best solution.

So, just what is this article? Methinks fluff. Sort of in line with "How to implement co-routines with setjmp/longjmp" thing. Or, "Restructuring data to assist processor cache residency". And "How to remove locks from performance critical MP code".

Except not as interesting or useful.

Ratboy.

There are better ways

[photon317]

A lot of shared memory synchronization and/or caching problems can be solved on Linux through the effective use of a few simple things:

1) shm_open (if seperately-started processes which need to coordinate in shared memory), or mmap(MAP_SHARED|MAP_ANONYMOUS) for a process which will fork children which need to communicate/share between themselves and the parent.

2) Use 's "atomic_t" integer type within that shared memory array (atomic_t* my_shm_array = mmap(....)). The atomic_t type has several functions defined in that header for atomic read, write, increment, etc for the linux hardware platform at hand. On most sane (cache-coherent) SMP architectures, reading and writing are already atomic operations, so this basically devolves to just setting and getting integers like normal (with a little bit of syntactic sugar (struct { volatile int val }) to make sure the C compiler doesn't optimize things away that it shouldn't. And you can implement a whole lot of sane algorithms using nothing but shared memory integer reads and writes with no locking or special atomic increment ops.

3) If you need more advanced or complex locking on the shared memory for synchronization, use Linux's "futex"'s. They're in the man pages, and they're really fast.

yeah, fast, and 10-fold chance of odd failures

[Krischi]

Yeah, this algorithm is fast. Too bad that it does not work. This kind of design is a common mistake by people who do not understand the intricacies of multithreaded programming. In short, it fails miserably when the CPUs are allowed to reorder loads and stores, a.k.a. pretty much any modern CPU. You need a memory barrier between setting and testing of a shared variable.

Google for Dekker's algorithm and memory barrier - you will find better explanations of the problem there than I could type up in my limited time here right now.

Preying on the non-comp SCI mods, I see.

[Inoshiro]

"How many people know about this? Nobody! I never read about it anywhere. I invented it myself years ago, .."

Turn to page 55 of your OS design and implementation by Tanenbaum. See where he says, "For a discussion of Dekker's algorithm, see Dijkstra (1965)."? How do you get through a proper comp sci honours degree to the point where you can take a masters and then a PhD without reading Dijkstra?

How about you crack open that copy of Operating Systems (4th ed) by William Stallings, which has a discussion of concurrency and Dekker's on pages 208-213? How can you get past a 2nd/3rd-year introductory operating systems class without having gone over this topic?

You are a troll. A troll preying on the fact that most of the moderators here have no idea about computer science, and have not taken a wiff of a real operatings systems class.

For the record, Peterson's algorithm (published in 1981) is a much simpler solution to your problem. It's on page 56 of the Tanenbaum book, and also discussed in Stallings on page 213. There's a new 5th edition of the Stallings book, but the index will take you to the correct chapter/page in short order.

Re:C++ has bigger memory issues

[kbw]

C++ is more than just an OO language. It provides direct support for the procedural paradigm too.

STL, for example, is not an OO library. Yet it has proved to be immensly useful.

One place where the garbage collected languages fall down is in the management of resources. The handling of limited resources such as files or sockets must be explicitly released by the programmer. This demonstrates that you simply cannot ignore the lifetime of objects with a garbage collector. And I also assert here that memory is a limited resource too.

That silly singleton thing in the example is a demonstration of the disregard for the lifetime of that particular object. Does it really need to live for the lifetime of the application? Does it need to be cleanly released?

I think C++'s memory management model is sufficient. One can hardly say that about garbage collected languages.

This is a mediocre way to get IPC.

[Animats]

For historical reasons, most of the UNIX-like operating systems have terrible interprocess communication mechanisms. Early UNIX only had pipes. This started a tradition that interprocess communication works like I/O, leading to named pipes, sockets, and domain sockets. The result is a set of rather slow interprocess communication mechanisms. (One can do worse. In the old MacOS, interprocess communication could only pass one message per vertical refresh time, and this wasn't documented.)

On top of those mechanisms, even slower interprocess communication systems are typically implemented, such as OpenRPC and CORBA. (For even more inefficiency, there's XPC. In Perl. But I digress.)

Because of this history, there's a perception that interprocess communication has to be slow. It doesn't.

What you really want looks more like what QNX has - fast interprocess messaging that interacts properly with the scheduler. QNX has to have interprocess communication done right, because it does everything through it, including all I/O. This works out quite well. You take a performance hit (maybe 20% for this), but you get much of that back because the higher levels become more efficient when built on good IPC.

The QNX messaging primitives are available for Linux, although the implementation isn't good enough for inclusion in the standard kernel. That work should be redone for the current kernel.

IPC/scheduler interaction really matters. If you get it wrong, each interprocess transaction results in an extra pass through the scheduler, or worse, both the sending process and the receiving process lose their turn at the CPU. This is easy to test. Start up two processes that communicate using your IPC mechanism. Measure the performance. Then start up a compute-bound process and measure again. If the IPC rate drops by much more than a factor of 2, something is wrong. Don't be surprised if it drops by two orders of magnitude. That's an indication that IPC/scheduler interaction was botched.

Sun addressed this in the mid-1990s with their "Doors" interface in Solaris, which had roughly the right primitives. But that idea never caught on.

The article here implements a message-passing system via shared memory, which is not exactly a new idea, even for UNIX. I think it first appeared in MERT, in the 1970s. It's an attempt to solve at the user level something that the OS should be doing for you.

Shared memory is a hack. It's hard to make it work right. With it, one process can crash other processes in hard-to-debug ways. Sometimes you need it because you're moving vast amounts of data, (by which I mean more than just a video stream) but that's rarely the case.