Best-effort Scheduling (m,k)-firm Real-time Tasks based on the (m,k)-firm Constraint Meeting Probability

摘要

Recent research in real-time systems has focused on firm real-time systems which are hard but permit occasional misses of deadlines. One of general firm task models is the (m, k)-firm task model. A task of(m, k)-firm constraint must meet at least m deadlines for any consecutive k periods. The previous best-effort scheduling algorithms for the (m, k)-firm tasks are based on either distance to failure state or loss rate. However, those schemes do not meet the (m, k)-firm constraint to a full extent, so that they have a limitation in performance. In this paper, we introduce a new probability of a task to meet its (m, k)-firm constraint, which reflects the (m, k)-firm constraint more than previous schemes. We also propose several scheduling algorithms based on the (m, k)-firm constraint meeting probability. Through simulation results, the success ratios of suggested algorithms show a better performance.