דפדוף (זיכרון)

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

סקירה כללית

דפדוף מתבצע כאשר תוכנית מנסה לגשת לדפים שאינם ממופים לזיכרון פיזי. בעת גישה לזיכרון, פונה המעבד לזיכרון באמצעות יחידת ניהול הזיכרון (MMU), האחראית על תרגום מרחב הכתובות הווירטואלי ומרחב הכתובות הפיזי. אם יחידת הניהול מגלה שהדף המבוקש אינו ממופה לזיכרון הראשי נוצר ליקוי דף (page fault) ובקר הזיכרון שולח פסיקה מתאימה כדי לגרום למערכת ההפעלה לטעון את הדף המבוקש מהזיכרון המשני. מערכת ההפעלה מבצעת את הפעולות הבאות:

1. קביעת מיקום הנתונים בהתקני האחסון המשני.
2. במידה והזיכרון הראשי מלא, בחירת דף להסרה מהזיכרון הראשי.
3. טעינת הנתונים המבוקשים לזיכרון הראשי.
4. עדכון טבלת הדפים עם הנתונים החדשים.
5. סיום הטיפול בפסיקה.

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

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

בשלב 2, כאשר יש לטעון דף מהזיכרון המשני אך כל הדפים הקיימים בזיכרון הפיזי תפוסים, יש להחליף את אחד הדפים עם הדף המבוקש. מערכת הדפדוף משתמשת באלגוריתם החלפה כדי לקבוע מהו הדף שיוחלף. קיימים מספר אלגוריתמים המנסים לענות על בעיה זו. כאשר ה-(LRU - Least Recently Used) "שימוש אחרון קדום ביותר" עצמו אינו מיושם בחומרה הקיימת, רוב מערכות ההפעלה משתמשות בגרסה מקורבת כלשהי של אלגוריתם ההחלפה LRU או באלגוריתם המבוסס על קבוצות עבודה (ראו העמסה להגדרה)^{[דרוש מקור]}. אם הדף הנבחר להחלפה השתנה מאז הטעינה, יש לכתוב אותו לזיכרון המשני טרם טעינת הדף החדש.

הבאה לפי דרישה

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

הבאה לפי תחזית

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

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

ניקוי מוקדם

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

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

העמסה (Thrashing)

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

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

באלגוריתמים המבוססים על קבוצות עבודה יש מעט מאוד גידול במספר ההחטאות של הדפים (מספר פסיקות הדף) עד לנקודה קריטית (כאשר התקלות עולות באופן דרמטי ורוב כוח העיבוד של המערכת מבוזבז על הטיפול בהם). דוגמה קיצונית מעין זו של המצב קרתה במערכות המיינפריים IBM System/360 מודל 67 וסדרת System/370 של IBM, שבהן הוראה מסוימת יכולה להכיל הוראת ביצוע שחוצה את גבול העמוד, שמצביעה להוראת תזוזה שגם היא חוצה גבולות הדף, שהיא בעצמה משתמשת בנתונים ממקור שחוצה את גבולות הדף, כדי להצביע על נתונים שהם מעבר לגבולות הדף. המספר הכולל של הדפים שבשימוש ההוראה המסוימת הזו הוא שמונה וכל שמונת הדפים חייבים להיות טעונים בזיכרון באותו זמן. אם מערכת ההפעלה תקצה פחות משמונה עמודים של הזיכרון הפיזי בדוגמה זו, הרי כאשר היא מנסה להחליף את חלק ההוראה או להביא נתונים בשאר הגישות, ההוראה תגרום שוב לתקלת דף, דבר שיגרום לכל ניסיון להפעיל מחדש את ההוראה להיכשל.

כדי להקטין את ההחלפה המוגזמת, וכך אולי לפתור בעיות העמסה, המשתמש יכול לעשות כל אחת מהפעולות הבאות:

• להגדיל את כמות ה־RAM במחשב (בדרך כלל הפתרון הטוב ביותר לטווח ארוך)
• להקטין את מספר התוכניות הרצות במקביל במחשב

מימושים של זיכרונות משניים

חלונות x‏.3 וחלונות 9x

מיקרוסופט הציגה את יכולת הזיכרון הווירטואלי בחלונות 3.0 ב־1990 וזאת בתגובה לכישלונות של חלונות 1.0 וחלונות 2.0 ובניסיון לקצץ את דרישות המשאבים של מערכת ההפעלה, המשתמשת בקבצים המכונים קובצי החלפה לצורך הזיכרון המשני.

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

