{"id":54,"date":"2018-07-19T05:10:18","date_gmt":"2018-07-19T05:10:18","guid":{"rendered":"http:\/\/csp3.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=54"},"modified":"2018-08-07T05:00:25","modified_gmt":"2018-08-07T05:00:25","slug":"cpu-scheduling-i","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/chapter\/cpu-scheduling-i\/","title":{"rendered":"CPU Scheduling – I"},"content":{"raw":"
\r\n\r\n \r\n

7.1 Introduction\u00a0<\/strong><\/p>\r\n \r\n

CPU scheduling is used in operating systems to make use of the processor time to the maximum and to provide multiple users with a feel that they are the sole users of the system. This module explains the basic concepts of CPU scheduling and the different criteria needed for evaluating CPU scheduling algorithms and the working of the First Come First Served (FCFS) and non-preemptive Shortest Job First (SJF) CPU scheduling algorithms.<\/p>\r\n \r\n

7.2 Basic Concepts\u00a0<\/strong><\/p>\r\n \r\n

In a multiprogramming system, many processes are kept in memory at a particular time. Any process, during execution may have to wait for the completion of some I\/O request. During this time, the CPU will remain idle. But, the objective of multiprogramming is to have some program running always and hence maximize CPU utilization. Hence, when a process waits for I\/O, the operating system takes away t he CPU from the process and assigns the CPU to another process. But, of the many processes residing in the memory, which is the next process to which the CPU is assigned? This selection is done by the CPU scheduler.<\/p>\r\n \r\n

The success of CPU scheduling depends on the following property of processes: Process execution comprises a cycle of CPU execution (CPU burst) and I\/O wait (I\/O burst). Any process alternates between these two states. Process execution begins with a CPU burst. This CPU burst is followed by an I\/O burst, then a CPU burst, then an I\/O burst and so on. Figure 7.1 shows an example of how a process alternates between CPU and I\/O bursts, during its execution.<\/p>\r\n \r\n

Consider the followi ng program in C to find the sum of two numbers:<\/p>\r\n

int main(void)<\/p>\r\n

{<\/p>\r\n

int a,b, sum;<\/p>\r\n

\/*I\/O burst*\/<\/p>\r\n

printf(\u201cEnter the two numbers to be added\\n\u201d);<\/p>\r\n

scanf(\u201c%d %d\u201d,&a,&b);<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n\/*CPU burst *\/\r\n\r\nsum = a+b;\r\n\r\n\/*I\/O burst*\/\r\n\r\nprintf(\u201c The sum of %d and %d is %d \\n\u201d, a,b,sum);\r\n\r\nreturn 0;\r\n\r\n}\r\n\r\n \r\n

It can be seen that the first two statements are I\/O bound, the third statement is CPU-bound and the next statement is I\/O bound. Thus any program will \u00a0have alternating CPU-bound and I\/O bound i nstructions.<\/p>\r\n\"\"\r\n

Fig. 7.1 Alternating sequence of CPU and I\/O bursts (Source: [1])<\/p>\r\n \r\n

If a program has few and very long CPU bursts , it is a CPU-bound program. An I\/O-bound program has many very short CPU bursts . The duration of CPU bursts vary from process to process and from computer to computer. Still, the CPU bursts tend to have a frequency curve similar to that shown i n Figure 7.2. It is seen from Figure 7.2 that very short CPU bursts are more frequent than long CPU bursts. Whenever a CPU burst ends, there is an I\/O burst. When there is an I\/O burst, the process has to wait for I\/O to get completed and is moved to the waiting state. Now, the CPU scheduler has to run to select the next process that should be assigned the CPU. Since the CPU bursts are frequent, the CPU scheduler has to run frequently.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Fig. 7.2 Histogram of CPU-burst times (Source: [1])<\/p>\r\n \r\n\r\n7.3 <\/strong>C<\/strong>P<\/strong>U Scheduler<\/strong>\r\n\r\n \r\n

Whenever the CPU becomes idle, the operating system should select one of the processes in the ready queue and that process is assigned the CPU. This selection is done by the CPU scheduler. The CPU scheduler is also called the s hort-term scheduler. The CPU scheduler selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them. The ready queue from which the processes are selected need not be a first i n, first out queue, always. The ready queue may even be a priority queue, a tree or an unordered linked list.<\/p>\r\n \r\n\r\nFigure 7.3 shows the change i n states during the lifetime of a process. CPU scheduling decisions may take place when a process:\r\n\r\n \r\n\r\n1.\u00a0 Switches from running to waiting state (I\/O, wait system call)\r\n\r\n2.\u00a0 Switches from running to ready state (timer i nterrupt)\r\n\r\n3.\u00a0 Switches from waiti ng to ready (completion of I\/O)\r\n\r\n4.\u00a0 Termi nates\r\n\r\n<\/div>\r\n\"\"\r\n

\r\n

Fig. 7.3 Process state transition diagram<\/p>\r\n \r\n

When the process switches from the running state to the waiting state or when the process terminates, the process relinquishes the CPU on its own. It is not forced to relinquish the CPU. When scheduling takes place in these circumstances, it is called non-preemptive CPU scheduling. When the process moves from the waiting state to the ready state or when the process moves from the running state to the ready state, the CPU is forcibly removed from the process. The scheduling that happens in these circumstances is called preemptive scheduling.<\/p>\r\n \r\n\r\n7.4\u00a0 Dispatcher\u00a0<\/strong>\r\n\r\n \r\n

Only the selection of which process will use the CPU next is done by the CPU scheduler. The dispatcher module is the one that gives control of the CPU to the process selected by the short-term scheduler. The dispatcher takes care of the following:<\/p>\r\n \r\n\r\n1. Switching context\r\n\r\n2. Switching to user mode\r\n

3. Jumping to the proper location in the user program to restart that program Thus, it takes some \u00a0time for the dispatcher to stop one process and start another process. This time is called dispatch latency. The dispatch latency should be as less as possible because the CPU does not do any useful work during this period.<\/p>\r\n \r\n\r\n7.5 Scheduling Criteria\u00a0<\/strong>\r\n\r\n \r\n

Many CPU scheduling algorithms have been proposed. To select the best CPU scheduling algorithm, various criteria can be considered. The following are some of the criteria that are used to analyze the performance of any CPU scheduling algorithm:<\/p>\r\n \r\n\r\n1. CPU utilization \u2013 Keep the CPU as busy as possible. Hence, CPU utilization should be maximum.\r\n

2. Throughput \u2013 Number of processes that complete their execution per time unit.\u00a0<\/span>Throughput should be maximum.<\/span><\/p>\r\n

3. Turnaround time \u2013 amount of time to execute a particular process. This should be as minimum as possible.<\/span><\/p>\r\n4. Waiting time \u2013 amount of time a process has been waiting in the ready queue.\u00a0<\/span>This should be as minimum as possible.<\/span>\r\n

5. Response time \u2013 amount of time it takes from when a request was submitted\u00a0<\/span>until the first response is produced, not output (for time-sharing environment). Response time should be as minimum as possible.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n7.6 Scheduling algorithms\u00a0<\/strong>\r\n\r\n \r\n

In this section, we will learn two CPU scheduling algorithms, First Come First Served (FCFS) scheduling and Shortest Job First (SJF) scheduling algorithms.<\/p>\r\n \r\n\r\n7.6.1 First-Come, First-Served (FCFS) Scheduling\u00a0<\/strong>\r\n\r\n \r\n

In FCFS, the process that arrived first and requests the CPU first is assigned the CPU first. In FCFS, the ready queue can be maintained as a FIFO queue. When processes arrive they are added to the tail of the queue. When the CPU becomes free, the process in the head of the queue is taken for execution. This is a non-preemptive algorithm. Once a process is assigned the CPU, the process continues to use the CPU till its CPU burst time is completed. When its CPU burst gets over, the process by itself relinquishes the CPU. FCFS is explained with an example given below:<\/p>\r\n \r\n

Consider three processes P<\/em>1, P<\/em>2 and P<\/em>3 with CPU-burst times 24 milliseconds (ms), 3 ms and 3 ms respectively. All three processes arrive at the same time i n the order P<\/em>1, P<\/em>2, P<\/em>3.<\/p>\r\n \r\n

The Gantt chart that shows the order i n which processes are assigned the CPU is shown below. Since process P<\/em>1 is the first process in the queue, P<\/em>1\u00a0 is assigned the CPU first. P<\/em>1 has a CPU-burst length of 24 ms. P<\/em>1 uses the CPU for 24 ms and then relinquishes the CPU as shown in Figure 7.4.<\/p>\r\n\"\"\r\n

Fig. 7.4 Process P<\/em>1 using the CPU<\/p>\r\n \r\n

The next process i n the queue is P<\/em>2. P<\/em>2 is scheduled next. P<\/em>2 has a CPU-burst time of 3 ms and uses the CPU till 27 ms as shown in Figure 7.5.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Fig. 7.5 Process P<\/em>2 using the CPU<\/p>\r\n \r\n

After P<\/em>2, P<\/em>3 is the only process in the queue and it is assigned the CPU. P<\/em>3 uses the CPU for a time duration of 3 ms and then relinquishes the CPU as shown i n Figure 7.6.<\/p>\r\n\"\"\r\n

Fig. 7.4 Process P<\/em>3 using the CPU<\/p>\r\n \r\n

The waiting time for each process and hence the average waiting time can be calculated. Since all the three processes arrive at the same time, the arrival time of the processes is taken as 0. Process P<\/em>1 arrived at time 0 and was assigned the CPU immediately. Hence, the waiting time for P<\/em>1 = 0. Process P<\/em>2 arrived at time 0 and was assigned the CPU at time 24. Hence, the waiting time for P<\/em>2 = 24. Process P3 arrived at time 0 and was assigned the CPU at time 27. Hence, the waiting time for P<\/em>3 = 27. Hence, the average waiting time is (0 + 24 + 27) \/ 3 = 17.<\/p>\r\n \r\n

Similarly, the turnaround time for each process and hence the average turnaround time can be calculated. Process P<\/em>1 arrived at time 0 and completed its CPU burst at time 24. Hence, the turnaround time for P<\/em>1 = 24. Process P<\/em>2 arrived at time 0 and completed its CPU burst at time 27. Hence, the turnaround time for P<\/em>2 = 27. Process P<\/em>3 arrived at time 0 and completed its CPU burst at time 30. Hence, the turnaround time for P<\/em>3 = 30.The average turnaround time is (24 + 27 + 30) \/ 3 = 27.<\/p>\r\n \r\n\r\nSuppose if the three processes arrive in the order P<\/em>2, P<\/em>3, P<\/em>1. The Gantt chart for the schedule is as shown in Figure 7.5.\r\n\r\n\"\"\r\n

Fig. 7.5 Gantt chart with the order of the processes changed<\/p>\r\n \r\n

The waiting time of the processes can be calculated as follows: The arrival time for all the processes is the same and is taken as 0. Therefore, the waiting time for P<\/em>1 = <\/em>6, P<\/em>2 = 0 and P<\/em>3 = <\/em>3. The average waiting time is (6 + 0 + 3)\/3 = 3. The turnaround time for P<\/em>1 = <\/em>30, P<\/em>2 = 3 and P<\/em>3 = <\/em>6. Therefore, the average turnaround time is (3 + 6 + 30)\/3 = 13. It is seen that the average waiting time and the average turnaround time have improved when the order of the processes is changed. In the earlier case, process P<\/em>1 had a long\u00a0CPU burst and the other processes had to wait for <\/span>P<\/em>1 to complete its CPU burst. This increased the average waiting time and the average turnaround time.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n7.6.2\u00a0 Shortest-Job-First (SJF) Scheduling\u00a0<\/strong>\r\n\r\n \r\n

The SJF CPU scheduling algorithm associates with each process the length of its next CPU burst. These lengths are used to schedule the process with the shortest time. When the CPU becomes available, the process with the shortest next CPU burst is assigned the CPU. There are two schemes i n SJF. One is non-preemptive in which once CPU is assigned to a process, it cannot be preempted until it completes its CPU burst. The other is preemptive in which if a new process arrives with CPU burst length less than the remaining time of the currently executing process, the currently executing process is preempted. This scheme is known as the Shortest-Remaining-Time-First (SRTF). In this module, we will learn how scheduling is done i n non-preemptive SJF.<\/p>\r\n \r\n\r\nConsider four processes P<\/em>1, P<\/em>2, P<\/em>3\u00a0 and P<\/em>4. <\/em>The arri val times and the CPU-burst times of the four processes are gi ven below:\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
Process<\/strong><\/td>\r\nArriva l Time<\/strong><\/td>\r\nBurst Time<\/strong><\/td>\r\n<\/tr>\r\n
P<\/em>1<\/td>\r\n0.0<\/td>\r\n7<\/td>\r\n<\/tr>\r\n
P<\/em>2<\/td>\r\n2.0<\/td>\r\n4<\/td>\r\n<\/tr>\r\n
P<\/em>3<\/td>\r\n4.0<\/td>\r\n1<\/td>\r\n<\/tr>\r\n
P<\/em>4<\/td>\r\n5.0<\/td>\r\n4<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

At time 0.0, P<\/em>1 is the only process that has arrived. Hence , P<\/em>1 is assigned the CPU first. Since it is non-preemptive SJF scheduling, P<\/em>1 continues to use the CPU till its CPU-burst gets over as shown in Figure 7.6<\/p>\r\n\"\"\r\n

Fig. 7.6 Process P<\/em>1 using the CPU<\/p>\r\n \r\n

After P<\/em>1 finishes its CPU-burst, the processes remaining i n the ready queue are P<\/em>2, P<\/em>3 and P<\/em>4. The processes P<\/em>2, P<\/em>3\u00a0 and P<\/em>4 have now arrived. Of these three processes, P<\/em>3 has the shortest CPU burst. Hence, P<\/em>3 is assigned the CPU. P<\/em>3 makes use of the CPU for a time duration that is equal to its CPU burst (1 ms) and then relinquishes the CPU as in Figure 7.7.<\/p>\r\n\"\"\r\n

Fig. 7.7 Process P<\/em>3usingtheCPU<\/p>\r\n\r\n<\/div>\r\n \r\n

P<\/em>2 and <\/span>P<\/em>4 are the remaining processes. Both the processes have the same CPU burst time. Any one of these can be assigned the CPU. So, the tie is now broken using FCFS. Of the two processes, <\/span>P<\/em>2 arrived earlier. Hence, <\/span>P<\/em>2 is assigned the CPU and <\/span>P<\/em>2 executes till its CPU burst is completed as i n Figure 7.8.<\/span><\/p>\r\n\r\n

\r\n\r\n\"\"\r\n

Fig. 7.8 P<\/em>2 using the CPU<\/p>\r\n \r\n

After P<\/em>2 finishes execution, the only process waiting is P<\/em>4. P<\/em>4 is now assigned the CPU. After P<\/em>4 runs for its CPU-burst time, it relinquishes the CPU as shown i n Figure 7.9.<\/p>\r\n\"\"\r\n

Fig. 7.9 P<\/em>4 using the CPU<\/p>\r\n \r\n

The average waiting time and the average turnaround time can be calculated as follows. The waiting time for process P<\/em>1 is 0. P<\/em>1 arrived at time 0 and was assigned the CPU immediately. P<\/em>1 did not wait. P<\/em>2 arrived at time 2.0 and was assigned the CPU at time 8.0. Hence, the waiting time for process P<\/em>2 is 8 - 2 = 6. P<\/em>3 arrived at time 4.0 and was assigned the CPU at time 7.0. Hence, the waiting time for process P<\/em>2 is 7 - 4 = 3. Process P<\/em>4 arrived at time 5.0 and was assigned the CPU at time 12.0. Hence the waiting time of process P<\/em>2 is 12 - 5 = 7. Hence, the average waiting time = (0 + (8 - 2) + (7 - 4) + (12 - 5)) \/ 4 = 4.<\/p>\r\n \r\n

P<\/em>1 arrived at time 0 and completed execution at 7. The turnaround time of process P<\/em>1 is 7. P<\/em>2 arrived at time 2.0 and completed execution at time 12.0. Hence, the turnaround time for process P<\/em>2 is 12 - 2 = 10. P<\/em>3 arrived at time 4.0 and completed execution at time 8.0. Hence , the waiting time for process P<\/em>2 is 8 - 4 = 4. Process P<\/em>4 arrived at time 5.0 and completed execution at time 16.0. Hence , the turnaround time of process P<\/em>2 is 16 - 5 = 11. Hence the a verage waiting time = (0 + (8 - 2) + (7 - 4) + (12 - 5)) \/ 4 = 4. Hence, the average turnaround time = ((7 - 0) + (12 - 2) + (8 - 4) + (16 - 5)) \/\u00a0 4 = 32 \/ 4 =8.<\/p>\r\n \r\n\r\n7.7\u00a0 Summary\u00a0<\/strong>\r\n\r\n \r\n

In this module, we learnt what CPU scheduling is. Multiprogramming maximizes CPU utilization. The CPU scheduler selects the next process that should be assigned the \u00a0CPU. \u00a0Many CPU scheduling algorithms \u00a0have \u00a0been proposed. CPU scheduling\u00a0algorithms can be preemptive or non-preemptive. In this module, we learnt how First Come First Served (FCFS) and non-preemptive Shortest Job First (SJF) CPU scheduling algorithms work. We saw that SJF has less waiting time and less turnaround time when compared to FCFS.<\/span><\/p>\r\n\r\n<\/div>\r\n \r\n

References<\/strong><\/p>\r\n\r\n

    \r\n \t
  1. Abraham Silberschatz, \u00a0Peter \u00a0B. \u00a0Galvin, \u00a0Greg \u00a0Gagne, \u00a0\u201cOperating \u00a0System Concepts\u201d, Sixth Edition, John Wiley & Sons Inc., 2003.<\/li>\r\n<\/ol>","rendered":"
    \n

     <\/p>\n

    7.1 Introduction\u00a0<\/strong><\/p>\n

     <\/p>\n

    CPU scheduling is used in operating systems to make use of the processor time to the maximum and to provide multiple users with a feel that they are the sole users of the system. This module explains the basic concepts of CPU scheduling and the different criteria needed for evaluating CPU scheduling algorithms and the working of the First Come First Served (FCFS) and non-preemptive Shortest Job First (SJF) CPU scheduling algorithms.<\/p>\n

     <\/p>\n

    7.2 Basic Concepts\u00a0<\/strong><\/p>\n

     <\/p>\n

    In a multiprogramming system, many processes are kept in memory at a particular time. Any process, during execution may have to wait for the completion of some I\/O request. During this time, the CPU will remain idle. But, the objective of multiprogramming is to have some program running always and hence maximize CPU utilization. Hence, when a process waits for I\/O, the operating system takes away t he CPU from the process and assigns the CPU to another process. But, of the many processes residing in the memory, which is the next process to which the CPU is assigned? This selection is done by the CPU scheduler.<\/p>\n

     <\/p>\n

    The success of CPU scheduling depends on the following property of processes: Process execution comprises a cycle of CPU execution (CPU burst) and I\/O wait (I\/O burst). Any process alternates between these two states. Process execution begins with a CPU burst. This CPU burst is followed by an I\/O burst, then a CPU burst, then an I\/O burst and so on. Figure 7.1 shows an example of how a process alternates between CPU and I\/O bursts, during its execution.<\/p>\n

     <\/p>\n

    Consider the followi ng program in C to find the sum of two numbers:<\/p>\n

    int main(void)<\/p>\n

    {<\/p>\n

    int a,b, sum;<\/p>\n

    \/*I\/O burst*\/<\/p>\n

    printf(\u201cEnter the two numbers to be added\\n\u201d);<\/p>\n

    scanf(\u201c%d %d\u201d,&a,&b);<\/p>\n<\/div>\n

    \n

     <\/p>\n

    \/*CPU burst *\/<\/p>\n

    sum = a+b;<\/p>\n

    \/*I\/O burst*\/<\/p>\n

    printf(\u201c The sum of %d and %d is %d \\n\u201d, a,b,sum);<\/p>\n

    return 0;<\/p>\n

    }<\/p>\n

     <\/p>\n

    It can be seen that the first two statements are I\/O bound, the third statement is CPU-bound and the next statement is I\/O bound. Thus any program will \u00a0have alternating CPU-bound and I\/O bound i nstructions.<\/p>\n

    \"\"<\/p>\n

    Fig. 7.1 Alternating sequence of CPU and I\/O bursts (Source: [1])<\/p>\n

     <\/p>\n

    If a program has few and very long CPU bursts , it is a CPU-bound program. An I\/O-bound program has many very short CPU bursts . The duration of CPU bursts vary from process to process and from computer to computer. Still, the CPU bursts tend to have a frequency curve similar to that shown i n Figure 7.2. It is seen from Figure 7.2 that very short CPU bursts are more frequent than long CPU bursts. Whenever a CPU burst ends, there is an I\/O burst. When there is an I\/O burst, the process has to wait for I\/O to get completed and is moved to the waiting state. Now, the CPU scheduler has to run to select the next process that should be assigned the CPU. Since the CPU bursts are frequent, the CPU scheduler has to run frequently.<\/p>\n<\/div>\n

    \n

    \"\"<\/p>\n

    Fig. 7.2 Histogram of CPU-burst times (Source: [1])<\/p>\n

     <\/p>\n

    7.3 <\/strong>C<\/strong>P<\/strong>U Scheduler<\/strong><\/p>\n

     <\/p>\n

    Whenever the CPU becomes idle, the operating system should select one of the processes in the ready queue and that process is assigned the CPU. This selection is done by the CPU scheduler. The CPU scheduler is also called the s hort-term scheduler. The CPU scheduler selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them. The ready queue from which the processes are selected need not be a first i n, first out queue, always. The ready queue may even be a priority queue, a tree or an unordered linked list.<\/p>\n

     <\/p>\n

    Figure 7.3 shows the change i n states during the lifetime of a process. CPU scheduling decisions may take place when a process:<\/p>\n

     <\/p>\n

    1.\u00a0 Switches from running to waiting state (I\/O, wait system call)<\/p>\n

    2.\u00a0 Switches from running to ready state (timer i nterrupt)<\/p>\n

    3.\u00a0 Switches from waiti ng to ready (completion of I\/O)<\/p>\n

    4.\u00a0 Termi nates<\/p>\n<\/div>\n

    \"\"<\/p>\n

    \n

    Fig. 7.3 Process state transition diagram<\/p>\n

     <\/p>\n

    When the process switches from the running state to the waiting state or when the process terminates, the process relinquishes the CPU on its own. It is not forced to relinquish the CPU. When scheduling takes place in these circumstances, it is called non-preemptive CPU scheduling. When the process moves from the waiting state to the ready state or when the process moves from the running state to the ready state, the CPU is forcibly removed from the process. The scheduling that happens in these circumstances is called preemptive scheduling.<\/p>\n

     <\/p>\n

    7.4\u00a0 Dispatcher\u00a0<\/strong><\/p>\n

     <\/p>\n

    Only the selection of which process will use the CPU next is done by the CPU scheduler. The dispatcher module is the one that gives control of the CPU to the process selected by the short-term scheduler. The dispatcher takes care of the following:<\/p>\n

     <\/p>\n

    1. Switching context<\/p>\n

    2. Switching to user mode<\/p>\n

    3. Jumping to the proper location in the user program to restart that program Thus, it takes some \u00a0time for the dispatcher to stop one process and start another process. This time is called dispatch latency. The dispatch latency should be as less as possible because the CPU does not do any useful work during this period.<\/p>\n

     <\/p>\n

    7.5 Scheduling Criteria\u00a0<\/strong><\/p>\n

     <\/p>\n

    Many CPU scheduling algorithms have been proposed. To select the best CPU scheduling algorithm, various criteria can be considered. The following are some of the criteria that are used to analyze the performance of any CPU scheduling algorithm:<\/p>\n

     <\/p>\n

    1. CPU utilization \u2013 Keep the CPU as busy as possible. Hence, CPU utilization should be maximum.<\/p>\n

    2. Throughput \u2013 Number of processes that complete their execution per time unit.\u00a0<\/span>Throughput should be maximum.<\/span><\/p>\n

    3. Turnaround time \u2013 amount of time to execute a particular process. This should be as minimum as possible.<\/span><\/p>\n

    4. Waiting time \u2013 amount of time a process has been waiting in the ready queue.\u00a0<\/span>This should be as minimum as possible.<\/span><\/p>\n

    5. Response time \u2013 amount of time it takes from when a request was submitted\u00a0<\/span>until the first response is produced, not output (for time-sharing environment). Response time should be as minimum as possible.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    7.6 Scheduling algorithms\u00a0<\/strong><\/p>\n

     <\/p>\n

    In this section, we will learn two CPU scheduling algorithms, First Come First Served (FCFS) scheduling and Shortest Job First (SJF) scheduling algorithms.<\/p>\n

     <\/p>\n

    7.6.1 First-Come, First-Served (FCFS) Scheduling\u00a0<\/strong><\/p>\n

     <\/p>\n

    In FCFS, the process that arrived first and requests the CPU first is assigned the CPU first. In FCFS, the ready queue can be maintained as a FIFO queue. When processes arrive they are added to the tail of the queue. When the CPU becomes free, the process in the head of the queue is taken for execution. This is a non-preemptive algorithm. Once a process is assigned the CPU, the process continues to use the CPU till its CPU burst time is completed. When its CPU burst gets over, the process by itself relinquishes the CPU. FCFS is explained with an example given below:<\/p>\n

     <\/p>\n

    Consider three processes P<\/em>1, P<\/em>2 and P<\/em>3 with CPU-burst times 24 milliseconds (ms), 3 ms and 3 ms respectively. All three processes arrive at the same time i n the order P<\/em>1, P<\/em>2, P<\/em>3.<\/p>\n

     <\/p>\n

    The Gantt chart that shows the order i n which processes are assigned the CPU is shown below. Since process P<\/em>1 is the first process in the queue, P<\/em>1\u00a0 is assigned the CPU first. P<\/em>1 has a CPU-burst length of 24 ms. P<\/em>1 uses the CPU for 24 ms and then relinquishes the CPU as shown in Figure 7.4.<\/p>\n

    \"\"<\/p>\n

    Fig. 7.4 Process P<\/em>1 using the CPU<\/p>\n

     <\/p>\n

    The next process i n the queue is P<\/em>2. P<\/em>2 is scheduled next. P<\/em>2 has a CPU-burst time of 3 ms and uses the CPU till 27 ms as shown in Figure 7.5.<\/p>\n<\/div>\n

    \n

    \"\"<\/p>\n

    Fig. 7.5 Process P<\/em>2 using the CPU<\/p>\n

     <\/p>\n

    After P<\/em>2, P<\/em>3 is the only process in the queue and it is assigned the CPU. P<\/em>3 uses the CPU for a time duration of 3 ms and then relinquishes the CPU as shown i n Figure 7.6.<\/p>\n

    \"\"<\/p>\n

    Fig. 7.4 Process P<\/em>3 using the CPU<\/p>\n

     <\/p>\n

    The waiting time for each process and hence the average waiting time can be calculated. Since all the three processes arrive at the same time, the arrival time of the processes is taken as 0. Process P<\/em>1 arrived at time 0 and was assigned the CPU immediately. Hence, the waiting time for P<\/em>1 = 0. Process P<\/em>2 arrived at time 0 and was assigned the CPU at time 24. Hence, the waiting time for P<\/em>2 = 24. Process P3 arrived at time 0 and was assigned the CPU at time 27. Hence, the waiting time for P<\/em>3 = 27. Hence, the average waiting time is (0 + 24 + 27) \/ 3 = 17.<\/p>\n

     <\/p>\n

    Similarly, the turnaround time for each process and hence the average turnaround time can be calculated. Process P<\/em>1 arrived at time 0 and completed its CPU burst at time 24. Hence, the turnaround time for P<\/em>1 = 24. Process P<\/em>2 arrived at time 0 and completed its CPU burst at time 27. Hence, the turnaround time for P<\/em>2 = 27. Process P<\/em>3 arrived at time 0 and completed its CPU burst at time 30. Hence, the turnaround time for P<\/em>3 = 30.The average turnaround time is (24 + 27 + 30) \/ 3 = 27.<\/p>\n

     <\/p>\n

    Suppose if the three processes arrive in the order P<\/em>2, P<\/em>3, P<\/em>1. The Gantt chart for the schedule is as shown in Figure 7.5.<\/p>\n

    \"\"<\/p>\n

    Fig. 7.5 Gantt chart with the order of the processes changed<\/p>\n

     <\/p>\n

    The waiting time of the processes can be calculated as follows: The arrival time for all the processes is the same and is taken as 0. Therefore, the waiting time for P<\/em>1 = <\/em>6, P<\/em>2 = 0 and P<\/em>3 = <\/em>3. The average waiting time is (6 + 0 + 3)\/3 = 3. The turnaround time for P<\/em>1 = <\/em>30, P<\/em>2 = 3 and P<\/em>3 = <\/em>6. Therefore, the average turnaround time is (3 + 6 + 30)\/3 = 13. It is seen that the average waiting time and the average turnaround time have improved when the order of the processes is changed. In the earlier case, process P<\/em>1 had a long\u00a0CPU burst and the other processes had to wait for <\/span>P<\/em>1 to complete its CPU burst. This increased the average waiting time and the average turnaround time.<\/span><\/p>\n<\/div>\n

    \n

     <\/p>\n

    7.6.2\u00a0 Shortest-Job-First (SJF) Scheduling\u00a0<\/strong><\/p>\n

     <\/p>\n

    The SJF CPU scheduling algorithm associates with each process the length of its next CPU burst. These lengths are used to schedule the process with the shortest time. When the CPU becomes available, the process with the shortest next CPU burst is assigned the CPU. There are two schemes i n SJF. One is non-preemptive in which once CPU is assigned to a process, it cannot be preempted until it completes its CPU burst. The other is preemptive in which if a new process arrives with CPU burst length less than the remaining time of the currently executing process, the currently executing process is preempted. This scheme is known as the Shortest-Remaining-Time-First (SRTF). In this module, we will learn how scheduling is done i n non-preemptive SJF.<\/p>\n

     <\/p>\n

    Consider four processes P<\/em>1, P<\/em>2, P<\/em>3\u00a0 and P<\/em>4. <\/em>The arri val times and the CPU-burst times of the four processes are gi ven below:<\/p>\n\n\n\n\n\n\n\n
    Process<\/strong><\/td>\nArriva l Time<\/strong><\/td>\nBurst Time<\/strong><\/td>\n<\/tr>\n
    P<\/em>1<\/td>\n0.0<\/td>\n7<\/td>\n<\/tr>\n
    P<\/em>2<\/td>\n2.0<\/td>\n4<\/td>\n<\/tr>\n
    P<\/em>3<\/td>\n4.0<\/td>\n1<\/td>\n<\/tr>\n
    P<\/em>4<\/td>\n5.0<\/td>\n4<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

     <\/p>\n

    At time 0.0, P<\/em>1 is the only process that has arrived. Hence , P<\/em>1 is assigned the CPU first. Since it is non-preemptive SJF scheduling, P<\/em>1 continues to use the CPU till its CPU-burst gets over as shown in Figure 7.6<\/p>\n

    \"\"<\/p>\n

    Fig. 7.6 Process P<\/em>1 using the CPU<\/p>\n

     <\/p>\n

    After P<\/em>1 finishes its CPU-burst, the processes remaining i n the ready queue are P<\/em>2, P<\/em>3 and P<\/em>4. The processes P<\/em>2, P<\/em>3\u00a0 and P<\/em>4 have now arrived. Of these three processes, P<\/em>3 has the shortest CPU burst. Hence, P<\/em>3 is assigned the CPU. P<\/em>3 makes use of the CPU for a time duration that is equal to its CPU burst (1 ms) and then relinquishes the CPU as in Figure 7.7.<\/p>\n

    \"\"<\/p>\n

    Fig. 7.7 Process P<\/em>3usingtheCPU<\/p>\n<\/div>\n

     <\/p>\n

    P<\/em>2 and <\/span>P<\/em>4 are the remaining processes. Both the processes have the same CPU burst time. Any one of these can be assigned the CPU. So, the tie is now broken using FCFS. Of the two processes, <\/span>P<\/em>2 arrived earlier. Hence, <\/span>P<\/em>2 is assigned the CPU and <\/span>P<\/em>2 executes till its CPU burst is completed as i n Figure 7.8.<\/span><\/p>\n

    \n

    \"\"<\/p>\n

    Fig. 7.8 P<\/em>2 using the CPU<\/p>\n

     <\/p>\n

    After P<\/em>2 finishes execution, the only process waiting is P<\/em>4. P<\/em>4 is now assigned the CPU. After P<\/em>4 runs for its CPU-burst time, it relinquishes the CPU as shown i n Figure 7.9.<\/p>\n

    \"\"<\/p>\n

    Fig. 7.9 P<\/em>4 using the CPU<\/p>\n

     <\/p>\n

    The average waiting time and the average turnaround time can be calculated as follows. The waiting time for process P<\/em>1 is 0. P<\/em>1 arrived at time 0 and was assigned the CPU immediately. P<\/em>1 did not wait. P<\/em>2 arrived at time 2.0 and was assigned the CPU at time 8.0. Hence, the waiting time for process P<\/em>2 is 8 – 2 = 6. P<\/em>3 arrived at time 4.0 and was assigned the CPU at time 7.0. Hence, the waiting time for process P<\/em>2 is 7 – 4 = 3. Process P<\/em>4 arrived at time 5.0 and was assigned the CPU at time 12.0. Hence the waiting time of process P<\/em>2 is 12 – 5 = 7. Hence, the average waiting time = (0 + (8 – 2) + (7 – 4) + (12 – 5)) \/ 4 = 4.<\/p>\n

     <\/p>\n

    P<\/em>1 arrived at time 0 and completed execution at 7. The turnaround time of process P<\/em>1 is 7. P<\/em>2 arrived at time 2.0 and completed execution at time 12.0. Hence, the turnaround time for process P<\/em>2 is 12 – 2 = 10. P<\/em>3 arrived at time 4.0 and completed execution at time 8.0. Hence , the waiting time for process P<\/em>2 is 8 – 4 = 4. Process P<\/em>4 arrived at time 5.0 and completed execution at time 16.0. Hence , the turnaround time of process P<\/em>2 is 16 – 5 = 11. Hence the a verage waiting time = (0 + (8 – 2) + (7 – 4) + (12 – 5)) \/ 4 = 4. Hence, the average turnaround time = ((7 – 0) + (12 – 2) + (8 – 4) + (16 – 5)) \/\u00a0 4 = 32 \/ 4 =8.<\/p>\n

     <\/p>\n

    7.7\u00a0 Summary\u00a0<\/strong><\/p>\n

     <\/p>\n

    In this module, we learnt what CPU scheduling is. Multiprogramming maximizes CPU utilization. The CPU scheduler selects the next process that should be assigned the \u00a0CPU. \u00a0Many CPU scheduling algorithms \u00a0have \u00a0been proposed. CPU scheduling\u00a0algorithms can be preemptive or non-preemptive. In this module, we learnt how First Come First Served (FCFS) and non-preemptive Shortest Job First (SJF) CPU scheduling algorithms work. We saw that SJF has less waiting time and less turnaround time when compared to FCFS.<\/span><\/p>\n<\/div>\n

     <\/p>\n

    References<\/strong><\/p>\n

      \n
    1. Abraham Silberschatz, \u00a0Peter \u00a0B. \u00a0Galvin, \u00a0Greg \u00a0Gagne, \u00a0\u201cOperating \u00a0System Concepts\u201d, Sixth Edition, John Wiley & Sons Inc., 2003.<\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":4,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-mary-anitha-rajam"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-54","chapter","type-chapter","status-publish","hentry","contributor-dr-mary-anitha-rajam"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/54","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":5,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/54\/revisions"}],"predecessor-version":[{"id":407,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/54\/revisions\/407"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/54\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/media?parent=54"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapter-type?post=54"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/contributor?post=54"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/license?post=54"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}