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.

39 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5 votes
1 answer
246 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
4 votes
0 answers
355 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", "...
theraven's user avatar
4 votes
0 answers
309 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 ...
Gilles 'SO- stop being evil''s user avatar
4 votes
0 answers
6k 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 ...
Fabrizio's user avatar
3 votes
0 answers
61 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 ...
Thomas Klimpel's user avatar
2 votes
0 answers
54 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
  • 141
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
2 votes
0 answers
40 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
2 votes
0 answers
237 views

Mesa Semantics without Starvation?

When a process inside a monitor with Mesa semantics finishes, another process can acquire the monitor. Now there can be starvation here when there is a thread with a lower priority. Are there ...
damat-perdigannat's user avatar
2 votes
0 answers
43 views

How can I talk about priority inversion if it's impossible to specify priority?

In the paper: Leslie Lamport: What It Means for a Concurrent Program to Satisfy a Specification: Why No One Has Specified Priority; ACM Symp Principles of Programming Languages, (POPL-12):78-83, ...
Wandering Logic's user avatar
1 vote
0 answers
23 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 vote
0 answers
187 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
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
1 vote
0 answers
30 views

Race Condition in Mesa Monitor

...
zeitgeist's user avatar
  • 111
1 vote
0 answers
101 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
0 answers
194 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
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
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
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
1 vote
0 answers
55 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
1 vote
0 answers
139 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-...
ultimate cause's user avatar
1 vote
0 answers
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 ...
Revolucion for Monica's user avatar
1 vote
0 answers
43 views

(semaphore y=1; int x=5) vs (semaphore x=5)?

Last time, I was asked to solve a concurrency problem involving 100 similar processes constrained to fit into 5 buffers. (I'm talking about the Dining Savages problem.) I thought that it was alright ...
damat-perdigannat's user avatar
1 vote
0 answers
356 views

NTP: synchronisation of time between two machines for ICMP timestamping

Some guy on the internet recommends using the same ntp server when it is required to troubleshoot asymmetric routes through ICMP, and it's somewhat important to have synchronised time between the two ...
cnst's user avatar
  • 201
0 votes
1 answer
96 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
0 votes
0 answers
33 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
123 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
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
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
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
0 votes
0 answers
212 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
0 votes
0 answers
191 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- ...
Dev2017's user avatar
  • 101
0 votes
0 answers
370 views

2 phase locking with added increment mode

Suppose that a DBMS recognizes increment as an atomic operation, in addition to the read and ...
Sravya's user avatar
  • 11
0 votes
0 answers
326 views

Using two separate mutexes for the Exclusive Queue Problem (Little Book of Semaphores)

I recently read the exclusive queue (exclusive ballroom dancers) problem on the "Little Book of Semaphores" by Allen Downey. His solution included a single mutex for both the leaders and the ...
damat-perdigannat's user avatar
0 votes
0 answers
75 views

Describing monitors and semaphores in terms of the three properties of critical section problem solutions

Solutions to the critical section problem exhibit three properties: mutual exclusion, progress, and bounded waiting. When do we say, or do we at least say, that operating system-implemented semaphores ...
damat-perdigannat's user avatar
-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
-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