Operations on Process scheduling: basic concepts, Preemptive, Non-preemptive, scheduling criteria

From the point of view of a particular process, the important criterion is how long it takes to execute that process.

The interval from the time of submission of a process to the time of completion is the turnaround time.

Turnaround time is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.

2.2.1 Process Scheduling

  • The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization.
  • The objective of time sharing is to switch the CPU among processes so frequently that users can interact with each program while it is running.
  • To meet these objectives, the process scheduler selects an available process (possibly from a set of several available processes) for program execution on the CPU.
  • For a single-processor system, there will never be more than one running process.
  • If there are more processes, the rest will have to wait until the CPU is free and can be rescheduled. Scheduling Queues

  • As processes enter the system, they are put into a job queue, which consists of all processes in the system.
  • The processes that are residing in main memory and are ready and waiting to execute are kept on a list called the ready queue.


  • The process control block in the Linux operating system is represented by the C structure task_struct.
  • This structure contains all the necessary information for representing a process, including the state of the process, scheduling and memory-management information, list of open files, and pointers to the process's parent and any of its children.
  • (A process's parent is the process that created it; its children are any processes that it creates.) Some of these fields include:
          • pid_t pid; /* process identifier */
          • long state; /* state of the process */
          • unsigned int time_slice /* scheduling information */
          • struct task_struct *parent; /* this process's parent */
          • struct list__head children; /* this process's children */
          • struct files_struct *files; /* list of open files */
          • struct mm_struct *mm; /* address space of this process */
  • For example, the state of a process is represented by the field long state in this structure.
  • Within the Linux kernel, all active processes are represented using a doubly linked list of task_struct, and the kernel maintains a pointer ¾ current to the process currently executing on the system.  This is shown in Figure 2.5.

Figure 2.5 Active process in Linux

  • As an illustration of how the kernel might manipulate one of the fields in the task_struct for a specified process, let's assume the system would like to change the state of the process currently running to the value new_state.
  • If current is a pointer to the process currently executing, its state is changed with the following:

current->state = new_state;

  • This queue is generally stored as a linked list. A ready-queue header contains pointers to the first and final PCBs in the list.
  • Each PCB includes a pointer field that points to the next PCB in the ready queue.

Figure 2.6 The ready queue and various I/O device queues.

  • The system also includes other queues. When a process is allocated the CPU, it executes for a while and eventually quits, is interrupted, or waits for the occurrence of a particular event, such as the completion of an I/O request.
  • Suppose the process makes an I/O request to a shared device, such as a disk. Since there are many processes in the system, the disk may be busy with the I/O request of some other process.
  • The process therefore may have to wait for the disk.
  • The list of processes waiting for a particular I/O device is called a device queue.
  • Each device has its own device queue (Figure 2.6).
  • A common representation of process scheduling is a queueing diagram, such as that in Figure 2.7.
  • Each rectangular box represents a queue. Two types of queues are present: the ready queue and a set of device queues.
  • The circles represent the resources that serve the queues, and the arrows indicate the flow of processes in the system.

Figure 2.7 Queueing-diagram representation of process scheduling.

  • A new process is initially put in the ready queue. It waits there until it is selected for execution, or is dispatched. Once the process is allocated the CPU and is executing, one of several events could occur:
    • The process could issue an I/O request and then be placed in an I/O queue.
    • The process could create a new subprocess and wait for the subprocess's termination.
    • The process could be removed forcibly from the CPU, as a result of an interrupt, and be put back in the ready queue.
  • In the first two cases, the process eventually switches from the waiting state to the ready state and is then put back in the ready queue.
  • A process continues this cycle until it terminates, at which time it is removed from all queues and has its PCB and resources deallocated. Schedulers

  • A process migrates among the various scheduling queues throughout its lifetime.
  • The operating system must select, for scheduling purposes, processes from these queues in some fashion.
  • The selection process is carried out by the appropriate scheduler.
  • Often, in a batch system, more processes are submitted than can be executed immediately.
  • These processes are spooled to a mass-storage device (typically a disk), where they are kept for later execution.
  • The long-term scheduler, or job scheduler, selects processes from this pool and loads them into memory for execution.
  • The short-term scheduler, or CPU scheduler, selects from among the processes that are ready to execute and allocates the CPU to one of them.
  • The primary distinction between these two schedulers lies in frequency of execution.
  • The short-term scheduler must select a new process for the CPU frequently.
  • A process may execute for only a few milliseconds before waiting for an I/0 request.
  • Often, the short-term scheduler executes at least once every 100 milliseconds.
  • Because of the short time between executions, the short-term scheduler must be fast.
  • If it takes 10 milliseconds to decide to execute a process for 100 milliseconds, then 10 (100 + 10) = 9 percent of the CPU is being used (wasted) simply for scheduling the work.
  • The long-term scheduler executes much less frequently; minutes may separate the creation of one new process and the next.
  • The long-term scheduler controls the degree of multiprogramming (the number of processes in memory).
  • If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system.
  • Thus, the long-term scheduler may need to be invoked only when a process leaves the system.
  • Because of the longer interval between executions, the long-term scheduler can afford to take more time to decide which process should be selected for execution.
  • It is important that the long-term scheduler make a careful selection.
  • In general, most processes can be described as either I/0 bound or CPU bound.
  • An I/O-bound process is one that spends more of its time doing I/O than it spends doing computations.
  • A CPU-bound process, in contrast, generates I/O requests infrequently, using more of its time doing computations.
  • It is important that the long-term scheduler select a good process mix of I/O-bound and CPU-bound processes.
  • If all processes are I/O bound, the ready queue will almost always be empty, and the short-term scheduler will have little to do.
  • If all processes are CPU bound, the I/O waiting queue will almost always be empty, devices will go unused, and again the system will be unbalanced.
  • The system with the best performance will thus have a combination of CPU-bound and I/O-bound processes.
  • On some systems, the long-term scheduler may be absent or minimal.
  • For example, time-sharing systems such as UNIX and Microsoft Windows systems often have no long-term scheduler but simply put every new process in memory for the short-term scheduler.
  • The stability of these systems depends either on a physical limitation (such as the number of available terminals) or on the self-adjusting nature of human users.

Figure 2.8 Addition of medium-term scheduling to the queueing diagram.

  • If performance declines to unacceptable levels on a multiuser system, some users will simply quit.
  • Some operating systems, such as time-sharing systems, may introduce an additional, intermediate level of scheduling.
  • This medium-term scheduler is diagrammed in Figure 2.8.
  • The key idea behind a medium-term scheduler is that sometimes it can be advantageous to remove processes from memory (and from active contention for the CPU) and thus reduce the degree of multiprogramrning.
  • Later, the process can be reintroduced into memory, and its execution can be continued where it left off. This scheme is called swapping.
  • The process is swapped out, and is later swapped in, by the medium-term scheduler.
  • Swapping may be necessary to improve the process mix or because a change in memory requirements has overcommitted available memory, requiring memory to be freed up. Context Switch

  • As mentioned earlier, interrupts cause the operating system to change a CPU from its current task and to run a kernel routine.
  • Such operations happen frequently on general-purpose systems. When an interrupt occurs, the system needs to save the current Context of the process running on the CPU so that it can restore that context when its processing is done, essentially suspending the process and then resuming it.
  • The context is represented in the PCB of the process; it includes the value of the CPU registers, the process state (see Figure 2.2), and memory-management information.
  • Generically, we perform a state save of current state of the CPU, be it in kernel or user mode, and then a state restore to resume the operations.
  • Switching the CPU to another process requires performing a state save of the current process and a state restore of a different process.
  • This task is known as a Context Switch.
  • When a context switch occurs, the kernel saves the context of the old process in its PCB and loads the saved context of the new process scheduled to run.
  • Context-switch time is pure overhead, because the system does no useful work while switching.
  • Its speed varies from machine to machine, depending on the memory speed, the number of registers that must be copied, and the existence of special instructions (such as a single instruction to load or store all registers).
  • Typical speeds are a few milliseconds.
  • Context-switch times are highly dependent on hardware support. For instance, some processors (such as the Sun UltraSPARC) provide multiple sets of registers.
  • A context switch here simply requires changing the pointer to the current register set. Of course, if there are more active processes than there are register sets, the system resorts to copying register data to and from memory, as before.
  • Also, the more complex the operating system, the more work must be done during a context switch. As we will see, advanced memory-management techniques may require extra data to be switched with each context.
  • For instance, the address space of the current process must be preserved as the space of the next task is prepared for use.
  • How the address space is preserved, and what amount of work is needed to preserve it, depend on the memory-management method of the operating system.

2.2.2 Operations on Processes

  • The processes in most systems can execute concurrently, and they may be created and deleted dynamically.
  • Thus, these systems must provide a mechanism for process creation and termination.
  • In this section, we explore the n1.echanisms involved in creating processes and illustrate process creation on UNIX and Windows systems. Process Creation

  • A process may create several new processes, via a create-process system call, during the course of execution.
  • The creating process is called a parent process, and the new processes are called the children of that process.
  • Each of these new processes may in turn create other processes, forming a tree of processes.
  • Most operating systems (including UNIX and the Windows family of operating systems) identify processes according to a unique process identifier (or pid), which is typically an integer number. Figure 2.9 illustrates a typical process tree for the Solaris operating system, showing the name of each process and its pid.
  • In Solaris, the process at the top of the tree is the sched process, with pid of 0. The sched process creates several children processes-including pageout and fsflush.
  • These processes are responsible for managing memory and file systems.
  • The sched process also creates the ini t process, which serves as the root parent process for all user processes.
  • In Figure 2.9, we see two children of init¾inetd and dtlogin. inetd is responsible for networking services such as telnet and ftp; dtlogin is the process representing a user login screen.
  • When a user logs in, dtlogin creates an X-windows session (Xsession), which in turns creates the sdt_shel process.
  • Below sdt_shel, a user's command-line shell-the C-shell or csh-is created.
  • In this command line interface, the user can then invoke various child processes, such as the ls and cat commands.
  • We also see a csh process with pid of 7778 representing a user who has logged onto the system using telnet.
  • This user has started the Netscape browser (pid of 7785) and the emacs editor (pid of 8105).
  • On UNIX, we can obtain a listing of processes by using the ps command.
  • For example, the command ps -el will list complete information for all processes currently active in the system.

Figure 2.9 A tree of processes on a typical Solaris system.

  • It is easy to construct a process tree similar to what is shown in Figure 2.9 by recursively tracing parent processes all the way to the init process.
  • In general, a process will need certain resources (CPU time, memory, files, I/0 devices) to accomplish its task.
  • When a process creates a subprocess, that subprocess may be able to obtain its resources directly from the operating system, or it may be constrained to a subset of the resources of the parent process.
  • The parent may have to partition its resources among its children, or it may be able to share some resources (such as memory or files) among several of its children.
  • Restricting a child process to a subset of the parent's resources prevents any process from overloading the system by creating too many subprocesses.
  • In addition to the various physical and logical resources that a process obtains when it is created, initialization data (input) may be passed along by the parent process to the child process.
  • For example, consider a process whose function is to display the contents of a file-say, img.jpg-on the screen of a terminal.
  • When it is created, it will get, as an input from its parent process, the name of the file img.jpg, and it will use that file name, open the file, and write the contents out.
  • It may also get the name of the output device. Some operating systems pass resources to child processes.
  • On such a system, the new process may get two open files, img.jpg and the terminal device, and may simply transfer the datum between the two.
  • When a process creates a new process, two possibilities exist in terms of execution:

  1. The parent continues to execute concurrently with its children.
  2. The parent waits until some or all of its children have terminated.

  • There are also two possibilities in terms of the address space of the new process:

  1. The child process is a duplicate of the parent process (it has the same program and data as the parent).
  2. The child process has a new program loaded into it.

  • To illustrate these differences, let's first consider the UNIX operating system.
  • In UNIX, as we've seen, each process is identified by its process identifier, which is a unique integer.
  • A new process is created by the fork() system call. The new process consists of a copy of the address space of the original process.
  • This mechanism allows the parent process to communicate easily with its child process.
  • Both processes (the parent and the child) continue execution at the instruction after the fork () , with one difference: the return code for the fork() is zero for the new (child) process, whereas the (nonzero) process identifier of the child is returned to the parent.
  • Typically, the exec() system call is used after a fork() system call by one of the two processes to replace the process's memory space with a new program.
  • The exec() system call loads a binary file into memory (destroying the memory image of the program containing the exec() system call) and starts its execution.
  • In this manner, the two processes are able to communicate and then go their separate ways.
  • The parent can then create more children; or, if it has nothing else to do while the child runs, it can issue await() system call to move itself off the ready queue until the termination of the child.
  • The C program shown in Figure 2.10 illustrates the UNIX system calls previously described. We now have two different processes running copies of the same program.
  • The only difference is that the value of pid (the process identifier) for the child process is zero, while that for the parent is an integer value greater than zero (in fact, it is the actual pid of the child process).

#include <sysltypes.h>

#include <stdio.h>

#include <unistd.h>

int main()


pid_t pid;

/* fork a child process */

pid =fork();

if (pid < 0)


/* error occurred */

fprintf(stderr, "Fork Failed");

return 1;


else if (pid == 0)


/* child process */



else { /* parent process */

/* parent will wait for the child to complete */

wait (NULL) ;

printf("Child Complete");


return 0;


Figure 2.10 Creating a separate process using the UNIX fork() system call.

  • The child process inherits privileges and scheduling attributes from the parent, as well certain resources, such as open files.
  • The child process then overlays its address space with the UNIX command lines (used to get a directory  listing) using the execlp() system call (execlp() is a version of the exec() system call).
  • The parent waits for the child process to complete with the wait() system call.
  • When the child process completes (by either implicitly or explicitly invoking exit ()) the parent process resumes from the call to wait (),where it completes using the exit() system call. This is also illustrated in Figure 2.11.

Figure 2.11 Process creation using fork() system call.

#include <stdio.h>

#include <windows.h>

int main(VOID)




// allocate memory

ZeroMemory(&si, sizeof(si));

si.cb = sizeof(si);

ZeroMemory(&pi, sizeof(pi));

// create child process

if (!CreateProcess(NULL, // use command line

"C:\\WINDOWS\\system32\\mspaint.exe", // command line

NULL, // don't inherit process handle

NULL, // don't inherit thread handle

FALSE, // disable handle inheritance

0, // no creation flags

NULL, // use parent's environment block

NULL, // use parent's existing directory




     fprintf(stderr, "Create Process Failed");

     return -1;


// parent will wait for the child to complete

WaitForSingleObject(pi.hProcess, INFINITE);

printf("Child Complete");

// close handles




Figure 2.12 Creating a separate process using the Win32 API.

  • As an alternative example, we next consider process creation in Windows.
  • Processes are created in the Win32 API using the CreateProcess () function which is similar to fork () in that a parent creates a new child process.
  • However, whereas fork() has the child process inheriting the address space of its parent CreateProcess () requires loading a specified program into the address space of the child process at process creation.
  • Furthermoref whereas fork() is passed no parameters, CreateProcess () expects no fewer than ten parameters.
  • The C program shown in Figure 2.12 illustrates the CreateProcess () function, which creates a child process that loads the application mspaint. exe.
  • We opt for many of the default values of the ten parameters passed to CreateProcess ().
  • Two parameters passed to CreateProcess() are instances of the STARTUPINFO and PROCESS_INFORMATION structures.
  • STARTUPINFO specifies many properties of the new process, such as window size and appearance and handles to standard input and output files.
  • The PROCESS_INFORMATION structure contains a handle and the identifiers to the newly created process and its thread.
  • We invoke the ZeroMemory() function to allocate memory for each of these structures before proceeding with CreateProcess().
  • The first two parameters passed to CreateProcess () are the application name and command-line parameters.
  • If the application name is NULL (as it is in this case), the command-line parameter specifies the application to load.
  • In this instance, we are loading the Microsoft Windows mspaint.exe application. Beyond these two initial parameters, we use the default parameters for inheriting process and thread handles as well as specifying no creation flags.
  • We also use the parent's existing environment block and starting directory. Last, we provide two pointers to the STARTUPINFO and PROCESS.lNFORMATION structures created at the beginning of the program. In Figure 2.10, the parent process waits for the child to complete by invoking the wait () system call.
  • The equivalent of this in Win32 is WaitForSingleObject(), which is passed a handle of the child process-pi.hProcess-and waits for this process to complete.
  • Once the child process exits, control returns from the WaitForSingleObject () function in the parent process. Process Termination

  • A process terminates when it finishes executing its final statement and asks the operating system to delete it by using the exit () system call.
  •  At that point, the process may return a status value (typically an integer) to its parent process (via the wait() system call).
  • All the resources of the process-including physical and virtual memory, open files, and I/O buffers-are deallocated by the operating system.
  • Termination can occur in other circumstances as well. A process can cause the termination of another process via an appropriate system call (for example, TerminateProcess () in Win32).
  • Usually, such a system call can be invoked only by the parent of the process that is to be terminated.
  • Otherwise, users could arbitrarily kill each other's jobs. Note that a parent needs to know the identities of its children.
  • Thus, when one process creates a new process, the identity of the newly created process is passed to the parent.
  • A parent may terminate the execution of one of its children for a variety of reasons, such as these:
    • The child has exceeded its usage of some of the resources that it has been allocated. (To determine whether this has occurred, the parent must have a mechanism to inspect the state of its children.)
    • The task assigned to the child is no longer required.
    • The parent is exiting, and the operating system does not allow a child to continue if its parent terminates.
  • Some systems, including VMS, do not allow a child to exist if its parent has terminated.
  • In such systems, if a process terminates (either normally or abnormally), then all its children must also be terminated.
  • This phenomenon, referred to as cascading termination, is normally initiated by the operating system.
  • To illustrate process execution and termination, consider that, in UNIX, we can terminate a process by using the exit() system call; its parent process may wait for the termination of a child process by using the wait() system call.
  • The wait() system call returns the process identifier of a terminated child so that the parent can tell which of its children has terminated.
  • If the parent terminates, however, all its children have assigned as their new parent the init process.
  • Thus, the children still have a parent to collect their status and execution statistics.

2.2.3 Basic Concepts

  • In a single-processor system, only one process can run at a time; any others must wait until the CPU is free and can be rescheduled.
  • The objective of multiprogramming is to have some process rum1ing at all times, to maximize CPU utilization.
  • The idea is relatively simple. A process is executed until it must wait, typically for the completion of some I/O request.
  • In a simple computer system, the CPU then just sits idle. All this waiting time is wasted; no useful work is accomplished.
  • With multiprogramming, we try to use this time productively. Several processes are kept in memory at one time.
  • When one process has to wait, the operating system takes the CPU away from that process and gives the CPU to another process. This pattern continues.
  • Every time one process has to wait, another process can take over use of the CPU.
  • Scheduling of this kind is a fundamental operating-system function.
  • Almost all computer resources are scheduled before use. The CPU is, of course, one of the primary computer resources. Thus, its scheduling is central to operating-system design. CPU-I/O Burst Cycle

Figure 2.13 Alternating sequence of CPU and I/O bursts.

  • The success of CPU scheduling depends on an observed property of processes: process execution consists of a cycle of CPU execution and I/O wait.
  • Processes alternate between these two states. Process execution begins with a CPU burst.
  • That is followed by an I/O burst, which is followed by another CPU burst, then another I/0 burst, and so on.
  • Eventually, the final CPU burst ends with a system request to terminate execution (Figure 2.13)
  • The duration of CPU bursts have been measured extensively.
  • Although they vary greatly from process to process and from computer to computer, they tend to have a frequency curve similar to that shown in Figure 2.14.

Figure 2.14 Histogram of CPU-burst durations.

  • The curve is generally characterized as exponential or hyper exponential, with a large number of short CPU bursts and a small number of long CPU bursts. An I/O - bound program typically has many short CPU bursts.
  • A CPU-bound program might have a few long CPU bursts. This distribution can be important in the selection of an appropriate CPU-scheduling algorithm. CPU Scheduler

  • Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed.
  • The selection process is carried out by the short-term scheduler (or CPU scheduler). The scheduler selects a process from the processes in memory that are ready to execute and allocates the CPU to that process.
  • Note that the ready queue is not necessarily a first-in, first-out (FIFO) queue.
  • As we shall see when we consider the various scheduling algorithms, a ready queue can be implemented as a FIFO queue, a priority queue, a tree, or simply an unordered linked list.
  • Conceptually, however, all the processes in the ready queue are lined up waiting for a chance to run on the CPU.
  • The records in the queues are generally process control blocks (PCBs) of the processes. Preemptive Scheduling

  • CPU-scheduling decisions may take place under the following four circumstances:

  1. When a process switches from the running state to the waiting state (for example, as the result of an I/O request or an invocation of wait for the termination of one of the child processes)
  2. When a process switches from the running state to the ready state (for example, when an interrupt occurs)
  3. When a process switches from the waiting state to the ready state (for example, at completion of I/O)
  4. When a process terminates

  • For situations 1 and 4, there is no choice in terms of scheduling.
  • A new process (if one exists in the ready queue) must be selected for execution.
  • There is a choice, however, for situations 2 and 3.
  • When scheduling takes place only under circumstances 1 and 4, we say that the scheduling scheme is non preemptive or cooperative; otherwise, it is preemptive.
  • Under non preemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state.
  • This scheduling method was used by Microsoft Windows 3.x; Windows 95 introduced preemptive scheduling, and all subsequent versions of Windows operating systems have used preemptive scheduling.
  • The Mac OS X operating system for the Macintosh also uses preemptive scheduling; previous versions of the Macintosh operating system relied on cooperative scheduling.
  • Cooperative scheduling is the only method that can be used on certain hardware platforms, because it does not require the special hardware (for example, a timer) needed for preemptive scheduling.
  • Unfortunately, preemptive scheduling incurs a cost associated with access to shared data.
  • Consider the case of two processes that share data. While one is updating the data, it is preempted so that the second process can run.
  • The second process then tries to read the data, which are in an inconsistent state. In such situations, we need new mechanisms to coordinate access to shared data.
  • Preemption also affects the design of the operating-system kernel.
  • During the processing of a system call, the kernel may be busy with an activity on behalf of a process.
  • Such activities may involve changing important kernel data (for instance, I/0 queues).
  • What happens if the process is preempted in the middle of these changes and the kernel (or the device driver) needs to read or modify the same structure? Chaos ensues.
  • Certain operating systems, including most versions of UNIX, deal with this problem by waiting either for a system call to complete or for an I/O block to take place before doing a context switch.
  • This scheme ensures that the kernel structure is simple, since the kernel will not preempt a process while the kernel data structures are in an inconsistent state.
  • Unfortunately, this kernel-execution model is a poor one for supportil1g real-time computing and multiprocessing.
  • Because interrupts can, by definition, occur at any time, and because they cannot always be ignored by the kernel, the sections of code affected by interrupts must be guarded from simultaneous use.
  • The operating system needs to accept interrupts at almost all times; otherwise, input might be lost or output overwritten.
  • So that these sections of code are not accessed concurrently by several processes, they disable interrupts at entry and reenable interrupts at exit.
  • It is important to note that sections of code that disable interrupts do not occur very often and typically contain few instructions. Dispatcher

  • Another component involved in the CPU-scheduling function is the dispatcher.
  • The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves the following:
    • Switching context
    • Switching to user mode
    • Jumping to the proper location in the user program to restart that program
  • The dispatcher should be as fast as possible, since it is invoked during every process switch.
  • The time it takes for the dispatcher to stop one process and start another running is known as the dispatch latency.

2.2.4 Scheduling Criteria

  • Different CPU-scheduling algorithms have different properties, and the choice of a particular algorithm may favor one class of processes over another.
  • In choosing which algorithm to use in a particular situation, we must consider the properties of the various algorithms.
  • Many criteria have been suggested for comparing CPU-scheduling algorithms.
  • Which characteristics are used for comparison can make a substantial difference in which algorithm is judged to be best. The criteria include the following:
    • CPU utilization.
      • We want to keep the CPU as busy as possible. Conceptually, CPU utilization can range from 0 to 100 percent.
      • In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily used system).
    • Throughput.
      • If the CPU is busy executing processes, then work is being done.
      • One measure of work is the number of processes that are completed per time unit, called throughput.
      • For long processes, this rate may be one process per hour; for short transactions, it may be ten processes per second.
    • Turnaround time.
      • From the point of view of a particular process, the important criterion is how long it takes to execute that process.
      • The interval from the time of submission of a process to the time of completion is the turnaround time.
      • Turnaround time is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.
    • Waiting time.
      • The CPU-scheduling algorithm does not affect the amount of time during which a process executes or does I/O; it affects only the amount of time that a process spends waiting in the ready queue.
      • Waiting time is the sum of the periods spent waiting in the ready queue.
    • Response time.
      • In an interactive system, turnaround time may not be the best criterion.
      • Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user.
      • Thus, another measure is the time from the submission of a request until the first response is produced.
      • This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.
      • The turnaround time is generally limited by the speed of the output device.
  • It is desirable to maximize CPU utilization and throughput and to minimize turnaround time, waiting time, and response time.
  • In most cases, we optimize the average measure.
  • However, under some circumstances, it is desirable to optimize the minimum or maximum values rather than the average.
  • For example, to guarantee that all users get good service, we may want to minimize the maximum response time.
  • Investigators have suggested that, for interactive systems (such as timesharing systems), it is more important to minimize the variance in the response time than to minimize the average response time.
  • A system with reasonable and predictable response time may be considered more desirable than a system that is faster on the average but is highly variable.
  • However, little work has been done on CPU-scheduling algorithms that minimize variance.
  • As we discuss various CPU-scheduling algorithms in the following section, we illustrate their operation. An accurate illustration should involve many processes, each a sequence of several hundred CPU bursts and I/O bursts.
  • For simplicity, though, we consider only one CPU burst (in milliseconds) per process in our examples. Our measure of comparison is the average waiting time.


    1. The Operating System Concepts by Silberschatz, Galvin, Gagne, 8th Edition
    2. MODERN OPERATING SYSTEMS by Andrew S. Tanenbaum, Second Edition

    Last modified: Sunday, 19 November 2017, 11:35 AM