Browse Prior Art Database

SCHEDULING TASKS WITH CRITICAL SECTIONS

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

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 knows, however, about the effect of such synchronization constraints on system performance. This paper investigates the deterministic sche-duling of tasks with s critical sections on a multiprocessor system. The worst-case bound is established for an arbitrary demand scheduling strategy when only one task at a time may eater a single critical sec tion. The bound is also derived when several tasks may enter the same critical section simultaneously.

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

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SCHEDULING TASKS WITH CRITICAL SECTIONS

by Dennis Kafura

Technical Report: # 76-3 March, 1976

Scheduling Tasks with Critical Sections

Dennis Kafura

Computer Science Department Iowa State University Ames, Iowa 50011

ABSTRACT

A .variety of techniques have been developed to correctly synchronize the use of shared, critical sections by concurrent processes. Little is knows, however, about the effect of such synchronization constraints on system performance. This paper investigates the deterministic sche-duling of tasks with s critical sections on a multiprocessor system. The worst-case bound is established for an arbitrary demand scheduling strategy when only one task at a time may eater a single critical sec tion. The bound is also derived when several tasks may enter the same critical section simultaneously.

I. INTRODUCTION

The deterministic multiprocessor model presented by Graham [1,2] has been extended in a variety of ways. These extensions include: increasing the power of the processors [3-5], adding one or more non-processor re= sources [6-9], using other performance measures [10-121, and applying more sophisticated heuristic scheduling methods [13,14]. In these investiga-tions possible mutual cooperation and/or exclusion of tasks has not been considered. Research in operating and software systems design has shown, however, that an important role is played by such processes [IS,lb):. While powerful tools have been developed to enforce legitimate sequencing [17,18], little is knows about the effect of these mechanisms on system performance. This paper uses deterministic methods to analyze a system processing tasks which may, via critical sections (semaphores, monitors), impose dynamic constraints on the parallel execution of other talks attempting to enter the same critical section.

II. MODEL

The processing system consists of m processors,

(Equation Omitted)

criti-cal sections,

Iowa State University Page 1 Dec 31, 1976

Page 2 of 9

SCHEDULING TASKS WITH CRITICAL SECTIONS

(Equation Omitted)

and a set of n tasks,

(Equation Omitted)

These tasks compete for use of the processors and entry into the critical sections: The task execution sequences are constrained in two ways: (1) no two tasks may be executing in the same critical section at the same time, and (2) a pre-cedence constraint,

(Equation Omitted)

cannot begin in any valid schedule until Ti has completed. Ti is called a predecessor of T J: Each task is described by a sequence of pairs. The pair (Ci,t) indicates that the next t processor time units executed by this task must be executed while the task has exclusive use of critical section Ci. Similarly, the pair. (P,t) indicates that the next t time units can be. executed by the task without the use of any critical section. Each task may request any number of different critical sections any number of times. An example of several tasks is presented in Figure ~. For ...