NDLI: Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling

Please wait, while we are loading the content...

On the complexity of distributed graph coloring

When selfish meets evil: byzantine players in a virus inoculation game

Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling

Computing separable functions via gossip

Self-stabilizing byzantine agreement

Oracle size: a new measure of difficulty for communication tasks

Common2 extended to stacks and unbounded concurrency

How fast can a very robust read be?

An Ω (n log n) lower bound on the cost of mutual exclusion

Synchronizing without locks is inherently expensive

The art of multiprocessor programming

Quorum placement in networks: minimizing network congestion

Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games

Sketching asynchronous streams over a sliding window

Peer counting and sampling in overlay networks: random walk methods

Irreducibility and additivity of set agreement-oriented failure detector classes

Object location using path separators

Single-scanner multi-writer snapshot implementations are fast!

Reliable broadcast in radio networks: the bounded collision case

Lower bound for scalable Byzantine Agreement

Transactional contention management as a non-clairvoyant scheduling problem

Century papers at the first quarter-century milestone

Distributed verification of minimum spanning trees

Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation

Adversarial queuing on the multiple-access channel

On the topologies formed by selfish peers

Optimally efficient multi-valued byzantine agreement

Optimal-stretch name-independent compact routing in doubling metrics

An O(1) RMRs leader election algorithm

Possibility and complexity of probabilistic reliable communication in directed networks

Stably computable predicates are semilinear

Towards a theory of transactional contention managers

Distributed social systems

EquiCast: scalable multicast with selfish users

Veracity radius: capturing the locality of distributed computations

Timeliness, failure-detectors, and consensus performance

Local approximation schemes for topology control

Life is not a state-machine: the long road from research to production

Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling

Content Provider	ACM Digital Library
Author	Stein, Clifford Caprita, Bogdan Nieh, Jason
Abstract	We present Grouped Distributed Queues (GDQ), the first proportional share scheduler for multiprocessor systems that scales well with a large number of processors and processes. GDQ uses a distributed queue architecture, and achieves accurate proportional fairness scheduling with only O(1) scheduling overhead. GDQ takes a novel approach to distributed queuing: instead of creating per-processor queues that need to be constantly balanced to achieve any measure of proportional sharing fairness, GDQ uses a simple grouping strategy to organize processes into groups based on similar processor time allocation rights, and then assigns processors to groups based on aggregate group shares. Group membership of processes is static, and fairness is achieved by dynamically migrating processors among groups. The set of processors working on a group use simple, low-overhead round-robin queues, while processor reallocation among groups is achieved using a new multiprocessor adaptation of Weighted Fair Queuing. By commoditizing processors and decoupling their allocation from process scheduling, GDQ provides, with only constant scheduling overhead, fairness within a constant of the ideal generalized processor sharing model for process weights with a fixed upper bound. We have implemented GDQ in Linux and measured its performance. Our experimental results show that GDQ has low overhead and scales well with the number of processors and processes.
Starting Page	72
Ending Page	81
Page Count	10
File Format	PDF
ISBN	1595933840
DOI	10.1145/1146381.1146396
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-07-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Multiprocessor scheduling Fair queuing Quality of service Scheduling Proportional sharing Resource management
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

ABSTRACT Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling

Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling (2006)

Interposed proportional sharing for a storage service utility

Interposed proportional sharing for a storage service utility

Controllable fair queuing for meeting performance goals (2005)

Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors

Improved conditions for bounded tardiness under EPDF fair multiprocessor scheduling

Surplus fair scheduling: a proportional-share cpu scheduling algorithm for symmetric multiprocessors.

Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors (2000)

Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling

Similar Documents

ABSTRACT Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling

Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling (2006)

Interposed proportional sharing for a storage service utility

Interposed proportional sharing for a storage service utility

Controllable fair queuing for meeting performance goals (2005)

Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors

Improved conditions for bounded tardiness under EPDF fair multiprocessor scheduling

Surplus fair scheduling: a proportional-share cpu scheduling algorithm for symmetric multiprocessors.

Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors (2000)

Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling