Queues and Algorithms in the Scheduling Context

            Since the early years, computer scientists in the search for computer science solutions to provide high complexity machines to support science, math and business related operations, developed the Queue technique in computing, which was and still one of the most important topics in computer science. “Queue” can be defined as “a storage organization in which objects (in this case, jobs) are ordered in first-in, first-out (abbreviated FIFO fashion.” (Glenn Brookshear, J, 2011). Jobs, in this context can be defined as the instructions (or programs) inserted into the computer operating system, which run a specific operation controlling both software and hardware.

            The most usual type of Queue is the FIFO concept, first-in, first-out, to illustrate it as an analogy it can be compared to the real world concept of line, the first that arrives, the first to get out the line. Something important to point is that the FIFO concept/structure is not always followed, because as in the real world, you can have priority for some kind of person in a line, you can have also a job with more priority. In spite of the FIFO concept be used in the processing context, it is also widely used in Memory Management, File Systems, Algorithms and so many other areas in computing.

            To enrich this research, two other concepts of algorithms will be introduced in order to organize scheduling/processing jobs. First, the Decreasing Time Algorithm or DTA follows the idea of putting all the longest jobs in terms of time to be executed first. It creates the list of tasks by the longest tasks at the top being followed by the shorter ones (James Sousa, 2013).

            To support this idea, consider you have the following process (with one processor) list to be processed defined by name (time to complete):

T1 (5), T4 (2), T2 (6), T3 (8)

By sorting with the Decreasing Time Algorithm, the priority list output would be:

T3 (8), T2 (6), T1 (5), T4 (2).

            The second, is the CPA – Critical Path Algorithm that is similar to the DTA algorithm, but it priories the largest critical time first though. To create the priority list using the CPA algorithm, the largest critical goes to the top preceding the less critical ones, if the critical time is equal so it can get any order, with no distinction.

            I personally believe that every kind of scheduling algorithm has its advantages and disadvantages and it only depends on what kind of solution it must offer. For instance, if you are developing a software in which its main objective is to dispatch e-mails, you could use the CPA (Critical Path Algorithm) with no doubt it would satisfy your needs, considering that the high critical e-mails should be sent first. On the other hand, if you are developing a system in which the user wait for feedback for its operations, you could probably go for FIFO, in which the feedback is much more instantaneous, considering the precedence.

Glenn Brookshear, J, 2011. Computer Science: An Overview. 11th ed. United States of America: Addison-Wesley.

James Sousa. (2013). Scheduling: The Decreasing Time Algorithm. [Online Video]. 16 September 2013. Available from: https://www.youtube.com/watch?v=WlDbWWnBnf4. [Accessed: 27 July 2014].

MATH 103. 2001. Scheduling Algorithms. [ONLINE] Available at: http://www.ctl.ua.edu/math103/scheduling/scheduling_algorithms.htm#Scheduling%20Algorithms. [Accessed 27 July 14].Bottom of Form

Advertisements