PROFILPELAJAR.COM

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

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

קיטוע זיכרון

העיקרון הבסיסי

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

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

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

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

תקורה (Overhead)

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

קיטוע פנימי (Internal Fragmentation)

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

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

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

קיטוע חיצוני (External Fragmentation)

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

${ExternalMemoryFragmentation=1-}{\frac {LargestBlockOfFreeMemory}{TotalFreeMemory}}$

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

קיטוע חיצוני הוא ערך בין 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% בתקציב השנתי לשדרוג חומרה. לקיטוע זיכרון יש אפוא השפעה לא רצויה לא רק על שימוש הזיכרון ומהירות העיבוד אלא גם על רכיבי חומרה ועלות פרויקטים מחשוביים.