برنامه نویسی چند نخی با POSIX
فهرست مطالب
مفاهیم اولیه نخها
برنامه نویسی چند نخی
مدلهای پیاده سازی نخها
انواع مدلهای نخ کشی
ایجاد و خاتمه نخ در POSIX
قابلیت الحاق
ارتباط بین نخها و همگام سازی
نخ (thread)
نخ یک جریان اجرایی در فرآیند(process) می باشد که می- تواند بصورت مستقل، توسط هسته زمانبندی گردد و از فضای آدرسی یکسان باسایر نخها به اشتراک استفاده نماید.
مستقل بودن
چون نخها بصورت مستقل زمانبندی می شوند، نخها بصورت همروند با سایر نخها اجرا می شوند و امکان اجرای موازی در سیستمهای چند پردازنده ای وجود دارد. این بدین معناست که هر نخ باید منابع مربوط به خودش داشته باشد:
شمارنده برنامه
فضای پشته
مجموعه ثبات ( فضایی برای ذخیره کردن مقدار ثباتها زمانی که پردازنده در اختیار ندارد)
اولویت(بهره گیری از زمانبندی پردازنده )
همروندی(concurrency)
عملیات همروند هستند اگر امکان اجرای نوبتی آنها فراهم گردد بنحویکه اجرای هر عملیات بصورت مستقل پیشرفت داشته باشد.
نخها می توانند برای استفاده از پردازنده با هر ترتیبی و با هر نخ دیگر زمانبندی شوند. ممکن است پردازنده از یک نخ در هر نقطه از اجرایش گرفته شده و با نخ دیگری جایگزین شود.
عملیات که سبب توقف اجرای یک نخ شده، سبب توقف اجرای سایر نخ ها نمی شود.
اگر ترتیب اجرای یک نخ مهم باشد یا یک نخ باید قبل از اجرای نخ دیگری کارش به پایان برسد، بنابراین اجرای نخ باید برای هماهنگی عملیات همگام گردد.
مزایای برنامه نویسی چند نخی
بهره گیری از اجرای موازی بر روی معماری چند پردازنده- ای برای اجرای سریعتر.
افزایش کارایی روی معماری تک پردازنده ای بوسیله فراهم آوردن امکان اجرای یک فرآیند بهنگام عملیات کُند ورودی-خروجی یا بلاک شدن عملیاتهای دیگر.
پاسخدهی سریعتر در سیستمهای بی درنگ و محاوره ای که باید به رخدادهای ناهمگام پاسخ دهند.
مشکلات برنامه نویسی چند نخی
سربار محاسباتی حاصل از همگام سازی و زمانبندی
در برنامه ها با امکان توازی سازی کم ممکن است قابل تحمل نباشد.
نیاز به دقت و نظم برنامه نویسی بیشتر برای طراحی و هماهنگی ترتیبهای اجرای مختلف.
اشکال زدایی مشکلتر.
POSIX
"Portable Operating System Interface [for Unix]"
POSIX standard for thread programming interface(1995)
Implementations of POSIX standard are referred to as POSIX threads or Pthreads.
Latest Edition IEEE std 1003.1,2004
Available for Linux and Unix OS family
Availabe for Windows
As Open Source http://sourceware.org/pthread-win32
پیاده سازی نخ
پیاده سازی نخ در POSIX در سه لایه انتزاعی
لایه های انتزاعی
Pthread توصیف POSIX برای رفتار نخها است که برنامه نویس سیستم مستقیما از آن استفاده می کند.
نخ سطح کرنل عنصری است که توسط کرنل، بعنوان متن اجرای یک نخ در فرآیند، بطور واقعی ایجاد، زمانبندی و مدیریت می شود. چگونگی مدیریت نخ وابسته به سیستم عامل است.
کتابخانه یک روال پوششی است که فراخوان کرنل سیستم را پیاده سازی می کند. بعضاً امکاناتی برای ایجاد، زمانبندی و مدیریت نخها مستقل از هسته فراهم می شود که عنصر ایجاد شده توسط کتابخانه، نخ سطح کاربر نامیده می شود.
سه مدل پیاده سازی نخها
چند به یک
یک به یک
چند به چند
چند به یک
Pthread بعنوان نخ سطح کاربر پیاده سازی می شود.
کتابخانه زمان اجرا نیز در حالت کاربر قرار دارد و نخ را زمانبندی می کند
برای سیستم عامل قابل مشاهده نیستند.
هر فرایند به یک نخ سطح کرنل نگاشت می شود.
مشخصات
قابلیت حمل بیشتر بدلیل عدم نیاز به پشتیبانی کرنل
تعویض متن سریعتر بین نخها
عدم استفاده از مزیت معماری چند پردازنده ای
Mach C-threads, BSD, Solaris UI-threads,DCE-threads
چند به یک
یک به یک
Pthreads بعنوان نخ سطح هسته در داخل هسته پیاده سازی می شود.
کتابخانه برای هر نخ سطح کاربر یک نخ سطح کرنل تقاضا می کند
کتابخانه نخ ممکن است هنوز بطور گسترده با همگام سازی نخها درگیر باشد اما کرنل ایجاد و زمانبندی نخ را انجام می دهد
تعداد نخها برای هر فرآیند باید معلوم باشد.
مشخصات
معمولا در تعویض متن نخها کُند می باشد چون نیاز به مداخله کرنل دارد. این بدین معنی است که برنامه ها که مکرراً نیاز دارند تا برای همگام سازی بلاک شوند کندتر از دیگر مدلها اجرا خواهند شد
در یک فرایند از امکانات معماری چند پردازنده ای بطور کامل استفاده می گردد
Windows,Linux
یک به یک
چند به چند
سعی به ادغام مزیت مدلهای یک به یک و چند به یک دارد.
نیاز گسترده به هماهنگی بین کتابخانه نخ سطح کاربر و سطح کرنل دارد. آنها در مسئولیت زمانبندی شریک هستند
هر فرایند دارای مخزنی از نخهای سطح کاربر است.
نخهای سطح کاربر توسط کتابخانه سطح کاربر مدیریت شده و آماده اجرا می گردند.
کرنل یکی از نخهای سطح کاربر را انتخاب کرده و به یکی از نخهای سطح کرنل متعلق به مجموعه نخهای فرآیند نگاشت می کند.
مشخصات
بیش از یک نخ سطح کاربر می تواند به یک نخ سطح کرنل نگاشت شود.
در یک فرایند از امکانات معماری چند پردازنده ای بطور کامل استفاده می گردد
بیشتر تعویض متن در حالت کاربر است، تعویض نخ های کاربر بدون تعویض نخهای سطح کرنل صورت می گیرد
پیچیدگی زیاد برای هماهنگ کردن کتابخانه سطح کاربر و هسته
Solaris, HP, AIX
چند به چند
انواع مدل های نخ کشی
Boss-worker
Peer-to-peer
pipeline
انواع مدل های نخ کشی
Boss-worker
یک نخ(boss) سایر نخها(worker) را ایجاد نموده و به هر کدام وظیفه ای را تخصیص می دهد.
نخ worker وظیفه را اجرا نموده و در صورت نیاز با سایر نخها همگام می شود.
نخ boss در یک حلقه مداوما رخدادها را دریافت کرده و نخهایی برای اجرای وظایف ایجاد می نماید.
نخ boss می تواند منتظر اجرا و خاتمه یک نخ بماند.
انواع مدل های نخ کشی
Peer-to-peer
همه نخهای وضعیت کاری یکسان دارند
یک نخ وظیفه ایجاد سایر نخها را دارد ولی خودش هم worker محسوب می شود.
Pipeline
مانند خط مونتاژ:پردازش دنباله ای از اقلام در مراحل مختلف.
برای هر مرحله یک نخ ورودی را دریافت کرده و آنرا پردازش می نماید. سپس نخ دیگر برای مرحله بعد پردازش دیگری را روی ورودی انجام می دهد.
مدل نخ کشی Pthread
نخ ها در یک فرآیند وجود دارند.
همه نخ ها ”همتا“(peer) هستند:
مدل پدر-فرزند صریح نمی باشد
استثنا : “main thread” اطلاعات فرآیند را نگه داری می کند
Pthread API
مدیریت نخ ها: creating, detaching, joining,etc
Mutex: مربوط به همگام سازی می باشد.
متغیرهای شرطی: ارتباط بین نخهایی که از mutex اشتراکی استفاده می کنند
main thread
نخ اولیه زمانی ایجاد می شود که تابع main() در C بوسیله بارکننده فرآیند احضار گردد.
اگر main thread خاتمه یابد، فرایند خاتمه می یابد حتی اگر نخ هایی در حال اجرا وجود داشته باشد، مگر اقدامات احتیاطی در نظر گرفته شده باشد.
برای اجتناب از خاتمه کامل نخ، از pthread_exit() استفاده می گردد.
ایجاد نخ
pthread_create(
pthread_t *tid,
const pthread_attr_t *attr,
void *(*func)(void *),
void *arg);
tid – pointer to the identifier of the created thread
attr – thread attributes
func – pointer to the function the thread will execute
arg – the argument of the executed function (usually a struct)
ایجاد نخ
pthread_create( tid, attr, func, arg);
زمانیکه تابع func() خاتمه یابد(return) نخ هم به پایان می رسد.
مقدار بازگشتی pthread_create اگر صفر باشد یعنی اجرا موفق بوده و در صورتیکه ناموفق باشد عدد مثبتی به عنوان شماره خطا بازگشت داده می شود.
متغیر errno مقدار دهی نمی گردد.
شناسه(ID) نخ در tid بازگشت داده می شود.
ایجاد نخ
pthread_create( tid, attr, func, arg);
خصیصه نخ که با attr می توان مقداردهی کرد:
detached state
scheduling policy
در صورتیکه attr برابر NULL قرار دهیم، خصیصه پیش فرض سیستم را به نخ خواهد داد.
پایان نخ
خاتمه روال اصلی برای ایجاد نخها
فراخوانی زیر روال pthread_exit در نخ
خاتمه یک نخ توسط نخ دیگر با روال pthread_cancel
خاتمه فرآیند توسط روالهایی مانند exit
#include <pthread.h>
#include <stdio.h>
#define NUM_THREADS 5
void *PrintHello(void *threadid)
{
long tid;
tid = (long)threadid;
printf("Hello World! It's me, thread #%ld!n", tid);
pthread_exit(NULL);
}
int main (int argc, char *argv[])
{
pthread_t threads[NUM_THREADS];
int rc;
long t;
for(t=0; t<NUM_THREADS; t++){
printf("In main: creating thread %ldn", t);
rc = pthread_create(&threads[t], NULL, PrintHello, (void *)t);
if (rc){
printf("ERROR; return code from pthread_create() is %dn", rc);
exit(-1);
}
}
pthread_exit(NULL);
}
ارسال پارامتر به نخ
امکان ارسال فقط یک پارامتر به نخ فراهم شده است
برای ارسال بیش از یک مقدار از struct استفاده می شود
همه پارامترها باید تبدیل نوع به (void *) گردند
مثال – ارسال پارامتر به نخ
long *taskids[NUM_THREADS];
for(t=0; t<NUM_THREADS; t++)
{
taskids[t] = (long *) malloc(sizeof(long));
*taskids[t] = t;
printf("Creating thread %ldn", t);
rc = pthread_create(&threads[t], NULL, PrintHello, (void *) taskids[t]);
…
}
int rc;
long t;
for(t=0; t<NUM_THREADS; t++)
{
printf("Creating thread %ldn", t);
rc = pthread_create(&threads[t], NULL, PrintHello, (void *) &t);
…
}
الحاق(joining)
الحاق یکی از راههای همگام کردن (synchronization) دو نخ می باشد
روال pthread_join() روال فراخواننده خود را مسدود می نماید تا زمانیکه نخ مشخص شده(thraedid) خاتمه یابد
الحاق(joining)
اطلاع از وضعیت نخ خاتمه یافته(status)
باید نخ با pthread_exit() خاتمه یافته باشد.
امکان الحاق چند نخ به یک نخ بطور همزمان وجود ندارد.
دو روش همگام سازی دیگر:
Mutex , Condition Variable
قابلیت الحاق
زمانیکه یک نخ ایجاد می شود، با مقداردهی یکی از خصایصش می توان قابلیت الحاق نخ را تعریف کرد:
Joinable or detached
قابل الحاق
بطور پیش فرض نخها قابل الحاق شدن هستند
منابع تا زمانیکه الحاق رخ دهد حفظ می شود
منفصل
نمی توانند به نخی ملحق شوند
منابع در زمان خاتمه نخ آزاد می شوند
عملکرد
تعریف یک متغیر از نوع داده pthread_attr_t
مقداردهی اولیه و پیش فرض متغیر خصیصه با روال pathread_attr_init()
مقدار دهی خصیصه با pathrad_attr_setdetachstate()
آزادسازی منابع استفاده شده توسط خصیصه: pthread_attr_destroy()
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define NUM_THREADS 4
void *BusyWork(void *t)
{
int i;
long tid;
double result=0.0;
tid = (long)t;
printf("Thread %ld starting…n",tid);
for (i=0; i<1000000; i++)
{
result = result + sin(i) * tan(i);
}
printf("Thread %ld done. Result = %en",tid, result);
pthread_exit((void*) t);
}
int main (int argc, char *argv[])
{
pthread_t thread[NUM_THREADS];
pthread_attr_t attr;
int rc;
long t;
void *status;
/* Initialize and set thread attribute */
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
for(t=0; t<NUM_THREADS; t++) {
printf("Main: creating thread %ldn", t);
rc = pthread_create(&thread[t], &attr, BusyWork, (void *)t);
if (rc) {
printf("ERROR; return code from pthread_create() is %dn", rc);
exit(-1);
}
}
/* Free attribute and wait for the other threads */
pthread_attr_destroy(&attr);
for(t=0; t<NUM_THREADS; t++) {
rc = pthread_join(thread[t], &status);
if (rc) {
printf("ERROR; return code from pthread_join() is %dn", rc);
exit(-1);
}
printf("Main: completed join with thread %ld having a status
of %ldn",t,(long)status);
}
printf("Main: program completed. Exiting.n");
pthread_exit(NULL);
}
ارتباط بین نخها
متغیرهای سراسری
پارامترهای ارسالی به نخ بهنگام ایجاد نخ
فایلها
مشکل : دسترسی همزمان به منابع
ارتباط بین نخها
روشهای همگام سازی
همگام سازی
ارتباط بین نخها از طریق به اشتراک گذاشتن منابع سخت افزاری و نرم افزاری ممکن است که برای دسترسی به آنها نیاز به همگام سازی وجود دارد.
مکانیزم های همگام سازی
سمافور و mutex
قفلهای خواندن-نوشتن
متغیرهای شرطی
Mutex
منبع اشتراکی: داده
با استفاده از متغیرهای سراسری یا فایلها
مشکل: شرایط رقابتی در دسترسی به ناحیه حافظه
ناحیه بحرانی: قطعه ای از کد که روی ناحیه مشترک تغییرات ایجاد می نماید
راه حل: انحصار متقابل در ناحیه بحرانی
mutex : سمافور دودویی برای جلوگیری از شرایط رقابتی در ناحیه بحرانی
Mutex
توالی عملیات نمونه برای استفاده از mutex
ایجاد و مقدار دهی اولیه mutex
تلاش چند نخ برای قفل کردن mutex
موفق شدن فقط یک نخ و در اختیار گرفتن mutex
اجرای تعدادی دستور توسط نخی که mutex را در اختیار دارد
باز کردن قفل توسط نخی که mutex را در اختیار دارد
سایر نخها mutex را در اختیار گرفته و تکرار مراحل فوق
آزادسازی mutex
Mutex
تعریف و مقداردهی اولیه mutex
تعریف متغیر از نوع pthread_mutex_t
مقداردهی اولیه
ایستا در زمان تعریف
pthread_mutex_t mutex =PTHREAD_MUTEX_INITIALIZER;
پویا, با استفاده از روال pthread_mutex_init()
با استفاده از شیء خصیصه می توان خصوصیات شیء mutex را نیز تعریف نمود.
Mutex
آزاد سازی اشیا
آزاد سازی شیء mutex با استفاده از روال
pthread_mutex_destroy()
آزاد سازی شیء خصیصه mutex
pthread_mutexattr_destroy()
Mutex
قفل گذاریmutex
قفل با روال : pthread_mutex_lock()
در صورتیکه mutex قبلاً توسط نخی قفل شده باشد، نخ فراخواننده روال بلاک می شود تا زمانیکه قفل mutex آزاد گردد.
قفل با روال : pthread_mutex_trylock()
در صورتیکه mutex قبلاً توسط نخی قفل شده باشد، روال خاتمه سافته و خطایی مبنی بر busy بر می گرداند(مناسب برای جلوگیری از deadlock).
بازکردن قفل mutex
فراخوانی روال pthread_mutex_unlock() توسط نخ قفل کننده mutex
typedef struct{
double *a;
double *b;
double sum;
int veclen;
}DOTDATA;
#define NUMTHRDS 4
#define VECLEN 100
DOTDATA dotstr;
pthread_t callThd[NUMTHRDS];
pthread_mutex_t mutexsum;
void *dotprod(void *arg)
{
int i, start, end, len ;
long offset;
double mysum, *x, *y;
offset = (long)arg;
len = dotstr.veclen;
start = offset*len;
end = start + len;
x = dotstr.a;
y = dotstr.b;
mysum = 0;
for (i=start; i<end ; i++) {
mysum += (x[i] * y[i]);
}
pthread_mutex_lock (&mutexsum);
dotstr.sum += mysum;
pthread_mutex_unlock (&mutexsum);
pthread_exit((void*) 0);
}
int main (int argc, char *argv[])
{
long i;
double *a, *b;
void *status;
pthread_attr_t attr;
a = (double*) malloc (NUMTHRDS*VECLEN*sizeof(double));
b = (double*) malloc (NUMTHRDS*VECLEN*sizeof(double));
for (i=0; i<VECLEN*NUMTHRDS; i++){
a[i]=1.0;
b[i]=a[i];
}
dotstr.veclen = VECLEN;
dotstr.a = a;
dotstr.b = b;
dotstr.sum =0;
pthread_mutex_init(&mutexsum, NULL);
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
for(i=0; i<NUMTHRDS; i++){
pthread_create(&callThd[i], &attr, dotprod, (void *)i);
}
pthread_attr_destroy(&attr);
for(i=0; i<NUMTHRDS; i++)
pthread_join(callThd[i], &status);
printf ("Sum = %f n", dotstr.sum);
free (a);
free (b);
pthread_mutex_destroy(&mutexsum);
pthread_exit(NULL);
}
قفلهای خواندن- نوشتن
ورود چند نخ به ناحیه بحرانی
در صورتیکه فقط عمل خواندن توسط نخها صورت پذیرد
در صورتیکه یک نخ عمل نوشتن را انجام دهد سایر نخها نمی توانند وارد ناحیه بحرانی گردند.
متغیرهای شرطی
امکان همگام سازی بر اساس مقادیر داده
mutex بر اساس دسترسی به داده همگام سازی می نمود
Polling
متغیرهای شرطی همیشه با یک mutex بکار می روند
متغیرهای شرطی
مراحل کار
تعریف و مقداردهی اولیه متغیرهای سراسری: در نخ اصلی
تعریف و مقدار دهی شیء متغیرهای شرطی: در نخ اصلی
تعریف و مقداردهی متغیر mutex :در نخ اصلی
ایجاد دو نخ A و B
نخ B
قفل کردن mutex
تغییر متغیر سراسری که نخ A منتظر آن می باشد
چک کردن مقدار متغیر سراسری انتظار نخ A و بمحض حصول شرایط ایجاد سیگنال به نخ A
باز کردن mutex
ادامه
نخ A
انجام کار تا حصول شرایط(رسیدن مقدار یک متغیر به مقدار مشخصی)
قفل کردن mutex و چک کردن متغیر سراسری
فراخوانی pthread_cond_wait برای بلاک شدن و انتظار یک سیگنال از نخ B (بطور خودکار و اتمیک mutex باز شده ودر اختیار نخ B قرار می گیرد(
وقتی سیگنال دریافت شد، mutex بطور خودکار و اتمیک قفل می شود.
باز کردن mutex بصورت صریح
ادامه
فضای آدرسی نخ
هر داده ای که آدرسش توسط یک نخ تعیین می گردد، در فرآیند برای همه نخها قابل دسترسی هست.
شامل متغیرهای ایستا، متغیرهای خودکار و حافظه های تخصیصی با malloc
این بدین معنا نیست که هر نخ نمی تواند داده اختصاصی داشته باشد.