It is of great importance to perform preventive rejuvenation of software systems with service degradation. In this paper we develop a faster estimation algorithm for the optimal periodic rejuvenation schedule which maximizes the steady-state system availability. In the case with unknown system failure time distribution, a non-parametric estimation approach based on the empirical distribution of system failure time has been proposed in the literature, but often failed to obtain the exact estimates for the small sample cases. We improve the existing availability estimation algorithm in terms of convergence speed and derive the more effective estimation scheme based on the kernel density of system failure time. Throughout simulation experiments, the proposed estimation scheme is compared with the existing approach and can be validated in the sense of asymptotic optimality.