ארכיון

רשומות עם התג ‘Multi-Threading’

Safe Value Pattern

23 יוני, 2010 רון קליין אין תגובות

בפוסט הזה: קוד קצר ולעניין של משתנה שקוראים אותו ומעדכנים אותו בסביבה שהיא Multi-Threaded.

כידוע, כדי להגן על המשתנה מפני corruption אנחנו צריכים נעילה (כן, אני יודע, יש גם את Interlock, אבל זה לא העניין פה, אל תטרידו אותי עם עובדות…)

אז במקום להצהיר בכל פעם על משתנה ועל האובייקט שנועל אותו, הנה Mini-Pattern שעושה את העבודה:

הגירסה הפשוטה

מנעול פשוט, עבודה עם lock:

namespace Pepperoni.Lib
{
  public class SafeValue<T>
  {
    private readonly object locker = new object();
    private T innerValue;

    public SafeValue()
    {
    }

    public SafeValue(T initialValue)
    {
      innerValue = initialValue;
    }

    public T Value
    {
      get
      {
        lock (locker)
        {
          return innerValue;
        }
      }
      set
      {
        lock (locker)
        {
          innerValue = value;
        }
      }
    }
  }
}

אין הרבה מה לכתוב ב code-review, בסה"כ גם ב getter וגם ב setter נועלים אובייקט פנימי ורק אז מחזירים את הערך (ב getter) או מעדכנים את הערך (ב setter). קצר, פשוט, קריא, עובד (נראה לי שאני מאמץ את זה בראשי תיבות: קפק"ע! :-P ).

אלטרנטיבה – הרבה קריאות, מעט עדכונים

אם אנחנו יודעים שיש הרבה יותר קריאות של הערך לעומת עדכונים של הערך, כלומר הרבה יותר שימושים ב getter מאשר ב setter, אז נוכל לייעל את העבודה אם נשתמש באובייקט ReaderWriterLockSlim (לקריאה נוספת – MSDN). הנה הקוד:

using System.Threading;

namespace Pepperoni.Lib
{
  public class SafeValueSeldomWrites<T>
  {
    private T innerValue;
    private readonly ReaderWriterLockSlim locker = new ReaderWriterLockSlim();
   
    public SafeValueSeldomWrites()
    {
    }

    public SafeValueSeldomWrites(T initialValue)
    {
      innerValue = initialValue;
    }

    public T Value
    {
      get
      {
        locker.EnterReadLock();
        T result = innerValue;
        locker.ExitReadLock();
        return result;
      }
      set
      {
        locker.EnterWriteLock();
        innerValue = value;
        locker.ExitWriteLock();
      }
    }
  }
}

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

עוד כמה מילים

אם רוצים, אז אפשר לעשות כאן אבסטרקציה לשני המימושים (ע"י interface או base-class). אבל זה נראה לי מיותר, כי בד"כ יודעים כבר בזמן הפיתוח עצמו באיזה מימוש להשתמש.

עניין נוסף: במקרים מסויימים אפשר לעבוד עם Interlock, שמאפשר קריאה/כתיבה בסביבה שהיא Multi-Threaded, ללא שימוש ב lock הסטנדרטי. מומלץ לגגל או לקרוא ב MSDN.

אפשר להוריד מכאן את הקוד, למי ש copy-paste גדול עליו :-)
תכנות נעים!

קטגוריות:תכנות תגיות:, ,

Startable – State Machine part 2

16 אפריל, 2010 רון קליין אין תגובות

