ארכיון

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

Parallels and Internals Shminternals

25 אוקטובר, 2010 6 תגובות

הלכתי לאחרונה למפגש במיקרוסופט רעננה בנושא Parallel Programming in Visual Studio 2010. המרצה היה סשה גולדשטיין. אז קודם כל קצת מחמאות: למיקרוסופט על האירועים האלה שמאורגנים היטב, מהחניה ועד המשובים; לסשה גולדשטיין על הרצאה ברמה גבוהה, בשפה ברורה ועם הרבה סבלנות.

ועכשיו לעניינים הטכניים עצמם.

נעים להכיר – System.Threading.Tasks

נתחיל מהקדמונת: החל מגירסה 4.0 של הדוט נט פריימוורק, מיקרוסופט הכניסו פנימה פיצ'רים חדשים בתחום ה Multi-Threading. הפיצ'רים האלה מאפשרים פיתוח נוח יותר ל Multi-Threading, ולמעשה כדאי יותר לקרוא לזה מיקבול משימות, מתוך הנחת יסוד שמשימה ו Thread זה לא אותו הדבר, למרות שיש קשר הדוק. את הפיצ'רים והמחלקות למיניהם אפשר למצוא ב namespace שנקרא System.Threading.Tasks. הרעיון הכללי של הפיצ'רים האלה הוא שהמפתחים לא יטריחו את עצמם יותר מדי סביב הפרטים הקטנים של המיקבול עצמו, ויוכלו למקבל משימות בקלות יחסית.

ובכן, במפגש עצמו, סשה הראה איך ניתן למקבל משימות בצורות שונות, ואחת הדוגמאות להמחשה היא סכימה של מטריצה. וכאן עלה איזה אישו (issue, יוּ קנואו) מעניין. אבל לפני האישו, בואו נראה קוד סטנדרטי, ללא מיקבול, שסוכם את כל איברי המטריצה:

namespace Bronze.Lib
{
  public class SimpleAggregator
  {
    public int Sum(int[,] matrix)
    {
      var result = 0;
      for (var i = 0; i < matrix.GetLength(0); i++)
        for (var j = 0; j < matrix.GetLength(1); j++)
          result += matrix[i, j];
      return result;
    }
  }
}

פשוט וקל.

מקבילית המוחות

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

עכשיו, יש שתי גישות עיקריות לביצוע של הפתרון הזה:

1

מגדירים משתנה מספרי משותף, נניח sum, ומאתחלים אותו ל 0 (אפס). כל משימה תסכום את השורה שלה במטריצה, ותעדכן את ה sum הנ"ל לפי הסכום של השורה. התוצאה הסופית, אחרי שכל המשימות הסתיימו, תהיה ב sum.

הנה קצת פסודו-קוד לעניין זה:

1. common_sum = 0
2. Parallel: for each row in matrix:
  2.1 temp = sum(row)
  2.2 append temp to common_sum

הנקודה הכואבת יחסית בקוד הזה היא סעיף 2.2, שבו כל משימה מעדכנת את המשאב המשותף. מכיוון שזו סביבה של ריבוי משימות וככל הנראה גם ריבוי threads, הרי שיש לנו משאב משותף שיכול להתעדכן ע"י מספר threads במקביל. מקור לא אכזב ל data corruption. כדי להתגבר על זה, צריך לכתוב קוד של פעולת העדכון בצורה שתהיה thread-safe. ניתן להשיג את זה ע"י lock, ובמקרה הספציפי הזה, נוכל להשתמש גם ב Interlocked שיכול בפעולה אטומית להוסיף ערך למשתנה int.

בואו נראה את הקוד שמבצע את הגישה הראשונה, עם Interlocked:

using System.Threading;
using System.Threading.Tasks;

namespace Bronze.Lib
{
  public class ParallelWithInterlock
  {
    public int Sum(int[,] matrix)
    {
      var outerUpperBound = matrix.GetLength(0);
      var commonSum = 0;

      var innerUpperBound = matrix.GetLength(1);
      Parallel.For(0, outerUpperBound, i =>
      {
        var localSum = 0;
        for (var j = 0; j < innerUpperBound; j++)
          localSum += matrix[i, j];
        Interlocked.Add(ref commonSum, localSum);
      });

      return commonSum;
    }
  }
}

2

במקום להגדיר משתנה משותף ולהגן עליו באמצעי סנכרון שונים, נוכל להגדיר מערך שבו לכל משימה מוקצה תא משלה. הגישה לאיברי המערך היא thread-safe לפי הגדרה (אגב, יצא לי לחפור על זה פעם ב stackoverflow), ולכן כל משימה יכולה לעדכן את התא "שלה" במערך הנ"ל, מבלי לחשוש מ data corruption. בסוף התהליך סוכמים את כל איברי המערך, ובא לציון גואל. שימו לב, עיקר התחכום כאן הוא שהפקודה Parallel.For יוצרת משתנה אינדקס, ושולחת אותו כפרמטר ל delegate של המשימה המבצעת, וזה בדיוק האינדקס של התא ה"פרטי" של המשימה במערך המשותף. הנה הקוד שממחיש את זה:

using System.Linq;
using System.Threading.Tasks;

namespace Bronze.Lib
{
  public class ParallelAggregator
  {
    public int Sum(int[,] matrix)
    {
      var outerUpperBound = matrix.GetLength(0);
      var partialSums = new int[outerUpperBound];

      var innerUpperBound = matrix.GetLength(1);
      Parallel.For(0, outerUpperBound, i =>
      {
        partialSums[i] = 0;
        for (var j = 0; j < innerUpperBound; j++)
          partialSums[i] += matrix[i, j];
      });

      var result = partialSums.Sum();
      return result;
    }
  }
}

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

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

using System.Linq;
using System.Threading.Tasks;

namespace Bronze.Lib
{
  public class ParallelAggregatorWithLocalSum
  {
    public int Sum(int[,] matrix)
    {
      var outerUpperBound = matrix.GetLength(0);
      var partialSums = new int[outerUpperBound];

      var innerUpperBound = matrix.GetLength(1);
      Parallel.For(0, outerUpperBound, i =>
      {
        var localSum = 0;
        for (var j = 0; j < innerUpperBound; j++)
          localSum += matrix[i, j];
        partialSums[i] = localSum;
      });

      var result = partialSums.Sum();
      return result;
    }
  }
}

כפי שניתן לראות, ההצהרה על המשתנה הלוקאלי יכולה להיראות מיותרת למי שלא מכיר את האישו הזה.

של מי ארוך יותר?

כתבתי תוכנית קטנה שמשווה את הביצועים, ויש יתרון מובהק בביצועים של ParallelAggregatorWithLocalSum (בוצע ב Release על הלפטופ שלי). היתרון אצלי במחשב הוא של 40%, כלומר המחלקה ParallelAggregatorWithLocalSum רצה ב 40% בממוצע מהר יותר מהמחלקה ParallelAggregator. לא יאמן. באותה תוכנית ניתן גם לראות שהביצועים של ParallelAggregatorWithLocalSum ושל ParallelWithInterlock ממש קרובים אחד לשני (לפעמים האחד מהיר יותר באחוז או שניים ולפעמים השני). את הקוד המלא אפשר להוריד מכאן. הנה גרף שממחיש את התוצאות של סכימת מטריצה עם 99 שורות ו 31841 עמודות:

משך זמן הסכימה של מטריצה ספציפית, ע"י המחלקות השונות, באחוזים לעומת ה Base

סיכום ומסקנות

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

אגב, בפוסט הזה אפשר לראות רק חלק מהאפשרויות של המיקבול ב Parallel, אתם מוזמנים לראות דוגמאות נוספות בבלוג של סשה וכמובן ב MSDN.

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

ומסקנה נוספת: כל מי שחשב שדוט נט זו סביבה שבה אין צורך לדעת את ה internals – צודק רק ברוב המקרים. בחלק קטן (אבל משמעותי) מהמקרים כדאי מאוד לדעת מה קורה under-the-hood, רק כדי להפיק יותר מהסביבה הזו. יש עוד הרבה דוגמאות שממחישות כמה טוב לדעת את ה internals, והפוסט הזה מציג רק דוגמה אחת, כמובן. עם זאת, התחושה האישית שלי היא שבמיקרוסופט ניסו לכוון לשפה שהיא יותר high-level ממה שהתקבל בסופו של דבר. במילים אחרות, הציפיה של המפתחים שרק מגיעים לדוט נט היא שהם לא יצטרכו להתעסק עם tweakים כדי לכתוב קוד יעיל, ובסוף הם נאלצים להיכנס לפינות שהם לא חלמו עליהם, ושמרחיקות אותם מכתיבת קוד "נטו".
במילים פשוטות ובוטות יותר: פייר, התאכזבתי 🙂

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

מיקבול נעים!

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

Safe Value Pattern

23 יוני, 2010 2 תגובות

בפוסט הזה: קוד קצר ולעניין של משתנה שקוראים אותו ומעדכנים אותו בסביבה שהיא 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();
        try
        {
          T result = innerValue;        
          return result;
        }
        finally
        {
          locker.ExitReadLock();
        }
      }
      set
      {
        locker.EnterWriteLock();
        try
        {
          innerValue = value;
        }
        finally
        {
          locker.ExitWriteLock();
        }
      }
    }
  }
}

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

עוד כמה מילים

אם רוצים, אז אפשר לעשות כאן אבסטרקציה לשני המימושים (ע"י 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

בפוסט הזה:

  • הקדמה
  • הגדרת החוזה
  • מימוש רגיל ללא נעילות
  • נעילה באמצעות 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 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

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