CAS döngüsünde yeniden denemeler
Görev tanımı
Problem
Birkaç thread kendi miktarını kilit (lock) olmadan tek bir paylaşılan değere ekliyor. Her thread iki adım üzerinde döner: paylaşılan değeri özel bir snapshot'a oku, sonra compare-and-swap yap. Swap yalnız paylaşılan değer hâlâ snapshot'a eşitse başarılı olur; o zaman snapshot + amount yazar ve thread işini bitirir. Değilse swap başarısız olur, hiçbir şey yazılmaz ve thread taze bir okumayla baştan başlar. Sana başlangıç değeri, her thread'in miktarı ve her elemanı o thread'in bir sonraki adımını atmasına izin veren thread numaralarından oluşan zamanlama listesi veriliyor. İşini bitirmiş bir thread'e ait elemanlar yok sayılır. Son değeri ve her thread'in kaç swap kaybettiğini döndür.
Örnekler
Input: start = 0, amounts = [5, 7], schedule = [0, 1, 0, 1, 1, 1]
Output: (12, [0, 1])
Neden: thread 1'in swap'i başarısız, çünkü thread 1 okuduktan sonra thread 0 değeri değiştirdi; yeniden okuyup tekrar dener
Input: start = 0, amounts = [1, 1, 1], schedule = [0, 1, 2, 0, 1, 2, 1, 2, 1, 2, 2, 2]
Output: (3, [0, 1, 2])
Neden: üçü de 0 okuyor, her turda yalnız bir swap kazanabilir ve thread 2 iki kez kaybeder
Input: start = 10, amounts = [3], schedule = [0, 0]
Output: (13, [0])
Neden: edge case: başka yazan yokken ilk swap her zaman başarılı olur
İpuçları
0 / 3
Düz bir okuma ve yazmanın aksine başarısız bir swap hiçbir şeyin üzerine yazmaz. Çekişmenin bedeli kaybolan güncellemelerden yeniden denemelere kayar.
Her thread'in bir snapshot'a, ya da bir sonraki adımının okuma olduğunu gösteren bir işarete, bir de bitip bitmediğini gösteren bir bayrağa ihtiyacı var.
Zamanlamayı dolaş. Bitmiş thread'leri atla. Okumada paylaşılan değeri snapshot olarak sakla. Swap'te paylaşılan değeri snapshot'la karşılaştır: eşitse snapshot + amount yaz ve bitir; değilse bir başarısızlık say ve sonraki adım okuma olsun diye snapshot'ı temizle.
- Hedef zaman
- O(s)
- Hedef alan
- O(t)
Çözüm
Bir compare-and-swap döngüsü, kilidin yerine iyimser bir kontrol koyar: yazma yalnız bu thread okuduğundan beri değeri kimse değiştirmediyse olur. Simülasyon bu kontrolün ihtiyaç duyduğu şeyi tutar: thread başına bir snapshot artı bitip bitmediği; None snapshot da thread'in bir sonraki adımının okuma olduğu anlamına gelir. Başarısız bir swap hiçbir şey yazmaz ve thread'i yeniden okumaya gönderir; böylece her miktar tam bir kez eklenir ve son değer her zaman başlangıç artı toplamdır, lost update yarışından farkı da bu. Çekişmenin bunun yerine bedeli yeniden denemelerdir; ikinci örnek bunların sürekli kaybeden thread'in üstüne yığıldığını gösterir. s adımlık bir zamanlama için zaman O(s), t thread için alan O(t).
def cas_add(start, amounts, schedule):
value = start # the shared value
snap = [None] * len(amounts) # None means the next step is a read
done = [False] * len(amounts)
failed = [0] * len(amounts)
for t in schedule:
if done[t]:
continue # finished threads take no more steps
if snap[t] is None:
snap[t] = value # read into a private snapshot
elif value == snap[t]:
value = snap[t] + amounts[t] # the swap wins: nobody wrote in between
done[t] = True
else:
failed[t] += 1 # someone got there first: retry from a read
snap[t] = None
return value, failed
print(cas_add(0, [5, 7], [0, 1, 0, 1, 1, 1])) # -> (12, [0, 1])
print(cas_add(0, [1, 1, 1], [0, 1, 2, 0, 1, 2, 1, 2, 1, 2, 2, 2])) # -> (3, [0, 1, 2])
print(cas_add(10, [3], [0, 0])) # -> (13, [0])Kodda değil de fikirde mi takıldın? Compare-and-swap bunu anlatıyor.