ساختمان داده هم‌زمان

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم رایانه، یک ساختار داده هم‌زمان شیوهٔ خاصی از ذخیره‌سازی و سازمان دهی داده‌ها برای دسترسی موضوعات چندگانهٔ محاسبات بر روی یک کامپیوتر می‌باشد.

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

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

ساختار داده هم‌زمان (گاهی اوقات نیز ساختمان داده مشترک نامیده می‌شود) اکثراً در نظر گرفته شده است که در یک محیط ذخیره‌سازی انتزاعی به نام حافظه داخلی اقامت داشته باشد، هرچند این حافظه ممکن است از لحاظ فیزیکی به صورت "همراه محکم"و یا یک مجموعهٔ توزیع واحدهای ذخیره‌سازی اجرا شده باشد.

اصول اساسی[ویرایش]

ساختمان داده هم‌زمان برای استفاده در محیط‌های محاسبات متوازی و یا توزیع در نظر گرفته شده است، اختلاف داشتن از ساختمان داده "ترتیبی" در نظر گرفته شده است برای استفاده در یک ماشین تک پردازنده، در راه‌های مختلف.

برجسته ترین این آثار در محیط ترتیبی،یکی از خواص ساختمان داده را مشخص می‌کند و بررسی می‌کند که آنها را به درستی با ارائه خواص ایمنی تکمیل کند.

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

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

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

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

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

طراحی و پیاده‌سازی[ویرایش]

ساختمان داده‌های هم‌زمان به میزان قابل توجهی برای طراحی و بررسی به عنوان صحیح بودن،سخت تر از همتایان ترتیبی آنهاست.

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

در ماشین‌های امروزی، آرایش پردازنده‌ها در حافظه، آرایش داده‌ها در حافظه، بار ارتباطات در عناصر مختلف از معماری چند پردازنده همگی بر روی اجرا تاثیر می‌گذارند. علاوه بر این کششی وجود دارد بین صحت و عملکرد: پیشرفت‌های الگوریتمی که برای پیشرفت عملکرد جستجو می‌کنند;که اکثراً آن را برای طراحی و بررسی صحیح بودن پیاده‌سازی ساختار داده سخت تر می‌کند.

اندازه کلیدی برای عملکرد، مقیاس پذیری است، توسط تسریع در پیاده‌سازی گرفته شده است.

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

در حالت ایده‌آل ما یک تسریع خطی می‌خواهیم:ما دوست داریم که برسیم به تسریع شدهٔ پ وقتی از یک پ-پردازنده استفاده می‌کنیم. ساختمان داده‌هایی که رشد را برای پ تسریع می‌کنند، مقیاس پذیر نامیده می‌شوند. اندازه‌ای را که می‌توان مقیاس کرد اجرای ساختمان داده هم‌زمان را توسط یک فرمول گرفته شده که قانون آمداهل شناخته شده و نسخه‌های تصفیه شده بیشتری مانند قانون گوستاف سون است.

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

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

جستارهای وابسته[ویرایش]

منابع[ویرایش]

^ Jump up to: a b Mark Moir and Nir Shavit (2007). "Concurrent Data Structures". In Dinesh Metha and Sartaj Sahni. 'Handbook of Data Structures and Applications' (1st ed.). Chapman and Hall/CRC Press. pp. 47–14–47–30

مطالعه بیشتر[ویرایش]

  • Nancy Lynch "Distributed Computing "
  • Hagit Attiya and Jennifer Welch "Distributed Computing: Fundamentals, Simulations And Advanced Topics, 2nd Ed"
  • Doug Lea, "Concurrent Programming in Java: Design Principles and Patterns"
  • Maurice Herlihy and Nir Shavit, "The Art of Multiprocessor Programming"
  • Mattson, Sanders, and Massingil "Patterns for Parallel Programming"

پیوند به بیرون[ویرایش]