Thread Sync #2. 實作篇 - 互相等待的兩個執行緒

上篇有人跟我講太深奧了... Orz, 其實不會,只是還沒看到 Code 而以...。就先來幫黑暗魔人賽說明一下程式碼...。首先來看的是黑暗大魔王: GameHost..

 

GameHost 呼叫 Player 的片段[copy code]
    public void Start(Player p)    {        // 略...        int[] guess = p.StartGuess(_maxNum, _digits);        // 略...        Hint hint = compare(guess);        // 略...        while (hint.A != _digits)        {            // 略...            guess = p.GuessNext(hint);            // 略...            hint = compare(guess);        }        p.Stop();        // 略...    }
   1:  public void Start(Player p)
   2:  {
   3:      // 略...
   4:      int[] guess = p.StartGuess(_maxNum, _digits);
   5:      // 略...
   6:      Hint hint = compare(guess);
   7:      // 略...
   8:      while (hint.A != _digits)
   9:      {
  10:          // 略...
  11:          guess = p.GuessNext(hint);
  12:          // 略...
  13:          hint = compare(guess);
  14:      }
  15:      p.Stop();
  16:      // 略...
  17:  }

 

這段程式完全是老闆的角度在思考。抓到 PLAYER 後就叫它開始猜 StartGuess(),然後拼命的叫 PLAYER 再猜 GuessNext(), 直到猜中才可以休息 Stop()

很典型的多型 ( Polymorphism ) 應用,實際上會 RUN 什麼 CODE,就看繼承 PLAYER 的人是怎麼寫的...。這次我們再從弱勢勞工的角度來看看 PLAYER 該怎麼實作 (以 darkthread 附的 DummyPlayer 為例):

 

Player 實作的範例 ( DummyPlayer )[copy code]
public class DummyPlayer : Player{    private int[] _currAnswer = null;    private Random _rnd = new Random();    private void randomGuess()    {        List<int> lst = new List<int>();        for (int i = 0; i < _digits; i++)        {            int r = _rnd.Next(_maxNum);            while (lst.Contains(r))                r = _rnd.Next(_maxNum);            lst.Add(r);            _currAnswer[i] = r;        }    }    public override int[] StartGuess(int maxNum, int digits)    {        base.StartGuess(maxNum, digits);        _currAnswer = new int[digits];        randomGuess();        return _currAnswer;    }    public override int[] GuessNext(Hint lastHint)    {        randomGuess();        return _currAnswer;    }}
   1:  public class DummyPlayer : Player
   2:  {
   3:      private int[] _currAnswer = null;
   4:      private Random _rnd = new Random();
   5:   
   6:      private void randomGuess()
   7:      {
   8:          List<int> lst = new List<int>();
   9:          for (int i = 0; i < _digits; i++)
  10:          {
  11:              int r = _rnd.Next(_maxNum);
  12:              while (lst.Contains(r))
  13:                  r = _rnd.Next(_maxNum);
  14:              lst.Add(r);
  15:              _currAnswer[i] = r;
  16:          }
  17:      }
  18:   
  19:      public override int[] StartGuess(int maxNum, int digits)
  20:      {
  21:          base.StartGuess(maxNum, digits);
  22:          _currAnswer = new int[digits];
  23:          randomGuess();
  24:          return _currAnswer;
  25:      }
  26:      public override int[] GuessNext(Hint lastHint)
  27:      {
  28:          randomGuess();
  29:          return _currAnswer;
  30:      }
  31:  }

 

因為 CODE 不多,我就不刪了,全文照貼。另一個原因是我想讓各位看看拆成好幾段的 CODE 是不是還能夠一眼就還原成原來的邏輯?  如果只看這段 CODE 十秒鐘,沒有看註解或說明,誰能馬上回答這段 CODE 解題的邏輯是什麼?

 

別誤會,不是指這 CODE 不易讀,而是因為呼叫的方式邏輯被迫配合 GameHost 而被切散了,你得再重新把它拼湊起來。它的邏輯很簡單,甚至簡單到連問題的答案都被忽略掉了,不過就每次都隨機丟個數字回去,在 StartGuess( ) 及 GuessNext( ) 都是。

 

 

可憐的勞動階級要站起來啊~ 先幻想一下,如果勞工 (PLAYER) 才是老闆,那麼程式可以改成怎麼樣? 這也才是我們本篇的主角。先來看看成果再回頭來看怎麼實作。這次看的是修改後的版本: AsyncDummyPlayer.

 

換 PLAYER 的角度思考的邏輯: AsyncDummyPlayer[copy code]
    public class AsyncDummyPlayer : AsyncPlayer    {        private int[] _currAnswer = null;        private Random _rnd = new Random();        private void randomGuess()        {            List<int> lst = new List<int>();            for (int i = 0; i < _digits; i++)            {                int r = _rnd.Next(_maxNum);                while (lst.Contains(r))                    r = _rnd.Next(_maxNum);                lst.Add(r);                _currAnswer[i] = r;            }        }        protected override void Init(int maxNum, int digits)        {            _currAnswer = new int[digits];        }        protected override void Think()        {            while (true)            {                this.randomGuess();                Hint h = this.GameHost_AskQuestion(this._currAnswer);                if (h.A == this._digits) break;            }        }    }
   1:  public class AsyncDummyPlayer : AsyncPlayer
   2:  {
   3:      private int[] _currAnswer = null;
   4:      private Random _rnd = new Random();
   5:      private void randomGuess()
   6:      {
   7:          List<int> lst = new List<int>();
   8:          for (int i = 0; i < _digits; i++)
   9:          {
  10:              int r = _rnd.Next(_maxNum);
  11:              while (lst.Contains(r))
  12:                  r = _rnd.Next(_maxNum);
  13:              lst.Add(r);
  14:              _currAnswer[i] = r;
  15:          }
  16:      }
  17:      protected override void Init(int maxNum, int digits)
  18:      {
  19:          _currAnswer = new int[digits];
  20:      }
  21:      protected override void Think()
  22:      {
  23:          while (true)
  24:          {
  25:              this.randomGuess();
  26:              Hint h = this.GameHost_AskQuestion(this._currAnswer);
  27:              if (h.A == this._digits) break;
  28:          }
  29:      }
  30:  }

 

程式碼也沒比較少,都差不多。不過是那堆 CODE 換個地方擺而以。但是仔細看看,這個版本的邏輯清楚多了,PLAYER 一開始就是執行 Init( ) 的部份,而 GameHost 叫 Player 開始解題時, Player 就開始思考 (Think),而這個無腦的 Player 也很直接,就一直執行 while (true) { .... } 這個無窮迴圈,直到亂猜猜中為止。

如果 Player 在思考的時,不管在那裡它都可以適時的呼叫 GameHost_AskQuestion( .... ) 來跟 GameHost 問答案。什麼時後該猜數字? 該猜什麼數字? 這正是整個 Player 的核心,也就是 "怎麼猜" 這件事。以人的思考方式一定會分階段,比如一開始先把所有數字猜一輪,有個概念後再想想怎麼猜能更逼近答案,最後才是致命的一擊,找出正確答案送出去,贏得比賽。

這樣的作法,如果套在 DummyPlayer (原版本),每個階段都要塞在一個大的 switch case, 放在 GuessNext( ) 裡。而現在是那個階段? 只能靠 instance variable 了,先存著等到下次又被呼叫時再拿出來回想一下,上回作到那...。

而第二個版本,則完全沒這個問題,就把它當作一般程式思考就夠了,第一階段就是一個 LOOP,有它自己用的一些變數。第一階段處理完畢就離開 LOOP 繼續執行後面的 CODE... 直到最後離開 Think( ) 這個 method (認輸) 或是猜中答案光榮返鄉...。

 

 

兩者的差別看出來了嗎? DummyPlayer 像是被動的勞工,老闆說一動他就作一動。第一動作完就拿個筆計記下來,等著下次老闆再叫他,他就翻翻筆記看看之前做到那,這次繼續...。

而 AsyncDummyPlayer 這個主動的勞工呢? 老闆交待給他一件任務後,他就自己思考起該怎麼做了。中間都不需要老闆下令。反而是過程中勞工需要老闆的協助時,老闆再適時伸出援手就可以了,一切雜務都由這位主動優秀的勞工自己處理掉。

 

 

 

有沒有差這麼多? 這麼神奇? 是怎麼辦到的? 先來看看類別關系圖:

ThreadSync

 

上圖中,AsyncPlayer 就是改變這種型態的關鍵類別。AsyncPlayer 會用我們在上一篇講到的關念,化被動為主動,轉換這兩種呼叫模式。先來看看這個類別的程式碼到底變了什麼把戲,可以讓弱勢的勞工也有自主的權力?

 

 

 

 

AsyncPlayer 實作: 化被動為主動[copy code]
    public abstract class AsyncPlayer : Player    {        public override int[] StartGuess(int maxNum, int digits)        {            base.StartGuess(maxNum, digits);            Thread thinkThread = new Thread(this.ThinkCaller);            thinkThread.Start();                        this._host_return.WaitOne();            return this._temp_number;        }        public override int[] GuessNext(Hint lastHint)        {            this._temp_hint = lastHint;            this._host_call.Set();            this._host_return.WaitOne();            return this._temp_number;        }        public override void Stop()        {            base.Stop();            this._temp_hint = new Hint(this._digits, 0);            this._host_call.Set();            this._host_end.WaitOne();            this._host_complete = true;        }        private void ThinkCaller()        {            try            {                this.Init(this._maxNum, this._digits);                this.Think();            }            catch (Exception ex)            {                Console.WriteLine("Player Exception: {0}", ex);            }            finally            {                this._host_end.Set();            }        }        protected abstract void Init(int maxNum, int digits);        protected abstract void Think();        private AutoResetEvent _host_call = new AutoResetEvent(false);        private AutoResetEvent _host_return = new AutoResetEvent(false);        private AutoResetEvent _host_end = new AutoResetEvent(false);        private bool _host_complete = false;        private int[] _temp_number;        private Hint _temp_hint;        protected Hint GameHost_AskQuestion(int[] number)        {            if (this._host_complete == true) throw new InvalidOperationException("GameHost stopped!");            lock (this)            {                try                {                    this._temp_number = number;                    this._host_return.Set();                    this._host_call.WaitOne();                    return this._temp_hint;                }                finally {                    this._temp_number = null;                    this._temp_hint = new Hint(-1, -1);                }            }        }    }
   1:  public abstract class AsyncPlayer : Player
   2:  {
   3:      public override int[] StartGuess(int maxNum, int digits)
   4:      {
   5:          base.StartGuess(maxNum, digits);
   6:          Thread thinkThread = new Thread(this.ThinkCaller);
   7:          thinkThread.Start();
   8:          this._host_return.WaitOne();
   9:          return this._temp_number;
  10:      }
  11:      public override int[] GuessNext(Hint lastHint)
  12:      {
  13:          this._temp_hint = lastHint;
  14:          this._host_call.Set();
  15:          this._host_return.WaitOne();
  16:          return this._temp_number;
  17:      }
  18:      public override void Stop()
  19:      {
  20:          base.Stop();
  21:          this._temp_hint = new Hint(this._digits, 0);
  22:          this._host_call.Set();
  23:          this._host_end.WaitOne();
  24:          this._host_complete = true;
  25:      }
  26:      private void ThinkCaller()
  27:      {
  28:          try
  29:          {
  30:              this.Init(this._maxNum, this._digits);
  31:              this.Think();
  32:          }
  33:          catch (Exception ex)
  34:          {
  35:              Console.WriteLine("Player Exception: {0}", ex);
  36:          }
  37:          finally
  38:          {
  39:              this._host_end.Set();
  40:          }
  41:      }
  42:      protected abstract void Init(int maxNum, int digits);
  43:      protected abstract void Think();
  44:      private AutoResetEvent _host_call = new AutoResetEvent(false);
  45:      private AutoResetEvent _host_return = new AutoResetEvent(false);
  46:      private AutoResetEvent _host_end = new AutoResetEvent(false);
  47:      private bool _host_complete = false;
  48:      private int[] _temp_number;
  49:      private Hint _temp_hint;
  50:      protected Hint GameHost_AskQuestion(int[] number)
  51:      {
  52:          if (this._host_complete == true) throw new InvalidOperationException("GameHost stopped!");
  53:          lock (this)
  54:          {
  55:              try
  56:              {
  57:                  this._temp_number = number;
  58:                  this._host_return.Set();
  59:                  this._host_call.WaitOne();
  60:                  return this._temp_hint;
  61:              }
  62:              finally {
  63:                  this._temp_number = null;
  64:                  this._temp_hint = new Hint(-1, -1);
  65:              }
  66:          }
  67:      }
  68:  }

 

這段程式碼長了一點,內容也都刪不得,各位請耐心點看。上一篇我畫了張概念性的時序圖,這次我們再拿同一張圖,不過這次會標上程式碼:

 ThreadSync2

 

 

請注意一下各個箭頭的上下順序。由上往下代表時間的進行,如果應該在後面執行的 CODE 不巧先被呼叫了,則動作較快的那個 THREAD 會被迫暫停,等待另一邊的進度跟上。先來看看 StartGuess( ) 怎麼跟 Think( ) 互動:

StartGuess(...)[copy code]
        public override int[] StartGuess(int maxNum, int digits)        {            base.StartGuess(maxNum, digits);            Thread thinkThread = new Thread(this.ThinkCaller);            thinkThread.Start();                        this._host_return.WaitOne();            return this._temp_number;        }
   1:  public override int[] StartGuess(int maxNum, int digits)
   2:  {
   3:      base.StartGuess(maxNum, digits);
   4:      Thread thinkThread = new Thread(this.ThinkCaller);
   5:      thinkThread.Start();
   6:      this._host_return.WaitOne();
   7:      return this._temp_number;
   8:  }

 

GameHost 呼叫 Player.StartGuess( ) 有兩個目的,一個是給 Player 題目範圍,讓 Player 做好準備動作。另一個則是準備好之後 GameHost 要取得 Player 傳回的第一個問題。

程式碼很忠實的做了一樣的事,只不過 StartGuess( ) 建立了新的執行緒來負責。新的執行緒會執行 ThinkCaller( ),啟動之後 GameHost 這邊就什麼都不作,等待 _host_return 這個 WaitHandle 被叫醒,代表另一邊已經做好了,可以從共用變數 _temp_number 取得問題傳回去。

既然 GameHost 在等待某人通知它,我們就來看看是誰會通知他題目已經準備好了:

 

GameHost_AskQuestion(...)[copy code]
        protected Hint GameHost_AskQuestion(int[] number)        {            if (this._host_complete == true) throw new InvalidOperationException("GameHost stopped!");            lock (this)            {                try                {                    this._temp_number = number;                    this._host_return.Set();                    this._host_call.WaitOne();                    return this._temp_hint;                }                finally {                    this._temp_number = null;                    this._temp_hint = new Hint(-1, -1);                }            }        }
   1:  protected Hint GameHost_AskQuestion(int[] number)
   2:  {
   3:      if (this._host_complete == true) throw new InvalidOperationException("GameHost stopped!");
   4:      lock (this)
   5:      {
   6:          try
   7:          {
   8:              this._temp_number = number;
   9:              this._host_return.Set();
  10:              this._host_call.WaitOne();
  11:              return this._temp_hint;
  12:          }
  13:          finally {
  14:              this._temp_number = null;
  15:              this._temp_hint = new Hint(-1, -1);
  16:          }
  17:      }
  18:  }

 

就在 GameHost 正在等題目的時後,另一個執行緒正在進行 "思考" 的動作,直到有結論後會呼叫 GameHost_AskQuestion( ... ) 送出問題。這時這個問題會被放到 _temp_number, 而下一步就是 _host_return.Set( ), 通知另一個執行緒,正在等這個結果的人: "喂! 東西已經準備好了,可以來取貨了!!"

整個機制就這樣串起來了。GameHost 那邊怎麼把答案傳回來? 同樣的作法,反過來而以。GameHost 會藉著呼叫 Player.GuessNext(...) 把答案傳回來,而這時就觸動一樣的機制,讓另一邊 Player Thread 呼叫的 GameHost_AskQuestion( ... ) 醒過來,把答案拿走, RETURN 回去。

這樣一直重複下去,剩下最後一個同步的點,就是結束遊戲的地方。說穿了也是一樣的把戲,只是這次是藉著 GameHost 呼叫 Player.Stop( ),而另一邊 Player Thread 執行完 Think( ) 後,兩邊就一起結束遊戲了。

 

總算講完了。其實 thread 能解決的問題還真是五花八門。每次當我想出這些方法來簡化問題時,我就會覺的很有成就感。雖然寫出這個不會讓我贏得比賽,反而因為同步的關係,AsyncDummyPlayer 執行的速度還遠遠落後 DummyPlayer (我的機器跑起來,大概差了四~五倍 ...) 。不過我知道我簡單的頭腦,不先把問題簡化的話,我大概解決不了太複雜的問題...。也許是缺了這種能力,才讓我更有動力去想簡化問題的方式吧?

 

最後,為什麼每次講到 thread 的文章,都是 code 一點點,文章跟圖一大堆? 咳咳... 難道我也到了靠一張嘴混日子的地步了嘛? Orz... 本系列到此結束,以後還會有什麼主題? 想到再說啦~~ 今天各位記得去拜拜~~ 下回見!






Search

    Post Directory

    Facebook Pages