Software rejuvenation is a technique for software fault tolerance which involves occasionally stopping the executing software, "cleaning" the "internal state" and restarting. This cleanup is done at desirable times during execution on a preventive basis set that unplanned failures, which result in higher costs compared to planned stopping, are avoided. Since during rejuvenation, the software is typically unavailable or in a degraded mode of operation, the operation involves a cost. In this paper, we present an analytical model of a software system which serves transactions. Due to "aging", not only the service rate of the software decreases with time hut the software itself experiences occasional crash/hang failures. We propose and compare two rejuvenation policies. The policies are evaluated for the resulting steady state availability as well the probability that a transaction is denied service. We also numerically illustrate the use of our model to compute the optimal rejuvenation interval which minimizes (maximizes) the loss probability (steady state availability).