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

3
votes
1answer
17 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 ...
0
votes
0answers
12 views

Can git be used to share files between multiple computers not on same lan? [on hold]

a friend and I have been working on a project and need a way to share files between computers easily. While there are other alternatives such as dropbox I'd prefer to use something else. Would git be ...
1
vote
1answer
42 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
13 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
18 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
27 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
31 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
23 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 ...
8
votes
1answer
201 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
45 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 ...
4
votes
0answers
22 views

Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems

The well-known ABD algorithm in Sharing Memory Robustly in Message-Passing Systems can emulate atomic, single-writer multi-reader registers in message-passing systems, in the presence of processor or ...
1
vote
1answer
36 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
151 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
53 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
23 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
316 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
48 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
49 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
75 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
58 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
477 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
54 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
143 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 ...
13
votes
1answer
4k views

Understanding 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
89 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 ...
3
votes
1answer
503 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 ...
3
votes
1answer
177 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
174 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 ...