We present guaranteed dynamic priority assignment schemes for multiple real-time tasks subject to (m, k)-firm deadlines. The proposed schemes have two scheduling objectives: providing a bounded probability of missing (m, k)-firm constraints and maximizing the probability of deadline satisfactions. The second scheduling objective is especially necessary in order to provide the best quality of service as well as to satisfy the minimum requirements expressed by (m, k)-firm deadlines. We analytically establish that the proposed schemes provide a guarantee on the bounded probability of missing (m, k)-firm constraints. Experimental studies validate our analytical results and confirm the effectiveness and superiority of the proposed schemes with regard to their scheduling objectives.