The Operating System scheduler is designed to allocate the CPU resources appropriately to all processes. The Linux Completely Fair Scheduler (CFS) design ensures fairness among tasks using the thread fair scheduling algorithm. This algorithm ensures allocation of resources based on the number of threads in the system and not within executing programs. This can lead to fairness issue in a multi-threaded environment as the Linux scheduler tends to favor programs with higher number of threads. We illustrate the issue of fairness through experimental evaluation thus exposing the weakness of the current allocation scheme where software developers could take advantage by spawning many additional threads in order to obtain more CPU resources. A novel algorithm is proposed as a solution towards achieving better fairness in the Linux scheduler. The algorithm is based on weight readjustment of the threads created in the same process to significantly reduce the unfair allocation of CPU resources in multi-threaded environments. The algorithm was implemented and evaluated. It demonstrated promising results towards solving the raised fairness issue. We conclude this paper highlighting the limitations of the proposed approach and the future work in the stated direction.
The design of an Operating System (OS) scheduler is meant to allocate its resources appropriately to all applications. In this paper, we present the scheduling techniques used by two Linux schedulers: O(1) and Completely Fair Scheduler (CFS). CFS is the Linux kernel scheduler that replaces the O(1) scheduler in the 2.6.23 kernel. The design goals of CFS are to provide fair CPU resource allocation among executing tasks without sacrificing interactive performance. The ability to achieve good fairness in distributing CPU resource among tasks is important to prevent starvation. However, these design goals have never been scientifically evaluated despite the fact that there are many conventional operating system benchmarks that are geared towards measuring systems performance in terms of throughput. We therefore scientifically evaluate the design goals of CFS by empirical evaluation. We measure the fairness and interactivity performance by using fairness and interactivity benchmarks. To provide a meaningful representation of results, comparisons of O(1) and CFS kernel schedulers of the open source Linux OS are used. Our experience indicates the CFS does achieve its design goals.
Current proportional thread-fair scheduling algorithms allocate CPU resources based on the total weight of runnable threads in the system instead of the total weight within runnable processes. This results in starvation issue in multithreading environments as the scheduler prefers processes with larger number of threads. We illustrate this issue through experimental evaluations on the Linux completely fair scheduler (which is based on proportional fair scheduling algorithm) thus revealing its weakness. Software developers can take advantage of this issue by spawning additional amount of threads in order to obtain more CPU resources. A novel approach based on weight readjustment techniques is proposed as a solution to provide performance bounding algorithm to limit the dominance of processes with excessive number of threads. The algorithm was implemented on CFS and evaluation results demonstrate that the proposed mechanism significantly minimizes the raised starvation issue.
1 January 2011 in Communications in Computer and Information Science
Generally, a courier company needs to employ a fleet of vehicles to travel through a number of locations in order to provide efficient parcel delivery services. The route planning of these vehicles can be formulated as a vehicle routing problem (VRP). Most existing VRP algorithms assume that the traveling durations between locations are time invariant; thus, they normally use only a set of estimated travel times (ETTs) to plan the vehicles’ routes; however, this is not realistic because the traffic pattern in a city varies over time. One solution to tackle the problem is to use different sets of ETTs for route planning in different time periods, and these data are collectively called the time-dependent estimated travel times (TD-ETTs). This paper focuses on a low-cost and robust solution to effectively scrape, process, clean, and analyze the TD-ETT data from free web-mapping services in order to gain the knowledge of the traffic pattern in a city in different time periods. To achieve the abovementioned goal, our proposed framework contains four phases, namely, (i) Full Data Scraping, (ii) Data Pre-Processing and Analysis, (iii) Fast Data Scraping, and (iv) Data Patching and Maintenance. In our experiment, we used the above framework to obtain the TD-ETT data across 68 locations in Penang, Malaysia, for six months. We then fed the data to a VRP algorithm for evaluation. We found that the performance of our low-cost approach is comparable with that of using the expensive paid data.