קיטוע

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

באחסון נתונים, קיטוע (פרגמנטציה) היא תופעה בה מקום אחסון נמצא בשימוש בצורה שאינה יעילה, כך שמקום האחסון בפועל קטן וברוב המקרים גם ביצועי המערכת.

קיימים שלושה סוגים שונים של קיטוע (הקשורים זה לזה): פנימי (internal), חיצוני (external) וקיטוע מידע (data fragmentation). שיטות שונות להקצאת מקום מפגינות אחד או יותר מסוגים אלו.

קיטוע זיכרון[עריכת קוד מקור | עריכה]

העקרון הבסיסי[עריכת קוד מקור | עריכה]

המונח "זיכרון מקוטע" (fragmented memory) מציין את כל זיכרון המערכת שאינו ניתן לשימוש. קיטוע של זיכרון מתרחש לרוב כאשר זיכרון מוקצה דינמית (על ידי קריאות כגון malloc). באופן כללי, הקצאת זיכרון בזמן ריצה לא נעשית על המחסנית. הקצאת הזיכרון הדינמית מבזבזת זיכרון בדרכים הבאות:

  • תקורה (overhead)
  • קיטוע פנימי
  • קיטוע חיצוני

כאשר זיכרון משוחרר בזמן ריצה, מירב הסיכויים שהמקום שיתפנה יהיה באמצע מקטע הזיכרון, ולכן, כאשר נרצה להקצות זיכרון חדש יווצרו 'חורים' בין מקטעי הזיכרון. חורים אלו עלולים להיות קטנים מדי מכדי לספק מספיק מקום להקצאה וכך אותו מקום מבוזבז.

סוגים של קיטוע זיכרון[עריכת קוד מקור | עריכה]

סוגים של קיטוע זיכרון

תקורה[עריכת קוד מקור | עריכה]

כאשר מערכת מקצה זיכרון עליה לשמור את כל הנתונים עליו כמו, לדוגמה, מיקומו, גודלו והרשאות הגישה אליו. תקורה כוללת את כל משאבי המערכת הנוספים הנדרשים כדי לממש את אלגוריתם הקצאת הזיכרון. נתונים אלו נשמרים, לרוב, בתוך הזיכרון עצמו, דבר המוביל לבזבוז זיכרון. בשל כך נחשבת התקורה לחלק מקיטוע הזיכרון.

קיטוע פנימי[עריכת קוד מקור | עריכה]

כאשר הזיכרון המוקצה גדול מהנצרך, שאר הזיכרון מבוזבז. סיבות, לדוגמה, לקיטוע פנימי:

  • כאשר המשתמש מבקש יותר מקום ממה שהוא צריך נוצרים חורים של מקום אחסון שאינם נגישים.
  • הגבלות של ארכיטקטורת הקצאת הזיכרון. לדוגמה: במערכות מסוימת התחלת קובץ היא דווקא בתחילת מקטע (cluster) על מנת להקל על ארגון הקבצים, ולכן, כאשר ישנם קבצים קטנים רבים עלולים להיווצר "חורים" של מקום שאינו מנוצל על הדיסק.

המונח "פנימי" מכוון לעובדה שהזיכרון המבוזבז נמצא בתוך האזור שהוקצה.

קיטוע חיצוני[עריכת קוד מקור | עריכה]

קיטוע חיצוני הוא חוסר היכולת להשתמש בזיכרון פנוי מכיוון שהוא מחולק למקטעים קטנים (fragments). המונח "חיצוני" מכוון לעבודה שהזיכרון המבוזבז נמצא מחוץ לאזור הזיכרון המוקצה. כאשר נמחק קובץ הנמצא בין מקטעי זיכרון אחרים או שגודלו משתנה נוצר אמנם מקטע זיכרון פנוי אך הוא קטן מכדי להיות שימושי. לדוגמה אם ניקח מערכת בעלת 15MB המסודרת כך: קובץ של 2MB, קובץ של 1MB ועוד קובץ של 2MB וכן הלאה לסרוגין, כאשר ימחקו הקבצים האמצעיים ונרצה להקצות 3MB לא נוכל לעשות זאת מכיוון שהמקטע הגדול ביותר הוא בן 1MB (אא"כ נחלק את ההקצאה לחלקים כפי שנראה בהמשך). בהשוואה לקיטוע חיצוני, התקורה והקיטוע הפנימי אחראים לכמות קטנה מאד של זיכרון מבוזבז. קיטוע חיצוני יוצר את רוב הנזק למערכת, הוא מוגדר כ:

 {External Memory Fragmentation = 1 - } \frac{Largest Block Of Free Memory}{Total Free Memory}

כלומר: אחד פחות גוש הזיכרון הגדול ביותר הפנוי חלקי כלל הזיכרון הפנוי.

קיטוע חיצוני הוא ערך בין 0 ל-1. קיטוע של 100% (כאשר ערך הנוסחא שווה ל-1) מצביע על כך שאין במערכת זיכרון שמיש פנוי, בעוד קיטוע של 0% (כאשר ערך הנוסחא הוא 0) מצביע על כך שכל הזיכרון נמצא בגוש אחד גדול.

לדוגמה, הקיטוע הוא 90% כאשר 100MB של זיכרון קיים במערכת, אבל הגוש הגדול ביותר של זיכרון פנוי הוא בגודל 10MB.

0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 הערות
A B C מוקצים שלושה גושים A, B, C בגודל 0x1000
A C הגוש B משוחרר. כעת לא ניתן להקצות במקום בו היה B זיכרון הגדול מגודלו של B.

קיטוע מידע[עריכת קוד מקור | עריכה]

קיטוע מידע מתרחש כאשר פיסת מידע מחולקת למספר חלקים על הדיסק, לדוגמה בדוגמה שהובאה לעיל – הקובץ אותו ניסינו לשמור יחולק לשלושה מקטעים של מגה אחד. דבר זה מאט את המערכת הצריכה לנוע בין מקטעי הקובץ על מנת לגשת אליו. לרוב, קיטוע מידע הוא תוצאה של מערכת שעברה קיטוע חיצוני.

הדרדרות ביצועים כתוצאה מקיטוע[עריכת קוד מקור | עריכה]

בעיית קיטוע הזיכרון היא אחת מהבעיות הקריטיות איתן מתמודדים מנהלי מערכות. לאורך זמן, היא מוביל לירידה בביצועים, כאשר בסופו של דבר קיטוע עלול להוביל לאובדן מוחלט של זיכרון פנוי. בעיית קיטוע הזיכרון היא בעיה תכנותית ברמת הגרעין (kernel). היא נעשית קריטית כאשר היא מגיעה לרמות גבוהות, לדוגמה, מערכות זמן אמת (real time) מגיעות באופן תדיר לקיטוע של 99%. רמה כזו של קיטוע מתרחשת שניות לפני קריסת המערכת, דבר המקשה על מניעתה מכיוון שקשה לצפות את הנקודה הקריטית בה עולה הקיטוע. על פי מחקר שהתבצע ב International Data Corporation, ירידה בביצועים מתרחשת לרוב בשל קיטוע חיצוני, כאשר זמן החיים של שרת מתקצר ב-33% בשל קיטוע חיצוני בלבד, דבר המוביל לעליה של 33% בתקציב השנתי לשדרוג חומרה. לקיטוע זיכרון יש אפוא השפעה לא רצויה לא רק על שימוש הזיכרון ומהירות העיבוד אלא גם על רכיבי חומרה ועלות פרויקטים מחשוביים.

איחוי מידע[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – איחוי