الگوریتم نانوایی
الگوریتم نانوایی (به انگلیسی: Bakery algorithm)، الگوریتمی رایانه‌ای است که توسط لزلی لمپورت، دانشمند علوم کامپیوتر ابداع شده‌است. این الگوریتم، با استفاده از انحصار متقابل، ایمنی استفاده از منابع مشترک توسط ریسه (Thread)هایی که به‌طور همزمان اجرا می‌شوند را بهبود می‌بخشد. در مسائل مربوط به علوم کامپیوتر، در بسیاری از اوقات چندین ریسه به‌طور همزمان سعی در دستیابی به منبع مشترکی را دارند. این منبع مشترک می‌تواند یک شمارش گر، محلی از حافظه، قطعه‌ای از کد برنامه، یا هر منبع دیگری باشد. اگر دو یا چند ریسه به‌طور همزمان بر روی بخشی از حافظه بنویسند، یا یکی قبل از آنکه دیگری فرایند نوشتن را تمام کرده باشد، همان حافظه را بخواند، اصطلاحاً خرابی داده (Data corruption) اتفاق می‌افتد. الگوریتم نانوایی لمپورت یکی از چندین الگوریتم کامپیوتری است که با استفاده از انحصار متقابل، از ورود ریسه‌های همزمان به بخش‌های بحرانی کد و در نتیجه خرابی داده، جلوگیری می‌کند.
قیاس ویرایش
لزلی لمپورت برای توضیح الگوریتمش، از یک مثال ساده نانوایی با سیستم شماره دهی استفاده می‌کند. فرض کنید که ورودی این نانوایی، دستگاهی وجود دارد که به مشتری‌ها شمارهٔ منحصر به فردی می‌دهد (مشابه سیستم نوبت دهی در بانک‌ها). هر شمارهٔ این دستگاه، یکی بیشتر از شمارهٔ قبلی آن است. یک نمایشگر عمومی نیز در نانوایی مثال ما وجود دارد که تعداد مشتری‌هایی که در حال خدمت گرفتن هستند را نشان می‌دهد. تمامی مشتریان دیگر باید در صفی به انتظار می‌نشینند تا نانوا، کار مشتری فعلی را راه بیندازد و شمارهٔ نفر بعدی روی نمایشگر ظاهر شود. هنگامی که مشتری نانش را تحویل بگیرد و شمارهٔ خود را نیز دور بیندازد، نانوا شمارشگر را یکی افزایش می‌دهد تا نوبت نفر بعدی شود. اگر کسی با استفاده از شماره اش، نانش را تحویل بگیرد، و دوباره بخواهد نان جدیدی بخرد، طبیعتاً باید شمارهٔ جدیدی بگیرد.
در این قیاس، مشتری‌ها همان ریسه‌ها هستند.
به علت محدودیت در معماری و ساختار رایانه، در الگوریتم لمپورت باید تغییرات کوچکی داده شود. محتمل است که بیش از یک ریسه شمارهٔ یکسانی را دریافت کنند (شماره‌ها کاملاً منحصر به فرد نیستند). به عنوان مثال، ممکن است دو مشتری گوناگون هر دو شمارهٔ ۱۰ را از دستگاه بگیرند. از آنجا که در این الگوریتم فرض شده‌است که هر مشتری شناسه‌ای دارد (نام و نام خانوادگی برای مشتری‌ها و رتبه برای ریسه‌ها)، در چنین مواقعی، ریسه‌ای با شناسهٔ کوچک‌تر را انتخاب می‌کنیم. در نتیجه، اگر دو ریسه برای ورود به بخش بحرانی برنامه با یکدیگر در حال رقابت هستند و هر دو ریسه یک شماره دارند، ریسه با شناسهٔ کوچک‌تر اولویت دارد و پیش از ریسهٔ دیگر به بخش بحرانی کد وارد می‌شود.
جستارهای وابسته ویرایش
منابع ویرایش
- مشارکت‌کنندگان ویکی‌پدیا. «Lamport's bakery algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۴ فروردین ۱۳۹۴.