Semafor (programlama) - Semaphore (programming)

Bir semafor (Flemenkçe: Seinpaal, Dijkstra'nın orijinal açıklamasında kullanılan terim[1]).

İçinde bilgisayar Bilimi, bir semafor bir değişken veya soyut veri türü birden çok kişi tarafından ortak bir kaynağa erişimi kontrol etmek için kullanılır süreçler içinde eşzamanlı gibi bir sistem çoklu görev işletim sistemi. Bir semafor basitçe bir değişkendir. Bu değişken çözmek için kullanılır kritik Bölüm sorunlar ve çoklu işlem ortamında süreç senkronizasyonu elde etmek. Önemsiz bir semafor, programcı tarafından tanımlanan koşullara bağlı olarak değiştirilen (örneğin, artırılmış veya azaltılmış veya geçişli) düz bir değişkendir.

Gerçek dünya sisteminde kullanıldığı şekliyle bir semaforu düşünmenin yararlı bir yolu, belirli bir kaynağın kaç biriminin mevcut olduğunun ve bu kaydı ayarlamak için yapılan işlemlerin bir kaydıdır. güvenli bir şekilde (yani kaçınmak için yarış koşulları ) birimler alındıkça veya serbest kaldıkça ve gerekirse kaynağın bir birimi kullanılabilir hale gelene kadar bekleyin.

Semaforlar, yarış koşullarının önlenmesinde yararlı bir araçtır; ancak bunların kullanımı hiçbir şekilde bir programın bu sorunlardan arınmış olduğunun garantisi değildir. Keyfi kaynak sayımına izin veren semaforlar semaforları saymak0 ve 1 değerleri ile sınırlı olan semaforlar (veya kilitli / kilidi açık, kullanılamaz / kullanılabilir) çağrılırken ikili semaforlar ve uygulamak için kullanılır kilitler.

Semafor kavramı tarafından icat edildi Flemenkçe bilgisayar uzmanı Edsger Dijkstra 1962 veya 1963'te,[2] Dijkstra ve ekibi bir işletim sistemi için Electrologica X8. Bu sistem sonunda şu şekilde bilinir hale geldi: Çoklu programlama sistemi.

Kütüphane benzetmesi

Bir kütüphanede, her seferinde bir öğrenci tarafından kullanılacak 10 özdeş çalışma odası olduğunu varsayalım. Bir çalışma odasını kullanmak isteyen öğrenciler ön bürodan bir oda talep etmelidir. Hiçbir oda boş değilse, öğrenciler biri odayı terk edene kadar masada beklerler. Bir öğrenci bir odayı kullanmayı bitirdiğinde, öğrenci masaya geri dönmeli ve bir odanın boş olduğunu belirtmelidir.

En basit uygulamada, ön bürodaki görevli yalnızca mevcut boş oda sayısını bilir; bu, yalnızca tüm öğrenciler onlar için kayıt olurken odalarını gerçekten kullanırsa ve iş bitince geri verirse doğru bir şekilde bilirler. . Bir öğrenci oda istediğinde, katip bu sayıyı azaltır. Bir öğrenci bir odayı serbest bıraktığında, katip bu sayıyı artırır. Oda istenildiği kadar uzun süre kullanılabilir ve bu nedenle önceden oda rezervasyonu yapmak mümkün değildir.

Bu senaryoda, ön büro sayaç sahibi bir sayım semaforunu temsil eder, odalar kaynaktır ve öğrenciler süreçleri / konuları temsil eder. Bu senaryoda semaforun değeri başlangıçta 10'dur ve tüm odalar boştur. Bir öğrenci bir oda talep ettiğinde, ona erişim izni verilir ve semaforun değeri 9 olarak değiştirilir. Bir sonraki öğrenci geldiğinde, 8'e, sonra 7'ye vb. Düşer. Birisi bir oda isterse ve semaforun mevcut değeri 0 ise,[3] bir oda serbest kalana kadar beklemeye zorlanırlar (sayı 0'dan artırıldığında). Odalardan biri serbest bırakıldıysa, ancak bekleyen birkaç öğrenci varsa, odayı işgal edecek olanı seçmek için herhangi bir yöntem kullanılabilir (örneğin FIFO veya yazı tura atmak). Ve tabii ki, bir öğrencinin odasını ancak gerçekten terk ettikten sonra serbest bırakılması konusunda bilgi vermesi gerekir, aksi takdirde, bu öğrenci odadan çıkma sürecinde (ders kitaplarını topluyorlar vb.) Garip bir durum olabilir. ve başka bir öğrenci odadan çıkmadan önce girer.

