Çözen : Şadi Evren ŞEKER
Çözümler için şifre : www.setegitim.com
Identify and explain one reason for constructing a program so that it uses multiple threads instead of just one thread. We are expecting two to four sentences of answer.
Tek lifli (threaded) programlama yerine neden çok lifli (threaded) programalam kullanıldığını açıklayınız.
Cevap : [password] Birden fazla işin aynı anda yapılması gereken durumlarda bir işin diğerini beklemesini engellemek için birden fazla lif kullanılması gerekir. Böylelikle işlemciye erişimde her lif bir diğerinden bağımsız olarak çalışabilmekte, bir iş beklerken diğeri etkilenmemektedir.[/password]
Joshua, Caroline, and Matt go to a Chinese restaurant at a busy time of the day. The waiter apologetically explains that the restaurant can provide only two pairs of chopsticks (for a total of four chopsticks) to be shared among the three people. Joshua proposes that all four chopsticks be placed in an empty glass at the center of the table and that eating should obey the following protocol.
/* Run by each philosopher */ while (!time_to_grade_P2()) { discuss_grading_plan(); acquire_one_chopstick(); /* may block */ acquire_one_chopstick(); /* may block */ eat(); release_one_chopstick(); /* does not block */ release_one_chopstick(); /* does not block */ }
Üç kişi bir çin restoranında yemeğe giderler. Garson sadece 4 yemek çubuğu getirebileceğini söyler (bir kişinin yemek yemesi için en az iki çubuk gerekmektedir). Bu kişilerden birisi bütün çubukları ortadaki bir bardağa koyarak yukarıdaki algoritmayı kullanmayı önerir.
Bu algoritmada bir kilitlenme (deadlock) olmayacağını gösteriniz:
[password] Yukarıdaki soruda bir kilitlenme olması için hiç kimsenin anlık olarak yemek yiyemediği ve yemek yeme ihtimali olmadığı bir durum bulunmalıdır. Bunu kilitlenme ihtimali olan bir durum üzerinden anlamaya çalışalım. Örneğin 4 çubuk ve 4 kişi bulunsaydı bu durumda herkesin tek bir çubuk aldığı ve ortada hiç çubuk bulunmadığı durumda kilitlenme olacaktı çünkü kimse yemek yiyemediği için kimse çubuğunu bırakmayacaktı ve kimse iki çubuk sahibi olamayacaktı ve kimse yemek yiyemeyecekti… Ancak bu durumda 4 çubuk ve 3 kişi bulunuyor o halde en az bir kişi iki çubuk alacak ve yemeğini yiyerek çubuklarını bırakacaktır. Bu durumda diğer kişiler yemeğini yiyecektir ve kilitlenme olmadan herkes yemeğini yemiş olacaktır. [/password]
Suppose now that instead of three diners there will be an arbitrary number, D. Furthermore, each diner may require a different number of chopsticks to eat. For example, it is possible that one of the diners is an octopus, who for some reason refuses to begin eating before acquiring eight chopsticks. The second parameter of this scenario is C, the number of chopsticks which would simultaneously satisfy the needs of all diners at the table. For example, Joshua, Caroline, Matt, and one octopus would result in C = 14. Each diner’s eating protocol will be as displayed below.
int s, nsticks = my_chopstick_requirement(); while (!time_to_grade_P2()) { discuss_grading_plan(); for (s = 0; s < nsticks; ++s) acquire_one_chopstick(); /* may block */ eat(); for (s = 0; s < nsticks; ++s) release_one_chopstick(); /* does not block */ }
Bu sefer D sayısında kişinin yemek yemek istediğini ve kişilerin çubuk ihtiyacını C ile gösterelim. Örneğin 8 kollu bir ahtopot ve üç kişi yemek yerken toplam çubuk ihtiyacı 2 + 2 + 2 + 8= 14 olacaktır.
Yukarıdaki açıklama ve algoritmaya göre kilitlenme (deadlock) olmaması için C ve D’ye bağlı olarak en az kaç çubuk gerekir?
Cevap:
[password] Buradaki ihtimalleri öncelikle tahlil etmemiz gerekir. Toplamda C adet çubuk ihtiyacı olduğunu ve D kişi bulunduğunu biliyoruz. Bilmediğimiz şey ise C adet çubuk ihtiyacının D kişiye nasıl dağıtıldığı. Yani herkes birer çubuk istiyor ve geri kalan çubukları tek kişi istiyor olabilir. Veya herkesin çubuk ihtiyacı eşit bir şekilde dağılmış olabilir.
Bu durumu iki farklı örnekle anlamaya çalışalım. C= 16 için ve D = 4 için aşağıdaki durumlar olabilir
- Herkes 4 çubuk istiyordur
- 3 kişi birer çubuk ve bir kişi 13 çubuk istiyordur.
Diğer alternatifler ise bu iki ihtimal arasında bir yerlerdedir.
İlk durumda herkesin 4 çubuk istemesi söz konusuysa ve 4 kişi varsa o zaman herkesin3er çubuk aldığını ve kilitlendiğini düşünebiliriz. Kilidin çözülmesi için ilave bir çubuk gerekir. Bu durumda kilit olmaması için 3 + 3 + 3 +4 = 13 çubuk gerekmektedir.
İkinci durumda ise durum farklı değildir kilitlenme en kötü ihtimalle bir kişinin 12 çubuk almasıyla olur ve çözüm için ilave bir çubuk yeterlidir ve sonuç yine 3 bulunur.
Yukarıdaki bu sayısal örnekten de gördüğümüz üzere sistemdeki kilit olabilecek maksimum çubuk sayısı C-D formülüyle bulunur. Bu kilidin çözülmesi için ilave tek bir çubuk yeterlidir. Öyleyse sorunun cevabı C-D+1 olmalıdır. [/password]