Software rejuvenation is a preventive maintenance technique that has been extensively studied in recent literature. In this paper, we extend the classical result by Huang et al. (1995), and in addition propose a modified stochastic model to generate the software rejuvenation schedule. More precisely, the software rejuvenation models are formulated via the semi-Markov reward process, and the optimal software rejuvenation schedules are derived analytically in terms of the reward rate. In particular, we consider the two special cases: steady-state availability and expected cost per unit time in the steady state. Further, we develop non-parametric algorithms to estimate the optimal software rejuvenation schedules, provided that the statistically complete (unsensored) sample data of failure time is given. In numerical examples, we compare two models from the viewpoints of system availability and economic justification, and examine asymptotic properties for the statistical estimation algorithms.