İçeriğe geç

CAS döngüsünde yeniden denemeler

Kolay#compare-and-swap#step-simulation~15 dk

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

Hedef zaman
O(s)
Hedef alan
O(t)

Kodda değil de fikirde mi takıldın? Compare-and-swap bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case