مانیتور (همگام‌سازی)

در برنامه‌نویسی همروند (یا همان برنامه‌نویسی موازی)، مانیتور یک ساختار همگام سازی است که به ریسمان‌ها این امکان را می‌دهد که هم، انحصار متقابل داشته باشند و هم، بتوانند برای یک وضعیت خاص منتظر بمانند (مسدود شوند) تا وضعیت غلط شود. مانیتورها همچنین دارای یک مکانیسم هستند که به ریسمان‌های دیگر، از طریق سیگنال می‌فهمانند که شرایط آن‌ها برآورده شده‌است. یک مانیتور، حاوی یک شئ میوتکس (قفل) و متغیرهای وضعیت است. یک متغیر وضعیت اساساً، ظرفی از ریسمان‌ها است که منتظر یک وضعیت خاص هستند. مانیتورها برای ریسمان‌ها مکانیسمی را فراهم می‌کنند، تا به‌طور موقت، و با هدف منتظر ماندن برای برآورده شدن شرایط خاص، دسترسی انحصاری را رها کنند، و سپس دسترسی انحصاری را مجدداً به‌دست آورند و کار خود را از سر گیرند.
یک تعریف دیگر برای مانیتور عبارت است از یک کلاس، شئ، یا ماژول امنیت-ریسمانی، که دور یک ریسمان می‌پیچد، تا به‌طور ایمن، به بیش از یک ریسمان اجازه دسترسی به یک متد یا متغیر را بدهد. مشخصهٔ تعریف کننده یک مانیتور این است که متدهای آن با انحصار متقابل اجرا می‌شوند: در هر لحظه، حداکثر یک ریسمان می‌تواند هر‌کدام از متدهای آن‌را اجرا کند. همچنین، با فراهم کردن یک یا بیش از یک متغیر شرطی، می‌تواند این قابلیت را به ریسمان ها بدهد تا، منتظر یک شرایط خاص بمانند (و بنابراین، از تعریف بالای یک مانیتور استفاده می‌شود). در ادامهٔ این مقاله، این مفهوم از «مانیتور» را، یک «ماژول/ کلاس/ شئ امنیت-ریسمانی» می‌نامیم.
مانیتورها، توسط آقایان Per Brinch Hansen و C. A. R. Hoare ابداع شدند، و اولین بار در زبان پاسکال همروند آقای Brinch Hansen پیاده‌سازی شدند.

انحصار متقابل

به عنوان یک مثال ساده، یک شئ امنیت ریسمانی را برای انجام تراکنش‌ها در یک حساب بانکی در نظر بگیرید:

monitor class Account {
 private int balance := 0
 invariant balance >= 0

 public method boolean withdraw(int amount)
 precondition amount >= 0
 {
 if balance < amount {
 return false
 } else {
 balance := balance - amount
 return true
 }
 }

 public method deposit(int amount)
 precondition amount >= 0
 {
 balance := balance + amount
 }
}

هنگامی که یک ریسمان یک متد از یک شئ امنیت- رسمانی را اجرا می‌کند، اصطلاحاً گفته می‌شود که، آن شئ را، با نگه داشتن میوتکس (قفل) آن، اشغال کرده‌است. اشیاء امنیت-ریسمانی، به این منظور پیاده‌سازی می‌شوند که مطمئن شویم که در هر زمان حداکثر، یک ریسمان می‌تواند شئ مورد نظر را اشغال کند. قفل، که در ابتدا باز است، در زمان شروع هر متد عمومی بسته می‌شود و در زمان هر بازگشت از متد عمومی باز می‌شود.

یک ریسمان، پس از فراخوانی یکی از متدها، و قبل از شروع اجرای متد خودش، باید منتظر بماند تا زمانیکه هیچ ریسمان دیگری، هیچ‌یک از متدهای شئ امنیت-ریسمانی را اجرا نکند. توجه داشته باشید که بدون این انحصار متقابل در مثال بالا، دو ریسمان می‌توانند موجب شوند تا، بدون هیچ دلیل خاصی، پولی از بین برود یا به دست آید. برای مثال، دو ریسمان، هرکدام با برداشت مقدار ۱۰۰۰ واحد از حساب می‌توانند هر دو، مقدار true را برگردانند، و در عین حال، موجب شوند تا مقدار باقی ماندهٔ حساب فقط به اندازه هزار واحد کاهش پیدا کند؛ به شکل زیر: ابتدا هر دو ریسمان مقدار کنونی حساب را دریافت می‌کنند و متوجه می‌شوند که بیشتر از هزار واحد است و هزار واحد را از آن برمی‌دارند، سپس هر دو ریسمان مقدار مانده حساب را ذخیره می‌کنند و بازمی‌گردند.
کلاس «مانیتور» که در مثال بالا به شکل شکلات نحوی(syntactic sugar) نوشته شده‌است، در واقع کد زیر را با پیچیدن هر کدام از اجراهای تابع در میوتکس‌ها، پیاده‌سازی می‌کند.

