Betriebssysteme->deadlocks

Christoph

blurry333 schrieb:

Dann noch zur Entstehung eines deadlocks. Es muss eine zirkuläre Abhänigkeit bestehen.

Prozess A hat Resource F zugeteilt bekommen und fordert zusätzlich Resoure G
an. Resoure G ist aber Prozess B zugeteilt. Ist das schon ein Deadlock oder
muss Resource B auch noch Resource F anforden ? Oder geht man bei einem
Deadlock davon aus dass wirklich alle vorhandenen Prozesse lahmgelegt sind.
Schließlich könnte Prozess B in meinem Beispiel normal weiterarbeiten .

Es gibt 4 Bedingungen, die für einen Deadlock alle erfüllt sein müssen: http://en.wikipedia.org/wiki/Deadlock#Necessary_conditions

Zirkuläre Abhängigkeit ist nur eine davon.

Tobiking2

Viele Programme warten nicht darauf das die Resource frei wird, sondern beenden sich einfach und zeigen einen Fehler. Damit werden natürlich die schon belegten Resourcen frei und andere Programme können weiter laufen.

Kommen deadlocks überhaupt noch vor ?

Schließlich sind die Betriebssysteme von heute nicht mehr mit DOS aus den
80er Jahren zu vergleichen. Die Algorithmen müßten doch so gut sein
dass es keine deadlocks mehr geben kann ?

asc

blurry333 schrieb:

Kommen deadlocks überhaupt noch vor ?

Warum sollten Deadlocks nicht mehr vorkommen? Das hat auch nichts mit Algorithmen zu tun, sondern eher mit der Frage was soll man machen wenn man eine Ressource nicht ansprechen kann. Soll man warten, abbrechen...

Wie soll das OS Deadlock bitte schön vermeiden?

Bashar

blurry333 schrieb:

Schließlich sind die Betriebssysteme von heute nicht mehr mit DOS aus den
80er Jahren zu vergleichen.

DOS hatte als Single-Task-Betriebssystem natürlich kein Deadlock-Problem.

@asc, die Wikipedia-Seite für Deadlock zählt einige Strategien auf, das sieht ganz interessant aus.

hustbaer

Deadlocks kommen meist innerhalb eines Prozesses vor.

Wenn auf "externe" Dinge zugegriffen wird, also wenn es um Dinge geht auf die auch andere Prozesse zugreifen können, sind die meisten Programmierer Gott sei Dank so schlau, dass sie irgendwelche Timeouts verwenden.

krabbels

Installiere Eclipse mit ein paar Plugins und mit etwas Glück gibts nach dem Start nen Deadlock

blurry333 schrieb:

Kommen deadlocks überhaupt noch vor ?
Schließlich sind die Betriebssysteme von heute nicht mehr mit DOS aus den
80er Jahren zu vergleichen. Die Algorithmen müßten doch so gut sein
dass es keine deadlocks mehr geben kann

dead- und andere locks können immer passieren, wenn man mist programmiert hat. sogar unter DOS, ein multitasking-OS ist nicht nötig dafür.

Bashar

;fricky schrieb:

sogar unter DOS, ein multitasking-OS ist nicht nötig dafür.

Du meinst, wenn irgendwelche TSRs sich verhaken? Egal, ich bleibe bei der Aussage. DOS hatte viele Probleme, aber besondere Anfälligkeit für Deadlocks war nicht dabei.

Wenn man beim Deadlock von Resourcen spricht, meint man da hauptsächlich
Prozessorzeit und Hauptspeicher ?

SideWinder

Nein, da spricht man eher von Dateizugriffen, falsch programmierten Semaphoren wo sich jeder aussperrt, etc. Evtl. ist auch Locking von Hauptspeicher-Bereichen vorstellbar (Shared memory...) aber Prozessorzeit nicht.

MfG SideWinder

Bashar schrieb:

Du meinst, wenn irgendwelche TSRs sich verhaken?

nö, auch in sequentiellem code, wenn z.b. zwei codeabschnitte ständig übersprungen werden, weil nur der jeweils andere dafür sorgen kann, dass das bei dem einen nicht mehr passiert.

Bashar schrieb:

Egal, ich bleibe bei der Aussage. DOS hatte viele Probleme, aber besondere Anfälligkeit für Deadlocks war nicht dabei.

hast ja auch recht. wenn multitasking im spiel ist, ist die verklemmungsgefahr viel höher, das bringt die sache so mit sich.

audacia

;fricky schrieb:

nö, auch in sequentiellem code, wenn z.b. zwei codeabschnitte ständig übersprungen werden, weil nur der jeweils andere dafür sorgen kann, dass das bei dem einen nicht mehr passiert.

Es stellt sich eben die Frage, ob das noch als "Deadlock" durchgeht.

Ein besonders schön anfälliges Exempel für solchen Code wäre das hier - die einzige Stelle in C++, wo ich bis jetzt eine Anwendung für goto gefunden habe:

