Operating System Scheduling Concepts

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

How are priorities assigned in Earliest Deadline First Scheduling?

The later the deadline, the higher the priority

Priorities are assigned randomly

All deadlines have equal priority regardless of timing

The earlier the deadline, the higher the priority (correct)

What does Proportional Share Scheduling ensure for applications?

Applications receive processor time based on a total share allocation (correct)

Every application gets an equal number of shares regardless of needs

Applications are assigned shares based on priority alone

Each application receives all available processor time

Which scheduling class in POSIX Real-Time Scheduling uses a First-Come, First-Served strategy?

SCHED_FIFO (correct)

SCHED_RR

SCHED_MLFQ

SCHED_EDF

In Proportional Share Scheduling, if an application receives N shares, what is true about the relationship between N and T?

N is less than T Signup and view all the answers

Which of the following correctly describes the principle of Rate Monotonic Scheduling?

Higher frequencies of tasks are assigned higher priorities Signup and view all the answers

What happens to a process after its time quantum has elapsed?

It is preempted and added to the end of the ready queue. Signup and view all the answers

What is the maximum amount of time a process may wait in the ready queue?

(n-1)q time units Signup and view all the answers

How does the time quantum (q) affect the scheduling algorithm used in a multilevel queue?

It decides the type of scheduling algorithm for each queue. Signup and view all the answers

What is a recommended time quantum range for optimal performance?

10ms to 100ms Signup and view all the answers

What generally happens when the time quantum is too small compared to context switch time?

It results in high overhead. Signup and view all the answers

Which scheduling algorithm is typically used for the foreground queue in a multilevel queue system?

Round Robin (RR) Signup and view all the answers

What impact does a larger time quantum have on process scheduling?

It leads to a FIFO scheduling approach. Signup and view all the answers

In Round Robin scheduling, what fraction of the CPU time does each process ideally get?

1/n of the CPU time Signup and view all the answers

What is a nonpreemptive scheduling method?

First-Come, First-Served (FCFS) Signup and view all the answers

What does dispatch latency refer to in operating systems?

Time taken for the dispatcher to stop one process and start another Signup and view all the answers

Which of the following is NOT a scheduling criterion?

Energy consumption Signup and view all the answers

What is the effect called when a short process waits behind a long process in FCFS scheduling?

Convoy effect Signup and view all the answers

Which scheduling algorithm is known to provide the minimum average waiting time?

Shortest-Job-First (SJF) Signup and view all the answers

In the example of SJF scheduling provided, what was the average waiting time for four processes?

7 Signup and view all the answers

What is a common method to estimate the next CPU burst time for a process?

Using exponential averaging of previous CPU bursts Signup and view all the answers

How is the average waiting time calculated in an FCFS scheduling scenario?

By adding the waiting times of all processes and dividing by the number of processes Signup and view all the answers

What challenge does the Shortest-Job-First (SJF) scheduling algorithm face?

Determining the length of the next CPU burst accurately Signup and view all the answers

Which factor is NOT typically considered in CPU scheduling?

User satisfaction scores Signup and view all the answers

Which of the following is a goal of CPU scheduling?

Minimize turnaround time Signup and view all the answers

What does a dispatcher module do?

Transfers control of the CPU to a process selected by the short-term scheduler Signup and view all the answers

What happens in preemptive scheduling?

A currently running process can be interrupted and moved back to the ready queue Signup and view all the answers

What does a lower nice value signify in a scheduling system?

Higher task priority Signup and view all the answers

In CFS scheduling, what is used to determine the next task to run?

Task with the lowest virtual run time Signup and view all the answers

In a real-time scheduling system, what is true about task priorities?

Real-time tasks have static priorities Signup and view all the answers

What happens when a thread's quantum expires in Windows scheduling?

Thread's priority is lowered but not below the base Signup and view all the answers

How many priority levels does Windows use for threads?

32 levels Signup and view all the answers

In Solaris, which scheduling class is the default?

Time sharing (TS) Signup and view all the answers

What is unique about the REALTIME_PRIORITY_CLASS in Windows?

It is the only fixed priority class Signup and view all the answers

What boosts a thread's priority in Windows if a wait occurs?

3x priority boost for foreground window Signup and view all the answers

What kind of threading management feature was added in Windows 7?

User-mode scheduling (UMS) Signup and view all the answers

What is a key characteristic of the CFS scheduler in a Linux environment?

It maintains a virtual run time for each task Signup and view all the answers

Which scheduling class in Solaris is intended for allocation based on resource fairness?

Fair Share (FSS) Signup and view all the answers

In the context of Windows scheduling, how does a dispatcher function?

It manages thread time-slices Signup and view all the answers

What is utilized in CFS to represent the time a task has run compared to others?

vruntime Signup and view all the answers

What happens to the thread with the highest priority in Solaris scheduling?

It runs until blocked or preempted Signup and view all the answers

What is the primary purpose of the multilevel feedback queue scheduling?

To prevent starvation by allowing process movement between queues Signup and view all the answers

What is the main distinguishing feature of kernel-level threads compared to user-level threads?

Kernel-level threads are managed directly by the operating system. Signup and view all the answers

How does aging function in a multilevel feedback queue scheduling system?

It promotes processes that consume high CPU time to higher priority queues. Signup and view all the answers

What type of scheduling is used by Queue Q0 in the multilevel feedback queue example?

Round Robin (RR) with a time quantum of 8 milliseconds Signup and view all the answers

What condition leads to a job being moved from Queue Q1 to Queue Q2 in the multilevel feedback queue example?

When the job exceeds 16 milliseconds and does not complete Signup and view all the answers

In Pthread scheduling, what does the PTHREAD_SCOPE_SYSTEM option do?

It enables system-contention scope scheduling. Signup and view all the answers

What is a characteristic of symmetric multiprocessing (SMP)?

Each processor self-schedules from a common ready queue. Signup and view all the answers

How does push migration in load balancing operate?

Tasks are pushed from overloaded CPUs to underloaded CPUs. Signup and view all the answers

What defines a hard real-time system in CPU scheduling?

Tasks must be serviced by their assigned deadlines. Signup and view all the answers

In what scenario do multicore processors operate efficiently?

When they can run multiple threads across cores simultaneously. Signup and view all the answers

What effect does the Round Robin (RR) time quantum have on scheduling performance?

Longer time quantum often leads to increased context switch time. Signup and view all the answers

What challenge does the scheduler face in systems employing many-to-many threading models?

Scheduling decisions can lead to fragmentation of CPU resources. Signup and view all the answers

What is meant by 'processor affinity' in scheduling?

It improves efficiency by minimizing context switches. Signup and view all the answers

Study Notes

Scheduling Concepts

Scheduling under 1 and 4 is nonpreemptive, otherwise it's preemptive.
Access to shared data and preemption while in kernel mode must be considered.
Interrupts occurring during crucial OS activities must be considered.

Dispatcher

The dispatcher module gives control of the CPU to the selected process.
It does this by switching context, switching to user mode, and jumping to the correct location in the user program to restart it.
Dispatch latency is the time it takes to swap between processes.

Scheduling Criteria

CPU Utilization: Maximize CPU usage.
Throughput: Number of processes that complete per time unit.
Turnaround Time: Time taken to run a process from start to finish.
Waiting Time: The time a process spends waiting in the ready queue.
Response Time: For time-sharing systems, the time from request submission to receiving the first response.

Scheduling Algorithm Optimization

Aims to maximize CPU utilization and throughput.
Minimize turnaround time, waiting time, and response time.

First-Come, First-Served (FCFS)

Processes are scheduled in the order they arrive.
A "convoy effect" can occur where a short process is delayed by a long process.

Shortest-Job-First (SJF)

Schedule the process with the shortest next CPU burst.
Optimal for minimizing average waiting time.
Difficult to know the length of the next CPU request.

Round Robin (RR) Scheduling

Processes are given a time quantum.
After the quantum expires, the process is preempted and moved to the back of the ready queue.
If n processes are waiting, each process gets 1/n of the CPU time in chunks.
Time quantum should be large enough relative to the context switch time.

Multilevel Queue Scheduling

The ready queue is split into separate queues.
Each queue might have a different scheduling algorithm (like RR for foreground and FCFS for background processes).
Scheduling between queues can be done via fixed priority, time slice, or a more dynamic approach.

Multilevel Feedback Queue

Processes can move between queues to tailor scheduling to their needs.
Dynamic scheduling using various parameters, including scheduling algorithm per queue, process upgrade and demotion methods, and queue entry method.

Thread Scheduling

Can be user-level or kernel-level.
User-level thread libraries schedule threads onto LWPs (Light-Weight Processes).
Kernel-level thread scheduling provides system-contention scope.

Pthread Scheduling

Pthread API allows specifying either Process-Contention Scope (PCS) or System-Contention Scope (SCS) during thread creation.
Linux and Mac OS X typically only allow PTHREAD_SCOPE_SYSTEM (SCS).

Multiple-Processor Scheduling

CPU scheduling gets more complex with multiple CPUs.
Can be symmetric multiprocessing (SMP) or asymmetric multiprocessing.
Processor affinity can be used to bind a process to a particular processor, which can improve performance in certain scenarios.

Load Balancing

In SMP systems, load balancing is needed to distribute the workload evenly.
Push migration and pull migration approaches are used to achieve balance.

Multicore Processors

Multiple processor cores on a single chip provide faster processing and lower energy consumption.
Multiple threads per core can improve performance by utilizing idle time during memory stalls.

Real-Time CPU Scheduling

Soft Real-Time Systems: No guarantee that a critical task will be scheduled on time.
Hard Real-Time Systems: Critical tasks must meet their deadlines.
Two types of latencies that impact performance: Interrupt Latencies and Jitter.

Rate Monotonic Scheduling

Priority is assigned based on the period of a task.
Higher priority tasks are scheduled more frequently.
Can be used for hard real-time applications.

Earliest Deadline First Scheduling (EDF)

Priority is assigned based on the deadline of a task.
A task with an earlier deadline has higher priority.
Can be more efficient than rate monotonic scheduling but more complex to implement.

Shares are allocated among all processes.
An application receives N shares where N < T (total shares in the system).

POSIX Real-Time Scheduling

Defines two real-time scheduling classes:
- SCHED_FIFO: Threads are scheduled using a First-Come, First-Served strategy with a FIFO queue.
- SCHED_RR: Threads are scheduled using a round-robin strategy.

CFS Scheduling

The Completely Fair Scheduler (CFS) uses a "nice" value system from -20 to +19 to determine task priorities. Lower values indicate higher priority.
CFS calculates a target latency for each task, which represents the desired interval for the task to run at least once.
The target latency can increase if the number of active tasks increases.
CFS maintains a virtual run time (vruntime) for each task.
The vruntime value is associated with a decay factor based on the task's priority. Lower priority tasks have a higher decay rate.
A normal default priority causes the vruntime to be equal to the actual run time.
To decide which task to run next, the scheduler selects the task with the lowest vruntime.

Linux Scheduling

Linux supports real-time scheduling as defined by POSIX.1b.
Real-time tasks have static priorities.
Both real-time and normal tasks are mapped to a global priority scheme.
A "nice" value of -20 maps to a global priority of 100.
A "nice" value of +19 maps to a global priority of 139.

Windows Scheduling

Windows uses priority-based preemptive scheduling, where the highest-priority thread runs next.
The dispatcher acts as the scheduler.
Threads run until they block, use their time slice, or are preempted by a higher-priority thread.
Real-time threads can preempt non-real-time threads.
Windows employs a 32-level priority scheme, with variable classes ranging from 1 to 15 and real-time classes from 16 to 31.
Priority 0 is reserved for the memory-management thread.
A separate queue exists for each priority level.
If no runnable thread exists, an idle thread is executed.

Windows Priority Classes

The Win32 API defines multiple priority classes for processes: REALTIME_PRIORITY_CLASS, HIGH_PRIORITY_CLASS, ABOVE_NORMAL_PRIORITY_CLASS, NORMAL_PRIORITY_CLASS, BELOW_NORMAL_PRIORITY_CLASS, and IDLE_PRIORITY_CLASS.
All priority classes are variable except for REALTIME.
Within a priority class, threads have a relative priority: TIME_CRITICAL, HIGHEST, ABOVE_NORMAL, NORMAL, BELOW_NORMAL, LOWEST, and IDLE.
The combination of priority class and relative priority determines the numeric priority.
The base priority within a class is NORMAL.
If a thread's quantum expires, its priority is lowered, but never below the base priority.
If a wait occurs, the priority is boosted depending on the type of wait.
Foreground windows receive a 3x priority boost.
Windows 7 introduced User-Mode Scheduling (UMS), allowing applications to independently create and manage threads.
UMS is more efficient for managing a large number of threads.
UMS schedulers can be implemented using libraries like the C++ Concurrent Runtime (ConcRT) framework.

Solaris Scheduling

Solaris uses priority-based scheduling with six available classes:
- Time sharing (TS) – default
- Interactive (IA)
- Real time (RT)
- System (SYS)
- Fair Share (FSS)
- Fixed priority (FP)
Threads belong to one class at a time.
Each class utilizes its own specific scheduling algorithm.
Time-sharing is implemented using a multi-level feedback queue with a loadable table that system administrators can configure.
The scheduler converts class-specific priorities into a global priority for each thread.
The thread with the highest priority runs next.
Threads continue running until they block, use their time slice, or are preempted by a higher-priority thread.
If multiple threads share the same priority, Round Robin (RR) is used for selection.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Test your knowledge on the key concepts of operating system scheduling, including nonpreemptive and preemptive scheduling, dispatcher functions, and performance criteria. Familiarize yourself with important metrics such as CPU utilization, throughput, and turnaround time through this quiz.