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.

learn more… | top users | synonyms

-1
votes
1answer
29 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 ...
3
votes
1answer
18 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 ...
1
vote
1answer
48 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
47 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 ...
-1
votes
1answer
28 views

Two threads are waiting on a mutex. Which one is unblocked?

Suppose there are three threads A, B, C and thread A has acquired a mutex lock and it is processing. If threads B and C try to acquire the same mutex, they will be blocked according to the mutex lock ...
1
vote
1answer
26 views

Confusion in the solution to first readers-writers synchronization

I am studying the solution to “First Readers-Writers Problem” from the book Operating System Concepts (9th edition) and it describes: First readers–writers problem, requires that no reader be kept ...
1
vote
2answers
50 views

Question on synchronisation

The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently. ...
0
votes
0answers
23 views

variant of minimum cost deadlock resolution

I have list of tasks that needs to be executed . Each task is a producer that updates multiple entities in response to consuming multiple entities. So tasks are dependent on each other for their ...
0
votes
0answers
40 views

2 phase locking with added increment mode

Suppose that a DBMS recognizes increment as an atomic operation, in addition to the read and ...
2
votes
0answers
15 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: ...
6
votes
1answer
490 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? ...
3
votes
1answer
62 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 ...
2
votes
1answer
558 views

Understanding the one-writer, many-readers problem?

I need some help understanding the implementation of the one-writer many-readers problem shown below as I am new to this concept: I have a rough idea that there will be starvation/deadlock among ...
2
votes
1answer
423 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 ...
3
votes
1answer
302 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 ...
8
votes
3answers
320 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 ...
3
votes
2answers
404 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 ...
3
votes
1answer
163 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 ...
0
votes
1answer
377 views

Chandy/Misra dining philosophers solution

So based on the Chandy/Misra section in this Wikipedia article we've got 5 philosophers numbered P1-P5. Based on this quote: For every pair of philosophers contending for a resource, create a ...
0
votes
1answer
47 views

What features should a critical section have to maximize performance?

Critical sections limit performance by constraining parallel execution and adding overhead. What features should a critical section have for improving performance?
2
votes
1answer
77 views

synchronization (test-and-set)

I have benn wondering about the following possibility: if I have multiple hardware threads on the same core, and then someone decides to use shared register to allow fast synchronization among threads ...
4
votes
0answers
34 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 ...
5
votes
1answer
444 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
2answers
58 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 ...
1
vote
0answers
41 views

Using sephamores to solve happens-before requirements [closed]

I have a practice problem that I'm not sure how to solve: Use sephamores to solve the following synchronization requirement. We have 4 processes: P1, P2,P3 and P4. P1 must run before any of the ...
2
votes
1answer
418 views

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

I'm studying the bakery algorithm. ...
4
votes
1answer
158 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 ...
1
vote
1answer
127 views

Use a Monitor like a Semaphore?

When using monitors for most concurrency problems, you can just put the critical section inside a monitor method and then invoke the method. However, there are some multiplexing problems wherein up to ...
0
votes
0answers
88 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 ...
1
vote
0answers
23 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 ...
2
votes
0answers
55 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 ...
0
votes
0answers
49 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 ...
11
votes
1answer
391 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 ...
1
vote
1answer
141 views

Is there a difference between the Bulk Synchronous Parallel Computing model and the Turing Machine [closed]

The Turing model of computing is widely accepted, as a Tape, Head, State register, and a finite state Table to manage transitions. The Bulk Synchronous Parallel Machine model has for its part ...
5
votes
2answers
127 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 ...
1
vote
1answer
320 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?
4
votes
1answer
221 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 ...
1
vote
1answer
63 views

How to synchronize a 2d cellular automaton in $\Theta(\sqrt{n} \log n)$ steps

Let's assume we have given a two dimensional cellular automaton with an initial configuration where alls cells are in an quiescent state, expect for one square of cells. Let $n$ be the number of cells ...
2
votes
0answers
33 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, ...
3
votes
0answers
2k 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 ...
0
votes
1answer
59 views

Issue with Multithreading spin locks

a spin lock solution to the critical path problem is shown below . my question is will this or will this not result in starvation ? ...
3
votes
1answer
96 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; ...
1
vote
1answer
147 views

How to present ping data from ICMP timestamp

The ICMP timestamp protocol is useful for determining which path — forward or reverse — is contributing to the jitter on the line. In an ideal world, all computers would have an excellent ntpd, and ...
1
vote
0answers
98 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 ...
6
votes
3answers
1k 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 ...
1
vote
1answer
133 views

Good “serializer” ADT implementations for Synchronization

I am looking for a library which provides a "serializer" ADT for synchronization. (http://courses.cs.vt.edu/~cs5204/fall99/Summaries/Concurrency/serializers2.html) Googling leads me to nowhere, ...
0
votes
2answers
244 views

What is the impact of synchronisation overhead on parallel speedup? [closed]

When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used? Is coarse-grained parallelism better ...
23
votes
1answer
11k 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: ...
1
vote
1answer
161 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 ...
4
votes
1answer
1k 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 ...