System and method for queue-less enforcement of queue-like behavior on multiple threads accessing a scarce resource

• US 8,341,636 B2
• Filed: 11/12/2004
• Issued: 12/25/2012
• Est. Priority Date: 03/14/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wilhelm, George William Jr.
• Primary Examiner(s): To, Jennifer
• Assistant Examiner(s): Kawsar, Abdullah Al
• Application Number:
  US10/988,047
• Publication Number:
  US 20050091656A1
• Time in Patent Office: 2,965 Days
• Field of Search: 707/5, 707/9, 707/200, 707/206, 718/1, 718/100, 718/102, 718/103, 718/104, 718/105, 718/101
• US Class Current: 718/104
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A system and method for managing simultaneous access to a scarce or serially re-usable resource by multiple process threads. A stationary queue is provided, including a wait counter for counting the cumulative number of threads that have been temporarily denied the resource; a satisfied counter for counting the cumulative number of threads that have been denied access and subsequently granted access to said resource; a sleep code routine responsive to the wait counter for generating a run identifier; and a wakeup code routine responsive to the satisfied counter for generating the run identifier.

Claims

1. A digital data processing system, comprising:

at least one scarce or serially re-usable hardware resource;

a plurality of process threads requesting access to said hardware resource; and

a multi-tasking operating system supported by a hardware device driver for managing simultaneous access to said hardware resource by said plurality of process threads, said multi-tasking operating system maintaining a stationary queue for allocating access to said hardware resource amongst said threads one at a time in the exact order in which they began waiting for said resource wherein no data is moved into or out of said stationary queue;

wherein said stationary queue comprises;

a wait counter for counting the cumulative number of threads that have been temporarily denied access to said hardware resource; and

a satisfied counter for counting the cumulative number of threads that have been temporarily denied access to said hardware resource and subsequently granted access to said hardware resource;

wherein said multi-tasking operating system creates a block identifier of a blocked thread of said plurality of process threads placed on said stationary queue by adding a base value associated with said hardware resource to a value of said wait counter.

2. A method for managing simultaneous access to scarce or serially re-usable hardware resources by multiple process threads, comprising:

responsive to a request from a thread for a scarce or serially re-usable hardware resource which is not available, creating a block identifier that identifies said thread that has been temporarily denied the hardware resource;

incrementing a wait count of a wait counter in a stationary queue based upon the block identifier, wherein no data is moved into or out of said stationary queue, wherein creating a block identifier comprises adding a base value associated with the hardware resource to said wait count; and

blocking said temporarily denied thread while the sum of said base value associated with the hardware resource and a run count of a run counter does not correspond to said block identifier, said run count being incremented responsive to each instance of said scarce or serially re-usable hardware resource becoming available, thereby enabling subsequent wake up of said temporarily denied thread identified by said block identifier, so that said temporarily denied thread is serviced in the exact FIFO order in which said temporarily denied thread began waiting for said hardware resource.

3. A method for managing simultaneous access to scarce or serially re- usable hardware resources by multiple process threads, comprising:

responsive to a scarce or serially re-usable hardware resource becoming available, creating one or more run identifiers that identify threads that have been first temporarily denied access to the resource but have been subsequently allowed access;

locating at least one block identifier in a stationary queue that is similar to at least one run identifier, said block identifier identifying at least one thread that has been temporarily denied access to the resource, wherein no data is moved into or out of said stationary queue;

awakening and running said temporarily denied thread identified by both said block identifier and by said run identifier, thereby granting said temporarily denied thread access to said hardware resource in the exact FIFO order in which said temporarily denied thread began waiting for said hardware resource;

wherein said block identifier is generated by adding a wait count to a base value associated with the hardware resource, said wait count representing the cumulative number of threads that have been temporarily denied access to said hardware resource; and

wherein creating a run identifier comprises adding said base value associated with the hardware resource to a satisfied count contained in a satisfied counter, said satisfied count representing the cumulative number of threads that have been temporarily denied access to said hardware resource and subsequently granted access to said hardware resource.

4. A method for managing simultaneous access to scarce or serially re- usable hardware resources by multiple process threads, comprising:

responsive to a request for a scarce or serially re-usable hardware resource which is not available,

creating a block identifier identifying a thread that has been temporarily denied said resource; and

adding said block identifier to a stationary queue by incrementing a wait count of a wait counter in said stationary queue, wherein no data is moved into or out of said stationary queue; and

blocking said thread identified by said block identifier;

wherein creating a block identifier comprises adding a base value associated with the hardware resource to said wait count; and

responsive to said hardware resource becoming available,

creating a run identifier identifying a thread that has been temporarily denied said resource but subsequently allowed access to said resource; and

locating said block identifier in said stationary queue that is similar to said run identifier; and

awakening and running a next thread relative to said thread identified by both said block identifier and said run identifier in the exact FIFO order in which said next thread began waiting for said resource;

wherein creating a run identifier comprises adding said base value associated with the hardware resource to a satisfied count contained in a satisfied counter,

said satisfied count representing the cumulative number of threads that have been temporarily denied access to said hardware resource and subsequently granted access to said hardware resource.

5. A hardware memory device storing code for controlling the operation of a computer for managing simultaneous access to scarce or serially re-usable hardware resources by multiple process threads, wherein the code when executed by the computer performs a method comprising:

responsive to a request for a scarce or serially re-usable hardware resource which is not available,

creating a block identifier identifying a thread that has been temporarily denied said resource; and

adding said block identifier to a stationary queue by incrementing a wait count of a wait counter in said stationary queue, wherein no data is moved into or out of said stationary queue; and

blocking said thread identified by said block identifier;

wherein creating a block identifier comprises adding a base value associated with the hardware resource to said wait count; and

responsive to said hardware resource becoming available,

creating a run identifier identifying a thread that has been temporarily denied said resource but subsequently allowed access to said resource; and

locating said block identifier in said stationary queue that is similar to said run identifier; and

awakening and running a next thread relative to said thread identified by both said block identifier and said run identifier in the exact FIFO order in which said next thread began waiting for said resource;

wherein creating a run identifier comprises adding said base value associated with the hardware resource to a satisfied count contained in a satisfied counter, said satisfied count representing the cumulative number of threads that have been temporarily denied access to said hardware resource and subsequently granted access to said hardware resource.