使用顯示器實施證券交易所

我正在嘗試使用Hoare的顯示器實施證券交易所。使用顯示器實施證券交易所

它有兩個功能購買（）和賣出（）如下：

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

這樣的方法能夠處理多個買賣雙方的買賣訂單嗎？還是會導致死衚衕？

來源

2013-04-29 ratsimihah

在我看來，這段代碼可能會導致死鎖的情況，因爲您在等待之後增加了available_shares變量，所以買方將始終在條件和兩者都失敗，賣方和買方，永遠等待 – 2013-04-29 13:33:49

它最有可能。你知道我該如何解決這個問題嗎？或者你能否提出一個不同的實施方案來實施這種證券交易所？ – ratsimihah 2013-04-30 13:26:43

@ladypada boost'lockfree' should help，but look out for http://stackoverflow.com/questions/14893246/trouble-with-boostlockfreequeue-in-shared-memory-boost-1-53-gcc-4-7- 2-CL btw：ty教我如何存儲和處理訂單。 – 2013-05-19 13:22:22

要解決死鎖問題，我會使用兩個條件變量一個買方和一個賣方。每個方法首先修改available_shares，然後發送自己的條件變量，最後等待另一個條件變量。儘管如此，每次操作都需要在喚醒完成交易或再次入睡後重新檢查有關available_shares的條件。

這裏的問題是，這不會跟蹤你從/向誰購買/銷售多少。它甚至不保證賣方出售交易中的所有股份。所以，在回答你最初的問題時，我不明白這樣的方法能夠處理多個買賣人的多個買賣訂單。我提出一種使用哈希表或dictionary，其中每個關鍵是限制這個其他解決方案，每個值是priority queue或由代號下令sorted list：

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-30 19:28:26

使用顯示器實施證券交易所

回答

相關問題