המדריך לתכנות מקבילי בשפת C Sharp – פרק ח' – DeadLock

Deadlock הוא מצב שבו 2-Threads מחכים אחד לשני שיסיימו את הפעולה על מנת להמשיך את פעולתם שלהם עצמם – מה שיגרום לכך שהם "יקפאו". מה נוכל לעשות כדי למנוע מצב זה?

בפרקים הקודמים של המדריך ראינו כיצד ביכולתנו להגביל גישה למקטע קריטי –

• על ידי נעילות אקסקלוסיביות – Lock, Monitor, Mutex

• על ידי נעילות שאינן אקסקלוסיביות – Semasphore, SemsphoreSlim

תארו לכם מצב שבו יש לנו תוכנית המשתמשת ב-Multithreading ולה שני משאבים משותפים – Resource1 ו-Resource2.
נניח וברשותנו שני Threads אשר נקראים Thread1 ו-Thread2,
כאשר Thread1 נועל את Resource1 ובמקביל מנסה לנעול את Resource2.
תארו לכם שבאותו הזמן Thread2 נועל את Resource2 ובמקביל מנסה לנעול את Resource1…

ובכן מצב כזה נקרא DeadLock, וכפי שניתן לראות נוצר לנו קונפליקט שגורם ל-"קיפאון" בתוכנית.

איך למנוע\לטפל במצב של Deadlock

לצורך ההדגמה נכתוב תוכנית שתדמה חשבון בנק.
ראשית ניצור מחלקה בשם Account:

namespace DeadLock
{
    public class Account
    {
        public int Id { get; }
        public string Name { get; }
        public double Balance;
        public Account(int id, string name, double balance)
        {
            Id = id;
            Name = name;
            Balance = balance;
        }
        public void WithdrawMoney(double amount)
        {
            Balance -= amount;
        }
        public void DepositMoney(double amount)
        {
            Balance += amount;
        }
    }
}

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

using System;
using System.Threading;

namespace DeadLock
{
    public class AccountManager
    {
        Account FromAccount;
        Account ToAccount;
        double TransferAmount;
        public AccountManager(Account fromAccount, Account toAccount, double transferAmount)
        {
            FromAccount = fromAccount;
            ToAccount = toAccount;
            TransferAmount = transferAmount;
        }
        public void Transfer()
        {
            Console.WriteLine($"{Thread.CurrentThread.Name} trying to acquire lock on {FromAccount.Name}");
            lock (FromAccount)
            {
                Console.WriteLine($"{Thread.CurrentThread.Name} acquired lock on {FromAccount.Name}");
                Console.WriteLine($"{Thread.CurrentThread.Name} doing Some work");
                Thread.Sleep(1000);
                Console.WriteLine($"{Thread.CurrentThread.Name} trying to acquire lock on {ToAccount.Name}");
                lock (ToAccount)
                {
                    FromAccount.WithdrawMoney(TransferAmount);
                    ToAccount.DepositMoney(TransferAmount);
                }
            }
        }
    }
}

כפי שתוכלו להבחין, מחלקה זו מחזיקה 3 משתנים:

• FromAccount – החשבון אשר ממנו מתבצעת ההעברה
• ToAccount – החשבון אשר אליו מתבצעת ההעברה
• TransferAmount – הסכום שיועבר

המתודה Transfer אחראית על ביצוע ההעברה כאשר היא פועלת באופן הבא:

• עם הכניסה למקטע הקריטי היא נועלת את FromAccount.
• מתבצעת פעולה מסוימת אשר אורכת כשנייה אחת.
• ננסה להשיג נעילה ל-ToAccount.
• ונבצע את ההעברה

כעת, נכתוב את המתודה הראשית של התוכנית שלנו כך:

using System.Threading;

namespace DeadLock
{
    public class Program
    {
        public static void Main()
        {
            Console.WriteLine("main thread started");
            Account account1 = new("Moshe", 5000);
            Account account2 = new("David", 5000);
            AccountManager accountManager1 = new(account1, account2, 2500);
            Thread thread1 = new(accountManager1.Transfer)
            {
                Name = "Thread1"
            };
            AccountManager accountManager2 = new(account2, account1, 4000);
            Thread thread2 = new(accountManager2.Transfer)
            {
                Name = "Thread2"
            };
            thread1.Start();
            Thread.Sleep(100);
            thread2.Start();
            thread1.Join();
            thread2.Join();

            Console.WriteLine($"{account1.Name} Balance: {account1.Balance}");
            Console.WriteLine($"{account2.Name} Balance: {account2.Balance}");
            Console.WriteLine("main thread Completed");
        }
    }
}

