一個低額外負擔,容錯的分散式並行控制機制

Abstract

在分散式系統裡，為了避免同時存取共享的資源所可能發生的競賽狀況， 在存取共享資源時，都會使用同步控制機制來避免這種問題發生。Lock， 或類似的機制，是目前被使用的最廣泛的一種同步控制機制。我們發現， 在很多情況下，程式在對Lock的使用上會發生Nesting的情況；也就是說 ，某個執行單元在獲得Lock之後，會再向系統要求相同的Lock。這在某些 自動提供同步控制的系統，例如交易處理系統；或是某些設計時不是很注 意的程式裡，都可以看到這樣的特性。因此，我們設計了一個階層式的 Lock機制，來利用程式中的這項特性。它使用了代理者的概念，來減少在 要求一個nested lock時所產生的額外負擔。另外，它也提供了容錯的功 能，可以容許系統裡一個伺服器節點發生錯誤的情況。它還提供了一個圖 形使用者介面，方便使用者管理與容錯相關的功能。我們這套同步控制機 制目前被實作在Windows NT 4.0上，它和NT內建的critical section機制 完全相容；而且它還可以提供程式更高的平行性。因為整個機制被完全地 實作在使用者模式下，所以也很容易移植到其他的作業系統平台上。另外 ，因為Windows NT是一種支援SMP的作業系統，所以我們也利用了一些MP 的特性，來減少這個機制所帶來的額外負擔。 In distributed systems, race condition may occur if two or more execution unitstry to access a shared resource concurrently. In order to prevent this problem,these execution units will use concurrency control facilities during theyaccess shared resources. Locks, or similar facilities, are the most popular concurrency control facilities for their simplicity. We find out that some programs often use nesting locks; that is, after an execution unit has been granted a lock, it still requests the same lock before it releases the lock. This property can be found in systems that provide automatic concurrency control, such as transaction processing systems. It also can be found in a program with mindless design. Hence, we devise a hierarchical lock facility to exploit this property. It employs the notion of proxy to reduce the overhead ofrequesting a nested lock. In addition, it is also fault-tolerant, and can tolerate single- site failure of server nodes. Moreover, it provides a GUI interface for managing fault-tolerant-related functions conveniently. We implement this facility upon Windows NT 4.0. It is compatible with the critical section facility that was built in Windows NT natively; furthermore, it makes programs exploit their concurrency more easily than using critical section. It can also be ported to other operating systems with ease because it is fully implemented under user-mode. Besides, since Windows NT is an operating system that supports SMP hardware platform, we take advantage of some characteristics of multiprocessor systems, and try to reduce the overhead of using this facility. In this thesis, we will examine each aspect of this facility.