Questions tagged [concurrency]

Questiont about issues of concurrency such as synchronization and deadlocks.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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'...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 &...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 143
1 vote
0 answers
29 views

Race Condition in Mesa Monitor

...
user avatar
  • 111
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 <...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
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?...
user avatar
  • 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: ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

1
2 3 4 5 6