Önemli gözlemler

Erişim kontrolü için kullanıldığında havuz kaynaklar, yalnızca semafor izleri kaç kaynaklar ücretsizdir; takip etmiyor hangi kaynakların% 'si ücretsizdir. Belirli bir serbest kaynağı seçmek için başka bir mekanizma (muhtemelen daha fazla semafor içeren) gerekebilir.

Paradigma özellikle güçlüdür çünkü semafor sayısı bir dizi farklı eylem için yararlı bir tetikleyici işlevi görebilir. Yukarıdaki kütüphaneci, öğrenci kalmadığında çalışma salonundaki ışıkları kapatabilir veya odaların çoğu dolu olduğunda odaların çok meşgul olduğunu belirten bir işaret koyabilir.

Protokolün başarısı, uygulamaların onu doğru şekilde takip etmesini gerektirir. Adalet ve güvenlikten taviz verilmesi muhtemeldir (bu, pratik olarak bir programın yavaş davranabileceği, düzensiz davranabileceği anlamına gelir. asmak veya çökmek ) tek bir işlem bile yanlış davranıyorsa. Bu içerir:

  • bir kaynak talep etmek ve onu serbest bırakmayı unutmak;
  • asla talep edilmeyen bir kaynağı serbest bırakmak;
  • bir kaynağı ihtiyaç duymadan uzun süre tutmak;
  • bir kaynağı talep etmeden (veya serbest bıraktıktan sonra) kullanmak.

Tüm işlemler bu kurallara uysa bile, çoklu kaynak kilitlenme Farklı semaforlar tarafından yönetilen farklı kaynaklar olduğunda ve süreçlerin bir seferde birden fazla kaynak kullanması gerektiğinde, yemek filozofları sorunu.

Anlambilim ve uygulama

Semafor sayma, tarihsel olarak P ve V olarak adlandırılan iki işlemle donatılmıştır (bkz. § İşlem adları alternatif isimler için). İşlem V semaforu artırır Sve P operasyonu bunu azaltır.

Semaforun değeri S şu anda mevcut olan kaynak birimlerinin sayısıdır. P işlemi zaman harcıyor veya uyur semafor tarafından korunan bir kaynak kullanılabilir hale gelene kadar, bu zamanda kaynak hemen talep edilir. V işlemi tersidir: İşlem onu ​​kullanmayı bitirdikten sonra bir kaynağı tekrar kullanılabilir hale getirir. Semaforun önemli bir özelliği S V ve P işlemleri dışında değerinin değiştirilemeyeceğidir.

Anlamanın basit bir yolu Bekle (P) ve sinyal (V) işlemleri:

  • Bekle: Semafor değişkeninin değerini 1 azaltır. Semafor değişkeninin yeni değeri negatifse, işlem yürütülür. Bekle engellenir (yani semaforun kuyruğuna eklenir). Aksi takdirde, işlem kaynağın bir birimini kullanarak yürütmeye devam eder.
  • sinyal: Semafor değişkeninin değerini 1 artırır. Artıştan sonra, ön artış değeri negatifse (yani, bir kaynağı bekleyen süreçler varsa), semaforun bekleme kuyruğundan hazır kuyruğuna bloke edilmiş bir işlemi aktarır.

Çoğu işletim sistemi, semafor artırıldığında bir bekleme sürecinin engelini kaldıran verimli semafor ilkelleri sağlar. Bu, süreçlerin semafor değerini kontrol ederek gereksiz yere zaman kaybetmediği anlamına gelir.