class Account {
 private lock myLock

 private int balance := 0
 invariant balance >= 0

 public method boolean withdraw(int amount)
 precondition amount >= 0
 {
 myLock.acquire()
 try {
 if balance < amount {
 return false
 } else {
 balance := balance - amount
 return true
 }
 } finally {
 myLock.release()
 }
 }

 public method deposit(int amount)
 precondition amount >= 0
 {
 myLock.acquire()
 try {
 balance := balance + amount
 } finally {
 myLock.release()
 }
 }
}

متغیر های شرطی

بیان مسئله

در بسیاری از موارد، انحصار متقابل کفایت نمی‌کند. ممکن است لازم باشد تا ریسمان‌هایی که یک عملیات را اجرا می‌کنند، منتظر بمانند، تا برخی شرایط P صحیح(true) شود. یک حلقه انتظار فعال

while not( P ) do skip

کار نخواهد کرد، زیرا انحصار متقابل مانع از این می‌شود که هر‌گونه ریسمان دیگری وارد مانیتور شود تا شرایط را صحیح کند. راه‌حل های دیگری وجود دارند، نظیر: داشتن یک حلقه که قفل مانیتور را باز می‌کند، برای مدت زمان خاصی منتظر می‌ماند، مانیتور را قفل میکند و شرایط P را چک می‌کند. به‌طور تئوری، این روش کار می کند و دچار بن بست نمی‌شود، اما مشکلاتی پیش می‌آید. مشخص کردن مقدار زمان لازم برای انتظار، دشوار است؛ اگر خیلی کم باشد، پروسه‌ی مذکور بیشتر وقت CPU را می‌گیرد و اگر خیلی زیاد باشد، آشکارا بدون پاسخ خواهد بود. آنچه لازم است، شیوه‌ای است که در آن، وقتی‌که شرایط P صحیح شد (یا بتواند صحیح شود)، از طریق یک سیگنال، ریسمان را مطلع کند.

مطالعه موردی: مشکل تولید کننده مصرف کننده محدود کلاسیک

یک مشکل همروندی کلاسیک، مسئله ی تولید کننده-مصرف کننده ی محدود شده است، که در آن یک صف یا بافر حلقوی از کارها وجود دارد که دارای یک گنجایش حداکثر است و در آن یک یا بیش از یک ریسمان نقش تولید کننده را ایفا می کند، یعنی کارهایی را به صف اضافه می‌کند و یک یا بیش از یک ریسمان نقش مصرف کننده را بازی می کند، یعنی کارهایی را از صف خارج می کند. فرض بر این است که خود صف امنیت-ریسمان ای ندارد و می تواند خالی، پر، یا چیزی بین خالی و پر باشد. زمانیکه صف از کارها پر می شود، آنگاه نیاز است تا ریسمان های تولید کننده مسدود شوند تا زمانیکه با خالی کردن کارها از صف توسط مصرف کننده ها، فضا خالی شود. از سوی دیگر، زمانیکه صف خالی است، لازم است تا ریسمان های مصرف کننده مسدود شوند، تا زمانیکه ریسمان های تولیدکننده آیتمی را به صف اضافه کنند تا در اختیار مصرف کننده قرار بگیرد.
از آنجاییکه صف، یک شیء همروند مشترک بین ریسمان ها است، دسترسی به آن باید به صورت اتمیک باشد، زیرا در زمان دسترسی به آن (که هرگز نباید بین ریسمان ها نمایان شود)، می تواند در وضعیت ناسازگار قرار بگیرد. بنابراین، هر کدی که به صف دسترسی پیدا می کند، یک ناحیه بحرانی را تشکیل می دهد که باید به طریق انحصار متقابل همگام سازی شود. اگر تعویض های زمینه ای(context switch) دلخواه بین ریسمان هایی که در یک پردازنده قرار دارند، یا بین ریسمان های موجود در چندین پردازنده که به طور همزمان اجرا می شوند، بتوانند در لابلای کد و دستورالعمل های پردازنده در نواحی بحرانی کد، که به صف دسترسی پیدا می کنند، قرار گیرند، آنگاه خطر نمایان شدن وضعیت ناسازگار یا ایجاد شرایط رقابتی وجود دارد.