בפוסט הזה אני אמשיך ב state machine שהצגתי כבר קודם, והפעם אני אצור abstract class שיכול להיות שימושי כאשר רוצים רכיב שרץ ברקע (נניח, רכיב שמציג מניות, רכיב שמאזין לבקשות TCP וכד').
מטבע הדברים, רכיב שכזה רץ על thread משלו, והקריאה למתודת ה Start שלו, ואח"כ גם ל Stop – יכולות להגיע מ threadים שונים, ולכן נצטרך לדאוג לנעילות.

בפשטות

נתחיל מהמקרה הפשוט יותר, בלי התייחסות לענייני multi-threading.
בואו נקפוץ פנימה לקוד ונסביר מה קורה:

public abstract class StartableBase
{
    private readonly IStartableStateMachine innerStateMachine;

    protected StartableBase()
        : this(StartableStatus.Stopped)
    {
    }

    protected StartableBase(StartableStatus initialStatus)
        : this(new StartableStateMachine(initialStatus))
    {
    }

    protected StartableBase(IStartableStateMachine innerStateMachine)
    {
        if (innerStateMachine == null)
            throw new ArgumentNullException("innerStateMachine");
        this.innerStateMachine = innerStateMachine;
        innerStateMachine.OnStart += OnStart;
        innerStateMachine.OnStop += OnStop;
    }

    protected abstract void OnStart();
    protected abstract void OnStop();

    public void Start()
    {
        innerStateMachine.Start();
    }

    public void Stop()
    {
        innerStateMachine.Stop();
    }

    public StartableStatus Status
    {
        get { return innerStateMachine.Status; }
    }
}

סקירה קצרה:
יש כאן abstract class, כלומר הכוונה היא שיהיה class שיורש מה class שלנו.
מי שמכיר אותי כבר יודע שאני לא מת על ירושה בקוד, אבל כאן זה מתבקש, כי זה באמת מעודד שימוש חוזר בקוד, ומצד שני די קל להבין מה הולך פה.
בכל מקרה, בקלות אפשר לעקוף ירושה ע"י composition, אבל לא נרחיב על זה כאן. בשביל זה יש גוגל.
בקיצור, ה class הזה חושף לעולם שתי מתודות: Start ו Stop.
בנוסף, ב class יש קונסטרקטורים שבסופו של דבר נסמכים על state machine חיצוני, שבו נמצא כל הקוד למעברים בין המצבים.
התפקיד של ה class הוא להעביר את הקריאות של ה Start וה Stop החיצוניות שלו אל ה state machine הנ"ל. ההתנהגות של ה state machine, עם ה events שלו, מתגלגלת ל class היורש, באמצעות מתודות אבסטרקטיות.
במילים אחרות, כל התפקיד של ה class הזה הוא לעטוף את ההתנהגות של ה state machine ולהפוך אותה ל abstract class. סבבצ'יק.

ניצור class חדש, שיורש מה StartableBase הנ"ל, כדי לקבל את התחושה.
נקרא לו MyCoolService. כי אנחנו גיקים שנותנים דוגמאות של קוּלים. זה למעשה המקסימום coolness שגיק יכול להיות, וזה רק הופך אותו ליותר גיק.
ככה זה, עולם אכזר.
נו, בכל אופן, הקוד:

public class MyCoolService : StartableBase
{
    protected override void OnStart()
    {
        Console.WriteLine("hey, now I should start working!");
    }

    protected override void OnStop()
    {
        Console.WriteLine("ok, now I should stop.");
    }
}

אכן, קוּל למהדרין. ככה משתמשים:

static void Main(string[] args)
{
    var myCoolService = new MyCoolService();
    Console.WriteLine("myCoolService.Status = " + myCoolService.Status);
    myCoolService.Start();
    Console.WriteLine("myCoolService.Status = " + myCoolService.Status);
    myCoolService.Stop();
    Console.WriteLine("myCoolService.Status = " + myCoolService.Status);
}

וזו התוצאה:

myCoolService.Status = Stopped
hey, now I should start working!
myCoolService.Status = Started
ok, now I should stop.
myCoolService.Status = Stopped

טוב, זה היה רק כדי לקבל תחושה, זה לא באמת קול.

Threads Ahoy!

זה מתחיל להיות מעניין כשעובדים עם יותר מ thread אחד.
אז גם כאן אולי כדאי שנתחיל מ abstract class, שמתבסס על הקודם (בירושה! סלח לי אבי כי חטאתי!), ונקפוץ לקוד:

/// <summary>
/// Marks the implementation as a thread-safe one.
/// Nothing more than that.
/// </summary>
public interface IThreadSafeStateMachine : IStartableStateMachine
{
}

public abstract class ThreadSafeStartableBase : StartableBase
{
    protected ThreadSafeStartableBase() :
        this(StartableStatus.Stopped)
    {
    }

    protected ThreadSafeStartableBase(StartableStatus initialStatus) :
        this(new StartableStateMachineInterlock(initialStatus))
    {
    }

    protected ThreadSafeStartableBase(IThreadSafeStateMachine innerStateMachine)
        : base(innerStateMachine)
    {
    }
}

סה"כ מעטפת ל abstract class שכבר היה לנו, עם תוספות קלות.
כדי להשתמש בכל הסיפור הזה, צריך רק לרשת ולהתחיל לעבוד עם קצת נעילות.
בדוגמה הבאה, יש לנו class שבכל X שניות (או כל TimeSpan שנקבע) מבצע פעולה מסויימת, נניח משהו כמו פינג.
בנוסף, יש לנו Counter שמונה את הפינגים שבוצעו. הקוד:

public class MyThreadSafeService : ThreadSafeStartableBase, IDisposable
{
    private readonly TimeSpan period;
    private readonly object syncLock;
    private readonly Timer timer;
    private int counter = 0;

    public MyThreadSafeService(TimeSpan period)
        : this(period, new object())
    {
    }

    private MyThreadSafeService(TimeSpan period, object syncLock)
        : base(new StartableStateMachineSimpleLock(StartableStatus.Stopped, syncLock))
    {
        this.period = period;
        this.syncLock = syncLock;
        timer = new Timer(MyTimerCallback);
    }

    private void MyTimerCallback(object state)
    {
        int current;
        lock (syncLock)
        {
            counter++;
            current = counter;
        }
        Console.WriteLine("Ping! so far {0} pings", current);
    }

    public int Counter
    {
        get
        {
            lock (syncLock)
            {
                return counter;
            }
        }
    }

    protected override void OnStart()
    {
        counter = 0;
        timer.Change(TimeSpan.Zero, period);
    }

    protected override void OnStop()
    {
        timer.Change(TimeSpan.FromMilliseconds(-1), TimeSpan.FromMilliseconds(-1));
    }

    public void Dispose()
    {
        Stop();
        timer.Dispose();
    }
}

הקריאה:

static void Main(string[] args)
{
    var period = new TimeSpan(0, 0, 1); // ping every second
    var myThreadSafeService = new MyThreadSafeService(period);
    myThreadSafeService.Start();
    Console.ReadLine();
    myThreadSafeService.Stop();
    Console.WriteLine("Counter = " + myThreadSafeService.Counter);
    myThreadSafeService.Dispose();
}

והתוצאה (אחרי בערך 5 שניות):

======== Thread Safe Example ===========
Ping! so far 1 pings
Ping! so far 2 pings
Ping! so far 3 pings
Ping! so far 4 pings
Ping! so far 5 pings

Counter = 5
=========== End of Example =============

press –enter– to quit

וואלה עובד.

סיכום

מי שכותב מדי פעם רכיב שפועל ברקע, כנראה מצא את עצמו חוזר על קוד התשתית של "להתחיל משהו, לדאוג לנעילות, לסנכרן סטטוס" וכו'.
בשני הפוסטים האלה הראיתי איך אפשר לכתוב base class שמעודד שימוש חוזר בקוד מהסוג הזה.
היתרון העיקרי הוא שאפשר להפריד בין המנגנון הפנימי של ה state machine וגם, באופן חלקי, לנעילות המתבקשות.
מצד שני, הירושה יכולה לגרום לכאב ראש כשנכנסים לדיבאג (או כשסתם מנסים להבין את זה).
בנוסף, יש לנו לא מעט קבצים לתחזק, רק כדי לכתוב קוד "נכון".
מה המסקנה? לא תמיד יש מסקנה חד משמעית, צריך לנסות ולראות אם זה מתאים לכם.
הערות והארות, או סתם תגובות יתקבלו בברכה. ובכלל, מי שקרא עד הלום – סחתן, כה לחי וישר כוח :-)

