How MLFQ Approximates Shortest Job First (SJF)

 

How MLFQ Approximates Shortest Job First (SJF)

Let us now examine a more realistic and slightly more complex scenario to understand how the Multi-Level Feedback Queue (MLFQ) scheduler attempts to approximate Shortest Job First (SJF) without knowing job lengths in advance.

Scenario Description

We consider two jobs:

  • Job A

    • Long-running

    • CPU-intensive

    • Has already been running for some time

    • Currently resides in the lowest-priority queue

  • Job B

    • Short-running

    • Interactive

    • Requires only 20 ms of CPU time

    • Arrives later, at time T = 100

What Happens When Job B Arrives?

Step-by-Step Execution

  1. Before T = 100

    • Job A is running continuously

    • Because it has consumed significant CPU time, it has been demoted to the lowest-priority queue

  2. At T = 100

    • Job B arrives

    • According to MLFQ rules, new jobs are placed in the highest-priority queue

  3. After T = 100

    • Job B immediately preempts Job A

    • Job B runs in the highest-priority queue

    • Job B completes execution in two time slices (20 ms total)

  4. After Job B Completes

    • Job A resumes execution

    • Job A continues running at low priority

Conceptual Timeline 

  • Black region → Job A (long-running, CPU-bound)

  • Gray region → Job B (short, interactive)

Job B finishes quickly without ever being pushed to lower-priority queues.

Why This Approximates SJF

MLFQ does not know job lengths ahead of time. Instead, it follows this strategy:

  • Assume every new job is short

  • Give it high priority

  • Observe its CPU usage:

    • If it finishes quickly → it was short

    • If it keeps using the CPU → gradually demote it

In This Example:

  • Job B truly is short

  • It finishes before being demoted

  • Job A, being long-running, stays at low priority

Thus, Job B effectively behaves as if it were scheduled by SJF.

Key Insight

MLFQ approximates SJF by learning from execution behavior rather than relying on prior knowledge.

Comments

Post a Comment

Popular posts from this blog

Operating Systems OS PCCST403 Semester 4 BTech KTU CS 2024 Scheme

 About Me Scheme and Syllabus Module-1 Introduction to OS - 3 important pieces- virtualization, concurrency, persistence Operating System Services Operating System and Kernel Linux Versus Classic Unix Kernels Difference between Linux and Unix Kernels Process and Process Creation- overview Process States in Operating System Data Structures in Operating Systems Key Aspects of a Program and Process in an Operating System-Summary Sharing the Processor Among Processes System Boot Sequence Threads and Concurrency Case Study: Linux Kernel Process management Case Study: Linux Implementation of Threads CPU Scheduling Multi-level feedback Queue ( MLFQ) Scheduler How MLFQ Approximates Shortest Job First (SJF) I/O in MLFQ Problems With the Basic MLFQ Scheduler Solving the Issues with MLFQ Scheduler Case Study: Linux Completely Fair Scheduler (CFS)
Read more

Introduction to Operating System -Virtualization, Concurrency, and Persistence

  How Operating Systems Really Work: Virtualization, Concurrency, and Persistence Have you ever wondered how your laptop can play music, run a web browser, download files, and open a Word document—all at the same time—without melting down? It might look simple, but beneath the surface, your operating system (OS) is doing incredibly sophisticated work. In this , we’ll break down the three most important ideas that make modern operating systems possible: Virtualization Concurrency Persistence These concepts are the foundation of how computers manage programs(applications), memory, and data.  1. Virtualization: Making One Computer Look Like Many Virtualization is all about creating useful illusions . You might have Spotify playing, Instagram open, and a browser loading—all on one phone. It feels like all apps run simultaneously, but the phone is rapidly switching between them so smoothly you don’t notice. Virtualization = making one CPU appear like many. Ev...
Read more

Operating Systems PCCST403 Scheme and Syllabus

  OPERATING SYSTEMS (Common to  CS/CD/CM/CR/CA/AD/AI/CB/CN/CC/CU/CI/CG)   Course  Code PCCST403 CIE Marks 40 Teaching Hours/Week (L: T:P: R)   3:1:0:0   ESE Marks   60 Credits 4 Exam Hours 2Hrs.30 Min. Pre requisites(if  any) None Course Type Theory Course  Objectives: 1. To introduce the structure of a typical operating system and its core functionalities. 2. To impart to the students, a practical understanding of OS implementation nuances based on the Linux operating system. 1.        SYLLABUS   Module No. Syllabus  Description Contact Hours       1 Introduction to Operating Systems (Book 1 Ch 2 introductory part), Operating System Services (Book 3 Ch...
Read more