Accession Number : ADA290021

Title :   Scheduler-Conscious Synchronization.

Descriptive Note : Technical rept.,

Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Personal Author(s) : Kontothanassis, L. I. ; Wisniewski, R. W. ; Scott, M. L.

PDF Url : ADA290021

Report Date : DEC 1994

Pagination or Media Count : 49

Abstract : Efficient synchronization is important for achieving good performance in parallel programs, especially on large-scale multiprocessors. Most synchronization algorithms have been designed to run on a dedicated machine, with one application process per processor, and can suffer serious performance degradation in the presence of multipre gramming. Problems arise when running processes block or, worse, busy-wait for action on the part of a process that the scheduler has chosen not to run. In this paper we describe and evaluate a set of scheduler-conscious synchronization algorithms that perform well in the presence of multiprogramming while maintaining good performance on dedicated machines. We consider both large and small machines, with a particular focus on scalability, and examine mutual-exclusion locks, reader-writer locks, and barriers. The algorithms we study fall into two classes: those that heuristically determine appropriate behavior and those that use scheduler information to guide their behavior. We show that while in some cases either method is sufficient, in general sharing information across the kernel-user interface both eases the design of synchronization algorithms and improves their performance.

Descriptors :   *ALGORITHMS, *SCHEDULING, *SYNCHRONIZATION(ELECTRONICS), *MULTIPROGRAMMING, OPTIMIZATION, DEGRADATION, EFFICIENCY, PARALLEL PROCESSING, SHARING, MULTIPROCESSORS.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE