Questions tagged [synchronization]

Questions about techniques for enforcing an agreed order of events between several concurrently executing threads. Specific synchronization mechanisms include mutexes (locks), condition variables, semaphores and monitors.

Filter by
Sorted by
Tagged with
52 votes
3 answers
27k 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: ...
  • 699
19 votes
1 answer
1k views

Are there hardware lock implementations without test-and-set or swap?

Locks are usually implemented thru test-and-set and swap machine-level instructions. Are there other implementations that do not use these? Also, can we say that all hardware level solutions to the ...
11 votes
3 answers
4k views

Why are most mutex implementations unfair?

My understanding is that most popular implementations of a mutex (e.g. std::mutex in C++) do not guarantee fairness -- that is, they do not guarantee that in instances of contention, the lock will be ...
10 votes
3 answers
7k views

Why would you use a monitor instead of a semaphore?

I am currently attending the concurrent programming course in my university and we recently started talking about the concept of a monitor. While I understand the necessity of mutual exclusion, I do ...
9 votes
1 answer
1k views

What does "monotonicity" mean in the context of mutability

I'm reading The Rust Programming Language and found the following passage: Remember that writing to a struct is not an atomic operation, and many functions like ...
  • 267
7 votes
3 answers
3k views

Solutions to synchronization problem need to be executed in critical section

I was reading about synchronization problems for cooperating processes and i learned that only hardware solutions like test_and_wait() and ...
7 votes
2 answers
2k views

Bounded waiting and starvation free in critical section problem

i have 4 question regarding relation between starvation and bounded waiting. 1.Does starvation-freedom imply deadlock-freedom? My Answer-: From here, definition of starvation free is Freedom ...
  • 317
7 votes
1 answer
1k views

Vector clocks: Why is it necessary to increment my clock on receiving a message?

Assume I have a distributed system of entities, each with a replica of the same data object that can be modified by broadcasting the changes and I'm using vector clocks to know how to order changes. ...
7 votes
2 answers
11k 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: ...
  • 1,695
6 votes
2 answers
7k views

Difference between Lamport timestamps and Vector clocks

Lamport timestamps and vector clocks sound like almost the same thing. Both are used to determine the order of events in a distributed system. What are their key differences?
6 votes
2 answers
20k views

Minimum number of processes for the deadlock?

A system has 6 identical resources and $N$ processes competing for them. Each process can request at most two requests. Which one of the following values of $N$ could lead to a deadlock? 1 2 3 4 My ...
  • 465
6 votes
6 answers
6k views

Does Deadlock imply Starvation

If there is a deadlock between the processes does that mean that there is starvation also? My Thinking: deadlock is no process using that resources , but starvation is like not giving chance to only ...
6 votes
1 answer
5k views

What is a linearization point?

With respect concurrent programming, what is a linearization point? They seem to occur at a compare-and-swap instruction apparently. The best definition I could find is here. All function calls ...
6 votes
1 answer
452 views

Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)

Please bear with my unhelpful typesetting. My question is regarding well known FLP paper Impossibility of Distributed Consensus with One Faulty Process by Fischer, Lynch and Patterson While ...
6 votes
3 answers
453 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 ...
  • 9,259
6 votes
1 answer
814 views

Lamport Timestamps: When to Update Counters

In the timepiece (excuse the pun) that is Time, Clocks and the Ordering of Events, Lamport describes the logical clock algorithm as the following: Each process $Pi$ increments $Ci$ between any two ...
6 votes
1 answer
817 views

Variation of the dining philosophers: is the standard solution still valid?

I have a problem that is almost equal to the standard one of the dining philosophers, but has a quirk: while a philosopher thinks, he still holds the fork on his left. If after the period of thinking ...
5 votes
3 answers
2k views

Implementing wait-free consensus with queues

Using Herlihy's model and definition of the wait-free hierarchy, a queue (a shared object with enqueue and dequeue) has consensus number 2, because we can initialize the queue with some value, and the ...
5 votes
1 answer
462 views

Priority inversion in Hoare and Mesa monitors

I understand the difference between Hoare and Mesa monitors. However I don't understand why priority inversion (when a lower priority process gets done before a higher priority process) is possible in ...
5 votes
2 answers
177 views

Modeling concurrent algorithms

I'm working on a class library (C++) that can be thought of as a producer/consumer queue of producer/consumer queues. There are many queues of data, and the goal is to assign worker threads to process ...
  • 2,497
5 votes
1 answer
1k views

Mutex implementation on top of a minimalistic preemptive scheduler

In this question, I'm implementing some synchronization primitives in the standard library of an operating system. Specifically, I want to implement mutexes and condition variables. This is on top of ...
4 votes
1 answer
4k views

Bakery algorithm: what is the choosing[] boolean array for?

I'm studying the bakery algorithm. ...
  • 195
4 votes
1 answer
509 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.
4 votes
1 answer
865 views

Lamport logical clock: what does partial mean in the concept of `Partial ordering`?

In lamport's paper[1], he define two concept The partial ordering and The totally ordering. What does partial mean in ...
  • 219
4 votes
2 answers
482 views

Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system?

Just what the title says. Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system (without a single point of failure)? My current thoughts are that this ...
4 votes
1 answer
105 views

generation-compare-and-swap, or GCAS, in CTries

The data structure is used for example in Scala: https://github.com/scala/scala/blob/v2.12.0-M3/src/library/scala/collection/concurrent/TrieMap.scala More details in this paper: http://lampwww.epfl....
4 votes
1 answer
2k views

How do locks work?