חלונות x‏.3 יוצרת קובץ מוסתר בשם 386SPART.PAR או WIN386.SWP (הנמצא בדרך כלל בספריית השורש אך עשוי להיות במקום אחר, בדרך כלל בספריה של חלונות) לשימוש כקובץ החלפה. גודל הקובץ תלוי במקום שהוקצה לקובץ ההחלפה שהוגדר במערכת (הגדרה שנבחרת על ידי המשתמש בלוח הבקרה). אם המשתמש מעביר או מוחק קובץ זה, המסך הכחול יופיע באתחול הבא של חלונות, עם הודעת שגיאה המודיע כי קובץ ההחלפה הקבוע פגום (בין אם הוא קיים או לא) והמשתמש יתבקש להחליט האם למחוק את הקובץ.

חלונות 95, חלונות 98 וחלונות Me משתמשות בקובץ דומה, שהגדרותיו נמצאות גם הן בלוח הבקרה. חלונות מגדירה באופן אוטומטי את הגודל ההתחלתי של הקובץ כגדול בחצי מגודל הזיכרון הפיזי ומרחיבה אותו עד פי 3 מגודל הזיכרון הפיזי במידת הצורך. אם המשתמש מפעיל יישומים עתירי שימוש בזיכרון במערכת עם זיכרון פיזי נמוך אזי עדיף להגדיר באופן ידני את הגדלים הללו לערך גבוה יותר מאשר ברירת המחדל ^{[דרוש מקור]}.

חלונות NT

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

קיטוע

בתצורת ברירת המחדל של חלונות, קובץ ההחלפה יכול להתרחב מעבר להקצאה הראשונית שלו בעת הצורך. אם דבר זה קורה בהדרגה, ניתן לקבל קיטוע מסיבי היכול לגרום לבעיות ביצועים. העצה הנפוצה למניעת זאת היא להגדיר גודל של קובץ החלפה אחד "נעול", כך שחלונות לא תרחיב אותו. אולם קובץ ההחלפה מתרחב רק כאשר הוא כבר מלא, קרי, בתצורת ברירת המחדל, כאשר הוא 150% של הזיכרון הפיזי הכולל. לפיכך, הגודל הכולל עבור קובץ ההחלפה של הזיכרון הווירטואלי על הדיסק חייב להיות גדול מ־250% של הזיכרון הפיזי של המחשב לפני ההרחבה של קובץ ההחלפה.

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

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

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

לינוקס

לינוקס ומערכות Unix אחרות, משתמשות במונח "החלפה (swap)" כדי לתאר הן את פעולת ההחלפה בין הדפים בזיכרון הפיזי ובדיסק, והן את האזור בדיסק שבו מאוחסנים הדפים שהוצאו מהזיכרון הראשי. נהוג להשתמש במחיצה שלמה (או LV שלם) של דיסק קשיח עבור החלפה. עם זאת, בליבת לינוקס 2.6 ניתן להשתמש בקובצי החלפה בדיוק באותה מהירות כמו במחיצות החלפה, הגמישות הניהולית של קובצי החלפה יכולה לגבור על יתרונות אחרים של מחיצות החלפה, הגם ש־Red Hat ממליצה להשתמש במחיצה. כמו כן היתרון של רציפות הנתונים בשל שימוש במחיצות איננו מובטח משום שבכוננים קשיחים מודרניים עם קיבולת גבוהה ניתן למפות מחדש את הסקטורים הפיזיים ולכן לא מובטח שהמחיצה תהא רציפה.

לינוקס תומכת במספר כמעט בלתי מוגבל של התקני (devices) החלפה הניתנים לתעדוף באופן אינדיבידואלי כאשר הסדר של ההתקנים אמור להיות מהמהיר ביותר עד האיטי ביותר (כלומר: המהיר ביותר שיש יקבל את העדיפות הגבוהה ביותר). וזאת משום שכאשר מערכת ההפעלה צריכה להחליף את הדפים בזיכרון הפיזי, היא משתמשת בהתקן בעדיפות הגבוהה ביותר עם מקום פנוי. אם למספר התקנים מוקצית אותה העדיפות, הם משמשים באופן במקביל (בדומה ל־RAID רמה 0), כך שהם מספקים ביצועים משופרים אם ניתן לגשת להתקנים בצורה יעילה במקביל (התקני החלפה הממוקמים באותו דיסק פיזי לא אמורים להיות בשימוש במקביל).