Sayma semafor kavramı, semafordan birden fazla "birim" talep etme veya iade etme yeteneği ile genişletilebilir, bu teknik Unix. Değiştirilmiş V ve P işlemleri, köşeli parantezler kullanılarak aşağıdaki gibidir atomik işlemler diğer süreçler açısından bölünemez görünen işlemler:

işlevi V (semafor S, tam sayı I): [S ← S + I]işlevi P (semafor S, tam sayı I): tekrar et:        [Eğer S ≥ I: S ← S - I kırmak]

Bununla birlikte, bu bölümün geri kalanı, aksi belirtilmedikçe, tekli V ve P işlemlerine sahip semaforlara atıfta bulunur.

Kaçınmak açlık semaforun ilişkili bir kuyruk süreçlerin (genellikle FIFO anlambilim). Bir işlem, sıfır değerine sahip bir semafor üzerinde bir P işlemi gerçekleştirirse, işlem semaforun kuyruğuna eklenir ve yürütülmesi askıya alınır. Başka bir işlem bir V işlemi gerçekleştirerek semaforu artırdığında ve kuyrukta işlemler varsa, bunlardan biri kuyruktan çıkarılır ve yürütmeye devam eder. İşlemlerin farklı öncelikleri olduğunda, kuyruk önceliğe göre sıralanabilir, böylece en yüksek öncelikli işlem önce kuyruktan alınır.

Uygulama, artırma, azaltma ve karşılaştırma işlemlerinin atomikliğini sağlamazsa, artma veya azalmanın unutulma veya semafor değerinin negatif olma riski vardır. Atomiklik, yapabilen bir makine talimatı kullanılarak elde edilebilir. oku, değiştir ve yaz semafor tek bir işlemde. Böyle bir donanım talimatının yokluğunda, bir atomik işlem, bir atomik işlemin kullanılmasıyla sentezlenebilir. yazılım karşılıklı dışlama algoritması. Açık tek işlemcili sistemler, atomik işlemler geçici olarak askıya alınarak sağlanabilir ön kabul veya donanımı devre dışı bırakma keser. Bu yaklaşım, bir semaforu paylaşan iki programın aynı anda farklı işlemcilerde çalışmasının mümkün olduğu çok işlemcili sistemlerde çalışmaz. Bu problemi çok işlemcili bir sistemde çözmek için semafora erişimi kontrol etmek için bir kilitleme değişkeni kullanılabilir. Kilitleme değişkeni, bir test ve set kilidi komut.

Örnekler

Önemsiz örnek

Bir değişken düşünün Bir ve bir boole değişkeni S. Bir sadece ne zaman erişilir S doğru olarak işaretlendi. Böylece, S için bir semafor Bir.

Bir stop lambası sinyali düşünülebilir (S) tren istasyonundan hemen önce (Bir). Bu durumda sinyal yeşil ise tren istasyonuna girilebilir. Sarı veya kırmızıysa (veya başka bir renkte), tren istasyonuna erişilemez.

Giriş sırası

Yalnızca on kullanıcıyı destekleyebilen bir sistem düşünün (S = 10). Bir kullanıcı oturum açtığında, P çağrılır ve semaforu azaltır. S 1. Bir kullanıcı oturumu kapattığında, V çağrılır ve S 1 kullanılabilir hale gelen bir oturum açma yuvasını temsil eder. Ne zaman S 0, giriş yapmak isteyen herhangi bir kullanıcının şu tarihe kadar beklemesi gerekir: S > 0 ve oturum açma isteği bir FIFO kuyruğuna sıralanır; Karşılıklı dışlama isteklerin sırayla sıralanmasını sağlamak için kullanılır. Her ne zaman S 0'dan büyük hale gelir (oturum açma yuvaları kullanılabilir), bir oturum açma isteği geri alınır ve isteğe sahip olan kullanıcının oturum açmasına izin verilir.

Üretici-tüketici sorunu

İçinde üretici-tüketici sorunu, bir süreç (üretici) veri öğeleri üretir ve başka bir süreç (tüketici) bunları alır ve kullanır. Maksimum büyüklükte bir sıra kullanarak iletişim kurarlar N ve aşağıdaki koşullara tabidir:

  • kuyruk boşsa tüketici üreticinin bir şeyler üretmesini beklemelidir;
  • Üretici kuyruk doluysa tüketicinin bir şeyler tüketmesini beklemelidir.

