Abstract: Aiming at the problem of target cost which is not cared about by most task execution algorithms in embedded systems, a task allocation and scheduling algorithm based on global constraints for multi-objective is proposed in this paper. The approach uses constraint logic programming to impose global constraints for multi-objective on the task execution resources such as processing units, communication devices and the usage of code and data memory. The proposed algorithm assumes that ROM and RAM are used for implementing code memory and data memory respectively, and also considers the actual placement of data in data memory. The experimental results show that, under the multiple constraints, the proposed task allocation and scheduling algorithm can perform both in terms of the usage of code and data memory as well as solving effectively the task better than the widely used greedy scheduling algorithms.

Key words: multi-objective, global constraints, allocation and scheduling, memory size, cost

摘要： 针对嵌入式系统中大多数任务执行算法不考虑目标成本问题，提出了一种基于多目标全局约束的任务分配和调度算法。算法使用约束逻辑编程来对任务执行资源如处理单元、通信设备以及代码和数据存储量的使用进行多目标全局约束。算法假设ROM和RAM分别用于代码存储和数据存储，算法还考虑数据在数据存储器中的位置。实验结果表明，尽管在多个约束条件下，提出的任务分配和调度算法无论在代码存储和数据存储量使用方面，还是在对任务有效求解方面都能取得比普遍采用的贪婪调度算法更好的结果。

关键词: 多目标, 全局约束, 分配和调度, 存储量, 成本