35

Original transactions: Insert record $r$. Update some field $f$ of $r$. Forward undo: Delete record $r$. Reverse the update to $r$ - oh wait, $r$ no longer exists! This causes an error.


28

One of the roles of a multitasking operating system kernel is scheduling: determining which thread of execution to execute when. So such a kernel has some notion of thread or process. A thread is a sequential piece of code that is executing, and has its own stack and sometimes other data. In an operating system context, people usually use process to mean a ...


24

Your informal descriptions of the algorithms is wonderful. I think in both cases the author was trying to come up with the simplest solution they could think of that guaranteed both mutual exclusion and deadlock freedom. Neither algorithm is starvation free or fair.[ed: as pointed out in the comments, Peterson's algorithm is starvation free and fair]. ...


23

The term "true concurrency" arises in the theoretical study of concurrent and parallel computation. It is in contrast to interleaving concurrency. True concurrency is concurrency that cannot be reduced to interleaving. Concurrency is interleaved if at each step in the computation, only one atomic computing action (e.g. an exchange of messages between sender ...


21

In addition to Nish's answer, let me recommend Simon Marlow's book on Parallel and Concurrent Programming in Haskell or his shorter tutorial. They answer your first question from Haskell's perspective, so they could be better suited for theoretically inclined readers (Haskell is a purely functional, lazy programming language that is much closer to ...


20

Conurrency and parallelism differ in the problems they solve and cause, but they are not independent. Concurrency Executing two tasks concurrently means that individual steps of both tasks are executed in an interleaved fashion. If you disregard parallelism, you can assume that only one statement is executed at any point in time, but you have (a priori) no ...


17

Just to make sure we are on the same page, first let us consider these three definitions: Definition. Test-and-set is a read-modify-write instruction on some binary register (let's just say that 0 and 1 are possible values) where a thread obtains the old value and writes 1. Definition. Consensus is reached between $n$ threads iff all $n$ threads decide on ...


16

So, can stack-based programming languages be concurrent? Sure. Could they achieve concurrency by using multiple stacks at the same time or something alike? Already for normal languages multi-threading usually means having multiple "call" stacks. It would be completely natural to give each thread its own data stack. It would be straightforward to have an ...


13

Yes, you can implement mutual exclusion with only memory load and store instructions. There is a long tradition of devising successively simpler solutions to this problem. The earliest version that I know of, called "Dekker's solution", was introduced in Dijkstra, Edsger W.; "Cooperating sequential processes", in F. Genuys, ed., Programming Languages: NATO ...


12

Hopefully they didn't say explicitly say exactly "a program consisting only of atomics is race free in SC-DRF." That's incorrect. They do say that "[in] scoped synchronization ... it is possible to write a racey program that is composed entirely of atomics if those atomics do not use scopes correctly," [top of page 2], which is slightly different (and uses ...


11

To add to DylanSp's answer, trying to update a field in a non-existing record will fail, but the result will still be the expected result: record r does not exist. However, consider a situation where deletion of a record actually will fail: Insert Order O. Insert Orderline L. Let's assume, not unrealistically, that every OrderLine must be related to an ...


10

I've reread Herlihy and Wing many times over the past 15 years. It is a very difficult read. And that is unfortunate, because while there are some subtleties around the edges the basic idea is actually quite reasonable. In short: linearizability is like serializability, but with the additional requirement that the serialization respect additional ordering ...


10

choosing[i] is true while number[i] is being updated to be larger than all the other values in the number array — the new ticket value that the thread is taking. In the body of the for loop, the code first waits for choosing[j] to be false, which indicates that thread number j has chosen its ticket for this round. If thread j goes on executing while thread i ...


10

Sorry for the late reply, but I've just found the question (questions, indeed). I am studying concurrency as well and I'll try to share some ideas with you. First, let's start with sequential consistency. A model has this property if operations appear to take effect in program order. In other words, the order in which lines of code are executed is the one ...


9

You can easily profit from warfare that way: $$ M \stackrel{\mathrm{def}} = c.( d_{\text{tea}}.\bar e_{\text{tea}}.M + r.\bar b.M + c.( d_{\text{coffee}}.\bar e_{\text{coffee}}.M + r.\bar b.\bar b.M ) ) $$ note that you have to press refund to get a tea if you put too many coins. If you don't want that, you can ...


9

Proving that a program is "thread safe" is hard. It is possible, however, to concretely and formally define the term "data race." And it is possible to determine whether an execution trace of a specific run of a program does or does not have a data race in time proportional to the size of the trace. This type of analysis goes back at least to 1988: ...


8

I only know CSP and CCS/pi-calculus (not ACP). CSP was motivated by imperative programming processes communicating via messages. Hoare then tried to abstract away a simple calculus out of it. CCS, on the other hand, was an effort to create a foundational calculus like lambda calculus. Given their original starting points, and given their final form, I ...


8

Sounds like you are reading The Art of Multiprocessor Programming. "All function calls have a linearization point at some instant between their invocation and their response" Okay that's fine, they occur somewhere within a function call, but what are they? Side effects of the functions. http://en.wikipedia.org/wiki/Side_effect_(...


8

They are nearly interchangeable and one can be built out of the other. It is somewhat language dependent which is implemented/ preferred (eg Java has built-in monitors using "synchronize" keyword). However the semaphore is considered a "lower level" entity than the monitor for the following reasons & differences: Both Monitors and Semaphores are used ...


8

I know a bit about FORTH so I will confine myself to that. It is a low level language, giving you as programmer access to all the hardware resources. So you can do whatever you like. Concurrency In order to have parallell programs (edit: used to say real concurrent programs) you need at least two execution units (CPU-s). It would be rather trivial to ...


7

I think hybrid threading is very similar to a thread pool. In thread pool, you are using $N$ kernel threads to execute $M$ “tasks”, where $M$ can be much higher than $N$. The advantage over using one thread for each task (kernel only threading) is that you consume less resources, like memory (both virtual and physical) and kernel objects (at least in the ...


7

The point you are missing is that in thread $y$ is loaded into $r1$ and that any subsequent changes to $y$ will not affect the value stored in $r1$. Thus, the value in $r1$ is $0$ even after statement $y=1$. From this it is easy to see that the result is $x=2$.


7

Another partial answer. The approach to semantics taken by the various communities differed, at least originally. ACP semantics are axiomatic/algebraic. CSP semantics are denotational, generally in terms of traces. CCS/$\pi$-calculus semantics are operational, generally in terms of labelled transition systems. Of course, since the original semantics, ...


7

Overview Multi-threaded programs are more prone to errors than single-threaded programs because of the problem of concurrency bugs. Concurrency is hard for most developers to reason about, which causes many bugs in multi-threaded programs; this issue normally doesn't arise in single-threaded programs, because single-threaded programs typically have no ...


7

Jim Sawyer's answer points to one answer: When you have threads with differing priorities, "fair" behaviour would be incorrect. When you have multiple threads which could run, the highest priority thread is generally the one that should run. However, there's a little-discussed secret of operating system implementation which you should be aware of, which is ...


6

Answering (at least) the part of your question regarding why research has diverged instead of converged. Being no expert on process algebras, I was once wondering the exact same thing: why are there so many theories? I was pointed to a survey by Parrow: Expressiveness of Process Algebras, 2008. I think it is very nicely written and even a novice could ...


6

From the pratical side, there is a verification system VCC which can be used to formally prove thread safety of C programs. This is a citation from the web site: VCC supports concurrency -- you can use VCC to verify programs that use both coarse-grained and fine-grained concurrency. You can even use it to verify your concurrency control primitives. ...


6

Here is how I think Erlang works. I believe Akka is very similar. Each process has a single mailbox. Messages are put into the receiver's mailbox by the sender, and fetched by the receiver using pattern matching. This matching process can change message ordering in the sense that the oldest message in a mailbox may not match, but a younger one does. In this ...


6

Since you are asking on CS.SE rather than StackOverflow, I presume you are looking for a principled look at the fundamental underlying problem and principled solutions to the general problem, from a scientific/conceptual perspective (as opposed to a "quick hack" or a engineering solution that'll work for your specific situation). So, that's what I'll try to ...


Only top voted, non community-wiki answers of a minimum length are eligible