Scheduling, mapping and synchronization have an essential impact on the performance of Multi-Processor System-on-Chips (MPSoCs), especially in heterogeneous systems with many cores and small tasks. This paper presents a technique to efficiently accelerate these operations. Key contribution is an Application-Specific Instruction-set Processor (ASIP) called OSIP which is especially tailored to achieve this. In contrast to pure HW solutions, OSIP is programmable and hence features higher flexibility and better scalability. OSIP comes with a compiler and a firmware that ease its usability, and an abstract formal model that allows analytical evaluation and integration into fast system level simulators. Together with OSIP, a thin software layer is proposed that leverages high level multi-task programming by abstracting OSIP's low level details away. In an extensive case study based on a synthetic benchmark and a benchmark from the multimedia domain (H.264), OSIP highlights its potential when compared against a standard RISC and an ARM926-EJS processor.