Questions tagged [concurrency]

Questiont about issues of concurrency such as synchronization and deadlocks.

Filter by
Sorted by
Tagged with
1
vote
2answers
104 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
139 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
108 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
73 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
93 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
827 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
239 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
51 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
125 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
504 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
65 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 ...
3
votes
0answers
217 views

Is the Bakery Lock fair?

Consider this implementation of the Bakery Lock: ...
0
votes
1answer
88 views

Checking claim in paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al

In the 2004 paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al. (which can be found here and here) the authors state: We also note that any execution of T1 and T2 ...
0
votes
1answer
56 views

How to keep track of changes done to concurrent stacks?

I am writing a small RPN calculator that works on some stacks concurrently. For example, if I have two functions: ...
1
vote
1answer
24 views

Are process-safe mutexes shared between OSes?

I understand you can use process wide mutexes, but does this still apply if you have an additional virtualized operating system provisioned? For example, take two OSes: ...
1
vote
2answers
2k views

Serializability and the Lost Update Problem

Serializability is the strongest consistency level with regard to the execution of two concurrent transactions T1 and T2. That is, if T1 and T2 independently change the application between consistent ...
-2
votes
1answer
190 views

Erlang- Creating a function which only adds/subtracts positive integers

I want to create a function which allows me to input a list, and then add all of the positive numbers from the list together, leaving any that are negative. ([3,1,-1]) For example only 3 and 1 would ...
2
votes
1answer
131 views

What are good resources for self teaching parallel/concurrent/multithreaded programming techniques? [closed]

I’m having a hard time finding anything thorough. I have found some courses with titles like "parallel and concurrent programming in Java", but I'm looking to learn general techniques, not their use ...
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
1answer
222 views

Concurrency and fairness

I'm studying the concurrency in programming and the atomic instructions. What i have not understood is the concept of "fairness" applied to this matter. Can you give me an hint ?
0
votes
0answers
29 views

Concurrency and non deterministm

I was introduced in concurrency programming this morning. I haven't understood why "non deterministm" is a fundamental aspect of cuncurrenty programming. What i think is that, since there is a ...
17
votes
2answers
3k views

Is it possible for a stack-based programming language to be concurrent?

