1

Hoare のモニターを使用して証券取引所を実装しようとしています。

次のように、buy() と Sell() の 2 つの関数があります。

buy(procid, ticker, nshares, limit)
sell(procid, ticker, nshares, limit)

また、買い手 ID、売り手 ID、ティッカー、株式数、および価格に関する情報を出力する必要があります。そして公平さは常に満たされています。

私のソリューションの疑似コードは次のとおりですが、完全ではありません。基本的に、ティッカーごとに条件変数キューを使用します。売り手プロセスは、売り注文を証券取引所に送信するときにこのキューでスリープ状態になり、買い手プロセスは、条件 (価格制限と株式数の一致) が満たされた場合に買いたいことをこの売り手プロセスに通知します。

monitor SE {
  int available_shares;
  int price;

  sell(procid, ticker, nshares, limit) {
    wait(ticker); // put sell order in ticker queue
    available_shares += nshares;
    price = limit;
    printf("Starting transaction with seller %i", procid);
  }

  buy(procid, ticker, nshares, limit) {
    if (limit <= price && nshares <= available_shares) {
      signal(ticker);
      available_share -= nshares;
      printf("Completing transaction with buyer %i", procid);
      printf("Transacting %i %s shares at %i", nshares, ticker, limit);
    } else {
      wait(ticker); // put buy order in ticker queue
    }
  }
}

このようなアプローチは、複数のティッカーの複数の売買注文を処理できるでしょうか? それとも行き止まりにつながりますか？

4

1 に答える 1

2

デッドロックの問題を解決するには、買い手用と売り手用の 2 つの条件変数を使用します。各メソッドは、最初に available_shares を変更し、次に独自の条件変数を通知し、最後に他の条件変数を待機します。とはいえ、各操作は、ウェイクアップ後にトランザクションを完了するか、再びスリープ状態になるために、available_shares に関する状態を再確認する必要があります。

ここでの問題は、これがあなたが誰から/誰にどれだけ売買しているかを追跡していないことです. 売り手がトランザクションですべての株式を売却することを保証するものではありません. したがって、最初の質問への回答として、そのようなアプローチが複数のティッカーの複数の売買注文をどのように処理できるかわかりません。各キーが制限であり、各値が優先キューまたはティッカーによって並べ替えられたリストである HashTable または辞書を使用するこの他のソリューションを提案します。

monitor SE {
  int available_shares;
  int price;
  Dictionary<int, SortedList<int, Transac>> Ts;

  sell(procid, ticker, nshares, limit) {
    Transac t = new Transac(procid, nshares, limit);

    Ts[limit].enqueue(ticker, t); //probably you should verify first if the entry is not null 

    available_shares += nshares;

    notifyAll(tickerB);

    while(Ts[limit][ticker] > 0)
      wait(tickerS); 

    printf("Starting transaction with seller %i", Ts[limit][ticker].procid);
  }

  buy(procid, ticker, nshares, limit) {

    int nshares_copy = nshares;

    while(true){
      int cnt = 0;
      List<Transac> tmp = new List<Transac>();
      for(int i = 0; i < Ts.keys.length && cnt < nshares; i++){
          if(Ts.keys[i] <= limit){
            for(int j = 0; j < Ts[Ts.keys[i]].lenght && cnt < nshares; j++){
                cnt += Ts[Ts.keys[i]][j].nshares;
                tmp.add(Ts[Ts.keys[i]][j]);
            }
          }
      }
      if(nshares <= cnt){
          available_share -= nshares;

          foreach(Transac t in tmp){
            int min = min(t.nshares, nshares);
            t.nshares -= min;
            nshares -= min;
          }
          break;
      } else {
          wait(tickerB);
      }
    }

    notifyAll(tickerS);

    printf("Completing transaction with buyer %i", procid);
    printf("Transacting %i %s shares at %i", nshares_copy, ticker, limit);
  }
}

最初のアイデアに従うためにモニターを使用してこれを行いましたが、これが最善の方法だとは思わないと言わざるを得ません。よりきめ細かいロックを使用すると、パフォーマンスが向上する可能性があると思います（ロックやアトミック操作など）。注: コードはテストされていません。そのため、実装の詳細をいくつか省略した可能性があります

于 2013-04-30T19:28:26.017 に答える