Come sono fatte le code thread-safe in Python

4

Ammetto che questo mi è stato chiesto in intervista molto tempo fa, ma non mi sono mai preso la briga di controllarlo.

La domanda era semplice, come fa Python a fare Queue thread-safe?

La mia risposta è stata, a causa di Interpreter Lock (GIL), in qualsiasi momento solo 1 thread sta effettuando una chiamata per ottenere l'elemento dalla coda mentre altri stanno dormendo / aspettando. Ero / non sono ancora sicuro se è una risposta valida.

L'intervistatore sembrava insoddisfatto e ha chiesto se Queue s è thread-safe in Java o implementazione .Net di Python che non ha GIL? In tal caso, come implementano funzionalità thread-safe su detta struttura dati.

Ho provato a cercarlo, ma mi sembra sempre di imbattermi in how to use thread-safe queues .

Quindi in che modo Queue o semplice list può essere reso thread-safe ed evitare condizioni di competizione?

In alternativa, quali algoritmi o tecniche utilizzate dall'implementazione GEvent di% thread-safe% s?

    
posta Harsh Gupta 02.02.2018 - 13:31
fonte

1 risposta

4

Ti stai sbagliando che GIL avrebbe reso un programma Python privo di thread.

rende l'interprete stesso sicuro da solo

Ad esempio, diamo un'occhiata a una coda LIFO molto semplice (ovvero una pila). Ignoreremo che un list può già essere utilizzato come stack.

class Stack(object):
  def __init__(self, capacity):
    self.size = 0
    self.storage = [None] * capacity

  def push(self, value):
    self.storage[self.size] = value
    self.size += 1

  def pop(self):
    self.size -= 1
    result = self.storage[self.size]
    self.storage[self.size] = None
    return result

È questo thread-safe? Assolutamente no, nonostante sia in esecuzione sotto GIL.

Considera questa sequenza di eventi:

  • Il thread 1 aggiunge un paio di valori

    stack = Stack(5)
    stack.push(1)
    stack.push(2)
    stack.push(3)
    

    Lo stato ora è storage=[1, 2, 3, None, None] , size=3 .

  • Il thread 1 aggiunge un valore stack.push(4) ed è sospeso prima che la dimensione possa essere incrementata

    self.storage[self.size] = value
    # interrupted here
    self.size += 1
    

    Lo stato ora è storage=[1, 2, 3, 4, None] , size=3 .

  • Il thread 2 rimuove un valore stack.pop() che è 3 .

    Lo stato ora è storage=[1, 2, None, 4, None] , size=2 .

  • Il thread 1 viene ripreso

    self.storage[self.size] = value
    # resume here
    self.size += 1
    

    Lo stato ora è storage=[1, 2, None, 4, None] , size=3 .

Di conseguenza, lo stack è danneggiato: il valore inserito non può essere recuperato e l'elemento superiore è vuoto.

Il GIL linearizza solo gli accessi ai dati, ma questo è quasi completamente inutile per lo sviluppatore Python ordinario perché l'ordine delle operazioni è ancora imprevedibile. Cioè il GIL non può essere usato come un blocco a livello di Python, garantisce solo che i valori di tutte le variabili siano aggiornati ( volatile in C o Java). Le implementazioni Python senza GIL devono inoltre fornire questa proprietà per la compatibilità, ad es. utilizzando volatile accessi di memoria o utilizzando i propri blocchi. Jython è un'implementazione senza GIL che utilizza specificamente implementazioni thread-safe per dict , list e così via.

Poiché Python non garantisce alcun ordine di operazioni tra i thread, non sorprende che le strutture di dati thread-safe debbano utilizzare un lock. Ad esempio, la libreria standard queue.Queue class @ v3.6.4 ha un % membro dimutex e alcuni condvars che usano quel mutex. Tutti gli accessi ai dati sono adeguatamente custoditi. Tuttavia, si noti che questa classe non è principalmente intesa come struttura dei dati della coda, ma come coda di lavoro tra più thread. Una pura struttura dati non riguarderebbe solitamente il blocco.

Naturalmente, blocchi e mutex puzzano per vari motivi, ad es. a causa della possibilità di deadlock e perché l'acquisizione di una serratura è lenta. Di conseguenza, c'è un grande interesse per le strutture di dati senza blocco . Quando l'hardware fornisce determinate istruzioni atomiche, è possibile aggiornare una struttura di dati con una tale operazione atomica, ad es. sostituendo un puntatore. Ma questo tende ad essere piuttosto difficile da fare.

    
risposta data 02.02.2018 - 22:22
fonte

Leggi altre domande sui tag