دانلود مقاله ماشینهای همزمانی

– همزمانی

ماشینهای همزمانی با روالهای نرم افزاری در سطح کاربر ساخته شده اند که آن استنادی است که دستورات همزمانی موجود در سخت افزار.

برای چند پردازنده های کوچکتر یا وضعیت رقابتی پایینتر،قابلیت کلید سخت افزاری در یک دستور بی‌وفقه یا ترتیب و توالی دستور در بازیابی ذره وار(اتمیک) و تغییر یک مقدار است و مکانیزم همزمانی نرم افزاری این توانایی را می سازد در این بخش ما روی پیاده سازی عملیات همزمانی،باز کردن و قفل کردن تمرکز می کنیم.

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 شرطی از بین می رود و اگر پردازنده یک سوئیچ میان آن دو دستور انجام دهد باز هم 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 چگونه از مکانیزم به هم پیوسته کش استفاده می کند شکل 4.23 نشان می دهد پردازنده و گذرگاه یا عملیات فهرستی برای فرایندهای چندگانه متغیری که از مبادله اتمیک استفاده می کند را قفل می کنند یکی از پردازنده ها 0 را در قفل ذخیره می کند و بقیه کش ها نامناسب بوده و مقدار جدید را برای به هنگام سازی کردن کپی آن در قفل واکشی می کنند در این کش کپی باز شدن قفل را با ارزش 0 نشان می دهد و بعد مبادله را انجام می دهد.

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