Scheduling: Operating System Class Notes

Updated: Aug 18

Mobiprep has created last-minute notes for all topics of operating system to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Operating System (OS).

  1. Introduction of Operating System

  2. Process

  3. Scheduling

  4. Threads

  5. Memory Management

  6. File Management

  7. Synchronization

  8. Disk Management

  9. IO Management

  10. Protection And Security

Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.

  1. Mention criteria for optimal CPU scheduling.

  2. What do you understand by preemptive and non-preemptive scheduling.

  3. Define i)CPU Utilization ii)Throughput iii)Turnaround time iv)Waiting time v)Response Time

  4. What do you mean by CPU-burst and I/O burst?

  5. What is multilevel queue?

  6. How scheduling is different from context switching?

  7. What are different scheduling algorithms?

  8. Explain the mechanism of First come first serve by the help of an example?

  9. Explain the mechanism of shortest remaining time first by the help of an example?

  10. Explain the mechanism of Round robin scheduling by the help of an example?

  11. Briefly discuss “SJF is optimal”.

  12. Differentiate between long term, short term, and medium term process scheduling.

  13. Explain why FCFS is called a non-preemptive scheduler with an example.

  14. What is rescheduled latency?

  15. What is a multilevel queue scheduler?

  16. What is a multilevel feedback queue scheduler?

  17. What do you understand by multiple processor scheduling?

  18. How CPU performance is measured.


Scheduling


Question- 1) Mention criteria for optimal CPU scheduling.

Answer: CPU scheduling is a process that allows one process to use the CPU while the execution of another process is on hold(in waiting state) due to unavailability of any resource like I/O etc., thereby making full use of CPU. The aim of CPU scheduling is to make the system efficient, fast, and fair.


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 from among the processes in memory that are ready to execute and allocates the CPU to one of them.


Scheduling of processes/work is done to finish the work on time.


Below are different time with respect to a process.


Arrival Time: Time at which the process arrives in the ready queue.

Completion Time: Time at which process completes its execution.

Burst Time: Time required by a process for CPU execution.

Turn Around Time: Time Difference between completion time and arrival time.


Turn Around Time = Completion Time – Arrival Time


Waiting Time(W.T): Time Difference between turn around time and burst time.

Waiting Time = Turn Around Time – Burst Time


 

Question- 2) What do you understand by preemptive and non-preemptive scheduling.

Answer: Preemptive Scheduling is a CPU scheduling technique that works by dividing time slots of CPU to a given process. The time slot given might be able to complete the whole process or might not be able to it. When the burst time of the process is greater than CPU cycle, it is placed back into the ready queue and will execute in the next chance. This scheduling is used when the process switch to ready state.


Algorithms that are backed by preemptive Scheduling are round-robin (RR), priority, SRTF (shortest remaining time first).


Non-preemptive Scheduling is a CPU scheduling technique the process takes the resource (CPU time) and holds it till the process gets terminated or is pushed to the waiting state. No process is interrupted until it is completed, and after that processor switches to another process.


Algorithms that are based on non-preemptive Scheduling are non-preemptive priority, and shortest Job first.


 

Question- 3) Define

i) CPU Utilization

ii) Throughput

iii) Turnaround time

iv) Waiting time

v) Response Time.

Answer:

  1. Throughput: – number of processes that complete their execution per time unit

  2. Turnaround time: – amount of time to execute a particular process

  3. Waiting time: – amount of time a process has been waiting in the ready queue

  4. Response time:– amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)


 

Question- 4) What do you mean by CPU-burst and I/O burst?

Answer: CPU Burst :- "The amount of time the process uses the processor before it is no longer ready".

Types Of CPU burst :-

  1. Long burst : ("Process is CPU bound")

  2. Short burst : ("Process I/O bound")

I/O Burst :- "Input/Output burst is that after completion the input burst CPU do process on that job".