אפשר להוריד את כל הקוד, כמובן.

קטגוריות:תכנות תגיות:, ,

Locking by Decorator

9 ינואר, 2010 רון קליין אין תגובות

בפוסט הזה:

  • הקדמה
  • הגדרת החוזה
  • מימוש רגיל ללא נעילות
  • נעילה באמצעות Decorator
  • יישום

הקדמה

לא מזמן כתבתי פוסט שמציע להפריד בין לוגיקה של רכיב ללוגיקה של נעילה ע"י אבסטרקציה. בפוסט הזה אני מציע דרך נוספת לעטוף רכיב בנעילה, תוך שימוש ב Design Pattern שנקרא Decorator. המטרה היא שוב להפריד בין לוגיקת רכיב ללוגיקת נעילה, כדי ליצור קוד נקי יותר וגמיש יותר לפי צרכי הפרויקט.

הגדרת החוזה

כדי לא להסתבך יותר מדי, אני אמשיך את הרעיון מהפוסט ההוא, ולכן דוגמת ה Counter תלווה אותנו גם כאן. נמיר את ה Counter שלנו מ class ל interface באופן הבא:

public interface ICounter
{
    void Hit();
    int Current { get; }
}

מימוש רגיל ללא נעילות

המימוש הרגיל והמיידי ל interface הנ"ל:

