Paylaşılan sayaçta kayıp güncellemeler
Görev tanımı
Problem
Birkaç thread tek bir sayacı paylaşıyor ve her thread birkaç kez count += 1 çalıştırıyor. Her artırma aslında üç adımdır: sayacı thread'in kendi register'ına oku, register'a bir ekle, register'ı geri yaz. Sana thread sayısı ve işletim sisteminin seçtiği zamanlama, thread numaralarından oluşan bir liste olarak veriliyor: her eleman o thread'in bir sonraki adımını atmasına izin verir. Her thread bütün adımlarını bitirir. 0'dan başlayan sayacın son değerini döndür.
Örnekler
Input: threads = 2, schedule = [0, 0, 0, 1, 1, 1]
Output: 2
Neden: thread 0 artırmasını thread 1 okumadan bitiriyor, hiçbir şey kaybolmuyor
Input: threads = 2, schedule = [0, 1, 0, 1, 0, 1]
Output: 1
Neden: iki thread de 0 okuyor, ikisi de 1 yazıyor ve bir artırma kayboluyor
Input: threads = 1, schedule = [0, 0, 0, 0, 0, 0]
Output: 2
Neden: edge case: tek bir thread kendisiyle asla yarışamaz
İpuçları
0 / 3
Tek durum paylaşılan sayaç değil. Her thread'in daha önce okuduğu özel bir kopyası da var ve o kopya bayatlayabilir.
Her thread için register'ını ve üç adımdan hangisini sırada attığını takip et. Adım oku, ekle, yaz, oku diye döner.
Zamanlamayı dolaş. Okumada sayacı thread'in register'ına kopyala; eklemede register'a bir ekle; yazmada sayacın üzerine register'ı yaz. Sonra o thread'i bir sonraki adımına geçir.
- Hedef zaman
- O(s)
- Hedef alan
- O(t)
Kısıtlar
- every thread finishes all of its steps
Çözüm
Bir data race'teki hata, bir okuma ile ona karşılık gelen yazma arasındaki boşlukta yaşar; bu yüzden simülasyon tam olarak o boşluğun ihtiyaç duyduğu durumu tutar: thread başına bir register ve her thread'in sırada hangi adımı attığı. Okuma paylaşılan değeri kopyalar, ekleme yalnız özel kopyayı değiştirir, yazma da özel kopyayı sayacın o an tuttuğu değerin üzerine yazar; bu, arada gelmiş her artırmayı sessizce siler. Bu yüzden zamanlamayı adım adım yeniden oynatmak, kaybolan güncellemeyi donanımın yapacağı gibi birebir üretir. s adımlık bir zamanlama için zaman O(s), t thread için alan O(t).
def final_count(threads, schedule):
count = 0 # the shared counter
reg = [0] * threads # each thread's private register
step = [0] * threads # 0 = read, 1 = add, 2 = write
for t in schedule:
if step[t] == 0:
reg[t] = count # read the shared value
elif step[t] == 1:
reg[t] += 1 # add one to the private copy
else:
count = reg[t] # write back, possibly over a newer value
step[t] = (step[t] + 1) % 3
return count
print(final_count(2, [0, 0, 0, 1, 1, 1])) # -> 2
print(final_count(2, [0, 1, 0, 1, 0, 1])) # -> 1
print(final_count(1, [0, 0, 0, 0, 0, 0])) # -> 2
print(final_count(2, [0, 1, 1, 1, 0, 0, 0, 0, 0])) # -> 2Kodda değil de fikirde mi takıldın? Race condition'lar bunu anlatıyor.