testi ile Karşılıklı Dışlama Sınırlı-bekleyen ve

Question

I (Avi Silberschatz Peter Baer Galvin Greg Gagne) baskı 9 ünlü İşletim Sistemi Kavramları kitap okuyorum ayarlayın: süreç senkronizasyonu bölümde http://codex.cs.yale.edu/avi/os-book/OS9/

, bir var aşağıdaki gibi "test_and_set ile Karşılıklı Dışlama Sınırlı-bekleme" için algoritması: I (3., yukarıdaki kod 4. ve 5. hatlar kullanılır) boolean değişken key rolünü göremiyorum

do { 
    waiting[i] = true; 
    key = true; // <-- Boolean variable that I do not see its utility 
    while (waiting[i] && key) // <-- the value of the key variable here is always true 
     key = test_and_set(&lock); // <-- it might become false here, but what is the point? 
    waiting[i] = false; 

    /* critical section */ 

    j = (i + 1) % n; 
    while ((j != i) && !waiting[j]) 
     j = (j + 1) % n; 
    if (j == i) 
     lock = false; 
    else 
     waiting[j] = false; 

    /* remainder section */ 
} while (true); 

, ben Algoritma üzerinde herhangi bir etkisi olmadan onu kaldırabileceğimizi görüyorum, haklı mıyım yoksa bir şeyleri özledim mi?

Answer 1

Sen hiç algoritma basitleştirmek olabilir:

do { 
    waiting[i] = true; 
    while (waiting[i] && test_and_set(&lock)) ; 
    waiting[i] = false; 

    /* critical section */ 

    j = (i + 1) % n; 
    while ((j != i) && !waiting[j]) 
     j = (j + 1) % n; 
    if (j == i) 
     lock = false; 
    else 
     waiting[j] = false; 

    /* remainder section */ 
} while (true); 

ve tamamen aynı olurdu. Yazarlar, key'u kullandılar çünkü kodun okunmasını daha kolay hale getireceğini düşündüler.

olarak yorumlarda sordu: Genellikle

, test_and_set kullanarak sadece while(test_and_set(&lock)) ; yapmak. Ancak bu durumda, iş parçacığının yalnızca kilit için sınırlı bir süre beklediğinden emin olmak istersiniz. Bu, waiting dizisiyle gerçekleştirilir. Kilit açtığımız kritik bölümün sonunda, lock'u yanlış olarak ayarlamayız; Bunun yerine, kilidi bekleyen sonraki parçayı bulmaya çalışıyoruz. Sırada, iplik kimliğini arttırmak ve n (j = (j + 1) % n; bölüm) 'e vurduğumuzda döngü yapmak demek istiyorum. j numaralı bir iş parçacığı bulunursa, lock yerine waiting[j] değerini false olarak ayarladık.

Bu, 2 veya daha fazla iş parçacığının sürekli olarak kilidi kaparken başka bir iş parçacığı veya iş parçacığı grubu her zaman beklediği senaryoları engeller. Örneğin, aynı kilit için 3 iş parçacığı beklediğini söyleyin (iş parçacığı 0, 1 ve 2). İş parçacığı 0, kilidi serbest bırakır ve iş parçacığı 1 onu alır. İplik 1, kilit dişi 0'a sahipken, daha sonra kilidi tekrar yakalamaya çalışır ve iplik 1 serbest bırakıldığında, kilit ipliği 0, iplik 2 yerine kavrar. Bu, sonsuza kadar tekrarlanabilir ve iplik 2, kilidi asla alamaz.

Bu sınırlayıcı bekleme algoritmasında waiting dizisini kullanarak bu davranış oluşmaz. Üç iş parçacığı sürekli olarak tutuluyorsa, sonraki iş parçacığı için sonraki iş parçacığı kilitlenir, örneğin, iş parçacığı 0, sonra iş parçacığı 1 ve sonra iş parçacığı 2 tarafından takip kilit ve serbest bırakacaktır. Bunun nedeni, her iş parçacığının lock ya da waiting dizisindeki girdisi false haline gelmesidir. Bir iş parçacığı kilidi serbest bırakmak üzere olduğunda başka bir evre kilitlenmeyi beklerse, lock yerine waiting girişini döndürür, yalnızca döndürme beklemede bu iş parçacığı serbest bırakır. Bu, kilit için süresiz olarak bekleyen bir veya daha fazla iş parçacığının patolojik durumunu önler.