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

[עוד אחד]

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

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

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

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

[שניצל]

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

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

[Ghosthunter]

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

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

[שניצל]

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

[עוד אחד]

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

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

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

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

[שניצל]

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

[עוד אחד]

בעברית זה קל.

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

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

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

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

נ.ב.

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

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

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

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

[Ghosthunter]

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

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

[עוד אחד]

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

[שניצל]

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

[עוד אחד]

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

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

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

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

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

[עוד אחד]

נפתר.

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

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

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

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

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