I have been reading about stack-based programming languages, such as FORTH and Cat, and it seems that given their nature, they can only execute one action at a time regardless of their paradigm (FORTH ...
1
vote
0answers
260 views

interval tree clocks

I understand how vector clocks detect concurrent events, but they are designed for a fixed number of nodes, so we can't easily add and remove nodes. And with interval tree clock we can. Could you ...
1
vote
0answers
139 views

bakery algorithm, switching up the condition

I'm currently studying the Bakery Algorithm. I understand it for what it is but now I want to switch it up a bit. If we changed the < in the 2nd ...
2
votes
1answer
105 views

Compute the mode of an array concurrently

As an academic exercise, I have to write a parallel algorithm that given a sorted array of $n$ integers computes the mode (i.e. the item with the highest frequency) efficiently using $p$ processors, ...
2
votes
1answer
140 views

How to do compare-and-increment different locations with in memory MVCC?

I'm reading the paper An Empirical Evaluation of In-Memory Multi-Version Concurrency Control which is about implementations of MVCC for in-memory databases. Section 3.3 on Two-phase Locking (MV2PL) ...
4
votes
1answer
3k views

What does synchronous and asynchronous mean in computer science?

Words synchronous and asynchronous can be met several times, in different contexts, when studying computer science. As an example : Synchronous and asynchronous circuits. Synchronous and asynchronous ...
0
votes
0answers
23 views

concurrency control in real time database

Can Lamport's Bakery algorithm be used for controlling concurrency in soft real time database system (case study of stock trading)?
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
2k views

Number of conflict serializable schedules

Two transactions $T_1$ and $T_2$ are given as: $$T_1: r_1(X)w_1(X)r_1(Y)w_1(Y)$$ $$T_2: r_2(Y)w_2(Y)r_2(Z)w_2(Z)$$ where $r_i(V)$ denotes a read operation by transaction $T_i$ on a variable $V$ and $...
3
votes
1answer
86 views

FLP Impossiblity Result assumption of $C_1 = e'(C_0)$

FLP86's famous proof regarding impossibility of async distributed processes with a single fault assumes in the proof of the third lemma the existence of an event $e'$ such that the neighbor ...
1
vote
0answers
65 views

Lamport's distributed mutual exclusion: wait-chain order clock

Regarding Lamport's mutual exclusion... Where messages are exchanged in the following sequence between nodes S, G1, and G2. G1 and G2 are the members of the group. (for this, lets just assume that ...
1
vote
0answers
121 views

Is Dekker's algorithm not k-bounded for any finite k?

Consider this version of the algorithm, for only 2 processes, 0 and 1: ...
2
votes
1answer
64 views

Are synchronous message sends a subset of async. ones?

Imagine any object oriented PL based around the idea of message sends: some method basically performs something like this: ...
4
votes
3answers
130 views

Finite state automaton's reaction to simultaneous events

What does happen if two events simultaneously occur at a particular state of a finite state automaton (FSA)? For example, assume that an FSA's event table at its state $s$ is as follows: $\delta(s,...
1
vote
1answer
87 views

Question about IO automaton

I'm currently reading Nancy Lynch book about distributed systems, chapter about IO automaton. And I have following questions related to book exercise 8.13(c). We are given some automaton A with sig(A)...
2
votes
1answer
980 views

semaphore implementation with test and set

I'm trying to understand the algorithm for implementing semaphores on SMP system using test and set instruction described here: https://people.mpi-sws.org/~druschel/courses/os/lectures/proc4.pdf (and ...
1
vote
2answers
414 views

2:1 Mutual exclusion with semaphores

I'm stuck on this semaphore exercise (it's a exam question of a previous exam and I'm studying for that exam): There are three processes: A, B and C. Process A wants to execute method a(); Process B ...
1
vote
3answers
1k views

How can a spinlock progress when it's busy-waiting?

I read that in spinlock, process keeps on waiting for the lock continuously in a loop until it receives signal(lock) or ...
4
votes
1answer
430 views

Are Test and set primitives as powerful as semaphores?

I get confused because i don't know if it is possible to use Test and Set primitives in case where more then one process can be enter in critical section at the same time.
2
votes
0answers
60 views

Select/Barrier statements in $\pi$-Calculus denotational semantics

A select statement waits on $n$ channels until channel $0$ or $1$ or ... or $n-1$ have data. A barrier lock waits on $n$ ...
0
votes
1answer
70 views

How is the concurrent tracking of "state position" in NFA's typically modelled?

Conceptually, to track the multitude of "state positions" arising in an NFA while it is processing a given input string, a quantitative notion of memory/cache/storage is required per "fork" of ...
1
vote
1answer
4k views

What is "time-slice multi-threading"?

My goal is to understand the exact differences between SoEMT, SMT and "time-slice multi threading". Thus far I already found information on SoEMT and SMT and it does not seem to hard to find more on ...
2
votes
0answers
40 views

Through how many levels must cache writeback propagate?

Suppose that my multicore computer system has the diagrammed memory caches. ...
1
vote
0answers
26 views

Communicating Sequential Processes: SQUASH

In C.A.R Hoare's Communicating Sequential Processes (1978), he presents the SQUASH problem: Replace every pair of consecutive asterisks "**" by an upward arrow "↑". Assume that the final character ...
0
votes
1answer
113 views

Why do functions containing `await` need to be `async`?

From what I understand, async/await enables to avoid the "callback pyramid of doom". Let's say that I have ...
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: ...
3
votes
2answers
828 views

What is the problem with this Busy Wait solution for two threads?

We have two processes. One process produces F and the other process consumes F Initialization: Consuming = false Produced = false F = EMPTY The first thread (...
2
votes
1answer
251 views

Consensus number of memory-to-memory swap

I think that consensus number of mem-to-mem-swap(a,b) operation which atomically swaps the values between shared locations a and b (shared R/W memory) is infinite , but I'm having trouble proving it. ...