Yatta! – I did it

הבלוג הזה היה פחות פעיל בשנים האחרונות, כי סיבות.

אבל כן קרו לי דברים מעניינים פה ושם. אז בקרוב אני אפרסם כאן פוסטים על בסגנון ״ככה היה וזה מה שקרה״.

בקיצור, לשחזר את ההיסטוריה, אבל בקטע טוב. stay tuned.

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

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

אז זהו, שלא.

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

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 גבוה יותר (בין השאר). מה שנקרא, אנחנו על המפה. אה כן, הנה הלינק לרשימת המאמרים המלאה באתר של ניר שביט.

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