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

2
votes
1answer
40 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 ...
7
votes
3answers
138 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
185 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 ...
1
vote
1answer
48 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
64 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
32 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?
1
vote
1answer
48 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 ...
3
votes
0answers
23 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
1answer
189 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
40 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
32 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
111 views

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

I'm studying the bakery algorithm. ...
3
votes
1answer
93 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
89 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
50 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
20 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 ...
0
votes
0answers
85 views

Solution Patterns Involving Semaphores

There are a lot of synchronization problems that can be solved using semaphores. Some of these include the Producer-Consumer Problem, Readers-Writers Problem and the Dining Savages Problem. I see a ...
2
votes
0answers
42 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
39 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 ...
9
votes
1answer
334 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
87 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
78 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
143 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?
3
votes
1answer
185 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
59 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
28 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
1k 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
56 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 ? ...
2
votes
1answer
86 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
108 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
83 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 ...
5
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
74 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
194 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 ...
18
votes
1answer
8k 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
110 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
752 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 ...
4
votes
1answer
252 views

Distributed algorithms - $\alpha, \beta$ synchronizers

I experience a difficulty in solving exercises in distributed algorithm. Below is the the exercise I try to solve, it looks like I miss basic idea. Exercise. Consider a 15-processor asynchronous ...
6
votes
1answer
222 views

Variation of the dining philosophers: is the standard solution still valid?

I have a problem that is almost equal to the standard one of the dining philosophers, but has a quirk: while a philosopher thinks, he still holds the fork on his left. If after the period of thinking ...