We extend the results about performance potentials, perturbation realization matrices, policy iteration of Markov decision processes, etc., to semi-Markov processes (SMPs). Starting with the concept of perturbation realization, we define a realization matrix and prove that it satisfies the Lyapunov equation. From the realization matrix we define a performance potential and prove that it satisfies the Poisson equation. Sensitivity formulas and policy iteration algorithms of Semi-Markov decision process (SMDPs) can be derived. The performance sensitivities can be obtained and policy iteration of SMDPs can be implemeted on a single sample path of the SMPs.