Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In the early days of FORTRAN and BASIC, essentially all programs were written with GOTO statements. The result was spaghetti code and the solution was structured programming.

Similarly, pointers can have difficult to control characteristics in our programs. C++ started with plenty of pointers, but use of references are recommended. Libraries like STL can reduce some of our dependency. There are also idioms to create smart pointers that have better characteristics, and some version of C++ permit references and managed code.

Programming practices like inheritance and polymorphism use a lot of pointers behind the scenes (just as for, while, do structured programming generates code filled with branch instructions). Languages like Java eliminate pointers and use garbage collection to manage dynamically allocated data instead of depending on programmers to match all their new and delete statements.

In my reading, I have seen examples of multi-process and multi-thread programming that don't seem to use semaphores. Do they use the same thing with different names or do they have new ways of structuring protection of resources from concurrent use?

For example, a specific example of a system for multithread programming with multicore processors is OpenMP. It represents a critical region as follows, without the use of semaphores, which seem not to be included in the environment.

th_id = omp_get_thread_num();
#pragma omp critical
{
  cout << "Hello World from thread " << th_id << '\n';
}

This example is an excerpt from: http://en.wikipedia.org/wiki/OpenMP

Alternatively, similar protection of threads from each other using semaphores with functions wait() and signal() might look like this:

wait(sem);
th_id = get_thread_num();
cout << "Hello World from thread " << th_id << '\n';
signal(sem);

In this example, things are pretty simple, and just a simple review is enough to show the wait() and signal() calls are matched and even with a lot of concurrency, thread safety is provided. But other algorithms are more complicated and use multiple semaphores (both binary and counting) spread across multiple functions with complex conditions that can be called by many threads. The consequences of creating deadlock or failing to make things thread safe can be hard to manage.

Do these systems like OpenMP eliminate the problems with semaphores?
Do they move the problem somewhere else?
How do I transform my favorite semaphore using algorithm to not use semaphores anymore?

share|improve this question
    
What exactly are you talking about? What did you see? –  svick Aug 16 '12 at 17:50
3  
Not meaning to be rude, but you could have eliminated the first three paragraphs. They don't really bear on your question, and they over-reach on their conclusions and will just generate a lot of argument. –  dbracey Aug 16 '12 at 19:44
1  
Whoa, big edit. I've taken a stab at an answer. The question still kind of wanders around through GOTO, pointers, inheritance, and polymorphism, but in my answer I've set these issues aside and have focused on the "deprecated practices" question. –  Stuart Marks Aug 18 '12 at 22:07

7 Answers 7

up vote 12 down vote accepted
+50

Are there concurrent programming techniques and practices that one should no longer use? I'd say yes.

One early concurrent programming technique that seems rare nowadays is interrupt-driven programming. This is how UNIX worked in the 1970s. See the Lions Commentary on UNIX or Bach's Design of the UNIX Operating System. Briefly, the technique is to suspend interrupts temporarily while manipulating a data structure, and then to restore interrupts afterward. The BSD spl(9) man page has an example of this style of coding. Note that the interrupts are hardware-oriented, and the code embodies an implicit relationship between the kind of hardware interrupt and the data structures associated with that hardware. For example, code that manipulates disk I/O buffers needs to suspend interrupts from disk controller hardware while working with those buffers.

This style of programming was employed by operating systems on uniprocessor hardware. It was much rarer for applications to deal with interrupts. Some OSes had software interrupts, and I think people tried to build threading or coroutine systems on top of them, but this wasn't very widespread. (Certainly not in the UNIX world.) I suspect that interrupt-style programming is confined today to small embedded systems or real-time systems.

Semaphores are an advance over interrupts because they are software constructs (not related to hardware), they provide abstractions over hardware facilities, and they enable multithreading and multiprocessing. The main problem is that they are unstructured. The programmer is responsible for maintaining the relationship between each semaphore and the data structures it protects, globally across the entire program. For this reason I think bare semaphores are rarely used today.

