ارتباط بین فرآیندها

ارتباط بین فرآیندها

اسلاید 1: Concurrency: Mutual Exclusion and Synchronizationفصل پنجم1

اسلاید 2: Concurrency ارتباط بین فرآیندها استفاده ی چند فرایند از یک ناحیه ی مشترکاشتراک منابع استفاده ی چند فرایند از یک منبع مشترک2

اسلاید 3: Difficulties with Concurrencyاشتراک منابع سراسریمدیریت تخصیص منابعتشخیص محل خطاهای برنامه نویسی3

اسلاید 4: A Simple Examplevoid echo(){chin = getchar();chout = chin;putchar(chout); }4

اسلاید 5: A Simple ExampleProcess P1Process P2. .chin = getchar(); .. chin = getchar();chout = chin; chout = chin;putchar(chout); .. putchar(chout);. .5

اسلاید 6: Process Interactionفرآیندها از وجود همدیگر با اطلاع نیستند.فرآیندها بطور غیر مستقیم از همدیگر اطلاع دارند.فرآیندها بطور مستقیم از همدیگر اطلاع دارند.6

اسلاید 7: Competition Among Processes for Resourcesانحصار متقابلنواحی بحرانیدر هر لحظه از زمان فقط یک برنامه می تواند در ناحیه بحرانی باشد.بن بستگرسنگی7

اسلاید 8: Cooperation Among Processes by Sharingانحصار متقابلبن بستگرسنگی8

اسلاید 9: Cooperation Among Processes by Communicationبن بستگرسنگی9

اسلاید 10: Requirements for Critical Regionانحصار متقابل: در هر لحظه از زمان فقط یک فرآیند می تواند در ناحیه بحرانی باشد.پیشرفت: وقتی که فرآیند دیگری از ناحیه بحرانی استفاده نمیکند، فرآیند متقاضی نباید با تأخیر روبرو شود.تاخیر محدود: مدت استفاده از ناحیه بحرانی برای هر فرآیند محدود است.10

اسلاید 11: Mutual Exclusion: Software Approachesهیچگونه حمایت از طرف OS یا سخت افزار لازم نیست11

اسلاید 12: First Attempt12

اسلاید 13: First Attemptانتظار مشغولیفرآیند مرتب چک می کند که ببیند می تواند وارد ناحیه بحرانی شود یا نه.در این حالت فرآیند تا وقتی که وارد ناحیه بحرانی نشود، هیچ کار مفیدی انجام نمی دهد.اگر فرآیندی در ناحیه بحرانی خود شکست بخورد، فرآیند دیگر تا ابد مسدود خواهد بود.فرآیندها به نوبت از ناحیه بحرانی استفاده می کنند.13

اسلاید 14: Second Attempt14

اسلاید 15: Second Attemptهر فرآیند می تواند وضعیت دیگران را ببیند، اما نمی تواند آنرا تغییر دهد.وقتی که فرآیند می خواهد وارد ناحیه بحرانی شود، ابتدا وضعیت دیگران را چک می کند.اگر هیچ فرآیندی در ناحیه بحرانی نباشد، وضعیت خود را به ناحیه بحرانی تغییر می دهد. متاسفانه این متد انحصار متقابل را تضمین نمی کند.15

اسلاید 16: Third Attempt16

اسلاید 17: Third Attemptقبل از چک کردن وضعیت دیگران، وضعیت خود را به حالت بحرانی تغییر دهیم.اگر بعد از این کار دیدیم که فرآیند دیگری در ناحیه بحرانی است، فرآیند تا خالی شدن ناحیه بحرانی مسدود می شود.در این حالت امکان بن بست وجود دارداگر دو فرآیند همزمان بخواهند وارد ناحیه بحرانی شوند ، ممکن است هر تا ابد مسدود بمانند.17

اسلاید 18: Fourth Attempt18

