פילוסופים מאכילים היטב או תכנות NET תחרותי

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

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

משימה

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

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

כדי להתחיל שרשורים, אנו משתמשים במאגר חוטים דרך Task.Run שיטה:

var cancelTokenSource = new CancellationTokenSource();
Action<int> create = (i) => RunPhilosopher(i, cancelTokenSource.Token);
for (int i = 0; i < philosophersAmount; i++) 
{
    int icopy = i;
    // Поместить задачу в очередь пула потоков. Метод RunDeadlock не запускаеться 
    // сразу, а ждет своего потока. Асинхронный запуск.
    philosophers[i] = Task.Run(() => create(icopy), cancelTokenSource.Token);
}

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

במילים אחרות, System.Threading.Tasks.Task הכיתה זהה Thread, אבל עם כל מיני נוחות: היכולת להפעיל משימה אחרי בלוק של משימות אחרות, להחזיר אותן מפונקציות, להפריע להן בצורה נוחה ועוד. וכו' הם נחוצים כדי לתמוך בבנייה אסינכרונית / ממתינה (דפוס אסינכרוני מבוסס משימות, סוכר תחבירי להמתנה לפעולות IO). נדבר על זה מאוחר יותר.

CancelationTokenSource כאן זה נחוץ כדי שהפתיל יוכל להפסיק את עצמו עם האות של החוט הקורא.

בעיות סנכרון

פילוסופים חסומים

אוקיי, אנחנו יודעים איך ליצור שרשורים, בואו ננסה לאכול ארוחת צהריים:

// Кто какие вилки взял. К примеру: 1 1 3 3 - 1й и 3й взяли первые две пары.
private int[] forks = Enumerable.Repeat(0, philosophersAmount).ToArray();

// То же, что RunPhilosopher()
private void RunDeadlock(int i, CancellationToken token) 
{
    // Ждать вилку, взять её. Эквивалентно: 
    // while(true) 
    //     if forks[fork] == 0 
    //          forks[fork] = i+1
    //          break
    //     Thread.Sleep() или Yield() или SpinWait()
    void TakeFork(int fork) =>
        SpinWait.SpinUntil(() => 
            Interlocked.CompareExchange(ref forks[fork], i+1, 0) == 0);

    // Для простоты, но можно с Interlocked.Exchange:
    void PutFork(int fork) => forks[fork] = 0;

    while (true)
    {
        TakeFork(Left(i));
        TakeFork(Right(i));
        eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
        PutFork(Left(i));
        PutFork(Right(i));
        Think(i);

        // Завершить работу по-хорошему.
        token.ThrowIfCancellationRequested();
    }
}

כאן אנחנו מנסים קודם כל לקחת את המזלג השמאלי, ואחר כך את המזלג הימני, ואם זה מסתדר, אז אנחנו אוכלים ומחזירים אותם. לקיחת מזלג אחד זה אטומי, כלומר. שני חוטים לא יכולים לקחת אחד בו זמנית (לא נכון: הראשון קורא שהמזלג פנוי, השני - גם הראשון לוקח, השני לוקח). לזה Interlocked.CompareExchange, אשר חייב להיות מיושם עם הוראת מעבד (TSL, XCHG), הנועל פיסת זיכרון לקריאה וכתיבה ברצף אטומי. ו- SpinWait שווה ערך למבנה while(true) רק עם קצת "קסם" - החוט לוקח את המעבד (Thread.SpinWait), אבל לפעמים מעביר את השליטה לשרשור אחר (Thread.Yeild) או נרדם (Thread.Sleep).

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

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

הרעב של הפילוסופים

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

