مقاله ماشينهاي همزماني

 مقاله ماشينهاي همزماني

… دانلود …

مقاله ماشينهاي همزماني دارای 12 صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله ماشينهاي همزماني کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ريختگي احتمالي در متون زير ،دليل ان کپي کردن اين مطالب از داخل فایل ورد مي باشد و در فايل اصلي مقاله ماشينهاي همزماني،به هيچ وجه بهم ريختگي وجود ندارد


بخشی از متن مقاله ماشينهاي همزماني :

ماشینهای همزمانی
– همزمانی

ماشینهای همزمانی با روالهای نرم افزاری در سطح كاربر ساخته شده اند كه آن استنادی است كه دستورات همزمانی موجود در سخت افزار.
برای چند پردازنده های كوچكتر یا وضعیت رقابتی پایینتر،قابلیت كلید سخت افزاری در یك دستور بی‌وفقه یا ترتیب و توالی دستور در بازیابی ذره وار(اتمیك) و تغییر یك مقدار است و مكانیزم همزمانی نرم افزاری این توانایی را می سازد در این بخش ما روی پیاده سازی عملیات همزمانی،باز كردن و قفل كردن تمركز می كنیم.
Locl وunlock می توانند بطور مستقیم در یك ممانعت متقابل بكار روند،همچنین در بكار بردن مكانیزمهای همزمانی پیچیده تر.

در یك مقیاس بزرگتر در چند پردازنده ها یا در وضعیت رقابتی بالاتر،همزمانی كارائی بیشتری را دارد چون رقابتهای بیشتر تأخیرهای اضافی را بوجود می آورد ما در اینجا بحث می كنیم كه چگونه مكانیزمهای همزمانی اولیه روی تعداد،بیشتری از پردازنده گسترش می یابد.

اسانس سخت افزار اولیه
در قابلیت كلید ما مستلزمیم همزمانی را در یك چند پردازنده كه مجموعه ای از سخت افزارهای اولیه با قابلیت خواندن ذره وار و یك مكان یابی حافظه است را اجرا كنیم بدون چنین قابلیتی هزینه ساخت همزمانی اولیه خیلی بیشتر خواهد بود و تعداد پردازنده ها افزایش خواهد یافت تعدادی قاعده دستورسازی برای سخت افزار اولیه وجود دارد كه در جهت بهبود قابلیت خواندن ذره وار و مكان یابی مناسب استفاده می شود و با چند راه می توان خواندن و نوشتن ذره وار را بیان كرد. این سخت افزار اولیه اساس ساخت بلوكهایی است كه در انواعی از عملیات همزمانی سطح كاربر استفاده می شود و همچنین شامل قفلها و مانع هاست.

بطور كلی در این معماری نمی توان انتظار داشت كه كاربران روی سخت افزار اولیه كار كنند اما در عوض انتظار می رود كه از سیستمهای برنامه نویسی برای ساخت یك كتابخانه همزمانی استفاده شود كه معمولاً یك پردازش پیچیده است.
حال بحث را با یك سخت افزار اولیه و چگونگی عملیات همزمانی برای آن شروع می كنیم یكی از انواع عملیات همزمانی مبادله اتمی (atomic exchanye) است كه ارزش یك رجیستر را با حافظه عوض می كند حال ببینیم چگونه از این عملیات همزمانی استفاده كنیم. فرض می كنیم كه می خواهیم یك قفل ساده بسازیم و در آن با ارزش 0صفر نشان می دهیم كه

قفل آزاد است و با 1 نشان می دهیم كه غیر قابل استفاده است در رجیستر و حافظه آدرس مطابق قفل است دستور emchanye 1 را برمی گرداند اگر پردازنده قبلاً دستیابی شده و در غیر اینصورت 5 را برمی گرداند. در حالت دیگر آن مقدار با 1 تغییر می كند و با حصول0 صفر از هر تغییری جلوگیری می كند. بطور مثال فرض می كنیم دو پردازنده داریم كه هر یك تلاش می كند همزمانی را عوض كند این رقابت وقتی تمام می شود . كه یكی از پردازنده ها تغییر را انجام می دهد و 0 را برگرداند و در اینصورت پردازنده دوم 1 را باز خواهد گرداند آن كلید از مبادله اولیه برای اجدا كردن همزمانی در عملیات اتمیك استفاده می كند. آن مبادله غیرقابل تقسیم است و دو مبادله همزمان با نوشتن مكانیزمهای پشت سرهم (سریالی ) مرتب می شود.