اسلاید 19: Fourth Attemptفرآیند یک پرچم را به نشانه تمایل خود به استفاده از ناحیه بحرانی روشن می کند، اما این آمادگی را دارد که در صورت لزوم پرچم را خاموش کند.سپس، فرآیندهای دیگر را چک می کند. اگر کسی در ناحیه بحرانی باشد پرچم را خاموش می کند و در زمان دیگری آنرا روشن می کند. این عمل تا وقتی که وارد ناحیه بحرانی نشود تکرار می گردد. 19

اسلاید 20: One Correct Solutionهر فرآیند یک نوبت برای ناحیه بحرانی می گیرد.اگر فرآیند بخواهد وارد ناحیه بحرانی شود ابتدا پرچم خود را روشن می کند و منتظر نوبتش می ماند. 20

اسلاید 21: Peterson Algorithm 21

اسلاید 22: Mutual Exclusion: Hardware Supportخاموش کردن وقفهاگر در حین اجرا وقفه را خاموش کنیم؟استفاده های مفید وقفه؟در سیستمهای چند پردازنده ای؟22

اسلاید 23: Mutual Exclusion: Hardware Supportوجود یک دستورالعمل خاص ماشیندستور test&setboolean test&set (boolean b) {if (b) retrun false;else {b = true;return true;}}23

اسلاید 24: Test&Set Usagewhile (true){ while (!test&set(a))/*do nothing*//* critical section*/a=false;/*remainder*/} 24

اسلاید 25: Mutual Exclusion: Hardware Supportدستور Exchangevoid exchange(int register,int memory) {int temp;temp = memory;memory = register;register = temp;}25

اسلاید 26: Process i// a is shared variable initialized to 0while (true){ int ki=1;while (ki!= 0) exchange (ki,a);/* critical section*/exchange (ki,a);/*remainder*/}26

اسلاید 27: Mutual Exclusion Machine Instructionsمزایابه سیستمهای چند پردازنده ای قابل اعمال است.ساده است.27

اسلاید 28: Mutual Exclusion Machine Instructionsعیوبانتظار مشغولیگرسنگیبن بست28

اسلاید 29: Semaphoresسمافور یک متغیر است که مقدار طبیعی دارد.این متغیر نشانگر تعداد فرآیندهایی است که می توانند بدون انتظار از سمافور استفاده کنند.هر عمل wait مقدار سمافور را یک واحد کم می کند.هر عمل signal مقدار سمافور را یک واحد افزایش میدهد.29

اسلاید 30: Semaphoresاگر فرآیندی منتظر یک سیگنال باشد، تا وقتی که سیگنال نرسد مسدود می شود.عملگرهای wait و signal وقفه پذیر نیستند.یک صف برای نگهداری از فرآیندهایی که منتظر یک سمافور هستند، تشکیل می شود.30

اسلاید 31: Definition of Semaphore Primitives (Counting Semaphore)struct semaphore{int count;queueType queue; };void Wait(semaphore s){ s.count--;if (s.count < 0){ place this process in s.queue; block this process;}}void Signal(semaphore s){s.count++;if (s.count ≤ 0){remove a process P from s.queue; place process P on ready list; }}31

اسلاید 32: Definition of Binary Semaphore Primitives struct binary_semaphore { enum {0,1} value; queueType queue; };void WaitB(binary_semaphore s){if (s.value == 1)s.value = 0; else{ place this process in s.queue; block this process;}} void SignalB(binary_semaphore s) {if (s.queue is empty()) s.value = 1;else{remove a process P from s.queue; place process P on ready list; }}32

اسلاید 33: 33

اسلاید 34: Mutual Exclusion Using Semaphoressemaphore s = 1; Pi{while(1) { Wait(s); /* Critical Section */ Signal(s); /* remainder */}}lock = 0;Pi{ while(1) { while(!Test_And_Set(lock)) { }; /* Critical Section */ lock =0; /* remainder */} }34

اسلاید 35: 35

