Abstract: Scheduling algorithms with preemption threshold collect characteristics of no preemption scheduling and full preemption scheduling It both decreases the waste of CPU resources caused by excessive random preemptions and guarantees suitable missed deadline percentage and CPU utilization However, the existing works basically focus on a determinated task set （i e , a given number of tasks, fixed priority and a given preemption threshold satisfied a certain condition）, and require that different task has a different priority integer The proposed scheduling algorithm with preemption threshold discussed in this paper relaxes the above limitations, i e , an uncertain number of tasks, and the priority and its preemption threshold can be dynamically changed during scheduling Finally, using usual LSF policy as example, simulations with dynamic preemption threshold are given Results show that the proposed dynamic scheduling algorithm with preemption threshold decreases the missed deadline percentage and increases efficient utilization percentage of CPU greatly for uncertain task set with no fixed priority and preemption threshold