Laden...

Ist lock fair? Bekommen die Threads in der Reihenfolge Zugang, in der sie die Sperre anfordern?

Erstellt von Sarc vor 11 Jahren Letzter Beitrag vor 10 Jahren 3.951 Views
Hinweis von herbivore vor 11 Jahren

Abgeteilt von Multithreading: Klasse mit Daten synchronisieren

Ausgangspunkt ist, ob lock in der Hinsicht fair ist, dass Threads in der Reihenfolge die Sperre bekommen, in der sie die Sperre anfordern bzw. angefordert haben. Sarc sagte im Ursprungs-Thread:

lock{} stellt eine sortierung nicht sicher, soweit ich weiss.

Ich habe dem mit den folgenden Worten widersprochen:

Doch, zumindest verwendet lock eine Queue und die Anforderungen werden in der Reihenfolge abgearbeitet, in der sie eingequeued wurden.

S
Sarc Themenstarter:in
417 Beiträge seit 2008
vor 11 Jahren
Ist lock fair? Bekommen die Threads in der Reihenfolge Zugang, in der sie die Sperre anfordern?

@herbivore: Hast du eine Quelle, die das von dir angesprochene Verhalten von lock{} dokumentiert?
Ich habe nur folgende Meinungen gefunden, die nicht für eine garantierte Reihenfolge sprechen

Does lock() guarantee acquired in order requested?
Is the C# lock statement FIFO? (first come first serve)

C
258 Beiträge seit 2011
vor 11 Jahren

Es gibt in .Net keine Synchronisationsklasse die die Wartenden Threads garantiert in FIFO Reihenfolge abarbeitet.

16.807 Beiträge seit 2008
vor 11 Jahren

...was daran liegt, dass lock auf dem Monitor basiert, und der eben nicht fair ist.
Wenn man sich durch die Threads klickt bekommt man doch auch die eindeutige Aussage:

Page 273 of the book "Concurrent Programming on Windows" says: "Because monitors use kernel objects internally, they exhibit the same roughly-FIFO behavior that the OS synchronization mechanisms also exhibit (described in the previous chapter). Monitors are unfair, so if another thread sneaks in and acquires the lock before an awakened waiting thread tries to acquire the lock, the sneaky thread is permitted to acquire the lock."

Heißt im Prinzip soviel: _normalerweise _sind .NET Monitors in einer FIFO; _ABER _dies wird in der Ausführung eben nicht garantiert.

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo Console32,

diese Aussage wird in Thread Synchronization Fairness in the .NET CLR gemacht. Allerdings bezieht sich die Argumentation zunächst nur auf TryEnter und wird dann ohne nähere Begründung auf die ganze Monitor-Klasse (also auch auf Monitor.Enter und lock) ausgedehnt. Mal abgesehen davon, dass die Aussage von 1996 ist, also zu einer Zeit, als Windows 95 und Windows NT 3.5 aktuell waren.

Hallo Sarc,

in den verlinkten Threads gibt es verschiedene widersprüchliche Aussagen. Ich muss mir das noch näher anschauen, bevor ich genaueres sagen kann. Meine Aussage stützte sich darauf, dass in der Beschreibung der Monitor-Klasse mehrfach von einer Queue die Rede ist und ich in der Dokumentation keinen Hinweis darauf gefunden habe, dass diese Queue bestimmte Threads bevorzugt. Daher habe ich geschlossen, dass es keine Bevorzugung gibt und die Threads in der Reihenfolge abgearbeitet werden, in der sie in der Queue stehen. Wenn das nicht so, wäre die Verwendung des Begriffes Queue aus meiner Sicht nicht gerechtfertigt oder es müsste zumindest einen Hinweis geben, dass von der Queue-Reihenfolge abgewichen werden kann. So einen Hinweis habe ich wie gesagt in der MSDN-Dokumentation der Monitor-Klasse nicht gefunden.

