Browse Prior Art Database

Minimizing Apparent Processor Deadlock

IP.com Disclosure Number: IPCOM000119828D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 2 page(s) / 75K

Publishing Venue

IBM

Related People

Wottreng, PM: AUTHOR

Abstract

A simple method for minimizing "apparent processor deadlock" (a common CPU resource scheduling problem) is disclosed. "Apparent processor deadlock" consists of a low priority task holding a resource that a high priority task is requesting, but the holder is unable to obtain CPU resources due to higher priority tasks consuming all the CPU processor cycles.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Minimizing Apparent Processor Deadlock

      A simple method for minimizing "apparent processor
deadlock" (a common CPU resource scheduling problem) is disclosed.
"Apparent processor deadlock" consists of a low priority task holding
a resource that a high priority task is requesting, but the holder is
unable to obtain CPU resources due to higher priority tasks consuming
all the CPU processor cycles.

      This method does not solve all instances of the problem, but
appears to be a "cost-effective" answer to the problem.  The design
requires 2 special tasks - T1 and T2 (T1 is the highest priority and
T2 is the lowest priority in the system).  T1 wakes periodically
(say, 3 minutes) and inspects the state of T2; if T2 is waiting on
its normal semaphore from T1, then the system is presumed to be safe,
i.e., not in a deadlock.  T1 would then send the semaphore to T2 and
wait for the next 3 minutes.  The inference is that if T2 was able to
get some cycles, then no task was waiting for cycles (for the entire
period) while holding a resource.

      If T1 wakes and sees that T2 has not received the semaphore
(which means that T2 is currently on the task dispatcher list,
waiting for processor cycles), then it "infers" that there is a
potential deadlock scenario and begins to take action to alleviate
the problem:  every 1/4 second it awakes and inspects and removes
progressively more tasks at the top of the task dispatching list
until T2 finally gets some cycles and receives its semaphore.  T1
then moves all the tasks it had removed from the task dispatching
list back to the list; sends the semaphore to T2; and waits the
nor...