Semaphore enhancement to improve system performance

Details Semaphore enhancement to improve system performance Semaphore enhancement to improve system performance

2000-05-17

2004-04-20

Follansbee, John (Department: 2126)

Electrical computers and digital processing systems: virtual mac

Task management or control

Process scheduling

C710S240000, C709S226000, C709S229000

Reexamination Certificate

active

06725457

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to an electronic system having a plurality of execution units requiring access to a shared resource, and more specifically to a method and apparatus for managing access to a resource that is shared by a plurality of execution units.
2. Description of the Prior Art
Semaphores are commonly used to enforce mutual exclusion rules for controlling access to shared resources in systems wherein a plurality of execution units, such as processing units and hardware engines, each require access to a shared resource. The shared resource is typically a memory space for storing information which may include a single bit of data, a byte, or a large data structure. The shared resources could also be the processing resources of a processing unit.
Computer operating systems (OS) commonly use semaphores in supervising software processes executed by a central processing unit (CPU), the processes functioning asynchronously and concurrently. Problems arise in an OS when concurrent processes attempt to use shared resources in an improperly synchronized manner. For example, it is generally necessary to prevent one process from writing to a shared resource while another process is reading from it. Semaphores generally serve as control flags for accessing the shared resource.
Another type of system for which semaphores are commonly used is a multiprocessing system which is a computer system having two or more processing units each executing an associated sequence of instructions, and each requiring access to a shared resource. A dedicated processing unit provides yet another example of a system for which semaphores have been used. A dedicated processing unit, such as a graphics processing unit, typically includes a plurality of execution units such as graphics engines, audio engines, video engines, and the like wherein groups of the execution units share resources.
FIG. 1A
shows a block diagram generally illustrating a first example of a conventional semaphore based resource sharing system at
10
, the system
10
including a plurality of processes
12
each requiring access to a shared resource
14
. The shared resource
14
, which is typically a portion of memory space, may be a system memory, a cache memory unit, a random access memory unit (RAM), a buffer, or a single register unit.
In the depicted example, a first process
12
designated PROCESS_
1
, and a second execution unit designated PROCESS_
2
each requires access to the shared resource
14
. Each of the processes
12
communicates with each other in accordance with a set of mutual exclusion rules in order to access the shared resource
14
asynchronously. For example, consider that while PROCESS_
2
is writing data to the shared resource
14
as illustrated by a line
16
, PROCESS_
1
needs to read data as illustrated by a line
18
. If PROCESS_
2
begins writing before PROCESS_
1
is done reading, PROCESS_
1
is likely to receive corrupted data.
The general rule for accessing the shared resource
14
in the system
10
is that only one of the processes
12
may write to the shared resource
14
at a time. Also, no process may read from the shared resource
14
while another process is writing. In accordance with one well-known resource sharing method, a semaphore
20
is used to indicate ownership of the resource
14
at an instance of time. The semaphore
20
is typically implemented as a semaphore value stored in memory (not shown) that can be accessed by each of the processes
12
. In the case of a computer system, the OS usually defines the rules for accessing the shared resources. Each type of OS may have different sets of rules for accessing a shared resource using a semaphore.
In the depicted example, PROCESS_
2
may claim ownership of the shared resource
14
by updating the value of the associated semaphore
20
if the semaphore
20
indicates that no process currently owns the shared resource. Thereafter, PROCESS_
2
may write to the shared resource. After PROCESS_
2
is done writing, PROCESS_
2
relinquishes ownership of the shared resource by updating the semaphore
20
with an appropriate value. PROCESS_
1
, which is operative to sample the semaphore as indicated by a line
24
, may subsequently determine that it may claim ownership of the resource, and eventually writes a value into the semaphore
20
to claim ownership. Note that the requirement that a process sample the semaphore can be problematic because time and processing power may be wasted. For example, if one of the processes
12
is a CPU, the CPU will “spin” while repetitively reading the semaphore in order to determine changes in ownership status.
FIG. 1B
shows a block diagram generally illustrating a second example of a conventional resource sharing system at
30
. In this example, a third process
12
designated PROCESS_
3
, and a fourth process
12
designated PROCESS_
4
both need to write data to the resource
14
at the same time. If PROCESS_
3
and PROCESS_
4
were to write data to the shared resource
14
at the same time, the result might be that the shared resource
14
would include corrupted data. Therefore, PROCESS_
4
may not write to the shared resource
14
as indicated by a line
32
while PROCESS_
3
is writing to the shared resource
14
as indicated by a line
34
. Likewise, a fifth process designated PROCESS_
5
may not read from the shared resource
14
as indicated by a line
36
while PROCESS_
3
is writing to the shared resource
14
.
FIG. 1C
shows a block diagram generally illustrating a third example of a conventional system at
30
including a sixth process designated PROCESS_
6
that is operative to write to the resource
14
, a seventh process
12
designated PROCESS_
7
operative to read from the resource, and an eighth process designated PROCESS_
8
operative to read from the resource. PROCESS_
7
and PROCESS_
8
may read from the resource
14
concurrently as indicated by lines
42
and
44
because data is not modified during reading, but only one process may write to the resource
14
at a time. However, while either or both of PROCESS_
7
and PROCESS_
8
is reading from the resource, PROCESS_
6
cannot write to the resource
14
as indicated by a line
46
.
Note that each shared resource must have a semaphore associated with it. If only one semaphore was to be used for two different shared resources, the method would fail. Also, note that any number of processes may share access to a resource. However, a semaphore associated with a particular shared resource must provide a range of values (or must have a number of bits) sufficient to provide a unique value associated with each process sharing access to the resource.
FIG. 2A
shows a block diagram generally illustrating a first conventional type of computer graphics system at
50
wherein a plurality of execution units share a resource. The system
50
includes: a CPU
52
; a system memory
54
coupled with the CPU via a bus
56
which may be a system bus or a local bus; a graphics engine
58
coupled with the bus via a first channel
60
; a disk controller
62
coupled with the bus via a second channel
64
; and an audio engine
66
coupled with the bus via a third channel
68
. Each of the channels
60
,
64
and
68
may be controlled via a programmed input/output (programmed I/O). Data is transferred to engines
58
,
62
, and
66
in accordance with a method wherein the CPU
52
writes instructions and data to each of the channels
60
,
64
, and
68
, and each of the engines reads instructions and data from the associated channel. The engines
58
,
62
, and
66
and the channels
60
,
64
and
68
provide a parallel I/O sub-system at
70
. Note that only one engine or process may access the system memory
54
via the bus at an instant of time.
Each of the channels
60
,
64
and
68
is typically a first-in first-out memory device (FIFO) including a dual-ported memory (not shown) having a semaphore built into it, the dual-ported memory providing a circular buffer using a “get

Affiliated with

Also associated with

Rating

Semaphore enhancement to improve system performance does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Semaphore enhancement to improve system performance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Semaphore enhancement to improve system performance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3197388