Scheduling and P vs NP

Scheduling

The problem of scheduling is simply to determine which ready-to-run process should be allowed to run next.  That is, whenever the OS regains control from an executing process as the result of

1. an external hardware interrupt,
2. an exception that occurs during execution of a machine language instruction, or
3. execution of a system call machine language instruction

the OS, since it is now executing, has the opportunity to do some rescheduling.  Whether it does this is up to the operating system design team. 

Part of a design team's efforts will go into the design of algorithms that determine, if rescheduling is to occur, which process should be allowed to execute next.  These algorithms are called scheduling algorithms.

Scheduling Policies

In order to determine which algorithms to apply or design for an OS, the objectives, or policies, of the OS must be determined.  There are various metrics one can look to for guidance:

• Throughput
• Turnaround Time
• Response Time

Throughput

Throughput is a measure of how much work the system accomplished in a particular time frame.  This can be, and usually is, measured as the number of actual jobs (programs) that get done.

Turnaround Time

This is a measure of the amount of time it takes for a particular process (associated with a program whose execution is begun) to complete from the time the request to run the program is made.

Response Time

Response time is a measure of how long it takes the system to respond to an interactive event, such as moving the mouse, clicking on an object, typing a character, and so forth.  It can also refer to how long it takes the system to respond to an external interrupt or event, which is particularly important for real-time operating systems that are typically found in embedded computer systems that drive some device (such as the antilock braking system on your car).

Policies Based on These Metrics

A policy based on these metrics might be, say, to minimize response time, or to maximize throughput. A general computing environment might have processes of various types—some, such as GUI programs, that require minimized response times, others that need to get done by a certain time in the future, but are not interactive, in which case some reasonable turnaround time is expected.  Others might not have any such constraints at all and can run when there is nothing else running (one must be careful to avoid starvation of such processes in this case).

Scheduling Algorithms

Scheduling algorithms are then designed to meet the overall policy of the OS. The objective is to meet some fairness criterion.  In order to accomplish this, a combination of algorithms is often used to ensure that different categories of processes are serviced according to their needs.  Algorithms types often referred to include:

• First Come First Served (FIFO)
• Shortest Job Next
  
• Round Robin

Computability and Tractability

Students often have a bit of difficulty recalling the issues surrounding the ideas of computability and tractability.  Lots of these issues come up in the design of algorithms for OS's.  For example, the idea of allowing the process that will take the least amount of time to execute to be the one to schedule to run next (SJN) is appealing.  However, there is no algorithm that can determine from a list of processes and the data they will execute on which will take the least amount of time.  I.e., this is an unsolvable problem.

In the realm of all problems that we can consider solving by way of a program, computer scientists have identified three categories.

• those that are unsolvable (no program can be written to solve the problem); in computability theory, the most famous instance of such a problem is known as the "halting problem."  No algorithm exists that takes as input some arbitrary algorithm and the data upon which that algorithm is to run and determines whether that input algorithm while running on its input data will ever halt (note that one could write an algorithm that could determine in some cases whether an input algorithm will halt on its given input data, but one could not write an algorithm that will provide a yes or no answer to every possible instance of an input algorithm and its data.  Determining what the shortest running process will be from a group of processes is one of these unsolvable problems.
• those that are intractable.  In computer science parlance, a problem is intractable if there exists no algorithm that solves the problem whose worst case time complexity function is a polynomial.
• those that are tractable.  In computer science parlance, a problem is tractable if there exists an algorithm that solves the problem whose worst case time complexity function is a polynomial.

There is one category of problems that has bedeviled computer scientists for decades, namely, NP-complete problems. The NP stands for "nondeterministic polynomial time."  These problems have three unique attributes:

• they can be solved by an algorithm that runs nondeterministically (for example, can guess an answer and check to see whether it is correct in polynomial time).  The nondeterministic part is the guessing, and, of course, we don't have nondeterministic computers, so the fact that the guessing followed by the checking can be done in polynomial time is of no practical use.  Still, there are problems that are harder than this...no algorithm, not even a nondeterministic one, can guess a possible solution and check it in polynomial time.  Thus, the NP-complete problems are just a way of categorizing a group of problems of interest...those that can be solved in polynomial time if we admit nondeterminism.
• the only known best deterministic algorithms for solving NP-complete problems have exponential time complexity
• no one has been able to prove that there are no deterministic algorithms for solving NP-complete problems.
• if one NP-complete problem can be solved by a deterministic algorithm that has polynomial time complexity, all NP-complete problems have deterministic polynomial time algorithms that solve them (hence the name NP-complete...each such problem represents the complete set of NP problems in terms of their inherent deterministic time complexity).

And the moral is?  If you find that you are about to have to write a program for a problem that is known to be NP-complete (or worse), you will have to resort to heuristics and other approaches that will allow your program to run in polynomial time.  Your program will not give the optimal answer to given input, but it may be able to give useful output.  That is better than providing a program that does solve the problem but runs in exponential time so that it will not produce output for larger instances of the problem in a time period short enough to be useful to the person running the program.