موضوع مقاله: مسئله خواننده-نویسنده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله خواننده-نویسنده | مقدمه: در علوم کامپیوتر مسئله‌های خواننده‌ها- نویسنده‌ها مثال‌هایی از یک مشکل محاسباتی شایع در بحث همروندی هستند. | ## بخش 1: مسئله خواننده-نویسنده | حداقل سه نوع مسئله در این رابطه وجود دارد که با شرایطی در ارتباط است که در آن چندین ریسۀ در حال اجرا به‌طور همزمان سعی می‌کنند تا در یک لحظه به منبع مشترکی دست پیدا کنند. برخی ریسه‌ها ممکن است بخوانند و برخی دیگر ممکن است بنویسند، با این محدودیت که هیچ ریسه‌ای در حالی‌که ریسه دیگری در حال نوشتن در منبع مشترک است، امکان دسترسی به منبع مشترک را چه برای خواندن و چه برای نوشتن نداشته باشد. به‌طور خاص، ما می‌خواهیم تا مانع از این شویم که بیش از یک ریسه به‌طور همزمان منبع مشترک را تغییر ندهند و دو یا بیش از دو خواننده اجازه دسترسی به منبع مشترک را به‌صورت همزمان داشته باشند. یک قفل خواننده‌ها-نویسنده نوعی ساختمان داده‌ای است که یک یا بیش از یک مسئله خواننده‌ها-نویسنده‌ها را حل می‌کند. اولین مسئله خواننده و نویسنده‌ها فرض کنید که ما یک ناحیه مشترک حافظه (ناحیه بحرانی) با محدودیت‌های اساسی ذکر شده در بالا داریم. این امکان وجود دارد تا داده مشترک را در پشت یک انحصار متقابل، mutex، حفاظت کنیم. با این حال، این راه حل بهترین راه حل نیست؛ زیرا این امکان وجود دارد که یک خواننده مثلاً با نام R1 قفل را داشته باشد و سپس خوانندهٔ دیگری مثلاً با نام R2 درخواست دسترسی کند. منطقی نیست که R2 منتظر بماند تا R1 کارش تمام شود و سپس عملیات خواندن را شروع کند، در عوض، R2 باید این اجازه را داشته باشد که همزمان با R1 منبع را بخواند؛ زیرا عملیات خواندن موجب تغییر داده نمی‌شود؛ بنابراین خواندن‌های همزمان بی خطر هستند. این شرایط انگیزه‌ای برای حل اولین مشکل خواننده ها- نویسنده‌ها هست که در آن محدودیت‌هایی اضافه می‌شود که اگر منبع مشترک در حال حاضر برای خواندن باز باشد، هیچ خواننده ای نباید منتظر بماند. زمانی که فایل در برابر نویسنده‌ها قفل شد، خواننده‌های بسیار دیگری، بدون اینکه مجبور باشند قفل آن را مجدداً باز کنند، می‌توانند از آن استفاده کنند. این کار برای این انجام می‌شود تا شرایط رقابتی بین خواننده‌ها به وجود نیاید (در این بستر، شرایط رقابتی شرایطی است که در آن دو یا بیش از دو ریسه به‌طور همزمان از خواب بیدار می‌شوند و تلاش می‌کنند تا وارد بخش بحرانی شوند؛ بدون محدودیت‌های بیشتر، این رفتار نامعین است؛ یعنی دو خواننده به صورت همزمان readcount را افزایش می‌دهند و هر دو سعی می‌کنند تا منبع را قفل کنند. برای عملی کردن این روش هر خواننده که وارد بخش ورود می‌شود، بخش ورود را برای خودش قفل می‌کند تا زمانی که کارش تمام شود. در طی این زمان، خوانندهٔ مذکور منبع را قفل نمی‌کند، و فقط منطقه ورود را قفل می‌کند تا هیچ خواننده دیگری در حالی که او در داخل آن قرار دارد، نتواند وارد این بخش شود. | ## بخش 2: مسئله خواننده-نویسنده | زمانی که خوانندهٔ مذکور اجرای منطقهٔ شروع را به پایان رساند، با سیگنال دهی به mutex قفل آن را باز می‌کند. در یک لحظه بیش از یک خواننده نمی‌تواند در بخش خروج قرار بگیرد، بنابراین هر خواننده ای قبل از استفاده از بخش خروج باید بخش خروج را در اختیار بگیرد و قفل کند. خواننده‌های بعدی فقط می‌توانند از منبع قفل شده (در برابر نویسنده‌ها) استفاده کنند. خواننده ای که آخر از همه تمام می‌کند (توسط متغیر readcount نشان داده می‌شود) باید قفل منبع را باز کند تا منبع در اختیار نویسندگان قرار بگیرد. این بدان معنا است که تعداد زیادی از خواننده‌های متوالی، بعداً می‌توانند دسترسی تمام نویسنده‌های بالقوه را به منبع قفل کنند و آنها را با قحطی منبع مواجه سازند. علت این پدیده این است که بعد از اینکه اولین خواننده منبع را قفل کرد، هیچ نویسنده ای نمی‌تواند آن را قفل کند، تا زمانی که آزاد شود و فقط توسط آخرین خواننده آزاد خواهد شد. دومین مسئله خواننده ها-نویسنده ها راه حل اول بهترین راه حل نبود، زیرا این امکان وجود داشت که یک خواننده مثلاً R1 دارای قفل باشد، یک نویسنده مثلاً W منتظر قفل باشد و سپس یک خواننده مثلاً R2 درخواست دسترسی کند. منصفانه نیست که R2 به طور ناگهانی و قبل از W داخل شود؛ اگر این اتفاق به اندازه کافی رخ دهد، W دچار قطعی منبع خواهد شد. این امر انگیزه ای است برای راه حل مسئله دوم خواننده ها- نویسنده ها که در آن این محدودیت افزوده می‌شود که هیچ نویسنده‌ای، زمانی که به صف وارد شد، نباید بیش از حد ضروری منتظر بماند. فقط اولین نویسنده readTry را قفل می کند، سپس تمام نویسنده های بعدی می توانند به سادگی و پس از آزاد شدن منبع توسط نویسنده قبلی از آن استفاده کنند. آخرین نویسنده باید سمافور را آزاد کند تا دروازه برای خواننده‌ها باز شود که بتوانند بخوانند. اگر سمافور قبلاً توسط یک نویسنده ست شده باشد، هیچ خواننده ای نمی‌تواند درگیر بخش ورود شود. از سوی دیگر، اگر یک خواننده ی خاص سمافور را قفل کرده باشد، به هرگونه نویسنده ی هم روند بالقوه این علامت را می دهد که یک خواننده در بخش ورود قرار دارد. | ## بخش 3: مسئله خواننده-نویسنده | بنابراین، نویسنده منتظر می ماند تا خواننده readTry آزاد کند و سپس نویسنده بلافاصله آن را برای خودش و برای تمام نویسندگان بعدی قفل میکند. با این وجود، نویسنده قادر نخواهد بود تا زمانی که خواننده کنونی منبع را آزاد نکرده است، به منبع دسترسی پیدا کند و منبع زمانی آزاد می‌شود، که خواننده مذکور کارش با منبع در ناحیه بحرانی تمام شده باشد. البته برای انجام این کار، باید ابتدا سمافور readTry را قفل کنند که فقط یکی از آنها در هر لحظه می تواند این کار را انجام دهد. اگر هیچ نویسنده‌ای برای دسترسی به منبع وجود نداشته باشد (شرایطی که توسط وضعیت سمافور readTry به خواننده نشان داده می شود)، آنگاه خواننده‌ها منبع را قفل نخواهند کرد. این کار از این جهت انجام می‌شود تا به یک نویسنده اجازه داده شود تا بلافاصله و به محض اینکه خواننده کنونی خواندن را تمام کرد، کنترل منبع را به دست گیرد. در غیر این صورت، نویسنده مجبور خواهد بود تا منتظر صفی از خواننده ها بماند تا کارشان تمام شود و آخرین خواننده بتواند قفل سمافور readTry را باز کند. سپس، به محض اینکه خواننده کنونی خواندنش تمام شد، کنترل منبع را به دست می گیرد و و مانع از ورود تمام خواننده های بعدی خواهد شد. تنها هدف آن ها اجتناب از شرایط مسابقه ای بین خواننده ها و نویسنده ها است، که این شرایط رقابتی در بخش های ورودی یا خروجی آن ها به وجود می آید. سومین مسئله خواننده ها- نویسنده ها در حقیقت راه حل هایی که توسط هر دو بیان های مسئله به صورت غیر مستقیم ارائه شد، می تواند منجر به قحطی منبع شود؛ راه حل اول ممکن است نویسنده ها را در صف با قحطی مواجه کند، و راه حل دوم ممکن است خواننده ها را با قحطی مواجه کند. بنابراین مسئله ی سوم خواننده ها- نویسنده ها گاهی مطرح می شود و محدودیت هایی را برقرار می کند که بر پایه آن هیچ ریسه ای نباید گرسنگی بکشد؛ این بدان معنا است که عملیات به دست آوردن یک قفل برای داده مشترک همیشه در یک بازه زمانی محدود شده خاتمه می یابد. در غیر این صورت، برای مثال یک نویسنده مسدود شده، در شرایطی که چرخه‌ای از سایر نویسنده ها سمافور را قبل از نویسنده ی مذکور کاهش دهند، ممکن است تا ابد مسدود شده باقی بماند. ساده ترین مسئله خواننده- نویسنده ساده ترین مسئله خواننده -نویسنده که فقط از دو سمافور استفاده میکند و نیازی نیست تا آرایه ای از خواننده ها، داده ی بافر را بخوانند. دقت کنید که این راه حل به این دلیل ساده تر از مورد کلی است که شبیه مسئله بافر محدود شده است و بنابراین فقط تعداد n خواننده اجازه پیدا می‌کنند که به‌صورت موازی وارد شوند. | ## جمع‌بندی | در نویسنده، مقدار سمافور نوشتن به سمافور خواندن داده می‌شود و در خواننده، مقدار خواندن به نوشتن داده می شود ( در هنگام کامل شدن حلقه ).