public class Counter : ICounter
{
    private int counter = 0;

    public void Hit()
    {
        ++counter;
    }

    public int Current
    {
        get { return counter; }
    }        
}

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

נעילה באמצעות Decorator

קצת הקדמה: מה זה Decorator?

אז ככה: בגדול, Decorator זה Design Pattern שמתייחס ל interface-ים ולהוספת פונקציונליות בזמן ריצה, לא על ידי ירושה. אפשר לקרוא עוד בויקיפדיה. במקרה שלפנינו, נוסיף פונקציונליות של נעילה על המימוש של ICounter. או, בניסוח אחר: "נקשט" את הפונקציונליות של Counter בנעילה, אבל נשמור על ה interface. כלומר החוזה נשמר אבל נקבל עוד משהו במימושים.

ניגש לקוד עצמו של ה Decorator שלנו:

public class CounterLockDecorator : ICounter
{
    private readonly ICounter core;
    private readonly object syncObject = new object();

    public CounterLockDecorator(ICounter coreCounter)
    {
        if (null == coreCounter)
            throw new ArgumentNullException("coreCounter");

        core = coreCounter;
    }

    public void Hit()
    {
        lock (syncObject)
        {
            core.Hit();
        }
    }

    public int Current
    {
        get
        {
            lock (syncObject)
            {
                return core.Current;
            }
        }
    }
}

כפי שניתן לראות, ה Decorator מממש בעצמו את החוזה ICounter. אבל הוא לא עושה את כל העבודה – הוא מצפה לקבל בקונסטרקטור שלו מימוש קיים ל ICounter ו"מגלגל" אליו את הקריאות לפי הצורך. כך, למשל, במימוש של המתודה Hit: ה Decorator רק עוטף בנעילה את הקריאה למתודת ה Hit של המימוש הקיים שהוא מחזיק.

יישום

הקריאה ל Counter הרגיל, ללא נעילות, יכולה להתבצע כך:

ICounter myCounter = new Counter();

ואם רוצים את הפונקציונליות של הנעילות, נוכל לקבל ICounter באופן הבא:

ICounter myCounter = new CounterLockDecorator(new Counter());

סיכום

