captain holly java blog

Concurrency. Where are we and how did we get here?

Posted in concurrency by mcgyver5 on June 1, 2009

Concurrency allows multiple parts a program to execute at the same time. Non-concurrent, program statements run one after another. Concurrency allows them to run in parallel, using system resources more efficiently.

Concurrency introduces indeterminate behavior when computer code executes. Essentially, randomness in outcomes is introduced by the hardware.

Concurrency also introduces situations where resources are requested at the same time by two different threads. If the resources are not managed appropriately, the resources or the threads themselves can become unavailable.

Concurrency is an illusion. At the processor level, only one task at a time can be performed. The ability of the processor to switch between tasks fast enough provides an illusion of concurrency. With multiple processors, this is still true because many more tasks can run than the number of processors. A language is “concurrent” to the extent that it can safely take advantage of this context switching.

History


As computers got fast enough to support virtual memory and fast context switching, it became possible for multiple users to use the same computer system and have the illusion they were the only ones on the system. An individual user still had to do sequential computing. One computation had to wait for another to finish before it could start.

The next leap in technology allowed one user to use concurrent computing so that one long computation could run at the same time as one or more others that didn’t depend on the outcome of the long computation. For example, printing the first page of a graph while the second page was still being processed would save time. An early language that made this possible was Algo68.

A problem that must be solved by all concurrent systems is how to allow simultaneous computations to access the same resources. This problem was described by The Dining Philosopher’s problem in which a group of philosophers sit down to eat a meal which requires two forks (or, in some versions, chopsticks). Each philosopher has one fork and must wait for another to put down theirs so they can eat. This can result in a stalled, or deadlocked, program if each philosopher picks up their fork at the same time and waits for someone else to put theirs down. Once the deadlock problem is solved, the program must be sure that none of the philosphers starves to death. This means that although the program never locks up, it may happen that one of the philosophers never gets a chance to eat.

Various conventions have been used in languages to implement concurrency

  • Shared Resource Annotation. Annotations abstracted the gory details of concurency so that they remained hidden from the programmer. A notation simply identified a resource as shared when first instantiated. Early implementations, however, did not ensure that the same resource could be declared somewhere else and not identified as shared.
  • Messaging. This would be analogous to the philosophers simply talking to one another. In the Erlang language, for example, concurrent processes never share the same memory. They can, however monitor each other and communicate.
  • Monitors are objects that govern resources that might be accessed by concurrent computations. Monitors ensure that only one thread at a time can operate on the resource they govern. They also establish a queue that governs which thread has next access to the resource. In some languages, the resources themselves can be made into monitors. In others, monitors area seperate object that controls access to a resource. In 1974, C.A.R Hoare wrote a famous paper outlining the use of monitors in a
    concurrent operating system. Read the paper here.