Another small step forward is a monitor, which encapsulates concurrency control mechanisms (locks and conditions) with the data being protected. This was carried over into the Mesa (alternate link) system and from there into Java. (If you read this Mesa paper, you can see that Java's monitor locks and conditions are copied almost verbatim from Mesa.) Monitors are helpful in that a sufficiently careful and diligent programmer can write concurrent programs safely using only local reasoning about the code and data within the monitor.

There are additional library constructs, such as those in Java's java.util.concurrent package, which includes a variety of highly concurrent data structures and thread pooling constructs. These can be combined with additional techniques such as thread confinement and effective immutability. See Java Concurrency In Practice by Goetz et. al. for further discussion. Unfortunately, many programmers are still rolling their own data structures with locks and conditions, when they really ought to just be using something like ConcurrentHashMap where the heavy lifting has already been done by the library authors.

Everything above shares some significant characteristics: they have multiple threads of control that interact over globally shared, mutable state. The problem is that programming in this style is still highly error-prone. It's quite easy for a small mistake to go unnoticed, resulting in misbehavior that is hard to reproduce and diagnose. It may be that no programmer is "sufficiently careful and diligent" to develop large systems in this fashion. At least, very few are. So, I'd say that multi-threaded programming with shared, mutable state should be avoided if at all possible.

Unfortunately it's not entirely clear whether it can be avoided in all cases. A lot of programming is still done in this fashion. It would be nice to see this supplanted by something else. Answers from Jarrod Roberson and davidk01 point to techniques such as immutable data, functional programming, STM, and message-passing. There is much to recommend them, and all are being actively developed. But I don't think they've fully replaced good old-fashioned shared mutable state just yet.

EDIT: here's my response to the specific questions at the end.

I don't know much about OpenMP. My impression is that it can be very effective for highly parallel problems such as numeric simulations. But it doesn't seem general-purpose. The semaphore constructs seem pretty low-level and require the programmer to maintain the relationship between semaphores and shared data structures, with all the problems I described above.

If you have a parallel algorithm that uses semaphores, I don't know of any general techniques to transform it. You might be able to refactor it into objects and then build some abstractions around it. But if you want to use something like message-passing, I think you really need to reconceptualize the entire problem.

share|improve this answer
    
Thanks, this is great information. I will look through the references and dive deeper in the concepts you mention that are new to me. –  DeveloperDon Aug 19 '12 at 5:32
    
+1 for java.util.concurrent and agreed on the comment - it's been in the JDK since 1.5 and I rarely if ever see it used. –  MebAlone Sep 20 '12 at 19:35
    
I wish you highlighted how important it is to not roll your own structures when ones already exist. So many, so many bugs... –  corsiKa Jun 17 at 14:40

The latest rage in academic circles seems to be Software Transactional Memory (STM) and it promises to take all the hairy details of multi-threaded programming out of the hands of the programmers by using sufficiently smart compiler technology. Behind the scenes it is still locks and semaphores but you as the programmer don't have to worry about it. The benefits of that approach are still not clear and there are no obvious contenders.

Erlang uses message passing and agents for concurrency and that is a simpler model to work with than STM. With message passing you have absolutely no locks and semaphores to worry about because each agent operates in its own mini universe so there are no data related race conditions. You still have some weird edge cases but they are nowhere near as complicated as livelocks and deadlocks. JVM languages can make use of Akka and get all the benefits of message passing and actors but unlike Erlang the JVM does not have built-in support for actors so at the end of the day Akka still makes use of threads and locks but you as the programmer don't have to worry about it.

The other model I'm aware of that doesn't use locks and threads is by using futures which is really just another form of async programming.

I'm not sure how much of this technology is available in C++ but chances are if you are seeing something that is not explicitly using threads and locks then it will be one of the above techniques for managing concurrency.

share|improve this answer
    
+1 for the new term "hairy details". LOL man. I just can't stop laughing at this new term. I guess I'm gonna use "hairy code" from now on. –  Saeed Neamati Aug 16 '12 at 6:48
1  
@Saeed: I've heard that expression before, it's not that uncommon. I agree it's funny though :-) –  Cameron Aug 16 '12 at 18:58
1  
Good answer. The .NET CLI supposedly also has support for signaling (as opposed to locking) but I have yet to come across an example where it completely replaced locking. I'm not sure if async counts. If you're talking about platforms like Javascript/NodeJs, they're actually single-threaded and only better at high IO loads because they are much less susceptible to maxing resource limits (ie on a ton of throwaway contexts). On CPU intensive loads there's little/no benefit to using async programming. –  Evan Plaice Aug 16 '12 at 20:37
1  
Interesting answer, I hadn't come across futures before. Also note that you can still have deadlock and livelock in message passing systems like Erlang. CSP allows you to formally reason about deadlock and livelock but it doesn't prevent it by itself. –  Mark Booth Aug 20 '12 at 9:19
1  
I would add Lock free and wait free data structures to that list. –  stonemetal Aug 20 '12 at 17:54

Answer to the Question

The general consensus is shared mutable state is Bad™, and immutable state is Good™, which is proven to be accurate and true again and again by functional languages and imperative languages as well.

The problem is mainstream imperative languages are just not designed to handle this way of working, things aren't going to change for those languages over night. This is where the comparison to GOTO is flawed. Immutable state and message passing is a great solution but it isn't a panacea either.

Flawed Premise

This question is based on comparisons to a flawed premise; that GOTO was the actual problem and was universally deprecated some how by the Intergalatic Universal Board of Language Designers and Software Engineering Unions©! Without a GOTO mechanism ASM wouldn't work at all. Same with the premise that raw pointers are the problem with C or C++ and some how smart pointers are a panacea, they aren't.

GOTO wasn't the problem, programmers were the problem. Same goes for shared mutable state. It in and of itself isn't the problem, it is the programmers using it that is the problem. If there was a way to generate code that used shared mutable state in a way that never had any race conditions or bugs, then it would not be an issue. Much like if you never write spaghetti code with GOTO or equivilent constructs it isn't an issue either.

Education is the Panacea

Idiot programmers are what were deprecated, every popular language still has the GOTO construct either directly or indirectly and it is a best practice when properly used in every language that has this type of constructs.

EXAMPLE: Java has labels and try/catch/finally both of which directly work as GOTO statements.

Most Java programmers that I talk to don't even know what immutable actually means outside them repeating the String class is immutable with a zombie like look in their eyes. They definitely don't know how to use the final keyword properly to create an immutable class. So I am pretty sure they have no idea why messaging passing using immutable messages is so great and why shared mutable state is so not great.

share|improve this answer
2  
+1 Great answer, clearly written and pinpointing the underlying pattern of mutable state. IUBLDSEU should become a meme :) –  Dibbeke Aug 16 '12 at 7:28
2  
GOTO is a codeword for 'please, no really please start a flame war here, I double dog dare you'. This question pots out the flames but doesn't really give a good answer. Honorable mentions of functional programming and immutability are great but there's no meat to those statements. –  Evan Plaice Aug 16 '12 at 20:28
1  
This seems to be a contradicting answer. First, you say "A is Bad, B is Good", then you say "Idiots were deprecated". Doesn't the same thing apply to the first paragraph? Can't I just take that last part of your answer and say "Shared mutable state is a best practice when properly used in every language". Also, "proof" is a very strong word. You shouldn't use it unless you have really strong evidence. –  luiscubal Aug 18 '12 at 23:00
2  
It was not my intention to start a flame war. Until Jarrod reacted to my comment, had thought that GOTO was non-controversial and would work well in an analogy. When I wrote the question, it didn't occur to me, but Dijkstra was at ground zero on both GOTOs and semaphores. Edsger Dijkstra seems like a giant to me, and was credited with the invention of semaphores (1965) and early (1968) scholarly work about GOTOs. Dijkstra's method of advocacy was often crusty and confrontational. Controversy/confrontation worked for him, but I just want ideas about possible alternatives to semaphores. –  DeveloperDon Aug 19 '12 at 6:40
1  
As a simple example, it would be helpful if parameters and local variables could be declared as being 'ephemeral' or 'returnable'. A routine would be allowed to dereference an ephemeral or returnable parameter, or pass it as ephemeral or returnable to other routines, but only store it to ephemeral or returnable variables, or (for returnable ones only) return it. A function return value would inherit the most restrictive attribute among the returnable parameters passed in. Such rules would allow references to unshared mutable objects to be passed safely to outside code. As it is... –  supercat Aug 24 '12 at 18:25

