Bmeitxh

Философичдийн хоолны ширээний асуудал [[Файл:Image

5 Философич хамт амьдардаг. Тэд амьдралынхаа турш бодох идэх л ажил хийдэг ба хоолны ширээ нь тойрог хэлбэртэй. Ширээний голд том саванд гоймон хийсэн ба 5 савахыг (хос савах бус нэг л ширхэг савах) ширээ тойруулан тавьсан. Философич өлсвөл ширээ тойруулан тавьсан тасан сандалын али нэгэнд нь суун(мэдээж уг суудал дээр хүн байхгүй бол) өөрийн баруун болон зүүн талд байгаа савахаа эхлээс зүүн талд дараа нь баруун талдаа байгаа савахаа аван (нэг зэрэг хоёр савахаа аваж болохгүй) ширээний голд байгаа гоймонгоос иддэг. Хэрэв өөрийнх нь авах ёстой савахыг өөр хэн нэгэн авсан бол тэр савах сулархыг хүлээнэ. Аль ч философич хоёр савахтай байж л хоол идэх боломжтой болдог.Философичдийн хоолны ширээний асуудал бол тал талаас нь сайтар бодсон зэрэгцүүлэлтийн асуудал биш философичдод компьютерийн тэргүүлэх эрдэмтэд дургүй учир нь үүнд бодит ач холбогдол байхгүй гэвч энэ нь томоохон класс-д давхцалын хяналтын жишээ болдог юм. Энэ нь гацалтыг үүсгэхгүйгээр хэд хэдэн нөөцийн байршилийг заадаг бодит жишээ юм. Нэг энгийн шийдэл бол савах бүрийг семапорд зааж өгөх. А Философич өлсвөл семапорт савахыг авахаар хүлээх үйлдэл хийнэ. Тэр савахны чөлөөлөгдөх талаарх мэдээллийг маш хурдан дамжуулж байдаг. (Semaphore chopstick[5]) Иймд бүх өгөгдөлд анхны утга 1-ыг олгоно. Философич i ингэж бичэгдэнэ.

do {

   wait (chopstick[i]);
   wait (chopstick[(i+1)%5]);
   ...
   //eat
   ...
  signal(chopstick[i]);
  signal(chopstick[(i+1)%5]);
  ...
  //think
  ...
 }while (TRUE)

Философич савах зөвхөн бэлэн байгаа тохиолдолд л авах боломжтой. Философич өөрийн баруун болон зүүн талд байгаа савахаа эхлээд зүүн талд дараа нь баруун талдаа байгаа савахаа авна. Баруун болон зүүн талдаа савахдаа болох үе. Философичдын хооллолтыг дэлгэцэнд ашиглах тайлбар: Бид одоо философичдын хооллолтыг дэлгэцийн түгжрэлийг чөлөөлхөд авч үзъе. Энэ шийдэл нь философич бэлэн байгаа савахыг авах боломжтой эсэхийг тогтоодог. Кодонд энэ шийдэл, бид аль нэг боломжтой философичийг хайж 3-н нэгдэлээс ялгах хэрэгтэй. Ийм зорилгоод бид дагалдах өгөгдлийн бүтцийг таниулах хэрэгтэй.

enum {thinking, hungry, eating}state[5];

философич i зөвхөн хувьсах хэмжигдэхүүн нь 2-той тэнцүү болсон тохиолдолд иддэг.

(state[(i+40%5) != eating])and(state[(i+1)%5] != eating).

Бид мөн нөхцөлийг зарлах хэрэгтэй.

condition self[5];

Аль ч философич өөрөө өлссөн үедээ өөрт хэрэгтэй савахаа авж чадахгүй. Бид одоо Философичдийн хоолны ширээний асуудал шийдэхдээ байрлалыг тодорхойлно. Савахны тархалт нь дэлгэцийн dp-ээр удирдагддаг. Аль ч философич өмнө нь идэж эхлэдэг, дуудах үйл ажилгааг pickup(). Үр дүнд нь философичийн үйл ажилгаа түр зогсдог. Дараа нь үр дүн нь амжилттай биелэж философич иддэг.

monitor dp {

 enum {THINKING, HUNGRY, BATING}state[5];
 condision self[5];

 void pickup(int i){
   state[i] = HUNGRY;
   test(i);
   if (state[i] != EATING)
   self[i].wait();
  } 
 Void outdown(int i){
   state[i] = THINKING;
   test((i+4)%5);
   test((i+1)%5);
   }
  void test(int i){
  if ((state[(i+4)%5] != EATING) && 
     (state[i] == HUNGRY) && 
     (state[(i+1)%5] != EATING)) {
         state[i] = EATING;
         self[i].signal();
  } 
  }
  
   initialization.code(){
      for (int i = 0; i<5; i++)
       state[i] = THINKING;
  }      
  }