سمافور

در علم رایانه سمافور (به انگلیسی: Semaphore) به متغیری گفته می‌شود که در محیط‌های همروند برای کنترل دسترسی فرایندها به منابع مشترک به کار می‌رود. سمافور می‌تواند به دو صورت دودویی (که تنها دو مقدار صحیح و غلط را دارا است) یا شمارنده اعداد صحیح باشد. از سمافور برای جلوگیری از ایجاد وضعیت رقابتی میان فرایندها استفاده می‌گردد. به این ترتیب، اطمینان حاصل می‌شود که در هر لحظه تنها یک فرایند به منبع مشترک دسترسی دارد و می‌تواند از آن بخواند یا بنویسد (انحصار متقابل)

سمافورها اولین بار به‌وسیلهٔ دانشمند علوم رایانه هلندی، ادسخر دیکسترا معرفی شدند.^[۱] و امروزه به‌طور گسترده‌ای در سیستم عاملها مورد استفاده قرار می‌گیرند.

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

منشی که در پیشخوان حاضر است، پیگیری نمی‌کند که کدام اتاق اشغال شده‌است یا چه کسی از آن اتاق استفاده می‌کند، او تنها تعداد اتاق‌های خالی را می‌داند. وقتی که دانشجویی اتاقی را تقاضا می‌کند، منشی تعداد اتاق ‌های خالی را یک واحد کم می‌کند. وقتی که دانشجویی اتاقی که قبلاً گرفته بود را پس می‌دهد، منشی این عدد را یک واحد افزایش می‌دهد. وقتی که دانشجویی توانست اتاقی را بردارد، می‌تواند تا هر وقت که خواست همان‌جا بماند و از آن استفاده کند، بنابراین رزرو کردن اتاق‌ها از قبل امکان‌پذیر نیست.

در مثال بالا، پیشخوان همان نقش سمافور را بازی می‌کند. دانشجوها همان پروسه‌هایی هستند که منابع را درخواست می‌کنند و اتاق‌ها هم مان منابعی هستند که در بین پروسه‌ها به اشتراک گذاشته می‌شود. مقدار اولیه سمافور در این مثال ۱۰ است. وقتی که اولین دانشجو اتاقی را درخواست می‌کند، منشی اتاق را به او اختصاص داده و مقدار سمافور را به ۹ کاهش می‌دهد. وقتی که دانشجوی بعدی وارد شد، این عدد به ۸ و سپس به ۷ و به همین ترتیب کاهش می‌یابد. اگر دانشجویی اتاقی را درخواست دهد، اما مقدار سمافور منفی باشد، مجبور است منتظر بماند تا یکی از دانشجوها اتاقش را پس دهد.

شمارش سمافورها با دو عملیات همراه است. به‌طور تاریخی، به این دو عملیات V (یا signal()‎) و P (یا wait()‎) می‌گویند. اگر سمافوری به نام S داشته باشیم، عملیات V آن را یک واحد افزایش می‌دهد و عملیات P یک واحد آن را کاهش می‌دهد. معانی این دو عملیات در زیر نشان داده شده‌است. براکت‌ها به معنی عملیات اتمی هستند. عملیات اتمی به عملیاتی می‌گویند که تجزیه ناپذیر باشد، یا کل آن اجرا می‌شود یا اصلاً اجرا نمی‌شود. به عبارت دیگر، عملیات از دید پروسه‌ها غیرقابل قسمت هستند.

مقدار سمافور S نشان‌دهنده تعداد واحد منابعی است که در حال حاضر در دسترس هستند و پروسه‌ها می‌توانند از آن استفاده کنند. عملیات P، وقت را تلف می‌کند یا پروسه را به خواب می‌برد تا وقتی که یکی از منابع اشغال شده مجدداً آزاد شود، وقتی که منبع آزاد شد، بلافاصله به پروسه اختصاص می‌یابد. عملیات V برعکس است. وقتی که پروسه‌ای کارش را با منبع به اتمام رساند، با استفاده از عملیات V می‌تواند آن را آزادسازی کند تا دیگر پروسه‌ها بتوانند از آن استفاده کنند. خصوصیت مهم سمافور S این است که مقدار آن را تنها می‌توان به وسیله عمیات‌های V و P تغییر داد.

یک راه ساده برای فهم عملیات‌های wait()‎ و signal()‎ به صورت زیر است:

• wait()‎: مقدار سمافور را یک واحد کاهش داده و یک واحد از منبع اشتراکی را مصرف می‌کند. اگر در هنگام کاهش، مقدار منفی شد، پروسه‌ای که wait()‎ را اجرا کرده بلوکه می‌شود و در انتهای صف سمافور قرار می‌گیرد تا منابع توسط پروسه‌های دیگر آزاد شوند.
• signal()‎: مقدار سمافور را یک واحد افزایش می‌دهد. پس از افزایش دادن، اگر مقدار قبل سمافور منفی باشد (به این معنی که در حال حاضر پروسه‌هایی در صف سمافور منتظر دریافت منبع هستند)، یکی از پروسه‌ها از صف آماده وارد صف اجرا می‌شود و منبع آزاد شده را در اختیار می‌گیرد.

function V(semaphore S, integer I):
    [S ← S + I]

function P(semaphore S, integer I):
    repeat:
        [if S>= 0:
            S ← S - I
            break]

اصل اساسی این است که دو یا چند فرایند می‌توانند به وسیلهٔ سیگنال‌های ساده با یکدیگر همکاری کنند. هر فرایند را می‌توان در نقطهٔ خاصی از اجرا متوقف نموده، و تا رسیدن سیگنال خاصی از اجرای آن جلوگیری نمود. برای ایجاد این اثر، از متغیرهای خاصی به نام سمافور استفاده می‌گردد.

هر فرایندی که بخواهد به منبع مشترک دسترسی داشته باشد، اعمال زیر را انجام خواهد داد:

1. مقدار سمافور را بررسی می‌کند.
2. در صورتی که مقدار سمافور مثبت باشد، فرایند می‌تواند از منبع مشترک استفاده کند. در این صورت، فرایند یک واحد از سمافور می‌کاهد تا نشان دهد که یک واحد از منبع مشترک را استفاده نموده‌است.
3. در صورتی که مقدار سمافور صفر یا کوچکتر از صفر باشد، فرایند به خواب می‌رود تا زمانی که سمافور مقداری مثبت به خود بگیرد. در این حالت فرایند از خواب بیدار شده و از مرحلهٔ یک شروع می‌کند.

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

سمافور متغیری است که میان چند فرایند به اشتراک گذاشته می‌شود. سمافور باید مستقل از فرایندها بوده و در فضایی از حافظه قرار گیرد که فرایندها بتوانند به آن دسترسی داشته باشند، همچنین عملیاتی که روی سمافور انجام می‌گیرد باید به صورتی پیاده‌سازی گردد که هیچ گونه وقفهای هنگام انجام آن عملیات به وجود نیاید (اتمیک باشد). به همین دلیل، سمافور در هسته سیستم‌عامل پیاده‌سازی می‌گردد و کنترل آن نیز توسط سیستم عامل صورت می‌گیرد. به این معنی که فرایندها تنها می‌توانند توسط فراخوانی سیستم (syscall یا system call) با سمافورها کار کنند.

در سیستم عامل‌هایی که از استاندارد پوزیکس پیروی می‌کنند، دو فراخوان سیستمی semget و semctl برای کار با سمافورها وجود دارد.^[۲]

از سمافورها برای حل مسائل همزمانی میان فرایندها به کار می‌رود و امروزه در تمامی سیستم‌عامل‌ها پیاده‌سازی شده‌است. سمافورها معمولاً به‌طور مستقیم مورد استفاده قرار نمی‌گیرند، مگر در جایی که راه حل سطح بالایی وجود نداشته باشد. چرا که برنامه‌نویس می‌تواند با ایجاد شرایطی، به بن‌بست رسیده یا فرایندهایی را گرسنه نگاه دارد (اجازهٔ دسترسی به منبع را برای مدتی طولانی ندهد.)

استاندارد پازیکس دسته‌ای تابع برای کار بر روی سمافورها تعریف می‌کند که در سیستم‌عاملهای سازگار با این استاندارد قابل استفاده هستند. برای استفاده از این توابع باید فایل سرایند semaphore.h را در کد منبع درج کرد. در این استاندارد یک نوع داده به نام sem_t تعبیه شده که برای تعریف کردن یک ساختار از نوع سمافور استفاده می‌شود:

sem_t mysem;

به کمک تابع sem_init()‎ می‌توان یک سمافور را آماده‌سازی کرد. قبل از انجام هر کاری، این تابع باید بر روی سمافور اجرا شود. این تابع به شکل زیر اعلان شده است:

int
sem_init(sem_t *sem, int pshared, unsigned int value);