تعداد دیگر از اتمیك های اولیه وجود دارد كه در انجام همزمانی بكار برده می شود و همه آنها قابلیت خواندن و update كردن حافظه دارند و همچنین وضعیتی كه می گوید آیا دو عملیات به صورت ذره وا انجام می شود یا نه.
در حال حاضر یكی از عملیاتی كه در چند پردارنده های قدیمی استفاده می شود تست كردن و نشاندن است (test-and-set) كه یك مقداررا تست می كند و اگر آن مقدار توسط آن تست تصویب شد آن را قرار می دهد. برای مثال ما می توانیم عملیاتی را تعریف كنیم كه برای 0 تست شده و در آن ارزش 1 قرار گرفته.نوع دیگر از همزمانی اتمیك او fetch a increment است كه ارزش محل حافظه و افزایش ذره ای را برمیگرداند وجود 0 نشان می دهد كه متغیر همزمانی مطالبه نشده و ما می توانیم از fe tch a increment فقط در مبادله استفاده كنیم كاربردهای دیگری از عملیات وجود دارد مشابه fetch a increment كه مختصراً به آنها خواهیم پرداخت. دستورات بی وقفه در اجرای عملیات حافظه اتمیك،زمانیكه به هر دو حافظه خواندنی و نوشتنی نیاز است یكسری رقابتها را مطرح می كند. پیچیدگی كه در كاربرد آن است مربوط به زمانیست كه سخت افزار هیچ عملیات دیگری را در بین خواندن و نوشتن نمی تواند انجام دهد و منجر به بن بست می شود.
یك تبدیلی در یك جفت دستور است زمانیكه دومین دستور ارزشی را برمی گرداند و می توان نتیجه گرفت كه اگر اتمیك بود آیا آن جفت دستور اجرا می شد و زمانی آن جفت دستور مؤثر هستند كه هیچ پردازنده دیگری ارزش را در بین آن جفت دستور تغییر ندهد.
این جفت دستور یك load ویژه است كه lood locked , load linked را شامل می شود و دستور دیگر یك store ویژه است كه store conditianad نامیده می شود این دستورات بترتیب استفاده می شوند:اگر محتویات مكان حافظه با load liaked مشخص شود آن قبل از دستور store condionad كه با آدرس یكسان رخ داده تغییر پیدا می كند. پس دستور store شرطی از بین می رود و اگر پردازنده یك سوئیچ میان آن دو دستور انجام دهد باز هم store شرطی از بین می رود.

دستور store شرطی اگر انجام شود 2 را باز می گرداند در غیر اینصورت 0 را برمی گرداند و تنها زمانی عملیات موفقیت آمیز است كه load linked مقدار اولیه نرا برگرداند و store شرطی هم مقدار 1 را بازگرداند. رشته زیر یك مبادله اتمیك را روی مكان حافظه مشخص شده بوسیله R1 انجام می دهد:

try:Mov R3,R4 :Mov of value exchange
LL R2,0(R1) :loud linked
Sc R3,0(R1) :store condi tionad
BEQZ R3,try :branch store fails
Mov R4,R2 :put lood value in R4

در پایان این رشته،محتویات R4 و مكان حافظه با R1 مشخص می شود(با نادیده گرفتن هر اثری از branch های به تأخیر افتاده).
در هر زمان یك پردازنده مداخله می كند و مقدار حافظه را میان دستورات LL و SC تغییر می دهد sc مقدار 0 را در R3 می گذارد و باعث ترتیب كه برای try می شود. یك مزیت مكانیزمهای LL/SC این است كه می توانند برای ساخت همزمانیهای اولیه دیگر استفاده شوند. به عنوان مثال در زیر به یك fetch
8increment اتمیك اشاره می شود:

try: LL R2.0(R1) :load linked
DADUI R3,R2,#1 :i increment
SC R3,0(R1) :store conditionad
BEQZ R3,try :branch store fails

این دستورات بوسیله نگهداری خط آدرس مشخص شده اجرا می شوند برای دستور LL اگر یك وقفه رخ دهد یا اگر بلوك كش تطابق پیدا كند آدرس در link registet از بین می رود (مثلاً به وسیله یك SC دیگر) دستور SC براحتی آدرس خود در لینك رجیستر را بررسی می كند اگر بود در اینصورت SC موفقیت آمیز بوده در غیر اینصورت از بین رفته.
زمانیكه SC از بین می رود بعد از دستور store ناتمام به آدرس LL باید در انتخاب دستورات جایگزین شده بین این دو دستور دقت كنیم كه دستورات رجیستر در آن مجاز به استفاده بوده و بدون خطرند،غیر از این ممكن است بن بست بوجود آید(زمانیكه آن پردازنده نمی تواند دستور scsc را كامل كند) همچنین تعداد دستورات میان S C.LL باید كم باشد چون امتحان رخداد غیرمنتظره یا تكرار خرابی SC وجود دارد.

 

اجرای قفلهای به هم پیوسته
قبلاً ما عملیات اتمیك داشتیم و می توانستیم از مكانیزمهای به هم پیوستگی در یك چند پردازنده استفاده كنیم در اجرای قفلهای چرخشی (spin lock) در یك حلقه آنقدر می چرخد تا اینكه به نتیجه برسد.spin lock زمانی استفاده می شود كه برنامه نویس ها می خواهند قفل را برای مدت كوتاهی نگهداری كنند و در مرحله ای با تأخیر اندك از آن استفاده كنند پس باید در دسترس باشد چون spin lock پردازنده را حبس می كند و در یك l oop منظر می ماند تا قفل آزاد شود البته در بعضی مواقع نامناسب هم هستند.

ساده ترین كاربرد آن مربوط به زمانی است كه كش به هم پیوسته نباشد و قفلهای متغیر را در حافظه نگهداری می كند. یك پردازنده دائماً تلاش می كند تا قفل را در یك عملیات اتمیك پیدا كند و تست كند كه آیا آن مبادله قفل را آزاد می كند یا نه برای آزاد سازی قفل، پردازنده مقدار 0 را ذخیره می كند در اینجا یك رشته كه برای قفل چرخشی داریم كه آدرسش در R1 در یك مبادله اتمیك استفاده می شود:

DADDUI R2,R0.#1
lockit: EXCH R2,0(R1) ,atomic exchange
BNEZ R2,lockit ,already locket

اگر پردازنده ما كش بهم پیوسته را پشتیبانی كند ما می توانیم كش قفلهای مورد استفاده آن مكانیزم بهم پیوسته برای مقدار قفل مربوطه نگهداری كنیم. كش بودن قفلها دو مزیت دارد:اول اینكه اجازه می‌دهد كه مرحله spining (تلاش برای تست و بدست آوردن قفل در حلقه) كه در كش كپی می شود سریعتر باشد از دستیابی حافظه كلی روی هر یك از دریافتهای قفل كه در هر جستجو نیاز است. دومین مزیت آن مربوط به لوكالیتی دستیابی قفل است یعنی اینكه پردازنده ای كه قفل را استفاده كرده درآیند نزدیك دوباره آن را استفاده می كند. در این مورد ممكن است مقدار قفل دركش پردازنده باشد و در نتیجه زمان پیدا كردن قفل كاهش زیادی پیدا كند.

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

بدین ترتیب ما باید پروسه قفل چرخشی را اصلاح كنیم بطوریكه با انجام عمل خواندن روی كپی موضعی قفل بچرخد تا اینكه آن قفل دستیابی شود جستجو برای بدست آوردن قفل با انجام یك عملیات جانشینی انجام می شود یك پردازنده ابتدا متغیر قفل را تست وضعیت می كند و آن پردازنده می خواند و تست می كند تا اینكه با توجه به مقدار بدست آمده مشخص شود كه قفل باز شده.