اسلاید 36: Producer/Consumer Problemیک یا چند تولید کننده داده تولید می کنند و در بافر قرار می دهند.یک مصرف کننده داده ها را از بافر برمی دارد و مصرف می کند.در هر لحظه از زمان فقط یک مصرف کننده یا تولید کننده می توانند به بافر دسترسی داشته باشند.این مساله در برنامه نویسی سیستم و برنامه نویسی کاربردی اتفاق می افتد:یک وب سرور درخواستهای وب ورودی را به فرآیندهای منتظر ارسال می کند تا سرویس داده شوند.اتفاقات مربوط به GUI (صادره از صفحه کلید و ماوس) توسط سیستم عامل در یک صف قرار داده می شوند و برنامه ها آنها را مصرف می کنند.36

اسلاید 37: Challengeجلوگیری از سرریز بافرتولید کننده تعداد زیادی آیتم در بافر قرار می دهد و آنرا پر می کند.جلوگیری از قحطیتولید کننده یک آیتم را تولید می کند.مصرف کننده یک آیتم را مصرف می کند.مصرف کننده دوباره یک آیتم دیگر را مصرف می کند. همزمانی مناسبانحصار متقابلپیشرفتانتظار محدود (جلوگیری از بن بست)37

اسلاید 38: Producerproducer:while (true) {/* produce item v */b[in++] = v;}38

اسلاید 39: Consumerconsumer:while (true) { while (in <= out) /*do nothing */;w = b[out++];/* consume item w */}39

اسلاید 40: Buffer40

اسلاید 41: Semaphores41

اسلاید 42: Bounded Buffer42

اسلاید 43: Bounded Bufferinout43

اسلاید 44: Functions in a Bounded Buffer.44

اسلاید 45: Semaphores45

اسلاید 46: Monitorsمانیتور یک ماژول نرم افزاری است.مشخصات اصلی:متغیرهای داده ای محلی فقط توسط خود مانیتور قابل دسترسی هستند. فرآیند با صدا زدن یکی از پروسه های مانیتور وارد آن می شود.در هر لحظه از زمان فقط یک فرآیند در داخل مانیتور در حال اجرا است.46

اسلاید 47: 47

اسلاید 48: A solution to producer-consumer problem using monitor48

اسلاید 49: فرآیند P بر روی یک متغیر شرطی سیگنال میدهد و فرآیند Q به خاطر همان شرط معلق شده است.P صبر میکند تا Q مانیتور را ترک کند.Q صبر میکند تا P مانیتور را ترک کند.49

اسلاید 50: Message Passingدر این روش انحصار متقابل بصورت ضمنی وجود دارد.اطلاعات بین فرآیندها از طریق پیغام رد و بدل می شود.send (destination, message)receive (source, message)50

اسلاید 51: Message Format51

اسلاید 52: Synchronizationفرستنده و گیرنده می توانند در حین ارسال و دریافت پیغام مسدود شوند یا مسدود نشوند.حالت اول: مسدود شدن فرستنده و گیرنده در هنگام مبادله پیغام.حالت دوم: فرستنده غیر مسدود و گیرنده مسدودحالت سوم: فرستنده و گیرنده غیر مسدود.52

اسلاید 53: Addressingآدرس دهی مستقیم:فرستنده آدرس گیرنده را در پیغام قرار می دهد.گیرنده می تواند از پارامتر فرستنده ی پیام برای اطلاع دادن به فرستنده استفاده کند.در گیرنده دو حالت امکان پذیر است:گیرنده دقیقاً از قبل می داند که چه کسی پیغام می فرستد. گیرنده از هر فرستنده ای داده قبول می کند .53

اسلاید 54: Addressingآدرس دهی غیر مستقیم:صندوق پست چهار حالت دارد:یک به یکیک به چندچند به یکچند به چند54

اسلاید 55: Indirect communication paradigms 55

اسلاید 56: Mutual exclusion using message passing56

اسلاید 57: A solution to producer-consumer problem using message passing57