Dartmouth logo Dartmouth College Computer Science
Technical Report series
CS home
TR home
TR search TR listserv
By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Constant RMR Solutions to Reader Writer Synchronization
Vibhor Bhatt, Prasad Jayanti
Dartmouth TR2010-662

Abstract: We study Reader-Writer Exclusion, a well-known variant of the Mutual Exclusion problem where processes are divided into two classes--readers and writers--and multiple readers can be in the Critical Section (CS) at the same time, although no process may be in the CS at the same time as a writer. Since readers don't conflict with each other, they should not obstruct each other. Specifically, the concurrent entering property must be satisfied: if all writers are in the remainder section, each reader should be able to enter the CS in a bounded number of its own steps. Three versions of the Reader-Writer Exclusion problem are commonly studied--one where writers have priority over readers, another where readers have priority, and the last where neither class has priority over the other and no process may starve.

To ensure high performance on Cache-Coherent (CC) and Distributed Shared Memory (DSM) multiprocessors, algorithms should be designed to generate as few remote memory references (RMRs) as possible. The ideal would be to achieve constant RMR complexity, i.e., the worst case number of RMRs that a process generates in order to enter and exit the CS once is a constant, independent of the number of processes.

Constant RMR complexity algorithms have existed for Mutual Exclusion for two decades, but none exists for Reader-Writer Exclusion. Danek and Hadzilacos' lower bound proof implies that it is impossible to achieve sublinear RMR complexity for DSM machines. For CC machines, the best existing bound, also due to Danek and Hadzilacos , is O(log n), where n is the number of processes. In this work, we present the first constant RMR complexity algorithms for all three versions of the Reader-Writer Exclusion problem (for CC machines).

Note: Submitted to the Proceedings of the Twenty-Ninth annual symposium on Principles of distributed computing (PODC 2010).


PDF PDF (240KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Vibhor Bhatt and Prasad Jayanti, "Constant RMR Solutions to Reader Writer Synchronization." Dartmouth Computer Science Technical Report TR2010-662, February 2010.


Notify me about new tech reports.

Search the technical reports.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu


Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.