آن پردازنده سپس بر خلاف همه پروسه های مشابه (در نوشتن چرخشی) عمل می كند تا ببیند كه چه كسی متغیر را ابتدا قفل می كند همه فرایندها از یك دستور مبادله ای استفاده می كنند كه مقدار قدیمی را می خواند و 1 را درون متغیر قفل ذخیره می كند تنها برنده مقدار 0 را می بیند و بقیه 1 را. پردازنده برنده كد را بعد از قفل اجرا می كند و وقتی كه تمام شد مقدار 0 را درون متغیر قفل برای آزاد كردن قفل ذخیره می كند. در اینجا كدهایی كه spin lock را اجرا می كند می بینیم( 0 برای باز شدن و 1 را برای قفل كردن)

lockit : LD R2,0(R2) , load of lock
BNEZ R2,lockit , not available-spin
DADDUI R2,R0,#1 , load locked valure
EXCH R2,0(R1) , swap
BNEZ R2,lockit , nranch if lock washt 0

حال بررسی می كنیم كه برنامه spin lock چگونه از مكانیزم به هم پیوسته كش استفاده می كند شكل 423 نشان می دهد پردازنده و گذرگاه یا عملیات فهرستی برای فرایندهای چندگانه متغیری كه از مبادله اتمیك استفاده می كند را قفل می كنند یكی از پردازنده ها 0 را در قفل ذخیره می كند و بقیه كش ها نامناسب بوده و مقدار جدید را برای به هنگام سازی كردن كپی آن در قفل واكشی می كنند در این كش كپی باز شدن قفل را با ارزش 0 نشان می دهد و بعد مبادله را انجام می دهد.
این مثال مزیت دیگر LL/SC را نشان می دهد :

