Browse Prior Art Database

Lock priority boosting in an MP system with multiple run queues

IP.com Disclosure Number: IPCOM000014824D
Original Publication Date: 2001-Jan-01
Included in the Prior Art Database: 2003-Jun-20
Document File: 1 page(s) / 36K

Publishing Venue

IBM

Abstract

Disclosed is an approach for lock priority boosting in a computer operating system with multiple dispatching, or "run," queues. In a single run queue system, lock priority boosting temporarily grants the better numerical priority of a presumed higher priority thread waiting for a lock to the lower priority thread holding the lock. In a system where dispatching priority is a function of recent cpu utilization, the priority calculated for any given thread is as much a function of the individual thread's behavior as it is of the amount of competition for the cpu by other threads sharing the same run queue. On such a system, then, it would be a mistake to simply transfer numerical priorities between run queues in an implementation of lock priority boosting. To better accomplish lock priority boosting in a multiple run queue system, we must determine if the thread waiting for any given look is assigned to the same run queue as the thread holds that lock. If so, the simple priority transference used by a single run queue system is adequate. However, if the two threads are assigned to different run queues, the priority of the lock holder should instead be increased to the best of its current priority, the waiter's priority, and the priority of the thread that is currently executing on the cpu served by the holder's run queue. (Assuming that only one cpu serves a run queue.) This transfers the desired benefit to the lock holder: its priority should be at least sufficient to cause it to run on its cpu, since the waiter's priority was similarly sufficient. 1

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

Page 1 of 1

Lock priority boosting in an MP system with multiple run queues

Disclosed is an approach for lock priority boosting in a computer operating system with multiple dispatching, or "run," queues. In a single run queue system, lock priority boosting temporarily grants the better numerical priority of a presumed higher priority thread waiting for a lock to the lower priority thread holding the lock. In a system where dispatching priority is a function of recent cpu utilization, the priority calculated for any given thread is as much a function of the individual thread's behavior as it is of the amount of competition for the cpu by other threads sharing the same run queue. On such a system, then, it would be a mistake to simply transfer numerical priorities between run queues in an implementation of lock priority boosting.

To better accomplish lock priority boosting in a multiple run queue system, we must determine if the thread waiting for any given look is assigned to the same run queue as the thread holds that lock. If so, the simple priority transference used by a single run queue system is adequate. However, if the two threads are assigned to different run queues, the priority of the lock holder should instead be increased to the best of its current priority, the waiter's priority, and the priority of the thread that is currently executing on the cpu served by the holder's run queue. (Assuming that only one cpu serves a run queue.)

This transfers the desired benefi...