CPU Scheduling

Multiprogramming:- it is defined as to have some processes at all the times, to maximize the CPU utilization.

Mono- programming:- for a uniprocessor system, there will never be more than one running process. If there are more than one running processes, the rest will have to wait until the CPU is free or rescheduled.

When a process is executes, it must wait until the completion of I/O request. The CPU would then just sit idle.

In multiprogramming, when processes have to wait, the O/S takes the CPU away from the process and gives the CPU to another process.

CPU-I/O burst cycle:

The success of the CPU Scheduling depends on the followings observed properties of processes.

Processes execution consist of

             I.      A cycle of CPU execution

          II.      I/O wait

Processes alternate back and forth between their two states. Processes execution begins with CPU burst that is followed by I/O burst. Which is followed by another CPU and then another I/O  burst.

            The last CPU burst will end with a system request to terminate execution.

Whenever a CPU becomes idle, the O/S must select one of the process from the ready queue to execute. The short-term scheduler carries the selection process.

Note: ready queue is not necessarily a first in first out (FIFO) queue.

As we consider the various scheduling algorithm, a ready queue may be implemented as

             I.      A FIFO queue

          II.      A priority queue

       III.      A tree

       IV.      Simply an unordered linked list

However, all the processes in the ready queue are linked up waiting for a chance to run on the CPU. The records in the ready are generally PCB’s of the processes.

Types of scheduling:

                           CPU scheduling decision may take place under the following circumstances:

1. When a process switches from running state to waiting state.

Eg. I/O request, wait for the termination of one of the child.

2. When a process switches from the running state to the ready state.

Eg. When an interrupt occurs.

3. When a process switches from the waiting state to ready state.

Eg. Completion of I/O request

4. When a process terminates.

Scheduling criteria:

                           Different CPU scheduling algorithms have different properties. Which algorithm to use in a particular situation, we must consider the properties of the various algorithms.

CPU utilization:

We want to keep the CPU as busy as possible. CPU utilization ranges from 0 – 100%.

In a real system, it should be 40 – 90%.

Throughput: the number of processes that are completes per unit time called the throughput.

For long processes:  one process per hours.

For short process: 10 processes per seconds.

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

Turnarround time is the sum of period spent waiting to get.

             I.      Memory

          II.      Waiting in the ready queue

       III.      Executing on the CPU

       IV.      And I/O

Waiting time: waiting time is the sum of period spends waiting in the ready queue.

Response time: a process can produce some outputs and continue computing new results while previous results are output to the user. Another measure is the time from the submission of a request until the first response is produced is called the response time.