Semafor (programlama) - Semaphore (programming)

Bu makale bilgisayar programlama terimi ile ilgili. Başlığın diğer anlamları için bkz Semafor (anlam ayrım) .
Bir semafor ( Hollandaca : seinpaal , Dijkstra'nın orijinal tanımında kullanılan terim).

Gelen bilgisayar bilimleri , bir semafor bir olan değişken veya soyut veri tipi çoklu bir ortak kaynağa erişimi kontrol için kullanılan süreçler ve önlemek kritik bölüm bir sorun eşzamanlı böyle bir şekilde sisteme çoklu görev işletim sistemi. Önemsiz bir semafor, programcı tarafından tanımlanan koşullara bağlı olarak değişen (örneğin, artan veya azalan veya değiştirilen) düz bir değişkendir.

Gerçek dünya sisteminde kullanılan bir semaforu düşünmenin yararlı bir yolu, belirli bir kaynağın kaç biriminin mevcut olduğunun bir kaydı olarak, birimler olarak bu kaydı güvenli bir şekilde ayarlamak için (yani, yarış koşullarından kaçınmak için ) işlemlerle birleştirilir. edinebilir veya özgürleşebilir 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ğunu garanti etmez. Rastgele bir kaynak sayımına izin veren semaforlara sayma semaforları denirken, 0 ve 1 değerleriyle sınırlandırılmış (veya kilitli/kilitsiz, kullanılamaz/mevcut) semaforlara ikili semaforlar denir ve kilitleri uygulamak için kullanılır .

Semafor kavramı, 1962 veya 1963'te, Dijkstra ve ekibi Electrologica X8 için bir işletim sistemi geliştirirken Hollandalı bilgisayar bilimcisi Edsger Dijkstra tarafından icat edildi . Bu sistem sonunda çoklu programlama sistemi olarak tanındı .

kütüphane benzetmesi

Bir kütüphanede her seferinde bir öğrenci tarafından kullanılmak üzere 10 özdeş çalışma odası olduğunu varsayalım. Çalışma odasını kullanmak isteyen öğrencilerin ön bürodan oda talep etmeleri gerekmektedir. Hiçbir oda boş değilse, öğrenciler biri odadan ayrılana kadar masada bekler. Bir öğrenci bir odayı kullanmayı bitirdiğinde, öğrenci sıraya geri dönmeli ve bir odanın boş olduğunu belirtmelidir.

En basit uygulamada, katip de ön büro öğrencilerin tümü aslında kendileri için kaydolduğunuzdan ederken onların odasını kullanabilir, bunları dönerseniz İşleri bitince onlar sadece doğru bilmek boş odaların sadece numarasını bilir . Öğrenci oda talep ettiğinde görevli bu sayıyı düşürür. Bir öğrenci bir odayı boşalttığında, katip bu sayıyı artırır. Oda istenildiği kadar kullanılabilir ve bu nedenle önceden oda rezervasyonu yapmak mümkün değildir.

Bu senaryoda, ön büro sayım sahibi bir sayma semaforunu temsil eder, odalar kaynaktır ve öğrenciler süreçleri/parçaları temsil eder. Bu senaryodaki semaforun değeri, tüm odalar boşken başlangıçta 10'dur. Bir öğrenci oda talep ettiğinde erişim izni verilir ve semaforun değeri 9 olarak değiştirilir. Bir sonraki öğrenci geldiğinde 8'e düşer, ardından 7'ye vb. Birisi bir oda talep ederse ve semaforun mevcut değeri 0 ise, bir oda serbest kalana kadar (sayı 0'dan artırıldığında) beklemek zorunda kalırlar. Odalardan biri serbest bırakıldıysa, ancak bekleyen birkaç öğrenci varsa, odayı kimin işgal edeceğini seçmek için herhangi bir yöntem kullanılabilir ( FIFO veya yazı tura atmak gibi ). Ve elbette, bir öğrencinin, ancak gerçekten çıktıktan sonra odasından ayrıldığını görevliye bildirmesi gerekir, aksi takdirde, bu tür bir öğrenci odadan ayrılma sürecindeyken (ders kitaplarını paketliyorlar, vb.) ve başka bir öğrenci, onlar ayrılmadan önce odaya girer.

