12 votes
Accepted

Does Deadlock imply Starvation

You should first state the deadlock freedom property and the starvation freedom property more precisely. I use the definition in the Book: The Art of Multiprocessor Programming; Section 2.2. Freedom ...
hengxin's user avatar
  • 9,521
6 votes
Accepted

How to satisfy bounded waiting in case of deadlock?

You are correct. Consider the simple synchronization algorithm which denies entry to all processes. In this case we have both deadlock and bounded waiting, since any process $p$ is not bypassed by ...
Ariel's user avatar
  • 13.4k
5 votes
Accepted

How does lack of deadlock relate to computability in process calculi?

I think you are asking about expressivity of concurrent programming languages. This is a deep and not well-understood field. For example you say that "the $\pi$-calculus [...] has the power to ...
Martin Berger's user avatar
4 votes
Accepted

What is the difference between "deadlock prevention" and "deadlock avoidance"

It seems that deadlock prevention and deadlock avoidance are two names for the same concept. Indeed, the Wikipedia section on deadlock avoidance has been marked as redundant. While the distinction ...
Yuval Filmus's user avatar
4 votes

How probable is a deadlock in the dining philosophers problem

the dining philosopher problem seems to be somewhat of a pedagogical "toy" example of concurrency and (dead)locking concepts for educational purposes. however it is studied seriously in some ...
vzn's user avatar
  • 11k
4 votes
Accepted

Bounded waiting and starvation free in critical section problem

No, starvation-free doesn't imply bounded waiting. For instance, consider a procedure that never even attempts to acquire any lock; but the amount of time it takes is variable and can be arbitrarily ...
D.W.'s user avatar
  • 158k
4 votes
Accepted

Why deadlock in cigarette smokers problem

Agent A consumes agentSem, and produces tobacco and paper. That might make Smoker I smoke but he is late: Smoker II already took the paper and Smoker III took tobacco. Now, all the smokers are stuck,...
chi's user avatar
  • 14.5k
3 votes

A real life system that faces and solves the dining philosophers problem

The dining philosopher's problem is a worst case scenario used to illustrate issues in algorithms. It's a test case. You probably won't find a static one-to-one mapping between it and a real world ...
orlp's user avatar
  • 13k
3 votes

difference between deadlock avoidance and detection

Simply to put Deadlock avoidance: you employ some methods to avoid the deadlock ,but prevention is more restrictive than avoidance. Deadlock detection: Here only the detection only takes place ...
Pavan Kumar Munnam's user avatar
3 votes
Accepted

Bankers Algorithm-Is the system in safe state?

you can say there is no deadlock if there is a safe sequence for the completion, after $P1$ request is granted there must be a safe sequence where by which every process is completed. ...
Pavan Kumar Munnam's user avatar
3 votes
Accepted

Is this solution to the dining philosopher's problem entirely valid?

The description of an altruistic philosopher given in this answer, that you quoted in your question, is slightly imprecise. What it really is going on is that: A possible approach for avoiding ...
Patrick Trentin's user avatar
3 votes
Accepted

A Dead-lock in an Operating System is

Your attempt "If a process is unable to change its state indefinitely because the resources requested by it are being used by another waiting process, then the system is said to be in a deadlock." is ...
gnasher729's user avatar
  • 29.4k
3 votes
Accepted

Is Bounded Waiting satisfied for this 2 process Solution?

In the following, I treat the first two statements acquire(lock1) acquire(lock2) as "trying", the middle two statements ...
hengxin's user avatar
  • 9,521
3 votes

Is bounded waiting satisfied in the 2 Process Solution?

A little remark first: The bounded waiting (BW) property is defined with respect to algorithms, which is in turn defined as a set of concrete executions. Thus, we cannot conclude whether an algorithm ...
hengxin's user avatar
  • 9,521
3 votes

How probable is a deadlock in the dining philosophers problem

I don't know what algorithm the philosophers follow, but let's assume that deadlock is reached if all philosophers try to start eating at the very same time. Since your time is discrete, under any ...
Yuval Filmus's user avatar
3 votes
Accepted

