Petri Ağları Nedir?

Çok bileşenli sistemlerde (distributed systems) ortaya çıkan eş zamanlı süreçlerin analizi ve modellenmesi için kullanılan “Petri Ağları” bir grafik aracıdır. Kimyasal süreçlerin modelleme amacıyla 13 yaşındaki genç Carl Petri tarafından 1939 ortaya atılmıştır. Programlamada ve sistem modellenmesinde oldukça büyük yere sahip olan bu methodu daha yakından inceleyelim.

A- A+

20.01.2016 tarihli yazı 10701 kez okunmuştur.

Petri Ağının Anatomisi

Durumlar (maddeler için) ve geçişler (reaksiyonlar için) ağların bileşenlerini oluşturmaktadır. Yuvarlak sembolü S durumlarını (koşul veya yer de denilebilir) ifade ederken, dikdörtgen sembolü ise T geçişlerini ifade etmektedir. Bu durum ve geçişler akış yönünü gösteren oklar ile birbirine bağlanmaktadır. Geçiş aktiviteleri almak ve vermek olarak ikiye ayrılmaktadır.

Üretim Ağı

Yukarıdaki şekilde ilk durumları ifade eden siyah noktalar (ya da semboller) geçişlerin oluşu ile taşınmaktadır. Her nokta bir molekülü temsil etmektedir. Geleneksel yaklaşımda, soyut yapılarını açıkça gösterme amacıyla düzenli olarak inşa edilmiş ağlara ait durum sembolleri ihmal edilmektedir. Bunun sonucu olarak Petri Ağ gösteriminde farklı şekiller görülebilmektedir.

Geleneksel Petri Ağ Gösterimi

Üretim ağında S ve T arasındaki değişim organizasyon ağı adı verilen çok farklı bir yapıyı vermektedir. Aşağıda verilen organizasyon ağı örneğinde geçişler ofisleri, durumlar ise kanalları sembolize etmektedir. Mesajlar başka bir alt ofis tarafından gerçekleştirilene kadar, bu durum ve geçişler mesaj (emir gibi) tutma kapasitesine sahiptir. Verilen ağ eşit rütbeye sahip A ile B ofislerini içeren bir organizasyon ağıdır ve bahsedilen A ve B ofisleri eğer kanal kapasitesi onlara izin verirse bağımsız şekilde emir verebilmektedir. D ve F gibi ofisler insan organizasyonlarında nadir görülürken askeriye gibi ortamlarda bulunabilmektedir.

Organizasyon Ağı

En önemli ağ sınıfı ise içindeki okların yönlendirilmiş bir devre üzerinde uzandığı periyodik (cylic) ağdır. Bu ağ iyi şekilde yapılandırılsa, sonsuz şekilde tekrar eden süreçleri açıklamaktadır. Bu ağın tarihinin sonlu bir parçası üretim ağı olarak tanımlanabilmektedir.Ayrıca bu ağ mekanik osilatör ile aynı yapıya sahiptir.

Genel Ağ Teorisi

Carl Petri’nin 1966 yılında yayınladığı “Communication with Automata” adlı doktora tezinden sonra, kendisi ve yardımcıları Petri ağlarının bilimdeki uygulamaları (ekonomi, mekanik, bilgisayar bilimi, lojik, organizasyon, biyoloji, telekomunikasyon protokolleri, vb alanlarda) üzerine pek çok çalışma yaptılar. Bu çalışmaları yapmalarındaki amaç yapısal bilginin disiplinler arası transferi için bir araç yaratmaktı.

Daha yüksek seviyeli ağ kavramı genel ağ teorisinin (GAT veya İngilizcesi ile GNT) aksiyomatik temeli tarafından hazırlanmıştır. GAT genel ağ tanımını, basit geçiş kurallarını, daha yüksek seviyeli ağların yaratılışını ve herhangi bir sayıya ait boyuta adım atılmasını içermektedir.

Ayrıntılı olarak, GAT aşağıdaki aksiyomlar üzerine kurulmuştur:

►1.1 Boş küme bir ağ değildir (bu aksiyom teoremin ispatı ile ilgilidir.)
►1.2 S ve Tayrı kümelerdir.
►1.3 Ağ içerisinde izole olan eleman bulunmaz.
►1.4 Kısa devre bulunmaz. (iki eleman arasındaki)

Bir olay eş zamanlı olarak yürütülebilen geçişlerin kümesidir. Olay aksiyomları:

►2.1 (Her olay işaretlenebilir bu nedenle) Olaylara ait sınıf E boş değildir.
►2.2 Aynı olay içindeki geçişler, bağlı durumlara ait örtüşmeyen kümelere sahiptir.
►2.3 e olayı işaretsiz hale geldikten sonra, e olayı içindeki her geçiş işaretli olan tüm gelen durumlara sahiptir.
►2.4 e olayı işaretli hale geldikten sonra, e olayı içindeki her geçiş işaretsiz olan tüm giden durumlara sahiptir.

Bir ağdan başka bir ağa yapılan planlama aksiyomlar tarafından yönetilmektedir.

►3.1 Plan (ya da şema) okları ters çevirmez.
►3.2Şema topoloji anlamında süreklidir: yani şema durumlar arasındaki komşuluğu yok etmez.

Basit bir ağa ait bağlantı matrisi C, SxT’lik (-1, 0, 1) girişli bir matristir.

Çok boyutlu bir nesneyi temsil eden ağlara ait anlamlı diziler aşağıdaki şekilde kurulmaktadır:

►4.1 Ağ N(n+1)’e ait T, Net(n)’e ait S ile özdeştir.
►4.2 Ağ N(n+1)’e ait C ile Net(n)’e ait C’nin çarpımı sıfır matrisine eşittir.

3 numaralı aksiyomlar basit ağlardan daha yüksek seviyeli ağlara doğru olan kavramsal adımları ifade etmektedir. Burada; oklar etiketleri taşıyabilmekte,S durumları herhangi bir sayıda sembolü taşıyabilmekte, T geçişleri bileşik süreçleri ifade edebilmekte ve eğer anlamları tanımlandıysa kısa devreleri izin verilmektedir. “Olay Aksiyomları” buna göre yeniden tanımlanmalıdır.

4 numaralı aksiyomlar basit ağlardan daha yüksek seviyeli ağlara doğru olan boyutsal adımları ifade etmektedir. Bahsedilen basit ağlar, istenilen herhangi bir sayıda ve türdeki kümelerin ağlandırılması amacıyla iki tür elemana (S ve T) sahiptir.

Sınıf İşaretleme, Güvenlik (Safety), Emniyet (Security) ve Adaletlilik

Verilen birbaşlangıç işaretlemesi için, ağa ait geleceği ve geçmişi sorgulama görevi mevcuttur. İşaretleme sınıfı, işaretlemeler kümesi olarak tanımlabilir ve bu işaretlemeler başlangıç işaretlemesinden itibaren ileri ve geri geçiş uygulamaları ile tarafından erişilebilmektedir.

Bir ağ yapısının kendi işaretleme sınıfı içerisinde herhangi bir bağlantı durumu yoksa bu yapı güvenli (safe) olarak adlandırılmaktadır. Sembollerin çarpışması tehlike belirtisi olduğunda, bağlantı görülmektedir. Bunun nedeni ise aksiyom 2.3 ve 2.4’ün sağlanmamasıdır.

Kendi işaretleme sınıfında transjunction bulunmayan ağ yapılarına emniyetli (secure) denmektedir. Transjunction durumların geçiş içinde birleşmesine verilen addır: giriş ve çıkış durumları işaretlenmiştir. Elektromanyetik sinyalleri ifade eden semboller girişebilirler.

Transjunction Durumu

Bazı ağlar iki ya da daha fazla bağımsız sürecin, birkarşılıklı dışlama mekanizması tarafından birbirinde uzak tutulmasına izin vermektedir. Bu mekanizma her tekrarlamada süreçlerden sadece birinin kritik aşamaya girebilmesini sağlamaktadır. Mekanizmaya ait çalışma prensibi şu şekilde açıklanabilir: karşılıklı dışlama hiç gerçekleşemeyen ölü geçişler ile belirtilmektedir. Bu ölü geçişler facts olarak adlandırılmaktadır. Çünkü işaretleme sınıfı hakkındaki gerçek açıklamaları temsil etmektedirler.

Adaletli rekabeti sağlamak için, döngüler buffer tarafından bağlanmalıdır. Uygulamada, daha büyük buffer daha fazla özgürlüğe izin vermektedir.

Karşılıklı Dışlama ve Buffer

Yukarıdaki şekilde, işaretleme sınıfı hakkındaki geçerli tüm mantıksal ifadeleri bir facts kümesi tarafından tanımlamak için genel bir method gösterilmiştir.

Petri Ağlarına Dair Örnekler

►Örnek 1: 4 Mevsim Döngüsü Örneği

►Örnek 2: Restaurant Örneği

Restaurant örneği için iki senaryo mevcuttur.

Birinci senaryoya göre; garson müşteri 1’in (customer 1) siparişini alır ve ona siparişini servis eder. Ardından müşteri 2’nin (customer 2) siparişini alır ve ona siparişini servis eder.

İkinci senaryoya göre; garson müşteri 2’nin (customer 2)siparişini alır ve ona siparişini servis eder. Ardından müşteri 1’in (customer 1) siparişini alır ve ona siparişini servis eder.

Kaynak:

►Carl Adam Petri and Wolfgang Reisig (2008) Petri net. Scholarpedia
►http://www.utdallas.edu/~gupta/courses/semath/petri.ppt

Yazar: Sena Koçak