Generational Thread Scheduler

Abstract

Disclosed herein is a generational thread scheduler. One embodiment may be used with processor multithreading logic to execute threads of executable instructions, and a shared resource to be allocated fairly among the threads of executable instructions contending for access to the shared resource. Generational thread scheduling logic may allocate the shared resource efficiently and fairly by granting a first requesting thread access to the shared resource allocating a reservation for the shared resource to each other requesting thread of the executing threads and then blocking the first thread from re-requesting the shared resource until every other thread that has been allocated a reservation, has been granted access to the shared resource. Generation tracking state may be cleared when each requesting thread of the generation that was allocated a reservation has had their request satisfied.

What is claimed is: 
     
         1 . A method for sharing a resource in a multiprocessing system, the method comprising:
 receiving, from a first plurality of requesting entities in a processor, requests for a shared resource;   granting a first entity of the first plurality of requesting entities access to the shared resource;   allocating a reservation to other entities of the first plurality of requesting entities for the shared resource; and   blocking the first entity from re-requesting the shared resource at least until each entity of the first plurality of requesting entities has been granted access to the shared resource.   
     
     
         2 . The method of  claim 1  further comprising:
 granting a second entity of the first plurality of requesting entities access to the shared resource; and 
 blocking the second entity from re-requesting the shared resource at least until each entity of the first plurality of requesting entities has been granted access to the shared resource. 
 
     
     
         3 . The method of  claim 2  further comprising:
 allocating a reservation to each entity of a second plurality of requesting entities for the shared resource; and 
 blocking the first and second entity from re-requesting the shared resource at least until each entity of the second plurality of requesting entities has been granted access to the shared resource. 
 
     
     
         4 . An article of manufacture comprising:
 a machine-accessible medium including data and instructions for allocating a shared resource among a plurality of entities such that, when accessed by a machine, cause the machine to:
 grant a first requesting entity of the plurality of entities access to the shared resource; 
 allocate a reservation for the shared resource to each requesting entity of the first plurality of entities; and 
 block the first entity from re-requesting the shared resource at least until no entity of the plurality of entities has been allocated a reservation but has not yet been granted access to the shared resource. 
   
     
     
         5 . The article of manufacture of  claim 4 , said machine-accessible medium including data and instructions that, when accessed by a machine, cause the machine to:
 grant a second requesting entity of the plurality of entities access to the shared resource; and   block the first and second entities from re-requesting the shared resource at least until there are none of the plurality of entities that, after being allocated a reservation, were not then granted access to the shared resource.   
     
     
         6 . The article of manufacture of  claim 5 , said machine-accessible medium including data and instructions that, when accessed by a machine, cause the machine to:
 allocate a reservation for the shared resource to each requesting entity of the plurality of entities that has not already been granted access to the shared resource; and   clear a first state variable when each entity of the plurality of entities that was allocated a reservation has had their request satisfied.   
     
     
         7 . A processor comprising:
 multithreading logic to execute a plurality of threads of executable instructions;   a shared resource to be allocated fairly among threads of the plurality of threads of executable instructions contending for access to the shared resource;   a thread scheduling logic to allocate the shared resource among the plurality of threads of executable instructions by:
 granting a first requesting thread of the plurality of threads of executable instructions access to the shared resource; 
 allocating a reservation for the shared resource to requesting threads of the first plurality of threads of executable instructions; and 
 blocking the first thread from re-requesting the shared resource at least until every thread of the plurality of threads of executable instructions that has been allocated a reservation, has had their request satisfied. 
   
     
     
         8 . The processor of  claim 7 , said thread scheduling logic to further allocate the shared resource among the plurality of threads of executable instructions by:
 granting a second requesting thread of the plurality of threads of executable instructions access to the shared resource; and   blocking the first and second thread from re-requesting the shared resource at least until every thread of the plurality of threads of executable instructions that has been allocated a reservation, has been granted access to the shared resource.   
     
     
         9 . The processor of  claim 7 , said thread scheduling logic to further allocate the shared resource among the plurality of threads of executable instructions by:
 blocking all threads from re-requesting the shared resource until every thread of the plurality of threads of executable instructions that has been allocated a reservation, has been granted access to the shared resource.   
     
     
         10 . The processor of  claim 7 , said thread scheduling logic to further allocate the shared resource among the plurality of threads of executable instructions by:
 allocating a reservation for the shared resource to each requesting thread of the plurality of threads of executable instructions that has not already been granted access to the shared resource; and   clearing a first state variable for each thread of the plurality of threads of executable instructions that has been allocated a reservation if it has been granted access to the shared resource.   
     
     
         11 . The processor of  claim 10 , said thread scheduling logic to further allocate the shared resource among the plurality of threads of executable instructions by:
 maintaining the first state variable for each thread of the plurality of threads of executable instructions having an outstanding or completed request, until every thread that has been allocated a reservation, has been granted access to the shared resource.   
     
     
         12 . A processor comprising:
 simultaneous multithreading logic to execute a plurality of threads of executable instructions;   one or more cache memories to store a copy of one or more portions of data and/or executable instructions from an addressable memory, at least in part through the use of a shared resource;   a finite-state machine for allocating the shared resource among the plurality of threads of executable instructions, said finite-state machine to:
 grant a first requesting thread of the plurality of threads of executable instructions access to the shared resource; 
 allocate a reservation for the shared resource to requesting threads of the first plurality of threads of executable instructions; and 
 block the first thread from re-requesting the shared resource at least until no thread of the plurality of threads of executable instructions has been allocated a reservation but has not been granted access to the shared resource. 
   
     
     
         13 . The processor of  claim 12 , said finite-state machine to:
 block all threads from re-requesting the shared resource until every thread of the plurality of threads of executable instructions that has been allocated a reservation, has also been granted access to the shared resource.   
     
     
         14 . The processor of  claim 12 , said finite-state machine to:
 allocate a reservation for the shared resource to each requesting thread that has not already been granted access to the shared resource; and   clear a first state variable for each thread that has been allocated a reservation if it has been granted access to the shared resource.   
     
     
         15 . The processor of  claim 14 , said finite-state machine to:
 maintain the first state variable for each thread having an outstanding or completed request, until every thread that has been allocated a reservation, has been granted access to the shared resource.   
     
     
         16 . A computing system comprising:
 an addressable memory to store data and also to store executable instructions;   one or more cache memories to store a copy of one or more portions of the data and/or the executable instructions stored in the addressable memory, at least in part through the use of a shared resource;   a multiprocessor including simultaneous multithreading logic to execute a plurality of threads of executable instructions, the multiprocessor operatively coupled with the addressable memory and including a finite-state machine for allocating the shared resource among the plurality of threads of executable instructions, said finite-state machine to:
 grant a first requesting thread of the plurality of threads of executable instructions access to the shared resource; 
 allocate a reservation for the shared resource to requesting threads of the first plurality of threads of executable instructions; and 
 block the first thread from re-requesting the shared resource at least until no thread of the plurality of threads of executable instructions has been allocated a reservation but has not yet been granted access to the shared resource. 
   
     
     
         17 . The computing system of  claim 16 , said finite-state machine to:
 allocate a reservation for the shared resource to each requesting thread that has not already been granted access to the shared resource; and   clear a first state variable for each thread that has been allocated a reservation if it has been granted access to the shared resource.   
     
     
         18 . The computing system of  claim 17 , said finite-state machine to:
 maintain the first state variable for each thread having an outstanding or completed request, until every thread that has been allocated a reservation, has been granted access to the shared resource.   
     
     
         19 . The computing system of  claim 16 , finite-state machine to:
 grant a second requesting thread of the plurality of threads of executable instructions access to the shared resource; and   block the first and second thread from re-requesting the shared resource at least until every thread of the plurality of threads of executable instructions that has been allocated a reservation, has been granted access to the shared resource.   
     
     
         20 . The computing system of  claim 19 , said finite-state machine to:
 block all threads from re-requesting the shared resource until every thread of the plurality of threads of executable instructions that has been allocated a reservation, has also been granted access to the shared resource.