1 of 27

Lectures On:

Process/CPU Scheduling Algorithms in Operating Systems

​

��Department of �Computer Science and Engineering�www.cse.ugv.edu.bd, 874/322, C&B Road, Barisal, Bangladesh.� 

University of Global Village (UGV)

Barishal, Bangladesh

​

Lectures By��Md. Tariqul Islam�Lecturer & Coordinator

�Mobile: +880-1842733104 �Email: tariq.ugv@gmail.com�Web: www.tariqul.ugv.edu.bd

2 of 27

3 of 27

CPU Scheduling in Operating Systems

  • CPU scheduling is a process used by the operating system to decide which task or process gets to use the CPU at a particular time.
  • This is important because a CPU can only handle one task at a time, but there are usually many tasks that need to be processed.
  • The following are different purposes of a CPU scheduling time.
        • Maximize the CPU utilization
        • Minimize the response and waiting time of the process.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

4 of 27

What is the Need for a CPU Scheduling Algorithm?

  • CPU scheduling is the process of deciding which process will own the CPU to use while another process is suspended.
  • The main function of CPU scheduling is to ensure that whenever the CPU remains idle
  • The OS has at least selected one of the processes available in the ready-to-use line.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

5 of 27

Terminologies Used in CPU Scheduling

  • Arrival Time (AT): The time at which the process arrives in the ready queue.
  • Completion Time (CT): The time at which the process completes its execution.
  • Burst Time (BT): Time required by a process for CPU execution.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

6 of 27

Terminologies Used in CPU Scheduling

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

Turn Around Time (TAT) = Completion Time – Arrival Time

​

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

7 of 27

Terminologies Used in CPU Scheduling

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

Waiting Time = Turn Around Time – Burst Time

​

​

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

8 of 27

Things to Take Care While Designing a CPU Scheduling Algorithm

Different CPU Scheduling algorithms have different structures and the choice of a particular algorithm depends on a variety of factors.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

9 of 27

Things to Take Care While Designing a CPU Scheduling Algorithm

CPU Utilization:

  • The main purpose of any CPU algorithm is to keep the CPU as busy as possible.
  • Theoretically, CPU usage can range from 0 to 100 but in a real-time system, it varies from 40 to 90 percent depending on the system load.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

10 of 27

Things to Take Care While Designing a CPU Scheduling Algorithm

Throughput:

  • The average CPU performance is the number of processes performed and completed during each unit. This is called throughput.
  • The output may vary depending on the length or duration of the processes.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

11 of 27

Things to Take Care While Designing a CPU Scheduling Algorithm

Turn Round Time:

  • For a particular process, the important conditions are how long it takes to perform that process.
  • The time elapsed from the time of process delivery to the time of completion is known as the conversion time.
  • Conversion time is the amount of time spent waiting for memory access, waiting in line, using CPU and waiting for I/O.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

12 of 27

Things to Take Care While Designing a CPU Scheduling Algorithm

Waiting Time:

  • The Scheduling algorithm does not affect the time required to complete the process once it has started performing.
  • It only affects the waiting time of the process i.e. the time spent in the waiting process in the ready queue.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

13 of 27

Things to Take Care While Designing a CPU Scheduling Algorithm

Response Time:

  • In a collaborative system, turn around time is not the best option.
  • The process may produce something early and continue to computing the new results while the previous results are released to the user.
  • Therefore another method is the time taken in the submission of the application process until the first response is issued.
  • This measure is called response time.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

14 of 27

Different Types of CPU Scheduling Algorithms

There are mainly two types of scheduling methods:

  1. Preemptive Scheduling
  2. Non-Preemptive Scheduling

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

15 of 27

16 of 27

Different Types of CPU Scheduling Algorithms

  • Preemptive Scheduling: Preemptive scheduling is used when a process switches from running state to ready state or from the waiting state to the ready state.
  • Preemptive Scheduling Example:
  • A user is playing music, but when a video call comes in, the CPU pauses the music and starts handling the video call first.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

17 of 27

Examples of Preemptive Scheduling Algorithms

​

​

  • Round Robin
  • Shortest Remaining Time First (SRTF)
  • Priority Scheduling (preemptive version)

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

18 of 27

Advantages of Preemptive Scheduling

  • Prevents one process from monopolizing CPU
  • Better average response time in multi-user systems
  • Widely used in modern OS (Windows, Linux, macOS)

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

19 of 27

Disadvantages of Preemptive Scheduling

  • More complex to implement
  • Higher overhead from context switching
  • Can cause starvation of low-priority processes
  • Risk of concurrency issues if preempted during shared resource access

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

20 of 27

Different Types of CPU Scheduling Algorithms

  • Non-Preemptive Scheduling: Non-Preemptive scheduling is used when a process terminates , or when a process switches from running state to waiting state.
  • Non-Preemptive Scheduling Example:
  • A document is printing. Even if another task arrives, the CPU waits until printing is finished before starting the next task.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

21 of 27

Examples Non-Preemptive Scheduling Algorithms

  • First Come First Serve (FCFS)
  • Shortest Job First (SJF)
  • Priority Scheduling (non-preemptive version)

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

22 of 27

Advantages of Non-Preemptive Scheduling

  • It is easy to implement in an operating system. It was used in Windows 3.11 and early macOS.
  • It has a minimal scheduling burden.
  • Less computational resources are used.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

23 of 27

Disadvantages of Non-Preemptive Scheduling

  • It is open to denial of service attack. A malicious process can take CPU forever.
  • Since we cannot implement round robin, the average response time becomes less.

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

24 of 27

Differences Between Preemptive and Non-Preemptive Scheduling

Parameter

Preemptive Scheduling

Non-Preemptive Scheduling

Basic

In this resources(CPU Cycle) are allocated to a process for a limited time.

Once resources(CPU Cycle) are allocated to a process, the process holds it till it completes its burst time or switches to waiting state

Interrupt

Process can be interrupted in between.

Process can not be interrupted until it terminates itself or its time is up

Starvation

If a process having high priority frequently arrives in the ready queue, a low priority process may starve

If a process with a long burst time is running CPU, then later coming process with less CPU burst time may starve

Overhead

It has overheads of scheduling the processes

It does not have overheads

Response Time

Average process response time is less

Average process response time is high

Decision making

Decisions are made by the scheduler and are based on priority and time slice allocation

Decisions are made by the process itself and the OS just follows the process's instructions

Concurrency Overhead

More as a process might be preempted when it was accessing a shared resource.

Less as a process is never preempted.

Examples

Examples of preemptive scheduling are Round Robin and Shortest Remaining Time First

Examples of non-preemptive scheduling are First Come First Serve and Shortest Job First

​

​

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

25 of 27

CPU Scheduling Algorithms

  • FCFS - First Come, First Serve
  • SJF - Shortest Job First
  • SRTF - Shortest Remaining Time First
  • Round Robin
  • Priority Scheduling
  • HRRN - Highest Response Ratio Next
  • Multiple Queue Scheduling
  • Multilevel Feedback Queue Scheduling

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd

26 of 27

CPU Scheduling Algorithms

27 of 27

“Thank You”

Lectures By Md. Tariqul Islam, Lecturer & Coordinator, Dept. of CSE, UGV, Email: tariq.ugv@gmail.com, Web: www.tariqul.ugv.edu.bd