Yazan : Şadi Evren ŞEKER
Bu yazının amacı, eş zamanlı işlemlerin (concurrent processes) yönetimini anlatmak için geliştirilmiş bir örnek olan yemek yiyen filozoflar konusunu açıklamaktır. Eş zamanlı işlemler, işletim sistemleri (operating systems), ağ programlama (network programming) gibi pek çok bilgisayar bilimi konusunda geçmektedir.
Yemek yiyen filozoflar örneği, literatüre Dijkstra tarafından kazandırılmıştır ve eş zamanlı işlem yönetimini (concurrent process management) sembolize eder.
Öncelikle örneği anlatarak konuya başlayalım. Örneğe göre, ikiden fazla ( örnek için n kadar kabul edilebilir) filozof, bir yuvarlak masanın etrafına dizilerek yemek yerler. Literatürde örnek iki şekilde anlatılmaktadır ve orijinalinde filozoflar pirinç pilavı yemektedir. Buna göre pirinç yemek için iki adet yemek sopası (chopstick) gerekmektedir. Çinlilerin yemek yerken kullandıkları sopaları düşünebilirsiniz. Tek sopa ile yemek yenmesi imkansızdır ve her filozofun en az iki sopaya ihtiyacı vardır. Olayın daha iyi anlaşılması için aşağıdaki şekilde bu durum tasvir edilmiştir:
Şekilde de görüldüğü üzere, başlangıç durumunda, her filozofun iki yanında birer sopa durmaktadır.
Örneğin biraz daha batı dünyasına uyarlanmış halinde ( buna göre batıda çatal kullanılmaktadır), her filozof makarna yemek ister ancak makarna yemek için en az iki çatala ihtiyaç vardır. Filozofların iki yanında birer çatal olduğuna göre problem bir önceki pirinç ve Çinlilerin yemek sopası probleminden bir farkı kalmaz.
Problemde, yukarıda anlatılanlara ilave olarak, filozofların belirli bir süre düşünme süreci bulunur.
Problemin buna göre filozofların hepsi örneğin sağındaki sopayı alırsa, hepsinde birer sopa olacak ve yemek yiyemeyeceklerdir. Şayet hepsi iki yanındakini birden almaya kalkarsa, bu durumda, eş zamanlı işlemlerde karşılaşılan yarış durumu (racing condition) ortaya çıkacaktır ve hangisi önce davranırsa (ki bu konuda bir garantimiz bulunmamaktadır) o yemeğini yiyebilecektir. Ve belki de hepsi birer sopa alacağı için yine hiçbirisi yemek yiyemeyecektir. Şayet hepsi birden sopalarını bir diğeri yesin diye bırakırsa, bu durumda yine hiçbirisi yiyemeyecektir. Bu tip problemler, genelde kıtlık problemi (starvation) olarak düşünülebilir. Buna göre her filozofun yemek yeme ihtimali bulunmaktadır ancak hiçbir şekilde yiyeceği garanti edilmemektedir. Örneğin filozoflardan birisi her durumda aç kalabilir ve asla sıra kendisine gelmeyebilir.
Problemde karşılaşılan diğer bir sorun ise ölümcül kilitlenmedir (deadlock). Yanlış bir tasarım sonucunda, tek çatal alan ve çatalı bırakmak için diğer filozofun bırakmasını bekleyen bir filozof sistemi kilitleyebilir. Bu da problemde bulunan ikinci risktir.
Son olarak problemin tanımında, filozoflar birbiri ile konuşamaz kuralı getirilmiştir. Bu kural önemli bir kural olmakla birlikte, aşağıdaki çözümlerin çoğunda bu kuralın ihlal edildiği görülebilir. Aslında filozoflar birbiriyle çatallar üzerinden iletişim kurmaktadır. Örneğin sağındaki veya solundaki filozofun o anda çatalı alıp almaması, yanındaki filozoflar hakkında bilgi vermekte ve bu da üstü kapalı bir iletişim olarak kabul edilmektedir. Aşağıdaki çözümlerin tamamında iletişim sadece çatalların durumuna göre sağlanmaktayken, sadece son çözüm olan chandy misra çözümünde, filozoflar doğrudan birbiri ile iletişime geçebilmektedir.
Problemin çözümü için farklı algoritmalar geliştirilmiştir. Bu algoritmalar aşağıda başlıklar altında anlatılacaktır.
1. Rastgele süre çözümü (Random Solution)
Bu çözümde, filozofların problemi çözmek için tamamen rastgele davranması öngörülür. Filozoflar, bir çatal aldıktan sonra ikincisini alabilirse yemeğini yer. Şayet ikinci çatalı alamazsa rastgele bir süre bekler ve bu süre içinde ikinci çatalın boşalmasını bekler. Şayet bu süre içerisinde diğer çatal, yanındaki filozof tarafından bırakılırsa, çatalı alır ve yemeğini yer. Şayet beklediği bu rastgele süre boyunca ikinci çatal bırakılmazsa bu durumda yemeğini yiyemeden elinde tuttuğu çatalı diğer filozofun yemesi için masaya geri bırakır.
Bu çözümde dikkat edileceği üzere, işlem tamamen rastgelelik üzerine kuruludur. Buna göre sistem tam başarı ile çalışmayabilir. Hatta sistemin çalışacağının hiçbir şekilde garantisi yoktur.
Çözüm yönteminin en önemli özelliği, çözümün gerçeklemesinin (kodlamasının) diğer bütün sistemlere göre çok daha kolay olmasıdır.
2. Garson çözümü (Conductor Solution)
Problemin bir seviye daha karmaşık ancak yine de basit bir çözümü, masanın etrafında bir garsonun (literatürde conductor ismi verilmiştir ve bu yüzden conductor solution olarak geçer) dolaşmasıdır.
Garson, sürekli olarak masada boş duran ve filozoflar tarafından yemek için kullanılan çatalların sayılarını takip etmektedir. Bir şekilde her filozof, masadan çatal alabilmek için garsonun iznini istemek zorundadır. Şayet garson izin vermezse filozof masadan çatal alamaz. Bu çözümde filozofların kıtlık problemi (starvation) ile karşılaşmaları engellenir çünkü mantıklı bir garson tasarımı, bütün filozoflara yemek imkanı tanır. Aynı zamanda ölümcül kilitlenme (deadlock) ihtimali de çözülmüştür çünkü garson hiçbir filozofu sonsuza kadar bekletmez. Yani filozofların birbirini bekleyerek sonsuza kadar yaşlanması sorunu çözülmüştür.
Çözümün daha iyi anlaşılabilmesi için, garsonun, saat yönünde masada döndüğünü, düşünelim. O anda işaretlediği filozof yemek yiyor, sonraki yemiyor sonraki yiyor ve böylece kaç filozof farsa, sırayla bir yiyor bir yemiyor şeklinde düşünülebilir. Bu durumda her filozofun yemek yemek için yeterli çatalı (veya sopası) bulunuyor demektir. Sonra garson, sırasıyla bir yönde (örneğin saat yönünde) dönerek masayı dolaşmakta ve sıradaki filozofa yemek yedirmekte (ve dolayısıyla sıradaki filozoftan sonraki yememekte ve sonraki yemekte ve böylece bütün masadakiler bir yer bir yemez şeklinde işaretlenmektedir).
3. Monitör Çözümü (Monitor Solution)
Bu çözüm, bir önceki garson çözümüne çok benzemektedir. Amaç sırasıyla her filozofun bir yiyen bir de yemeyen şeklinde sıralanmasıdır. Burada her filozof belirli bir sırayla sıralanmaktadır (örneğin saat yönünde veya saat yönünün tersi istikamette) ardından kendinden önceki filozofun durumunu kontrol ederek yemek yiyorsa yemez, kendinden önceki filozof yemek yemiyorsa bu durumda kendisi yemek yer.
Tek sayıda filozof olması durumunda yemek yeme eyleminin masada bir dalga şeklinde bir noktadan başlayarak sürekli döndüğü görülebilir. Şayet filozof sayısı çift ise bu durumda sürekli aynı filozoflar yemek yerken diğer filozoflar ölecektir. Bir çözüm olarak, şayet toplam filozof sayısı çift ise, sırasıyla tek ve çift filozoflara yemek yedirmek bir çözüm olabilir. Örneğin önce 1,3,5 numaralı filozoflar yemek yerken, sonra 2,4,6 numaralı filozoflar yemek yiyebilir.
4. Chandy Misra Çözümü (Chandy Misra Solution)
Bu çözüm, geliştiren iki kişinin ismi ile anılmaktadır (K. Mani Chandy ve J. Misra). Çözümün en önemli özelliği, merkezi bir karar mekanizmasını ortadan kaldırması ancak buna karşılık, filozoflar birbiri ile konuşamaz kuralını çiğnemesidir.
Çözüm aşağıdaki 4 adımdan oluşmaktadır denilebilir:
- Her filozof ikilisi için bir çatal üretilir ve bu çatal en düşük sayı sahibi olan filozofa verilir. Her çatal kirli veya temiz olarak işaretlenebilir ve başlangıç durumunda bütün çatallar kirlidir.
- Bir filozof, bir kaynak kümesini kullanmak istediğinde (yani yemek yemek istediğinde), komşusu olan çatalları kullanmak zorundadır. Elinde olmayan (ihtiyacı olan) bütün çatallara bir talep yollar.
- Bir filozof, elindeki bir çatal için talep aldığında, şayet elindeki çatal temizse kullanmaya devam eder, şayet çatal kirli ise, çatalı masaya koyar. Ayrıca masaya konan çatal temiz olarak işaretlenerek konulur.
- Bir filozof yemek yedikten sonra çatalı kirli olarak işaretler. Şayet bir filozof, daha önce bir çatalı talep ettiyse, çatalı temzileyerek masaya koyar.
Yukarıdaki algoritma adımlarını şu şekilde anlamak mümkündür. Öncelikle bütün çatallara bir işaret getiriliyor. Buna göre bir çatal, kirli veya temiz olabiliyor. Çatalın talep edilmesi ve edilmemesi arasındaki fark, bu işaret ile belirleniyor. Üzerinde talep olmayan çatallar temiz olarak tutulurken, üzerinde bir filozofun talebi bulunması halinde kirli oluyor. Bu durumda ikinci bir filozofun talepte bulunması engelleniyor. Her çatal sadece talep eden filozof tarafından kullanılacağı için de kullanma işlemi öncesinde tek bir filozofa atama yapılmış oluyor. Ayrıca filozofların talep işleminin gerçekleşebilmesi için çatal kümesinin (iki çatalın birden) atamasının yapılması gerekmektedir. Şayet tek bir çatal ataması yapılırsa bu durumda çatal filozofa ayrılmadan diğer filozofun kullanımı için serbest olmuş oluyor.
Burada akla, acaba bu çatal ayırımı sırasında, problemin orjinalinde bulunan kilitlenme ihtimali bulunmaz mı? Şeklinde bir soru gelebilir. Bu soru aslında mantıklı bir soru olmakla birlikte, kilitlenme probleminin önüne geçmek için, algoritma tasarımında bulunan en küçük numaraya sahip filozof koşulu getirilmiştir. Yani filozofların hepsi aynı önceliğe sahip olduğu durumlarda bir kilitlenme ihtimali bulunmakla birlikte, bu ihtimali bertaraf etmek için her filozofa bir numara verilmiş ve bu numaraya göre en düşük değere sahip filozof öncelikli olmuştur. Peki sürekli bu filozof yemek yiyerek diğerlerini bir kıtlığa sokabilir mi? Bu durumda kirli ve temiz çatal ataması ile engellenmiştir.
Diğer İşletim Sistemi Senkronizasyon Problemleri ve Çözümleri:
Merhaba,
Ben kendimce bir gui oluşturup, javada semaphore classını ve threadleri kullanarak bir çözüm oluşturmaya çalıştım fakat, malesef belli threadlerde tıkanıp kalıyor gibi belli bir noktadan sonra ilerleme gösteremiyor, sizin acaba bir yorumunuz olabilir mi, geliştirebilmem adına?
Kod şu şekilde:
import java.awt.EventQueue; import java.util.concurrent.Semaphore; import java.util.Random; import javax.imageio.ImageIO; import javax.swing.ImageIcon; import javax.swing.JFrame; import javax.swing.JLabel; import java.awt.Color; import java.awt.image.BufferedImage; import java.io.File; import java.io.IOException; class Table { // FOR GUI: static JFrame frame; private JLabel[] plates = new JLabel[5]; private JLabel[] forks = new JLabel[5]; static Table window; static BufferedImage fork; /** * Launch the application. /** * Create the application. */ public Table() { initialize(); } /** * Initialize the contents of the frame. */ private void initialize() { frame = new JFrame(); frame.setResizable(false); frame.setBounds(100, 100, 450,400); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.getContentPane().setBackground(Color.WHITE); BufferedImage plate = null; try { plate = ImageIO.read(new File("spaghetti_white.jpg")); } catch (IOException e) { e.printStackTrace(); } frame.getContentPane().setLayout(null); plates[0] = new JLabel(new ImageIcon(plate)); plates[0].setBounds(185, 10, 100, 100); frame.getContentPane().add(plates[0]); plates[1] = new JLabel(new ImageIcon(plate)); plates[1].setBounds(300, 100, 100, 100); frame.getContentPane().add(plates[1]); plates[2] = new JLabel(new ImageIcon(plate)); plates[2].setBounds(230, 230, 100, 100); frame.getContentPane().add(plates[2]); plates[3] = new JLabel(new ImageIcon(plate)); plates[3].setBounds(70, 210, 100, 100); frame.getContentPane().add(plates[3]); plates[4] = new JLabel(new ImageIcon(plate)); plates[4].setBounds(50, 80, 100, 100); frame.getContentPane().add(plates[4]); try { fork = ImageIO.read(new File("fork_white_1.jpg")); } catch (IOException e) { e.printStackTrace(); } forks[0] = new JLabel(new ImageIcon(fork)); forks[0].setBounds(250, 40, 100, 100); frame.getContentPane().add(forks[0]); try { fork = ImageIO.read(new File("fork_white_2.jpg")); } catch (IOException e) { e.printStackTrace(); } forks[1] = new JLabel(new ImageIcon(fork)); forks[1].setBounds(280, 170, 100, 100); frame.getContentPane().add(forks[1]); try { fork = ImageIO.read(new File("fork_white_3.jpg")); } catch (IOException e) { e.printStackTrace(); } forks[2] = new JLabel(new ImageIcon(fork)); forks[2].setBounds(150, 220, 100, 100); frame.getContentPane().add(forks[2]); try { fork = ImageIO.read(new File("fork_white_4.jpg")); } catch (IOException e) { e.printStackTrace(); } forks[3] = new JLabel(new ImageIcon(fork)); forks[3].setBounds(60, 145, 100, 100); frame.getContentPane().add(forks[3]); try { fork = ImageIO.read(new File("fork_white_5.jpg")); } catch (IOException e) { e.printStackTrace(); } forks[4] = new JLabel(new ImageIcon(fork)); forks[4].setBounds(95, 15, 100, 100); frame.getContentPane().add(forks[4]); } public void Hungry_GUI(int i) { try { plates[i].setIcon(new ImageIcon(ImageIO.read(new File("spaghetti_yellow.jpg")))); } catch (IOException e) { e.printStackTrace(); } try { Thread.sleep(500); } catch (InterruptedException e) { e.printStackTrace(); } } public void ForkTake_GUI(int i) { try{ if (i == 0) { forks[0].setIcon(new ImageIcon(ImageIO.read(new File("fork_red_1.jpg")))); forks[4].setIcon(new ImageIcon(ImageIO.read(new File("fork_red_5.jpg")))); } else if (i == 1) { forks[0].setIcon(new ImageIcon(ImageIO.read(new File("fork_red_1.jpg")))); forks[1].setIcon(new ImageIcon(ImageIO.read(new File("fork_red_2.jpg")))); } else if (i == 2) { forks[1].setIcon(new ImageIcon(ImageIO.read(new File("fork_red_2.jpg")))); forks[2].setIcon(new ImageIcon(ImageIO.read(new File("fork_red_3.jpg")))); } else if (i == 3) { forks[2].setIcon(new ImageIcon(ImageIO.read(new File("fork_red_3.jpg")))); forks[3].setIcon(new ImageIcon(ImageIO.read(new File("fork_red_4.jpg")))); } else if (i == 4) { forks[3].setIcon(new ImageIcon(ImageIO.read(new File("fork_red_4.jpg")))); forks[4].setIcon(new ImageIcon(ImageIO.read(new File("fork_red_5.jpg")))); } }catch (IOException e) { e.printStackTrace(); } } public void Eating_GUI(int i) { try { plates[i].setIcon(new ImageIcon(ImageIO.read(new File("spaghetti_red.jpg")))); } catch (IOException e) { e.printStackTrace(); } try { Thread.sleep(3000); } catch (InterruptedException ex){ ex.printStackTrace(); } } public void ForkPut_GUI(int i) { try{ if (i == 0) { forks[0].setIcon(new ImageIcon(ImageIO.read(new File("fork_white_1.jpg")))); forks[4].setIcon(new ImageIcon(ImageIO.read(new File("fork_white_5.jpg")))); } else if (i == 1) { forks[0].setIcon(new ImageIcon(ImageIO.read(new File("fork_white_1.jpg")))); forks[1].setIcon(new ImageIcon(ImageIO.read(new File("fork_white_2.jpg")))); } else if (i == 2) { forks[1].setIcon(new ImageIcon(ImageIO.read(new File("fork_white_2.jpg")))); forks[2].setIcon(new ImageIcon(ImageIO.read(new File("fork_white_3.jpg")))); } else if (i == 3) { forks[2].setIcon(new ImageIcon(ImageIO.read(new File("fork_white_3.jpg")))); forks[3].setIcon(new ImageIcon(ImageIO.read(new File("fork_white_4.jpg")))); } else if (i == 4) { forks[3].setIcon(new ImageIcon(ImageIO.read(new File("fork_white_4.jpg")))); forks[4].setIcon(new ImageIcon(ImageIO.read(new File("fork_white_5.jpg")))); } }catch (IOException e) { e.printStackTrace(); } } public void StopEating_GUI(int i) { try { plates[i].setIcon(new ImageIcon(ImageIO.read(new File("spaghetti_white.jpg")))); } catch (IOException e) { e.printStackTrace(); } } } /********************************************** * START EDITING BELOW THIS LINE !!! * **********************************************/ public class Philosopher implements Runnable { private static Table table; private int ID; private int N = 5; private static Semaphore s1 = new Semaphore(1) ; private static Semaphore[] sarray = new Semaphore[5]; private int[] array = new int[5]; private int thinking = 0; private int hungry = 1; private int eating = 2; private int left = (ID + N - 1) % N; private int right = (ID + 1) % N; void test(int i) { if((array[i] == hungry) && (array[left] != eating) && (array[right] != eating)) { table.ForkTake_GUI(i); array[i] = eating; sarray[i].release(); } } void take_forks(int i) { try { s1.acquire(); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } array[i] = hungry; table.Hungry_GUI(i); test(i); s1.release(); table.Eating_GUI(i); sarray[i].release(); } void put_forks(int i) { table.StopEating_GUI(i); try { s1.acquire(); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } array[i] = thinking; test(left); test(right); table.ForkPut_GUI(i); s1.release(); } public Philosopher(int i) { setID(i); } public void run() { while(true) { Random RandomGenerator = new Random(); int randomNum = RandomGenerator.nextInt(10); try { Thread.sleep((randomNum * 1000)); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } take_forks(ID); //table.Eating_GUI(); put_forks(ID); } } public static void main(String args[]) { EventQueue.invokeLater(new Runnable() { public void run() { try { table = new Table(); table.frame.setVisible(true); } catch(Exception e){ e.printStackTrace(); } } }); Philosopher p1 = new Philosopher(1); Philosopher p2 = new Philosopher(2); Philosopher p3 = new Philosopher(3); Philosopher p4 = new Philosopher(4); Philosopher p5 = new Philosopher(5); Thread pt1 = new Thread(p1); Thread pt2 = new Thread(p2); Thread pt3 = new Thread(p3); Thread pt4 = new Thread(p4); Thread pt5 = new Thread(p5); sarray[0] = new Semaphore(1); sarray[1] = new Semaphore(1); sarray[2] = new Semaphore(1); sarray[3] = new Semaphore(1); sarray[4] = new Semaphore(1); pt1.start(); pt2.start(); pt3.start(); pt4.start(); pt5.start(); } public int getID() { return ID; } public void setID(int iD) { ID = iD; } }Hocam ellerinize sağlık bu kadar güzel bir anlatım şuana kadar görmemiştim. Çok güzel ve temiz anlatmışsınız tebrik ederim.