Method, apparatus and computer program product for...

Details Method, apparatus and computer program product for... Method, apparatus and computer program product for...

2006-06-20

2006-06-20

Thomson, William (Department: 2194)

Electrical computers and digital processing systems: virtual mac

Task management or control

Process scheduling

C718S107000, C370S395400

Reexamination Certificate

active

07065762

ABSTRACT:
The present invention includes a scheduling mechanism that fairly allocates a resource to a number of schedulable elements of which some are latency-sensitive. The invention tracks each element's use of the resource by determining the element's virtual time. An active element is selected from the elements that are ready to use the resource by determining the element that has the smallest effective virtual time. The effective virtual time is the element's actual virtual time modified by a borrowed virtual time value. When an element has a short-term need for the resource, it can borrow the privilege to run by borrowing virtual time. As the element uses the resource, it consumes virtual time according to its weight. When the elements are scheduled for the resource, the ready elements having the smallest virtual time is selected. The invention enforces long-term fairness to each element while allowing latency-sensitive elements to be preferably selected.

REFERENCES:
patent: 4131767 (1978-12-01), Weinstein
patent: 4161719 (1979-07-01), Parikh et al.
patent: 4316284 (1982-02-01), Howson
patent: 4397020 (1983-08-01), Howson
patent: 4419728 (1983-12-01), Larson
patent: 4424565 (1984-01-01), Larson
patent: 4437087 (1984-03-01), Petr
patent: 4438511 (1984-03-01), Baran
patent: 4439763 (1984-03-01), Limb
patent: 4445213 (1984-04-01), Baugh et al.
patent: 4446555 (1984-05-01), Devault et al.
patent: 4456957 (1984-06-01), Schieltz
patent: 4464658 (1984-08-01), Thelen
patent: 4499576 (1985-02-01), Fraser
patent: 4506358 (1985-03-01), Montgomery
patent: 4507760 (1985-03-01), Fraser
patent: 4532626 (1985-07-01), Flores et al.
patent: 4644532 (1987-02-01), George et al.
patent: 4646287 (1987-02-01), Larson et al.
patent: 4677423 (1987-06-01), Benvenuto et al.
patent: 4679189 (1987-07-01), Olson et al.
patent: 4679227 (1987-07-01), Hughes-Hartogs
patent: 4723267 (1988-02-01), Jones et al.
patent: 4731816 (1988-03-01), Hughes-Hartogs
patent: 4750136 (1988-06-01), Arpin et al.
patent: 4757495 (1988-07-01), Decker et al.
patent: 4763191 (1988-08-01), Gordon et al.
patent: 4769810 (1988-09-01), Eckberg, Jr. et al.
patent: 4769811 (1988-09-01), Eckberg, Jr. et al.
patent: 4771425 (1988-09-01), Baran et al.
patent: 4819228 (1989-04-01), Baran et al.
patent: 4827411 (1989-05-01), Arrowood et al.
patent: 4833706 (1989-05-01), Hughes-Hartogs
patent: 4835737 (1989-05-01), Herrig et al.
patent: 4879551 (1989-11-01), Georgiou et al.
patent: 4893306 (1990-01-01), Chao et al.
patent: 4903261 (1990-02-01), Baran et al.
patent: 4922486 (1990-05-01), Lidinsky et al.
patent: 4933937 (1990-06-01), Konishi
patent: 4960310 (1990-10-01), Cushing
patent: 4962497 (1990-10-01), Ferenc et al.
patent: 4962532 (1990-10-01), Kasirai et al.
patent: 4965767 (1990-10-01), Kinoshita et al.
patent: 4965772 (1990-10-01), Daniel et al.
patent: 4970678 (1990-11-01), Sladowski et al.
patent: 4979118 (1990-12-01), Kheradpir
patent: 4980897 (1990-12-01), Decker et al.
patent: 4991169 (1991-02-01), Davis et al.
patent: 5003595 (1991-03-01), Collins et al.
patent: 5014265 (1991-05-01), Hahne et al.
patent: 5020058 (1991-05-01), Holden et al.
patent: 5033076 (1991-07-01), Jones et al.
patent: 5034919 (1991-07-01), Sasai et al.
patent: 5054034 (1991-10-01), Hughes-Hartogs
patent: 5059925 (1991-10-01), Weisbloom
patent: 5072449 (1991-12-01), Enns et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5095480 (1992-03-01), Fenner
patent: RE33900 (1992-04-01), Howson
patent: 5115431 (1992-05-01), Williams et al.
patent: 5128945 (1992-07-01), Enns et al.
patent: 5136580 (1992-08-01), Videlock et al.
patent: 5166930 (1992-11-01), Braff et al.
patent: 5199049 (1993-03-01), Wilson
patent: 5206886 (1993-04-01), Bingham
patent: 5208811 (1993-05-01), Kashio et al.
patent: 5212686 (1993-05-01), Joy et al.
patent: 5224099 (1993-06-01), Corbalis et al.
patent: 5226120 (1993-07-01), Brown et al.
patent: 5228062 (1993-07-01), Bingham
patent: 5229994 (1993-07-01), Balzano et al.
patent: 5237564 (1993-08-01), Lespagnol et al.
patent: 5241682 (1993-08-01), Bryant et al.
patent: 5243342 (1993-09-01), Kattemalalavadi et al.
patent: 5243596 (1993-09-01), Port et al.
patent: 5247516 (1993-09-01), Bernstein et al.
patent: 5249178 (1993-09-01), Kurano et al.
patent: 5253251 (1993-10-01), Aramaki
patent: 5255291 (1993-10-01), Holden et al.
patent: 5260933 (1993-11-01), Rouse
patent: 5260978 (1993-11-01), Fleischer et al.
patent: 5268592 (1993-12-01), Bellamy et al.
patent: 5268900 (1993-12-01), Hluchyj et al.
patent: 5271004 (1993-12-01), Proctor et al.
patent: 5274631 (1993-12-01), Bhardwaj
patent: 5274635 (1993-12-01), Rahman et al.
patent: 5274643 (1993-12-01), Fisk
patent: 5280470 (1994-01-01), Buhrke et al.
patent: 5280480 (1994-01-01), Pitt et al.
patent: 5280500 (1994-01-01), Mazzola et al.
patent: 5283783 (1994-02-01), Nguyen et al.
patent: 5287103 (1994-02-01), Kasprzyk et al.
patent: 5287453 (1994-02-01), Roberts
patent: 5291482 (1994-03-01), McHarg et al.
patent: 5305311 (1994-04-01), Lyles
patent: 5307343 (1994-04-01), Bostica et al.
patent: 5309437 (1994-05-01), Perlman et al.
patent: 5311509 (1994-05-01), Heddes et al.
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5313582 (1994-05-01), Hendel et al.
patent: 5317562 (1994-05-01), Nardin et al.
patent: 5319644 (1994-06-01), Liang
patent: 5327421 (1994-07-01), Hiller et al.
patent: 5331637 (1994-07-01), Francis et al.
patent: 5345445 (1994-09-01), Hiller et al.
patent: 5345446 (1994-09-01), Hiller et al.
patent: 5359592 (1994-10-01), Corbalis et al.
patent: 5361250 (1994-11-01), Nguyen et al.
patent: 5361256 (1994-11-01), Doeringer et al.
patent: 5361259 (1994-11-01), Hunt et al.
patent: 5365524 (1994-11-01), Hiller et al.
patent: 5367517 (1994-11-01), Cidon et al.
patent: 5371852 (1994-12-01), Attanasio et al.
patent: 5386567 (1995-01-01), Lien et al.
patent: 5390170 (1995-02-01), Sawant et al.
patent: 5390175 (1995-02-01), Hiller et al.
patent: 5394394 (1995-02-01), Crowther et al.
patent: 5394402 (1995-02-01), Ross
patent: 5400325 (1995-03-01), Chatwani et al.
patent: 5408469 (1995-04-01), Opher et al.
patent: 5416842 (1995-05-01), Aziz
patent: 5422880 (1995-06-01), Heitkamp et al.
patent: 5422882 (1995-06-01), Hiller et al.
patent: 5423002 (1995-06-01), Hart
patent: 5426636 (1995-06-01), Hiller et al.
patent: 5428607 (1995-06-01), Hiller et al.
patent: 5430715 (1995-07-01), Corbalis et al.
patent: 5430729 (1995-07-01), Rahnema
patent: 5442457 (1995-08-01), Najafi
patent: 5442630 (1995-08-01), Gagliardi et al.
patent: 5452297 (1995-09-01), Hiller et al.
patent: 5473599 (1995-12-01), Li et al.
patent: 5473607 (1995-12-01), Hausman et al.
patent: 5477541 (1995-12-01), White et al.
patent: 5485455 (1996-01-01), Dobbins et al.
patent: 5490140 (1996-02-01), Abensour et al.
patent: 5490258 (1996-02-01), Fenner
patent: 5491687 (1996-02-01), Christensen et al.
patent: 5491804 (1996-02-01), Heath et al.
patent: 5497368 (1996-03-01), Reijnierse et al.
patent: 5504747 (1996-04-01), Sweasey
patent: 5509006 (1996-04-01), Wilford et al.
patent: 5517494 (1996-05-01), Green
patent: 5519704 (1996-05-01), Farinacci et al.
patent: 5519858 (1996-05-01), Walton et al.
patent: 5526489 (1996-06-01), Nilakantan et al.
patent: 5530963 (1996-06-01), Moore et al.
patent: 5535195 (1996-07-01), Lee
patent: 5539734 (1996-07-01), Burwell et al.
patent: 5541911 (1996-07-01), Nilakantan et al.
patent: 5546370 (1996-08-01), Ishikawa
patent: 5555244 (1996-09-01), Gupta et al.
patent: 5561669 (1996-10-01), Lenney et al.
patent: 5583862 (1996-12-01), Callon
patent: 5592470 (1997-01-01), Rudrapatna et al.
patent: 5598581 (1997-01-01), Daines et al.
patent: 5600798 (1997-02-01), Cherukuri et al.
patent: 5602770 (1997-02-01), Ohira
patent: 5604868 (1997-02-01), Komine et al.
patent: 5608726 (1997-03-01), Virgile
patent: 5617417 (1997-04-01), Sathe et al.
patent: 5617421 (1997-04-01), Chin et al.
patent: 5630125 (1997-05-01), Zellweger
patent: 5631908 (1997-05-01), Saxe
patent: 5632021 (1997-05-01), Jennings et al.
patent: 5634010 (1997-05-01), Ciscon et al.
patent: 5638359 (1997-06-01), Peltola et al.
patent: 5644718 (1997-07-01),

Affiliated with

Also associated with

Rating

Method, apparatus and computer program product for... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method, apparatus and computer program product for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, apparatus and computer program product for... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3640735