TPoint TImageDrawer::TImageSection::getBoundaryPoint (TRect rect, TPoint point, double angle)
{
    static const double epsilon = 0.00001;

    if (!rect.Contains (point))
        return point;

    double dx = std::cos (angle),
           dy = std::sin (angle);
    bool dxIsNotNull = std::abs (dx) > epsilon,
         dyIsNotNull = std::abs (dy) > epsilon;
    long w = rect.Width (),
         h = rect.Height ();

    TPoint retval;
    switch (angleToQuadrant (angle))
    {
    case_0: // C# supports "goto case". C++ apparently doesn't.
    case 0:
            // Right boundary
        if (dxIsNotNull)
        {
            retval.x = rect.left + w - 1;
            retval.y = point.y + dy / dx * (retval.x - point.x) + 0.5 /* round */;
            if (retval.y >= rect.top && retval.y <= rect.top + h)
                return retval;
        }

    case 1:
            // Bottom boundary
        if (dyIsNotNull)
        {
            retval.y = rect.top + h - 1;
            retval.x = point.x + dx / dy * (retval.y - point.y) + 0.5 /* round */;
            if (retval.x >= rect.left && retval.x <= rect.left + w)
                return retval;
        }

    case 2:
            // Left boundary
        if (dxIsNotNull)
        {
            retval.x = rect.left;
            retval.y = point.y + dy / dx * (retval.x - point.x) + 0.5 /* round */;
            if (retval.y >= rect.top && retval.y <= rect.top + h)
                return retval;
        }

    case 3:
            // Top boundary
        if (dyIsNotNull)
        {
            retval.y = rect.top;
            retval.x = point.x + dx / dy * (retval.y - point.y) + 0.5 /* round */;
            if (retval.x >= rect.left && retval.x <= rect.left + w)
                return retval;
        }

        goto case_0; // Ain't that an elegant goto?
    }

    return TPoint (-1, -1); // Satisfy the compiler.
}

SCNR

audacia schrieb:

Ein besonders schön anfälliges Exempel für solchen Code wäre das hier ...

^^das ist ja bloss eine endlosschleife.
was ich meine, geht etwa so (simples beispiel, in der realität sind solche hänger meistens nicht so offensichtlich):

int t;

void process_1 (void)
{
   if (t > 9)
      return;
   t++;
   puts ("p1 running");
}

void process_2 (void)
{
   if (t > 5)
      return;
   t++;
   puts ("p2 running");
}

int main (void)
{
   for(;;)
   {
      process_1();
      process_2();
      ...
      // noch mehr code, der davon nicht betroffen ist
      ...
   }
}

^^ keiner von beiden setzt 't' zurück, deswegen blockt es. beide würden weiterlaufen, wenn's einer tun würde.

mal nee andere Frage.

wieso ist in deinem Beispiel t=0 obwohl du es nicht mit 0 initialisiert hast

SideWinder

Ich rate mal ins Blaue: Die ist default-static und static-Primitive werden initialisiert? Im Notfall: Vielleicht ist es gar nicht 0 und er war ;schlampig.

MfG SideWinder

blurry333 schrieb:

wieso ist in deinem Beispiel t=0 obwohl du es nicht mit 0 initialisiert hast

globale variablen werden vorm aufruf von 'main' automatisch auf 0 gesetzt (wenn sie nicht mit was anderem initialisiert werden).

hustbaer

;fricky schrieb:

audacia schrieb:

Ein besonders schön anfälliges Exempel für solchen Code wäre das hier ...

^^das ist ja bloss eine endlosschleife.
was ich meine, geht etwa so (simples beispiel, in der realität sind solche hänger meistens nicht so offensichtlich):
int t;

void process_1 (void)
{
   if (t > 9)
      return;
   t++;
   puts ("p1 running");
}

void process_2 (void)
{
   if (t > 5)
      return;
   t++;
   puts ("p2 running");
}

int main (void)
{
   for(;;)
   {
      process_1();
      process_2();
      ...
      // noch mehr code, der davon nicht betroffen ist
      ...
   }
}
^^ keiner von beiden setzt 't' zurück, deswegen blockt es. beide würden weiterlaufen, wenn's einer tun würde.

das ist auch nur ne endlosschleife, hat mit deadlock noch nix zu tun.

hustbaer schrieb:

das ist auch nur ne endlosschleife, hat mit deadlock noch nix zu tun.

lass mich raten: dir fehlt der preemptive multitasking-kernel, der das ganze antickert, richtig?

Zusätzlich benötigt man für jeden Prozess noch eine Funktion y = f(x) welche für jede Adresse im virtuellen Speicher die zugehörige Adresse im physischen Speicher zurückliefert.

Jetzt kommts:

Die Abbildung f(x) ist keine mathematische Funktion, sondern wird von einem Hardwaregerät bereitgestellt.

Den letzten Satz versteh ich nicht. Das Hardwaregerät hat doch bestimmt
auch eine Software die die Berechnung ausführt oder ?

Betriebssysteme-&gt;deadlocks

Betriebssysteme->deadlocks