US 9,870,258 B1Granted

Systems and methods for performing scheduling for a cluster

AssigneeGoogle Inc.

InventorsJohn Wilkes, Todd Pu-Tse Wang, Walfredo Cirne, David Oppenheimer, Brian Grant, Jason Hickey, Kai-Peter Backman, Joseph Hellerstein, David Bort

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

Multiple scheduler verticals can allocate tasks to resources that are shared by the scheduler verticals. Information regarding a state of each resource may be stored in memory accessible by the multiple scheduler verticals, and a processor updates the information. The scheduler verticals schedule events to be performed by any of the resources, and submit updates to reflect the scheduled events in the information. In the event of conflicting events, an update corresponding to only one of the conflicting events is committed. Moreover, disruptions may be preplanned and scheduled so as to minimize impact on scheduled tasks.

Claims16

Dependent claims

A system, comprising:

a first scheduler vertical;
a second scheduler vertical;
and
a memory accessible by the first scheduler vertical and the second scheduler vertical, the memory storing an assignment of work for machines;
wherein the first scheduler vertical is in communication with one or more processors and programmed to:
access the memory;
determine timeslots for scheduling a first set of tasks;
and
schedule the first set of tasks;
wherein the second scheduler vertical is in communication with one or more processors and programmed to:
access the memory;
determine, concurrently with the first scheduler vertical, timeslots for scheduling a second set of tasks;
and
schedule the second set of tasks;
and
reschedule conflicting tasks that conflict with any of the first set of tasks scheduled by the first scheduler vertical;
wherein the first scheduler vertical is configured to execute decisions regarding allocation of tasks among machines more quickly than the second schedule vertical.

14 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/164,098Filed 25 May 2016 · continuation
Priority: 13 Jul 2012
Granted: 16 Jan 2018
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 9/4881
By program, e.g. task dispatcher, supervisor, operating system: scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
G06F 9/4818
By interrupt, e.g. masked: priority circuits therefor
G06F 9/5027
To service a request: the resource being a machine, e.g. CPUs, Servers, Terminals
G06F
Computing and data processing

Family

Application61/671,395Us provisional application · filed 13 Jul 2012
Application13/788,195Parent of this division · filed 7 Mar 2013
Application14/864,130Parent of this continuation · filed 24 Sep 2015
Application14/985,584Parent of this continuation · filed 31 Dec 2015
US 9,229,774 B1Parent of this division · filed 5 Jan 2016
US 9,329,892 B1Parent of this continuation · filed 3 May 2016
US 9,378,051 B1Parent of this continuation
Application14/864,130Parent of this division
US 9,870,258 B1This patent

From the US filing history. Foreign family members aren’t listed.