Okuyucu ve editör sorunu

Okuyucu ve yazar problemi klasik bir sorundur bilgisayar teorisi mümkün erişimi modellemek için yapar, veritabanları .

Bu formda , filozofların akşam yemeği sorununun da (özellikle süreçlerin sıralanmasıyla ilgili sorun) kökeninde olan Edsger Dijkstra tarafından ifade edilmiştir .

Sorun

Bir veritabanının okuyucuları ve yazarları olduğunu ve bu veritabanının okuyucularının ve yazarlarının programlanması gerektiğini varsayalım .

Kısıtlamalar aşağıdaki gibidir:

• birkaç okuyucu aynı anda veritabanını okuyabilmelidir;
• bir düzenleyici veritabanını değiştiriyorsa, başka hiçbir kullanıcı (ne düzenleyici ne de okuyucu) veritabanına erişemez.

Çözümler

Hala okuyucular varken editörü beklemeye almak oldukça basittir.

Ancak okuyucu akışı düzenliyse, bu çözüm büyük sorunlar ortaya çıkarır: editörün sonsuz bir süre beklemesi gerekebilir.

Bu nedenle, bir editörden sonra erişim taleplerini gönderen tüm okuyucuları beklemeye almaktan oluşan ikinci bir çözüm vardır.

Bu sorunu formüle eden Edsger Dijkstra , semaforlar aracılığıyla çözmeyi önermektedir .

Semafor kullanımıyla çözüm ve okuyuculara öncelik

Aşağıdaki çözüm , okuyuculara öncelik vererek okuyucuların ve yazarların sorununu çözmektedir . Bu çözüm üç semafor ve bir değişken gerektirir , yani:

• Değişkenin korunmasına izin veren, 1 olarak başlatılan bir M_Lect semaforu lect. Bu nedenle bir mutekstir .
• Yazma görevlerinin engellenmesine izin veren (okuyuculara öncelik vererek) 1 olarak başlatılan bir M_Red semaforu . Bu nedenle bir mutekstir .
• Yazma sürerken okuma görevlerinin engellenmesine izin veren, 1 olarak başlatılan bir Kırmızı semafor .
• lectOkuyucu sayısını sayan bir değişken .

Bu çözüm aşağıdaki dört yöntemi kullanır:

Okumaya başlamak Commencer_Lire: P(M_Lect) SI (red) ALORS pbloque=true V(M_Lect) p(synch) FIN SI SINON lect++; V(M_Lect)

Bu yöntem okuyucu sayısını artırır; o zaman, bu, girmeye çalışan ilk okuyucu ise, yalnızca geçerli yazı yoksa girişe izin verir. Aksi takdirde, yöntem taslak hazırlama bitene kadar beklemelidir. Editörler için iki semafor kullanılması, okuyuculara öncelik verilmesine izin verir.

Bir okumayı bitir Finir_Lire: P(M_Lect) lect-- SI Lect==0 ALORS V(Red) FIN SI V(M_Lect)

Bu yöntem okuyucu sayısını azaltır. Ardından, bu son okuyucu çıkıyorsa, editörlerin girmesine izin verir (gerekirse).

Bir yazmaya başlayın Commencer_Ecrire: P(M_Red) P(Red) SI (red or lect>0) ALORS pbloque=true V(Red) SINON red=true V(Red) V(M_Red)

M_Red semaforunu kullanan bu yöntem, bir yazarın sonunda okuyuculara öncelik verilmesini sağlamayı mümkün kılar (aslında bir yazarın sonu, M_Red semaforunu serbest bırakmadan önce Kırmızı semaforu serbest bırakır - böylece olası bir okuyucuyu serbest bırakır).

Bir yazıyı bitir Finir_Ecrire: V(Red) V(M_Red)

Bu yöntem, okuyuculara öncelik verilmesini sağlamayı mümkün kılar (aslında, Red semaforunu serbest bırakmak, M_Red semaforunu kullanarak olası bir düzenleyiciyi serbest bırakmadan önce olası bir okuyucuyu serbest bırakır).

Veri yapısının eşzamansız kopyası ile çözüm

Okuyucuların amacının verileri eşzamansız olarak okumak olduğunu varsayalım. Tüm okuyucular, taleplerinin yapıldığı sırada (muhtemelen uzak bir makineden) bilgilere sahiptir.

Veya mevcut tüm bilgileri içeren bir veri yapısına bir DATA işaretçisi . Editörler bir DOSYA kuyruğunda saklanacak istekler göndereceklerdir .

Bir M1 muteksi , aşağıdaki yapıyı korur:

Liste de DATA : PRECEDENT DATA : ACTUEL DATA : PROCHAIN booléen : MISAJOUR

M2 muteksi , aşağıdaki yapıyı korur:

File de mises à jour : FILE Date de dernière modification : DERNIER Okuyucu tarafından yürütülen kod verrouille M1: si MISAJOUR est vrai: enfile ACTUEL dans PRECEDENT pour chaque élément de PRECEDENT: effacer l'élément si son compteur de références est nul (1) fin pour ACTUEL := PROCHAIN (2) PROCHAIN := copie de ACTUEL MISAJOUR := faux fin si récupérer un pointeur P sur ACTUEL et incrémenter son compteur de références déverrouille M1 lire dans P ... décrémenter le compteur de références de P Yazar tarafından yürütülen kod verrouille M2: enfiler les modifications dans FILE si DERNIER est dépassé de 10 secondes: verrouiller M1: effectuer toute modification de FILE dans PROCHAIN vider FILE MISAJOUR := vrai (3) déverrouille M1 fin si déverrouille M2 Uyarılar

1. Veri yapısı güncellendiğinde, eski sürümü eşzamanlı hafif süreçlerde bir işaretçi olarak kalabilir . Bu nedenle bellek sızıntılarını önlemenin iyi bir yolu, daha fazla işlem kullanılmadığında işaretli bellek alanlarını silmek için bir referans sayacı tutmaktır.
2. CURRENT ve NEXT statik işaretçilerdir, ikinciyi birinciye kopyalamak bir işaretçi atamasına eşdeğerdir. İlk noktada söylendiği gibi, eski işaretçi daha önce yürütülen ışık işlemlerinde kalır. Öte yandan, aşağıdaki satırda, CURRENT tarafından belirtilen verilerin tam bir kopyası gerçekleştirilir ve kopyaya NEXT'i işaret eder.
3. Basitçe bu boole değerini true olarak ayarlamak , gelecekteki okuyucuların verilerin doğru sürümünü kullanmasına izin verecektir.

Bu model, güncellemelerin veri tabanlarının sağlaması gereken işlem yönetimini gerektirmediği durumlarda uygundur .

Ayrıca görün

• Luigi Zaffalon ve Pierre Breguet, ADA 95 ile eşzamanlı ve gerçek zamanlı programlama , Presses polytechniques et universitaire romandes, Lozan , 1999
• filozofların yemeği