Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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
1
vote
0answers
21 views

How to do atomic operations on systems that don't support it?

I need to sync data with WebDAV and other similar backend that do not have a concept of atomic operations. In some cases, I might need to read a file, change its content and write it back. And of ...
0
votes
0answers
9 views

Time-slice Equalizing Algorithm

I have a requirement for which I am trying to write an algorithm and struggling a bit conceptually with. This seems like it should be a common-ish type problem so I imagine there is a name/standard ...
1
vote
0answers
19 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 ...
0
votes
0answers
34 views

Confusion about monitor synchronisation

If I understand right, a monitor itself defines a critcal region, guarded by a lock. When a process S1 is in the region, it can ...
0
votes
4answers
89 views

Compiler instructions to sync core caches: are they really needed?

I have read reviews of this book, and quote the following from one of the reviews (emphasis mine): Other than straining your eyes with old-styled C++, you can read such misconceptions in the book ...
0
votes
0answers
28 views

Any good source explaining multiprocessor synchronization techniques and their implementation

I need to study how synchronization is done in a multiprocessor operating system, but I am unable to find a good source. I have read about it in the book "Modern Operating System" by Tanenbaum, but I ...
2
votes
1answer
181 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 ...
0
votes
0answers
299 views

Two Process Solution for Critical Section Problem- Algorithm 1

I have started learning Critical Section Problem and its various solutions. To explain my question, let me first give a brief background of it. The general structure for a two Process Solution for ...
1
vote
1answer
80 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 ...
0
votes
0answers
56 views

How to design synchronisation algorithm to combine two automata?

I have two automata of states, transition and events (Etat, Transition, evenements) and I want to create a function that create the synchronized product between those two automata. For instance, given ...
1
vote
1answer
416 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?
1
vote
0answers
52 views

Do we really need a mutex in this case?

Wikipedia's solution for multi Producer-Consumer problem uses both mutexes and semaphores. ...
2
votes
1answer
73 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 ...
2
votes
1answer
171 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 ...
1
vote
0answers
31 views

semaphore for two groups of processes

Can someone help me giving a pseudo code to this problem : There are two groups of processes , A and B. Maximum 3 Processes from group A or group B(only from one group) can use the given resource . ...
1
vote
0answers
122 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
308 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 ...
2
votes
1answer
70 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
37 views
1
vote
0answers
108 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: ...
3
votes
1answer
197 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. ...
2
votes
1answer
599 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
342 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 ...
3
votes
1answer
145 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
2answers
210 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 ...
2
votes
1answer
47 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 ...
1
vote
0answers
69 views

Behaviour of Regular Registers for Multiple Writer Case ( in context of Safe, Regular and Atomic Registers)

From the link below I understand the behaviour of different kinds of registers. However that raises few more queries in my mind. https://stackoverflow.com/questions/8871633/whats-the-difference-...
0
votes
0answers
133 views

Algorithm to construct timeline graph with arrival and departure times

So I am trying to construct a timeline graph for threads interacting with synchronization functions e.g. pthread_mutex_lock. I have the following information: 1- ...
6
votes
1answer
566 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 ...
10
votes
3answers
1k 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 ...
4
votes
0answers
278 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", "...
2
votes
2answers
693 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$. ...
4
votes
1answer
208 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 ...
1
vote
1answer
131 views

Starvation is possible or not?

let S and Q to be initialized to 1 ...
4
votes
6answers
2k 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 ...
0
votes
1answer
339 views

Is Bounded Waiting satisfied for this 2 process Solution?

This is my new post linked with my previous post. Is bounded waiting satisfied in the 2 Process Solution? The answer in that post was very useful and cleared many concepts, but I just want to apply ...
1
vote
1answer
512 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 ...
4
votes
1answer
185 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 ...
8
votes
1answer
780 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 ...
2
votes
1answer
58 views

Does a multi-agent system have to have a synchronous component in order for the agents to cooperate?

During my programming assignments in multi-agent systems, I noticed that it feels impossible to get distributed agents to cooperate without a synchronous component. Let me explain what I mean by these ...
1
vote
0answers
17 views

Optimal linking in synchronous environment for shortest path tree problem

I am dealing with the Shortest path tree problem in the specific synchronous environment. In the following algorithm, initiator begin the execution calling primitives ...
1
vote
1answer
87 views

Does the process exiting from critical section will always call signal instruction?

I have seen many solutions to critical section problems in process synchronization chapter . Many of them first acquire resources , execute critical section and leave . My Question is a process ...
2
votes
2answers
667 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 ...
0
votes
1answer
220 views

Is bounded waiting satisfied in this 2 process solution?

Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes: ...
3
votes
0answers
51 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 ...
5
votes
1answer
6k 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
1answer
2k views

Peterson's vs. Bakery Algorithm

From my CS course, the Peterson's Algorithm and the Bakery Algorithm both are solutions which satisfy the 3 requirements of any solution to the critical section problem. a) What are their adv/disadv ...
4
votes
1answer
55 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
1answer
731 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. ...
2
votes
1answer
303 views

Exclusive queue problem

There is the exclusive queue problem in The Little Book of Semaphores, which is stated as follows: Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers,...