חוצץ
במדעי המחשב חוצץ (באנגלית: Buffer) הוא מקטע זיכרון המאחסן מידע באופן זמני בעת העברתו ממקום למקום. העברה של מידע יכולה להתבצע מהתקן קלט ליישום מחשב במחשב, מיישום במחשב אל הפלט, בין שני תהליכים, בין שני התקני אחסון וכו'. חוצץ יכול להיות מיושם ברמת החומרה או התוכנה.
שימושים
חוצצים קשורים קשר הדוק עם התקני קלט/פלט. לרבים מהתקני החומרה יש חוצץ באמצעותו ניתן להעביר מהם או אליהם גושי מידע. בכונן קשיח למשל, ישנו חוצץ המקבל את המידע הנקרא על ידי הראש הקורא/כותב. לאחר שהחוצץ מתמלא, הכונן מסמן למערכת ההפעלה באמצעות פסיקה שיש לקרוא את תוכן החוצץ.
שימוש נוסף בחוצצים הוא על-מנת לסנכרן זרם של נתונים המתקבל בקצב בלתי ידוע או במהירות שלא ניתן לטפל בו בזמן אמת. בצורב דיסקים למשל, פעולת הצריבה חייבת להתבצע מהתחלה עד הסוף בשטף בלתי פוסק על-מנת למנוע את פגימת הדיסק (Data corruption). לכן, יש להכין את כל החומר המיועד לצריבה בטרם התחלת פעולת הצריבה. בדוגמה זו, החוצץ עוזר להתגבר גם על בעיית המהירות (פעולת הכתיבה למדיה היא פעולה איטית ביחס לגישה לקובץ בזיכרון ה-RAM), וגם על כך שהנתונים נדרשים באופן סדרתי בקצב מסוים.
חוצץ בודד
כאשר קיים חוצץ יחיד, המידע נכתב אל החוצץ. כאשר החוצץ מתמלא, הוא מאותת למערכת ההפעלה שיש לנקות אותו, המידע מועתק מהחוצץ ליעדו, תוכן החוצץ נמחק והחוצץ חוזר לשימוש. בשיטה זו, התהליך הכותב חייב להמתין עד שהחוצץ יתפנה לכתיבה.
חוצץ כפול
בשיטה זו קיימים שני חוצצים. המידע נכתב בכל פעם אל חוצץ אחד בלבד. כאשר חוצץ זה מתמלא, הוא מועבר לטיפול מערכת ההפעלה שמעבירה את תוכנו ליעד. בינתיים, ממשיך התהליך לכתוב לחוצץ השני. כאשר החוצץ השני מתמלא, התהליך חוזר לכתוב אל החוצץ הראשון (שהתרוקן בינתיים) ומעביר את הטיפול בחוצץ המלא למערכת ההפעלה. יתרונה של שיטה זו הוא שבכל זמן נתון קיים לפחות חוצץ אחד פנוי אליו אפשר לכתוב מידע ולכן אין צורך לחכות לריקון של החוצץ.
חוצץ מעגלי
חוצץ מעגלי הוא חוצץ שהתא האחרון בו מצביע חזרה לתא הראשון. בעת הכנסת איבר, מוסיפים את האיבר בתא הפנוי הבא ובעת קריאה קוראים את התו הראשון שהוכנס. היתרון בשיטה זו הוא שמאחר ומדובר בתאים שונים ניתן לבצע פעולות כתיבה וקריאה במקביל.
בעיות עם חוצצים
בדומה לכל מבנה נתונים, חוצצים סובלים מבעיות.
חריגה מהמינימום (Underflow)
חריגה מהמינימום נגרמת כאשר תהליך מרוקן חוצץ מהר יותר מאשר החוצץ מתמלא. כיוון שקצב עיבוד הנתונים גדול מקצב הכנסת הנתונים, על התהליך הקורא לעצור על מנת לאפשר לחוצץ להתמלא - דבר שעלול לגרום להשחתת מידע מכיוון שחוצצים מיושמים בדרך-כלל במקומות בהם סוג המידע אינו מאפשר עצירה כזאת. על-מנת להתגבר על הבעיה, נהוג להגדיר חוצצים גדולים מספיק ולכתוב אליהם מספיק מידע לפני תחילת הקריאה מהם.
הצפה (Overflow)
בניגוד לחריגה מהמינימום שהיא בעיה מובנית במודל, הצפה היא בעיה הקשורה ליישומים מעשיים. הצפה מתבצעת כאשר תהליך מנסה לגשת לקטע בזיכרון הנמצא אחרי המקום שהוגדר עבור החוצץ (בדרך-כלל כאשר החוצץ התמלא). המידע המוצף מהחוצץ עשוי לגרום נזק למידע המצוי בתאים הסמוכים בזיכרון. נזק זה עלול להתבטא בנתונים שגויים ואף בקריסה של המערכת.
| מבני נתונים | ||
|---|---|---|
| מבנים מופשטים | רשימה • מחסנית • קבוצה • רב קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות | |
| מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ | |
| גרפים ועצים | ערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R • Trie • טריי X מהיר • טריי y מהיר• עץ WAVL | |
| הסתברותיים | מסנן בלום | |
קישורים חיצוניים
