דף הבית > כללי > תור מקבילי – Concurrent Queue

תור מקבילי – Concurrent Queue

רוב המתכנתים מכירים מבני נתונים בסיסיים, כמו מערך, רשימה מקושרת, וגם תור ומחסנית. הבעיה מתחילה כשרציתי למקבל תור. כלומר, ליצור מחלקה עם התכונות של תור, לצד העובדה שיכולים לגשת אליה במספר ת'רדים במקביל (אני לא מת על התרגום ל"חוטים", ומי שרוצה לתת תרגום אחר – תעירו חופשי).

נשמע פשוט, נכון? כולה לעטוף תור קיים ומוכח בנעילה קטנה, ויש לך תור מקבילי.

אז זהו, שלא.

כדי להמחיש את העניין, הנה המימוש הנאיבי ("כולה לעטוף תור קיים" וכו' וגו') של תור מקבילי:

public class NaiveConcurrentQueue<T>
{
  private Queue<T> queue = new Queue<T>();

  public void Enqueue(T item)
  {
    lock (queue)
    {
      queue.Enqueue(item);
    }
  }

  public T Dequeue()
  {
    lock (queue)
    {
      return queue.Dequeue();
    }
  }
}

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

נעילה בקוד, או lock, זה סוג של מאקרו ברמת הקומפיילר, שמאפשר לנו, המתכנתים העצלנים, לכתוב קוד שאמור לרוץ ע"י ת'רד אחד בכל פעם. למה מאקרו? כי פיסת הקוד הבאה:

lock (x)
{
  DoSomething();
}

למעשה הופכת להיות הקוד הבא:

System.Object obj = (System.Object)x;
System.Threading.Monitor.Enter(obj);
try
{
  DoSomething();
}
finally
{
  System.Threading.Monitor.Exit(obj);
}

נו, אז? סה"כ עטיפה נוחה ל Monitor.Enter ול Monitor.Exit.

אז בואו נקרא עוד קצת על Monitor.Enter. מתוך MSDN, כל עוד מדובר במערכת Win32, הוא ממופה לפקודה EnterCriticalSection. יופי, בואו נקרא עוד קצת על EnterCriticalSection, שוב מתוך MSDN. נתמקד במשפט אחד:

There is no guarantee about the order in which waiting threads will acquire ownership of the critical section

הממממם. מעניין. אז בואו נסתכל רגע על המצב הבא:

בזמן T0, הת'רד הנוכחי נועל משאב X, ומבצע משימה שלוקחת 5 שניות.

אחרי 2 שניות (נקרא לזה זמן T2), ת'רד נוסף, שנקרא לו מנדל, גם רוצה לנעול את משאב X, ולבצע משימה קטנטונת, שלוקחת 0.01 שניה. מכיוון ש X כבר נעול, מנדל מחכה.

שניה אחרי T2 (נקרא לזה זמן T3), ת'רד נוסף, שנקרא לו צביקי, גם רוצה לנעול את משאב X, ולבצע משימה קטנטונת, שלוקחת 0.01 שניה. שוב, מכיוון ש X כבר נעול, גם צביקי מחכה.

שניה אחרי T3 (נקרא לזה זמן T4), ת'רד נוסף, שנקרא לו פושקש, גם רוצה לנעול את משאב X, ולבצע משימה קטנטונת, שלוקחת 0.01 שניה. ושוב, מכיוון ש X עדיין נעול, גם פושקש מחכה.

עכשיו, סוף סוף עברו 5 שניות מאז T0, ומשאב X משתחרר. יש כרגע שלושה ת'רדים שממתינים ל X: מנדל, צביקי ופושקש. לפי התיעוד למעלה, סדר הביצוע של הת'רדים הוא לא בהכרח סדר ההגעה שלהם. כלומר, זה יכול להיות מנדל-צביקי-פושקש, וזה יכול גם להיות מנדל-פושקש-צביקי, וכל קומבינציה אחרת. בדקתי את העניין, וכתבתי תוכנית קטנה שממחישה את זה. ברוב ההרצות הסדר נשמר. בחלק מההרצות הסדר השתנה. זה מספיק כדי להמחיש שהסדר לא בהכרח נשמר.

בעיה. כי בדיוק רציתי תור, כלומר מבנה נתונים שישמור גם על סדר ההגעה של הת'רדים. מעין message queue.

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

