Cache allocation to a virtual machine

A system for cache allocation to a plurality of virtual machines, the system comprising:

• a memory having processor-readable instructions stored therein;
• and
• one or more processors configured to access the memory and execute the processor-readable instructions, which, when executed by the one or more processors configures the one or more processors to perform a method, the method comprising:
• sequentially receiving a sequence of requests, each request of the sequence of requests associated with an access of a plurality of accesses to a data element of a plurality of data elements, the plurality of accesses comprising a plurality of read accesses and a plurality of write accesses;
• detecting a plurality of access sequences to the plurality of data elements, each of the plurality of access sequences comprising two successive accesses to a single data element of the plurality of data elements, the two successive accesses comprising a first access and a second access, the first access associated with a first request of the sequence of requests and the second access associated with a second request of the sequence of requests, the second request received after the first request, the second request associated with a read access of the plurality of read accesses to the single data element;
• calculating a reuse distance of a plurality of reuse distances by calculating a number of distinctive data elements of the plurality of data elements, each of the distinctive data elements associated with one or more of a plurality of request, each of the plurality of requests located between the first request and the second request in the sequence of requests;
• estimating an optimal cache size ci according to an operation defined by the following:
• ci=(URDmax+1)×BLK,
• where URDmax is a largest of the plurality of reuse distances and BLK is a size of a cache block associated with the data element;
• and
• estimating an efficient cache size by minimizing an objective function OF(ci) with respect to the cache size ci subject to a set of minimization constraints;
• assigning the efficient cache size to a virtual machine of a plurality of virtual machines;
• and
• determining a writing policy for the virtual machine based on the number of the plurality of access sequences.

A system for cache allocation to a plurality of virtual machines, the system comprising:

• a plurality of virtual machines;
• a storage subsystem comprising a plurality of data elements;
• and
• a hypervisor associated with the plurality of virtual machines, the hypervisor comprising:
• a monitor configured to:
• sequentially receive a sequence of requests, each request of the sequence of requests associated with an access of a plurality of accesses to a data element of a plurality of data elements, the plurality of accesses comprising a plurality of read accesses and a plurality of write accesses;
• and
• detect a plurality of access sequences to the plurality of data elements, each of the plurality of access sequences comprising two successive accesses to a single data element of the plurality of data elements, the two successive accesses comprising a first access and a second access, the first access associated with a first request of the sequence of requests and the second access associated with a second request of the sequence of requests, the second request received after the first request, the second request associated with a read access of the plurality of read accesses to the single data element;
• an analyzer configured to:
• calculate a reuse distance of a plurality of reuse distances by calculating a number of distinctive data elements of the plurality of data elements, each of the distinctive data elements associated with one or more of a plurality of requests, each of the plurality of requests located between the first request and the second request in the sequence of requests;
• and
• estimate an optimal cache size based on the plurality of reuse distances;
• and
• an actuator configured to assign the optimal cache size to a virtual machine of the plurality of virtual machines.