Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-10-22
2001-05-22
Treat, William M. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
06237089
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to data processors, and more particularly to affecting subsequent instruction processing in a data processor.
BACKGROUND OF THE INVENTION
As data processors are used more and more in real-time control systems, new techniques are required to ensure the efficient use of system resources. For example, in many multi-tasking systems, there are several tasks trying to share some of the same system resources, such as memory storage, a printer, or a port to a display screen. It is crucial in such multi-tasking systems that the shared system resources are used in the most efficient way possible. For example, if multiple tasks are sharing a resource, there must be a way to indicate which task is currently using the resource and whether that task is performing a function that must not be disturbed. Semaphores are used for this function in many multitasking systems.
Semaphores are a type of flag or status indicator that reflects the present status of a system resource. Usually the status information in a semaphore indicates whether or not the system resource is presently being used. In some multi-tasking systems, the semaphore may also include information about which task is using the resource, and possibly even the type of function being performed on the resource.
For example, a particular location in memory can be designated as the location of the semaphore for a shared variable X. If any task wants to use the shared variable X, that task must read the semaphore for the shared variable X by reading that particular location in memory. The variable X semaphore contains information on the status of the variable X, such as whether the variable X is currently reserved for exclusive access by a particular task. If the variable X semaphore indicates that the variable X is currently reserved and is thus busy, the new task must wait. The new task can continue to poll the variable X semaphore by periodically reading the variable X semaphore to see if the variable X is still being used or if it has become available.
Once the variable X semaphore indicates that the variable X is no longer reserved and thus available, the waiting task writes to the variable X semaphore to change its status to busy or nonavailable. The waiting task has thus effectively locked the variable X resource for its own use. No other tasks can use the variable X while the variable X's semaphore indicates that the variable X is being used. Once the waiting task has finished using the variable X, it writes a new value to the variable X semaphore location in order to change the variable X semaphore to indicate that the variable X is once again available.
There is a significant problem that arises in systems that use semaphores to allocate shared system resources. The problem arises when more than one task is polling the semaphore of a shared resource to see if the resource has become available yet. For example, assume task #1 and task #2 are both polling the variable X semaphore. Task #1 is the first to read the variable X semaphore after it has been changed to indicate that the variable X is available. Task #2 now reads the variable X semaphore and also learns that the variable X is available. Neither task #1 nor task #2 is aware that another task is competing for the use of the variable X.
If task #1 receives an interrupt, task #1 must execute a software interrupt routine before resuming where it left off. Meanwhile, task #2 writes a value to the variable X semaphore to indicate that the variable X is now busy. Task #2 then proceeds to use the variable X. Task #1 finishes its interrupt routine and resumes where it left off in its software program. Task #1 left off knowing that the variable X was available. Task #1 thus writes a value to the variable X semaphore to indicate that the variable X is now busy and then proceeds to try to use the variable X. But the variable X is already being used by Task #2. Thus a collision results. As a consequence, the variable X may be corrupted and tasks may receive the incorrect value of variable X. Thus, an approach is needed which allows multiple tasks to effectively and efficiently share common resources.
REFERENCES:
patent: 4236204 (1980-11-01), Groves
patent: 4259717 (1981-03-01), Nakamura
patent: 4435766 (1984-03-01), Haber et al.
patent: 4764893 (1988-08-01), Karabatsos
patent: 5283870 (1994-02-01), Joyce et al.
patent: 5301312 (1994-04-01), Christopher, Jr. et al.
patent: 5363506 (1994-11-01), Fukuoka
patent: 5471595 (1995-11-01), Yagi et al.
patent: 5579505 (1996-11-01), Ohkami
patent: 5581745 (1996-12-01), Muraoka et al.
patent: 5590380 (1996-12-01), Yamada et al.
patent: 5594880 (1997-01-01), Moyer
patent: 5615374 (1997-03-01), Sadoi et al.
patent: WO 91/20039 (1991-12-01), None
patent: WO 97/30391 (1997-08-01), None
David Mosberger, et al. “Implementing Atomic Sequences on Uniprocessors Using Rollforward,” Software-Practice and Experience, vol. 26(1), Jan. 23, 1996, pp. 1-23.
Brian N. Bershad “Practical Considerations for Non-Blocking Concurrent Objects,” © 1993 IEEE Computer Society Press, pp. 264-273.
Moyer William C.
Scott Jeffrey W.
Hill Susan C.
Motorola Inc.
Treat William M.
LandOfFree
Method and apparatus for affecting subsequent instruction... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for affecting subsequent instruction..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for affecting subsequent instruction... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2443191