기아 (컴퓨터 과학)

Starvation (computer science)
다른 용도는 기아(동음이의)를 참조하십시오.

컴퓨터 과학에서 자원 부족은 동시 컴퓨팅에서 발생하는 문제이며,[1] 프로세스가 작업을 처리하는 데 필요한 자원을 지속적으로 거부합니다.기아는 스케줄링 또는 상호 제외 알고리즘의 오류로 인해 발생할 수 있지만 리소스 누출로 인해 발생할 수도 있으며 포크 폭탄 등의 서비스 거부 공격을 통해 의도적으로 발생할 수도 있습니다.

동시 알고리즘에서 기아가 불가능한 경우, 이 알고리즘을 기아가 없는 알고리즘, 록아웃[2] 프리 알고리즘 또는 유한 [3]바이패스가 있는 알고리즘이라고 합니다.이 속성은 활성의 인스턴스이며 상호 제외 알고리즘의 두 가지 요건 중 하나이며, 다른 하나는 정확성입니다."무한 바이패스"라는 이름은 알고리즘의 모든 프로세스(동시 부분)가 공유 [3]리소스에 대한 액세스가 허용되기 전에 제한된 횟수만큼 바이패스됨을 의미합니다.

스케줄

기아는 보통 지나치게 단순한 스케줄링 알고리즘에 의해 발생합니다.예를 들어 (잘 설계되지 않은) 멀티태스킹시스템이 항상 첫 번째 두 작업 사이를 전환하고 세 번째 작업을 실행할 수 없는 경우 세 번째 작업은 CPU 시간이 부족합니다.커널의 일부인 스케줄링 알고리즘은 리소스를 공평하게 할당하도록 되어 있습니다.즉, 알고리즘은 필요한 리소스가 영구적으로 부족한 프로세스가 없도록 리소스를 할당해야 합니다.

많은 운영체제스케줄러는 프로세스 priority 개념을 채택하고 있습니다.우선도가 높은 프로세스 A는 우선도가 낮은 프로세스 B보다 먼저 실행됩니다.고우선순위 프로세스(프로세스 A)가 차단되어 실행되지 않는 경우, 저우선순위 프로세스(B)는 스케줄 되지 않고(일부 시스템에서는) 기아 상태가 됩니다.프로세스 B의 결과에 따라 priority가 더 높은 프로세스X가 존재하는 경우 시스템 내에서 가장 중요한 프로세스임에도 프로세스X가 완료되지 않을 수 있습니다.이 상태를 priority inversion이라고 합니다.현대의 스케줄링 알고리즘에는 일반적으로 프로세스가 고갈되는 것을 방지하기 위해 모든 프로세스가 각 중요한 자원의 최소량(대부분 CPU 시간)을 수신하도록 보장하는 코드가 포함되어 있습니다.

컴퓨터 네트워크, 특히 무선 네트워크에서 스케줄링 알고리즘은 스케줄링 부족에 시달릴 수 있습니다.예를 들어 최대 throughput 스케줄링입니다.

기아는 일반적으로 프로세스가 동결되는 교착 상태에 의해 발생합니다.같은 세트의 다른 프로그램이 점유하는 리소스를 기다리는 동안 각 프로세스가 아무것도 하지 않으면 둘 이상의 프로세스가 교착 상태가 됩니다.한편, 다른 프로세스에 지속적으로 제공되는 자원을 대기하고 있을 때는 프로세스가 고갈 상태에 있습니다.기아의 자유는 데드록이 없는 것보다 더 강력한 보증입니다.즉, 두 프로세스 중 하나를 중요한 섹션으로 허용하고 임의로 하나를 선택해야 하는 상호 배타 알고리즘은 데드록이 없지만 기아가 [3]없는 것은 아닙니다.

기아에 대한 가능한 해결책은 에이징 기술을 사용하는 priority 큐에 스케줄링 알고리즘을 사용하는 것입니다.에이징은 시스템에서 장시간 [4]대기하는 프로세스의 우선순위를 점차 높이는 기술입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Tanenbaum, Andrew (2001). Modern Operating Systems. Prentice Hall. pp. 184–185. ISBN 0-13-092641-8.
  2. ^ Herlihy, Maurice; Shavit, Nir (2012). The Art of Multiprocessor Programming. Elsevier. p. 24. ISBN 9780123977953.
  3. ^ a b c Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer Science & Business Media. pp. 10–11. ISBN 3642320279.
  4. ^ Galvin, Peter (2010). Operating System Concepts. Wiley India Edition. p. 193. ISBN 978-81-265-2051-0.