Questions tagged [concurrency]
Questiont about issues of concurrency such as synchronization and deadlocks.
277
questions
1
vote
0
answers
25
views
Dot symbol in set-builder expressions in CRDT literature?
In Conflict-free Replicated Data Types: An Overview and other CRDT-related publications by Preguiça's group, a dot symbol often appears without definition. What does it indicate, how standard is it as ...
- 11
2
votes
2
answers
76
views
What does Herb Sutter refer to in his seminal paper The free lunch is over?
In his paper The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software, Herb Sutter writes:
The mainstream state of the art revolves around lock-based programming, which is subtle and ...
- 325
1
vote
0
answers
27
views
How do I prove the following invariant of this program?
I have been studying different topics within the realm of concurrent programming and came across "Lamport's bakery algorithm" which is based on the original version of the bakery algorithm ...
- 131
1
vote
1
answer
62
views
Tigers and elephants can't drink water from a pond simultaneously, while more than one tiger or more than one elephants can drink water simultaneously
Below is a question on synchronization mechanism which was asked in an interview in Indian Statistical Institute, M.Tech CS. I got hold of it from here.
There is a forest where there are tigers and ...
- 1,034
1
vote
0
answers
15
views
Spin-free synchronization primitives
I'm interested in concurrent algorithms where, if a thread is waiting for a shared resource, it must call a blocking primitive, and not busy-wait. I'll call such algorithms spin-free. Specifically, I'...
2
votes
0
answers
21
views
Is there a review of lock free priority queues for single consumer multiple producer?
Background
The task I have at hand is to write an event scheduler. From what I understood, it is basically a priority queue which needs to support concurrent insertions and single threaded delete ...
- 121
0
votes
0
answers
16
views
Linearizability compositional?
Can anyone explain how linearizability is compositional? What do you mean by that, perhaps with an example.
The confusion I have is the following. Say methid A and method B are linearizable. If I ...
0
votes
0
answers
18
views
Resources to self-study counting/sorting networks
I am reading The Art of Multiprocessor Programming. I was able to grasp almost everything up to Counting Networks in chapter 12 - Counting Sorting and Distributed Coordination. However I am having ...
1
vote
2
answers
116
views
Are there any programming languages that don't support concurrency out of the box?
My class had a discussion prompt that stated "Many programming languages, especially older ones, provide no language support for concurrency. C and C++ are examples of such languages." I ...
- 13
1
vote
1
answer
49
views
Deadlocks: Why if 2 threads are waiting for a lock from each other results in a deadlock?
I am confused as to why 2 threads waiting for a lock from each other will result in a deadlock. Let's say I have a Thread 1 that needs to execute contents in Lock 1 and then Lock 2 and a Thread 2 that ...
- 213
1
vote
1
answer
143
views
Invariant vs Assertion vs lemma
I am reading Distributed Algorithms by Nancy Lynch. I have come across lemmas, assertions and invariants, but I do not understand the difference between them. I think lemma means an intermediate ...
0
votes
1
answer
64
views
What will you do if multiple users access your application at the same time?
I'm an experienced Software Engineer but very weak in concurrency because of no prior experience in that. I've been interviewing with several companies in which I was asked similar kinds of questions ...
- 243
3
votes
1
answer
69
views
PetersonNP, mechanical mutual exclusion proof
Good day everyone,
I'm currently trying to carry out the PetersonNP (a.k.a. FilterLock) correctness proof (mutual exclusion).
I've found several proof sketches on concurrency books but I'm interested ...
- 169
1
vote
3
answers
121
views
Cache coherence is worthless and does nothing?
When you perform a write on a multi-cpu system, relevant cache flushes are done to ensure that the other cpus see the change immediately.
BUT
That write was issued from an independent thread on a ...
- 11
1
vote
3
answers
112
views
concurrency vs parallelism
I am so confused between concurrency vs parallelism in multi-core processors.
If a concurrent process has many threads and if the processor is multi-core then can each thread run on multiple cores? If ...
- 11
0
votes
1
answer
183
views
Prove correctness of a solution to the critical section problem in general?
I was wondering if there is any formal, general way to prove the correctness of a candidate solution to the critical section problem in synchronization. For example, in the image enclosed, I have ...
- 25
0
votes
2
answers
348
views
concurrency in multiple core
I know the basic definition between parallelism and concurrency. But there is not much information about
concurrency in multiple core.
what is the difference between concurrency in single-core vs ...
- 11
1
vote
1
answer
32
views
Why does taking advantage of locality matter in multithreaded systems?
As we all know, when a given thread/process reaches a memory address it does not have cached, the execution will (for the most part) freeze up until said data is fetched from memory. What I don't ...
- 13
3
votes
1
answer
138
views
How to use Parallel Semaphores for Dining Philosophers Problem
I am in an intro to OS class and we are learning about mutual exclusion and semaphores. One classical problem we learned about was the dining philosophers problem. My professor touched on the ...
2
votes
1
answer
96
views
Why sequential consistency model is widely used if it is unsound
From this talk and these lecture notes here and here I learned that sequential consistency does not actually model what really happens in practice. However, it is also pointed out that most of the ...
- 473
1
vote
1
answer
32
views
Fast software pipelining for stream processing
I have a pipelined stream processing situation, where a number of streams is linked in the computational process S0 -> S1 -> S2 -> .... You can understand &...
- 359
1
vote
1
answer
25
views
Uncertainty of coroutines writing to single socket
A program runs in a low-spec hardware utilizes coroutines writes to a single socket but how does the socket know when the data should be sent as there could more coroutines writing given N time.
I ...
- 111
2
votes
0
answers
25
views
Algorithm for locking based on a shared resource (dictionary)
I am working with a shared resource with the following specifications
acts as a dictionary (values can be obtained with key name: dictionary['key'])
does not have ...
- 121
1
vote
0
answers
54
views
Dekker's Algorithm spin on intent instead of turn
For Dekker's algorithm given below (from Wikipedia), why is it that we wait for the turn to change, instead of waiting for p1 to set it's flag to false? It seems to me that it would be safer (or more ...
- 11
1
vote
1
answer
302
views
Does upgrading after all locks and before all unlocks violate 2PL?
2PL's rule says:
Upgrading of lock (from S(a) to X (a)) is allowed in growing phase.
But what if upgrading lies after the last lock and before the first unlock? Does it still count "in the ...
- 13
1
vote
0
answers
33
views
Calculus for Communicating Systems vs. Calculus of Communicating Systems
Robin Milner uses both terms: Calculus for Communicating Systems and Calculus of Communicating Systems and, AFAIK, writes CCS for both. Is there any difference between the two? Is there a difference ...
- 161
0
votes
1
answer
191
views
Two-phase locks: why is it better?
I'm reading Arpaci's Operating Systems: Three Easy Pieces, the chapter on Locks.
At the end of the chapter, they present Two-phase locks (section 28.16). They say
A two-phase lock realizes that ...
- 123
0
votes
0
answers
45
views
Concurrent Garbage-Collectiong/Compacting Memory Allocator
I'm developing an algorithm for concurrent heap garbage collection/compaction. It will be used in low latency systems that need to scale well to a lot of clients, e.g. web servers.
I thought about an ...
- 1
3
votes
1
answer
377
views
What is the difference between a lock convoy and lock/thread contention?
From wikipedia on lock convoy:
A lock convoy occurs when multiple threads of equal priority contend repeatedly for the same lock. Unlike deadlock and livelock situations, the threads in a lock convoy ...
- 143
1
vote
0
answers
29
views
2
votes
1
answer
140
views
Count number of ways in which atomic operation(s) of n different processes can be interleaved
PROBLEM: Count the number of ways in which atomic operation(s) of n different processes can be interleaved. A process may crash mid way before completion.
Suppose there are a total of n different ...
- 147
2
votes
1
answer
503
views
Estimating P in Amdahl's Law theoretically and in practice
In parallel computing, Amdahl's law is mainly used to predict the theoretical maximum speedup for program processing using multiple processors. If we denote the speed up by S then Amdahl’s law is ...
- 123
0
votes
0
answers
12
views
parallelized data structure
I'm searching a data structure that supports O(1) concurrent insertions (thread number is known in advance) and iteration over its elements (insertion order doesn't need to be preserved).
While one ...
1
vote
1
answer
252
views
Difference between consensus number n and consensus number infinite
In book Concurrent Programming: Algorithms, Principles, and Foundations of Michel Raynal, in Section 16.5.1, Theorem 75 says
Compare&swap objects have infinite consensus number.
and in ...
- 123
1
vote
0
answers
71
views
Unconditionally fair, weakly fair, and strongly fair scheduling
I am trying to understand the difference between weakly fair and strongly fair scheduling.
For example, what scheduling policy would ensure that a process delayed at its first await statement will ...
- 113
1
vote
0
answers
54
views
Bakery algorithm: How does it work with single-writer safe registers?
I'm trying to understand the bakery algorithm and read that the Bakery algorithm uses single-writer safe registers. But I am not able to understand the correctness of bakery algorithm with safe ...
- 111
3
votes
0
answers
88
views
Why is the Black-White Bakery Algorithm considered bounded?
As stated in Lamport's papers for the bakery algorithm he states that the ticket numbers are unbounded specifically
The range of values of number is unbounded.
and
Fortunately, practical ...
1
vote
1
answer
81
views
Does Dekkers solutions to critical section problem ensure progress?
I was reading concurrency control section from Operating Systems book by William Stallings. In this book, he gives three attempts by Dekker to give solution to critical section problem:
Attempt 1
<...
- 1,547
3
votes
2
answers
360
views
Why the most dominant programming languages didn't follow CSP thread model?
I was trying to ask this question in StackOverflow, but later realized that this question is more relevant to general computer science, not specific engineering problems. If you think it's not, please ...
- 133
-1
votes
2
answers
350
views
Is this a deadlock?
Consider we have two processes P1 and P2. There are also two semaphores M and N which are initialized to zero. Here's how they execute:
...
- 153
1
vote
0
answers
48
views
n thread consensus queues
Its generally agreed that wait free queues have a consensus number of 2.
But what about this following code for a consensus protocol for a queue.
How is it that this does not go against the idea above?...
- 11
1
vote
0
answers
127
views
How to prove that an algorithm has no deadlock
I need to mathematically prove that this algorithm is deadlock-free:
...
1
vote
1
answer
1k
views
What is google docs solution to handling multiple users editing and reading at the same time?
I have always been curious as to how google solved the solution of real time collaboration in their google docs product where they allow multiple users to edit and read the same document in real time.
...
- 113
1
vote
1
answer
46
views
Distributed algorithm can be executed in a single process
Looking at a "Distributed" algorithm from a textbook on distributed algorithms (e.g. Building a spanning tree, Broadcast/Convergecast.) I found that one can implement it using Golang's concurrency ...
- 111
3
votes
0
answers
114
views
Concurrent Element-wise Reduction Algorithm (multi-threaded) (C++)
I'd like to implement a high-performance implementation of a multi-threaded reduction, element-wise, on x86 CPUs. Without loss of generality, assume the reduction operation is a sum of integers (so, ...
- 153
1
vote
0
answers
27
views
Comparing wait-signal alternatives for synchronizing two piece of programs
I came across following problem:
A certain computation generates two arrays a and b such that ...
- 1,547
2
votes
1
answer
182
views
Designing solution to critical section problem with two semaphores vs single semaphore
I came across following problem:
Let two processes P1 and P2 are there:
...
- 1,547
2
votes
0
answers
35
views
Does this state certify to be called as a deadlock?
I came across following problem:
Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others ...
- 1,547
1
vote
4
answers
4k
views
Whats exact definition of 'atomicity' in programming?
the definition of 'atomicity' says that a transaction should be able to be terminated without being touched or manipulated by possibly concurrent running actions during its process. But does that also ...
- 111
5
votes
1
answer
116
views
Are two CCS processes equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas?
I was skimming this recent paper and I was struck by the following statement:
two processes are equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML ...
- 228