Önemli gözlemler

Bir kaynak havuzuna erişimi denetlemek için kullanıldığında , bir semafor yalnızca kaç kaynağın boş olduğunu izler ; hangi kaynakların ücretsiz olduğunu takip etmez . 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 salonunun ışıklarını kapatabilir veya odaların çoğu doluyken odaların çok meşgul olduğuna dair bir işaret koyabilir.

Protokolün başarısı, uygulamaların onu doğru bir şekilde takip etmesini gerektirir. Adil ve güvenlik olasıdır (pratik bir program düzensiz, hareket, yavaş davranabilir anlamına gelir tehlikeye için askıda veya kilitlenme da tek bir işlem hatalı hareket ise). Bu içerir:

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

Tüm süreçler bu kuralları takip etse bile , yemek felsefecileri probleminde gösterildiği gibi, farklı semaforlar tarafından yönetilen farklı kaynaklar olduğunda ve süreçlerin bir seferde birden fazla kaynak kullanması gerektiğinde çoklu kaynak kilitlenmesi ortaya çıkabilir .

Semantik ve uygulama

Sayma semaforları, geçmişte P ve V olarak belirtilen iki işlemle donatılmıştır ( alternatif adlar için bkz. § İşlem adları). İşlem V semaforunu S artırır ve işlem P onu azaltır.

S semaforunun değeri , kaynağın şu anda mevcut olan birimlerinin sayısıdır. P işlemi , semafor tarafından korunan bir kaynak kullanılabilir hale gelene kadar zaman harcar veya uyur , bu sırada kaynak hemen talep edilir. V işlemi bunun tersidir: işlemin kullanımı bittikten sonra bir kaynağı tekrar kullanılabilir hale getirir. S semaforunun önemli bir özelliği , değerinin V ve P işlemleri kullanılmadan değiştirilememesidir.

Bekleme (P) ve sinyal (V) işlemlerini anlamanın basit bir yolu şudur:

  • wait : Semafor değişkeninin değerini 1 azaltır. Semafor değişkeninin yeni değeri negatifse, wait yürüten süreç bloke edilir (yani, semaforun kuyruğuna eklenir). Aksi takdirde süreç, 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ım değeri negatifse (yani bir kaynağı bekleyen işlemler var), engellenen bir işlemi semaforun bekleme kuyruğundan hazır kuyruğa aktarır.

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

Sayma semaforu kavramı, Unix'te uygulanan bir teknik olan semafordan birden fazla "birim" talep etme veya iade etme yeteneği ile genişletilebilir . Değiştirilmiş V ve P işlemleri, atomik işlemleri , yani diğer işlemlerin perspektifinden bölünmez görünen işlemleri belirtmek için köşeli parantezler kullanılarak aşağıdaki gibidir : 

function V(semaphore S, integer I):
    [S ← S + I]

function P(semaphore S, integer I):
    repeat:
        [if S ≥ I:
        S ← S − I
        break]

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

Açlıktan kaçınmak için , bir semaforun ilişkili bir işlem sırası vardır (genellikle FIFO semantiği ile). 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ütmesi 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 olduğunda, bunlardan biri kuyruktan kaldırılır ve yürütmeye devam eder. İşlemler farklı önceliklere sahip olduğunda, sıra önceliğe göre sıralanabilir, böylece en yüksek öncelikli işlem kuyruktan önce alınır.

