Concurrency: Mutual Exclusion and Synchronization
اسلاید 1: Concurrency: Mutual Exclusion and Synchronizationفصل پنجم
اسلاید 2: Currencyارتباط بین فرآیندها استفاده ی چند فرایند از یک ناحیه ی مشترکاشتراک منابع استفاده ی چند فرایند از یک منبع مشترکهمزمان سازی فرآیندها استفاده ی چند فرایند از یک پیغام یا سمافور مشترکتخصیص زمان پردازنده استفاده ی چند فرایند از یک یا چند پردازنده ی مشترک
اسلاید 3: Concurrencyچند کاربرد مختلفچند برنامگی – اجرای همزمان چند برنامه ی مرتبطیک کاربرد ساختار یافتهکاربرد می تواند شامل مجموعه ای از فرآیندهای همزمان باشد – اجرای همزمان چند فرآیند یا نخ یک برنامهسیستم عاملسیستم عامل مجموعه ای از فرآیندها و نخها است
اسلاید 4: Difficulties with Concurrencyاشتراک منابع عمومیمدیریت تخصیص منابعتشخیص محل خطاهای برنامه نویسی مشکل است.
اسلاید 5: A Simple Examplevoid echo(){chin = getchar();chout = chin;putchar(chout); }
اسلاید 6: A Simple ExampleProcess P1Process P2. .chin = getchar(); .. chin = getchar();chout = chin; chout = chin;putchar(chout); .. putchar(chout);. .
اسلاید 7: Operating System Concernsدنبال کردن فرآیندهای فعالتخصیص و بازپس گیری منابعزمان پردازنده حافظهفایلهادستگاههای I/Oحفاظت داده و منابعنتیجه اجرای یک فرآیند نباید به سرعت اجرای فرآیندهای همزمان ربط داشته باشد.
اسلاید 8: Process Interactionفرآیندها از وجود همدیگر با اطلاع نیستند.فرآیندها بطور غیر مستقیم از همدیگر اطلاع دارند.فرآیندها بطور مستقیم از همدیگر اطلاع دارند.
اسلاید 9: Competition Among Processes for Resourcesانحصار متقابلنواحی بحرانیدر هر لحظه از زمان فقط یک برنامه می تواند در ناحیه بحرانی باشد.بن بستگرسنگی
اسلاید 10: Cooperation Among Processes by Sharingنوشتن در ناحیه بحرانی باید بصورت انحصار متقابل انجام شود.نواحی بحرانی برای اطمینان از جامعیت داده لازم هستند.
اسلاید 11: Cooperation Among Processes by Communicationتبادل پیغامنیازی به انحصار متقابل نیست.امکان بن بست وجود داردممکن است هر دو فرآیند منتظر پیغام دیگری باشند.امکان گرسنگی داریمدو فرآیند با هم پیغام مبادله می کنند در حالیکه سومی منتظر است.
اسلاید 12: Requirements for Critical Regionانحصار متقابل: در هر لحظه از زمان فقط یک فرآیند می تواند در ناحیه بحرانی باشد.پیشرفت: وقتی که فرآیند دیگری از ناحیه بحرانی استفاده نمی کند، فرآیند متقاضی نباید با تأخیر روبرو شود.فرضهای ساده: در مورد تعداد و سرعت نسبی فرآیندها نباید فرضی انجام شود.تاخیر محدود: مدت استفاده از ناحیه بحرانی برای هر فرآیند محدود است.
اسلاید 13: ProgressMutual ExclusionBounded WaitOversimplifying Assumptionsآیا درها قفل دارند؟اگر بدویم، اولین نفر ما هستیم!کسی بی نوبت داخل نرود!خوب، اصلا دیدی کسی بره تو؟!
اسلاید 14: First Attemptانتظار مشغولیفرآیند مرتب چک می کند که ببیند می تواند وارد ناحیه بحرانی شود یا نه.در این حالت فرآیند تا وقتی که وارد ناحیه بحرانی نشود، هیچ کار مفیدی انجام نمی دهد.اگر فرآیندی در ناحیه بحرانی خود شکست بخورد، فرآیند دیگر تا ابد مسدود خواهد بود.فرآیندها به نوبت از ناحیه بحرانی استفاده می کنند.
اسلاید 15: Second Attemptهر فرآیند می تواند وضعیت دیگران را ببیند، اما نمی تواند آنرا تغییر دهد.وقتی که فرآیند می خواهد وارد ناحیه بحرانی شود، ابتدا وضعیت دیگران را چک می کند.اگر هیچ فرآیندی در ناحیه بحرانی نباشد، فرآیند ما وضعیت خود را به ناحیه بحرانی تغییر می دهد. متاسفانه این متد انحصار متقابل را تضمین نمی کند.ممکن است دو فرآیند با هم ناحیه بحرانی را خالی ببیند و با هم وارد آن شوند.
اسلاید 16: Third Attemptقبل از چک کردن وضعیت دیگران، وضعیت خود را به حالت بحرانی تغییر دهیم.اگر بعد از این کار دیدیم که فرآیند دیگری در ناحیه بحرانی است، فرآیند تا خالی شدن ناحیه بحرانی مسدود می شود.در این حالت امکان بن بست وجود دارد- اگر دو فرآیند همزمان بخواهند وارد ناحیه بحرانی شوند ، هر کدام به اشتباه فکر می کنند که دیگری در ناحیه بحرانی است وهر دو تا ابد مسدود خواهند ماند.
اسلاید 17: Fourth Attemptفرآیند یک پرچم را به نشانه تمایل خود به استفاده از ناحیه بحرانی روشن می کند، اما این آمادگی را دارد که در صورت لزوم پرچم را خاموش کند.سپس، فرآیندهای دیگر را چک می کند. اگر کسی در ناحیه بحرانی باشد پرچم را خاموش می کند و در زمان دیگری آنرا روشن می کند. این عمل تا وقتی که وارد ناحیه بحرانی نشود تکرار می گردد.
اسلاید 18: Fourth Attemptفرض کنید ناحیه بحرانی خالی است. ممکن است که دو فرآیند پرچم خود را روشن کنند، دیگری را چک کنند و دوباره پرچم را خاموش کنند. این امر البته خیلی طول نخواهد کشید و بن بست اتفاق نمی افتد اما مطلوب نیست.
اسلاید 19: Correct Solutionهر فرآیند یک نوبت برای ناحیه بحرانی می گیرد.اگر فرآیند بخواهد وارد ناحیه بحرانی شود ابتدا پرچم خود را روشن می کند و منتظر نوبتش می ماند.
اسلاید 20: Dekker Alghorithm
اسلاید 21: Peterson Algorithm
اسلاید 22: Mutual Exclusion: Hardware Supportخاموش کردن وقفهدر حالت عادی وقتی فرآیندی اجرا می شود به دو دلیل ممکن است متوقف شود:وقوع وقفهدرخواست یک خدمت سیستم عامللذا اگر در حین اجرا وقفه را خاموش کنیم، انحصار متقابل تضمین می گردد.این امر استفاده های مفید وقفه را از بین می برد.در سیستمهای چند پردازنده ای، خاموش کردن وقفه در یکی از پردازنده ها انحصار متقابل را تضمین نمی کند.
اسلاید 23: Mutual Exclusion: Hardware Supportوجود یک دستورالعمل خاص ماشین (اسمبلی)باید در یک سیکل اجرا شود.لذا دستورات دیگر روی آن تاثیری ندارند.دستور test&setboolean testset (int i) {if (i == 0) {i = 1;return true;}else {return false;}}
اسلاید 24: Test&set Usagewhile (true){ while (!test&set(a))/*do nothing*//* critical section*/a=0;/*remainder*/}
اسلاید 25: Mutual Exclusion: Hardware Supportدستور Exchangevoid exchange(int register, int memory) {int temp;temp = memory;memory = register;register = temp;}
اسلاید 26: Process i/* a is shared variable initialized to 0int ki=1;while (true){ do exchange (ki,a);while (ki!=0)/* critical section*/exchange (a,ki);/*remainder*/}
اسلاید 27: Mutual Exclusion Machine Instructionsمزایابه سیستمهای چند پردازنده ای قابل اعمال است.ساده است.می توان چندین ناحیه بحرانی داشت.
اسلاید 28: Mutual Exclusion Machine Instructionsعیوبانتظار مشغولی وقت پردازنده را مصرف می کند.امکان گرسنگی وجود دارد. اگر یک فرآیند ناحیه بحرانی را ترک کند و چند فرآیند منتظر ورود باشند. بن بست:اگر یک فرآیند کم اهمیت داخل ناحیه بحرانی باشد و یک فرآیند مهم به ناحیه بحرانی نیاز داشته باشد. فرآیند مهم تر پردازنده را با وقفه در اختیار می گیرد.فرآیند کم اهمیت تر تا ابد منتظر ناحیه بحرانی می ماند، زیرا هیچوقت به فرآیند معمولی اجازه در اختیار گرفتن پردازنده و اتمام کار داده نمی شود.
اسلاید 29: Semaphoresسمافور یک متغییر مخصوص است که برای مبادله سیگنال از آن استفاده می گردد.اگر فرآیندی منتظر یک سیگنال باشد، تا وقتی که سیگنال نرسد مسدود می شود.عملگرهای wait و signal وقفه پذیر نیستند.یک صف برای نگهداری از فرآیندهایی که منتظر یک سمافور هستند ، تشکیل می شود.
اسلاید 30: Semaphoresسمافور دارای یک متغییر است که مقدار طبیعی دارد.این متغییر نشانگر تعداد فرآیندهایی است که می توانند بدون انتظار از سمافور استفاده کنند.هر عمل wait مقدار سمافور را یک واحد کم می کند.هر عمل signal مقدار سمافور را یک واحد افزایش می دهد.
اسلاید 31: Definition of Semaphore Primitives (Counting Semaphore)struct semaphore{int count;queueType queue; };void semWait(semaphore s){ s.count--;if (s.count < 0){ place this process in s.queue; block this process;}}void semSignal(semaphore s){s.count++;if (s.count ≤ 0){remove a process P from s.queue; place process P on ready list; }}
اسلاید 32: Definition of Binary Semaphore Primitives struct binary_semaphore { enum {0,1} value; queueType queue; };void semWaitB(binary_semaphore s){if (s.value == 1)s.value = 0; else{ place this process in s.queue; block this process;}} void semSignalB(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; }}
اسلاید 33: Mutual Exclusion Using Semaphoressemaphore s = 1; Pi{while(1) { semWait(s); /* Critical Section */ semSignal(s); /* remainder */}}lock = 0;Pi{ while(1) { while(!Test_And_Set(lock)) { }; /* Critical Section */ lock =0; /* remainder */} }
اسلاید 34: Value of SemaphorelockQueueAsemWait(lock)01semWait(lock)BB-1semSignal(lock)0semSignal(lock)1ProcessProcess Critical RegionNormal ExecutionBlocked onsemaphore lock
اسلاید 35: Producer/Consumer Problemیک یا چند تولید کننده داده تولید می کنند و در بافر قرار می دهند.یک مصرف کننده داده ها را از بافر برمی دارد و مصرف می کند.در هر لحظه از زمان فقط یک مصرف کننده یا تولید کننده می توانند به بافر دسترسی داشته باشند.این مساله در برنامه نویسی سیستم و برنامه نویسی کاربردی اتفاق می افتد:یک وب سرور درخواستهای وب ورودی را به فرآیندهای منتظر ارسال می کند تا سرویس داده شوند.اتفاقات مربوط به GUI (صادره از صفحه کلید و ماوس) توسط سیستم عامل در یک صف قرار داده می شوند و برنامه ها آنها را مصرف می کنند.
اسلاید 36: Producer-Consumer Problemمی توان با یک بافر حلقوی و دو اشاره گر برای درج و حذف داده مسأله را حل کرد.insertPtrremovePtr
اسلاید 37: Challengeجلوگیری از سرریز بافرتولید کننده تعداد زیادی آیتم در بافر قرار می دهد و آنرا پر می کتد.جلوگیری از قحطیتولید کننده یک آیتم را تولید می کند.مصرف کننده یک آیتم را مصرف می کند.مصرف کننده دوباره یک آیتم دیگر را مصرف می کند. همزمانی مناسبانحصار متقابلپیشرفتانتظار محدود (جلوگیری از بن بست)
اسلاید 38: 2 Counting Semaphores and a mutexیک سمافور برای شمارش آیتمهای موجود در بافریک سمافور برای شمارش جاهای خالی (slots) در بافریک سمافور برای قفل کردن ناحیه بحرانی
اسلاید 39: Assembling the solutionsem_wait(slots), sem_post(slots)sem_wait(items), sem_post(items)sem_wait(mutex)و sem_post(mutex)insertptr=(insertptr+1) % Nremovalptr=(removalptr+1) % Nمقدار اولیه سمافور slots برابر سایز بافر است.مقدار اولیه سمافور items برابر صفر است. مقدار اولیه سمافور mutex برابر یک است.
اسلاید 40: Pseudocode getItem()sem_wait(items)sem_wait(mutex)result=buffer[ removePtr ];removePtr=(removePtr +1 ) % Nsem_post(mutex)sem_post(slots)
اسلاید 41: Pseudocode putItem(data)sem_wait(slots)sem_wait(mutex)buffer[ insertPtr]= data;insertPtr=(insertPtr + 1 ) % Nsem_post(mutex)sem_post(items)
اسلاید 42: Analysis#1 Whats the precise problem?putItem(data) {sem_wait(mutex)sem_wait(slots) buffer[ insertPtr]= … insertPtr=…sem_post(items)sem_post(mutex)}getItem() {sem_wait(mutex)sem_wait(items) result=buffer[ removePtr ]; removePtr=…sem_post(slots)sem_post(mutex) }
اسلاید 43: Deadlock e.g Consumer waits for producer to insert a new item but Producer is waiting for Consumer to release mutexputItem(data) {sem_wait(mutex) #2sem_wait(slots) buffer[ insertPtr]= … insertPtr=…sem_post(items)sem_post(mutex)}getItem() {sem_wait(mutex)sem_wait(items) BLOCKS #1 result=buffer[ removePtr ]; removePtr=…sem_post(slots)sem_post(mutex) }
اسلاید 44: Analysis#2 putItem(data) {sem_wait(slots)sem_wait(mutex) buffer[ insertPtr]= … insertPtr=…sem_post(items)sem_post(mutex)}getItem() {sem_wait(items)sem_post(slots)sem_wait(mutex) result=buffer[ removePtr ]; removePtr=…sem_post(mutex)}
اسلاید 45: Buffer overflow when reader removes item from a full buffer: Producer inserts item too earlyputItem(data) {sem_wait(slots)sem_wait(mutex) buffer[ insertPtr]= … insertPtr=…sem_post(items)sem_post(mutex)}getItem() {sem_wait(items)sem_post(slots)sem_wait(mutex) result=buffer[ removePtr ]; removePtr=…sem_post(mutex)}
اسلاید 46: First Reader-Writer Problemخواننده: خواندن دادهنویسنده: نوشتن دادهقوانین:چند خواننده می توانند داده را با هم بخوانند.در هر زمان فقط یک نویسنده می تواند داده را بنویسد.یک خواننده و نویسنده با هم نمی توانند در ناحیه بحرانی باشند.
اسلاید 47: Writer while (TRUE) {Think_up_data(); /*noncritical section*/sem_wait(&wrt); do writing Sem_post(&wrt); }Reader while (TRUE) { sem_wait(&mutex); readcount =readcount+1; if readcount == 1 then sem_wait(&wrt); sem_post(&mutex); do reading sem_wait(&mutex)readcount=readcount-1; if readcount == 0 then sem_post(&wrt); sem_post(&mutex); Use read data }Reader-writer solution using semaphores
اسلاید 48: Monitorsمانیتور یک ماژول نرم افزاری است.مشخصات اصلی:متغییرهای داده ای محلی فقط توسط خود مانیتور قابل دسترسی هستند. فرآیند با صدا زدن یکی از پروسه های مانیتور وارد آن می شود.در هر لحظه از زمان فقط یک فرآیند در داخل مانیتور در حال اجرا است.
اسلاید 49:
اسلاید 50: A solution to producer-consumer problem using monitor
اسلاید 51: Message Passingدر این روش انحصار متقابل بصورت ضمنی وجود دارد.اطلاعات بین فرآیندها از طریق پیغام رد و بدل می شود.send (destination, message)receive (source, message)
اسلاید 52: Synchronizationفرستنده و گیرنده می توانند در حین ارسال و دریافت پیغام مسدود شوند یا مسدود نشوند.حالت اول: مسدود شدن فرستنده و گیرنده در هنگام مبادله پیغام.این روش وعده گاه نیز نامیده شده است.حالت دوم: فرستنده غیر مسدود و گیرنده مسدود: در این حالت گیرنده تا وقتی که پیغام را بطور کامل دریافت نکند مسدود می شود. اما فرستنده می تواند به کار خود ادامه دهد.حالت سوم: فرستنده و گیرنده غیر مسدود.
اسلاید 53: Addressingآدرس دهی مستقیم:فرستنده آدرس گیرنده را در پیغام قرار می دهد.گیرنده می تواند از پارامتر فرستنده ی پیام برای اطلاع دادن به فرستنده استفاده کند.در گیرنده دو حالت امکان پذیر است:گیرنده دقیقاً از قبل می داند که کی برای آن پیغام می فرستد. (برای ارتباط دو فرآیند مفید است).گیرنده از هر فرستنده ای داده قبول می کند .
اسلاید 54: Addressingآدرس دهی غیر مستقیم:پیغامها به یک ساختار داده مشترک که جعبه پستی نام دارد فرستاده می شوند.فرآیند پیغام را به جعبه پستی می فرستد و دیگری پیغام را بر می دارد.چهار حالت دارد:یک نفر به یک نفریک نفر به چند نفرچند نفر به یک نفرچند نفر به چند نفر
اسلاید 55: Indirect communication paradigms
اسلاید 56: Message Format
اسلاید 57: Mutual exclusion using message passing
اسلاید 58: A solution to producer-consumer problem using message passing
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.