עבור לתוכן

תכנות תור דו צדדי ב multi thread

Featured Replies

פורסם

אני צריך לממש תור דו צדדי ב multi thread.

האם יש פתרון לנעילות, שהוא טוב יותר מהנעילה הטריוויאלית ? (כל פעולה על התור נחשבת לקטע קוד קריטי)

בינתיים פסלתי נעילה לכל צד, + נעילה כללית, + שימוש ב counter.

האם מישהו מכיר פתרון textbook לבעיה הזו ?

פורסם

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

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

פורסם

אתה יכול להסביר קצת יותר את הבעיה שלך, ומה זה תור דו צדדי?

איך תור יכול להיות לא דו צדדי (אתה מכניס לצד אחד ומוריד מהשני)?

פורסם

נראה לי שהכוונה היא שאפשר גם להכניס וגם להוציא משני הצדדים (מה שנקרא deque - double ended queue).

פורסם
  • מחבר

ממומש ב C, כרשימה מקושרת דו צדדית.

אי אפשר עם 2 נעילות (אחד לכל צד)

אם בא PUSH מצד ימין, אז רצף POP מצד שמאל יכול להתבצע עד שהתור מתרוקן.

אכן מדובר על DEQ.

פורסם

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

פורסם
  • מחבר

בעברית זה קל.

איך אני מגדיר במחשב מהי "הפעולה האחרונה". זו הבעיה.

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

ורצף של POP בשלב הזה, יכול להוציא לי את כל אברי הרשימה.

כשהPUSH של הצד השני יחזור לפעולה, הוא יקבל segmentation fault.

נ.ב.

לפני שאתם אומרים - counter

זה לא עבד לי. כי יכול להיות שבין הבדיקה של הcounter לפעולה המתאימה שבעקבות הבדיקה, התהליך מתחלף...

אולי עשיתי משהו לא בסדר ?

זה מקרה דיי כללי... אף אחד לא מכיר פתרון מדף לבעיה הזו ? google לא עזר.

פורסם

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

הבדיקה האם אתה מוציא את האיבר הזה או לא תתבצע בתחילת התהליך והיא תנעל את 2 הצדדים, אבל אחרי הבדיקה הזו אתה יכול לשחרר את הMUTEX ולעבוד בלי הפרעה.

פורסם
  • מחבר

ומה יקרה לאיבר האמצעי הזה כשאדחוף 100 מצד אחד ואמשוך 100 מצד שני ? הוא כבר לא יהיה באמצע.

פורסם

בבירור הכוונה היא לא בדיוק באמצע, פשוט לא איבר שנמצא באחד הקצוות.

פורסם
  • מחבר

אוקיי, הבנתי עכשיו.

הבעיה היא שזה קצת אמורפי. מה האיבר הזה ? כל איבר שאינו בקצוות ? (ואז כל 2 פעולות עוקבות של POP בצד מסויים יתחילו לנעול את הכל...)

קיוויתי שאולי מישהו מכיר איזה פתרון סטנדרטי של השטות הזו.

אני אשבור את הראש עם הנעילות עד שנסדר את זה.

תודה בכל מקרה.

פורסם
  • מחבר

נפתר.

מכיוון שאני חסיד גדול של חלוקת הידע באינטרנט -

הפתרון הוא 2 mutexים, אחד לכל צד,

+ מונה, שאם מספר האיברים <= 3 ידאג לנעול גם את הצד השני.

+ mutex שנועל את כל הקטע של הפעלת הנעילות (למניעת deadlock)

תודה בכל זאת למי שניסה לעזור.

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים