Browse Prior Art Database

Fast Method for Simultaneous Exclusive Table Modifications

IP.com Disclosure Number: IPCOM000040291D
Original Publication Date: 1987-Oct-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Earnst, R: AUTHOR [+2]

Abstract

This article describes a method for providing exclusive, synchronized updating of an operating system process table without requiring exclusive use of the process table, therefore allowing multiple processes and processors simultaneous access to the system process table. By doing so, system contention over the process table is eliminated, thus providing a substantial overall system performance improvement. Whenever processes in a system modify shared data, there is a potential problem in concurrently updating such data. The data must be accessed and modified by each process is such a way that its validity does not depend on the order or synchronization of the processes.

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

Page 1 of 3

Fast Method for Simultaneous Exclusive Table Modifications

This article describes a method for providing exclusive, synchronized updating of an operating system process table without requiring exclusive use of the process table, therefore allowing multiple processes and processors simultaneous access to the system process table. By doing so, system contention over the process table is eliminated, thus providing a substantial overall system performance improvement. Whenever processes in a system modify shared data, there is a potential problem in concurrently updating such data. The data must be accessed and modified by each process is such a way that its validity does not depend on the order or synchronization of the processes. The general solution is to provide access to data to a process (mutual exclusion) while executing a critical section of code, and ensuring orderly access to the data among processes (process synchronization) In an operating system such as UNIX*, most system data is shared among processes, creating a high probability for concurrency problems in the shared system data. The traditional, single-processor UNIX operating system environment prevents such currency problems by implementing interrupt routines such that these interrupt routines execute within the executing process's environment. When necessary, exclusive access to data structures may be maintained when a process is inactive through the implementation of simple lock bits. These concurrency algorithms must be extended when UNIX is implemented on large multi-processor hardware configurations for two reasons: First, a process may be arbitrarily blocked at any point (due to page fault, end of time slice, etc.) and another process given the processor. Second, in a multi-processor configuration several processes can be executing simultaneously. In the prior art, concurrency control on large multi-processor hardware configurations was to implement extended process synchronization and mutual exclusion within the UNIX kernel, using semaphores with P and V operators. The question posed in implementing P and V operators with the kernel is: at what level should mutual exclusion be provided on resources? The prior-art implementation of P and V within the kernel was based on providing mutual exclusion, in general, only on those resources which required mutual exclusion. The premise behind this strategy is to limit the scope of process blockage caused by the unavailability of specific resources. This prior art is inadequate because it simply reduces the scope of the contention and does not eliminate it. Where a major operating system resource requires mutual exclusion, sufficient contention still occurs and can result in substantial performance degrada tion. In a multi-processor environment, the reduction in scope is diminished because a process holding a resource executing on one processor can effectively block access to all the other processors to that resource. Su...