Scheduling: Problems, Models and Solution Methods - Case Study Example

of the of the of the Scheduling: some of the most important problems, models and solution methods Literally, scheduling can be defined as the arrangement of the execution of a number of tasks/operations with respect to time. According to ‘hyperdictionary’ (2003) there are various meanings of scheduling with respect to computers: “{instruction scheduling} - sequencing the instructions executed by the {CPU} {multitasking} ("process scheduling") - sharing a CPU between several processes {application} {software} to help organize your daily meetings etc. {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 highlights the processing time and the blue portion represents the respective waiting time of each process in a process queue. The average turnaround time is 8.6 units and the average waiting time of processes is 6 units. The average turnaround time and average waiting time with FCFS is usually high. Considering the unrealistic assumptions maintained for simplicity, there are certain issues. The presence of I/O bound processes would definitely change the whole picture. The effect of context switches done by CPU for marking the arrivals and service of input requests on the turnaround times and waiting times of processes. The duration of stay of a process is always unpredictable due to the incorporated conditional structures and random input requests. A deterministic model is not sufficient to study this algorithm. Simulation or large scale implementation with beta testing are better techniques for analysis. The FCFS environment is also designated as a prioritized environment. The arrival time is the basis of priority. Theoretically the average turnaround time seems to reduce when the priority is given to the shortest duration process first. Shortest Remaining Time First: A preemptive approach. This approach produces the minimum optimal turnaround times and waiting times theoretically. The main reason of its being impractical is the absence of advance knowledge of process durations. For the above example the average turnaround time and average waiting time with SRTF are 7 units and 3.33 units respectively. The anomalies associated with this strategy are outlined as, Process durations cannot be determined in advance. Probabilistic estimates are used for implementation. Does not support deadlines. Shorter the size higher would be the priority. This theme violates rest of the important factors that must be taken into account like system initiated processes etc. Constant preemption may result in process starvation. Although the average turnaround time and waiting time are optimal as compared to other strategies, but the selection of a feasible schedule for a subset of processes takes factorial time. Priority Algorithm: Non-preemptive and preemptive approach. The main theme is to assign integers as priorities explicitly or through a mathematical model after a careful evaluation of most of the important factors. This resolves the issue of unrealistic priorities of SRTF. The process queue becomes a heap based priority queue which further resolves the problem of accommodating external priorities or system designated specialized priorities. The remedy to starvation is achieved through waiting time based increment in the priority by one. This method is known as aging. The idea fully depends on the model or criteria of priority determination. Any flaw in the process may lead to complete failure. Example Table 2: Deterministic Model for Priority Algorithm with 1 as highest priority Processes Arrival Time Duration/Size Priorities 1 1 5 units 3 2 3 7 units 1 3 4 2 units 2 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 average turnaround time and average waiting time are 9.6 and 5 respectively. The average waiting time is lesser than that of FCFS. The assumptions are same as considered for FCFS. Unlike FCSF and SRTF this algorithm fully supports real time processing. Priority algorithm does not support processes with deadlines and time sharing. Scheduling with Deadlines: The main objective of generalized scheduling is to minimize the total time a job spends in system. Scheduling with deadlines, on the other hand, focuses on the optimization of profit. Table 3 contains example with respective assumptions. Example 1 Table 3: Example 1 Job Deadline Profit 1 2 30 2 1 35 3 2 25 4 1 40 The duration of each job is 1 unit of time. Jobs can be performed before or by their deadlines. The main goal is to find a schedule that reveals maximum yield. A brute force approach considers all feasible schedules and then selects the schedule with maximum profit. This approach takes factorial time. While a greedy approach gives better algorithm. According to Neapolitan (166) following Algorithm 1.1 exhibits greedy approach in solving the problem of scheduling with deadlines. Algorithm 1.1: The objective is to obtain the maximum yield schedule. n represents number of jobs. Array deadline with size n contains respective deadlines. It is sorted according to the respective in profits non increasing order. K contains schedule. J contains optimal sequence. void schedule (int n, const int deadline [], sequence_of_integer& j) { index i; sequence_of_integer K; J = [1]; for (i = 2; i Read More