| Although there is wide agreement that backfill produces significant benefits in scheduling of parallel jobs in many algorithms. The algorithm is based on FCFS algorithm, it backfills littler queued jobs into idle CPU to improve CPU utilization. But when idle CPU is still unfit the backfill algorithm to backfill littler queued jobs. There are still parts of CPU are idle in system. so it is difficult to get the goal of improving CPU utilization. This paper presents an algorithm for backfill-based "Requirement Self-adapted" parallel job scheduling, and to Memory-Shared architecture parallel computer system, the paper also presents another algorithm for backfill-based "Resources Auto-reclaimed" parallel job scheduling.The "Requirement Self-adapted" algorithm was proposed based on the concept of backfill. The CPU free space was adopted as a judgment, and the numbers of jobs were extended to take part in backfill operation and made up the shortage of the backfill. The parameters of the jobs, such as the required CPU number and the estimated running time, were modified in queue. The job that can't be operated by backfill were filled into the CPU space, and the CPU utilization of job scheduling in parallel system was great improved.The "Resources Auto-reclaimed" algorithm adopts CPU utilization of runningjobs as a judgment . To enlarge CPU space for backfill by adjusting dynamically the running jobs' CPU numbers in reason, so it can backfill the jobs which can't bebackfilled by the backfill algorithm. The "Resources Auto-reclaimed" algorithmremedies the lack of the backfill algorithm and improves the CPU utilization of theMemory-Shared architecture parallel computer system better.The two improved algorithms improve the backfill algorithm in differenttechnology ways all based on the concept of backfill. By combining with FCFS andBackfill, these algorithms take part in jobs scheduling in parallel system together andimprove the CPU utilization continue. |
PDF Full Text Request