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
2 votes
0 answers
56 views

Theoretical origin of acquire semantics only for reads?

What theoretical concept lies behind the strong restriction of acquire semantics - to reads, and release semantics - to writes? (With papers titles and authors, if possible.) Is it related to ...
Netch's user avatar
  • 151
0 votes
1 answer
98 views

Bankers Algorithm - maximum number of processes

I recently got the following question in my exam. Q1) In the banker's algorithm, if the total number of resources in the system is 20 and the maximum resource allocation for a process is 5, what is ...
ray an's user avatar
  • 115
1 vote
0 answers
24 views

Why is Bully algorithm in leader election considered synchronous?

The original paper of Bully algorithm [1] does not make any assumption of a synchronous processing. But I see few lectures explicitly call it suitable for synchronous processing. I am not sure why do ...
KRG's user avatar
  • 11
-1 votes
1 answer
29 views

What is a real life analogy of busy waiting by process "i" when "turn=i"?

...
barnyard9's user avatar
  • 133
0 votes
1 answer
38 views

Process Synchronization and Atomic Instructions

According to the book " Operating Systems Concepts ", ninth edition , page 210, we have the following statement : Many modern computer systems therefore provide special hardware ...
John adams's user avatar
0 votes
1 answer
73 views

Deadlock in LockTwo Algorithm

I was reading the Book: The Art of Multiprocessor Programming; Section 2.3.2. and I have a doubt regarding their $\texttt{LockTwo}$ algorithm mentioned in Page 26. The snippet of the algorithm is: <...
Equation_Charmer's user avatar
0 votes
0 answers
35 views

Implementing an atomic reference count where only the last one drops with acquire semantics

I just finished watching both parts of Herb Sutter's 2012 C++ and Beyond talk about atomics. In it he mentions that they initially shipped with a bug where the atomic reference count type only guarded ...
dspyz's user avatar
  • 416
0 votes
1 answer
178 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
1 answer
130 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
2 votes
2 answers
156 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
190 views

Meaning of pulse driven sequential logic?

I am trying to understand the meaning of this scheme, providing a sort of classification of sequential logic circuits. This taken from https://www.electronics-tutorials.ws/sequential/seq_1.html Does ...
Ste's user avatar
  • 131
0 votes
1 answer
127 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
0 votes
0 answers
18 views

Partition in a tree shaped distributed network

We are given a synchronic undirected tree shaped network, with $n$ indexed nodes. We know that there is at least one node with at least $\log_k n$ neighbors, $k>1000$, and $k$ is given. We need to ...
Mathguy's user avatar
  • 33
0 votes
1 answer
495 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
5 votes
1 answer
247 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
0 votes
1 answer
34 views

How to reconcile the different definitions of asynchrony?

There are 3 definitions of asynchrony that I know of: In event-based programming, asynchrony refers to the execution of tasks in a non-sequential way, which may involve creating another thread. For ...
JacopoStanchi's user avatar
1 vote
0 answers
102 views

Starvation and Livelock

I think Option C is false. Following is my thought process: Starvation in general mean Process is waiting indefinitely for the resource or to get scheduled etc. [A/c to Galvin Book]. So, here in this ...
sgoel's user avatar
  • 41
0 votes
1 answer
41 views

Verification of atomic primitives using Petri Net Models

I want to verify semantics of a library of atomic primitives that I wrote. The idea is, only if the semantics of all the primitives are consistent with each other, an application that uses them could ...
ultimate cause's user avatar
0 votes
0 answers
108 views

Simultaneous buffer access in the bounded buffer problem

Galvin and various other resources only allow either the producer or the consumer to access the buffer at a time, the common code is as follows: ...
Yueor's user avatar
  • 83
2 votes
1 answer
192 views

Synchronization in Distributed Systems

If there is no global clock in Distributed systems , then what is the solution for synchronization in DS ? Also , no global clock in DS is a direct consequence of the fact that the only communication ...
John adams's user avatar
-1 votes
1 answer
117 views

Operating system , synchronization

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned. ...
Rahul Ambastha's user avatar
1 vote
0 answers
30 views

Race Condition in Mesa Monitor

...
zeitgeist's user avatar
  • 111
0 votes
1 answer
104 views

Process synchronization problem

The atomic fetch-and-set x,y instruction unconditionally sets the memory location x to 1 and fetches the old value of x in y without allowing any intervening access to the memory location x. Consider ...
Abhishek Kumar's user avatar
1 vote
0 answers
102 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
1 vote
1 answer
202 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,667
1 vote
2 answers
500 views

Does pre-emption of a process occur when that process is busy waiting?

I was reading about Peterson's Solution for Synchronisation. Let's assume the two shared variables to be int bool flag[2] and ...
Reshma Suresh's user avatar
1 vote
0 answers
196 views

How to prove that an algorithm has no deadlock

I need to mathematically prove that this algorithm is deadlock-free: ...
PorcoDioBastardo's user avatar
0 votes
1 answer
188 views

Can timestamp be used in synchronization of processes having Race Condition?

I am wondering whether timestamp can be used to solve process synchronization problem, when race condition occurs? Below is an algorithm for entry as well as exit sections for every process who wants ...
Shiv's user avatar
  • 21
1 vote
0 answers
66 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 ...
laurent's user avatar
  • 119
2 votes
0 answers
41 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 ...
RajS's user avatar
  • 1,667
0 votes
4 answers
406 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 ...
Wad's user avatar
  • 153
0 votes
0 answers
39 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 ...
Goodfellow's user avatar
2 votes
1 answer
701 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 ...
mahesh 2222's user avatar
1 vote
1 answer
177 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 ...
asap diablo's user avatar
0 votes
0 answers
213 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 ...
Revolucion for Monica's user avatar
12 votes
2 answers
12k 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?
bkoodaa's user avatar
  • 367
1 vote
0 answers
138 views

Do we really need a mutex in this case?

Wikipedia's solution for multi Producer-Consumer problem uses both mutexes and semaphores. ...
abjoshi - Reinstate Monica's user avatar
3 votes
1 answer
273 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 ...
Ryan Lyu's user avatar
  • 249
5 votes
1 answer
1k 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 ...
Ryan Lyu's user avatar
  • 249
1 vote
0 answers
68 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 . ...
unnamed's user avatar
  • 65
1 vote
0 answers
166 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 ...
jaydee's user avatar
  • 11
3 votes
1 answer
992 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 ...
Zephyr's user avatar
  • 993
3 votes
1 answer
101 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 ...
Aditya Naik's user avatar
1 vote
0 answers
56 views

Does the following piece of code lead to a deadlock?

Process X ...
Krish__'s user avatar
  • 23
1 vote
0 answers
126 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: ...
user80614's user avatar
3 votes
1 answer
285 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. ...
ultimate cause's user avatar
2 votes
1 answer
1k 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 ...
MK.'s user avatar
  • 123
1 vote
2 answers
558 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 ...
Freddie Mercury's user avatar
4 votes
1 answer
668 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.
user292174's user avatar
4 votes
2 answers
565 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 ...
skittish's user avatar