Suppose I have an application with two threads, which both use the same resource. Normally, a synchronized block keeps these threads from messing with the resource in a way the user doesn't expect. I ...
4 votes
1 answer
190 views

“Standard” approach to syncing data?

I'm wondering if there are any universally accepted "best" algorithms for syncing data sets. I imagine there would be different solutions depending on circumstances: Are all peers online all the ...
  • 213
4 votes
1 answer
70 views

How does coarser lock granularity cause an decrease in time required to acquire and release locks?

I understand the principles required to program locks and I have run into the following problem: In my Operating Systems course, as well as on Wikipedia, one of the notions associated with lock ...
4 votes
1 answer
3k views

What happens when two processes hold an election using bully algorithm simultaneously

A coordinator is used to sychronise the usage of resources in a distributed system. The Bully Algorithm is a method to elect a new coordinator in a distributed system when the current coordinator ...
4 votes
1 answer
689 views

Distributed algorithms - $\alpha, \beta$ synchronizers

I experience a difficulty in solving exercises in distributed algorithm. Below is the the exercise I try to solve, it looks like I miss basic idea. Exercise. Consider a 15-processor asynchronous ...
  • 3,149
4 votes
0 answers
341 views

Classic Problems on Process Synchronization

I have been studying Process Synchronization and inter-process communication in Operating Systems Engineering and have come across multiple problems like "Sleeping Barbers", "Producer Consumers", "...
4 votes
0 answers
289 views

Mutex implementation on top of a preemptive scheduler that does not guarantee liveness

I'm implementing some synchronization primitives in the standard library of an operating system. Specifically, I want to implement mutexes and condition variables. This is on top of a microkernel with ...
3 votes
1 answer
2k views

Provide some help regarding the "Dining Philosophers Problem"?

I have an assignment based on operating systems and the question is divided into two sub-questions. The first is: Prove any seating arrangement of lefties and righties, with at least one of each ...
  • 210
3 votes
1 answer
3k views

Using a counting semaphore as a binary semaphore

Are there any methods, so that I can use a counting semaphore as a binary semaphore? A binary semaphore should have two possible states: 0 and ...
3 votes
1 answer
1k views

How are lamport clocks implemented in real world distributed systems?

Can anyone explain, how lamport clocks implementations are used in modern distributed systems? Can you name an open source package which implements this algorithm?
3 votes
1 answer
190 views

Lamport logical clock: why event occurs in a process with smaller pid is treated earlier?

In lamport's paper1, he define global local timestamp, which is composed of process id and local lamport timestamp. This timestamp is used to order all the events in a distributed system. The rule ...
  • 219
3 votes
1 answer
89 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 ...
3 votes
1 answer
476 views

Finding issues in concurrent implementation of carpark overflow control

Firstly, I am revising for my Concurrent Programming exam and have come across the following question from a previous exam paper. I have attempted to answer it, and will try and convey this effort; I'...
  • 63
3 votes
1 answer
266 views

Is it possible to write a wait free leader election algorithm?

I want to understand if there exists an algorithm which is wait free and operates on non-shared memory, asynchronously. Finally I want to know how to derive the consensus number of this algorithm. ...
3 votes
1 answer
143 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 ...
3 votes
1 answer
852 views

Does starvation freedom imply progress?

The above answer taken from the book https://www.amazon.com/Operating-Systems-Sibsankar-Haldar/dp/8131730220 says starvation freedom may not imply progress as processes can be deadlocked. I think ...
  • 953
3 votes
0 answers
59 views

How to apply insights from the theory of codes to alternating codes?

The book Theory of codes by J. Berstel and D. Perrin from 1985 studies variable-length codes. The focus is less on error-correction and compression, but more on algebraic properties, synchronization ...
3 votes
0 answers
5k views

totally ordered multicast with Lamport timestamp

I'm studying Distributed Systems and synchronization and I didn't catch this solution of totally ordered multicast with Lamport timestamps. I read that it doesn't need ack to deliver a message to the ...
2 votes
2 answers
1k views

Reader and Writer mutex

I am looking over the classic Reader and Writer Problem Just to give a quick overview: Many readers can be in CS (as long as no writers are) Only one writer can be in the CS (with no combination of ...
  • 125
2 votes
2 answers
2k views

Increment and Decrement on binary semaphores when their values are $1$ and $0$ respectively?

What happens if we increment binary semaphore $x$ when it is equal to $1$. E.g A process executes $V(x)$ when $x==1$; What are the possible cases then- Process would be blocked till $x$ becomes $0$. ...
  • 1,253
2 votes
1 answer
840 views

Is bounded waiting satisfied in the 2 Process Solution?

Suppose, There are $2$ processes $P1$ and $P2$. It is given that Mutual Exclusion and Progress are satisfied by these $2$ processes. Suppose, Programming protocol is designed such that CPU only ...
  • 452
2 votes
1 answer
2k views

Synchronization using serialization

How can someone synchronize two or more threads using serialization? According to my professor's slides and code assignments you can use serialization to solve the synchronization problem. (He doesn't ...
  • 227
2 votes
1 answer
651 views

Why do OS and DBMS have their own synchronisation mechanisms, when OS can alone do it and it sits at the bottom of DB?

I know that synchronization is important in the OS, but why do we need a separate topic synchronization and concurrency in the DBMS? The OS concentrates on program synchronization while the DBMS ...
2 votes
1 answer
66 views

Should we assume both processes are getting same CPU clock while we solve SYNCHRONIZATION problems in uniprocessor system?

In synchronization, when one process is in a critical section & another is busy waiting, both are using CPU. But in a uni processor system, in the same clock both cant get the CPU. So there must ...