Нехватка ресурсов в компьютерах: причины, последствия и алгоритмы предотвращения "голодания" процессов. Статья о лишенности ресурсов и взаимном исключении.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Нехватка ресурсов в компьютерах
Resource shortage in computers
В информатике, истощение ресурсов – это проблема, возникающая в параллельных вычислениях, когда процессу постоянно отказывают в необходимых ресурсах для выполнения его работы. Истощение может быть вызвано ошибками в алгоритме планирования или алгоритме взаимного исключения, но также может быть вызвано утечками ресурсов и может быть намеренно вызвано атакой типа «отказ в обслуживании», такой как «форк-бомба». Если истощение невозможно в параллельном алгоритме, такой алгоритм называется свободным от истощения, свободным от блокировок или обладающим конечным обходом. Это свойство является примером живости и является одним из двух требований к любому алгоритму взаимного исключения; другим является корректность. Термин «конечный обход» означает, что любая часть алгоритма (параллельный процесс) обходится максимум конечное число раз, прежде чем ей будет предоставлен доступ к общим ресурсам.
In computer science, resource starvation is a problem encountered in concurrent computing where a process is perpetually denied necessary resources to process its work. Starvation may be caused by errors in a scheduling or mutual exclusion algorithm, but can also be caused by resource leaks, and can be intentionally caused via a denial of service attack such as a fork bomb. When starvation is impossible in a concurrent algorithm, the algorithm is called starvation free, lockout freed or said to have finite bypass. This property is an instance of liveness, and is one of the two requirements for any mutual exclusion algorithm; the other being correctness. The name "finite bypass" means that any process (concurrent part) of the algorithm is bypassed at most a finite number times before being allowed access to the shared resource.
Расписание
Голод обычно вызывается чрезмерно упрощенным алгоритмом планирования. Например, если (некорректно спроектированная) многозадачная система постоянно переключается между первыми двумя задачами, в то время как третья никогда не получает возможность выполняться, то третья задача испытывает недостаток процессорного времени. Алгоритм планирования, являющийся частью ядра, должен распределять ресурсы справедливо, то есть таким образом, чтобы ни один процесс постоянно не испытывал недостатка в необходимых ресурсах. Многие операционные системы используют концепцию приоритета процессов. Процесс с высоким приоритетом А будет выполняться перед процессом с низким приоритетом В. Если процесс с высоким приоритетом (процесс А) блокируется и никогда не освобождает ресурсы, процесс с низким приоритетом (B) (в некоторых системах) никогда не будет запланирован к выполнению – он столкнется с голодом. Если существует процесс X еще более высокого приоритета, который зависит от результата процесса B, то процесс X может никогда не завершиться, даже если он является самым важным в системе. Это состояние называется инверсией приоритетов. Современные алгоритмы планирования обычно содержат код, гарантирующий, что все процессы получат минимальное количество каждого важного ресурса (чаще всего процессорного времени), чтобы предотвратить возникновение голода. В компьютерных сетях, особенно в беспроводных, алгоритмы планирования могут страдать от голодания планирования. Примером является планирование с максимальной пропускной способностью. Голод обычно вызывается взаимоблокировкой (deadlock), поскольку она приводит к зависанию процесса. Два или более процессов попадают во взаимоблокировку, когда каждый из них бездействует, ожидая ресурс, занятый другой программой из того же набора. С другой стороны, процесс находится в состоянии голода, когда он ожидает ресурс, который постоянно предоставляется другим процессам. Гарантия отсутствия голода является более строгой, чем отсутствие взаимоблокировки: алгоритм взаимного исключения, который должен выбрать один из двух процессов для доступа к критической секции и выбирает один произвольно, свободен от взаимоблокировки, но не свободен от голода. Возможным решением проблемы голода является использование алгоритма планирования с приоритетной очередью, который также применяет метод старения. Старение – это метод постепенного повышения приоритета процессов, которые долгое время ожидают в системе.
Starvation is usually caused by an overly simplistic scheduling algorithm. For example, if a (poorly designed) multi tasking system always switches between the first two tasks while a third never gets to run, then the third task is being starved of CPU time. The scheduling algorithm, which is part of the kernel, is supposed to allocate resources equitably; that is, the algorithm should allocate resources so that no process perpetually lacks necessary resources. Many operating system schedulers employ the concept of process priority. A high priority process A will run before a low priority process B. If the high priority process (process A) blocks and never yields, the low priority process (B) will (in some systems) never be scheduled—it will experience starvation. If there is an even higher priority process X, which is dependent on a result from process B, then process X might never finish, even though it is the most important process in the system. This condition is called a priority inversion. Modern scheduling algorithms normally contain code to guarantee that all processes will receive a minimum amount of each important resource (most often CPU time) in order to prevent any process from being subjected to starvation. In computer networks, especially wireless networks, scheduling algorithms may suffer from scheduling starvation. An example is maximum throughput scheduling. Starvation is normally caused by deadlock in that it causes a process to freeze. Two or more processes become deadlocked when each of them is doing nothing while waiting for a resource occupied by another program in the same set. On the other hand, a process is in starvation when it is waiting for a resource that is continuously given to other processes. Starvation freedom is a stronger guarantee than the absence of deadlock: a mutual exclusion algorithm that must choose to allow one of two processes into a critical section and picks one arbitrarily is deadlock free, but not starvation free. A possible solution to starvation is to use a scheduling algorithm with priority queue that also uses the aging technique. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.