کوبیدگی (علوم رایانه)

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

بعد از کامل شدن شروع برنامه، اکثر برنامه ها روی تعداد معدودی از کد ها و صفحات داده در مقایسه با حافظه کلی مورد نیاز برنامه کار می کنند. صفحاتی که بیشتر از همه مورد دسترسی قرار می‌گیرند میز کاری(working set) نام دارند.

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

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

اصطلاح زد و خورد همچنین در زمینه هایی غیر از سیستم های حافظه مجازی استفاده می شود. برای مثال برای توصیف مشکلات محاسباتی کش  یا سندروم پنجره احمق در شبکه.

مروری بر کلیات

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

دلایل

در سیستم حافظه مجازی زد و خورد ممکن است معلول برنامه‌ها یا میزان باری باشد که کمبود ارجاعات محلی به‌بار می‌آورد: اگر مجموعه کاری یک برنامه یا میزان کاری‌اش به‌طور کارآمد توسط حافظه اصلی دربر گرفته نشود و به دنبال آن انتقال اطلاعات داشته باشیم، زد و خورد ممکن است رخ دهد. اولین استفاده از صفحه‌بندی در دوران سیستم‌عامل‌های وابسته به نوار مغناطیسی برای توصیف صدای نوارها به کاربرده شد، وقتی که داده‌ها به سرعت از روی آن‌ها نوشته و خوانده می‌شدند. بسیاری از کامپیوترهای اولیه دارای حافظه ناکافی برای استفاده از الگوهای جدید بودند و افزایش مقدار حافظه اصلی اغلب افزایش قابل توجه سرعت عملکرد کامپیوتر را به همراه دارد. این افزایش سرعت منوط به کاهش مقدار مورد نیاز صفحه‌بندی است. یک مثال از این دسته از وضعیت‌ها در کامپیوترهای مین‌فریم سری ۳۷۰ شرکت آی‌بی‌ام اتفاق افتاد، یک ساختار به خصوص می‌توانست شامل یک دستورالعمل اجرایی باشد که به یک دستورالعمل جابه‌جایی اشاره می‌کرد با این هدف که یک جابه‌جایی اطلاعات از یک منبع که در محدوده یک صفحه بود، به یک مقصد که در آن هم در حوزهٔ یک صفحه بود انجام پذیرد؛ بنابراین تعداد کلی صفحات استفاده شده در این ساختار هشت صفحه بود و همه هشت صفحه باید در حافظه همزمان حاضر می‌بودند. اگر سیستم عامل کمتر از هشت صفحه در حافظه اصلی تخصیص می‌داد، در هنگامی‌که این فرایند اقدام به جابه‌جایی اطلاعات می‌کرد، با نقض صفحه مواجه می‌شد و پدیدهٔ زد و خورد در هر عملیات رخ می‌داد که در نهایت دستورالعمل به انجام نرسیده از سر گرفته می‌شد.

راه حل‌ها

جهت حل مشکل زد و خورد که باعث صفحه‌بندی بیش‌از حد می‌شود، یک کاربر می‌تواند یکی از راه‌حل‌های زیر را به کار گیرد:

• افزایش مقدار حافظه اصلی کامپیوتر
• کاهش تعداد برنامه‌های در حال اجرا در کامپیوتر
• جایگزینی برنامه‌هایی که به حافظه فراوان نیاز دارند با برنامه‌های معادل که حافظه کمتری مصرف می‌کنند.
• نسبت دادن اولویت کارکرد به برنامه‌ها مانند پایین، متوسط و بالا
• بهبود spatial locality به وسیلهٔ جایگزینی حلقه‌هایی مانند:

 // recall that in C, arrays use Row-major order
 int m[256][256]; 
 for (column=0; column<256; column++) { 
   for (row=0; row<256; row++) { 
     m[row][column] = foo(); 
   } 
 }

با:

  int m[256][256]; 
  for (row=0; row<256; row++) {
    for (column=0; column<256; column++) {
      // consecutive columns reside in adjacent memory locations 
      m[row][column] = foo(); 
    } 
  }

استفاده‌های دیگر

از این روش هم‌چنین برای حل فقدان‌های بین سطوح دیگر سلسله‌مراتب حافظه، نه فقط صفحه‌بندی، استفاده می‌شود. وقتی مجموعه کوچکتر از حافظه سریعتر برای سرعت بخشیدن به دسترسی به مجموعه بزرگتر با حافظه کندتر استفاده می‌شود. یک مثال از این مورد زد و خورد حافظه کش است، جایی که حافظه اصلی با الگویی مورد دستیابی است که منجر به رقابت نقاط مختلف حافظه اصلی برای برای دسترسی به خطوط حافظه کش می‌شود و در نتیجه آن تعداد گزافی خطای کش اتفاق می‌افتد. بزرگترین مسئله برای کش این است که خاصیت انجمنی پایینی داشته باشد. مورد مشابه دیگر زد و خورد حافظه TLB است، جایی که بافر TLB با درخواست‌هایی بیش از آن‌چه می‌تواند انجام دهد مواجه است.^[1]

منابع

1. https://en.wikipedia.org/wiki/Thrashing_(computer_science)