Questions tagged [concurrency]

Questiont about issues of concurrency such as synchronization and deadlocks.

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

Can (intrinsic) locks act in different ways in addition to mutexes?

I'm reading Java Concurrency in Practice, and I came across the following sentence (section 2.3.1 Intrinsic locks, pg. 25): Every Java object can implicitly act as a lock for purposes of ...
uzluisf's user avatar
  • 101
1 vote
0 answers
16 views

Rationale behind prefix-closure in CSP trace semantics

I'm currently studying Hoare's "Communicating Sequential Processes" (1) and I've come across a concept that I find a bit puzzling. In CSP trace semantics, a process's semantics are described ...
nasosev's user avatar
  • 111
0 votes
1 answer
36 views

How are waits in semaphores made atomic in nature?

I was going through the book Operating Systems by Galvin. First they explain Semaphores acting like a mutex. While talking about semaphores as mutex, they mention that the wait operation of semaphores ...
Himanshuman's user avatar
0 votes
0 answers
37 views

How to test progress and bounded waiting in Peterson's algorithm?

This is Petersons's solution for critical section problem. I want to test mutual exclusion, progress and bounded waiting for it. Of course, it satisfied all three. ...
zeeshanseikh's user avatar
0 votes
2 answers
62 views

What's the standard technique to test if the algorithm satisfies mutual exclusion, progress and bounded waiting or not?

Sorry if this is a stupid question. But it really intrigued me. Same resources at different algorithms are telling different ways to test these stuffs. Here's an algorithm and how I'd test for its 3 ...
zeeshanseikh's user avatar
0 votes
0 answers
13 views

Write-Ordering Problem, Idempotency in Distributed File Systems

I have recently finished reading the section on Distributed Systems in OSTEP. For NFS, they briefly mention the cache consistency problem and say how it is solved for reads by maintaining an attribute ...
user129393192's user avatar
2 votes
1 answer
27 views

Logics for multi-agent and distributed systems and algorithms

The various temporal logics are particularly suitable for the specification and verification of concurrent computer programs. Are there logics that are particularly suitable for the specification and ...
Evan Aad's user avatar
  • 227
0 votes
0 answers
16 views

Concurrent shared workshop problem

I found an assignment which tells me to implement concurrent workshop. Workshop consists of N workstations and each process can enter the workshop (by entering he occupies one of the workstations), ...
Yashiru99's user avatar
0 votes
3 answers
214 views

What is the minimum and maximum value of Counter when the two threads are executed concurrently?

I'm studying for an exam and have run into a problem that I do not understand. The main program starts two threads that execute the following program concurrently, whenever both threads terminate the ...
LinkedLists101's user avatar
0 votes
3 answers
86 views

Trading time for work; does this concurrency phenomenon have a name?

Recently, my girlfriend and I were trying to get out of the house, when I encountered a phenomenon which I thought might be analogous to a tradeoff in concurrent systems. Here's the real world setup. ...
lmonninger's user avatar
0 votes
1 answer
36 views

How to handle Insert and Delete requests arriving out of order?

Entries need to be stored in a database. There is Insert(entry) RPC, which adds a new entry in a database, and Delete(entry) RPC,...
mercury0114's user avatar
0 votes
1 answer
106 views

Why is this code for dining philosophers deadlock free?

...
user308485's user avatar
2 votes
0 answers
173 views

Is there a way to parallelise find and inserts for a binary search tree?

Background: I'm working on a data structure benchmark tool to benchmark insert and search time and I am trying to improve my own implementation of a BST to support parallelism. I have implemented a ...
Eterm's user avatar
  • 129
1 vote
0 answers
32 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 ...
aas's user avatar
  • 11
3 votes
2 answers
265 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 ...
Gergely's user avatar
  • 359
2 votes
2 answers
108 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 ...
NoName123's user avatar
  • 141
2 votes
1 answer
122 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 ...
Abhishek Ghosh's user avatar
1 vote
0 answers
17 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'...
Gilles 'SO- stop being evil''s user avatar
2 votes
0 answers
31 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 ...
Incomputable's user avatar
0 votes
0 answers
22 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 ...
Thanuja Dilhan's user avatar
1 vote
2 answers
377 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 ...
ganondork's user avatar
1 vote
1 answer
201 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 ...
Adam Lee's user avatar
  • 213
1 vote
1 answer
195 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 ...
Thanuja Dilhan's user avatar
0 votes
1 answer
96 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 ...
KhiladiBhaiyya's user avatar
3 votes
1 answer
100 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 ...
Chaos's user avatar
  • 433
1 vote
3 answers
181 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 ...
grud's user avatar
  • 11
1 vote
3 answers
176 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 ...
Rohit's user avatar
  • 11
0 votes
1 answer
368 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 ...
punter147's user avatar
  • 125
0 votes
2 answers
846 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 ...
Rohit's user avatar
  • 11
1 vote
1 answer
36 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 ...
KeeganB's user avatar
  • 13
5 votes
1 answer
203 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 ...
Ana Vanderwoodson's user avatar
2 votes
1 answer
135 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 ...
Barte's user avatar
  • 483
1 vote
1 answer
33 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 &...
apen's user avatar
  • 369
1 vote
1 answer
26 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 ...
jeffbRTC's user avatar
  • 111
2 votes
0 answers
30 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 ...
Simo Kivistö's user avatar
1 vote
0 answers
123 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 ...
Chien's user avatar
  • 11
1 vote
1 answer
610 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 ...
soma's user avatar
  • 13
0 votes
1 answer
298 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 ...
89f3a1c's user avatar
  • 123
0 votes
0 answers
68 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 ...
thebear8's user avatar
  • 101
3 votes
1 answer
607 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 ...
AlexH's user avatar
  • 143
1 vote
0 answers
30 views

Race Condition in Mesa Monitor

...
zeitgeist's user avatar
  • 111
2 votes
1 answer
231 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 ...
Haslo Vardos's user avatar
2 votes
1 answer
760 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 ...
Steve's user avatar
  • 123
0 votes
0 answers
14 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 ...
SomePerson's user avatar
3 votes
1 answer
377 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 ...
Bruce Wayne's user avatar
1 vote
0 answers
102 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 ...
HotWheels's user avatar
  • 113
1 vote
0 answers
85 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 ...
vrnithinkumar's user avatar
3 votes
0 answers
106 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 ...
MarkovsConundrum's user avatar
1 vote
1 answer
120 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 <...
RajS's user avatar
  • 1,637
4 votes
2 answers
536 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 ...
Tura's user avatar
  • 143

1
2 3 4 5 6