نادرست، بدون همگام سازی

یک روش ناشیانه این است که کد مورد نظر را با استفاده از انتظار فعال و بدون همگام سازی طراحی کنیم، که باعث می شود کد در معرض شرایط رقابتی قرار گیرد:

global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.
        while (queue.isFull()) {} // Busy-wait until the queue is non-full.
        queue.enqueue(myTask); // Add the task to the queue.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        while (queue.isEmpty()) {} // Busy-wait until the queue is non-empty.
        myTask = queue.dequeue(); // Take a task off of the queue.
        doStuff(myTask); // Go off and do something with the task.
    }
}

این کد دارای یک مشکل جدی است و آن این است که دسترسی ها به صف ممکن است دچار وقفه شوند و سایر دسترسی های ریسمان ها به صف، در ما بین آن قرار گیرد. متدهای queue.enqueue و queue.dequeue احتمالاً دارای دستورالعمل‌هایی برای به روز رسانی متغیرهای عضو صف، همچون اندازه ی آن، وضعیت های شروع و پایان، نسبت دهی و اختصاص عناصر صف و ... است. علاوه بر این، متدهای ()queue.isEmpty و ()queue.isFull نیز این وضعیت مشترک را می خوانند. اگر این اجازه بدهیم که ریسمان‌های تولیدکننده/مصرف‌کننده در حین فراخوانی ها به enqueue/dequeue در لابلای هم قرار گیرند، آنگاه وضعیت ناسازگار  درصف می توانند نمایان شود، که منجر به شرایط رقابتی می شود. علاوه بر این، اگر یک مصرف کننده در زمان بین خروج مصرف کننده دیگر از انتظار فعال و فراخوان dequeue، صف را تهی کند، آنگاه مصرف‌کننده ی دوم تلاش خواهد کرد تا یک صف خالی را، خالی کند، که منجر به یک خطا می شود. به همین شکل، اگر یک تولید کننده در زمان بین خروج تولیدکننده دیگر از انتظار فعال و فراخوانی enqueue، صف را پر کند، آنگاه مصرف‌کننده دوم تلاش خواهد کرد تا به صفی که پر است اضافه کند، که منجر به یک خطا می‌شود.

انتظار  چرخشی

یک روش ناشیانه برای دستیابی به همگام سازی، که در بالا اشاره ی گذرا به آن شد، استفاده از انتظار چرخشی است که در آن از یک میوتکس برای محافظت از نواحی بحرانی کد استفاده می شود و همچنین از انتظار فعال نیز استفاده می شود و قفل، ما بین چک کردن های انتظار فعال، در اختیار قرار می گیرد و آزاد می شود.

global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock; // A mutex for the ring-buffer of tasks.

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial busy-wait check.
        while (queue.isFull()) { // Busy-wait until the queue is non-full.
            queueLock.release();
            // Drop the lock temporarily to allow a chance for other threads
            // needing queueLock to run so that a consumer might take a task.
            queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isFull()".
        }

        queue.enqueue(myTask); // Add the task to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial busy-wait check.
        while (queue.isEmpty()) { // Busy-wait until the queue is non-empty.
            queueLock.release();
            // Drop the lock temporarily to allow a chance for other threads
            // needing queueLock to run so that a producer might add a task.
            queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isEmpty()".
        }
        myTask = queue.dequeue(); // Take a task off of the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.
        doStuff(myTask); // Go off and do something with the task.
    }
}

در این روش قطعاً وضعیت ناسازگار رخ نمی دهد، اما منابع CPU را، به دلیل انتظار فعال بی مورد، تلف می کند. حتی اگر صف، خالی باشد و ریسمان های تولید کننده به مدت طولانی چیزی برای اضافه کردن نداشته باشند، باز هم ریسمان های مصرف کننده همیشه، و به طور غیرضروری در انتظار فعال هستند. به همین شکل، حتی اگر مصرف کننده ها برای مدت طولانی، روی پردازش کارهای کنونی خود مسدود شوند و صف پر باشد، باز هم تولیدکننده ها همیشه در انتظار فعال هستند. بنابراین، این یک مکانیسم اتلاف کننده است. در اینجا، نیاز به روشی داریم که تا زمانیکه صف غیر پر شود، ریسمان های تولید کننده مسدود شوند، و ریسمان های مصرف کننده را تا زمانیکه صف غیر خالی شود، مسدود کند.
(توجه کنید که خود میوتکس ها هم می توانند قفل های چرخشی باشند، که شامل انتظار فعال به منظور دستیابی به قفل هستند، اما با هدف حل مشکل اتلاف منابع CPU، ما فرض را بر این می گیریم که queueLock یک قفل چرخشی نیست و خودش به شکل درستی از یک صف قفلی مسدود کننده استفاده می کند).

