Abstract: In the fault-tolerant real-time scheduling algorithms of software fault-tolerant module, each task possesses two versions, namely, primary and alternate. The prediction of executable primaries is the key issue that affects scheduling performance. In order to improve the prediction precision of primaries, new algorithms named DPA (deep-prediction based algorithm) and EDPA (EDF-based DPA) are put forward. Two algorithms schedule tasks with the help of prediction-table, which is created for the released primary and contains the information of the tasks between the current time and the notification time. In DPA algorithm, the primaries in prediction-table are scheduled according to the temporal sequence of their corresponding alternates' notification time. EDPA algorithm schedules primaries using EDF algorithm in prediction-table. If primaries in prediction-table do not fail, the table is referenced to schedule tasks with no cost. Simulation results show that DPA and EDPA algorithms provide more execution time for primaries and waste less CPU time than the well-known algorithms so far. It is shown that the two algorithms can get higher scheduling performance with lower cost in the circumstance when tasks periods are short and software fault probability is low.