Concurrent systems are systems where several threads of computation are potentially executing simultaneously and interacting.

learn more… | top users | synonyms

2
votes
1answer
27 views

Why is a program with only atomics in SC-DRF but not in HRF-direct?

In the paper "Heterogeneous-Race-Free Memory Models" [1], the authors state that a program consisting only of atomic is race free in SC-DRF but it is not in HRF-direct. I am not able to understand why ...
3
votes
1answer
140 views

How do locks work?

Suppose I have an application with two threads, which both use the same resource. Normally, a synchronized block keeps these threads from messing with the resource in a way the user doesn't expect. I ...
1
vote
1answer
82 views

Build a scheduler, to simulate parallel game flow [closed]

I am building a strategy game where units can interact with each other. As input I am getting a list of actions. I need to output a scheduler, that will tell when to start each action. The goal is to ...
0
votes
1answer
47 views

Simulating a sequence of events concurrently subject to a happened-before partial order

I am building a strategy game where multiple units(5 - 20) is fighting each other in the same time. I have a logic part that calculate those actions for each turn, and than pass it to the game ...
1
vote
3answers
86 views

Additional clarification about Simultaneous Multithreading

I was looking for comments about SMT and got several responses. The last one looks strange: Simultaneous multithreading, which can only be implemented on a multicore system, executes the ...
2
votes
1answer
73 views

Superscalar processors and complex instructions

