Advanced   Java   Services

Starvation

Ein Thread wird vor dem eigentlichen Start vom sog. Scheduler des Betriebssystems in die Warteschlange wartender Threads eingereiht. Sobald ein laufender Thread beendet ist, kann er in der Warteschlange nach vorne rücken. Es gibt aber mehrere Situationen die ein Vorrücken verzögern oder verhindern. Zum einen werden Threads mit hoher Priorität bevorzugt, zum anderen kann es sein, daß ein Thread sich sofort wieder um den Prozessor bewirbt und so den anderen kaum Chancen läßt zum Zug zu kommen. Tritt dadurch eine Situation ein, daß ein Thread in der Schlange nicht vorankommt, spricht man von Starvation (to starve - verhungern). Der Thread verhungert. Die Gefahr ist immer dann besonders groß, wenn Betriebsmittel durch Threads exklusiv belegt werden.

Die Idee ist die folgende:

Mehrere Threads wollen eine Resource exklusiv über synchronized erhalten und einen gewissen Zeitraum belegen. Während der Belegzeit ist die Resource natürlich gelockt. In einem Beispiel erreicht man das am einfachsten mit sleep(), da sleep() den Lock nicht zurückgibt (eine ander Möglichkeit wäre ein zeitlich begrenztes wait(), aber nicht auf die Resource, da ein wait() ja den Lock zurückgibt).

Nach diesem Zeitraum versuchen der Threads sofort wieder auf die Resource zuzugreifen. Damit dies so schnell wie möglich geschieht dürfen in run() außerhalb des synchronized-Blocks keine Statements stehen, da außerhalb von synchronized die Resource nicht gesperrt ist.

Es werden 26 Threads gestartet. In einer Endlosschleife versuchen sie permanent die Resource zu bekommen. Hat einer Erfolg behält er die Resource für 200ms. Jeder Thread erhält einen Buchstaben des Alphabets als ID. Bei jedem Zugriff auf die Resource hat, gibt ein Thread seine ID aus. Nach dem Starten aller Threads wartet main() 2 Minuten und beendet sich dann. Da alle 26 Threads Dämonen sind werden sie nach dem Ende von main sofort von der JVM gekillt. An den Ausgaben erkennt man welche Threads zum Zug gekommen sind (und welche nicht).

Bis auf drei Threads, die die niedrigste Priorität bekommen, erhalten alle anderen die höchstmögliche Priorität.

import java.util.concurrent.TimeUnit;

public class Starvation
{
   public static void main(String[] args)
   {
      int threadCount = 26;
      System.out.println("starting " + threadCount + " threads " + 'a' + " to " + (char) ('a' + threadCount - 1));

      Object resource = new Object();
      // create sample runners and start them
      Starvation[] starvation = new Starvation[threadCount];
      Thread[] thread = new Thread[threadCount];
      for(int i = 0; i < threadCount; i++)
      {
         starvation[i] = new Starvation(resource, (char) ('a' + i));
         thread[i] = new Thread(starvation[i]);
         thread[i].setDaemon(true);
         thread[i].setPriority(Thread.MAX_PRIORITY);
      }
      thread[8].setPriority(Thread.MIN_PRIORITY); //i
      thread[9].setPriority(Thread.MIN_PRIORITY); //j
      thread[10].setPriority(Thread.MIN_PRIORITY); //k

      for(int i = 0; i < threadCount; i++)
         thread[i].start();

      try
      {
         TimeUnit.MINUTES.sleep(2);
      }
      catch(InterruptedException ex)
      {
      }
      System.out.println("\nend main");
   }
}

class Starvation implements Runnable
{
   private Object resource;
   private char id;

   public Starvation(Object resource, char id)
   {
      this.resource = resource;
      this.id = id;
   }

   public void run()
   {
      for(;;)
      {
         synchronized(resource)
         {
            System.out.print(id);
            try
            {
               TimeUnit.MILLISECONDS.sleep(250);
            }
            catch(InterruptedException ignored)
            {
            }
         }
         // Möglichkeit mehr Fairness zu erreichen
         //Thread.yield();
      } // end for

   } // end run()

}  // end class

Mit Hilfe von yield() erricht man mehr Fairness.

Zeilenumbrüche per Hand eingefügt !

1)  starting 26 threads a to z; sleep 250ms; main sleep 2 minutes; i,j,k lowest, others highest priority

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
xxxxx
wwwwwwww
vvvvv
uuuuuuuuuuuuuuuuuuuuuuuuu
ttttt
sssssss
rrrrrr
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

2)  starting 26 threads a to z; sleep 250ms; main sleep 2 minutes; i,j,k lowest, others highest priority

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
xxxxxxxxxxxxxxxxxxxxxxxxxx
wwwwww
v
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt
ssssssssssssssssssssssss
rrrrrrrrrrrrrrrrrrrrrrrr
qqqqqqqqqqqqqqqqqqq
pppppppppppppppp
oooooo
nnnnnnnnnnnnnnnnn

3)  starting 26 threads a to z; sleep 250ms; main sleep 2 minutes; i,j,k lowest, others highest priority
aaaaaa
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxx

Bei keinem der drei Durchlaüfe sind die Threads mit niedriger Priorität zum Zug gekommen.