Üretici-tüketici problemine yönelik semafor çözümü, sıranın durumunu iki semaforla izler: emptyCount, kuyruktaki boş yerlerin sayısı ve fullCount, kuyruktaki öğelerin sayısı. Bütünlüğü korumak için, emptyCount kuyruktaki gerçek boş yer sayısından daha düşük olabilir (ancak hiçbir zaman yüksek olmayabilir) ve fullCount kuyruktaki gerçek öğe sayısından daha düşük olabilir (ancak hiçbir zaman yüksek olmayabilir). Boş yerler ve öğeler iki tür kaynağı temsil eder, boş kutular ve dolu kutular ve semaforlar emptyCount ve fullCount bu kaynaklar üzerinde kontrolü sürdürmek.

İkili semafor useQueue Örneğin, iki üreticinin eşzamanlı olarak boş bir kuyruğa öğe eklemeye çalışarak iç durumunu bozarak kuyruğun kendi durumunun bütünlüğünden ödün verilmemesini sağlar. Alternatif olarak a muteks ikili semafor yerine kullanılabilir.

emptyCount başlangıçta N, fullCount başlangıçta 0 ve useQueue başlangıçta 1'dir.

Üretici aşağıdakileri tekrar tekrar yapar:

üretmek:    P (emptyCount) P (useQueue) putItemIntoQueue (öğe) V (useQueue) V (fullCount)

Tüketici aşağıdakileri tekrar tekrar yapar

tüketmek:    P (fullCount) P (useQueue) öğesi ← getItemFromQueue () V (useQueue) V (emptyCount)

Aşağıda önemli bir örnek verilmiştir:

  1. Tek bir tüketici kritik bölümüne girer. Dan beri fullCount 0, tüketici blokları.
  2. Üretici kritik bölümüne birkaç üretici giriyor. Den fazla değil N üreticiler kritik bölümlerine girebilirler. emptyCount girişlerini kısıtlamak.
  3. Üreticiler, sıraya teker teker erişim sağlar. useQueue ve sıradaki öğeleri yatırın.
  4. İlk üretici kritik bölümünden çıktığında, fullCount artırılarak bir tüketicinin kritik bölümüne girmesine izin verilir.

Bunu not et emptyCount Kuyruktaki gerçek boş yer sayısından çok daha düşük olabilir, örneğin, birçok üreticinin listeyi düşürdüğü ancak sırasını beklediği durumlarda useQueue boş yerleri doldurmadan önce. Bunu not et emptyCount + fullCount ≤ N her zaman eşitlikle, ancak ve ancak üretici veya tüketicilerin kritik bölümlerini yürütmemesi durumunda geçerlidir.

Operasyon adları

Kanonik isimler V ve P'nin baş harfleri Flemenkçe kelimeler. V genellikle şu şekilde açıklanır: verhogen ("artırmak"). P için aşağıdakiler de dahil olmak üzere çeşitli açıklamalar sunulmuştur: Proberen ("test etmek" veya "denemek"),[4] Passeren ("geçiş") ve Pakken ("kapmak"). Dijkstra'nın konuyla ilgili en eski makalesi[2] verir geçen ("geçme") anlamı olarak P, ve Vrijgave V'nin anlamı olarak ("serbest bırakma"). Ayrıca, terminolojinin demiryolu sinyallerinde kullanılanlardan alındığından da söz edilmektedir. Dijkstra, sonradan, P için durmak Portmanteau prolaag,[5] kısaltması probeer te verlagen, kelimenin tam anlamıyla "azaltmaya çalışın" veya diğer durumda kullanılan terimlere paralel olarak "azaltmaya çalışın".[6][7][8]