Explanation :- CPU burst is like a car and input Input burst is like a pedestrian , because CPU speed is much faster than Input Output burst , we can not reduce the speed of CPU burst but we can increase the Input Output speed.


 

Question- 5) What is multilevel queue?

Answer: A multi-level queue scheduling algorithm partitions the ready queue into several separate queues. The processes are permanently assigned to one queue, generally based on some property of process, such as memory size, process priority, or process type. Each queue has it own scheduling algorithm.


 

Question- 6) How scheduling is different from context switching?

Answer: Context switching is stopping one process and starting a new process, whereas scheduling is choosing a process among many processes which is eligible and efficient for execution.

 

Question- 7) What are different scheduling algorithms?

Answer: Different scheduling algorithms are -:

  • FCFS

  • Shortest Job First(Preemptive and non Preemptive)

  • Shortest Remaining Time First

  • Longest Job First

  • Longest Remaining Time First

  • Round Robin

  • Priority (Preemptive and Non Preemptive)

  • Highest Response Ratio next

  • Multilevel queue

  • Multilevel Feedback queue


 

Question- 8) Explain the mechanism of First come first serve by the help of an example?

Answer:

  • First come first serve is a non-preemptive scheduling algorithm and it works like the data structure queue.

  • The name itself states which process will request the CPU first that will be served first.

  • Example: Let us consider set of processes and its burst time (the time required to complete the execution) as follows:

Process

Burst Time

P1

30

P2

12

P3

6

P4

7

P5

8


  • Assume, all the processes arrive at 0ms (milliseconds).

  • The order in which they arrived are P1, P2, P3, P4, P5.

  • So, the execution is also done in the same order in which they arrived.

  • The numbers mentioned below is the time that process has been executed in ms.

P1

P2

P3

P4

P5

0 30 42 48 55 63



 

Question- 9) Explain the mechanism of shortest remaining time first by the help of an example?

Answer:

  • Shortest Remaining Time First is preemptive algorithm, when a new process enters into the ready queue, short-term scheduler will compare the remaining time of executing process and the burst time of the new process.

  • If the new process has the least CPU burst time, the CPU will move the currently executing process to the ready queue and then executes the new process.

  • Example: Let us consider set of processes, its burst time and arrival time as follows:

Process

Burst Time

​Arrival Time

P1

3

0

P2

4

2

P3

5

4

P4

6

6

P5

2

8

At time 0ms only P1 has arrived, so we start executing the P1 process.

After the 2ms P2 process has arrived, the scheduler compares burst times of P1 and P2, P1 has 1ms and P2 has 4ms, so it executes P1 and then P2.

At 4th millisecond P3 enters but P2 has less burst time, so P2 is executed.

At 6th millisecond P4 enters and at 8th millisecond P5 enters.

P1, P2 have finished their execution till then and P3 is under execution.

When P5 arrives, it has less burst time so P3 is sent into the ready queue and P5 is executed first.

And the P3 and P4 are executed.

P1

P2

P3

P5

P3

P4

0 3 7 8 10 14 20


 

Question- 10) Explain the mechanism of Round robin scheduling by the help of an example?

Answer:

  • Round Robin Scheduling is a preemptive scheduling algorithm and it is especially designed for time sharing systems.

  • CPU switches among the processes when the time quantum is expired.

  • Time quantum is nothing but a small unit of time, also called time slice which varies from 10ms to 100ms).

  • If the process may have a CPU burst time of less than one-time quantum then the process releases the CPU voluntarily then the scheduler will proceed to the next process in the ready queue.

  • If the process requires more than one quantum it will be moved to the tail of the ready queue only when the time quantum is expired.

  • Example: Let us consider set of processes and its burst time (the time required to complete the execution) as follows, and time quantum to be 5ms:

Process

Burst Time

P1

20

P2

2

P3

13

P4

