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
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 ...
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", "...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
1
vote
0
answers
30
views
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 ...
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:
...
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 ...
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.
...
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 . ...
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 ...
1
vote
0
answers
55
views
Does the following piece of code lead to a deadlock?
Process X
...
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:
...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
...
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 ...
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:
...
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 ...
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 ...
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- ...
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 ...
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 ...
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 ...
-1
votes
1
answer
29
views
-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.
...