גם בפוסט הזה הראיתי כיצד ניתן להפריד בין הלוגיקה של הרכיב לבין הנעילות שלו. יש להפרדה הזו גם יתרונות וגם חסרונות. היתרונות העיקריים הם קוד גמיש וטסטבילי (כלומר כזה שניתן לבדיקות בצורה קלה). גם הקוד של הרכיב עצמו קריא וברור. עם זאת, יש אי אילו חסרונות להפרדה הזו: פתאום יש שלושה קבצים לתחזק (החוזה, המימוש הרגיל וה decorator) במקום אחד, והקריאה הופכת להיות קצת יותר מורכבת (אפשר לפתור את זה עם factory). יש פתרון נוסף לעניין הזה, והוא שימוש ב dynamic proxy. אם יהיה לי זמן אני ארחיב על זה, אבל הרעיון הכללי הוא ליצור את ה Decorator בזמן ריצה באמצעות הכלים הסטנדרטיים של דוט נט כמו CodeDOM או באמצעות פריימוורק שהוא קצת יותר high level כמו Dynamic Proxy של Castle.

אגב, אפשר להשתמש בנעילה האבסטרקטית שהצעתי בפוסט ההוא בתוך ה Decorator וכך "להרוויח" עוד קצת גמישות בבחירת מנגנון הנעילה עצמו, אבל זה כבר עניין אחר :-)

כל הקוד נמצא כאן, ושיהיה קישוט נעים!

קטגוריות:תכנות תגיות:, , ,

From lock to abstract locker

6 ינואר, 2010 רון קליין 2 תגובות

כמו שמשתמע מהכותרת של הפוסט הזה, לא חייבים לנעול דווקא עם lock (כלומר נעילה שמבוססת על Monitor).
יש נעילות נוספות (למשל, Spin-Lock), ולכן אני מציע כאן אבסטרקציה לנעילה.

במילים אחרות, במקום הקוד הזה:

lock(locker)
{
    // do something
}

אני מציע משהו כזה:

locker.Enter();
// do something
locker.Exit();

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

using(locker.EnterLock())
{
    // do something
}

אז בפוסט הזה יש:

  • קצת אבסטרקציה
  • קצת מוטיבציה
  • קוד בסיס
  • 2 ירושות
  • וקצת אינטגרציה :-)

קצת מוטיבציה

מתי זה שימושי?
-בעיקר אם נרצה לכתוב class שיכול להיות שימושי גם בסביבה שהיא single-threaded וגם בסביבה שהיא multi-threaded.

קצת קוד בסיס

ניגש לקוד עצמו. הנה ה base class עם תוספת פנימית בשביל ה using הנכסף:

using System;

public abstract class LockerBase
{
    public abstract void Enter();
    public abstract void Exit();

    public class DisposableLocker : IDisposable
    {
        private readonly LockerBase locker;

        public DisposableLocker(LockerBase locker)
        {
            this.locker = locker;
        }

        public void Dispose()
        {
            locker.Exit();
        }
    }

    public DisposableLocker EnterLock()
    {
        Enter();
        return new DisposableLocker(this);
    }
}

המתודות Enter ו Exit הן אבסטרקטיות, וכל מי שירצה לרשת מה base class הזה יצטרך לממש אותן.
אגב, אני לא מת על ירושה (לא בתכנות, לפחות), אבל כאן זה נראה יותר מתאים, כי יש איזה state לשמור עליו.

ירושה – המימוש ה"רגיל"

בואו נראה למשל, את המימוש המתבקש לנעילה "שגרתית":

using System.Threading;

public class MonitorLocker : LockerBase
{
    private readonly object syncRoot;

    public MonitorLocker(object syncObject)
    {
        syncRoot = syncObject;
    }

    public MonitorLocker() : this(new object())
    {
    }

    public override void Enter()
    {
        Monitor.Enter(syncRoot);
    }

    public override void Exit()
    {
        Monitor.Exit(syncRoot);
    }        
}

בקונסטרקטור נשים אובייקט שתפקידו להיות המשאב המשותף שעליו מבוססים השיתוף והנעילה.

ירושה – המימוש הריק

ועכשיו לקוד קצת אחר: class שלמעשה לא נועל. מעין dummy class שרק שומר על הפונקציונליות כלפי חוץ:

public class DummyLocker : LockerBase
{
    public override void Enter()
    {
    }

    public override void Exit()
    {
    }
}

בעקרון ה class הזה לא ישבור קומפילציה, אבל הוא לא באמת נועל כלום. זה ה dummy שלנו למקרה שמריצים את הקוד בסביבה שהיא single-threaded.

קצת אינטגרציה

אחרי כל הקוד הזה, נראה שימוש לאבסטרקציה הזו. נניח שיש לנו class בשם Counter. כל מה שיש שם זה מתודה בשם Hit ופרופרטי בשם Current.
וכל מה שצריך לקרות זה שכל קריאה ל Hit מעלה ב 1 את הערך של Current (שערכו ההתחלתי הוא 0).
אנחנו יודעים מראש שיהיו מצבים שבהם ה class הזה יהיה שימושי בסביבה שהיא single-threaded וכן בסביבה שהיא multi-threaded. לכן נשתמש בנעילה האבסטרקטית:

public class Counter
{
    private readonly LockerBase locker;
    private int counter = 0;

    public Counter(LockerBase locker)
    {
        this.locker = locker;
    }

    public void Hit()
    {
        using (locker.EnterLock())
        {
            ++counter;
        }

    }

    public int Current
    {
        get
        {
            using (locker.EnterLock())
            {
                return counter;
            }
        }
    }
}

הקוד די פשוט: כל התייחסות ל counter הפנימי "עטופה" בנעילה, אבל אנחנו לא יודעים מה יהיה המנעול שאיתו נעבוד.
המנעול עצמו יכנס ל class דרך הקונסטרקטור (ולזה קוראים Dependency Injection).
כך, למשל, ניצור instance של Counter לסביבה שהיא single-threaded (כלומר ללא צורך בנעילות):

Counter myCounter = new Counter(new DummyLocker());

אבל, כדי לא לעצבן את המתכנת שישתמש ב class הזה, אולי כדאי שנוסיף overload עם ה dummy-locker שלנו כברירת מחדל לקונסטרקטור ריק:

public Counter() : this(new DummyLocker())
{
}

ואז השימוש יהיה קל יותר:

Counter myCounter = new Counter();

נוכל גם להוסיף מתודה סטאטית שתפקידה ליצור instance שהוא thread-safe באופן הבא:

public static Counter Synchronized()
{
    return new Counter(new MonitorLocker());
}

והקריאה:

Counter myCounter = Counter.Synchronized();

סיכום

מה שהצעתי כאן זה אבסטרקציה למנגנון הנעילה, תוך שימוש במאקרו של using כדי לכתוב קוד שמתנהג קרוב ככל האפשר ל lock המוכר.
האבסטרקציה הזו שימושית אם יודעים מראש שיש איזה class שיהיה שימושי גם בסביבה שהיא multi-threaded וגם בסביבה שהיא single-threaded.
עם זאת, יש דרכים נוספות להשיג את התוצאה הזו.
למשל, לכתוב interface ל Counter וליצור decorator שהוא יעטוף כל פעולה בנעילה, או dynamic proxy שיעשה את זה באופן אוטומטי. אולי אני ארחיב על זה בהזדמנות.
בכל מקרה, מה שאנחנו משיגים כאן זו הפרדה של הלוגיקה של הקוד עצמו מהלוגיקה של הנעילה, וזה נחמד לכשעצמו, וגם נותן לנו יתרון משמעותי אם נרצה לכתוב unit testing לקוד הזה.

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

קטגוריות:תכנות תגיות:, , ,

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

28 יוני, 2009 ronklein 3 תגובות

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

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

אז זהו, שלא.

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

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

קטגוריות:כללי תגיות: