使用监控器实现证券交易所 [英] Implementing a stock exchange using monitors

问题描述

我正在尝试使用Hoare的监视器进行证券交易所.

I am trying to implement a stock exchange using Hoare's monitors.

它具有两个功能buy()和sell()，如下所示:

It has two functions buy() and sell() as follow:

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

并应打印有关买方编号，卖方编号，股票编号，股份数量和价格的信息. 公平总是可以满足的.

And should print information on buyer id, seller id, ticker, number of shares, and price. And fairness is always satisfied.

我的解决方案的伪代码如下，但它并不完整. 它基本上为每个股票代码使用条件变量队列.当卖方进程向股票交易所发送卖单时，该进程处于休眠状态，并且买方进程在满足条件(匹配价格限制和股份数量)的情况下，向该卖方进程发出要购买的信号./p>

The pseudo-code of my solution is as follows, but it's not complete. It basically uses a condition variable queue for each ticker. A seller process is put to sleep on this queue when it sends a sell order to the stock exchange, and a buyer process signals this seller process that it wants to buy if the conditions (matching price limit and number of shares) are satisfied.

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
    }
  }
}

这种方法是否能够处理多个股票的多个买卖订单?还是导致死胡同?

Would such an approach be able to handle multiple buy and sell orders for multiple tickers? Or does it lead to a dead-end?

推荐答案

要解决死锁问题，我将使用两个条件变量，一个用于买方，一个用于卖方.每个方法首先修改available_shares，然后发信号通知其自己的条件变量，最后等待另一个条件变量.即使如此，每个操作在唤醒完成交易或再次进入睡眠状态后，都必须重新检查关于available_shares的条件.

To solve the deadlock problem I would use two condition variables one for buyers and one for sellers. Each method first modifies available_shares, then signals its own condition variable and finally waits on the other condition variable. Even though, each operation has to recheck the condition about available_shares after it wakes up to complete the transaction or to go to sleep again.

这里的问题是，这无法跟踪您向/向谁购买/销售多少商品.它甚至不保证卖方在交易中出售其所有股份.因此，在回答您最初的问题时，我不知道这种方法将如何处理多个股票的多个买卖订单.我提出了另一种解决方案，该解决方案使用HashTable或字典，其中每个键是一个限制，每个值都是优先级队列或

The problem here is that this does not keep track on how much you are buying/selling from/to who. It does not even guarantee that the seller sells all its shares in a transaction. So, in response to your original question I don't see how such an approach would be able to handle multiple buy and sell orders for multiple tickers. I propose this other solution which use a HashTable or dictionary in which each key is a limit and each value is a priority queue or a sorted list ordered by the tickers:

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);
  }
}

我是使用监视器来遵循您的最初想法的，但是我不得不说我认为这不是最好的方法.我认为更细粒度的锁可以为您提供更好的性能(例如锁或原子操作). 注意:该代码尚未经过测试.因此，我可能省略了一些实现细节

I did this using monitors to follow your initial idea, but I have to say that I don't think this is the best way. I think a more fine-grain lock could give you a better performance (such as locks or atomic operations). Note: The code has not been tested. So, I might have left out some implementation details

这篇关于使用监控器实现证券交易所的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！