mile posts along the way to concurrency:

  1. Assembly. Concurrency was known as “multiprogramming” and was implemented in Assembly. People went insane trying to maintain large concurrent systems written in assembly.
  2. Semaphores. semaphores are flags indicating “yes” the resource is in use and “no” it is free. The “occupied” sign on a port-a-potty is a binary semaphore. PL/1 was the first language to use binary semaphores to protect “critical regions”.
  3. The THE operating system was a multi tasking operating system written in Assembly, but providing ALGOL as the sole programming language available. The ALGOL language “abstracted” the ugly details of concurrency from the programmer, who implemented concurrency through notations, starting the concepts of A) hiding implementation details from people who did not need to see them, and B), protecting resources by using a higher level language.
  4. Simula was the first language to group like resources into things called classes. This allowed a paradigm you will recognize from Java in which you can define protection levels for groupings of resources like private, public, default, protected. The problem with classes in Simula is that outside modules could access the variables of the classes themselves, bypassing the procedures meant to protect the resources. This is possible in Java only by doing something really crazy like using introspection.
  5. Concurrent Pascal In 1974, A man named Hansen developed Concurrent Pascal as the first generally used concurrent programing language. It was the first to use monitors.
    Concurrent Pascal implemented a set of features deemed “required ” by a true concurrent language. These are:

    • The compiler should make sure that all resources that can be accessed by more than one thread be protected by monitors
    • The language should be a high level language in which memory addresses, interrupts, and so on are hidden from the developer. So, things like assembly or C are out. It is possible in those languages to perhaps write a monitor, but it is also possible for some joker to write a program that invades the memory space of the resources you are trying to protect, as there is no way to enforce access control like there is in java with private, protected, and public modifiers
    • The language needs to be modular. When things are modularized, the entire module can be designated as shared or synchronized. In Concurrent Pascal, unlike Simula, variables could be protected. This was vital to concurrency as competing code segments cannot now access a single variable somewhere, (like reaching in a window to adjust a thermostat), they must walk in the front door with permission. A language called Simula had the concept of classes, which were groupings of resources.

    Monitors are a central part of Concurrent Pascal. A monitor is essentially a shared class with explicit queues. A shared class is simply one that has all of its fields private and all of its methods synchronized.

    Explicit Queue: In java, a “monitor” has one queue. When the state of the monitored object changes, all waiting threads are woken up and notified of the change. In a “true” monitor, we could have one queue for each possible state of the watched object so that threads waiting on one aspect of the object to change could all be in the same queue and wouldn’t get notified unless something of interest to them happened.

    Errors with shared resources or time-dependent operations must be detected during compilation. No amount of testing can tell for sure that a shared resource will or will not lock up / finish in a finite time. Thus, the compiler is used to detect whether shared resources are defined as such and that concurrency errors are handled.

  6. Mesa was a high level language developed by Xerox PARC in the late 1970s with strong concurrency and modularity. It was mainly used within Xerox as an experimental and teaching language. One of the requirements in Mesa was to be able to hatch new processes on the fly when they were needed. In earlier concurrent languages such as Algo68, the necessary processes had to be requested and rationed out in the declarations section of the program.
  7. Modula-2+ was a concurrent language that was used to develop operating systems at DEC, most notably the VAX.
  8. Erlang. Erlang was developed in the 1980s by the Erickson Corporation to run their phone switches. It was required to be massively concurrent and scalable. It was open sourced by Erickson and picked up by others including Erickson’s competitor Nortal and some web 2.0 applications such as Facebook chat. It uses the “Actor” model to achieve concurrency. Actors are lightweight processes. They wink in and out all the time like quantum particles and they chat with one another constantly and asynchronously. Reading about actors reminds me very much of web services.

    Actors never share state and thus never need to compete for locks for access to shared data. Instead, actors share data by sending messages that are immutable. Immutable data cannot be modified, so reads do not require a lock.

    link

  9. Java. With monitors established in academic circles as THE way to solve concurrency problems, Java came along with “Shared-state” concurrency and without a “true” monitor. With Shared state, concurrent computations live in the same memory space and it is up to the programmer to make them play nicely with one another.

    This all made P. Brinch Hansen write:

    Java’s most serious mistake was the decision to use the sequential part of the language to
    implement the run-time support for the parallel features.
    .
    In 1975, Concurrent Pascal demonstrated that platform-independent parallel programs (even
    small operating systems) can be written as a secure programming language with monitors. It
    is astounding to me that Java’s insecure parallelism is taken seriously by the programming
    language community a quarter of a century after the invention of monitors and Concurrent
    Pascal. It has no merit.

    link

    With java 5, Java has revamped their concurrency. It introduced a Monitor, deprecated thread methods like suspend() and stop() that enabled unsafe operations by one thread on other threads and could lead to deadlock, and now they have a Concurrency framework. It is still a “shared-state” solution, but with more tools to help the programmer make the threads play nicely together.
    It doesn’t quite meet the classic definition of proper concurrency because the compiler cannot detect errors, but it implements most other things. Here is a full discussion of the concessions java had to make with regards to concurrency and why they argue on Wikipedia that Java isn’t a truly concurrent language.
    straight from sun:

    Monitors provide greater security from system breakdown than Java does.
    Compilers for languages that support monitors can assure that all fields that can be accessed by more than one thread are protected by monitors. They can also assure mutual exclusion to those fields. They can check for the possibility of deadlock due to cycles in the graph of monitor calls. The implementation of these compilers can guarantee that a thread waiting for a condition will gain access to the monitor immediately, so the condition
    will still be true.

  10. Scala. Concurrency is now getting even more important because it is needed to take advantage of multi-core systems (systems with lots of CPU chips instead of just one). It may be that Java’s leap in concurrency is not enough or is too difficult to harness completely to take advantage of multi-core systems.

    So, bringing us up to the current day, Scala was developed by Martin Odersky to run on the Java Virtual Machine. Odersky also developed Generic Java, which was incorporated into Java 1.5. Among other “improvements”, Scala implements concurrency using the “actor” method as opposed to Java’s “shared-state”.

Tagged with: , ,