5

  • Here, the time quantum given is 5ms, first P1 process is executed for one-time quantum i.e., 5ms.

  • Still 15ms burst time is left for P1, it is pushed back into the ready queue, and P2 is being executed now.

  • P2 has a 2ms burst tie so it is finished and then P3 gets started with execution.

  • After 5ms P3 is pushed back into the ready queue and P4 is executed completely as it has 5ms as burst time.

  • Again, P1 starts executing after 5ms again it is pushed back into the ready queue and P3 starts executing. This will happen until all processes finish their execution.

P1

P2

P3

P4

P1

​P3

P1

P3

P1

0 5 7 12 17 22 27 32 35 40

 

Question- 11) Briefly discuss “SJF is optimal”.

Answer: SJF is called the Shortest Job First Scheduling Algorithm. It is a non preemptive scheduling algorithm. The process with least burst time is executed first. If two processes have the same burst time then it follows the FCFS algorithm.

SJF is an optimal algorithm because it decreases the wait times for short processes much more than it increases the wait times for long processes. It gave us the least average waiting time for each process. It also avoids multiple encounters on a single process.


 

Question- 12) Differentiate between long term, short term, and medium term process scheduling

Answer:

Long term scheduler

Short term scheduler

Medium term scheduler

  • Job scheduler.

  • CPU scheduler.

  • Process swapping scheduler.

  • Speed is lesser than a short-term scheduler.

  • ​Faster than other schedulers.

  • Its speed is in between long and short-term schedulers.

  • It takes processes from the job pool and loads these processes to main memory.

  • It takes process from the ready queue and give the control of the CPU to the process with the help of a dispatcher.

  • It takes process from running or wait/dead state once the I/O request is updated.

  • ​Also called as process scheduler.

  • ​Also called as processor scheduler.

  • ​Also called a process swapping scheduler.


 

Question- 13) Explain why FCFS is called a non-preemptive scheduler with an example.

Answer: First Come First Serve is a non-preemptive scheduling. The name itself states which process will request the CPU first that will be served first.

It doesn’t depend on the burst time or the arrival time of a process.

It is not controlled by any of the parameters.

Once it starts the execution it will be there until it is finished, so FCFS is a non-preemptive scheduler.

Example: If we have three processes P1, P2, P3 arrived in order P1, P3, P2 then the execution also happens in the order of arrival i.e., P1, P3, P2.


 

Question- 14) What is rescheduled latency?

Answer: Reschedule latency is nothing but the time that the system is not productive because of scheduling tasks. It is a system latency incurred because it has to spend time scheduling. It consists of the delay between a task waking up and actually running and also time spent making scheduler decisions.


 

Question- 15) What is a multilevel queue scheduler?

Answer: The multilevel queue scheduler is allowed for multiple active threads at each priority level, limited only by system resources. It is the data structure used to represent the number of ready threads at each priority level.

Ready queue is divided into different queues. Each queue has different priority, upper being at highest. Each queue has its own scheduling algorithm. Each queue performs a particular task.

For example:


multilevel queue scheduler in operating system


 

Question- 16) What is a multilevel feedback queue scheduler?

Answer: In this scheduling, a process is allowed to move between different queues, having different CPU burst time. Priority of the upper queue is higher than lower. If a process waits too long, its priority is changed and so the queue. Thus, it prevents starvation.


multilevel feedback queue scheduler in operating system

 

Question- 17) What do you understand by multiple processor scheduling?

Answer: Multi processor scheduling is an NP-hard optimization problem. In this scheduling we have multiple CPUs available. As there are many CPUs, load sharing is possible. It is the ability of processing more than one process at a time. It is more complex than single process scheduling. It is of two types: Symmetric and Asymmetric.


 

Question- 18) How CPU performance is measured.

Answer: The common measure of CPU speed is clock speed, which is measured in MHz (Mega Hertz) or GHz (Gigahertz). One of the standard units of CPU performance is throughput, i.e., the number of processes executed in a unit of time.


 






4 views0 comments