Design, testing and performance analisys of efficient lock-free solutions for multi-core Linux scheduler

Multiprocessor systems are nowadays de facto standard for both personal computers and server workstations. Benefits of multi-core technology has recently been used for embedded devices and cellular phones as well. Linux has not been originally designed to be a Real-Time Operating System (RTOS) but, recently, a new scheduling class, named SCHED_DEADLINE, was added to it. SCHED_DEADLINE is an implementation of the well known Earliest Deadline First algorithm. In this thesis we first present PRACTISE, a tool for developing, debugging, testing and analyse real-time scheduling data structures in user space. Unlike other similar tools, PRACTISE executes code in parallel, allowing to test and analyse the performance of the code in a realistic multiprocessor scenario. We also show an implementation of a skiplist, realized with the help of the tool above. This implementation is intended to be used for processes migration among the CPUs in SCHED_DEADLINE. To effectively manage the concurrent accesses to the data structure we used a revised version of the flat combining framework