776:
105:
In multilevel processor sharing a finite set of thresholds are defined and jobs partitioned according to how much service they have received. The lowest level (containing jobs which have received the least service) has the highest priority and higher levels monotonically decreasing priorities. Within
85:
Generalized processor sharing is a multi-class adaptation of the policy which shares service capacity according to positive weight factors to all non-empty job classes at the node, irrespective of the number of jobs of each class present. Often it is assumed that the jobs within a class form a queue
32:
where the customers, clients or jobs are all served simultaneously, each receiving an equal fraction of the service capacity available. In such a system all jobs start service immediately (there is no queueing).
97:, generalized processor sharing is "an idealized scheduling algorithm that achieves perfect fairness. All practical schedulers approximate GPS and use it as a reference to measure fairness."
327:
616:
176:
533:
392:
604:
320:
80:
685:
574:
647:
490:
652:
457:
798:
779:
675:
462:
313:
87:
763:
558:
758:
548:
397:
281:
193:
131:
94:
61:
37:
589:
452:
579:
500:
419:
431:
286:
748:
728:
723:
495:
198:
753:
738:
705:
599:
247:
184:
154:
370:
743:
642:
553:
483:
267:"Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin"
172:
594:
538:
424:
291:
239:
230:
203:
146:
382:
611:
478:
336:
49:
621:
584:
680:
222:
792:
733:
718:
695:
507:
690:
517:
251:
158:
713:
670:
637:
414:
409:
404:
387:
377:
365:
360:
355:
350:
68:
57:
53:
436:
243:
512:
295:
266:
150:
207:
67:
The sojourn time jobs experience has no closed form solution, even in an
90:
basis, but this assumption is not necessary for many GPS applications.
130:
Aalto, S.; Ayesta, U.; Borst, S.; Misra, V.; Núñez-Queija, R. (2007).
29:
305:
309:
36:
The processor sharing algorithm "emerged as an idealisation of
40:
scheduling algorithms in time-shared computer systems".
223:"Sojourn time asymptotics in processor-sharing queues"
704:
663:
630:
567:
526:
471:
445:
343:
221:Borst, S.; Núñez-Queija, R.; Zwart, B. (2006).
18:Form of resource sharing for tasks in computing
177:"Time-shared Systems: A theoretical treatment"
321:
8:
139:ACM SIGMETRICS Performance Evaluation Review
60:) with a processor sharing discipline has a
106:each level an internal discipline is used.
48:A single server queue operating subject to
328:
314:
306:
285:
265:Li, T.; Baumberger, D.; Hahn, S. (2009).
197:
125:
123:
121:
119:
115:
7:
14:
775:
774:
86:and that queue is served on a
1:
605:Flow-equivalent server method
81:generalized processor sharing
75:Generalized processor sharing
26:egalitarian processor sharing
686:Adversarial queueing network
575:Continuous-time Markov chain
101:Multilevel processor sharing
648:Heavy traffic approximation
393:Pollaczek–Khinchine formula
815:
132:"Beyond processor sharing"
78:
772:
653:Reflected Brownian motion
458:Markovian arrival process
244:10.1007/s11134-006-7585-9
64:stationary distribution.
676:Layered queueing network
463:Rational arrival process
88:first-come, first-served
764:Teletraffic engineering
559:Shortest remaining time
296:10.1145/1594835.1504188
151:10.1145/1243401.1243409
759:Scheduling (computing)
398:Matrix analytic method
590:Product-form solution
491:Gordon–Newell theorem
453:Poisson point process
344:Single queueing nodes
208:10.1145/321386.321388
52:arrivals (such as an
617:Decomposition method
95:processor scheduling
749:Pipeline (software)
729:Flow control (data)
724:Erlang distribution
706:Information systems
496:Mean value analysis
274:ACM SIGPLAN Notices
754:Quality of service
739:Network congestion
600:Quasireversibility
580:Kendall's notation
185:Journal of the ACM
786:
785:
744:Network scheduler
643:Mean-field theory
554:Shortest job next
544:Processor sharing
501:Buzen's algorithm
484:Traffic equations
472:Queueing networks
446:Arrival processes
420:Kingman's formula
22:Processor sharing
806:
778:
777:
595:Balance equation
527:Service policies
425:Lindley equation
330:
323:
316:
307:
300:
299:
289:
271:
262:
256:
255:
231:Queueing Systems
227:
218:
212:
211:
201:
181:
169:
163:
162:
136:
127:
814:
813:
809:
808:
807:
805:
804:
803:
799:Queueing theory
789:
788:
787:
782:
768:
700:
659:
626:
612:Arrival theorem
563:
522:
479:Jackson network
467:
441:
432:Fork–join queue
371:Burke's theorem
339:
337:Queueing theory
334:
304:
303:
287:10.1.1.567.2170
269:
264:
263:
259:
225:
220:
219:
215:
179:
171:
170:
166:
134:
129:
128:
117:
112:
103:
83:
77:
46:
44:Queueing theory
19:
12:
11:
5:
812:
810:
802:
801:
791:
790:
784:
783:
773:
770:
769:
767:
766:
761:
756:
751:
746:
741:
736:
731:
726:
721:
716:
710:
708:
702:
701:
699:
698:
693:
688:
683:
681:Polling system
678:
673:
667:
665:
661:
660:
658:
657:
656:
655:
645:
640:
634:
632:
631:Limit theorems
628:
627:
625:
624:
619:
614:
609:
608:
607:
602:
597:
587:
582:
577:
571:
569:
565:
564:
562:
561:
556:
551:
546:
541:
536:
530:
528:
524:
523:
521:
520:
515:
510:
505:
504:
503:
498:
488:
487:
486:
475:
473:
469:
468:
466:
465:
460:
455:
449:
447:
443:
442:
440:
439:
434:
429:
428:
427:
422:
412:
407:
402:
401:
400:
395:
385:
380:
375:
374:
373:
363:
358:
353:
347:
345:
341:
340:
335:
333:
332:
325:
318:
310:
302:
301:
257:
238:(1–2): 31–51.
213:
199:10.1.1.74.3945
192:(2): 242–261.
164:
114:
113:
111:
108:
102:
99:
79:Main article:
76:
73:
45:
42:
17:
13:
10:
9:
6:
4:
3:
2:
811:
800:
797:
796:
794:
781:
771:
765:
762:
760:
757:
755:
752:
750:
747:
745:
742:
740:
737:
735:
734:Message queue
732:
730:
727:
725:
722:
720:
719:Erlang (unit)
717:
715:
712:
711:
709:
707:
703:
697:
696:Retrial queue
694:
692:
689:
687:
684:
682:
679:
677:
674:
672:
669:
668:
666:
662:
654:
651:
650:
649:
646:
644:
641:
639:
636:
635:
633:
629:
623:
620:
618:
615:
613:
610:
606:
603:
601:
598:
596:
593:
592:
591:
588:
586:
583:
581:
578:
576:
573:
572:
570:
566:
560:
557:
555:
552:
550:
547:
545:
542:
540:
537:
535:
532:
531:
529:
525:
519:
516:
514:
511:
509:
508:Kelly network
506:
502:
499:
497:
494:
493:
492:
489:
485:
482:
481:
480:
477:
476:
474:
470:
464:
461:
459:
456:
454:
451:
450:
448:
444:
438:
435:
433:
430:
426:
423:
421:
418:
417:
416:
413:
411:
408:
406:
403:
399:
396:
394:
391:
390:
389:
386:
384:
381:
379:
376:
372:
369:
368:
367:
364:
362:
359:
357:
354:
352:
349:
348:
346:
342:
338:
331:
326:
324:
319:
317:
312:
311:
308:
297:
293:
288:
283:
279:
275:
268:
261:
258:
253:
249:
245:
241:
237:
233:
232:
224:
217:
214:
209:
205:
200:
195:
191:
187:
186:
178:
174:
173:Kleinrock, L.
168:
165:
160:
156:
152:
148:
144:
140:
133:
126:
124:
122:
120:
116:
109:
107:
100:
98:
96:
91:
89:
82:
74:
72:
70:
65:
63:
59:
55:
51:
43:
41:
39:
34:
31:
28:is a service
27:
23:
16:
691:Loss network
622:Beneš method
585:Little's law
568:Key concepts
543:
518:BCMP network
277:
273:
260:
235:
229:
216:
189:
183:
167:
142:
138:
104:
92:
84:
66:
47:
35:
25:
21:
20:
15:
714:Data buffer
671:Fluid queue
638:Fluid limit
549:Round-robin
415:G/G/1 queue
410:G/M/1 queue
405:M/G/k queue
388:M/G/1 queue
383:M/M/∞ queue
378:M/M/c queue
366:M/M/1 queue
361:M/D/c queue
356:M/D/1 queue
351:D/M/1 queue
69:M/M/1 queue
58:M/G/1 queue
54:M/M/1 queue
38:round-robin
664:Extensions
437:Bulk queue
110:References
513:G-network
282:CiteSeerX
280:(4): 65.
194:CiteSeerX
145:(4): 36.
62:geometric
793:Category
780:Category
175:(1967).
252:7704706
159:7692913
50:Poisson
284:
250:
196:
157:
30:policy
270:(PDF)
248:S2CID
226:(PDF)
180:(PDF)
155:S2CID
135:(PDF)
539:LIFO
534:FIFO
292:doi
240:doi
204:doi
147:doi
93:In
56:or
24:or
795::
290:.
278:44
276:.
272:.
246:.
236:53
234:.
228:.
202:.
190:14
188:.
182:.
153:.
143:34
141:.
137:.
118:^
71:.
329:e
322:t
315:v
298:.
294::
254:.
242::
210:.
206::
161:.
149::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.