İçeriğe geç

Paylaşılan sayaçta kayıp güncellemeler

Kolay#race-condition#step-simulation~15 dk

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

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

Kısıtlar

  • every thread finishes all of its steps

Kodda değil de fikirde mi takıldın? Race condition'lar bunu anlatıyor.

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