Operating System Scheduling For Multicore Processors

The problems of power consumption, heat dissipation and design complexity be-come increasingly obvious, as billions of transistors are pushed onto a single chip withthe advances of integrated circuit manufacturing technology. Improving processor per-formance by exploiting its clock speed had come to its end. Researchers had been tryingto find another way to improve processor performance without incurring much designcomplexity and power consumption. At last, multicore processor (or chip multiproces-sors) microarchitecture, which has the advantage of high performance but low powerconsumption, thus was proposed as an alternative of the traditional unicore processor.However, the newly proposed multicore processor microarchitecture is not perfectwithout any shortcomings. It introduces a series of unique challenges to related researchareas. Among them, OS scheduling design, no doubt, is one of the directions of greatconcern, since it is one of the factors affecting how well the cores be utilized. As a result,OS scheduling for multicore processors has been gaining more and more attention andbecoming a hot topic in industry and academia.There are so many issues to be addressed for OS scheduling on multicore proces-sors that all of the issues can not be fully covered in this thesis. In this dissertation theauthor primarily focuses on some of these issues. Specifically, this thesis mainly ac-counts for two multicore microarchitectures, performance heterogeneous multicoreprocessors and classical multicore processors, from the viewpoints of server computingand real time computing respectively. The author’s major contributions could be out-lined as follows.To begin with, a new performance measuring technique, called ASTPI (averagestall time per instruction), is proposed for performance heterogeneous multicore systems.It is well known that performance heterogeneous multicore processors have better per-formance/power ratio than comparable homogeneous counterparts. Nevertheless, per-formance heterogeneous multicore systems can only be best utilized when schedulingdecisions are made based on the characteristics of both the tasks and cores. Previoustechniques measure performance characteristics for a task in terms of the ratio of IPC(instructions per cycle) values achieved on different core types. This indicates that tomeasure the characteristic of a given task, the task has to be pre-executed on every coretype for some time to measure its execution rates. Whereas this novel technique doesnot need to run all core types, running any core is necessary to obtain the ASTPI valuefor a task. Moreover, a formal proof is presented that the ASTPI value of a task is dispropor-tional to its performance characteristic. In other words, the greater the ASTPI value of atask, the lower the performance characteristic the task has, and vice versa.Furthermore, a cache sharing mode is provided for performance heterogeneousmulticore processors that performance heterogeneous cores share the same last levelcache (LLC). Through experiments, it is confirmed that in heterogeneous multicoresystems, the cache sharing mode that performance heterogeneous cores share the sameLLC is better than the one that performance homogeneous cores share the same LLC.In addition, an adaptive scheduling algorithm, AS4HMS, is devised to take accountof the problem in existing algorithms that all tasks have to be synchronized before makethe scheduling decision. In order to choose the most suitable task for the most powerfulcore, all tasks need to be measured for obtaining their characteristics and compared witheach other. The existing algorithms use a global queue for comparing the tasks, which iseasy to become a performance bottleneck, and have the constraint that all tasks have tobe synchronized and arrive at the same time. Unlike the existing algorithms, AS4HMSadopts distributed mechanism for comparing the characteristics of tasks, overcomingabove shortcomings.Finally, a lightweight scheduling algorithm, PSEKG, is designed for real-time mul-ticore systems. By introducing a period sensitive mechanism, PSEKG greatly cuts downthe number of task switch times.