I think this is mostly about levels of abstraction. Quite often in programming, it is useful to abstract away some details in a way that is safer or more readable or something like that.

This applies to control structures: ifs, fors and even try-catch blocks are just abstractions over gotos. These abstractions are almost always useful, because they make your code more readable. But there are cases when you will still need to use goto (e.g. if you're writing assembly by hand).

This also applies to memory management: C++ smart pointers and GC are abstractions over raw pointers and manual memory de-/allocation. And sometimes, these abstractions are not appropriate, e.g. when you really need maximum performance.

And the same applies to multi-threading: things like futures and actors are just abstractions over threads, semaphors, mutexes and CAS instructions. Such abstractions can help you make your code much more readable and they also help you avoid errors. But sometimes, they are simply not appropriate.

You should know what tools you have available and what are their advantages and disadvantages. Then you can choose the correct abstraction for your task (if any). Higher levels of abstraction don't deprecate lower levels, there will be always some cases where the abstraction is not appropriate and the best choice is to use the “old way”.

share|improve this answer
    
Thanks, you are catching the analogy, and I don't have a preconceived idea or even ax to grind as to whether the answer WRT semaphores is that they are or are not deprecated. The bigger questions for me is are there better ways and in systems that don't seem to have semaphores missing something important and would they be unable to do the full range of multithread algorithms. –  DeveloperDon Aug 19 '12 at 5:26

Yes, but you're not likely to run into some of them.

In the old days, it was common to use blocking methods (barrier synchronization) because writing good mutexes was hard to do right. You can still see traces of this in things as recent Using modern concurrency libraries gives you a much richer, and thoroughly-tested, set of tools for parallelization and inter-process coordination.

Likewise, an older practice was to write torturous code such that you could figure out how to parallelize it manually. This form of (potentially harmful, if you get it wrong) optimization has also largely gone out the window with the advent of compilers that do this for you, unwinding loops if necessary, predictively following branches, etc. This is not new technology, however, being at least 15 years on the market. Taking advantage of things like thread pools also circumvents some really tricksy code of yesteryear.

So perhaps the deprecated practice is writing concurrency code yourself, instead of using modern, well-tested libraries.

share|improve this answer
    
Thanks. It seems like there is great potential for use of concurrent programming, but it could be a Pandora's box if not used in a disciplined way. –  DeveloperDon Aug 19 '12 at 5:53

One of the major changes to parallel programming is that CPUs are tremendously faster than before, but to achieve that performance, require a nicely filled cache. If you try to run several threads at the same time swapping between them continually, you're nearly always going to be invalidating cache for each thread (ie each thread requires different data to operate on) and you end up killing performance much more than you used to with slower CPUs.

This is one reason why async or task-based (eg Grand Central Dispatch, or Intel's TBB) frameworks are more popular, they run code 1 task at a time, getting it finished before moving to the next one - however, you must code each each task to take little time unless you want to screw the design (ie your parallel tasks are really queued). CPU-intensive tasks are passed to an alternative CPU core rather than processed on the single thread processing all the tasks. Its also easier to manage if there are no truly multi-threaded processing going on too.

share|improve this answer
    
Cool, thanks for references to Apple and Intel tech. Is your answer pointing out challenges of managing thread to core affinity? Some cache performance problems are eased because multicore processors may repeat L1 caches per core? For example: software.intel.com/en-us/articles/… High speed cache for four cores with more cache hits can be more than 4x as fast as one core with more cache misses on the same data. Matrix multiplication can. Random scheduling of 32 threads on 4 cores can't. Let's use affinity and get 32 cores. –  DeveloperDon Aug 20 '12 at 17:51
    
not really though its the same problem - core affinity just refers to the problem where a task is bounced from core to core. Its the same issue if a task is interrupted, replaced with a new one, then the original task continues on the same core. Intel's saying there: cache hits = fast, cache misses = slow, regardless of the number of cores. I think they're trying to persuade you to buy their chips rather than AMDs :) –  gbjbaanb Aug 20 '12 at 18:01

Apple's Grand Central Dispatch is an elegant abstraction that changed my thinking about concurrency. Its focus on queues make implementing asynchronous logic an order of magnitude simpler, in my humble experience.

When I program in environments where it's available, it had replaced most of my usages of threads, locks, and inter-thread communication.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.