Abstract: Hard real-time systems are those that are specified in terms of stringent reliability and strong timing constraints owing to the fact that any failure to support correct outputs in a timely manner may result in a disaster. They are often involved in critical activities, where human lives may be at stake. These characteristics emphasize the need for making the services provided by this kind of system fault-tolerance. Software fault-tolerant model is a cost-effective means which trades the quality of computation results for promptness to tolerate the software faults. A new fault-tolerant scheduling algorithm is proposed based on the software fault-tolerant model in order to improve system fault resilience and, at the same time, reduce the preemptions. In order to achieve the optimal configuration, a maximal dual priority configuration search algorithm (MDPCSA), which based on the worst-case response time schedulability analysis, is presented. Then, together with the MDPCSA, we propose an optimal dual priority configuration search algorithm (ODPCSA). We show that ODPCSA is optimal in the sense that the fault resilience of task sets is maximized and the preemptions are minimized as for the proposed analysis. Compared with the related algorithms, the proposed approach is evaluated and shown to be more effective by simulation.