היי...

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

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

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

Subtle and insubstantial, the expert leaves no trace; divinely mysterious, he is inaudible.
Thus he is the master of his enemy's fate.

אמת, הקצאת הזיכרון/שחרור ב-kernel mode בתדירות גבוהה ייגרום לירידת ביצועים במערכת.
אחד הסיבות שחובה תמיד כשאפשר להשתמש מחדש בזיכרון שהוקצא ולא להקצאות מחדש.

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

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

C pogrammers never die. They are just cast into void.

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

יש דרך שבהתחלה עשיתי שזה פשוט להגדיר 5 גדלים קבועים שאני יכול להקצות 4 8 16 32 64
ואז כל פעם שאני רוצה להקצות בלוק אני מקצה אותו בבלוק שהכי קרוב לגודל שלו... אבל רציתי בסוף לשחק קצת עם הקצאות הזכרון קצת יותר אז החלטתי לממש הקצאה מתוך pool משלי


פשוט עניין אותי אלו גישות אחרות ממה שאני חשבתי עליה יש לבעיה הזו....

Subtle and insubstantial, the expert leaves no trace; divinely mysterious, he is inaudible.
Thus he is the master of his enemy's fate.

אני לא יודע אם יש חומר שאני אוכל לחדש בו, אבל אם אני אמשיך את קו המחשבה שלך,
ישנה שיטת הקצאה הנקראת Buddy System (שיטת הזוגות)
השיטה נוחה מאחר והיא מהירה (גם בהקצאה מחדש) וגם בחיפוש. הבעייה העיקרית שלה היא
ניצול לא יעיל של הזיכרון (Internal fragmentation) - אבל אם אתה מראש משתמש בבלוקים
בעלי גודל קבוע מראש, אז גם ככה את "סובל" מבעייה זו.

מידע על שיטה זו:
http://www.memorymanagement.org/art...ml#buddy.system
וגוגל כמובן
בהצלחה,

[ זיו ]
[ fat fish ]

אני רוצה למצוא פתרון יעיל כמה שאפשר להקצאות שגודל הבלוקים לא קבוע....

Subtle and insubstantial, the expert leaves no trace; divinely mysterious, he is inaudible.
Thus he is the master of his enemy's fate.

שיעזרו לנו לעזור לך...

האם יש מספיק מקום להקצות בכל זמן נתון לכל המשימות שצריכות לרוץ במקביל.
או שאתה מבצע החלפה ביזכרון בין משימות בזמן ביצוען?
מטרתה של השאלה היא לדעת האם מתבצעת החלפה (swap) של שמירת הנתונים להמשך עבודה
עם אותו תהליך בהמשך - אם הוא מופסק כרגע ואין מספיק מקום בזיכרון.

בקיצור - אלו שני מצבים שונים לחלוטין (עם החלפה או ללא) שפתרונם שונה ומוביל לשיטות ניהול
זיכרון שונות.

[ זיו ]
[ fat fish ]

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

C pogrammers never die. They are just cast into void.

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

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

--
גל דיסקין (gal diskin)

עצות והמלצות: