36

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.


26

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, both algorithms are starvation free, and Peterson's ...


24

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 ...


21

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 ...


17

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

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 ...


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

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 ...


11

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

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: ...


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 ...


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 ...


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

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

Let's go by analogy: say you're going out for dinner. Put socks on. Put shoes on. Stand up. Walk to door. Then you get a phone call. Dinner plans cancelled. Take socks off. Take shoes off. Sit down. Walk away from door. Something goes wrong in there. You may trip and hurt yourself. Or more likely, you'll realize that some actions can't be undone ...


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

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 ...


6

The wikipedia article does have a reference that answers you question, but perhaps you don't want to read that 26 page paper. I'll give a simplified version of the (quite technical) proof, showing that test-and-set can not solve binary consensus for 3 processes. This kind of argument is widely used in proving consensus numbers. Let's suppose we have a ...


6

Answer: none. That's not what those sections of Herlihy and Shavit's The Art of Multiprocessor Programming are about. In the chapters on mutual exclusion Herlihy and Shavit are not giving you alternatives to the pthread library, they are showing you how it is implement the equivalent of the pthread library. Chapter 2 of Herlihy and Shavit is titled "...


6

This paper Some results on the impossibility, universality, and decidability of consensus (by Prasad Jayanti and Sam Toueg, 1992) directly answers your question. We study how initialization of shared objects affects their ability to solve consensus. In particular, although a queue or a stack can solve name-consensus between two processes, we prove that an ...


6

We finally discussed why you would use a monitor instead of a semaphore in the lecture today. It basically comes down to this: The monitor and the semaphore are equally expressive, meaning you can find a solution for a problem with a monitor where originally a semaphore was used and vice versa. Well, we already knew that, so why would you use a monitor ...


6

If you are familiar with temporal logic, the difference is quite easy to demonstrate: Weak fairness is $FGp\to Fq$. That is, if $p$ holds from some point and on, then $q$ will hold eventually. Strong fairness is $GFp\to Fq$ (or sometimes $GFp\to GFq$). That is, if $p$ holds infinitely often, then eventually $q$ will hold (or $q$ will hold infinitely often, ...


6

In what sense are this locks fast/slow? Lamport optimizes for a very specific scenario, as pointed out in the paper: The current belief among operating system designers is that contention for a critical section is rare in a well-designed system; most of the time, a process will be able to enter without having to wait. The reasoning goes like this: ...


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