Let n be the number of threads that can compete for a shared resource R. The mutual exclusion problem involves coordinating these n concurrent threads in accessing R in a mutually exclusive way. This paper addresses t...
详细信息
Let n be the number of threads that can compete for a shared resource R. The mutual exclusion problem involves coordinating these n concurrent threads in accessing R in a mutually exclusive way. This paper addresses two basic questions related to the First-Come-First-Served (FCFS) mutual exclusion algorithms that use only read-write operations: one is regarding the lower bound on the shared space requirement and the other is about fairness. The current best FCFS algorithm using read-write operations requires 5n shared bits. Could the shared space requirement be further reduced? The existing FCFS mutual exclusion algorithms assure fairness only among the threads which cross the 'doorway' sequentially. In systems with multicore processors, which are becoming increasingly common nowadays, threads can progress truly in parallel. Therefore, it is quite likely that several threads can cross the doorway concurrently. In such systems, the threads which cross the doorway sequentially may constitute only a fraction of all competing threads. While this fraction of threads follow the FCFS order, the rest of the threads have to rely on a biased scheme which always favors threads with smaller identifiers. Is there a simpler way to remove this bias to assure global fairness? This paper answers the above two questions affirmatively by presenting simple FCFS mutual exclusion algorithms using only read-write operations the first one using 3n shared bits and the latter algorithms using 4n shared bits. The resulting algorithms are simple, space-efficient, and highly fair. (C) 2013 Elsevier Inc. All rights reserved.
As multicore processors are becoming increasingly common everywhere, the future computing systems and devices are becoming inevitably concurrent. Also, on the applications side, automation is steadily infiltrating int...
详细信息
As multicore processors are becoming increasingly common everywhere, the future computing systems and devices are becoming inevitably concurrent. Also, on the applications side, automation is steadily infiltrating into everyday life, and hence, most software systems are becoming increasingly complex and concurrent. As a result, recent developments and projections indicate that we are entering into the era of concurrent programming. Synchronizing asynchronous concurrent processes in accessing a shared resource is an important issue. Among the synchronization issues, mutual exclusion is fundamental. Solutions to most higher level synchronization problems rely on the assurance of mutual exclusion. Several algorithms with varying characteristics are proposed in the literature to solve the mutual exclusion problem. This paper presents two new algorithms to solve the mutual exclusion problem. The algorithms are simple and have many nice properties.
暂无评论