In Operating Systems, I can't understand why deadlock happens, why does a process not let go of a resource when it is done using it?

To answer part of your question: Processes are not smart. Processes just execute the code of their program, so if the program of P1 has not been written to release R1 when it's done with it, it won't ...
Steven's user avatar
  • 29.4k
3 votes
Accepted

Deadlocks: Why if 2 threads are waiting for a lock from each other results in a deadlock?

The situation you are describing is not a deadlock. A deadlock would be more like this: Both Thread A and Thread B require both Lock 1 and Lock 2. Thread A first acquires Lock 1, then Lock 2. Thread ...
Jörg W Mittag's user avatar
3 votes

Why does a lock ordering prevent deadlocks?

The four necessity conditions for deadlock are: Mutual exclusion Hold and Wait No preemption Circular Wait Let there be two processes/threads - P1 and P2 and two resources - R1 and R2. Now assume ...
Russel's user avatar
  • 2,735
2 votes
Accepted

Falsifying the "Circular Wait" Condition - Deadlock Prevention

It's fixed. Your example violates the protocol. If the process needs mutually exclusive access to both the tape drive and the disk drive, then it needs to take locks in increasing order, i.e. first ...
Derek Elkins left SE's user avatar
2 votes
Accepted

Does the following modified Two-Phase Locking protocol ensure serializability and freedom from deadlock?

The question is not clear about the details, but assuming said resources are always locked-then-accessed sequentially, then a deadlock is not possible to occur. Since the locks are always obtained in ...
Marcelo De Zen's user avatar
2 votes

When will deadlock occur in this producer-consumer code

It will be caused as follows: Both processes blocked at the end, hence deadlocked.
Mahesha999's user avatar
  • 1,745
2 votes
Accepted

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

Semaphores are an abstract mechanism to control access to a shared resource. Other such mechanisms exist, for example locks and monitors. These are the counterparts of abstract data structures – they ...
Yuval Filmus's user avatar
2 votes

Why does a lock ordering prevent deadlocks?

How you get a deadlock: Thread 1 waits for lock A and grabs it. Thread 2 waits for lock B and grabs it. Then thread 1 waits for lock B which is already locked and thread 2 waits for lock A which is ...
gnasher729's user avatar
  • 29.4k
1 vote
Accepted

Can 2-philosophers problem be analogous to dining philosophers problem?

Short answer: yes, though it could be considered a "degenerate case" (that is, a case that ends up being somewhat different from most others). Long answer: the Dining Philosophers problem is really ...
Draconis's user avatar
  • 7,078
1 vote

Deadlock vs "Progress" requirement of the solution to the critical section problem

and this selection cannot be postponed indefinitely In case of deadlock, deciding which process will enter next will be postponed indefinitely. So progress won't happen.
Ayush's user avatar
  • 117
1 vote
Accepted

Can a safe state in Banker's Algorithm cause deadlock eventually?

No deadlock as long as you keep running the Banker's algorithm. By definition, a state is considered safe if it is possible for all processes to finish executing, which means there is no deadlock. ...
John L.'s user avatar
  • 38.8k
1 vote
Accepted

deadlock caused by a cyle of locks ? unprobable event causing it or just a false intuition

If a thread takes the Couple 5, the thread taking the couple 4 will lock D and wait, etc... to Couple 2. Couple 1 tries to start and is waiting on A, couple 4 tries to start but is also waiting on A....
ratchet freak's user avatar
1 vote

Does starvation freedom imply progress?

It depends on how exactly you define "starvation freedom" and "liveness." I believe the book is talking about starvation freedom from the perspective of the OS scheduler, which usually does not know ...
Vimal's user avatar
  • 119
1 vote

Deadlock and safe state

That is not possible, when a deadlock occurs, the system is in an UNSAFE state. A safe state wouldn't have any purpose if a deadlock could occur.
NimaJan's user avatar
  • 353

Only top scored, non community-wiki answers of a minimum length are eligible