什么是饥饿? [英] What is starvation?

问题描述

在多任务系统中，某些异常情况会阻止执行进程或线程的进度.我将把进程和线程简称为进程".其中两个条件称为死锁和活动锁.

In multitasking systems, some abnormal conditions prevent progress of executing processes or threads. I'll refer to both processes and threads simply as "processes". Two of these conditions are called dead-lock and live-lock.

前者是指相互阻塞的进程，因此阻止了两者之一的执行.后者是指互相阻止进度但实际上不阻止执行的进程.例如，它们可能会不断导致彼此回滚事务，而无法完成它们.

The former refers to processes which are blocking each other, thus preventing either from executing. The latter refers to processes which prevent each other from progressing, but do not actually block the execution. For instance, they might continually cause each other to rollback transactions, neither ever being able to finish them.

另一种情况称为资源匮乏，其中，进程的进度已消耗了一个或多个有限的资源，这些资源已被它们耗尽，除非进程进行进度，否则无法恢复.这也是活锁的一种特殊情况.

Another condition is known as resource starvation, in which one or more finite resources, required for the progress of the processes, have been depleted by them and can't be restored unless the processes progress. This is also a special case of live-lock.

我想知道是否存在饥饿"的其他定义，特别是学术上的定义，而不仅限于资源饥饿".特别欢迎提供参考.

I'd like to know if there is any other definition, particularly an academic one, for "starvation" that is not limited to "resource starvation". References are specially welcome.

而且，不，这不是家庭作业. :-)

And, no, this is not homework. :-)

推荐答案

我不会说资源匮乏是活动锁的特例.通常:

I wouldn't say that resource starvation is a special case of a livelock. Usually:

• 在活动锁中，没有线程取得进展，但它们继续执行. (陷入僵局，他们甚至没有继续执行)

• In a livelock, no thread makes progress but they keep executing. (In a deadlock, they don't even keep executing)

饥饿时，某些线程确实取得了进展，而某些线程没有执行.

When starving, some thread(s) DO make progress and some thread(s) aren't executing.

一个很好的解释: http://docs.oracle.com /javase/tutorial/essential/concurrency/starvelive.html .但是我知道术语的选择可能会有所不同.

A good explanation: http://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html. But I understand the choice of terminology may vary.

关于饥饿，我听到的定义是:

When it comes to starvation, the definition I heard is:

假设可以指定与假设(信号量语义，OS调度程序行为...)一致的无限执行路径(隔行扫描)，以使线程T被挂起以等待某些资源并且永不恢复，即使有可能无限多次.然后，T被称为饥饿.

Suppose it is possible to specify an infinite path of execution (interlace) consistent with assumptions (semaphore semantics, OS scheduler behaviour...) such that thread T is suspended waiting for some resource and never resumed, even if it was possible infinitely many times. Then T is called starving.

但是这种做法与之不符.假设两个线程在无限循环中执行相同的关键部分.您的同步代码允许第一个线程每小时进入关键部分.是饥饿吗?这两个线程都可以继续进行，但是第一个线程正在缓慢地痛苦地工作.

But the practice doesn't match that. Suppose two threads execute the same critical section in an infinite loop. Your synchronization code allows the first thread to enter the critical section once per hour. Is it starvation? Both threads are allowed to progress, but the first one is doing its work painfully slowly.

最简单的饥饿根源是弱信号量.如果您使用行为相似的同步原语(或构建自己的同步原语)，则会导致饥饿.

The simplest source of starvation are weak semaphores. If you are using a synchronization primitive (or building your own) that behaves similarly, then starvation will result.

众所周知的饥饿问题:

• 读写器问题.可以同步线程，以便 (1)读者将能够饿死作家 (2)作者将能够使读者挨饿 (3)不会发生饥饿 (请参见 http://en.wikipedia.org/wiki/Readers-writers_problem )

• Readers-writers problem. It is possible to synchronize the threads such that (1) the readers will be able to starve the writers (2) the writers will be able to starve the readers (3) no starvation will occur (See http://en.wikipedia.org/wiki/Readers-writers_problem)

用餐哲学家( http://en.wikipedia.org/wiki/Dining_philosophers_problem)

有关更多详细信息，我全力推荐《信号量小书》(免费): http://www. greenteapress.com/semaphores/.

For more details, I wholeheartedly recommend The Little Book of Semaphores (free): http://www.greenteapress.com/semaphores/.

您要询问的是每个饥饿是否都是由于等待某些资源引起的.我会说-是的.

You are asking if every starvation is caused by waiting for some resource. I'd say - yes.

线程可以被挂起:

(1)在某些阻塞的系统调用上-等待/获取互斥量，信号量，条件变量； write()，poll()等.

(1) on some blocking system call - waiting on/acquiring a mutex, semaphore, conditional variable; write(), poll() etc.

(2)进行一些非阻塞操作-例如执行计算.

(2) on some nonblocking operation - like performing computations.

挨饿(1)就是挨饿资源(互斥体，缓冲区等).

Starving on (1) is starving on resources (mutexes, buffer etc.).

饥饿(2)导致CPU饥饿-您可以将其视为资源.如果发生这种情况，则问题出在调度程序上.

Starving on (2) is starving on CPU - you can regard it as a resource. If it happens, the problem is with scheduler.

HTH

这篇关于什么是饥饿?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！