پارامتر sem همان ساختار نوع sem_t است که باید به روش فراخوانی با ارجاع به تابع ارسال شود. پارامتر value مقدار اولیه سمافور را تعیین می‌کند. به عبارت دیگر، این تابع مقدار value به عنوان مقدار اولیه سمافور sem تعیین می‌کند. اگر پارامتر pshared غیر صفر باشد، مشخص‌کننده سمافور مشترکی است که می‌تواند توسط چند فرایند مورد استفاده قرار بگیرد. به عبارت دیگر، پارامتر pshared تعیین می‌کند که آیا سمافور قرار است بین ریسه‌های یک فرایند به اشتراک گذاشته شود یا بین چند فرایند مجزا. برای اشتراک گذاشتن یک سمافور بین چند فرایند، سمافور باید در یک حافظه مشترک قرار گیرد تا همه فرایندها بتوانند به آن دسترسی داشته باشند. هر پروسه‌ای که به آدرس sem دسترسی داشته باشد، می‌تواند بر روی سمافور عملیات انجام دهد. بعد از اینکه این تابع بر روی یک سمافور با موفقیت اجرا شد، می‌تواند از آن سمافور در توابع دیگر استفاده کرد. این تابع در صورت موفقیت مقدار صفر و در صورت شکست مقدار ‎-1 را برمی‌گرداند و متغیر سراسری errno را با خطای مورد نظر مقداردهی می‌کند.

int
sem_getvalue(sem_t * restrict sem, int * restrict sval);

این تابع مقدار فعلی سمافور sem را در متغیر sval قرار می‌دهد. در صورت موفقیت مقدار صفر و در صورت شکست مقدار -۱‎ برمی‌گردد.

int
sem_wait(sem_t *sem);

این تابع یک واحد از سمافور sem کم می‌کند، به این معنی که قرار است یک واحد از منبع اشتراکی استفاده شود. فرایند باید قبل از استفاده از منبع اشتراکی این تابع را بر روی سمافور اجرا کند. اگر مقدار فعلی سمافور صفر باشد (به این معنی که هم‌اکنون منبع اشتراکی در اختیار فرایند دیگری است)، فرایند فراخوان بلوکه می‌شود، تا وقتی که فرایند دیگر منبع اشتراکی را آزاد کند.

int
sem_trywait(sem_t *sem);

این تابع هم مشابه sem_wait است. اما اگر مقدار سمافور صفر باشد، پروسه بلوکه نخواهد شد و در عوض یک خطا برخواهد گشت.

int
sem_post(sem_t *sem);

این تابع سمافور sem را یک واحد افزایش می‌دهد. پس از اینکه فرایندها کار خود را با منبع اشتراکی به اتمام رساندند، باید این تابع را بر روی سمافور فراخوانی کنند تا فرایندهای دیگر بتوانند از منبع استفاده کنند. اگر در حال حاضر فرایند(هایی) بر روی سمافور بلوکه شده باشد، فرایندی که اولویت بالاتری دارد بیدار شده و منبع را در دست خواهد گرفت. در صورت موفقیت مقدار صفر را برمی‌گرداند.

int
sem_destroy(sem_t *sem);

این تابع سمافور sem را نابود می‌کند و منابع آن را به سیستم برمی‌گرداند. پس از اینکه این تابع بر روی یک سمافور با موفقیت اجرا شد، سمافور مورد نظر دیگر قابل استفاده نیست و هیچ تابعی نباید بر روی آن منتظر دستیابی به منبع اشتراکی باشد. مگر اینکه بار دیگر هم تابع sem_init روی سمافور اجرا شود.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

sem_t lock;
pthread_t tid[3];

int count;

void* init(void*);

int main()
{
	int i;

	if(0 != (sem_init(&lock, 0, 1)))
	{
		perror("sem_init()");
		exit(EXIT_FAILURE);
	}

	for(i=0; i<3; i++)
	{
		
		if(0 != (pthread_create(&tid[i], NULL, init, NULL)))
		{
			perror("pthread_create()");
			exit(EXIT_FAILURE);
		}
	}

	for(i=0; i<3; i++)
	{
		if(0 != (pthread_join(tid[i], NULL)))
		{
			perror("pthread_join()");
			exit(EXIT_FAILURE);
		}
	}

	if(0 != (sem_destroy(&lock)))
	{
		perror("sem_destroy()");
		exit(EXIT_FAILURE);
	}

	return 0;
}

void* init(void* arg)
{
	if(0 != (sem_wait(&lock)))
	{
		perror("sem_wait()");
		exit(EXIT_FAILURE);
	}

	(void)printf("%d\n", count++);

	if(0 != (sem_post(&lock)))
	{
		perror("sem_post()");
		exit(EXIT_FAILURE);
	}

	return NULL;
}

• همروندی
• کنترل همروندی