Questions tagged [concurrency]

Questiont about issues of concurrency such as synchronization and deadlocks.

Filter by
Sorted by
Tagged with
1
vote
1answer
74 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
vote
2answers
58 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 ...
0
votes
2answers
249 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
1answer
42 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 ...
3
votes
1answer
65 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 ...
0
votes
2answers
121 views

Conflict serializibility

So, the task is to prove the following: If S is a schedule containing at most one write action, then S is conflict-serializable. The answer is yes, but I disagree, because the following schedule ...
4
votes
1answer
129 views

Identifying Coffman conditions in a given situation with deadlock

Let's suppose there are N processes and we have the following code: ...
1
vote
1answer
114 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 ...
4
votes
1answer
126 views

Task scheduling algorithm that limits concurrency

My prof introduced us an algorithm with semaphores that was used to solve the "dining philosophers" problem. The algo is ok, apart from that it limits concurrency. What does mean that it "limits ...
0
votes
2answers
161 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 ...
1
vote
1answer
515 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 $...
3
votes
1answer
63 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 ...
0
votes
1answer
80 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 ...
0
votes
1answer
57 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 ...
1
vote
3answers
107 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 ...
1
vote
1answer
31 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 &...
1
vote
3answers
92 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 ...
0
votes
0answers
19 views

Companion volume to Concurrency verification of Willem-Paul de Roever

At the moment I am working hard with the book "Concurrency Verification Introduction to Compositional and Non-compositional Methods" written by Willem-Paul de Roever et al. In the ...
7
votes
2answers
10k views

Understanding N process Peterson's algorithm

The intuitive informal description of two process Peterson's algorithm for process 0 can be given as follows: ...
0
votes
0answers
43 views

How to Concurrently Add a Row to a Relational Database

Say I have a relational database and I want to support allowing multiple writers to add create a new row in the same table. How is this implemented? I've read a lot about locks for dealing with ...
1
vote
1answer
31 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 ...
2
votes
1answer
83 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 ...
1
vote
4answers
3k 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 ...
0
votes
0answers
35 views

How many different values can a shared variable take in concurrent computing?

Question: Is there a way to find out number of different values that a shared variable can take in concurrent computing, in general, without listing all the possibilities and then counting the ones ...
0
votes
0answers
31 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
24 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
22 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
36 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
1answer
158 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
27 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
115 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 ...
2
votes
5answers
11k 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 dot ...
2
votes
3answers
107 views

How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop?

A semaphore is a variable that, apart from initialization is accessed through only two standard atomic operations wait(s) and signal(s). ...
0
votes
0answers
41 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 ...
3
votes
1answer
273 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 ...
2
votes
1answer
3k views

User level threads are transparent to the kernel?

Find whether given statement True or False? Explain. User level threads are transparent to the kernel? My attempt : False. Since, user level threads are managed by a user level library however, they ...
1
vote
1answer
92 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 ...
2
votes
1answer
369 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
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
1answer
189 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 ...
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 ...
1
vote
0answers
53 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
47 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
72 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 ...
52
votes
3answers
26k views

Contrasting 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: ...
3
votes
2answers
293 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 ...
2
votes
1answer
298 views

Does the following modified Two-Phase Locking protocol ensure serializability and freedom from deadlock?

Consider the following variant of the two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects ${O_1,...,O_k}$. The modified algorithm ...
1
vote
0answers
44 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?...
6
votes
3answers
447 views

Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems

The ABD algorithm in paper: Sharing Memory Robustly in Message-Passing Systems can emulate single-writer multi-reader atomic registers in message-passing systems, in the presence of processor or link ...

1
2 3 4 5 6