Natürlich kann es Race Conditions geben, welcher von mehren (nahezu) gleichzeitigen Threads zuerst in die Queue kommt, deshalb schrieb ich auch nur: "zumindest verwendet lock eine Queue und die Anforderungen werden in der Reihenfolge abgearbeitet, in der sie eingequeued wurden."

herbivore

W
872 Beiträge seit 2005
vor 11 Jahren

In der ECMA Spezifikation steht nur

The lock statement obtains the mutual-exclusion lock for a given object, executes a statement, and then releases the lock.
lock-statement:
lock ( _expression _ ) embedded-statement
The compile time type of the expression of a lock statement shall be a reference-type or a type parameter (§25.1.1) known to be a reference type. It is a compile-time error for the compile time type of the expression to denote a value-type.

A lock statement of the form

   lock (x) …   

is precisely equivalent to:

object obj = x;   
System.Threading.Monitor.Enter(obj);   
   try {   
      …   
   }   
   finally {   
      System.Threading.Monitor.Exit(obj);   
   }   
  

[Example:

   class Cache   
   {   
    public void Add(object x) {   
        lock (key) {   
           …   
        }   
    }   
    public void Remove(object x) {   
        lock (key) {   
            …   
        }   
    }   
    private readonly object key = new object();   
}   

end example]

C
258 Beiträge seit 2011
vor 11 Jahren

diese Aussage wird in
>
gemacht.

Nein meine Aussage basiert auf der Antwort in diesem Thread Is there a synchronization class that guarantee FIFO order in C#?
die ebenfalls einen verweiß auf das von abt genannte buch/den genannten Absatz enthält.

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo Console32,

selbst wenn die Aussage aus dem Buch stimmt, folgt daraus keinesfalls zwangsläufig, dass das es in .NET kleine Klasse gibt (bzw. geben kann), die sicherstellt, das wartende Threads FIFO abgearbeitet werden. Es gibt ja auch lock-freie, aber trotzdem threadsichere Queues, die von dem lock-Problem nicht betroffen sind.

Hallo weismat,

die Spezifikation sagt, dass lock wie bekannt auf Monitor.Enter/Exit abgebildet wird. Insofern bleibt die Frage, ob von Monitor.Enter FIFO eingehalten wird. Das, was für Monitor.Enter gilt, gilt dann aufgrund der Spezifikation automatisch auch für lock.

herbivore

C
258 Beiträge seit 2011
vor 11 Jahren

Hallo herbivore,

Die Aussage das es keine .NET Klasse gibt die wartende Threads in FIFO Reihenflolge abarbeitet stammt ebenfalls aus der Antwort im genannten Thread. Natürlich kann ich nicht sicherstellen das diese Richtig ist...

Mutex Objects (Windows) schreibt ebenfalls:

If more than one thread is waiting on a mutex, a waiting thread is selected. Do not assume a first-in, first-out (FIFO) order. External events such as kernel-mode APCs can change the wait order.

