In this paper, we investigate how software rejuvenation can be used in a Cloud environment to increase the availability of a virtualized system composed of a single virtual machine monitor (VMM) on top of which a certain number of virtual machines (VMs) can be instantiated. We start from the assumption that the aging of a VMM increases with the number of VMs it is managing, thus characterizing the problem in terms of dynamic reliability. Therefore, by identifying the age of the VMM with its reliability and based on the conservation of reliability principle, we characterize the time to failure of the VMM through continuous phase type distributions. The system availability is thus modeled by an expanded continuous time Markov chain expressed in terms of Kronecker algebra in order to face the state space explosion and to keep memory of the age reached by the VMM in case the number of the hosted VMs change. Time-based rejuvenation is taken into consideration and the optimal timer is evaluated in order to maximize the VMM availability.