Questions tagged [concurrency]

Questiont about issues of concurrency such as synchronization and deadlocks.

Filter by
Sorted by
Tagged with
-1
votes
0answers
12 views

What is exactly happening in GANG scheduling in multiprocessing systems?

I am trying to find how gang scheduling works. I know about time-sharing, and space sharing and I know the difference between them. But I could not find a good explanation on GANG scheduling .
0
votes
0answers
23 views

How the task is divided between multiple cores to perform in multiprocessing systems?

I am trying to find how single task is divided between two cores? what are the methods makes them work at the same time without interfering with each other?
1
vote
1answer
22 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 ...
2
votes
0answers
13 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 ...
1
vote
0answers
25 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 ...
1
vote
0answers
26 views

How does 2PL protocol apply to schedule of multiple transactions?

If a schedule follows the two-phase locking protocol, does every transaction have to follow 2PL, or is it the case that all locks must appear all unlocks in the whole schedule? I am a little confused ...
1
vote
1answer
31 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 ...
1
vote
0answers
24 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 ...
0
votes
1answer
55 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 ...
0
votes
0answers
24 views

Why is shared register's consensus number 1?

I'm trying to understand the consensus number concept. It is trivially clear that a shared register doesn't create any problem when there is only one thread using it. By why does its consensus number ...
0
votes
0answers
36 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 ...
2
votes
1answer
62 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 ...
0
votes
0answers
22 views

Strategies for event-driven concurrency

Is there any good formal investigation or at least definition of different strategies of event-driven concurrent programming? I've read that there exist readiness based (pull based) and completion ...
1
vote
0answers
25 views
1
vote
1answer
39 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 ...
1
vote
1answer
134 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 ...
0
votes
0answers
11 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
1answer
117 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 ...
1
vote
0answers
35 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 ...
1
vote
0answers
37 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 ...
3
votes
0answers
66 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 ...
0
votes
1answer
49 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 <...
3
votes
2answers
156 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 ...
0
votes
2answers
118 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: ...
1
vote
0answers
37 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?...
1
vote
0answers
79 views

How to prove that an algorithm has no deadlock

I need to mathematically prove that this algorithm is deadlock-free: ...
0
votes
1answer
342 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. ...
1
vote
1answer
26 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 ...
2
votes
0answers
46 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, ...
1
vote
0answers
24 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 ...
2
votes
1answer
84 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: ...
2
votes
0answers
26 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
vote
3answers
1k 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 ...
4
votes
1answer
68 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 ...
1
vote
0answers
57 views
1
vote
1answer
200 views

Can a schedule be conflict serializable but not serializable?

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Then, My question is: Can a schedule be conflict serializable but ...
4
votes
1answer
346 views

What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?

Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle). It ...
1
vote
0answers
47 views

Prove that set of operations form a commutative Monoid

this is my first post on this exchange. I am looking for some help with defining a proof that a set of operations I have designed forms a commutative monoid. (Disclaimer: I am not sure that I have ...
1
vote
2answers
49 views

System restarted before transaction is committed

Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest. ...
1
vote
1answer
113 views

Can 2-philosophers problem be analogous to dining philosophers problem?

Two philosophers A and B, two forks numbered "1", "2"; A needs both "1" and "2" for eating, so does B. Is this theoretical a dining philosopher problem? I'm questioning about the forks philosopher A ...
1
vote
0answers
89 views

How can I implement locking a range of values in a sorted sequence?

I am trying to write a general purpose locking algorithm which allows me to lock a range of contiguous values in a sorted array. To start with, these could be exclusive locks - so two concurrent locks ...
0
votes
1answer
2k views

Thoughts on definition for disadvantage of concurrent processing?

I'm a Computer Science student currently learning about concurrent processing. I found the benefits and disadvantages in my book vague, did some online research and put together a more detailed way of ...
2
votes
2answers
68 views

What is the formal statement of the dining philosopher's problem?

I've read about it in a few places and I'm not sure I get it. Are the philosopher's allowed to act simultaneously? Do they each take 1 action simultaneously, then go on to their next action?
1
vote
0answers
64 views

Do we really need a mutex in this case?

Wikipedia's solution for multi Producer-Consumer problem uses both mutexes and semaphores. ...
1
vote
1answer
632 views

Which Peterson’s Solution is right?

I have seen two different Peterson’s Solution to mutual exclusion, one is from Modern Operating Systems: ...
2
votes
0answers
172 views

how to find the depth of a concurrency bug

How to find the depth of a concurrency bug The below program runs on two separate threads and shares the variable x. Variables t1 and t2 are local to their threads. The program has a concurrency bug ...
0
votes
1answer
43 views

Can Multiprocessor Systems Implement Both Temporal Multithreading and Simultaneous Multithreading?

I am aware that multiprocessor systems often implement simultaneous multithreading in order to allow multiple threads to run on different CPUs. I am also aware that uni-core systems often implement ...
0
votes
1answer
91 views

What is the Difference Between Many-to-Many (M:M) Threading and Hybrid (M:N) Threading?

I have been researching threading and come across several websites which all say contradicting statements about which and how many thread models exist. Some websites say there are only three: 1:1, M:1 ...
1
vote
1answer
272 views

What fraction of all combinations is guaranteed to be deadlock free?

I found this question in the exercise of Tanenbaum (operating systems): Two processes, $A$ and $B$,each need three records $1, 2, \text{ and } 3$ in a database. If $A$ asks for them in the order $...
1
vote
0answers
63 views

How to Optimise Each Multithreading Technique? (Cooperative/Preemptive/Simultaneous)

I am currently in the process of writing an IB Extended Essay on the efficacy of multithreading on increasing the performance of applications. So far, I have been able to deduce that there are three ...

1
2 3 4 5 6