I read that a supercalar processor has redundant functional units. One can read this e.g. on Wikipedia. How do such redundant units work? Is a complex instruction (for accelerating heavy process, ...
5
votes
1answer
69 views

Inconsistent state of a lock

I'm reading The Art of Multiprocessor programming and trying to understand their concept of inconsistent locks. Specifically, on page 37, the definition 2.8.1 of an inconsistent lock is not clear to ...
4
votes
2answers
101 views

Why is there readonly (const) in C++, but not writeonly (sink)?

C++ initially had "readonly" and "writeonly" qualifiers, before "readonly" was renamed to "const", and "writeonly" removed. My question is: What are the problems with "writeonly" (or a "sink" ...
2
votes
1answer
20 views

Deadlock prevention by killing a victim

In our operating systems class, the teacher told us about deadlocks prevention methods. One of them is that to select as a victim the process which requires the CPU time or one that requires a lot of ...
4
votes
0answers
40 views

Extending the causal memory model to wide-area distributed storage systems

In the seminal paper "Causal memory: definitions, implementations, and programming", distributed causal memory is defined to ensures that all the processes in a system agree on the relative ordering ...
2
votes
0answers
22 views

How can I talk about priority inversion if it's impossible to specify priority?

In the paper: Leslie Lamport: What It Means for a Concurrent Program to Satisfy a Specification: Why No One Has Specified Priority; ACM Symp Principles of Programming Languages, (POPL-12):78-83, ...
3
votes
1answer
46 views

Session Memory in the Windows Kernel

While reading the paper Effective Data-Race Detection for the Kernel by John Erickson and Madanlal Musuvathi. I was stuck on a slightly tricky sentence. "Similarly, a range of kernel-address space, ...
2
votes
1answer
64 views

Does “serializable” also mean that it's lockable

Here's an final exam question for a Database Fundamentals class. I've read the book, stuff online.. I can't figure out if "serializable" also means that the schedule is ...
2
votes
3answers
124 views
5
votes
1answer
87 views

Question about threads and locks

I am currently reading Fuss, Futexes and Furwocks: Fast Userland Locking in Linux and came across this quote: In a fair locking scheme the lock is granted in the order it was requested. This can ...
1
vote
1answer
35 views

If a thread containing main terminates, can another thread do anything?

I'm studying threads in C and I have this theoretical question in mind that is driving me crazy. Assume the following code: ...
1
vote
0answers
20 views

Why is this execution happens-before consistent?

In section 17.4.5 "Happens-before Order" of Java Language Specification, a trace is examined for the notion of happens-before consistency. The trace is shown in the figure in which $A$ and $B$ are ...
3
votes
0answers
80 views

“Data-race free” programs

In section 6.3 of the paper Causal memory: definitions, implementations, and programming, the authors define "data-race free" as follows: Program $\Pi$ is data-race free if, for all histories $H$ ...
1
vote
0answers
25 views

Proof strategies for linearizability of implementations

Background: In section 4.2 of the paper Linearizable Implementations Do Not Suffice for Randomized Distributed Computation@STOC'2011, the authors mentioned two typical proof strategies for ...
3
votes
0answers
36 views

What are methods for showing that concurrent objects are not linearizable?

Linearizability is a well-known correctness condition for concurrent objects. It provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point ...
2
votes
0answers
40 views

Proof of contention of the wait-free consensus algorithm

I know that this is a known theorem but I can't find its proof. The theorem is: The write-contention of any $n$-process wait-free consensus algorithm (implemented from any read-modify-write ...
2
votes
0answers
26 views

Polylogarithmic value-bounded concurrent data structures such as max register, counter, and monotone circuit

While reading the research paper Polylogarithmic Concurrent Data Structures from Monotone Circuits [@JACM'2012] by James Aspnes, Hagit Attiya, and Keren Censor-Hillel, I am not sure about some points ...
0
votes
2answers
316 views

Deadlock and cycle in a resource allocation graph

Here is a resource allocation graph asked in my Operating Systems Theory midterm. The question is, "Is there a deadlock here? Explain your answer in detail" Ra and Rb are resource sets and every ...
2
votes
1answer
45 views

Finding issues in concurrent implementation of carpark overflow control

Firstly, I am revising for my Concurrent Programming exam and have come across the following question from a previous exam paper. I have attempted to answer it, and will try and convey this effort; ...
6
votes
3answers
823 views

Difference between Parallel and Concurrent programming?

When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel. And some programming languages specifically claim support for parallel programming, such as Java. ...
3
votes
2answers
101 views

How can an extended linearizable history G be equivalent to sequential history S?

I am undertaking a module in Concurrent Programming where some of the new content this year covers linearizability, the Java Memory Model, and sequential consistency. Our class slides are companion ...
2
votes
1answer
393 views

Differences between the Actor Model and Communicating Sequential Processes (CSP)

When we look at the Actor Model and Communicating Sequential Processes we see that they are both trying to do concurrency based on message passing, yet they are distinct. (We see implementations of ...
2
votes
1answer
52 views

How to express Rob Pike's classic Go Code presentation in Hoare's CSP Algebra?

At 15:30 in this talk (p13 of this presentation here) Rich Hickey mentions the formalisms available for reasoning about Communicating Sequential Processes. He then goes on to mention that these ...
1
vote
0answers
23 views

defining the operational semantics of a concurrent language

As big-step operational semantics is about evaluating an expression to a final value, can we state that for defining a concurrent language one needs small-step semantics, as concurrent programs need ...
-2
votes
1answer
117 views

Number of concurrent schedules in database

In a database system, say there are $N$ transactions each having $m_1,m_2,\dots,m_N$ operations. How many concurrent schedules are possible? $(m_1+m_2+....+m_n)!$ is the number of possible ...
2
votes
2answers
2k views

Difference between multitasking, multithreading and multiprogramming

I was a little confused between these three terms Multitasking, Multithreading and Multiprogramming Although every one means executing different lines of codes, and for every one we need something ...
1
vote
1answer
76 views

Is it possible to do multitasking without context switch with just one cpu?

All the article I can find seems to talk about multitasking and context switch as its a two different thing. It seems that multitasking and context switch are the same thing.
4
votes
3answers
356 views

Solutions to synchronization problem need to be executed in critical section

I was reading about synchronization problems for cooperating processes and i learned that only hardware solutions like test_and_wait() and ...
1
vote
3answers
268 views

Maximum degree of concurrency in task dependency graphs

I've been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that's bugging me is how can I find ...
1
vote
0answers
18 views

What are some visual tools for the design of concurrent systems?

I am looking for visual tools for the design, and optionally verifications, of concurrent systems. PS: There is no tag for visual-programming, I must have 150 reputation to create one, so please ...
5
votes
3answers
129 views

Is it possible to prove thread safety?

Given a program consisting of variables and instructions which modify these variables, and a synchronization primitive (a monitor, mutex, java's synchronized or C#'s lock), is it possible to prove ...
0
votes
2answers
137 views

What is the impact of synchronisation overhead on parallel speedup? [closed]

When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used? Is coarse-grained parallelism better ...
6
votes
2answers
160 views

Automaton equivalent of the π calculus?

If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing ...
4
votes
2answers
95 views

How does a race condition work?

When two threads try to access the same resources at exactly the same time how does the computer decide which one gets the resource, or is it just decided at random?
11
votes
1answer
3k views

Understanding Peterson’s and Dekker’s algorithms

I am trying to understand the algorithms by Peterson and Dekker which are very similar and display a lot of symmetries. I tried to formulate the algorithms in informal language like follows: ...
1
vote
1answer
101 views

Using Little's law to find the average N of customers

I'm trying to understand Little's law and can't seem to get past this scenario: Let's say people arrive at the register at 12 per hour. It takes 10 minutes (1/6 of an hour) to service each one of ...
3
votes
1answer
42 views

Is there a mistake in the expression for clean behavior in Pnueli's article from 81'?

I am reading an article called The temporal semantics of concurrent programs . On page $9$, there is a small section (numbered as $2$) called "clean behavior". I think that there is a problem with ...
1
vote
1answer
87 views

Definition of “K-fairness” with respect to concurrency?

There are definitions of Absolute, Strong and Weak Fairness available across the internet, but I cannot find a definition of "K-Fairness" property for critical section algorithms (also algorithms that ...
16
votes
1answer
911 views

What does 'true concurrency' mean?

I often hear phrases like 'true concurrency semantics' and 'true concurrency equivalences' without any references. What does those terms mean and why are they important? What are some examples of ...
6
votes
1answer
93 views

Formalisms in concurrent and/or distributed programming?

My background came from imperative languages, primarily C, C++, and Python. I picked up Scala, Erlang, and a bit of Haskell a few years later and have since become very interested in functional ...
0
votes
1answer
134 views

concurrency and hardware

I've a couple of questions that I need answers for. What I am looking for here is the outline of the answers. Not necessarily the exact complete answer. I can do that. The question is that common ...
1
vote
1answer
85 views

Synchronization using serialization

How can someone synchronize two or more threads using serialization? According to my professor's slides and code assignments you can use serialization to solve the synchronization problem. (He doesn't ...
1
vote
1answer
49 views

Multithreaded access to a persistent linked list data structure

I previously asked a question about persistent data structures here. After that I came across an article that introduced persistent data structures. I have got a question on the following figure from ...
0
votes
1answer
72 views

applying CTL/LTL model-checking on some system

I apologies if my title is vague, I'm trying to apply CTL/LTL model-checking on some system written in java, however, I still don't understand how to reach a result using either of the approaches ...
3
votes
1answer
59 views

Process graphs and finding infinite processes

I am reading on concurrent processes and algorithms which find infinite processes by searching the process graph recursively. Most of the material I have found is not for beginners. I am looking for ...