Die Funktionalität selbst implementieren kann man natürlich immer.
Könnte so aussehen: Funktioniert nur mit instanzen von object als lockObject! (da ich es nur so brauche)(


    public class Lock : IDisposable
    {
        private readonly object lockObject;
        private static readonly Dictionary<object, Ticket> Tickets = new Dictionary<object, Ticket>();
        private static readonly object TicketLock = new object;

        public Lock(object lockObject)
        {
            if (!lockObject.GetType().Name.Equals("Object", StringComparison.InvariantCultureIgnoreCase))
                throw new ArgumentException("lockObject");

            this.lockObject = lockObject;

            if (!Tickets.ContainsKey(this.lockObject))
            {
                lock (ticketLock)
                {
                    if (!Tickets.ContainsKey(this.lockObject))
                        Tickets.Add(this.lockObject, new Ticket() { TicketCount = 0, CurrentTicket = 1 });
                }
            }

            int myTicket = Interlocked.Increment(ref Tickets[this.lockObject].TicketCount);
            Monitor.Enter(this.lockObject);
            while (true)
            {
                if (myTicket == Tickets[this.lockObject].CurrentTicket)
                    return;
                else
                    Monitor.Wait(this.lockObject);
            }
        }

        public void Dispose()
        {
            if (this.lockObject != null)
            {
                Interlocked.Increment(ref Tickets[this.lockObject].CurrentTicket);
                Monitor.PulseAll(this.lockObject);
                Monitor.Exit(this.lockObject);
            }
        }

        private class Ticket
        {
            public volatile int CurrentTicket;
            public volatile int TicketCount;
        }
    }

EDIT: Überarbeitete Version weiter unten!


using (new Lock(this.myLock))
{
     ///....
}

16.807 Beiträge seit 2008
vor 11 Jahren

Dein Code ist nicht sauber
a) Wie man Dispose "optimal" implementiert, steht mit Beispielcode in der MSDN
b) Es wäre bei Dir ein Thread-übergreifender und zeitgleicher Zugriff auf Ticket möglich, da Du Ticket nicht lockst und Dictionary von Hause aus nicht Thread-sicher ist. Ebenso muss man bei Threading und Int aufpassen volatile (C# Reference)
(c) Kleinigkeiten der C# Regeln, wie Felder sind immer private, oder Schreibweise.){gray}

C
258 Beiträge seit 2011
vor 11 Jahren

Danke, ich kenne die Optimale implementierung von Dispose, ändert jedoch nichts an der Funktionalität (und kann man ja gerne selber auf ein private Dispose(bool disposing) umschreiben).

Das einfügen ins Dictionary muss synchronisiert sein (habe ich oben eingefügt), danke für den hinweiß, die Integer Operation sind durch das Interlock threadsicher. (ich habe trotzdem die felder auf volatile geändert).

Das die Felder public sind liegt am ref der Increment Methode, da es sich um eine private Klasse handelt die nur zwei Zahlen kapselt habe ich beide als felder deklariert. Kann man auch ändern wenn es stört.

16.807 Beiträge seit 2008
vor 11 Jahren

Das einfügen ins Dictionary muss synchronisiert sein (habe ich oben eingefügt), danke für den hinweiß, die Integer Operation sind durch das Interlock threadsicher. (ich habe trotzdem die felder auf volatile geändert).

Bei Deinem Increment ja; aber beim Lesen der Ints nicht.

Ich will Dir nich in Deinem Code rumwerken, daher meine Beiträge als Hinweis.

int myTicket = Interlocked.Increment(ref Tickets[this.lockObject].TicketCount);

ist auch nicht Thread-sicher - auf Tickets bezogen.

Ebenso

 if (myTicket == Tickets[this.lockObject].CurrentTicket)
 

und

Interlocked.Increment(ref Tickets[this.lockObject].CurrentTicket);
if (!lockObject.GetType().Name.Equals("Object", StringComparison.InvariantCultureIgnoreCase))

ist auch nicht gerade die elegenteste Lösung =)

49.485 Beiträge seit 2005
vor 11 Jahren

Hallo zusammen,

If more than one thread is waiting on a mutex, a waiting thread is selected. Do not assume a first-in, first-out (FIFO) order. External events such as kernel-mode APCs can change the wait order.

dass ein solcher Hinweis bei der Monitor-Klasse fehlt, dafür aber die Rede von einer Queue ist, war gerade der Grund für mich, bei Monitor von FIFO auszugehen.

Hallo Console32,

die gleichen Punkte, die Abt genannt hat, waren mir auch aufgefallen, nur war ich nicht schnell genug. 😃 Dafür habe ich einen weiteren, noch nicht genannten Punkt. Wenn Monitor tatsächlich nicht FIFO wäre, dann könnte dein Code Stravation verursachen, wenn immer wieder der gleiche Thread, der eigentlich noch nicht dran ist, sich vordrängelt und als erster die Sperre bekommt, nur um festzustellen, dass er noch nicht dran ist und damit den Ablauf neu in Gang zu setzen, bis in alle Ewigkeit.

