Job Scheduling

For every process there are a number of individual units of work which need to be strung together and executed in order to achieve something greater. As more people contribute to the work, more considerations arise in order to get the work done on time and to have everyone be as effective as they can be. In the business world, job scheduling is often represented by the Gantt chart which not only lists each piece of work and how long it will take, but their dependencies and how they line up with the other work involved in the larger goal. We will explore the methods which are used to schedule jobs.

Operating Systems

In the technology world, operating systems are home to one of ubiquitous places for scheduling). In order to multiple different processes to run at the same time, the operating system must decide how to allocate the system's resources to each process.

Depending on the system and software involved, scheduling can be cooperative or preemptive. In systems where there is cooperation and trust, cooperative scheduling lets the processes being run to give back the resources to the scheduler when it is completed running. Usually this would mean that the process runs a block of work and then lets the scheduler give the resources to the next process. However, this means that if the process doesn't give up control back to the scheduler, none of the other processes can run. In a multitasking system, one bad process can lock up the system entirely. With preemptive scheduling, we don't have this problem. At any time, the scheduler can take away resources from the currently running system and give it to the next process. The state of the process is saved so that it can resume where it stopped.

  • First come first served
  • Shortest process next
  • Shortest remaining time
  • Pre-emption
  • Priority scheduling

Dependency Graph

For more complex work with known dependencies, we can utilize an directed acyclic graph to map those dependencies. Once we have built the graph, we can utilize topological sorting in order to map the graph into a linear sequence of jobs so that we know then we start working on each task, the dependent tasks will all be completed. This is a great approach when there is only one worker or core that you are using. Modern computers and businesses often have many people working on different tasks for a job. This increase the complexity of scheduling the work, especially if different cores or individuals will do each job at different rates. This optimization problem is called job shop scheduling.

Further Reading