死锁和活锁有什么区别?

发布于 11-10 07:16 字数 68 浏览 4 评论 0原文

有人可以用示例(代码)解释一下死锁活锁之间的区别吗?

Can somebody please explain with examples (of code) what is the difference between deadlock and livelock?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(7

饮湿2024-11-17 07:16:42

摘自http://en.wikipedia.org/wiki/Deadlock

在并发计算中,死锁是一种状态,其中一组操作的每个成员都在等待其他成员释放锁

活锁类似于死锁,
除了以下各州
活锁涉及的进程
关于一个人不断变化
另一个,没有任何进展。活锁是
资源匮乏的特殊情况;
一般定义仅说明
特定过程不是
进展顺利。

一个现实世界的例子
当两个人相遇时就会发生活锁
在狭窄的走廊里,每个人都尝试
礼貌地让到一边
另一个通过,但他们最终
左右摇摆而不
取得任何进展,因为他们都
重复以相同的方式移动
同一时间。

活锁是一种风险
一些检测和
从僵局中恢复。如果超过
一个进程采取行动,死锁
检测算法可重复
触发。这可以通过以下方式避免
确保只有一个进程(选择
随机或按优先级)采取行动。

Taken from http://en.wikipedia.org/wiki/Deadlock:

In concurrent computing, a deadlock is a state in which each member of a group of actions, is waiting for some other member to release a lock

A livelock is similar to a deadlock,
except that the states of the
processes involved in the livelock
constantly change with regard to one
another, none progressing. Livelock is
a special case of resource starvation;
the general definition only states
that a specific process is not
progressing.

A real-world example of
livelock occurs when two people meet
in a narrow corridor, and each tries
to be polite by moving aside to let
the other pass, but they end up
swaying from side to side without
making any progress because they both
repeatedly move the same way at the
same time.

Livelock is a risk with
some algorithms that detect and
recover from deadlock. If more than
one process takes action, the deadlock
detection algorithm can be repeatedly
triggered. This can be avoided by
ensuring that only one process (chosen
randomly or by priority) takes action.

橙味迷妹2024-11-17 07:16:42

活锁

一个线程通常会响应另一个线程的操作。如果
另一个线程的操作也是对另一个线程操作的响应
线程,则可能会导致活锁。

与死锁一样,活锁线程无法取得进一步进展。然而,线程并没有被阻塞 - 它们只是太忙于相互响应而无法恢复工作。这类似于两个人试图在走廊里超越对方:阿尔方斯移动到他的左边让加斯顿通过,而加斯顿移动到他的右边让阿尔方斯通过。阿尔方斯见他们还在互相阻挡,就往他的右边移动,而加斯顿则往他的左边移动。他们仍然互相阻挡,等等......

活锁死锁之间的主要区别是线程不会被阻塞,相反,它们会尝试不断地相互响应。

在此图像中,两个圆圈(线程或进程)将尝试通过左右移动为另一个圆圈提供空间。但他们不能再进一步了。

在此处输入图像描述

Livelock

A thread often acts in response to the action of another thread. If
the other thread's action is also a response to the action of another
thread, then livelock may result.

As with deadlock, livelocked threads are unable to make further progress. However, the threads are not blocked — they are simply too busy responding to each other to resume work. This is comparable to two people attempting to pass each other in a corridor: Alphonse moves to his left to let Gaston pass, while Gaston moves to his right to let Alphonse pass. Seeing that they are still blocking each other, Alphonse moves to his right, while Gaston moves to his left. They're still blocking each other, and so on...

The main difference between livelock and deadlock is that threads are not going to be blocked, instead they will try to respond to each other continuously.

In this image, both circles (threads or processes) will try to give space to the other by moving left and right. But they can't move any further.

enter image description here

心房的律动2024-11-17 07:16:42

这里的所有内容和示例均来自

操作系统:内部结构和设计原则
威廉·斯托林斯
8° 版

死锁:两个或多个进程无法继续进行的情况,因为每个进程都在等待另一个进程执行某项操作。

例如,考虑两个进程 P1 和 P2,以及两个资源 R1 和 R2。假设每个进程都需要访问这两种资源来执行其部分功能。那么可能会出现以下情况:OS将R1分配给P2,将R2分配给P1。每个进程都在等待这两个资源之一。两者都不会释放它已经拥有的资源,直到它获得为止
另一个资源并执行需要这两个资源的功能。两人
进程死锁

活锁:两个或多个进程不断改变其状态以响应其他进程的变化而不做任何有用的工作的情况:

饥饿:调度程序无限期地忽略可运行进程的情况;尽管它能够进行,但它从未被选择。

假设三个进程(P1、P2、P3)各自需要定期访问资源 R。考虑这样的情况:P1 拥有该资源,而 P2 和 P3 都被延迟,等待该资源。当 P1 退出其关键部分时,应允许 P2 或 P3 访问 R。假设操作系统授予对 P3 的访问权限,并且在 P3 完成其关键部分之前 P1 再次需要访问。如果操作系统在 P3 完成后授予对 P1 的访问权限,随后交替授予对 P1 和 P3 的访问权限,则即使不存在死锁情况,也可能无限期地拒绝 P2 对资源的访问。

附录 A - 并发主题

死锁示例

如果两个进程在执行 while 语句之前将其标志设置为 true,则每个进程都会认为对方已进入其临界区,造成僵局。

/* PROCESS 0 */
flag[0] = true;            // <- get lock 0
while (flag[1])            // <- is lock 1 free?
    /* do nothing */;      // <- no? so I wait 1 second, for example
                           // and test again.
                           // on more sophisticated setups we can ask
                           // to be woken when lock 1 is freed
/* critical section*/;     // <- do what we need (this will never happen)
flag[0] = false;           // <- releasing our lock

 /* PROCESS 1 */
flag[1] = true;
while (flag[0])
    /* do nothing */;
/* critical section*/;
flag[1] = false;

活锁示例

/* PROCESS 0 */
flag[0] = true;          // <- get lock 0
while (flag[1]){         
    flag[0] = false;     // <- instead of sleeping, we do useless work
                         //    needed by the lock mechanism
    /*delay */;          // <- wait for a second
    flag[0] = true;      // <- and restart useless work again.
}
/*critical section*/;    // <- do what we need (this will never happen)
flag[0] = false; 

/* PROCESS 1 */
flag[1] = true;
while (flag[0]) {
    flag[1] = false;
    /*delay */;
    flag[1] = true;
}
/* critical section*/;
flag[1] = false;

[...]考虑以下事件序列:

  • P0 将 flag[0] 设置为 true。
  • P1 将 flag[1] 设置为 true。
  • P0 检查标志[1]。
  • P1 检查标志[0]。
  • P0 将 flag[0] 设置为 false。
  • P1 将 flag[1] 设置为 false。
  • P0 将 flag[0] 设置为 true。
  • P1 将 flag[1] 设置为 true。

该序列可以无限期地延长,并且两个进程都不能进入其临界区。严格来说,这不是死锁,因为两个进程相对速度的任何改变都会打破这个循环并允许进入临界区。这种情况称为活锁。回想一下,当一组进程希望进入其临界区但没有进程能够成功时,就会发生死锁。使用活锁,可能存在成功的执行序列,但也可以描述一个或多个没有进程进入其临界区的执行序列。

不再满足于书本。

那么自旋锁呢?

自旋锁是一种避免操作系统锁定机制成本的技术。通常您会这样做:

try
{
   lock = beginLock();
   doSomething();
}
finally
{
   endLock();
}

beginLock() 的成本远高于 doSomething() 时,问题就开始出现。用非常夸张的话说,想象一下当 beginLock 花费 1 秒,但 doSomething 只花费 1 毫秒时会发生什么。

在这种情况下,如果你等待 1 毫秒,你就可以避免受到 1 秒的阻碍。

为什么beginLock会花费这么多?如果锁是免费的,则不会花费很多(请参阅https://stackoverflow.com/a/49712993/5397116 ),但如果锁未释放,操作系统将“冻结”您的线程,设置一种机制在锁释放时唤醒您,然后在将来再次唤醒您。

所有这些都比一些检查锁的循环要昂贵得多。这就是为什么有时最好使用“自旋锁”。

例如:

void beginSpinLock(lock)
{
   if(lock) loopFor(1 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   if(lock) loopFor(2 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   // important is that the part above never 
   // cause the thread to sleep.
   // It is "burning" the time slice of this thread.
   // Hopefully for good.

   // some implementations fallback to OS lock mechanism
   // after a few tries
   if(lock) return beginLock(lock);
   else 
   {
     lock = true;
     return;
   }
}

如果您的实现不小心,您可能会遇到活锁,将所有 CPU 都花在锁机制上。

另请参阅:

https://preshing.com/20120226/roll-your-own -轻量级互斥体/
我的自旋锁实现是否正确且最佳?

摘要

死锁:没有人进步、什么都不做的情况(睡觉、等待等)。 CPU使用率会很低;

活锁:没有人进步的情况,但是CPU花费在锁定机制上而不是在你的计算上;

饥饿:一个进程永远没有机会运行的情况;由于纯粹的运气不佳或由于其某些属性(例如低优先级);

自旋锁:避免等待锁释放的成本的技术。

All the content and examples here are from

Operating Systems: Internals and Design Principles
William Stallings
8º Edition

Deadlock: A situation in which two or more processes are unable to proceed because each is waiting for one the others to do something.

For example, consider two processes, P1 and P2, and two resources, R1 and R2. Suppose that each process needs access to both resources to perform part of its function. Then it is possible to have the following situation: the OS assigns R1 to P2, and R2 to P1. Each process is waiting for one of the two resources. Neither will release the resource that it already owns until it has acquired
the other resource and performed the function requiring both resources. The two
processes are deadlocked

Livelock: A situation in which two or more processes continuously change their states in response to changes in the other process(es) without doing any useful work:

Starvation: A situation in which a runnable process is overlooked indefinitely by the scheduler; although it is able to proceed, it is never chosen.

Suppose that three processes (P1, P2, P3) each require periodic access to resource R. Consider the situation in which P1 is in possession of the resource, and both P2 and P3 are delayed, waiting for that resource. When P1 exits its critical section, either P2 or P3 should be allowed access to R. Assume that the OS grants access to P3 and that P1 again requires access before P3 completes its critical section. If the OS grants access to P1 after P3 has finished, and subsequently alternately grants access to P1 and P3, then P2 may indefinitely be denied access to the resource, even though there is no deadlock situation.

APPENDIX A - TOPICS IN CONCURRENCY

Deadlock Example

If both processes set their flags to true before either has executed the while statement, then each will think that the other has entered its critical section, causing deadlock.

/* PROCESS 0 */
flag[0] = true;            // <- get lock 0
while (flag[1])            // <- is lock 1 free?
    /* do nothing */;      // <- no? so I wait 1 second, for example
                           // and test again.
                           // on more sophisticated setups we can ask
                           // to be woken when lock 1 is freed
/* critical section*/;     // <- do what we need (this will never happen)
flag[0] = false;           // <- releasing our lock

 /* PROCESS 1 */
flag[1] = true;
while (flag[0])
    /* do nothing */;
/* critical section*/;
flag[1] = false;

Livelock Example

/* PROCESS 0 */
flag[0] = true;          // <- get lock 0
while (flag[1]){         
    flag[0] = false;     // <- instead of sleeping, we do useless work
                         //    needed by the lock mechanism
    /*delay */;          // <- wait for a second
    flag[0] = true;      // <- and restart useless work again.
}
/*critical section*/;    // <- do what we need (this will never happen)
flag[0] = false; 

/* PROCESS 1 */
flag[1] = true;
while (flag[0]) {
    flag[1] = false;
    /*delay */;
    flag[1] = true;
}
/* critical section*/;
flag[1] = false;

[...] consider the following sequence of events:

  • P0 sets flag[0] to true.
  • P1 sets flag[1] to true.
  • P0 checks flag[1].
  • P1 checks flag[0].
  • P0 sets flag[0] to false.
  • P1 sets flag[1] to false.
  • P0 sets flag[0] to true.
  • P1 sets flag[1] to true.

This sequence could be extended indefinitely, and neither process could enter its critical section. Strictly speaking, this is not deadlock, because any alteration in the relative speed of the two processes will break this cycle and allow one to enter the critical section. This condition is referred to as livelock. Recall that deadlock occurs when a set of processes wishes to enter their critical sections but no process can succeed. With livelock, there are possible sequences of executions that succeed, but it is also possible to describe one or more execution sequences in which no process ever enters its critical section.

Not content from the book anymore.

And what about spinlocks?

Spinlock is a technique to avoid the cost of the OS lock mechanism. Typically you would do:

try
{
   lock = beginLock();
   doSomething();
}
finally
{
   endLock();
}

A problem start to appear when beginLock() costs much more than doSomething(). In very exagerated terms, imagine what happens when the beginLock costs 1 second, but doSomething cost just 1 millisecond.

In this case if you waited 1 millisecond, you would avoid being hindered for 1 second.

Why the beginLock would cost so much? If the lock is free is does not cost a lot (see https://stackoverflow.com/a/49712993/5397116), but if the lock is not free the OS will "freeze" your thread, setup a mechanism to wake you when the lock is freed, and then wake you again in the future.

All of this is much more expensive than some loops checking the lock. That is why sometimes is better to do a "spinlock".

For example:

void beginSpinLock(lock)
{
   if(lock) loopFor(1 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   if(lock) loopFor(2 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   // important is that the part above never 
   // cause the thread to sleep.
   // It is "burning" the time slice of this thread.
   // Hopefully for good.

   // some implementations fallback to OS lock mechanism
   // after a few tries
   if(lock) return beginLock(lock);
   else 
   {
     lock = true;
     return;
   }
}

If your implementation is not careful, you can fall on livelock, spending all CPU on the lock mechanism.

Also see:

https://preshing.com/20120226/roll-your-own-lightweight-mutex/
Is my spin lock implementation correct and optimal?

Summary:

Deadlock: situation where nobody progress, doing nothing (sleeping, waiting etc..). CPU usage will be low;

Livelock: situation where nobody progress, but CPU is spent on the lock mechanism and not on your calculation;

Starvation: situation where one procress never gets the chance to run; by pure bad luck or by some of its property (low priority, for example);

Spinlock: technique of avoiding the cost waiting the lock to be freed.

山色无中2024-11-17 07:16:42

死锁
死锁是任务等待的一种情况
无限期地满足永远无法实现的条件
使满意
- 任务要求对共享的独占控制
资源
- 任务在等待其他任务时保留资源
待释放资源
- 任务不能被迫放弃资源
- 存在循环等待条件

LIVELOCK
当两个或
更多任务依赖并使用一些
导致循环依赖的资源
这些任务继续进行的条件
永远运行,从而阻塞所有较低的
运行优先级任务(这些
较低优先级的任务遇到某种情况
称为饥饿)

DEADLOCK
Deadlock is a condition in which a task waits
indefinitely for conditions that can never be
satisfied
- task claims exclusive control over shared
resources
- task holds resources while waiting for other
resources to be released
- tasks cannot be forced to relinguish resources
- a circular waiting condition exists

LIVELOCK
Livelock conditions can arise when two or
more tasks depend on and use the some
resource causing a circular dependency
condition where those tasks continue
running forever, thus blocking all lower
priority level tasks from running (these
lower priority tasks experience a condition
called starvation)

沧笙踏歌2024-11-17 07:16:42

也许这两个示例向您说明了死锁和活锁之间的区别:


死锁的 Java 示例:

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class DeadlockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(DeadlockSample::doA,"Thread A");
        Thread threadB = new Thread(DeadlockSample::doB,"Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
        lock1.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 1");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
            lock2.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } finally {
            lock1.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
        }
    }

    public static void doB() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
        lock2.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 2");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
            lock1.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } finally {
            lock2.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
        }
    }
}

示例输出:

Thread A : waits for lock 1
Thread B : waits for lock 2
Thread A : holds lock 1
Thread B : holds lock 2
Thread B : waits for lock 1
Thread A : waits for lock 2

活锁的 Java 示例:


import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class LivelockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(LivelockSample::doA, "Thread A");
        Thread threadB = new Thread(LivelockSample::doB, "Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        try {
            while (!lock1.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                while (!lock2.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 2");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
                } finally {
                    lock2.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
                }
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }

    public static void doB() {
        try {
            while (!lock2.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                while (!lock1.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 1");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
                } finally {
                    lock1.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
                }
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }
}

示例输出:

Thread B : holds lock 2
Thread A : holds lock 1
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
...

这两个示例都强制线程以不同的顺序获取锁。
当死锁等待另一个锁时,
活锁并不真正等待——它拼命地尝试获取锁,但没有机会获得它。每次尝试都会消耗 CPU 周期。

Maybe these two examples illustrate you the difference between a deadlock and a livelock:


Java-Example for a deadlock:

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class DeadlockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(DeadlockSample::doA,"Thread A");
        Thread threadB = new Thread(DeadlockSample::doB,"Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
        lock1.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 1");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
            lock2.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } finally {
            lock1.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
        }
    }

    public static void doB() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
        lock2.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 2");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
            lock1.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } finally {
            lock2.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
        }
    }
}

Sample output:

Thread A : waits for lock 1
Thread B : waits for lock 2
Thread A : holds lock 1
Thread B : holds lock 2
Thread B : waits for lock 1
Thread A : waits for lock 2

Java-Example for a livelock:


import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class LivelockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(LivelockSample::doA, "Thread A");
        Thread threadB = new Thread(LivelockSample::doB, "Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        try {
            while (!lock1.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                while (!lock2.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 2");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
                } finally {
                    lock2.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
                }
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }

    public static void doB() {
        try {
            while (!lock2.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                while (!lock1.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 1");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
                } finally {
                    lock1.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
                }
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }
}

Sample output:

Thread B : holds lock 2
Thread A : holds lock 1
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
...

Both examples force the threads to aquire the locks in different orders.
While the deadlock waits for the other lock,
the livelock does not really wait - it desperately tries to acquire the lock without the chance of getting it. Every try consumes CPU cycles.

心的位置2024-11-17 07:16:42

想象一下,您有线程 A 和线程 B。它们在同一个对象上同步,并且在该块内有一个它们都在更新的全局变量;

static boolean commonVar = false;
Object lock = new Object;

...

void threadAMethod(){
    ...
    while(commonVar == false){
         synchornized(lock){
              ...
              commonVar = true
         }
    }
}

void threadBMethod(){
    ...
    while(commonVar == true){
         synchornized(lock){
              ...
              commonVar = false
         }
    }
}

因此,当线程 A 进入 while 循环并持有锁时,它会执行其必须执行的操作,并将 commonVar 设置为 true。然后线程B进来,进入while循环,由于commonVar现在是true,它能够持有锁。它这样做,执行synchronized块,并将commonVar设置回false。现在,线程 A 再次获取新的 CPU 窗口,它原本即将退出 while 循环,但线程 B 刚刚将其设置回 false ,因此循环再次重复。线程会做一些事情(因此它们不会被传统意义上的阻塞),但几乎什么也不做。

也许还值得一提的是,活锁不一定必须出现在这里。我假设一旦同步块完成执行,调度程序就会优先考虑另一个线程。大多数时候,我认为这是一个很难实现的期望,并且取决于幕后发生的许多事情。

Imagine you've thread A and thread B. They are both synchronised on the same object and inside this block there's a global variable they are both updating;

static boolean commonVar = false;
Object lock = new Object;

...

void threadAMethod(){
    ...
    while(commonVar == false){
         synchornized(lock){
              ...
              commonVar = true
         }
    }
}

void threadBMethod(){
    ...
    while(commonVar == true){
         synchornized(lock){
              ...
              commonVar = false
         }
    }
}

So, when thread A enters in the while loop and holds the lock, it does what it has to do and set the commonVar to true. Then thread B comes in, enters in the while loop and since commonVar is true now, it is be able to hold the lock. It does so, executes the synchronised block, and sets commonVar back to false. Now, thread A again gets it's new CPU window, it was about to quit the while loop but thread B has just set it back to false, so the cycle repeats over again. Threads do something (so they're not blocked in the traditional sense) but for pretty much nothing.

It maybe also nice to mention that livelock does not necessarily have to appear here. I'm assuming that the scheduler favours the other thread once the synchronised block finish executing. Most of the time, I think it's a hard-to-hit expectation and depends on many things happening under the hood.

意中人2024-11-17 07:16:42

我只是想分享一些知识。

死锁
如果一组线程/进程中的每个线程/进程都在等待只有该组中的另一个进程才能引发的事件,则一组线程/进程将陷入死锁。

这里重要的是另一个进程也在同一组中。这意味着另一个进程也被阻止,没有人可以继续。

当进程被授予对资源的独占访问权限时,就会发生死锁。

必须满足这四个条件才会发生死锁。

  1. 互斥条件(每个资源分配给1个进程)
  2. 保持等待条件(进程持有资源,同时可以请求其他资源)。
  3. 无抢占条件(之前授予的资源不能被强行夺走)#此条件取决于应用程序
  4. 循环等待条件(必须是2个或更多进程的循环链,并且每个进程都在等待链中下一个成员持有的资源) # 它会动态发生

如果我们发现这些条件,那么我们可以说可能会发生像死锁这样的情况。

LiveLock

每个线程/进程都一次又一次地重复相同的状态,但不会进一步前进。类似于死锁,因为进程无法进入临界区。然而,在死锁中,进程等待而不执行任何操作,但在活锁中,进程尝试继续,但进程一次又一次地重复到相同的状态。

(在死锁计算中,没有可能成功的执行序列。但在活锁计算中,有成功的计算,但有一个或多个执行序列,其中没有进程进入其临界区。)

与死锁和死锁的区别livelock

当死锁发生时,不会发生任何执行。但在活锁中,会发生一些执行,但这些执行不足以进入临界区。

I just planned to share some knowledge.

Deadlocks
A set of threads/processes is deadlocked, if each thread/process in the set is waiting for an event that only another process in the set can cause.

The important thing here is another process is also in the same set. that means another process also blocked and no one can proceed.

Deadlocks occur when processes are granted exclusive access to resources.

These four conditions should be satisfied to have a deadlock.

  1. Mutual exclusion condition (Each resource is assigned to 1 process)
  2. Hold and wait condition (Process holding resources and at the same time it can ask other resources).
  3. No preemption condition (Previously granted resources can not forcibly be taken away) #This condition depends on the application
  4. Circular wait condition (Must be a circular chain of 2 or more processes and each is waiting for resource held by the next member of the chain) # It will happen dynamically

If we found these conditions then we can say there may be occurred a situation like a deadlock.

LiveLock

Each thread/process is repeating the same state again and again but doesn't progress further. Something similar to a deadlock since the process can not enter the critical section. However in a deadlock, processes are wait without doing anything but in livelock, the processes are trying to proceed but processes are repeated to the same state again and again.

(In a deadlocked computation there is no possible execution sequence which succeeds. but In a livelocked computation, there are successful computations, but there are one or more execution sequences in which no process enters its critical section.)

Difference from deadlock and livelock

When deadlock happens, No execution will happen. but in livelock, some executions will happen but those executions are not enough to enter the critical section.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文