Mac OS X

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

AmigaOS 4

גרסת "עדכון סופי" של AmigaOS 4.0 הציגה מערכת חדשה להקצאת זיכרון RAM ואיחוי בזמני אי פעילות של התוכנות המבוססת על שיטת הקצאת לוחות זיכרון ודפי זיכרון המאפשרים החלפה. מימוש זה נבדק לאחר מכן על ידי המפתחים ולבסוף הוכנס בגרסה 4.1.

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

ביצועים

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

1. לינוקס מציעה את הפרמטר proc/sys/vm/swappiness/ אשר משנה את האיזון בין החלפת זיכרון בזמן ריצה, בניגוד להורדת הדפים מדפי זיכרון המטמון של המערכת
2. חלונות 2000, XP ו־Vista מציעות את הגדרת הרישום DisablePagingExecutive הקובעת האם קוד הליבה והנתונים יכולים להיות מועברים לזיכרון המשני

מחשבי מיינפריים משתמשים לעיתים קרובות בכונני דיסקים עם ראש לכל מסלול או כוננים תופיים עבור שטח הדפדוף על מנת להימנע מהעיכוב בחיפוש אחר ראש הפנוי לפעולה.

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

מערכות הפעלה Unix רבות (למשל AIX, לינוקס ו-Solaris) מאפשרות שימוש בהתקני אחסון מרובים עבור שטח ההחלפה במקביל, כדי לשפר את הביצועים.

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

שימוש בקובץ החלפה על התקני NAS עלול לגרום לעומס ניכר על הרשת בשל כמות המידע הרב הנדרש.

כוונון גודל שטח החלפה

בחלק ממערכות הפעלה הישנות המשתמשות בזיכרון וירטואלי, מקום לאחסון קובצי ההחלפה נשמר כאשר תוכניות מקצות זיכרון עבור נתונים בזמן ריצה. ספקי מערכת ההפעלה בדרך כלל מספקים קווים מנחים לכמות שטח ההחלפה שאמור להיות מוקצה, כאשר 1.5 או 2 פעמים גודל זיכרון ה־RAM של המחשב הוא גודל טיפוסי כך שעם כמות גדולה של זיכרון RAM, שטח הדיסק הדרוש לאחסון מידע ההחלפה יכול להיות גדול מאוד. גרסאות חדשות יותר של מערכות הפעלה אלו מנסות לפתור בעיה זו: למשל, כמה ליבות HP-UX מציעות פרמטר swapmem_on הניתן לכוונון ושולט האם לשמור על זיכרון מסוים בזיכרון הפיזי כך שבמערכות עם זיכרון RAM מספיק, יכולת זו מפחיתה באופן משמעותי את הצורך להקצות שטח לאחסון של הנתונים המוחלפים.

מענה על מגבלות של חומרת 32 סיביות

אין זה נדיר למצוא מחשבי 32 סיביות עם 4GB זיכרון RAM (הגודל המקסימלי למיעון ללא שימוש בהרחבת זיכרון פיזי - PAE). אולם ניתן להשתמש בשטח ההחלפה מעבר לגבול זיכרון זה משום שהתייחסות אליו היא במונחים של דפים ולא בתים בודדים.

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

בחירת דף להחלפה

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

היא יכולה לבחור דף מבין הדפים ששייכים לתהליך הנוכחי, או מבין כל הדפים במערכת.

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

אלגוריתם NRU - not recently used

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

אלגוריתם FIFO - first in, first out

כלל FIFO הפשוט, הראשון שנטען לזיכרון הוא גם הראשון שימחק.

מערכת ההפעלה שומרת תור של כל הדפים בזיכרון ומעדכנת אותו בכל פעם שהיא טוענת דף חדש (כשיש page-fault למשל)

אלגוריתם Second - chance

וריאציה של FIFO. אם ה-reference bit של הדף הבא בתור הוא 1, הביט מאופס והדף מוחזר לסוף התור. אחרת, הוא יוחלף.

אלגוריתם השעון

זהו מימוש יעיל של אלגוריתם Second - chance. במקום תור יש רשימה מעגלית, ומצביע שעובר אחד אחד על האיברים ברשימה. אם ה-reference-bit של הדף המוצבע הוא 1, כשצריך להחליף דף, הוא יאופס והמצביע ימשיך הלאה. אחרת, הדף הזה הוא הבא שיוחלף, ולאחר מכן המצביע ימשיך הלאה.