Spin-yielding in multi-threaded systems

• US 7,234,143 B2
• Filed: 06/20/2002
• Issued: 06/19/2007
• Est. Priority Date: 06/20/2002
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Venkatasubramanian, Lakshminarayanan
• Primary Examiner(s): An; Meng-Al T.
• Assistant Examiner(s): Tang; Kenneth
• Application Number:
  US10/177,453
• Publication Number:
  US 20030236816A1
• Time in Patent Office: 1,825 Days
• Field of Search: 718/100, 718/102, 718/104, 718107-108, 710/200
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Techniques are provided for use in spin-yielding in multi-threaded systems. Each thread that is waiting for a lock is bound to a spin-yield processor in the list of a plurality of spin-yield processors so that other processors that otherwise may be used for spin-yield cycles by the waiting threads can be used for other purposes by other threads. Further, in a defined time period, a thread is bound to or removed from a spin-yield processor based on the number of context switches experienced by that thread in that defined time period.

Claims

1. A method for use in a multi-threaded system, comprising the steps of:

dedicating a processor identified as a spin-yield processor to run a thread while the thread is waiting for a lock acquired by another thread;

a first thread acquiring a first lock to run a program portion on a first processor, wherein running the program portion requires the first lock; and

a second thread, while waiting to acquire the first lock based on a relationship between a context switching threshold and a number of context switches experienced by the second thread within a first defined time period, performs the steps of;

running on the spin-yield processor;

trying to acquire the first lock, wherein the second thread acquires the first lock if the first thread yields the first processor; and

if the second thread does not acquire the first lock, then the second thread repeats the steps of running and trying;

wherein the second thread, before running on the spin-yield processor the first time, performs the steps of;

running on the first processor; and

trying to acquire the first lock;

if the second thread does not acquire the first lock, then the second thread repeats the steps of running on the first processor and trying to acquire the first lock.

2. The method of claim 1 wherein the second thread repeats the steps of running and trying for a second defined time period.

3. The method of claim 1 wherein the second thread repeats the steps of running on the first processor and trying to acquire the first lock for a second defined time period.

4. The method of claim 1 wherein, if the second thread does not acquire the first lock, then the second thread performs the further step of yielding the spin-yield processor.

5. The method of claim 1 wherein the spin-yield processor is selected from a plurality of processors dedicated for running waiting threads.

6. The method of claim 1 wherein, each time the second thread runs on the spin-yield processor, the spin-yield processor is selected from a plurality of processors dedicated for running waiting threads.

7. The method of claim 1 further comprising the step of allowing a third thread to run on the spin-yield processor based on a number of context switches that the third thread experiences in a second defined time period.

8. The method of claim 1 wherein the second thread quits running on the spin-yield processor based on a number of context switches that the second thread experiences in a second defined time period.

9. A system comprising:

a processor dedicated to run a thread that is waiting for a lock acquired by another thread;

the processor being identified as a spin-yield processor;

a first thread acquiring a first lock to run a program portion on a first processor, wherein running the program portion requires the first lock; and

a second thread, while waiting to acquire the first lock based on a relationship between a context switching threshold and a number of context switches experienced by the second thread within a first defined time period, performs the steps of;

running on the spin-yield processor

trying to acquire the first lock, wherein the second thread acquires the first lock if the first thread yields the first processor; and

if the second thread does not acquire the first lock, then the second thread repeats the steps of running and trying;

wherein the second thread, before running on the spin-yield processor the first time, performs the steps of;

running on the first processor; and

trying to acquire the first lock;

if the second thread does not acquire the first lock, then the second thread repeats the steps of running on the first processor and trying to acquire the first lock.

10. The system of claim 9 wherein the second thread repeats the steps of running and trying for a second defined time period.

11. The system of claim 9 wherein, if the second thread repeats the steps of running on the first processor and trying to acquire the first lock for a second defined time period.

12. The system of claim 9 wherein, if the second thread does not acquire the first lock, then the second thread performs the further step of yielding the spin-yield processor.

13. The system of claim 9 wherein the spin-yield processor is selected from a plurality of processors dedicated for running waiting threads.

14. The system of claim 9 wherein, each time the second thread runs on the spin-yield processor, the spin-yield processor is selected from a plurality of processors dedicated for running waiting threads.

15. The system of claim 9 further comprising a third thread that runs on the spin-yield processor based on a number of context switches that the third thread experiences in a second defined time period.

16. The system of claim 9 wherein the second thread quits running on the spin-yield processor based on a number of context switches that the second thread experiences in a second defined time period.

17. A computer-readable medium wherein said computer readable medium is a medium selected from the group consisting of a floppy disk, a hard disk, a zip-drive cartridge, a magnetic tape, a magnetic medium, a DC-ROM, a CD-RAM, a DVD-ROM, a DVD-RAM, an optical medium, a paper tape, a punch card, a pattern of holes, a RAM, a ROM, an EPROM, a memory chip, and a memory cartridge, said computer readable medium embodying instructions for use in a multi-threaded system, the instructions performing the steps of:

defining a time period;

determining a number of context switches experienced by a thread during the defined time period, wherein the thread is waiting for a lock acquired by another thread; and

based on a relationship between a context switch threshold and the number of context switches, if the thread has not been bound to a spin-yield processor then binding the thread to the spin-yield processor, else if the thread has been bound to the spin-yield process, then unbinding the thread from the spin-yield processor;

wherein the spin-yield processor is a processor being dedicated to run the thread, wherein the thread acquires the lock if the other thread yields the lock;

wherein the other thread, before running on the spin-yield processor the first time, performs the steps of;

running on a first processor; and

trying to acquire the lock;

if the other thread does not acquire the lock, then the other thread repeats the steps of running on the first processor and trying to acquire the lock.

18. The computer-readable medium of claim 17 wherein a context switch is initiated by the thread.

19. The computer-readable medium of claim 17 wherein a context switch is initiated by an operating system running the thread or by a unit other than the thread.

20. The computer-readable medium of claim 17 wherein the spin-yield processor is selected from a plurality of processors.