Abstract: A hard real-time system is usually subject to stringent reliability and timing constraints due to the fact that failure to produce correct results in a timely manner may lead to a disaster. Almost all fault-tolerant scheduling algorithms at present are designed to deal with hardware faults, while less of those take possible software faults into account. Presented in this paper is a new software fault-tolerant real-time scheduling algorithm that is similar to EDF, called EBPA(expectation-based probing algorithm). The important contributions of the algorithm are probing a certain steps during the executions of primaries, which leads to improving the predictive quality of canceling ineffective primaries when heavy workload occurs and preventing early failures in execution from triggering failures in the subsequent primary executions as soon as possible. Therefore, the algorithm increases the successful percentage of tasks' completion, and meanwhile decreases the wasted CPU time slots. The simulation experiments show that the algorithm has a better trade-offs between scheduling costs and scheduling performance than the well-known algorithms so far. Moreover, some experimental parameters, such as the number of probing steps and failure probability, are also taken into account.