כמה מיילים לעולם, ומישהו הציע להסתכל על PLinq, שיש שם מימוש כזה. אבל אני לא יכול להסתכן בספריה כמו Plinq היא עדיין CTP, ועוד לא יצאה לאור באופן רשמי. פעם נכוויתי מספריה לא בשלה (Atlas, למי שזוכר), ומאז כבר למדתי את הלקח.

גוגל! גוגל יעזור לי. רק צריך לבקש, ובעיקר לדעת מה לבקש. אז גיגלתי lock free queue, וחיפשתי גם ב stackoverflow, ומצאתי עולם ומלואו. עולם שלם של אלגוריתמים ומבני נתונים שמיועדים לסביבה שהיא Multi-Threaded ושאין בהם נעילות רגילות, אלא לכל היותר Interlock. אז גיגלתי וריאציות של lock free queue, והנה כמה דברים שמצאתי:

קודם כל, כבר עשו את זה. בכנס שנקרא בקיצור PODC96 ובאריכות Fifteenth ACM Symposium on Principles of Distributed Computing, מתואר מבנה נתונים שמספק את דרישת FIFO, במאמר בעל השם הקצרצר: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. כותבי המאמר, מייקל וסקוט, או בקיצור MS, מתארים איך אפשר להשתמש בטכניקות קלות יותר מאשר נעילות (כמו CAS, שבדוט נט זה Interlocked.CompareExchange) כדי לקבל את התוצאה הרצויה. התור (או הרעיון המרכזי שלו) נקרא בהרבה מקומות אחרים MS-Queue. לשם שינוי ה MS מציין את שמות המשפחה מייקל וסקוט, ולא חברת תוכנה ענקית.

יש כבר מימוש לזה בשפות רבות, וגם בדוט נט (C# ליתר דיוק). הבחורצ'יק הזה נותן לנו מימוש מלא.

שני ישראלים, אחד בשם ניר שביט ואחת בשם Edya Ladan Mozes (ואיך מתרגמים את זה לעברית?) מציגים במאמר בשם An Optimistic Approach to Lock-Free FIFO Queues שאפשר לייעל את האלגוריתם המקורי של MS-Queue ולהגיע ל throughput גבוה יותר (בין השאר). מה שנקרא, אנחנו על המפה. אה כן, הנה הלינק לרשימת המאמרים המלאה באתר של ניר שביט.

מה שנקרא, החכמנו.

Edya Ladan Mozes

קטגוריות:כללי תגיות:
  1. 6 אוגוסט, 2009 מתוך 21:12 | #1

    הבעיה שאתה מתאר לא בלעדית ל-lock'ים. אותו דבר יכול לקרות למשל כשאתה עובד עם wait handle'ים למשל. הבעיה התיאורתית, היא שנניח ויש לך autoResetEvent ות'רד שמחכה לקבל עליו signal. אבל יתכן שבכל פעם שעושים set ל-event יגיע ת'רד אחר "שיגנוב" לו את ה-signal ויגרום ל-reset של ה-event. כך שאותו ת'רד שחיכה כל הזמן אף פעם לא מצליח לקבל signal

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

  2. 9 אוגוסט, 2009 מתוך 06:05 | #2

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

  3. 16 ינואר, 2010 מתוך 17:07 | #3

    בתרחישים מהסוג הזה לא בהכרח חייבים להשתמש בתור סטנדרטי, אלא במקום זה אפשר גם לבדוק מימושים אלטרנטיבים שפותרים את בעיית ה-single producer/consumer בצורה יעילה יותר. למשל: http://www.bluebytesoftware.com/blog/2009/10/05/FastSynchronizationBetweenASingleProducerAndSingleConsumer.aspx

    בפוסט יש אנלוגיה די מבלבלת לשימוש במבנה הנתונים "תור" (שמירת נתונים במבנה FIFO), לבין הבטחת סדר נעילות של ת'רדים על אובייקט מסויים. בהקשר של fairness, לדעתי דוגמה טובה יותר תהיה ההבדל בין מימוש SpinLock "רגיל" לצד מימוש של Queue Lock כלשהו, למשל MCS Lock (הראשון גורם לכך שברגע שהנעילה משתחררת כל הת'רדים "נלחמים" על תפיסת הנעילה, בעוד שהשני דואג לכך שרק ת'רד מסויים יזכה לראות שהנעילה השתחררה והוא בוודאות יהיה זה שיזכה לבצע את הנעילה)

  1. אין הפניות עדיין.

Quantcast