Browse Prior Art Database

TASK SCHEDULING WITH CRITICAL SECTION CONSTRAINTS

IP.com Disclosure Number: IPCOM000127992D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 14 page(s) / 41K

Publishing Venue

Software Patent Institute

Related People

Dennis Kafura: AUTHOR [+3]

Abstract

A variety of techniques have been developed to correctly synchronize the use of shared, critical sections by concurrent processes. Little is known, however, about the effect of such synchronization constraints on system performance. This paper characterizes the performance of parallel processing systems where concurrent tasks compete for the use of s critical sections. The effect of allowing multiple entries to the same critical section (general semaphores) and/or allowing a single task to simultaneously request entry to several critical section is specifically examined. Both non-preemptive and preemptive systems are considered. The results are expressed as a limit on performance relative to the optimal.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

TASK SCHEDULING WITH CRITICAL SECTION CONSTRAINTS

by

Dennis Kafura

Technical Report #76-11 October 1976

Task Scheduling with Critical Section Constraints

Dennis Kafura Computer Science Department Iowa State University Ames, Iowa 50010

ABSTRACT

A variety of techniques have been developed to correctly synchronize the use of shared, critical sections by concurrent processes. Little is known, however, about the effect of such synchronization constraints on system performance. This paper characterizes the performance of parallel processing systems where concurrent tasks compete for the use of s critical sections. The effect of allowing multiple entries to the same critical section (general semaphores) and/or allowing a single task to simultaneously request entry to several critical section is specifically examined. Both non-preemptive and preemptive systems are considered. The results are expressed as a limit on performance relative to the optimal.

I. INTRODUCTION

Innovations in hardware and software technology have led to continuing interest in parallel processing systems. The performance of multiprocessor and network organizations has been analyzed at various level of detail arid from different perspectives [1-61 . Recent studies have attempted to establish broad analytical results which require only minimal assumptions [7-91. This paper uses the techniques of deterministic analysis [10-151 to derive general per-formance measures for a parallel processing system which explicitly models the competition for shared, critical sections. Research in operating and software systems has shown that an important role is played by the mutual exclusion of cooperating processes with respect to a shared, critical section [16,17]. These critical sections may be used, for example, to grant access to limited system resources, to synchronize the timing of asynchronous processes, or to regulate the manipulation of common data structures or data bases. While powerful tools have been developed to enforce legitimate sequencing [18,19], little is known about the effect of these mechanisms on system performance. One brief consideration of this problem has been presented [20]. The model developed below will focus on a system which processes tasks capable, via semaphores, monitors, etc., of imposing dynamic constraints on the parallel execution of other tasks attempting to enter the same critical section. The analysis of this model avoids dependence on statisitical assumptions regarding the task's resource demands. They are not assumed to be Poisson distributed. The results are also not conditioned on the state of the system. The system need not be in a steady state. Instead, each task is required only to have invariant resource demands which, for example, do not depend on the time of execution or the demands of other tasks. The processing system is assumed not to delay the execution of

Iowa Stat...