Agenda

<aside> 📌 Reminders

• P1 due February 2, 2025 </aside>

👋 Introduction

As we’ve seen before, the OS needs to manage several threads that are each vying for the CPU, its needs some way to manage which thread to run, and for how long a thread should hold the CPU (this is called a time quantum).

<aside> 💡

Time Quantum: The shortest period of time a process is allowed to occupy the CPU

</aside>

• What happens if the time quantum is too short? Too long?

In lecture, you will discuss several ways to measure performance of a scheduling algorithm, one thing to note is that any decent scheduling algorithm must prevent thread starvation.

<aside> 💡

Starvation: The phenomenon in which a thread/process is prevented from ever running due to the scheduler’s choices

</aside>

Below is a summary of common scheduling algorithms along with their strengths and weaknesses. We discuss the notable algorithms in more detail in the next sections.

• First-Come, First-Served (FCFS)
  • Description: Jobs are executed in the order they arrive.
  • 😃 Simple and easy to implement.
  • 😔 Poor performance with long jobs (can lead to the “convoy effect”).
• Shortest Job First (SJF)
  • Description: Executes the job with the shortest burst time first.
  • 😃 Minimizes average waiting time.
  • 😔 Requires knowledge of job length; prone to starvation for longer tasks.
• Round Robin (RR)
  • Description: Run threads in circular order for a fixed time quantum.
  • 😃 Fair and responsive for time-sharing systems.
  • 😔 High context-switch overhead if time quantum is too small.
• Priority Scheduling
  • Description: Processes are executed based on priority levels.
  • 😃 Flexible, supports task prioritization.
  • 😔 Can lead to starvation for low-priority tasks (unless explicitly prevented).
• Shortest Remaining Time First (SRTF)
  • Description: Preemptive version of SJF; executes process with the shortest remaining CPU time.
  • 😃 Minimizes average waiting time.
  • 😔 Requires precise CPU time information which is usually impossible to obtain.
• Multilevel Feedback Queue (MLFQ)
  • More below…

🥇🥈🥉 Priority Scheduling

Not all threads are created equal, some have far more important goals to accomplish than others (you wouldn’t want a thread updating your clock to be prioritized over one handling your lane assist in your car’s software). For this reason, threads are usually associated with a priority (see struct thread) and, as the name suggests, higher priority threads are given priority to run.

• This has two obvious issues. What are they?

The multi-level feedback queue resolves both of these issues.

pintOS Considerations

You will implement priority scheduling in P1. There are three main requirements for this section: