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

  • 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, אין בלוק פנוי אחרי.

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

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

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

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. תקינות הפרמטרים:

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

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

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

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

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

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

אפשרות 1: הבלוק שהמשתמש רוצה לשחרר זהו בלוק זיכרון חופשי.

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

שורה (3) מטפלת באפשרות מספר 1.

שורה (4) מטפלת באפשרות מספר 2.

  1. מצבים אפשריים עבור מיקום הבלוק:
  • q==NULL וגם p==NULL, כלומר אין אף בלוק זיכרון פנוי.

מצב זה מטופל בשורה (6):

-          שמים בתחילת block את הרשומה החדשה.

-          memlist מצביע כעת על block.

  • q==NULL וגם p!=NULL, כלומר אין בלוק פנוי לפני הבלוק שרוצים לשחרר, אולם יש בלוק פנוי אחריו.

טיפול ראשון למצב זה בשורה (6):

-          שמים בתחילת block את הרשומה החדשה.

-          memlist מצביע כעת על block.

כעת נבדוק האם צריך לאחד את הבלוק הפנוי החדש עם הבלוק הפנוי שאחריו או שלא.

אם לא צריך לאחד את הבלוקים, סיימנו. אחרת, שורה (7) דואגת לאיחוד.

  • q!=NULL וגם p!=NULL. במקרה זה ישנן מספר אפשרויות:

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

טיפול ראשון בשורה (5): מרחיבים את q לכלול גם את block.

טיפול שני בשורה (7): מרחיבים את q לכלול גם את p, ומוציאים את p מהרשימה.

אפשרות 2: block צמוד ל-q אבל לא ל-p.

שורה (5) מטפלת במקרה זה. q גדל כדי לכלול את block.

אפשרות 3: block נמצא בין q ל-p, אבל הוא איננו צמוד לאף אחד מהם.

במקרה זה אנו רואים את הבאג שבפונקציה freemem:

שורה (6) גורמת ש-block יהיה הבלוק הראשון ברשימה. כל הזיכרון הפנוי שהיה לפני block נאבד.

אפשרות 4: block לצמוד ל-p אבל לא ל-q.

גם מקרה זה לא מטופל כראוי על ידי freemem. גם במקרה זה, הזיכרון שלפני block נאבד.

תגיות המסמך:

מאת: יחיאל

EDOK

EEP3EI
מאת: יחיאל

EDOK

EDOK
מאת: יחיאל

EDOK

EDOK
מאת: באסל

תודה

הסברתם את זה, כמו שאר הנושאים, באופן הכי ברור שיש.
שיתוף:
| עוד