Uygulama, artırma, azaltma ve karşılaştırma işlemlerinin atomikliğini sağlamazsa, artırma veya azaltmaların unutulması veya semafor değerinin negatif olması riski vardır. Atomiklik , semaforu tek bir işlemde okuyabilen, değiştirebilen ve yazabilen bir makine talimatı kullanılarak elde edilebilir . Böyle bir donanım talimatının yokluğunda, bir yazılım karşılıklı dışlama algoritması kullanılarak bir atomik işlem sentezlenebilir . Tek işlemcili sistemlerde, atomik işlemler, önceden almayı geçici olarak askıya alarak veya donanım kesintilerini devre dışı bırakarak sağlanabilir . 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 sorunu ç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 ayarla kilit komutu kullanılarak değiştirilir.

Örnekler

önemsiz örnek

Bir değişken A ve bir boole değişkeni S düşünün . A'ya yalnızca S doğru olarak işaretlendiğinde erişilir . Dolayısıyla S , A için bir semafordur .

Bir tren istasyonundan ( A ) hemen önce bir trafik ışığı sinyali ( S ) hayal edilebilir . Bu durumda, sinyal yeşilse, tren istasyonuna girilebilir. Sarı veya kırmızı (veya başka bir renk) ise, tren istasyonuna erişilemez.

Giriş kuyruğu

Yalnızca on kullanıcıyı destekleyebilen bir sistem düşünün (S=10). Bir kullanıcı oturum açtığında, S semaforunu 1 azaltarak P çağrılır. Bir kullanıcı oturumu kapattığında, S'yi 1 artırarak kullanılabilir hale gelen bir oturum açma yuvasını temsil eden V çağrılır . Ne zaman S 0, giriş yapmak isteyen tüm kullanıcılar kadar beklemek zorundadır S > 0 ve giriş isteği FIFO kuyruğuna üzerine kuyruğa alınmadan; isteklerin sırayla sıralanmasını sağlamak için karşılıklı dışlama kullanılır. Her ne zaman S 0'dan büyük (mevcut giriş yuvaları) olur, bir oturum açma isteği dequeued edilir ve istek sahibi kullanıcı giriş yapmak için izin verilir.

Üretici-tüketici sorunu

Olarak üretici-tüketici bir sorun , tek bir işlem (yapımcı) veri öğeleri oluşturur ve diğer bir yöntem (tüketici) alır ve kullanımları bunları. Maksimum N boyutunda bir kuyruk kullanarak iletişim kurarlar ve aşağıdaki koşullara tabidirler:

  • tüketici, sıra boşsa üreticinin bir şeyler üretmesini beklemek zorundadır;
  • Üretici, sıra doluysa tüketicinin bir şeyler tüketmesini beklemek zorundadır.

Üretici-tüketici sorununun semafor çözümü, kuyruğun durumunu iki semaforla izler: emptyCount, kuyruktaki boş yerlerin fullCountsayısı ve , kuyruktaki öğelerin sayısı. Bütünlüğü korumak için emptyCount, kuyruktaki gerçek boş yer sayısından fullCountdaha düşük (ancak asla daha yüksek) ve kuyruktaki gerçek öğe sayısından daha düşük (ancak asla daha yüksek) olmayabilir. Boş yerler ve öğeler iki tür kaynağı temsil eder, boş kutular ve dolu kutular ve semaforlar emptyCountve fullCountbu kaynaklar üzerinde kontrolü sağlar.

İkili semafor useQueue, örneğin iki üreticinin aynı anda boş bir kuyruğa öğe eklemeye çalışması ve böylece iç durumunu bozması gibi sıranın durumunun bütünlüğünün tehlikeye atılmamasını sağlar. Alternatif olarak, ikili semafor yerine bir muteks kullanılabilir.

emptyCountBaşlangıçta , N , fullCountilk olarak 0, ve useQueueilk olarak 1'dir.

Yapımcı aşağıdakileri tekrar tekrar yapar: 

produce:
    P(emptyCount)
    P(useQueue)
    putItemIntoQueue(item)
    V(useQueue)
    V(fullCount)

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

consume:
    P(fullCount)
    P(useQueue)
    item ← getItemFromQueue()
    V(useQueue)
    V(emptyCount)

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

  1. Tek bir tüketici kritik bölümüne girer. Yana fullCount0 tüketici blok.
  2. Birkaç üretici, üretici kritik bölümüne girer. Girişlerinin kısıtlanması nedeniyle kritik bölümlerine N'den fazla üretici giremez emptyCount.
  3. Üreticiler, birer birer kuyruğa erişir ve sıradaki useQueueöğeleri depolar.
  4. İlk üretici kritik bölümünden çıktıktan sonra, fullCountbir tüketicinin kritik bölümüne girmesine izin verecek şekilde artırılır.

emptyCountÖrneğin, birçok üreticinin sırayı azalttığı ancak useQueueboş yerleri doldurmadan önce sırasını beklediği durumlarda, bunun kuyruktaki gerçek boş yer sayısından çok daha düşük olabileceğini unutmayın . Bunun her zaman, ancak ve ancak hiçbir üretici veya tüketici kritik bölümlerini yürütmüyorsa eşitlikle geçerli olduğunu unutmayın . emptyCount + fullCount ≤ N

Operasyon adları

Kanonik isimler V ve P, Hollandaca kelimelerin baş harflerinden gelir . V genellikle verhogen ("artış") olarak açıklanır . P için, proberen ("test etmek" veya "denemek"), passeren ("geçmek") ve pakken ("kapmak") dahil olmak üzere çeşitli açıklamalar yapılmıştır . Konuda Dijkstra eski kağıt verir passering için anlam olarak ( "geçen") , P ve vrijgave V. Ayrıca terminoloji demiryolu sinyalleri de kullanılana alınır bahseder için anlam olarak ( "serbest"). Dijkstra sonradan o amaçlanan yazdı P için durmak prolaag kısaca, probeer te verlagen kelimenin tam anlamıyla "azaltmaya çalışın", veya "azaltmak için deneyin", diğer durumda kullanılan terimleri paralel.

In ALGOL 68 , Linux çekirdeği ve bazı İngiliz ders kitaplarında, V ve P işlemleri sırasıyla denir yukarı ve aşağı . Yazılım mühendisliği Uygulamada, genellikle denir sinyal ve bekleme , serbest bırakma ve acquire (standart Java kütüphanesi kullanır) veya sonrası ve pend . Bazı metinler onları boşalır ve orijinal Hollanda baş harfleriyle eşleşmesi için tedarik eder.

Semaforlar ve muteksler

Bir muteksin bir olan kilitleme mekanizması bazen ikili semafor gibi aynı temel uygulaması kullanır. Aralarındaki farklar nasıl kullanıldıklarıdır. İkili bir semafor, halk dilinde bir muteks olarak adlandırılabilse de, gerçek bir muteksin daha spesifik bir kullanım durumu ve tanımı vardır, çünkü yalnızca muteksi kilitleyen görevin onu açması beklenir. Bu kısıtlama, semaforların kullanılmasıyla ilgili bazı olası sorunları ele almayı amaçlar:

  1. Önceliği tersine çevirme : Muteks onu kimin kilitlediğini biliyorsa ve kilidini açması gerekiyorsa, daha yüksek öncelikli bir görev muteks üzerinde beklemeye başladığında o görevin önceliğini yükseltmek mümkündür.
  2. Erken görev sonlandırma: Muteksler, muteks tutan görevin yanlışlıkla silinemeyeceği durumlarda silme güvenliği de sağlayabilir.
  3. Sonlandırma kilitlenmesi: Bir muteks tutma görevi herhangi bir nedenle sona ererse, işletim sistemi muteks'i serbest bırakabilir ve bu koşulun bekleyen görevlerini işaret edebilir.
  4. Özyineleme kilitlenmesi: Bir görevin, yeniden giriş yapan bir muteksini eşit sayıda kilidini açtığı için birden çok kez kilitlemesine izin verilir .
  5. Yanlışlıkla serbest bırakma: Serbest bırakma görevi sahibi değilse, muteksin serbest bırakılmasında bir hata oluşur.

Ayrıca bakınız

Referanslar

Dış bağlantılar

Tanıtımlar

Referanslar