متغیر های شرطی

راه حل این است که از متغیرهای شرطی استفاده کنیم. از نظر مفهومی، متغیر شرطی، صفی از ریسمان ها است همراه با یک میوتکس که ممکن است یک ریسمان، روی آن برای تحقق یک شرط منتظر بماند. بنابراین هر متغیر شرطی c با یک عبارت بررسی صحت(assertion, Pc) همراه است. زمانیکه یک ریسمان منتظر یک متغیر شرطی است، در واقع، آن ریسمان مانیتور را اشغال نمی کند و بنابراین ریسمان های دیگر می توانند وارد مانیتور شوند تا وضعیت مانیتور را تغییر دهند. در اکثر انواع مانیتور ها این ریسمان های دیگر ممکن است با استفاده از سیگنال به متغیر شرطی c نشان دهند که بررسی صحت(assertion, Pc)، در وضعیت کنونی صحیح است.
بنابراین سه عملیات اصلی روی متغیرهای شرطی وجود دارد:
wait c, m : که در آن c یک متغیر شرطی است و m یک میوتکس (قفل) است که به مانیتور مربوط است. این عملیات توسط یک ریسمان فراخوانی می شود که لازم است منتظر بماند تا زمانیکه بررسی سقم وصحت (assertion, Pc) صحیح شود و سپس به کارش ادامه دهد. در زمانیکه ریسمان مذکور منتظر است، در واقع مانیتور را اشغال نمی کند. عملکرد و تعهد اساسی عملیات "انتظار" این است که مراحل زیر را انجام دهد:
۱. به صورت اتمیک:
الف) میوتکس m را آزاد کن،
ب) این ریسمان را از صف اجرا به صف انتظار c (یا همان صف خواب) ریسمان ها منتقل کن و،
ج) این ریسمان را خواب کن. (زمینه به صورت همگام به ریسمان دیگری واگذار می شود)
۲. هنگامی که این ریسمان بعداً آگاه سازی/ سیگنال دهی شد و از سر گرفته شد، آنگاه، به طور خودکار میوتکس m را مجدداً به دست آور.
مرحله ۱-الف و ۱-ب می توانند به هر ترتیبی رخ دهند، و مرحله ۱-ج معمولاً بعد از آن ها رخ می دهد. هنگامی که ریسمان مذکور خوابیده است و در صف انتظار c قرار دارد، شمارنده برنامه بعدی که قرار است اجرا شود، در مرحله ۲، یعنی در وسط تابع ساب روتین انتظار است، بنابراین ریسمان مذکور می خوابد و بعداً در میانه عملیات انتظار بیدار می شود.
اتمیک بودن عملیات در داخل مرحله ۱ مهم است تا از شرایط رقابتی اجتناب شود. این شرایط رقابتی توسط یک تعویض اجباری ریسمان در ما بین آن ها رخ می دهد. اگر این ها به صورت اتمیک نباشند، یک مد شکست می تواند رخ دهد که از بین رفتن بیدار‌کردن (به انگلیسی: wakeup miss) نام دارد، در این نوع مد شکست، ریسمان مذکور می‌تواند،  در حالی که میوتکس را آزاد کرده است، در صف خواب c باشد، اما یک تغییر ریسمان اجباری، قبل از اینکه ریسمان مذکور به خواب رود رخ دهد و ریسمان دیگری  عملیات سیگنال دهی/آگاه‌سازی  را روی c فراخوانی کند و باعث شود که ریسمان اول از صف c خارج  گردد (عقب نشینی کند). به محض اینکه ریسمان اول (مورد بحث) به حالت اول برگردد، شمارنده ی برنامه آن در مرحله ی ۱-ج خواهد بود، و به خواب خواهد رفت و مجدداً قابل بیدار شدن نیست که این قانون را نقض می کند که، باید زمانی که به خواب رفت در صف خواب c قرار داشته باشد. سایر شرایط رقابتی بستگی به ترتیب مراحل ۱-الف و ۱-ب و همچنین بستگی به این دارد که در کجا تعویض زمینه رخ می دهد.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Monitor (synchronization)». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۴ آوریل ۲۰۲۱.