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

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

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

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

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

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

ניקוי מוקדם

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

חלונות 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. זיכרון ההחלפה יכול להיות מנוטרל או משופעל בכל רגע כך שהמשתמש יכול לבחור להשתמש רק בזיכרון הפיזי.

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

בחלק ממערכות הפעלה הישנות המשתמשות בזיכרון וירטואלי, מקום לאחסון קובצי ההחלפה נשמר כאשר תוכניות מקצות זיכרון עבור נתונים בזמן ריצה. ספקי מערכת ההפעלה בדרך כלל מספקים קווים מנחים לכמות שטח ההחלפה שאמור להיות מוקצה, כאשר 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, כשצריך להחליף דף, הוא יאופס והמצביע ימשיך הלאה. אחרת, הדף הזה הוא הבא שיוחלף, ולאחר מכן המצביע ימשיך הלאה.