Anderseits kann man vermutlich Probleme umgehen, wenn man für jeden Thread seinen eigenen WaitHandle verwendet und eine zentrale Instanz entscheiden lässt, welcher dieser WaitHandle als nächster signalisiert wird.

herbivore

C
258 Beiträge seit 2011
vor 11 Jahren

Dafür habe ich einen weiteren, noch nicht genannten Punkt. Wenn Monitor tatsächlich nicht FIFO wäre, dann könnte dein Code Stravation verursachen, wenn immer wieder der gleiche Thread, der eigentlich noch nicht dran ist, sich vordrängelt und als erster die Sperre bekommt, nur um festzustellen, dass er noch nicht dran ist und damit den Ablauf neu in Gang zu setzen, bis in alle Ewigkeit.

Das sollte nicht Passieren, da die vorgedrängelten Threads auf das Wait laufen, und dort solange stehen bis ein Thread im Dispose() das PulseAll() aufruft. Zumindest nach meinem Verständniss.

5.941 Beiträge seit 2005
vor 11 Jahren

Hallo

Zu:

if (!lockObject.GetType().Name.Equals("Object", StringComparison.InvariantCultureIgnoreCase))

Könnte man so sauberer umsetzen:


if(lockObject.GetType() != typeof(object))

Gruss Peter

--
Microsoft MVP - Visual Developer ASP / ASP.NET, Switzerland 2007 - 2011

C
258 Beiträge seit 2011
vor 11 Jahren

So das ganze nochmal überarebietet:

 
    public class Lock : IDisposable
    {
        private readonly object lockObject;
        private static readonly ConcurrentDictionary<object, Ticket> Tickets = new ConcurrentDictionary<object, Ticket>();

        public Lock(object lockObject)
        {
            if (lockObject.GetType() != typeof(object))
                throw new ArgumentException("lockObject");

            this.lockObject = lockObject;
            Ticket ticket = Tickets.GetOrAdd(this.lockObject, (key) => new Ticket() { TicketCount = 0, CurrentTicket = 1 });

            int myTicket = Interlocked.Increment(ref ticket.TicketCount);
            Monitor.Enter(this.lockObject);

            while (true)
            {
                if (myTicket == ticket.CurrentTicket)
                    return;

                Monitor.Wait(this.lockObject);
            }
        }

        public void Dispose()
        {
            if (this.lockObject != null)
            {
                Interlocked.Increment(ref Tickets[this.lockObject].CurrentTicket);
                Monitor.PulseAll(this.lockObject);
                Monitor.Exit(this.lockObject);
            }
        }

        private class Ticket
        {
            public volatile int CurrentTicket;
            public volatile int TicketCount;
        }
    }
U
1.688 Beiträge seit 2007
vor 10 Jahren

Wenn Monitor tatsächlich nicht FIFO wäre, dann könnte dein Code Stravation verursachen, wenn immer wieder der gleiche Thread, der eigentlich noch nicht dran ist, sich vordrängelt und als erster die Sperre bekommt, nur um festzustellen, dass er noch nicht dran ist und damit den Ablauf neu in Gang zu setzen, bis in alle Ewigkeit.

Interessanterweise tritt aber genau das bei den CRITICAL_SECTION's in Windows seit Vista/Windows 2003 SP1 auf:
CriticalSection Changed
Man will wohl damit Leistungseinbußen vermeiden:
Critical Section Objects

Wir hatten gerade den Fall, wo das Problem nicht durch Sleep, sondern durch ein per Timeout zeitlich begrenztes blockierendes Lesen von externer Hardware verursacht wurde (C++ Anwendung mit herstellerspezifischer DLL). Eine andere "Lösung", als durch Sleep(1) nach dem Unlock das alte Verhalten nachzustellen, konnte ich nicht finden.

Es ist schon unschön, wenn die Software solche Interna berücksichtigen muss bzw. davon abhängig ist.