İçinde ALGOL 68, Linux çekirdeği,[9] ve bazı İngilizce ders kitaplarında V ve P işlemler sırasıyla adlandırılır, yukarı ve aşağı. Yazılım mühendisliği uygulamasında, genellikle sinyal ve Bekle,[10] serbest bırakmak ve elde etmek[10] (hangi standart Java kütüphane[11] kullanır) veya İleti ve askı. Bazı metinler[12][13] onları ara boşaltmak ve temin etmek orijinal Hollandaca baş harfleriyle eşleşecek şekilde.

Semaforlar ve muteksler

Bir muteks bir Kilitleme mekanizması bu bazen ikili semaforla aynı temel uygulamayı kullanır. Aralarındaki farklar nasıl kullanıldıklarında. İkili bir semafor, konuşma dilinde muteks olarak adlandırılabilirken, gerçek bir muteksin daha spesifik bir kullanım durumu ve tanımı vardır; görev kilitlenen muteksin kilidini açması gerekiyor. Bu kısıtlama semaforları kullanmanın bazı olası sorunlarını ele almayı amaçlamaktadır:

  1. Öncelikli ters çevirme: Eğer muteks onu kimin kilitlediğini biliyorsa ve kilidini açması gerekiyorsa, muteks üzerinde daha yüksek öncelikli bir görev beklemeye başladığında o görevin önceliğini yükseltmek mümkündür.
  2. Erken görev sonlandırma: Muteksler ayrıca, muteksi tutan görevin kazara silinemeyeceği durumlarda silme güvenliği sağlayabilir.[kaynak belirtilmeli ]
  3. Sonlandırma kilitlenmesi: Bir muteks tutma görevi herhangi bir nedenle sona ererse, işletim sistemi bu koşulun muteks ve sinyal bekleyen görevlerini serbest bırakabilir.
  4. Özyineleme kilitlenmesi: bir görevin bir evresel muteks eşit sayıda açtığı için birden çok kez.
  5. Kazayla serbest bırakma: Serbest bırakma görevi sahibi değilse, muteksin yayınlanmasıyla ilgili bir hata oluşur.

Ayrıca bakınız

Referanslar

  1. ^ Dijkstra, Edsger W. Seinpalen üzerinde (EWD-74) (PDF). E.W. Dijkstra Arşivi. Amerikan Tarihi Merkezi, Austin'deki Texas Üniversitesi. (transkripsiyon )
  2. ^ a b Dijkstra, Edsger W. De sequentialiteit van procesbeschrijvingen (EWD-35) (PDF). E.W. Dijkstra Arşivi. Amerikan Tarihi Merkezi, Austin'deki Texas Üniversitesi. (transkripsiyon ) (tarihsiz, 1962 veya 1963)
  3. ^ Semaforların Küçük Kitabı Allen B. Downey
  4. ^ Silberschatz, Galvin ve Gagne 2008, s. 234
  5. ^ Dijkstra, Edsger W. EWD-74 (PDF). E.W. Dijkstra Arşivi. Amerikan Tarihi Merkezi, Austin'deki Texas Üniversitesi. (transkripsiyon )
  6. ^ Dijkstra, Edsger W. MULTIPROGAMMERING EN DE X8 (EWD-51) (PDF). E.W. Dijkstra Arşivi. Amerikan Tarihi Merkezi, Austin'deki Texas Üniversitesi. (transkripsiyon ) (içinde Flemenkçe )
  7. ^ Dijkstra'nın kendi çevirisi "dene-ve-düşür ", ancak bu ifade, farkında olmayanlar için kafa karıştırıcı olabilir. konuşma dilinde "dene ve ..."
  8. ^ (YAMA 1/19) MUTEX: Basit muteks uygulamasını tanıtın Linux Kernel Posta Listesi, 19 Aralık 2005
  9. ^ Linux Kernel hacking NASIL LinuxGrill.com
  10. ^ a b Mullender, Sape; Cox, Russ (2008). Plan 9'daki Semaforlar (PDF). 3. Uluslararası Çalıştay Plan 9.
  11. ^ java.util.concurrent.Semaphore
  12. ^ "exec.library / Procure". amigadev.elowar.com. Alındı 2016-09-19.
  13. ^ "exec.library / Vacate". amigadev.elowar.com. Alındı 2016-09-19.

Dış bağlantılar

Tanıtımlar

Referanslar