Questions tagged [mutual-exclusion]

Questions about the concurrency-control requirement of ensuring that no two processes are simultaneously in a critical section (a period when the process is accessing a shared resource). Failing to achieve mutual exclusion leads to the problem of data races.

52 questions
Filter by
Sorted by
Tagged with
58 views

PetersonNP, mechanical mutual exclusion proof

Good day everyone, I'm currently trying to carry out the PetersonNP (a.k.a. FilterLock) correctness proof (mutual exclusion). I've found several proof sketches on concurrency books but I'm interested ...
83 views

How are semaphores and test-and-set instructions connected?

Cheers, so my textbook explains these parts very poorly, so I would gladly take any advice! I am confused between the test-and-set instructions, which per my book is a very common CPU instruction set, ...
32 views

Dekker's Algorithm spin on intent instead of turn

For Dekker's algorithm given below (from Wikipedia), why is it that we wait for the turn to change, instead of waiting for p1 to set it's flag to false? It seems to me that it would be safer (or more ...
49 views

Unconditionally fair, weakly fair, and strongly fair scheduling

I am trying to understand the difference between weakly fair and strongly fair scheduling. For example, what scheduling policy would ensure that a process delayed at its first await statement will ...
26k 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: ...
78 views

When does a semaphore issue a wait and when does it issue a signal?

In my textbook, Operating Systems: Internals and Design Principles (9th Edition) by William Stallings in chapter 5, it explains how semaphores work: The fundamental principle is this: Two or more ...
563 views

What should be the minimum value when the two threads are executed concurrently

int count=0; void *thfunc() { int ctr=0; for(ctr=0;ctr<100;ctr++) count++; } If *thfunc() is executed by two threads concurrently in a uniprocessor ...
543 views

What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion?

After reading Lamport Algorithm for Mutual Exclusion, I can not understand the purposes of reply messages. I think they are not necessary because the assumption of the algorithms is that all messages ...
25 views

Comparing wait-signal alternatives for synchronizing two piece of programs

I came across following problem: A certain computation generates two arrays a and b such that ...
583 views

What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?

Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle). It ...
87 views

Do we really need a mutex in this case?

Wikipedia's solution for multi Producer-Consumer problem uses both mutexes and semaphores. ...
276 views

Peterson algorithm for mutual exclusion

In the Peterson Algorithm for mutual exclusion an implicit assumption is that the operations with the shared global variables happen atomically. To me, this is not a superficial assumption , cause it'...
119 views

Starvation algorithm in operating system

Is there an algorithm for mutual exclusion with shared flag variables, as the Peterson's one, that doesn't prevent the starvation ?
112 views

a problem with Suzuki-Kasami mutex algorithm

I have some sort of a misunderstanding regarding the Suzuki-Kasami distributed mutex algorithm. I am writing my question here because I failed on gaining access to the original paper. I will call ...
61 views

Lamport's distributed mutual exclusion: wait-chain order clock

Regarding Lamport's mutual exclusion... Where messages are exchanged in the following sequence between nodes S, G1, and G2. G1 and G2 are the members of the group. (for this, lets just assume that ...
43 views

Process X ...
121 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: ...
1k views

How can a spinlock progress when it's busy-waiting?

I read that in spinlock, process keeps on waiting for the lock continuously in a loop until it receives signal(lock) or ...
2k views

What is the difference between consensus and mutual exclusion in Distributed Systems?

If we can achieve consensus, does it imply we can achieve mutual exclusion? Is there a difference? Example : Paxos solves the consensus problem, can it also be used to solve mutual exclusion?
800 views

What is the problem with this Busy Wait solution for two threads?

We have two processes. One process produces F and the other process consumes F Initialization: Consuming = false Produced = false F = EMPTY The first thread (...
386 views

What are the practical use of weak semaphores?

Weak semaphores are often defined as if a process (or thread), say p1, performs a V operation and some other process is waiting on that semaphore, then the first process (i.e. p1) is not ...
305 views

What is the abstract idea of a semaphore and how can we use it to implement mutual exclusion?

So I've got this so far to try and wrap my head around the abstract idea of a semaphore: A semaphore is a variable or abstract datatype (commonly an integer), used to control access to a common ...
335 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", "...
365 views

186 views

Mutex-/semaphore-/locking-algorithm using atomic reads/writes with data-propagation delays

Is there a mutual exclusion or semaphore or locking algorithm that only relies on atomic reads and atomic writes of shared memory and can tolerate a delay in propagation of the written data between ...
457 views

Mutual exclusion algorithm using only atomic reads and writes for unknown number of processes and robust to process abortion

I am trying to come up with a mutual exclusion algorithm that is based only on atomic reads and atomic writes of shared memory (i.e. no compare-and-swap or similar). Apart from mutual exclusion and ...
7k 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 ...
471 views

Disabeling interrupts to solve critical section issue on multiprocessor system

Assume I have a multicore system and a critical section. I understand how disableling interrupts on a single core systems solves the critical section problem. So assume I could disable interrupts on ...
417 views

This is from a textbook on operating systems. This is not homework, just part of the chapter on deadlocks. ...
1k 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 ...
244 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 ...
71 views

What happens if the holder of a lock tries to acquire a lock? [closed]

In a system, suppose there is a process and a resource with only one instance. Let us assume that the process holds the instance and requests the same instance of that resource. Will there be a ...
169 views

What is the practical relevance of textbook mutual exclusion algorithms?

There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is ...
100 views

Concurrent Programming Bar Problem

I have been posed a question by my lecturer and I'm trying to figure the right way to go about it. They want me to ensure mutual exclusion for n processes. The code provided is as follows: ...
1k views

Is it possible to solve the critical section problem with an atomic subtract operation?

In my Operating Systems class, our professor asked us to solve the critical section problem with the following atomic operation: ...
960 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 ...