Scheduling: some description of the most important problems, models and solution methods - Essay Example

{task scheduling} - {algorithms} to solve the general problem of satisfying time and resource {constraints} between a number of tasks. Compare {planning}. “ Scheduling, in the scenario of present day computing, has broadened and diversified effects. The performance and requirement of scheduling can be observed in almost all areas pertaining to computing. From a barber’s shop to car assembly line the effectiveness of scheduling has been proven upon various real world scenarios. Theoretical and applied perspectives add more diversity to this phenomenon.

In spite of immense work being done in this regard, the performance issues, algorithmic complexities and limitations are few of the areas that are still open for researchers. Optimization of the resource utilization is the main objective of all scheduling strategies. This text takes specific example of CPU scheduling for further detailed discussion. The effectiveness, implications, limitations and remedies of different scheduling strategies is discussed henceforth. A scheduling problem can ideally be defined with respect to its model.

On a broader scale, the model refers to the environment, characteristics, constraints and the objective of the scheduling scenario at hand. From the most complex to the most trivial tasks within a system, each processing requires the help of this mechanism. More specifically, every multiprocessing and multi tasking environment cannot survive without proper scheduling algorithms working at its backend. CPU Scheduling: The CPU is a central resource in a computer system environment. The simplest instance that can be considered for scheduling is a uni-processor (1 CPU) environment.

CPU scheduling is an attempt to allocate and de-allocate this central resource to the processes in an optimal manner. Maximum CPU utilization and throughput; and Minimum turn-around time (the time for which a process resides in the system) are the goals to be achieved. Following are some of the very basic assumptions established to acquire the basic understanding of the process. The environment is composed of a process queue for CPU. The arrival time of each process in a queue and the expected duration of processing are already recorded.

There is just one input device with is respective queue. When a process requires input its request is scheduled accordingly in the input queue and its processing halts for the time being. There are different algorithms that can be studied in this regard. Few are discussed below. First Come First Served (FCFS). This algorithm is considered as the simplest and most robust of all. It can be implemented using a FIFO process queue. It simply schedules the processes according to their arrival times.

The basic version of this strategy does not allow process preemption during processing. The algorithm is explained through the following example with table 1. Table 1: Deterministic Model Processes Arrival Time Duration/Size 1 1 5 units 2 3 7 units 3 4 2 units Following are the assumptions that are taken for the sake of simplicity. The time line is assumed to start at zero (0). No input requests. The continuity of process execution remains undisturbed despite the marking of arrival of a new process in the queue by CPU.

The Gantt. Chart is as follows, Gantt Chart Processes/Time line 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 Legend: Gray shade indicates processing and Blue indicates waiting The grey portion