Abstract: On-chip trace data contains run-time information of embedded multi-core processors for software debug. Trace data are transferred through special data path and output pins. Scheduling for combining the traffic of multi-source trace data is one of the key issues that affect performance of the on-chip trace system. Features of trace traffic combination，evaluation metrics and scheduling schemes are analyzed. A novel queue scheduling algorithm (TraceDo algorithm) with service required threshold (SRH) and minimum service granularity (MSG) is presented. Setting a SRH to each queue，queue switching is controlled by comparing the queue length with the threshold level of SRH. Users can control queue length distributions and overflow rates according to overflow costs, buffer capacities and burst characteristics of trace traffic. Using MSG and lazy switching together, the minimum number of consumers served in a queue between two switchovers is promised and such service granularity is increased when other queues have marginal capacity of buffer. Therefore switchover counts are reduced and overflow probabilities along with such gains are constrained by SRH. Simulation results show that the algorithm controls the overflow rate of each queue effectively and utilizes the buffer capacity according to the queues priority assigned sufficiently. The algorithm is realized in Verilog-HDL. Compared with a leading method, the overflow rate is reduced 30% with additional 2015μm\+2 in area.