Couldn't load preferences. Check your connection and try again.
החלפת מצב תפריט אישי
לא בחשבון
כתובת ה־IP שלך תהיה גלויה לציבור אם תעשה עריכות כלשהן.
חוצץ מעגלי
מתוך ויקיפדיה, האנציקלופדיה החופשית
פעולות נוספות
קובץ:Circular buffer.svgטבעת הממחישה, באופן רעיוני, חוצץ מעגלי. המחשה זו מראה שלחוצץ אין סוף אמיתי ושאפשר לעבור עליו שוב ושוב. עם זאת, מכיוון שהזיכרון אינו מוקצה פיזית בצורת טבעת, בדרך כלל משתמשים בייצוג ליניארי, כפי שיוצג להלן.
במדעי המחשב, חוצץ מעגלי, תור מעגלי, חוצץ מחזורי או חוצץ טבעתי (באנגלית: <phonos ipa="" lang="he" text="<span dir="auto">circular buffer</span>" wikibase="no entity" file="">circular buffer</phonos>Ⓘ) הוא מבנה נתונים המשתמש בחוצץ יחיד בגודל קבוע הפועל כאילו קצותיו מחוברים זה לזה. מבנה זה מתאים במיוחד לטיפול בזרמי נתונים רציפים.[1] גרסאות מוקדמות של חוצצים מעגליים יושמו אף ישירות בחומרה.[2][3]
קובץ:Circular Buffer Animation.gifחוצץ מעגלי של מקלדת המכיל 24 בתים. כאשר מצביע הכתיבה מתקרב למצביע הקריאה — מכיוון שהמיקרו-מעבד אינו מגיב — החוצץ מפסיק לרשום הקשות מקלדת. במחשבים מסוימים יושמע צפצוף כדי להתריע על מצב זה.
חוצץ מעגלי מתחיל במצב ריק והקיבולת שלו קבועה. בתרשים להלן מוצג חוצץ המסוגל להכיל 7 איברים:
אם מוסרים שני איברים, שני הערכים הוותיקים ביותר בחוצץ המעגלי ימחקו. חוצצים מעגליים פועלים לפי עיקרון FIFO (נכנס ראשון, יוצא ראשון). בדוגמה זו, הערכים 1 ו-2 נכנסו ראשונים לחוצץ, ולכן הם יוסרו ראשונים, וכך יישאר הערך 3 בחוצץ.
מאפיין מרכזי של חוצץ מעגלי הוא שכאשר הוא מתמלא ומתבצעת כתיבה נוספת, הנתונים הוותיקים ביותר נדרסים. בדוגמה הנוכחית מתווספים שני איברים נוספים – A ו־B – אשר מחליפים את הערכים 3 ו־4:
לחלופין, השגרות המנהלות את החוצץ יכולות למנוע דריסה של נתונים, ובמקום זאת להחזיר שגיאה או לזרוק חריגה. ההחלטה אם נתונים יידרסו או לא תלויה בסמנטיקה של שגרות ניהול החוצץ או ביישום המשתמש בחוצץ המעגלי.
לבסוף, אם בשלב זה מוסרים שני איברים, לא A ו-B הם שיוסרו, אלא 5 ו-6, משום שהם כעת האיברים הוותיקים ביותר. כתוצאה מכך, החוצץ יכיל:
היתרון המרכזי של חוצץ מעגלי הוא שאין צורך להזיז או לסדר מחדש את האיברים שבו כאשר אחד מהם נצרך. לעומת זאת, בחוצץ שאינו מעגלי יש להזיז את כל האיברים הנותרים לאחר הסרת איבר. לכן, חוצץ מעגלי מתאים במיוחד למימוש FIFO (נכנס ראשון, יוצא ראשון), בעוד שחוצץ רגיל שאינו מעגלי מתאים יותר להתנהגות LIFO (נכנס אחרון, יוצא ראשון).
שימוש בחוצץ מעגלי (Circular buffering) הוא אסטרטגיית מימוש יעילה לתור בעל גודל מרבי קבוע. כאשר לתור יש קיבולת מוגדרת מראש, חוצץ מעגלי הוא פתרון אידיאלי, משום שכל פעולות התור מתבצעות בזמן קבוע. עם זאת, הרחבת חוצץ מעגלי דורשת הקצאה מחדש של זיכרון והזזת נתונים, פעולה יקרה יחסית. עבור תורים שצריכים לגדול באופן דינמי ללא מגבלה קבועה, ייתכן שמימוש באמצעות רשימה מקושרת יהיה עדיף.
במצבים מסוימים, דריסה של נתונים בחוצץ מעגלי היא תכונה רצויה, למשל ביישומי מולטימדיה. כאשר החוצץ משמש כחוצץ חסום בבעיית היצרן–צרכן, ייתכן שעדיף שהיצרן (כגון מחולל שמע) ידרוס נתונים ישנים אם הצרכן (כגון כרטיס הקול) אינו מצליח לעמוד בקצב באופן זמני. בנוסף, משפחת אלגוריתמי הדחיסה הלא־מאבדת מידע LZ77 פועלת בהנחה שמחרוזות שנראו לאחרונה בזרם הנתונים צפויות להופיע שוב בקרוב. לכן, מימושים של אלגוריתמים אלה שומרים את הנתונים העדכניים ביותר בתוך חוצץ מעגלי.
בהתחלה, האינדקסים start ו-end מוגדרים ל-0. פעולת כתיבה בחוצץ המעגלי שומרת איבר במיקום האינדקס end, ולאחר מכן מגדילה את end למיקום הבא בחוצץ. פעולת קריאה מחזירה איבר ממיקום האינדקס start ולאחר מכן מגדילה את start למיקום הבא.
שימוש רק באינדקסים start ו-end אינו מספיק כדי להבחין בין מצב של חוצץ מלא לבין חוצץ ריק תוך שימוש בכל איברי החוצץ.[1] פתרון אחד הוא להגביל את הגודל המרבי של החוצץ לשימוש של Length - 1 בלבד. במקרה כזה, החוצץ נחשב ריק כאשר start שווה ל-end, ומלא כאשר מספר האיברים בשימוש מגיע ל־Length - 1. פתרון נוסף הוא להשתמש במשתנה שלם נוסף count, שמוגדל בעת כתיבה ומוקטן בעת קריאה. בדיקה האם החוצץ ריק מתבצעת על ידי בדיקה האם count == 0, ובדיקה האם החוצץ מלא מתבצעת על ידי בדיקה האם count == Length.[3]
קטע הקוד הבא בשפת C מציג מימוש יחד עם בדיקה מינימלית. הפונקציה put() מוסיפה איבר לחוצץ, והפונקציה get() מחזירה איבר מהחוצץ. שתי הפונקציות מטפלות נכון בקיבולת החוצץ:
#include<stdio.h>enum{N=10};// size of circular bufferintbuffer[N];// note: only (N - 1) elements can be stored at a given timeintwriteIndx=0;intreadIndx=0;intput(intitem){if((writeIndx+1)%N==readIndx){// buffer is full, avoid overflowreturn0;}buffer[writeIndx]=item;writeIndx=(writeIndx+1)%N;return1;}intget(int*value){if(readIndx==writeIndx){// buffer is emptyreturn0;}*value=buffer[readIndx];readIndx=(readIndx+1)%N;return1;}intmain(){// test circular bufferintvalue=1001;while(put(value++));while(get(&value))printf("read %d\n",value);return0;}
ניתן לבצע אופטימיזציה למימוש חוצץ מעגלי על ידי מיפוי (אנ') הזיכרון הבסיסי של החוצץ לשני אזורים רציפים בזיכרון הווירטואלי (אורך החוצץ חייב להיות כפולה של גודל הדף במערכת).[1] גישה כזו מאפשרת קריאה וכתיבה בחוצץ ביעילות רבה יותר באמצעות גישה ישירה לזיכרון. כל גישה החורגת מסוף האזור הראשון בזיכרון הווירטואלי תמשיך אוטומטית מכתובת ההתחלה של החוצץ בזיכרון. כאשר הזזת הקריאה נכנסת לאזור השני בזיכרון הווירטואלי, גם הזזות הקריאה וגם הכתיבה מוקטנות באורך של הזיכרון הבסיסי של החוצץ.
