Experiment Number: 5

TITLE: CPU Scheduling Algorithms.

Problem Statement:

Simulate any two of the following CPU Scheduling Algorithms (One each from preemptive and
non-preemptive types)
a. FCFS
b. SJF
c. Round Robin
d. Priority
Aim:

1. To study and simulate CPU Scheduling algorithms.

Theory:

CPU scheduling is the task of selecting a waiting process from the ready queue and allocating the CPU to
it. The CPU is allocated to the selected process by the dispatcher (It is the module that gives control of
the CPU to the processes by short-term scheduler).

Scheduling is a fundamental operating system function. In a single processor system, only one process
can run at a time; any other process must wait until the CPU is free and can be rescheduled. The
objective of multiprogramming is to have some process running always, to maximize CPU utilization.

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

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

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

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

4. When a process terminates.

CPU Scheduling algorithms are of two types:

1. NON-PREEMPTIVE

2. PREEMPTIVE

1. NON-PREEMPTIVE: Under this 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.

2. PREEMPTIVE: Under this class of scheduling scheme, the process may be preempted by the scheduler
after allocating the CPU to it, so as to allocate the CPU to another deserving process.
SCHEDULING CRITERIA:

1. CPU utilization: It is the fraction of time for which CPU is busy. It can range from 0-100%.

2. Throughput: Number of processes that are completed per unit time.

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

4. Waiting time: It is the sum of the periods spent waiting in the ready queue.

5. Response time: Time from the submission of a request until the first response is produced. It is
desirable to maximize CPU utilization and Throughput and minimize Turnaround time, waiting time and
Response time.

BASIC CPU SCHEDULING ALGORITHMS:

NON-PREEMPTIVE PREEMPTIVE
FIRST COME FIRST SERVE (FCFS) SHORTES REMAINING TIME NEXT (SRTN)
SHORTEST JOB FIRST (SJF) ROUND ROBIN
Non- PREMPTIVE PRIORITY PREMPTIVE PRIORITY

(Note: Here, write in brief about each of these algorithms in brief)

------------------------------------------------------------------------------------------------------------------------------------------
-

Program1: Non-preemptive Algorithm -

…………………. write your code neatly here…………….

Input (CPU Workload):

………………………

Output:

Gantt Charts

Average waiting time

Average turnaround time

Program2: Preemptive Algorithm -

…………write your code neatly here…………………..

Input (CPU Workload):

…………………………

Output:

Gantt Charts
 Average waiting time

Average turnaround time

Conclusion:

………………………………………………

Sample Viva-Voce Questions

1. What is a Gantt chart?

2. What are the advantages and disadvantages of SJF?
3. What is SRTF (Shortest-Remaining-Time-First) scheduling?
4. Is Round-robin scheduling a preemptive algorithm?
5. What is the time quantum used for?
6. How should the time quantum be related to the context switch time?
8. Define the difference between preemptive and non-preemptive scheduling.
9. What advantage is there in having different time-quantum sizes on different levels of a
multilevel queueing system?
10. Explain the differences in the degree to which the following scheduling algorithms discriminate
in favor of short processes: FCFS, RR, Multilevel feedback queues
11. Differentiate between I/O-bound and CPU-bound program.
12. List performance criteria for selecting a CPU scheduling algorithms.
13. What is the relation between FCFS and Round Robin Algorithm ?
14. Number of process switches are more in preemptive algorithms. Justify.