שפת C/ניהול זיכרון דינאמי
לעתים, אי אפשר לדעת בזמן כתיבת הקוד את כמות הזיכרון הנדרשת לצורך הריצה. מערכת ניהול הזיכרון הדינאמי מאפשרת להקצות ולשחרר זיכרון בזמן הריצה.
|
כדאי לדעת: קטעי הקוד שבפרק זה משתמשים בספרייה הסטנדרטית. נדון בספריות באופן מעמיק יותר כאן. לעת עתה, פשוט יש לזכור לרשום בראשי הקבצים המשתמשים בקטעי הקוד שבפרק זה#include <stdlib.h>
|
הצורך בניהול זיכרון דינאמי
[עריכה]במערכים ראינו תוכנית לקליטת מספרים והדפסתם בסדר הפוך:
#include <stdio.h>
int main()
{
int numbers[10];
int i;
for(i = 0; i < 10; i++)
scanf("%d",&numbers[i]);
for(i = 9; i >= 0; i--)
printf("%d\n",numbers[i]);
return 0;
}
התוכנית יודעת לטפל ב-10 מספרים בדיוק.
כעת נחשוב על מקרה שונה. המשתמש אינו יודע כלל מראש כמה מספרים ברצונו להקליד. נכתוב, לכן, תוכנית, ששואלת אותו לאחר כל מספר, האם הוא רוצה להמשיך או לא:
#include <stdio.h>
int main()
{
int c;
int numbers[10];
int i=0;
do
{
int d;
printf("Please enter a number: ");
scanf("%d", &d);
numbers[i] = d;
i++;
printf("Please enter 0 to quit, or any other number to continue: ");
scanf("%d", &c);
}
while(c != 0);
printf("The numbers you entered, in reverse order, are:\n");
do
{
i--;
printf("%d\n",numbers[i]);
}
while(i > 0);
return 0;
}
נשים לב שתוכנית זו פועלת עד 10 מספרים. אם המשתמש יקליד יותר מספרים מכך, נקבל גלישה מהמערך. לכאורה, קל לתקן זאת. נחליף את השורה:
int numbers[10];
בשורה:
int numbers[1000];
אך ברור למדי שה"פתרון" בעייתי:
- לא פתרנו את הבעיה, אלא "דחינו" אותה, מ-10 ל-1000.
- אם יתברר בדיעבד שהמשתמש הקליד 9 מספרים, חבל שהקצינו מערך כה גדול.
מערכת ניהול הזיכרון הדינאמי
[עריכה]כפי שראינו במצביעים, אפשר לחשוב על זיכרון המחשב כמערך ארוך. חלק ממערך זה, הערימה (heap בלעז), מיועד למערכת ניהול הזיכרון הדינאמי. נוכל לדמיין את הערימה בתחילה כריקה כולה, כך:
במהלך ריצת התוכנית, נוכל להשתמש בפונקציות כדי לבקש ממערכת ההפעלה להקצות לנו זיכרון (רציף) בגודל המבוקש. מערכת ההפעלה תחפש האם קיים קטע זיכרון מתאים בערימה, ואם כן, תסמן אותו כתחת שימוש ותחזיר לנו את כתובתו. לדוגמה, אם נבקש 6 בתים, הערימה תוכל להראות כך:
ששת הבתים הללו מסומנים כתחת שימוש. אם תגיע עוד בקשה להקצאת זיכרון, מערכת ההפעלה לא תחזיר כתובת של קטע החופף לקטע הזה. במילים אחרות, קטע זה בטוח לשימושנו. לאחר שנסיים להשתמש בקטע הזיכרון, נוכל להשתמש בפונקציה אחרת כדי לשחרר אותו. הדבר יודיע למערכת ההפעלה שקטע זה אינו בשימוש יותר, ואפשר להקצותו לבקשות אחרות.
|
|
כדאי לדעת: מערכת ההקצאה הדינמית משתמשת באיזור הזיכרון heap, ואילו משתנים מקומיים נשמרים באיזור הזיכרון stack. |
הקצאה
[עריכה]גודל ההקצאה הרצוי
[עריכה]כדי להקצות זיכרון, צריך לדעת ראשית את גודל הזיכרון הרצוי (בבתים). לרוב אנו יודעים משהו שונה במקצת: טיפוס המשתנים הרצוי, ומספר המשתנים הרצויים ברצף.
שפת C מאפשרת לנו לתרגם דרישות טיפוסים וסוגים לדרישות גודל על ידי האופרטור sizeof. כדי לראות את מספר הבתים שתופס טיפוס, נשתמש באופרטור sizeof בצורה:
sizeof(<t>)
כאשר t הוא טיפוס או משתנה. לדוגמה:
sizeof(int)
הוא מספר הבתים שתופס משתנה מסוג שלם,
ואילו:
sizeof(char) * 80
הוא מספר הבתים שתופסים 80 תווים רצופים (כמו במערך של תווים, לדוגמה). חשוב להשתמש באופרטור sizeof ולא להסתמך על כך שהגודל אותו תופס טיפוס מסויים כבר ידוע (למשל - 4 עבור משתנה מטיפוס שלם). הסיבה היא שבמחשבים מארכיטקטורות שונות ייתכן מצב בו משתנה מאותו טיפוס יתפוס נפח זיכרון שונה.
פונקציות ההקצאה malloc ו- calloc
[עריכה]כדי להקצות זיכרון, אפשר להשתמש בפונקציה malloc, בקריאה מהצורה הבאה:
malloc(<total_size>)
כאשר total_size הוא הגודל (בבתים) שאותו רוצים להקצות. לדוגמה:
malloc(sizeof(int))
היא בקשה להקצות מספיק בתים לשלם יחיד, ואילו:
malloc(sizeof(int) * 80)
היא בקשה להקצות מספיק בתים ל-80 שלמים רצופים.
לחלופין, אפשר להשתמש בפונקציה calloc, בקריאה מהצורה הבאה:
calloc(<num>, <size>)
כאשר num * size הוא הגודל (בבתים) שאותו רוצים להקצות. בפרט, אם num הוא מספר משתנים, וsize הוא גודל כל אחד מהם, אז הקריאה הנ"ל תקצה מקום רציף לnum משתנים. לדוגמה:
calloc(80, sizeof(int));
היא בקשה להקצות מספיק בתים ל80 שלמים רצופים.
שתי הפונקציות נבדלות בעיקר בכך שcalloc, מעבר להקצאת זיכרון, גם מאפסת את קטע הזיכרון אותו היא מקצה. למעט זאת, אין הבדל בין הקריאות הבאות:
malloc(80 * sizeof(int));
calloc(80, sizeof(int));
calloc(sizeof(int), 80);
הערך המוחזר
[עריכה]הן malloc והן calloc מחזירות את כתובת הזיכרון שאותו היקצו. טיפוס הערך המוחזר הוא void * (שהוסבר כאן). אם הפונקציות נכשלו בהקצאה, הכתובת שיחזירו תהיה NULL. לכן, לרוב יש שתי פעולות שיש לבצע על הערך המוחזר:
- לשים אותו למשתנה מצביע.
- לבדוק האם הערך המוחזר הוא NULL, ובמקרה שכן, לטפל בכישלון ההקצאה.
מיד נראה דוגמה כיצד לעשות שתי פעולות אלו.
דוגמה
[עריכה]להלן קטע קוד טיפוסי המקצה מקום למערך של n שלמים:
int *numbers = (int *)malloc( n * sizeof(int) );
if (numbers == NULL)
printf("Error: could not allocate memory!\n");
נעבור כעת על חלקי הקוד. הקריאה
malloc( n * sizeof(int) )
קוראת לפונקציה malloc, ומבקשת להקצות מקום לn מספרים שלמים. קריאה זו מחזירה טיפוס void *. את תוצאת הקריאה רוצים לשים בnumbers שהוא מטיפוס int *. ההמרה (cast בלעז)
(int *)
מבקשת מהמהדר להתייחס לטיפוס המוחזר כמצביע לשלמים ולא כvoid *. (בשפת C החלק הזה מיותר). השורה
int *numbers = (int *)malloc( n * sizeof(int) );
משימה לכן למצביע numbers את תוצאות ההקצאה המבוקשת. השורה
if (numbers == NULL)
בודקת האם ההקצאה נכשלה, והשורה לאחריה מדפיסה הודעה בהתאם.
שפת C ידועה בקיצורים הרבים שהיא מאפשרת. יש הכותבים את שורת הבדיקה כך:
if(!numbers)
נזכר שהקבוע NULL הנו למעשה 0, וכל מה שאינו 0 הנו ערך אמת בוליאני בשפת C. עם זאת, למען קריאות הקוד - עדיף להשתמש בצורה המלאה של שורת הבדיקה.
שחרור
[עריכה]פונקצית השחרור free
[עריכה]כדי לשחרר זיכרון שהוקצה, משתמשים בפונקציה free לפי הצורה:
free(<p>)
כאשר p היא כתובת זיכרון שהוחזרה על ידי אחת מפונקציות ההקצאה. אסור להעביר לפונקציה free כתובת זיכרון אחרת, או כתובת זיכרון שכבר שוחררה (אלא אם כן היא הוקצתה מאז מחדש, כמובן).
הנה דוגמה לשימוש בfree:
int *numbers = (int *)malloc(sizeof(int) * 80);
...
free(numbers);
להלן מספר שימושים שגויים בfree:
int n;
free(&n) /* This is not the address of allocated memory! */
וכן:
int *numbers = (int *)malloc(sizeof(int) * 80);
...
free(numbers);
free(numbers); /* This second deallocation is a mistake! */
חשיבות השחרור
[עריכה]כפי שראינו במערכת ניהול הזיכרון הדינאמי, קטע זיכרון שלא נשחרר אותו במפורש - לא יהיה זמין יותר לשימוש - זיכרון המחשב הוא משאב מוגבל.
|
שימו לב: הקצאה דינאמית של זיכרון מבלי לשחררו - דליפת זיכרון (memory leak בלעז) - עלולה לפגוע בביצועי המערכת. |
מערכות הפעלה מודרניות יודעות להתמודד עם דליפת זיכרון של תוכנית, ולאחר שהיא מסיימת את פעילותה - לפנות את הזיכרון שהקצתה. עם זאת, כל זה מסייע רק כאשר כותבים יישום שאמור לבצע פעולה קצרה ותו לא. יישום שפועל באופן רציף (למשל - משחק מחשב) וסובל מדליפת זיכרון, אפילו מצומצמת מאוד, יאט את פעילות המחשב עד שבסופו של דבר יקרוס.
דוגמה: רשימה מקושרת
[עריכה]נפתור כאן את הבעיה שראינו בצורך בניהול זיכרון דינאמי, על ידי רשימה מקושרת.
מהי רשימה מקושרת?
[עריכה]רשימה מקושרת היא מבנה נתונים המורכב מחוליות. כל חוליה היא מבנה ששדותיו הם תוכן החוליה (לדוגמה מספר שלם) ומצביע לחוליה הבאה. התרשים הבא מראה זאת.
נממש חוליה על ידי הstruct הבא:
struct link_
{
int data;
struct link_ *next;
};
typedef struct link_ link;
במבנה זה, השדה data מכיל את תוכן החוליה, והשדה next הוא מצביע לחוליה הבאה.
כפי שהראה התרשים הראשון, נחזיק מספר חוליות כאלו. כל אחת מהן תצביע לבאה. בנוסף, נחזיק מצביע head, שיצביע לחוליה הראשונה ברשימה.
הוספת חוליה
[עריכה]נניח שמשתנה d מכיל ערך כלשהו, ואנו מעוניינים ליצור חוליה חדשה המכילה ערך זה, ולהוסיף חוליה זו לראש הרשימה.
ראשית מקצים זיכרון לחוליה חדשה, ומשימים את התוצאה למצביע l (כמובן שבודקים האם ההקצאה הצליחה):
link *const l = (link *)malloc(sizeof(link));
if(l == NULL)
/* Handle allocation failure. */
...
כעת קובעים שערך data, התוכן, הוא d, וערך next, המצביע לחוליה הבאה, לhead, ראש הרשימה:
l->data = d;
l->next = list->head;
לבסוף קובעים שראש הרשימה הוא l:
head = l;
קטע הקוד הבא מסכם זאת:
link *const l = (link *)malloc(sizeof(link));
if(l == NULL)
/* Handle allocation failure. */
...
l->data = d;
l->next = list->head;
head = l;
מחיקת חוליה
[עריכה]נניח שאנו רוצים לשמור את תוכן החוליה הראשונה במשתנה d, ולמחוק את החוליה הראשונה.
שתי השורות הבאות מאתחלות מצביע l לחוליית הראש ומשתנה d לתוכנו:
link *const l = list->head;
const int d = l->data;
כעת נגרום למצביע לראש הרשימה להצביע על החוליה הבאה:
head = l->next;
לבסוף, נשחרר את החוליה המיותרת:
free(l);
קטע הקוד הבא מסכם זאת:
link *const l = list->head;
const int d = l->data;
head = l->next;
free(l);
שימוש לקליטת והפיכת מספרים
[עריכה]נוכל להשתמש ברשימה מקושרת לצורך קליטת מספרים והדפסתם בסדר הפוך. הפתרון שנראה כאן מדגיש את הנקודות החדשות הנוגעות לניהול זיכרון דינאמי, ונכתוב אותו בצורה רשלנית מבחינת הנדסת תוכנה; במעט על מבנים והנדסת תוכנה נתקן זאת מעט. להלן התוכנית:
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int main()
{
struct link_
{
int data;
struct link_ *next;
};
typedef struct link_ link;
int c;
link *head = NULL;
do
{
int d;
printf("Please enter a number: ");
scanf("%d", &d);
link *const l = (link *)malloc(sizeof(link));
if(l == NULL)
return -1;
l->data = d;
l->next = head;
head = l;
printf("Please enter 0 to quit, or any other number to continue: ");
scanf("%d", &c);
}
while(c != 0);
printf("The numbers you entered, in reverse order, are:\n");
while(head != NULL)
{
link *const l = head;
const int d = l->data;
head = l->next;
free(l);
printf("%d\n", d);
}
return 0;
}
הקוד מורכב משני חלקים עיקריים.
החלק הראשון מורכב מלולאת do while. הוא מבקש מספר מהמשתמש, מכניס מספר לרשימה המקושרת כפי שראינו בהוספת חוליה, ושואל האם יש עוד מספרים להוסיף:
do
{
int d;
printf("Please enter a number: ");
scanf("%d", &d);
link *const l = (link *)malloc(sizeof(link));
if(l == NULL)
return -1;
l->data = d;
l->next = head;
head = l;
printf("Please enter 0 to quit, or any other number to continue: ");
scanf("%d", &c);
}
while(c != 0);
החלק השני עובד בלולאת while. הוא מוצא את הערך בראש הרשימה, מוחק את החוליה בראש הרשימה כפי שראינו במחיקת חוליה, ומדפיס את הערך.
printf("The numbers you entered, in reverse order, are:\n");
while(head != NULL)
{
link *const l = head;
const int d = l->data;
head = l->next;
free(l);
printf("%d\n", d);
}
שינוי הקצאה
[עריכה] |
שקלו לדלג על נושא זה הבנה שטחית של נושא זה עלולה ליצור קטעי קוד בעלי דליפת זיכרון פוטנציאלית. מומלץ לחזור לנושא לאחר שליטה סבירה בניהול זיכרון דינאמי. |
הבעיה
[עריכה]לפעמים נתקלים בבעיה הבאה. המצביע p מצביע לרצף זיכרון מוקצה בעל מספר בתים כלשהו, אך פתאום נוכחים לדעת שיש צורך להגדיל או להקטין את רצף הזכרון המוקצה. לדוגמה, נתבונן בקטע הקוד הבא:
char *chars = (char *)calloc(3, sizeof(char));
if(!chars)
...
chars[0] = 'a';
chars[1] = 'b';
chars[2] = 'e';
/* Do some operations. */
...
בתחילה מקצים לchars רצף המתאים למערך של 3 תווים, אך לאחר רצף פעולות כלשהו, יש צורך להגדיל את הרצף המוצבע על ידי chars למערך של 5 תווים, לדוגמה.
פונקציית שינוי-ההקצאה realloc
[עריכה]שינויי הקצאות אפשר לעשות בעזרת הפונקציה realloc, על ידי קריאות מהצורה הבאה:
realloc(<old_ptr>, <total_size>)
כאשר old_ptr היא כתובת הזיכרון המוקצאת הנוכחית, וtotal_size הוא הגודל החדש המבוקש (בבתים).
מערכת ההפעלה תנסה לראות האם אפשר לשנות את רצף הזיכרון הנוכחי לגודל המבוקש. אם הדבר אפשרי, הפונקציה תחזיר את כתובת הזיכרון של הרצף הנוכחי כvoid * (בדיוק כפי שראינו מקודם בהקצאה). אם הדבר אינו אפשרי, היא תבדוק האם יש רצף אחר מתאים בזיכרון. אם היא הצליחה, היא תעתיק את תוכן הרצף הנוכחי לרצף החדש, תשחרר את הרצף הנוכחי, ותחזיר את כתובת הרצף החדש. אם אין רצף אחר מתאים בזיכרון, היא לא תשנה כלום בזיכרון (ובפרט, לא תשחרר את הרצף הנוכחי), ותחזיר NULL כדי לסמן שלא הצליחה.
שני התרשימים הבאים מראים מצב אפשרי בו realloc תחזיר כתובת זיכרון שונה מהכתובת הנוכחית. תחילה נראה הזיכרון כך:
שני רצפים נמצאים כעת בזיכרון: אחד מתאים למצביע chars, והשני למצביע אחר py. אפשר להאריך את רצף הזיכרון הנוכחי של chars בתו אחד, אך לא בשניים. הפונקציה realloc תזהה שקיים רצף אחר גדול מספיק, תקצה אותו, תעתיק את שלושת התווים אליו, תשחרר את הרצף הנוכחי, ותחזיר את הכתובת החדשה. לאחר שנשים את הכתובת החדשה בchars, ייראה הזיכרון כך:
מעט על מבנים והנדסת תוכנה
[עריכה]הבעיה
[עריכה]בשימוש ברשימה מקושרת לקליטת והפיכת מספרים ראינו כיצד להשתמש ברשימה מקושרת כדי לקלוט מספרים ולהדפיסם בסדר הפוך. הפתרון שראינו, למרות נכונותו - בעייתי. קשה לכתוב ולתחזק קוד כזה (ראה גם מעט על פונקציות והנדסת תוכנה). בפרט, הקוד שמטפל בקלט ופלט מעורבב בקוד שמנהל את הרשימה המקושרת. לכן:
- קשה לעשות שימוש חוזר (כלומר בתוכנית אחרת) בקוד הרשימה המקושרת
- הקוד מסובך להבנה יחסית למה שהוא עושה
- אם תתגלה שגיאה בקוד, יהיה קשה יותר להבין איזה חלק גרם לה
כימוס רשימה
[עריכה]נחשוב ראשית מה הפעולות שבהן היינו רוצים שרשימה תתמוך. להלן הצעה אפשרית:
- פעולה שיוצרת רשימה
- פעולה שהורסת רשימה בתום השימוש (כולל שחרור משאבים שטרם שוחררו)
- שאילתה לגבי מספר האיברים
- דחיפת איבר לראש הרשימה
- שליפת איבר מראש הרשימה
- שאילתה לגבי האיבר בראש הרשימה
כדי לתמוך בפעולות הנ"ל, אפשר לממש רשימה כמבנה ששדותיו הם מצביע לראש הרשימה ומונה למספר האיברים ברשימה:
struct list_
{
link *head;
unsigned long size;
};
typedef struct list_ list;
להלן ההצהרות לפעולות שבהן רצינו שרשימה תתמוך:
/* Constructs a list (prepares it for use). */
void list_ctor(list *list);
/* Destructs a list (after use). */
void list_dtor(list *list);
/* Returns the number of elements in the list. */
unsigned long list_size(const list *list);
/* Pushes new data to the head of the list.
* Returns 0 if the operation succeeded, -1 otherwise. */
int list_push(list *list, int data);
/* Pops (removes) the element at the head of the list.
* Returns the element.
* Don't call if the size of the list is 0. */
int list_pop(list *list);
/* Returns the element at the head of the list.
* Don't call if the size of the list is 0. */
int list_head(const list *list);
כעת נוכל לממש כל אחת מפעולות אלו.
void list_ctor(list *list)
{
list->head = NULL;
list->size = 0;
}
void list_dtor(list *list)
{
link *l = list->head;
while(l != NULL)
{
link *const old = l;
l = old->next;
free(old);
}
list_ctor(list);
}
unsigned long list_size(const list *list)
{
return list->size;
}
int list_push(list *list, int data)
{
link *const l = (link *)malloc(sizeof(link));
if(l == NULL)
return -1;
l->data = data;
l->next = list->head;
list->head = l;
++list->size;
return 0;
}
int list_pop(list *list)
{
link *const l = list->head;
const int data = l->data;
list->head = l->next;
--list->size;
free(l);
return data;
}
int list_head(const list *list)
{
const link *const l = list->head;
return l->data;
}
שימוש ברשימה המכומסת
[עריכה]כעת, לאחר שכימסנו את הרשימה, נוכל להשתמש בה כדי לקלוט מספרים ולהדפיסם בסדר הפוך:
int main()
{
int c;
list lst;
list_ctor(&lst);
do
{
int d;
printf("Please enter a number: ");
scanf("%d", &d);
list_push(&lst, d);
printf("Please enter 0 to quit, or any other number to continue: ");
scanf("%d", &c);
}
while(c != 0);
printf("The numbers you entered, in reverse order, are:\n");
while(list_size(&lst) > 0)
printf("%d\n", list_pop(&lst));
list_dtor(&lst);
return 0;
}
נשים לב שהקוד מופרד הרבה יותר. הקוד בmain עוסק כמעט כולו בבירור בקליטת המספרים והדפסתם. הקוד המטפל בחוליות נמצא במקום אחר לחלוטין. בדוגמה לרשימות מקושרות במודולים נראה אפילו כיצד להפריד את הקוד לקבצים שונים לצורך שימוש חוזר.
להלן הקוד המלא בשלב זה:
#include <stdio.h>
#include <stddef.h>
#include <malloc.h>
struct link_
{
struct link_ *next;
int data;
};
typedef struct link_ link;
struct list_
{
link *head;
unsigned long size;
};
typedef struct list_ list;
/* Constructs a list (prepares it for use). */
void list_ctor(list *list);
/* Destructs a list (after use). */
void list_dtor(list *list);
/* Returns the number of elements in the list. */
unsigned long list_size(const list *list);
/* Pushes new data to the head of the list.
* Returns 0 if the operation succeeded, -1 otherwise. */
int list_push(list *list, int data);
/* Pops (removes) the element at the head of the list.
* Returns the element.
* Don't call if the size of the list is 0. */
int list_pop(list *list);
/* Returns the element at the head of the list.
* Don't call if the size of the list is 0. */
int list_head(const list *list);
void list_ctor(list *list)
{
list->head = NULL;
list->size = 0;
}
void list_dtor(list *list)
{
link *l = list->head;
while(l != NULL)
{
link *const old = l;
l = old->next;
free(old);
}
list_ctor(list);
}
unsigned long list_size(const list *list)
{
return list->size;
}
int list_push(list *list, int data)
{
link *const l = (link *)malloc(sizeof(link));
if(l == NULL)
return -1;
l->data = data;
l->next = list->head;
list->head = l;
++list->size;
return 0;
}
int list_pop(list *list)
{
link *const l = list->head;
const int data = l->data;
list->head = l->next;
--list->size;
free(l);
return data;
}
int list_head(const list *list)
{
const link *const l = list->head;
return l->data;
}
int main()
{
int c;
list lst;
list_ctor(&lst);
do
{
int d;
printf("Please enter a number: ");
scanf("%d", &d);
list_push(&lst, d);
printf("Please enter 0 to quit, or any other number to continue: ");
scanf("%d", &c);
}
while(c != 0);
printf("The numbers you entered, in reverse order, are:\n");
while(list_size(&lst) > 0)
printf("%d\n", list_pop(&lst));
list_dtor(&lst);
return 0;
}
| הפרק הקודם: מבנים |
ניהול זיכרון דינאמי תרגילים |
הפרק הבא: איגודים |