// То же что и в RunDeadlock, но теперь кладем вилку назад и добавляем плохих философов.
private void RunStarvation(int i, CancellationToken token)
{
    while (true)
    {
        bool hasTwoForks = false;
        var waitTime = TimeSpan.FromMilliseconds(50);
        // Плохой философов может уже иметь вилку:
        bool hasLeft = forks[Left(i)] == i + 1;
        if (hasLeft || TakeFork(Left(i), i + 1, waitTime))
        {
            if (TakeFork(Right(i), i + 1, TimeSpan.Zero))
                hasTwoForks = true;
            else
                PutFork(Left(i)); // Иногда плохой философ отдает вилку назад.
        } 
        if (!hasTwoForks)
        {
            if (token.IsCancellationRequested) break;
            continue;
        }
        eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
        bool goodPhilosopher = i % 2 == 0;
        // А плохой философ забывает положить свою вилку обратно:
        if (goodPhilosopher)
            PutFork(Left(i));
        // А если и правую не положит, то хорошие будут вообще без еды.
        PutFork(Right(i));

        Think(i);

        if (token.IsCancellationRequested)
            break;
    }
}

// Теперь можно ждать определенное время.
bool TakeFork(int fork, int philosopher, TimeSpan? waitTime = null)
{
    return SpinWait.SpinUntil(
        () => Interlocked.CompareExchange(ref forks[fork], philosopher, 0) == 0,
              waitTime ?? TimeSpan.FromMilliseconds(-1)
    );
}

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

כאן אתה יכול לראות שהשרשורים מתעוררים לפעמים ומנסים להשיג את המשאב. שתיים מארבע הליבות לא עושות כלום (גרף ירוק למעלה).

מותו של פילוסוף

ובכן, בעיה נוספת שיכולה להפריע לארוחת ערב מפוארת של פילוסופים היא אם אחד מהם ימות פתאום עם מזלגות בידיו (והם יקברו אותו כך). ואז השכנים יישארו בלי ארוחת צהריים. אתה יכול להמציא קוד לדוגמה למקרה הזה בעצמך, למשל, הוא נזרק NullReferenceException אחרי שהפילוסוף לוקח את המזלגות. ודרך אגב, החריג לא יטופל והקוד המתקשר לא רק יתפוס אותו (בשביל זה AppDomain.CurrentDomain.UnhandledException וכו.). לכן, דרושים מטפלי שגיאות בשרשורים עצמם ובסיום חינני.

מלצר

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

הדרך הפשוטה ביותר היא כשהפילוסופים פשוט יבקשו כל הזמן מהמלצר גישה למזלגות. הָהֵן. עכשיו פילוסופים לא יחכו למזלג בקרבת מקום, אלא ימתינו או ישאלו את המלצר. בהתחלה, אנחנו משתמשים רק ב-User Space בשביל זה, בו אנחנו לא משתמשים בפסיקות כדי לקרוא לפרוצדורות כלשהן מהקרנל (עליהם למטה).

פתרונות במרחב המשתמש

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

private static SpinLock spinLock = new SpinLock();  // Наш "официант"
private void RunSpinLock(int i, CancellationToken token)
{
    while (true)
    {
        // Взаимная блокировка через busy waiting. Вызываем до try, чтобы
        // выбрасить исключение в случае ошибки в самом SpinLock.
        bool hasLock = false;
        spinLock.Enter(ref hasLock);
        try
        {
            // Здесь может быть только один поток (mutual exclusion).
            forks[Left(i)] = i + 1;  // Берем вилку сразу, без ожидания.
            forks[Right(i)] = i + 1;
            eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
            forks[Left(i)] = 0;
            forks[Right(i)] = 0;
        }
        finally
        {
            if(hasLock) spinLock.Exit();  // Избегаем проблемы со смертью философа.
        }

        Think(i);

        if (token.IsCancellationRequested)
            break;
    }
}

SpinLock זה חוסם, עם, בערך, אותו דבר while(true) { if (!lock) break; }, אבל עם אפילו יותר "קסם" מאשר ב SpinWait (שמשתמשים בו שם). עכשיו הוא יודע לספור את הממתינים, להרדים אותם קצת ועוד. וכו' באופן כללי, עושה הכל כדי לייעל. אבל עלינו לזכור שזהו עדיין אותו מחזור אקטיבי שאוכל את משאבי המעבד ושומר על הזרימה, מה שעלול להוביל לרעב אם אחד מהפילוסופים יקבל עדיפות יותר מאחרים, אבל אין לו מזלג מוזהב (בעיית פריוריטי היפוך) . לכן, אנו משתמשים בו רק לשינויים קצרים מאוד בזיכרון המשותף, ללא שיחות של צד שלישי, מנעולים מקוננים והפתעות אחרות.

ציור עבור SpinLock. הנחלים "נלחמים" ללא הרף על מזלג הזהב. יש כשלים - באיור, האזור הנבחר. הליבות אינן מנוצלות במלואן: רק כ-2/3 על ידי ארבעת החוטים הללו.

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

על Interlocked יש לציין שאין רק CompareExchange, אבל גם שיטות אחרות לקריאה וכתיבה אטומית. ובאמצעות החזרה על השינוי, במקרה של שרשור אחר יש זמן לבצע את השינויים שלו (לקרוא 1, לקרוא 2, לכתוב 2, לכתוב 1 זה רע), ניתן להשתמש בו לשינויים מורכבים לערך בודד (דפוס Interlocked Anything) .

פתרונות מצב ליבה

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

המבנה הבסיסי כאן הוא הסמפור שהציע דיקסטרה לפני למעלה מחצי מאה. סמפור הוא, במילים פשוטות, מספר שלם חיובי המנוהל על ידי המערכת, ושתי פעולות עליו, הגדלה והקטנה. אם זה לא יצליח לרדת, אפס, אז חוט הקורא נחסם. כאשר המספר מוגדל על ידי חוט/תהליך פעיל אחר, הדילוגים על השרשורים והסמפור מופחת שוב במספר שעבר. אפשר לדמיין רכבות בצוואר בקבוק עם סמפור. NET מציעה מספר מבנים עם פונקציונליות דומה: AutoResetEvent, ManualResetEvent, Mutex ואת עצמי Semaphore. אנחנו נשתמש AutoResetEvent, זהו הקונסטרוקציה הפשוטה ביותר: רק שני ערכים 0 ו-1 (שקר, נכון). השיטה שלה WaitOne() חוסם את השרשור הקורא אם הערך היה 0, ואם 1, מוריד אותו ל-0 ומדלג עליו. שיטה Set() מעלה ל-1 ונותן למלצר אחד לעבור, ששוב מוריד ל-0. מתנהג כמו קרוסלת רכבת תחתית.

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

// Для блокирования отдельного философа.
// Инициализируется: new AutoResetEvent(true) для каждого.
private AutoResetEvent[] philosopherEvents;

// Для доступа к вилкам / доступ к столу.
private AutoResetEvent tableEvent = new AutoResetEvent(true);

// Рождение философа.
public void Run(int i, CancellationToken token)
{
    while (true)
    {
        TakeForks(i); // Ждет вилки.
        // Обед. Может быть и дольше.
        eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
        PutForks(i); // Отдать вилки и разблокировать соседей.
        Think(i);
        if (token.IsCancellationRequested) break;
    }
}

// Ожидать вилки в блокировке.
void TakeForks(int i)
{
    bool hasForks = false;
    while (!hasForks) // Попробовать еще раз (блокировка не здесь).
    {
        // Исключающий доступ к столу, без гонок за вилками.
        tableEvent.WaitOne();
        if (forks[Left(i)] == 0 && forks[Right(i)] == 0)
            forks[Left(i)] = forks[Right(i)] = i + 1;
        hasForks = forks[Left(i)] == i + 1 && forks[Right(i)] == i + 1;
        if (hasForks)
            // Теперь философ поест, выйдет из цикла. Если Set 
            // вызван дважды, то значение true.
            philosopherEvents[i].Set();
        // Разблокировать одного ожидающего. После него значение tableEvent в false.
        tableEvent.Set(); 
        // Если имеет true, не блокируется, а если false, то будет ждать Set от соседа.
        philosopherEvents[i].WaitOne();
    }
}

// Отдать вилки и разблокировать соседей.
void PutForks(int i)
{
    tableEvent.WaitOne(); // Без гонок за вилками.
    forks[Left(i)] = 0;
    // Пробудить левого, а потом и правого соседа, либо AutoResetEvent в true.
    philosopherEvents[LeftPhilosopher(i)].Set();
    forks[Right(i)] = 0;
    philosopherEvents[RightPhilosopher(i)].Set();
    tableEvent.Set();
}

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

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

פתרונות היברידיים

בדקנו שתי גישות לתזמון, כאשר אנו נשארים במצב משתמש ולולאה, וכאשר אנו חוסמים חוט דרך הליבה. השיטה הראשונה טובה למנעולים קצרים, השנייה לארוכים. לעתים קרובות יש צורך להמתין לזמן קצר עד שהמשתנה ישתנה בלולאה, ולאחר מכן לחסום את השרשור כאשר ההמתנה ארוכה. גישה זו מיושמת במה שנקרא. מבנים היברידיים. להלן אותם מבנים כמו עבור מצב ליבה, אך כעת עם לולאת מצב משתמש: SemaphorSlim, ManualResetEventSlim וכו' העיצוב הפופולרי ביותר כאן הוא Monitor, כי ב-C# יש ידוע lock תחביר. Monitor זהו אותו סמפור עם ערך מקסימלי של 1 (מוטקס), אבל עם תמיכה בהמתנה בלולאה, רקורסיה, דפוס ה-Condition Variable (עוד על כך בהמשך) וכו'. בואו נסתכל איתו על פתרון.

// Спрячем объект для Монитора от всех, чтобы без дедлоков.
private readonly object _lock = new object();
// Время ожидания потока.
private DateTime?[] _waitTimes = new DateTime?[philosophersAmount];

public void Run(int i, CancellationToken token)
{
    while (true)
    {
        TakeForks(i);
        eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
        PutForks(i);
        Think(i);
        if (token.IsCancellationRequested) break;
    }
}

// Наше сложное условие для Condition Variable паттерна.
bool CanIEat(int i)
{
    // Если есть вилки:
    if (forks[Left(i)] != 0 && forks[Right(i)] != 0)
        return false;
    var now = DateTime.Now;
    // Может, если соседи не более голодные, чем текущий.
    foreach(var p in new int[] {LeftPhilosopher(i), RightPhilosopher(i)})
        if (_waitTimes[p] != null && now - _waitTimes[p] > now - _waitTimes[i])
            return false;
    return true;
}

void TakeForks(int i)
{
    // Зайти в Монитор. То же самое: lock(_lock) {..}.
    // Вызываем вне try, чтобы возможное исключение выбрасывалось выше.
    bool lockTaken = false;
    Monitor.Enter(_lock, ref lockTaken);
    try
    {
        _waitTimes[i] = DateTime.Now;
        // Condition Variable паттерн. Освобождаем лок, если не выполненно 
        // сложное условие. И ждем пока кто-нибудь сделает Pulse / PulseAll.
        while (!CanIEat(i))
            Monitor.Wait(_lock); 
        forks[Left(i)] = i + 1;
        forks[Right(i)] = i + 1;
        _waitTimes[i] = null;
    }
    finally
    {
        if (lockTaken) Monitor.Exit(_lock);
    }
}

void PutForks(int i)
{
    // То же самое: lock (_lock) {..}.
    bool lockTaken = false;
    Monitor.Enter(_lock, ref lockTaken);
    try
    {
        forks[Left(i)] = 0;
        forks[Right(i)] = 0;
        // Освободить все потоки в очереди ПОСЛЕ вызова Monitor.Exit.
        Monitor.PulseAll(_lock); 
    }
    finally
    {
        if (lockTaken) Monitor.Exit(_lock);
    }
}

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

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

У lock לתחביר יש הפתעות מגעילות. ממליץ להשתמש Monitor ישירות [ריכטר] [אריק ליפרט]. אחד מהם הוא זה lock תמיד מחוץ Monitor, גם אם היה חריג, ובמקרה זה שרשור אחר יכול לשנות את מצב הזיכרון המשותף. במקרים כאלה, לרוב עדיף ללכת למבוי סתום או להפסיק איכשהו את התוכנית בבטחה. הפתעה נוספת היא שמוניטור משתמש בלוקי סנכרון (SyncBlock), הנמצאים בכל האובייקטים. לכן, אם נבחר אובייקט לא הולם, אתה יכול בקלות לקבל מבוי סתום (לדוגמה, אם אתה נועל על מחרוזת פנימית). לשם כך אנו משתמשים באובייקט הנסתר תמיד.

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

פילוסופים רבים או async / await

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

SemaphoreSlim יש לזה WaitAsync() שיטה. הנה יישום באמצעות דפוס זה.

// Запуск такой же, как раньше. Где-нибудь в программе:
Task.Run(() => Run(i, cancelTokenSource.Token));

// Запуск философа.
// Ключевое слово async -- компилятор транслирует этот метот в асинхронный.
public async Task Run(int i, CancellationToken token)
{
    while (true)
    {
        // await -- будем ожидать какого-то события.
        await TakeForks(i);
        // После await, продолжение возможно в другом потоке.
        eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
        // Может быть несколько событий для ожидания.
        await PutForks(i);

        Think(i);

        if (token.IsCancellationRequested) break;
    }
}

async Task TakeForks(int i)
{
    bool hasForks = false;
    while (!hasForks)
    {
        // Взаимоисключающий доступ к столу:
        await _tableSemaphore.WaitAsync();
        if (forks[Left(i)] == 0 && forks[Right(i)] == 0)
        {
            forks[Left(i)] = i+1;
            forks[Right(i)] = i+1;
            hasForks = true;
        }
        _tableSemaphore.Release();
        // Будем ожидать, чтобы сосед положил вилки:
        if (!hasForks)
            await _philosopherSemaphores[i].WaitAsync();
    }
}

// Ждем доступа к столу и кладем вилки.
async Task PutForks(int i)
{
    await _tableSemaphore.WaitAsync();
    forks[Left(i)] = 0;
    // "Пробудить" соседей, если они "спали".
    _philosopherSemaphores[LeftPhilosopher(i)].Release();
    forks[Right(i)] = 0;
    _philosopherSemaphores[RightPhilosopher(i)].Release();
    _tableSemaphore.Release();
}

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

בואו נבחן. עבודה של 100 פילוסופים על מכונה עם 4 ליבות לוגיות, 8 שניות. הפתרון הקודם עם Monitor הריץ רק את 4 השרשורים הראשונים והשאר לא פעל בכלל. כל אחד מארבעת החוטים הללו היה פעיל במשך כ-4 אלפיות השנייה. ופתרון ה-async / await רץ את כל ה-2, עם המתנה ממוצעת של 100 שניות כל אחד. כמובן שבמערכות אמיתיות, סרק של 6.8 שניות אינו מקובל ועדיף לא לעבד כל כך הרבה בקשות כאלה. הפתרון עם Monitor התברר כבלתי ניתן להרחבה כלל.

מסקנה

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

מקורות

• הדמיית זרימה: Visualizer של מקביליות
• MSDN: הַשׁחָלָה, דפוסי תכנות אסינכרוניים ורבים אחרים אחר
• [ריכטר] - CLR דרך C#, ג'פרי ריכטר
• [אריק ליפרט] - לגבי מנעול
• קוד מקור
• סרט - "ריקוד בין חרבות", ג. Semiradsky

מקור: www.habr.com