一個適用於共用記憶體多處理機系統中結合持續等待與系統呼叫的互斥演算法

Abstract

在共用記憶體多處理機系統中的互斥演算法，大致可分為使用持續等待及 系統呼叫兩類。持續等待是讓每一個程序一直測試共用變數，直到可以進 入臨界區為止，因此適用於以加速程式執行的應用。系統呼叫是將不能進 入臨界區的程序暫時擱置，因此適用於以增加系統工作量的環境。本論文 中，我們提出一個結合持續等待與系統呼叫的互斥演算法，增加了系統工 作量而只稍微延遲程式的執行。 我們在實際系統下比較我們和Anderson 的演算法，並提出一個數學模型，來分析在理想系統下，所提出的演算法 在加速程式執行與增加系統工作量的效果。 The mutual exclusion algorithms for shared-memory multiprocessors are mainly categorized into two classes: spinning and blocking. The spinning constructs are good for speeding up the concurrent program in which processes repeatedly test shared variable to determine when they may proceed. Blocking constructs are good for system throughput: waiting process blocks itself and leaves an idle processing element for other processes. In this thesis, we propose a spinning-cum-blocking algorithm which yields drastic improvement in system throughput, sacrificing only a small amount of speed up for time critical application. We compare the speed up of our algorithm with Anderson's queueing lock, which works best in a coherent-cache multiprocessor, on a Sequent Symmetry. We also build a mathematical model to show the speed up and throughput gain in an ideal system.