عمل خواندن و نوشتن به وضوح از یكدیگر جدا شده اند.LL موجب هر ترافیك گذرگاهی نیست این واقعیت نشان می دهد كه آن رشته كد ساده همان مشخصات بهینه شده نسخه استفاده از مبادله را دارد (R1 آدرس قفل را نگه می دارد،LL جایگزین LD می شود و SC جایگزین EXCH

.
Lockit : LL R2,0(R1) , load linked
BNEZ R2,lockit ,not available-spin
DADDUI R2,R0,#1 ,locked value
SC R2,0(R1) ,store
BEQZ R2,lockit ,branch if store fails

اولین شرط فرم حلقه چرخشی را مشخص می كند و دومین شرط رقابتی كه دو پردازنده سر دسترسی همزمان به قفل دارند را حل می كند.
هر چند برنامه قفل چرخشی ساده است اما پیچایش بالای آن در بكار بردن تعداد زیاد پردازنده ها مشكل است چون ترافیك تولید شده مربوط به زمانی است كه قفل آزاد شده است.

مدلهایی از حافظه های پایدار
وابستگی كش باعث می شود كه پردازنده های چندگانه به نمایش پایداری حافظه بنگرند حال سؤال این است كه پایداری چگونه است و چه موقع یك پردازنده باید مقدارش توسط پردازنده دیگر update از آنجایی كه پردازنده ها از طریق متغیرهای به اشتراك گذاشته ارتباط برقرار می كنند پس این سؤال را می توان اینگونه مطرح كرد: در چه دستوراتی باید به داده های نوشته شده توسط پردازنده های دیگر توجه كرد؟ در جایی كه تنها راه به واسطه خواندن است.
سؤال را می توان بدینصورت گفت:چه چیزی را باید بین خواندن و نوشتن در پردازنده های متفاوت اجرا كرد؟در میان این سوالات پایداری حافظه كه به نظر می رسید باید ساده باشد فوق العاده پیچیده می شود.

بعنوان مثال با یك مثال ساده می توان آن را بیان كرد در اینجا دو كد سگمنت از پردازنده P2 , P1 است كه پهلو به پهلوی یكدیگر نشان داده شده اند.
P1 : A=0 P2:B=0
……. …….
A=1 B=2
L2:if (B=0)….. L2:if (A=0)…..
با فرض اینكه پروسه هایی در پردازنده های مختلف در حال اجرا هستند و محل های , B , A از دو پردازنده ابتدا در كش مقدار 0 را دارند. دستورات (برچسب دارL2 ,L1) شرطها را ارزیابی می كنند و اگر درست بود در اینصورت B, , A مقدار 1 را كه به آن اختصاص داده ایم نشان می دهند. اما فرض كنید كه آن نوشتن های اضافی به تأخیر افتاده باشد و آن پردازنده ها در طی آن تأخیر به پردازش ادامه دهند. و ممكن است كه P 2 ,P1 مقداری برای B, A نداشته باشد(بترتیب) و قبل از اینكه شروع به خواندن مقدار ها كند سؤالی كه پیش می آید این است كه چه شرایطی لازم است تا این وضعیت ادامه داشته باشد؟آسانترین مدل برای پایداری حافظه پایداری ترتیبی sequential consistency نامیده می شود.
در پردازش ترتیبی باید نتیجه هر اجرایی مشابه باشد همچنین دستیابی های حافظه كه توسط هر پردازنده انجام می شود به طور صحیح نگهداری می شود و این دستیابی های پردازنده های مختلف به دلخواه جایگذاری می شوند. پایداری ترتیبی امكان اینكه تعدادی از اجراها نامعلوم باشد را در مثال قبل رفع كرد چون آن انتصابها باید قبل از ورود دستورات بعدی كامل شوند.

ساده ترین را در اجرای پایداری ترتیبی وجود پردازنده ای است كه با تأخیر دستیابی حافظه را به اتمام برساند تا اینكه همه آن موارد از بین رفته با دستیابی كامل شود. و آن تأخیر برابر با دستیابی حافظه بعدی است به یاد داریم كه پایداری حافظه عملیات را با متغیرهای مختلف درگیر می كرد:

آن دو دستیابی كه باید مرتب باشند در واقع مكانهای متفاوت حافظه هستند در این مثال ما باید تأخیر A یا B را با تأخیر انجام دهیم (B=0 یا A=0) تا اینكه نوشته قبلی كامل شود(A=1 یا B=1) در نهایت اینكه در پایداری ترتیبی ما عمل خواندن و نوشتن را با هم نمی توانیم انجام دهیم هر چند پایداری ترتیبی یك شكل ساده از برنامه نویسی را ارائه كرد اما كارائی را پایین آورد. حال به یك مثال دیگر می پردازیم.

مثال:تصور كنید كه ما پردازنده ای داریم كه write miss آن so سیكل برای برقراری مالكیت می گیرد،10 سیكل برای تولید هر ابطالی بعد از برقراری پایداری نیاز است 0 8 سیكل برای كامل شدن یك ابطال و تصدیق اینكه تولید شده است فرض می كنیم كه یك بلوك كش بین چهار پردازنده تقسیم شده است حال چقدر write miss باید توقف داشته باشد تا پردازنده نوشته شود؟(البته اگر پردازنده پایدار ترتیبی دارد.)و نیز فرض می كنیم كه قبل از اینكه كنترل كننده های وابسته كامل شود باید باطل سازی صریحاً تصدیق شود چنانچه ما بعد از بدست آوردن مالكیت برای write miss بتوانیم اجرا را دامه دهیم بدون اینكه برای باطل سازی صبر كنیم پس نوشتن چقدر طول می كشد؟

پاسخ: وقتی كه ما برای باطل كردن صبر می كنیم هر نوشتنی به اندازه زمان مالكیت وقت می گیرد و وقتی كه باطل سازی ها روی هم می افتند ما فقط در مورد آخرین آن نگران می شویم كه این با10+10+10+10=40 سیكل بعد از اینكه مالكیت برقرار شده آغاز می شود سپس زمان كل برای هر نوشتن 50+40+80=170 سیكل است در این مقایسه زمان مالكیت se سیكل است.

با سلام،محصول دانلودی مقاله ماشينهاي همزماني آماده ارائه به شما پژوهنده عزیز میباشد.با کلیک روی دکمه ادامه مطلب به صفحه توضیحات کامل مقاله ماشينهاي همزماني هدایت میشوید
مقاله ماشينهاي همزماني