מערכת ההפעלה XINU

ספר אלקטרוני מאת: ניר אדר

פונקציות הקשורות לניהול זיכרון

getmem(nbytes)	הפונקציה מקצה שטח זיכרון באורך nbytes מתוך ה-heap.
freemem(block, nbytes)	הפונקציה משחררת שטח זיכרון לשימוש חוזר. הפונקציה מקבלת כפרמטר מצביע אל התחלת הבלוק וגם את גודל הבלוק לשחרר.

שמורה המנוהלת על ידי הפונקציות לטיפול בזיכרון:

בלוקים ברשימת הזיכרון הפנוי ממוינים בסדר עולה לפי כתובתם.

getmem()

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

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

הפונקציה משתמשת במקרו roundew(), המקבל מספר ומחזיר את העיגול שלו כלפי מעלה למספר הבא המתחלק ב-4. המקרו מוסיף 3 למספר, ואז מחזיר ממנו את שארית החלוקה שלו ב-4.

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

כאשר נמצא בלוק בגודש המבוקש: אם הבלוק בדיוק בגודל הרצוי, getmem מוחקת את הבלוק מרשימת הבלוקים הפנויים ומחזירה את כתובתו. אחרת, הפונקציה מחזירה בלוק בגודל nbytes מתחילת הבלוק הפנוי שמצאנו, ומשרשרת את שאר הבלוק הפנוי בחזרה אל רשימת הפנויים.

כאשר אנו מפצלים בלוק בצורה זו, המשתנה הפנימי leftover מצביע אל תחילת הקטע אותו נרצה לשרשר. החישוב כדי למצוא את leftover הוא פשוט: leftover נמצא במרחק nbytes בתים מתחילת הבלוק.

נשים לב שהוספת nbytes ל-p לא תשיג את התוצאה הרצויה, עקב אריתמטיקת המצביעים של שפת C. לכן, כדי לבצע חישוב מספרי, ראשית אנו ממירים את p ל-(char*), ולאחר מכין אנו ממירים את p בחזרה ל-(struct mblock*).

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

freemem()

בדומה ל-getmem, שני המצביעים p, q רצים על רשימת הזיכרון הפנוי. אנחנו עוצרים כאשר כתובת הזיכרון אותו רוצים לשחרר נמצאת ביניהם.

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

q מצביע אל הבלוק הפנוי שלפני הבלוק שרוצים לשחרר. p מצביע אל הבלוק הפנוי שאחרי הבלוק שרוצים לשחרר.

אם q הוא NULL, אין בלוק פנוי לפני. אם p הוא NULL, אין בלוק פנוי אחרי.

בפונקציה זו יש גם באג נוסף: הפונקציה איננה משרשרת את הזיכרון הפנוי כראוי.

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

$plot:\[\begin{gathered} {\text{/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }} \hfill \\ {\text{ * freemem - - free a memory block, returning it to memlist}} \hfill \\ {\text{ * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }} \hfill \\ {\text{ */}} \hfill \\ {\text{SYSCALL}} & {\text{freemem(block, size)}} \hfill \\ {\text{char *block;}} \hfill \\ {\text{word size;}} \hfill \\ {\text{\{ }} \hfill \\ & {\text{int}} & {\text{ps;}} \hfill \\ & {\text{struct}} & {\text{mblock}} & {\text{*p, *q;}} \hfill \\ & {\text{char}} & {\text{*top;}} \hfill \\ \hfill \\ & {\text{size = roundew(size);}} \hfill \\ & {\text{block = (char *) truncew( (word)block );}} \hfill \\ & \overbrace \begin{gathered} {\text{if ( size = = 0 || block > maxaddr || (maxaddr - block) < size ||}} \hfill \\ & & {\text{block < end )}} \hfill \\ \end{gathered} ^{{\text{(1)}}} \hfill \\ & & {\text{return(SYSERR);}} \hfill \\ & {\text{disable(ps);}} \hfill \\ & {\text{(char *)q = NULL;}} \hfill \\ & \overbrace \begin{gathered} {\text{for( p = memlist}}{\text{.mnext ;}} \hfill \\ & & {\text{(char *)p ! = NULL \& \& (char *)p < block ;}} \hfill \\ & & {\text{q = p, p = p - > mnext )}} \hfill \\ & & & {\text{;}} \hfill \\ \end{gathered} ^{{\text{(2)}}} \hfill \\ & {\text{if ( }}\overbrace {{\text{(char *)q ! = NULL \& \& (top = (char *)q + q - > mlen) > block}}}^{{\text{(3)}}} \hfill \\ & & {\text{ || }}\underbrace {{\text{(char *)p ! = NULL \& \& (block + size) > (char *)p}}}_{{\text{(4)}}}{\text{ ) \{ }} \hfill \\ & & {\text{restore(ps);}} \hfill \\ & & {\text{return(SYSERR);}} \hfill \\ & {\text{\} }} \hfill \\ & {\text{if ( }}\overbrace {{\text{(char *)q ! = NULL \& \& top = = block}}}^{{\text{(5)}}}{\text{ )}} \hfill \\ & & {\text{q - > mlen + = size;}} \hfill \\ & \overbrace {{\text{else}}}^{{\text{(6)}}}{\text{ \{ }} \hfill \\ & & {\text{((struct mblock *)block) - > mlen = size;}} \hfill \\ & & {\text{((struct mblock *)block) - > mnext = p;}} \hfill \\ & & {\text{memlist}}{\text{.mnext = (struct mblock *)block;}} \hfill \\ & & {\text{(char *)q = block;}} \hfill \\ & {\text{\} }} \hfill \\ & {\text{/* Note that q ! = NULL here */}} \hfill \\ & \overbrace \begin{gathered} {\text{if ( (char *)p ! = NULL}} \hfill \\ & & {\text{\& \& ((char *)q + q - > mlen) = = (char *)p ) \{ }} \hfill \\ \end{gathered} ^{{\text{(7)}}} \hfill \\ & & {\text{q - > mlen + = p - > mlen;}} \hfill \\ & & {\text{q - > mnext = p - > mnext;}} \hfill \\ & {\text{\} }} \hfill \\ & {\text{restore(ps);}} \hfill \\ & {\text{return(OK);}} \hfill \\ {\text{\} }} \hfill \\ \hfill \\ \end{gathered} \]$

ננתח כעת את הפונקציה.

תקינות הפרמטרים:

בשורה (1) אנו בודקים שלא גלשנו מגבולות הזיכרון הפנוי להקצאה – מלמעלה ומלמטה.

סריקת רשימת הבלוקים הפנויים:

שורה (2): שני המצביעים q, p מטיילים על הרשימה.

בסוף הלולאה: q מצביע אל הבלוק הפנוי שלפני הבלוק שרוצים לשחרר. p מצביע אל הבלוק הפנוי שאחרי הבלוק שרוצים לשחרר.

בדיקת חוקיות הבלוקים:

לאחר שקבענו את ערכי q, p, נבדוק שחוקי לשחרר את הבלוק המבוקש. ישנם שני מצבים בהם לא חוקי לשחרר את הבלוק:

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