Operating systems for reconfigurable devices enable the development of embedded systems where software tasks, running on a CPU, can coexist with hardware tasks running on a reconfigurable hardware device (FPGA). Furthermore, in such systems relocatable tasks can be migrated from software to hardware and viceversa. The combination of high performance and predictability of hardware execution with software flexibility makes such architecture especially suitable to implement high-performance real-time embedded systems. In this work, we first discuss design and scheduling issues for relocatable tasks. We then concentrate on the on-line admission control problem. Task allocation and migration between the CPU and the reconfigurable device is discussed and sufficient feasibility tests are derived. Finally, the effectiveness of our relocation strategy is shown through a series of synthetic simulations.