The performance of computer systems has rapidly grown in the recent years, Although they have always faced ever-increasing demand for more computational power by new applications. In order for responding to such requisition, multiprocessor and multicomputer systems have received considerable attention. Executing the applications easily and quickly is the primary goal of these systems to fulfill. Effectively utilizing such systems, which are called parallel systems, is accomplished by simultaneous executing of different jobs or applications. At the approach of fully utilization, allocating processors to jobs with dissimilar computational requirements or job scheduling problem shows itself more than ever. Different strategies such as Backfilling algorithms with the aims of reducing waiting time, response time and slowdown have been proposed in the recent years. Despite the fact that almost a decade has elapsed since introducing the original EASY Backfilling algorithm, the scheme is extensively employed in today’s production systems due to its low complexity and impressive performance. In the Backfilling algorithm, in the case when the first queued job cannot be executed on account of insufficient idle processors, other waiting jobs are given the chance of execution out of order. Nevertheless, the facility is only granted to those jobs which do not postpone the execution of first queued job. By reducing the gaps, the approach can lead to improving the performance of the system. There are also other job scheduling algorithms such as Moldability and Malleability in which the partition size can be altered while launching the job or during the runtime. The capability of changing partition size empowers the scheduler to decide on the partition size based on current conditions so that it results in the minimum response time. In this thesis, different scheduling methods are presented and evaluated. According to the studies, two new scheduling algorithm herein named XFactorWithBackfilling and Virtual Moldability are then proposed. In XFactorWithBackfilling, queued jobs are sorted based on the Xfactor parameter. Then the backfilling strategy is employed to schedule the jobs. In Virtual Moldability, folded execution of the job on virtual machines is investigated in the case when the first queued job cannot be executed on account of insufficient idle processors. This leads to increasing the overall performance of the system. It is well-known that the performance of a scheduling solution is influenced by the workload submitted to the system. Realistic workloads are thus crucial to establish how well scheduling solutions perform in practice. Therefore in order to evaluate how proposed algorithms are going to be Keywords: Multiprocessors systems, Backfilling, XFactorWithBackfilling, Virtual Moldability, Virtualization.
