os - memory Flashcards
כיצד החומרה תחשב את הכתובת הזכרון הפיזית של הכתובות הווירטואליות
בחומרה ישנם שני אוגרים
- limit, שאליו יטען גודל המחיצה של התהליך ו
-base, שאליו יטען המקום הרצוי בתוך המחיצה.
על החומרה לוודא שהחישוב אינו חורג מגבולות המחיצה של התהליך.
הרכיב שאחראי לתרגום המקומות הווירטואליים הוא ה-Memory Management Unit (MMU)
בכל התייחסות לכתובת וירטואלית תתבצע השוואתה אל הערך באוגר limit .אם
הכתובת הווירטואלית מתייחסת לאזור שחורג מגבולות המחיצה, הדבר מעיד על
ניסיון לגישה בלתי חוקית. במקרה של גישה בלתי חוקית, המעבד יגרום לפסיקת
.protection fault
במקרה של התייחסות לכתובת חוקית, יתווסף לכתובת הווירטואלית הערך של
האוגר base ,והתוצאה המתקבלת תהיה הכתובת הפיזית.
מבני נתונים להקצאת שטחי זיכרון בשיטת המחיצות הניידות:
הקצאת שטחי זיכרון פנויים באמצעות מפת סיביות (bits-map)
הקצאת שטחי זיכרון פנויים באמצעות רשימות מקושרות (linked lists)
Quick Fit
הקצאת שטחי זיכרון פנויים באמצעות מפת סיביות (bits-map):
מחלקים את הזיכרון לקטעים בגודל קבוע. מקום תפוס בזיכרון מסומן ב-1 ומקום פנוי מסומן ב-0. הקצאת זיכרון תתבצע על ידי חיפוש סדרת 0-ים רציפה במפת הסיביות כך שהקטעים המתאימים יספיקו להכיל את התהליך. נשים לב כי בחירת קטעים גדולים תביא לריסוק פנימי (תופעת בזבוז זיכרון הנגרמת מהקצאת זיכרון עודפת לתהליך) גדול, כיוון שגודל התהליך לא תמיד יהיה כפולה שלמה של גודל קטע ההקצאה. מצד שני, זה יגרום לכך שמפת הסיביות תהיה קטנה יותר. שיטה זו היא פשוטה למימוש, אך זמן החיפוש בה עלול להיות ארוך.
הקצאת שטחי זיכרון פנויים באמצעות רשימות מקושרות (linked lists)
שתי רשימות מקושרות ממוינות לפי כתובות (או לפי גודל)- האחת של שטחים פנויים והשנייה של שטחים תפוסים (ניתן גם לשמור רק את הרשימה של השטחים הפנויים ולהסיק ממנה אילו שטחים תפוסים).
הקצאת שטחי זיכרון פנויים באמצעות Quick Fit
החזקת מספר רשימות של שטחים פנויים, כאשר כל רשימה מחזיקה טווח מסוים של גדלים. קל למצוא בשיטה הזאת שטח פנוי, אך בעת שחרור שטחי זיכרון יש צורך לבדוק אם ניתן לאחד את השטח שהתפנה עם שטח אחר, דבר הדורש זמן ניכר.
אלגוריתמים להקצאת שטח זיכרון פנוי
First Fit: חיפוש מהיר הנעשה כל פעם מתחילת הרשימה. המקום שיוחזר הוא המקום הראשון ברשימה שמתאים לביקוש. יוצר שטחי זיכרון לא פנויים בתחילת הזיכרון, ושטח רציף בסופו.
Next Fit: דומה ל-First Fit, רק שבמקום להתחיל כל פעם מתחילת הרשימה, ממשיכים מהמקום ממנו הפסקנו בסריקה הקודמת.
הוא נוטה לפצל את השטח הפנוי בסוף הזיכרון, ולכן ייתכן שבסופו של דבר
אלגוריתם זה ידרוש את הביצוע של פעולת הציפוף )compaction( יותר פעמים
Best Fit: מתבצעת סריקה של כל הרשימה. המקום שיוחזר הוא המקום הקטן ביותר שמסוגל להכיל את התהליך. שיטה זו גורמת להיווצרות המון חורים קטנים בזיכרון, ולכן זהו האלגוריתם הגרוע ביותר.הוא נוטה ליצור הרבה שטחים פנויים שקשה לנצלם עקב גודלם
הקטן. לכן השימוש בו ידרוש לרוב את הציפוף התכוף מבין שלושת האלגוריתמים.
Worst Fit: מתבצעת סריקה של כל הרשימה. המקום שמוחזר הוא המקום הפנוי הגדול ביותר.
יוצר גם הוא תבנית ריסוק אחידה, מכיוון שבכל פעם הוא
מנסה לפצל את השטחים הרציפים הגדולים ביותר
מה הוא זיכרון וירטואלי
על מנת להריץ תהליכים שגודלם עולה על גודל הזיכרון הפיזי במערכת, ניתן לאחסן בזיכרון הראשי רק את החלק החיוני לביצוע, ואת יתר החלקים ניתן לאחסן בדיסק
מרחב הכתובות של התהליך מחולק לדפים בגודל קבוע. המיפוי של הדפים השמור במבנה נתונים נקרא טבלת דפים (page table), ששורותיה מכילות מידע על הדפים כגון האם הדף ממופה למסגרת זיכרון, לאיזו מסגרת וכו’.
ממה מורכבת כתובת זיכרון וירטואלית
מספר הדף ולהיסט בתוך הדף
מספר הדף משמש כאינדקס של שורה בטבלת הדפים
ממה מורכבת כתובת זכרון פיזית
מספר המסגרת בזיכרון ומערכו של ההיסט בתוך המסגרת עצמה
Translation Lookaside Buffer (TLB)
הוא סוג של זיכרון מטמון, בו מוחזקת רק קבוצה קטנה של שורות מטבלת דפים. שורות ב-TLB צריכות להכיל שדה עם מספר דף כדי לציין לאיזה דף מתייחס המידע בשורה (שורות אלה אינן מכילות שדה של reference bit). מדיניות החלפת הדפים ב-TLB היא LRU, כך שהחיפוש נעשה בצורה מקבילית ולכן מהירה.
זיכרון אסוציאטיבי
8 אלגוריתמים להחלפת דפים כולל פירוט
Not Recently Used (NRU): נעיף דפים לפי ההעדפה הבאה (לפי ה-reference bit וה-modified bit), כך שהאלגוריתם בוחר באופן רנדומלי דף מקבוצת הסיווג הגבוהה ביותר שקיימת:
א. לא הייתה התייחסות אל הדף לאחרונה וגם לא השתנה לאחרונה.
ב. לא הייתה התייחסות אל הדף לאחרונה אך השתנה לאחרונה.
ג. הייתה התייחסות אל הדף לאחרונה אך הוא לא השתנה.
ד. הייתה התייחסות אל הדף לאחרונה והוא גם השתנה לאחרונה.
האלגוריתם קל למימוש, וביצועיו סבירים (אך אינם אופטימליים).
FIFO: הדפים נשמרים ברשימה מקושרת לפי הסדר שבו הם נכנסו לזיכרון. הדף שנמצא בראש הרשימה (זה שהגיע לפני הכי הרבה זמן) יוחלף. שיטה זו קלה למימוש אך חסרונה הוא שגם דפים שמשתמשים בהם לעיתים קרובות יכולים להיות מוחלפים מהזיכרון.
Second Chance: שדרוג של FIFO, מהבחינה שבכל פעם שהדף מגיע לראש התור, אם סיבית ההתייחסות שלו דלוקה נכבה אותה ונכניס אותו לסוף התור. אם היא כבויה אז נוכל להעיף את הדף.
Clock Page Replacement: שינוי במבנה הנתונים (מעבר לרשימה מעגלית) של אלגוריתם הזדמנות שנייה, מה שגורם לשיפור בביצועים שלו, כיוון שאין צורך להעביר דפים לסוף התור. קיימים שני מצביעים: האחד מצביע אל הדף הבא שנבדק לפינוי, שבודק אם סיבית ההתייחסות שלו היא 0 או 1 (ופועל כמו באלגוריתם הזדמנות שנייה). המצביע השני מאפס את סיבית ההתייחסות (paging daemons).
Least Recently Used (LRU): זורק את הדף שהיה לא בשימוש בזמן הארוך ביותר. אלגוריתם זה הוא מצוין אך יקר מאוד למימוש, כיוון שיש צורך בעדכון הרשימה בכל גישה לזיכרון, ולכן לא משתמשים בו בצורתו הטהורה.
Aging: לכל דף קיים מונה המורכב ממספר מסוים של ביטים. בכל פרק זמן המוגדר מראש, מתבצע למונה shift right. הביט הימני ביותר נהיה 1 אם הדף היה בשימוש בפרק הזמן המוגדר, ונהיה 0 הוא לא. בעת פסיקת דף, הדף עם המונה הנמוך ביותר הוא זה שנמחק. כאשר יש שני דפים עם אותו ערך של מונה, האלגוריתם בוחר אחד מהם באקראי. אלגוריתם יעיל שנותן ערך קרוב לאלגוריתם LRU.
Working Set (WS): דומה ל-NRU רק שעבור כל דף נשמר בנוסף גם מועד הפנייה האחרון אליו. אם סיבית ההתייחסות היא 0, הדף שיצר הוא דף שגדול מ- מסוים המוגדר במערכת. אם עבור כל דף מתקיים , יוצא הדף שה-age שלו הוא הגדול ביותר. אלגוריתם זה הוא יקר למימוש.
WSClock: אותו אלגוריתם של WS, רק שהרשימה מוצגת בתור רשימה מעגלית. דף שעבורו אך סיבית ההתייחסות שלו היא 1, נחליף את ה-age שלו לזמן הנוכחי ונכבה את סיבית ההתייחסות שלו. אלגוריתם זה הוא טוב ויעיל.
מדיניות החלפה של דפים - מדינות לוקלית
מדינות בה פינוי דף מתבצע רק מתוך קבוצת הדפים של התהליך הדורש דף נוסף. ניתן להקצות כמות קבועה של דפים לכל תהליך, מה שיכול להוביל לסחרור (thrashing)- תהליך הגורם לפסיקת דף מיד אחרי ביצוע של מספר קטן של הוראות קוד. במצב זה התהליך כמעט אינו מתקדם מכיוון שמרבית הזמן מתבזבז על החלפת דפים בין הזיכרון הראשי לזיכרון המשני, או לבזבוז (הקצאת דפים מיותרים). ניתן גם להקצות מספר משתנה של דפים. דבר זה דורש משאבים חישוביים, בנוסף לחישובים הכרוכים בשימוש באלגוריתם להחלפת דפים.
כאשר מדיניות זו ממומשת, כל תהליך מקבל
הקצאה קבועה של מסגרות דף פיזיות
(הקצאה לתהליכים שונים יכולה להיות
שונה). כאשר יש צורך להביא לזיכרון הפיזי
דף בעבור תהליך מסוים, הדף שיפנה לו את
מקומו ייבחר רק מבין הדפים השייכים
לאותו התהליך.
מדיניות החלפה של דפים - מדינות גלובלית
פינוי דפים ללא קשר לזהות של התהליך הדורש דף חדש. ניתן להקצות מספר משתנה של דפים, שיטה הקלה ליישום וגם נותנת ביצועים טובים כשיש עוד מסגרות פנויות. החיסרון שלה הוא כאשר נדרש להוציא דף לזיכרון המשני, מה שעלול לגרום לפגיעה בקבוצת העבודה של תהליך שלא גרם לפסיקת דף
מדיניות זו קובעת כי כאשר יש צורך להביא
לזיכרון דף בעבור תהליך מסוים, הדף שיפנה
לו את מקומו ייבחר מבין כל הדפים בזיכרון,
ללא קשר לשייכות של הדף לתהליך זה או
אחר.
ניהול כמות הקצאת המסגרות על ידי אלגוריתם Page Fault Frequency (PFF)
יש צורך לעקוב בשתי השיטות שלהלן אחר כמות הדפים המוקצית לתהליכים. נשים לב כי תנאי הכרחי למניעת סחרור הוא הימצאותה של כל קבוצת העבודה של תהליך מסוים בזיכרון, אך הקצאת דפים מעבר לכך גורמת לבזבוז. לכן, אם יודעים אילו תהליכים גורמים בצורה מתמדת לפסיקות דף, ניתן להסיק שמדיניות ההחלפה פגעה בקבוצת העבודה שלהם. אם התהליך מתבצע כמעט בלי פסיקות דף, כנראה יש לו עודף של מסגרות. אלגוריתם PFF משתמש בעיקרון זה.
קביעת גודל הדף - שיקולים בעד דפים קטנים
דפים קטנים גורמים לפחות בזבוז בדף האחרון של התהליך (ריסוק פנימי שגודלו מחצית מגודל הדף), דפים קטנים מחלקים את המרחב הווירטואלי לכמות גדולה יותר של חלקים, מה שאולי יגרום לכך שהגודל הכולל של קבוצת העבודה של תהליך יהיה קטן יותר מבחינת זיכרון.
