# US 8,752,058 B1 · Implicit co-scheduling of CPUs

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,752,058 B1
- Document ID: US8752058B1
- Status: Granted
- Kind: B1
- Application number: 13/105,396
- Filed: 2011-05-11
- Granted: 2014-06-10
- Earliest claimed: 2010-05-11
- Assignees: VMware, Inc.
- Applicants: Haoqiang Zheng; Carl A. Waldspurger
- Inventors: Haoqiang Zheng; Carl A. Waldspurger
- Web page: https://patentgrep.com/patent/US8752058B1

## CPC

- G06F 9/45533: {Hypervisors; Virtual machine monitors}
- G06F 9/45545: {Guest-host, i.e. hypervisor is an application program itself, e.g. VirtualBox}
- G06F 9/45558: {Hypervisor-specific management and integration aspects}
- G06F 9/46: Multiprogramming arrangements
- G06F 9/485: {Task life-cycle, e.g. stopping, restarting, resuming execution (G06F9/4881 takes precedence)}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/522: {Barrier synchronisation}
- G06F 2009/4557: {Distribution of virtual machine instances; Migration and load balancing}
- G06F 2009/45575: {Starting, stopping, suspending or resuming virtual machine instances}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques for implicit co scheduling of CPUs to improve corun performance of scheduled contexts are described. One technique minimizes skew by implementing corun migrations, and another technique minimizes skew by implementing a corun bonus mechanism. Skew between schedulable contexts may be calculated based on guest progress, where guest progress represents time spent executing guest operating system and guest application code. A non-linear skew catch-up algorithm is described that adjusts the progress of a context when the progress falls far behind its sibling contexts.

## Claims

### Claim 1

A method for bounding skew between sibling contexts that are executing on a computer system, wherein skew between a first and second context is a difference in progress of the two contexts, the progress being a measure of time during which a context is executing, the first context and second context being sibling contexts that are associated with a common underlying system, each context being a software construct of the underlying system, the method comprising:
calculating the skew between the first context and the second context, the second context having a greater progress than the first context;
determining whether the skew exceeds a threshold amount of skew; and
when the skew exceeds the threshold, calculating a metric as a function of the skew and adjusting the progress of the first context by an amount that is a function of the metric, the adjusting of the progress being performed only when the skew exceeds the threshold;
calculating a new skew based on the adjusted progress of the first context; and
performing, by operation of one or more processors, a scheduling operation on a particular context associated with the underlying system, the scheduling operation including determining when to execute the particular context on the one or more physical processors, the scheduling operation being based at least in part on the new skew.

### Claim 2 (depends on 1)

The method of claim 1, wherein each context is a virtual processor (VCPU) associated with a virtual machine, and the progress of the virtual processor is determined based on execution of guest code, guest code including guest operating system and application code that is associated with the virtual machine.

### Claim 3 (depends on 1)

The method of claim 1, wherein the particular context is the first context.

### Claim 4 (depends on 1)

The method of claim 1, wherein the metric comprises a value for n that satisfies an inequality 2(n-1)*T<skew<2n*T, where T is the threshold amount of skew.

### Claim 5 (depends on 4)

The method of claim 4, wherein the calculating and determining are performed upon wakeup of the first context, the second context is a context having a largest amount of progress of all contexts that are siblings of the first context, and the advancing of the progress of the first context comprise adding a value to the progress of the first context that is a function of both the metric and an amount of guest progress of the first context since a prior update.

### Claim 6 (depends on 5)

The method of claim 5, wherein the function of the metric and the amount of progress of the first context since the prior update is 2 to the nth power multiplied by the amount of guest progress of the first context since the prior update, wherein n is the metric.

### Claim 7 (depends on 1)

The method of claim 1, wherein the advancing of the progress of the first context is performed when at least one of: when the first context is descheduled, when the first context wakes up from idle, and upon periodic sampling of the first context while the first context is running.

### Claim 8 (depends on 1)

The method of claim 1, the computer system having multiple physical processors (PCPUs) including a first processor and a second processor, wherein the performing the scheduling operation on the particular context associated with the underlying system further comprises:
determining that the plurality of the sibling contexts are running or queued on the first processor;
determining whether the second processor is available that is not associated with any sibling context;
when each of the multiple physical processors is associated with at least one of the sibling contexts, executing the plurality of the sibling contexts on the first processor; and
when the second processor is available and not associated with any of the sibling contexts, migrating one of the plurality of the sibling contexts to the second processor; and
executing the one of the plurality of the sibling contexts on the second processor.

### Claim 9 (depends on 8)

The method of claim 8, wherein the determining whether the second processor is available and the migrating of the one of the sibling contexts to the second processor occurs upon wakeup of the one of the sibling contexts.

### Claim 10 (depends on 1)

The method of claim 1, the computer system having multiple physical processors (PCPUs), wherein the performing the scheduling operation on the particular context associated with the underlying system further comprises:
identifying an idle PCPU of the multiple PCPUs;
identifying the first context that is associated with another PCPU and is ready to run, the first context being one of a family of sibling contexts, the other PCPU being any of the PCPUs that is not the idle PCPU;
waiting for a time period to elapse;
after the waiting, determining whether the second context of the family of sibling contexts that is associated with the idle PCPU has restarted on the idle PCPU and whether the first context associated with the other PCPU remains ready to run; and
when the second context has not restarted on the idle PCPU during the time period and the first context remains ready to run after the lapsing of the time period, migrating the first context associated with the other PCPU to the idle PCPU.

### Claim 11 (depends on 10)

The method of claim 10, further comprising:
determining whether a context that is ready to run exists that has no siblings on the idle PCPU;
when the context exists that is ready to run and has no siblings on the idle PCPU, migrating the context that is ready to run to the idle PCPU; and
performing the identifying of the first context, the waiting, and the migrating of the first context only when no context exists that is ready to run and has no siblings on the idle PCPU.

### Claim 12 (depends on 1)

The method of claim 1, the computer system having multiple physical processors (PCPUs), wherein the performing the scheduling operation on the particular context associated with the underlying system further comprises:
for each of the sibling contexts queued on one of the PCPUs, reducing a virtual time of the sibling context by a corun bonus when the sibling context has at least one other sibling context currently running on another one of the PCPUs; and
granting execution priority to a queued thread associated with the sibling context that has the lowest virtual time.

### Claim 13 (depends on 12)

The method of claim 12, wherein the amount of corun bonus is normalized by an amount of the sibling context's CPU entitlement.

### Claim 14 (depends on 12)

The method of claim 12, wherein an amount of the corun bonus is scaled based on a number of the plurality of sibling contexts that are currently running on the other PCPUs.