כלומר שכאשר שני הלקוחות ינסו לבצע העברה במקביל, נמצא את עצמנו במצב של DeadLock…

על ידי שימוש ב-Monitor.TryEnter

נוכל למנוע מצב כזה באמצעות שימוש במתודה Monitor.TryEnter.
מתודה זו מקבלת Out Parameter אשר הערך שלו נמדד במילי-שניות,
כלומר שעל ידי שימוש בפרמטר זה נוכל להגדיר זמן timeout שבו ה-thread הנוכחי ישחרר את הנעילה.
אם כך, התוצאה תהיה שה-Monitor יאלץ את Thread1 לשחרר את הנעילה במידה ו-Thread2 ממתין יותר מדי זמן להיכנס למקטע הקריטי.
שנו את מחלקת AccountHandler בהתאם:

using System;
using System.Threading;

namespace DeadLock
{
    public class AccountManager
    {
        Account FromAccount;
        Account ToAccount;
        double TransferAmount;
        public AccountManager(Account fromAccount, Account toAccount, double transferAmount)
        {
            FromAccount = fromAccount;
            ToAccount = toAccount;
            TransferAmount = transferAmount;
        }
        public void Transfer()
        {
            Console.WriteLine($"{Thread.CurrentThread.Name} trying to acquire lock on {FromAccount.Name}");
            lock (FromAccount)
            {
                Console.WriteLine($"{Thread.CurrentThread.Name} acquired lock on {FromAccount.Name}");
                Console.WriteLine($"{Thread.CurrentThread.Name} doing Some work");
                Thread.Sleep(1000);
                Console.WriteLine($"{Thread.CurrentThread.Name} trying to acquire lock on {ToAccount.Name}");
                if (Monitor.TryEnter(ToAccount, 1000))
                {
                    Console.WriteLine($"{Thread.CurrentThread.Name} acquired lock on {ToAccount.Name}");
                    try
                    {
                        FromAccount.WithdrawMoney(TransferAmount);
                        ToAccount.DepositMoney(TransferAmount);
                    }
                    finally
                    {
                        Monitor.Exit(ToAccount);
                    }
                }
                else
                {
                    Console.WriteLine($"{Thread.CurrentThread.Name} failed to acquire lock on {ToAccount.Name}, existing.");
                }
            }
        }
    }
}

וכשנריץ את התוכנית נוכל לקבל את התוצאה הבאה:

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

על ידי נעילה לפי סדר מוגדר

על מנת להגדיר סדר שלפיו תתבצע הכניסה למקטע הקריטי, נכתוב את מחלקת AccountHandler כך:

using System;
using System.Threading;

namespace DeadLock
{
    public class AccountManager
    {
        Account FromAccount;
        Account ToAccount;
        double TransferAmount;
        public AccountManager(Account fromAccount, Account toAccount, double transferAmount)
        {
            FromAccount = fromAccount;
            ToAccount = toAccount;
            TransferAmount = transferAmount;
        }
        public void Transfer()
        {
            object lock1, lock2;
            if (FromAccount.Id > ToAccount.Id)
            {
                lock1 = FromAccount;
                lock2 = ToAccount;
            }
            else
            {
                lock1 = ToAccount;
                lock2 = FromAccount;
            }
            Console.WriteLine($"{Thread.CurrentThread.Name} trying to acquire lock on {((Account)lock1).Name}");

            lock (lock1)
            {
                Console.WriteLine($"{Thread.CurrentThread.Name} acquired lock on {((Account)lock1).Name}");
                Console.WriteLine($"{Thread.CurrentThread.Name} doing Some work");
                Thread.Sleep(1000);
                Console.WriteLine($"{Thread.CurrentThread.Name} trying to acquire lock on {((Account)lock2).Name}");
                lock (lock2)
                {
                    Console.WriteLine($"{Thread.CurrentThread.Name} acquired lock on {((Account)lock2).Name}");
                    FromAccount.WithdrawMoney(TransferAmount);
                    ToAccount.DepositMoney(TransferAmount);
                }
            }
        }
    }
}

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

בפרק הבא של המדריך נכיר את AutoResetEvent ו-ManualResetEvent ואיך נוכל להשתמש בהם על מנת לנהל ולסנכרן אירועים אשר נובעים מ-Threads שונים.
לקריאה מורחבת על Thread ו-Threading באתר של מייקרוסופט יש ללחוץ כאן.